NC109

class Solution {
public:
    /**
     * 判断岛屿数量
     * @param grid char字符型vector<vector<>> 
     * @return int整型
     */
    int solve(vector<vector<char> >& grid) {
        // write code here

        int cnt = 0;
        for(int i = 0; i < grid.size(); i++){
            for(int j = 0; j < grid[0].size(); j++){
                if(grid[i][j] == '1'){
                    cnt++;
                    dfs(grid, i, j);
                }
            }
        }
        return cnt;
    }
    void dfs(vector<vector<char> >& grid, int x, int y){
        //上下右四个方向
        int dx[] = {0, 0, -1, 1}; 
        int dy[] = {-1, 1, 0, 0};
        grid[x][y] = '0'; //走过的路记0
        for(int i = 0; i < 4; i++){
            int tx = x + dx[i];
            int ty = y + dy[i];
            //超出边界
            if(tx < 0 || ty < 0 || tx >= grid.size() || ty >= grid[0].size()){
                continue;
            }
            if(grid[tx][ty] == '1'){
                dfs(grid, tx, ty);
            }
        }
    }

};
#学习路径#