number of island

key point: 1) use flag to record whether a single cell has been gone through; 2) when it goes to a new island, add 1 to the result, and set all its connected cell to be flag true;

code

class Solution {
public:
    int numIslands(vector<vector<char>>& grid) {
        int m = grid.size();
        if(m == 0)
        {
            return 0;
        }

        int n = grid[0].size();

        int ret = 0;
        vector<vector<bool>> flag(m, vector<bool>(n, false));

        for(int i = 0 ; i<m; i++)
        {
           for(int j = 0; j<n; j++)
           {
               if(flag[i][j] == true || grid[i][j] == '0')
               {
                   continue;
               }

               ret++;
               dfs(grid, flag, i, j);
           }
        }

        return ret;
    }

    void dfs(vector<vector<char>>& grid, vector<vector<bool>>& flag, int x, int y)
    {
        int m = grid.size();
        int n = grid[0].size();

        if(x < 0 || x >= m || y < 0 || y >= n || flag[x][y] == true || grid[x][y] == '0')
        {
            return ;
        }

        flag[x][y] = true;

        int dx[] = {0, 1, 0, -1};
        int dy[] = {1, 0, -1, 0};

        for(int i = 0; i<4; i++)
        {
            int nx = x + dx[i];
            int ny = y + dy[i];
            dfs(grid, flag, nx, ny);
        }

    }
};