Leetcoe 200. 島の個数C++深さ優先探索

タイトルの説明
「1」(陸地)と「0」(水)からなる2次元メッシュを与え,島の数を計算した.1つの島は水に囲まれ、水平方向または垂直方向に隣接する陸地で接続されている.グリッドの4つのエッジが水で囲まれていると仮定できます.
例1:

  :
11110
11010
11000
00000
  : 1

例2:

  :
11000
11000
00100
00011
  : 3

に答える
本題の構想とLeetcode 79.単語検索C++(深さ優先検索&&遡及)の方法は同じです.深さ優先探索を使用して、所与のマトリクスgridのいずれかの位置の値が’1’であり、陸地であることを示す場合、深さ優先探索アルゴリズムを使用して、それに接続された陸地のすべてのタグを付ける.これで島が手に入ります.これにより,所与の行列gridを遍歴すると答えが得られる.注意:最初はgridの陸地が使用されたかどうかをマークするために同じ大きさのflag行列を申請するつもりです.しかし、実際には使わず、grid[i][j]の値を直接変更すればマークできることが分かった.

class Solution {
public:
    int numIslands(vector<vector<char>>& grid) {
        if(grid.empty()) return 0;//           
        int row=grid.size(), column=grid[0].size();
        //vector> flag(row,vector(column,0));
        int count=0;
        for(int i=0;i<row;++i)
        {
            for(int j=0;j<column;++j)
            {
                if(grid[i][j]=='1')
                {
                    count++;
                    grid[i][j]='2';//   2           
                    dfs(grid,i,j);
                }
            }
        }
        return count;
    }
   void dfs(vector<vector<char>> &grid, int i, int j)
    {
        if(j+1<grid[0].size() && grid[i][j+1]=='1')
        {
            grid[i][j+1]='2';
            dfs(grid,i,j+1);
        }
        if(i+1<grid.size() && grid[i+1][j]=='1')
        {
            grid[i+1][j]='2';
            dfs(grid,i+1,j);
        }
       if(j-1>=0 && grid[i][j-1]=='1')
       {
           grid[i][j-1]='2';
           dfs(grid,i,j-1);
       }
       if(i-1>=0 && grid[i-1][j]=='1')
       {
           grid[i-1][j]='2';
           dfs(grid,i-1,j);
       }
    }
};