leetcode200. 岛屿数量

分析

dfs

遍历图的每个位置，如果这个点为1说明这里有一个岛屿，ans++，同时从这个点向四个方向开始dfs，将相邻的点全都置为0，此次dfs结束。

class Solution {
public:
    void dfs(int x,int y,vector<vector<char>>& grid){
        int m=grid.size(),n=grid[0].size();
        int dx[4]={-1,0,1,0},dy[4]={0,1,0,-1};
        for(int i=0;i<4;i++){
            int xx=x+dx[i],yy=y+dy[i];
            if(xx>=0&&xx<m&&yy>=0&&yy<n&&grid[xx][yy]=='1'){
                grid[xx][yy]='0';
                dfs(xx,yy,grid);
            }
        }
    }
    int numIslands(vector<vector<char>>& grid) {
        int ans=0;
        int m=grid.size(),n=grid[0].size();
        for(int i=0;i<m;i++){
            for(int j=0;j<n;j++){
                if(grid[i][j]=='1'){
                    dfs(i,j,grid);
                    ans++;
                }
            }
        }
        return ans;
    }
};