题解 | #岛屿数量#

/*
简单的dfs问题，遍历图中的每个点，如果是是非‘0’点，
则以此点为根节点，沿四个方向搜索它的所有子节点，并把它的子节点置为‘0’
保证不会重复搜索
*/
class Solution {
private:
    int n,m;
    void dfs(int x,int y, vector<vector<char>>& grid){
        //左
        if(y-1>=0&&grid[x][y-1]!='0')grid[x][y-1]='0',dfs(x,y-1,grid);
        //右
        if(y+1<m&&grid[x][y+1]!='0')grid[x][y+1]='0',dfs(x,y+1,grid);
        //上
        if(x-1>=0&&grid[x-1][y]!='0')grid[x-1][y]='0',dfs(x-1,y,grid);
        //下
        if(x+1<n&&grid[x+1][y]!='0')grid[x+1][y]='0',dfs(x+1,y,grid);
    }
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 判断岛屿数量
     * @param grid char字符型vector<vector<>> 
     * @return int整型
     */
    int solve(vector<vector<char> >& grid) {
        // write code here
        n=grid.size();
        m=grid[0].size();
        int cnt=0;
        for(int i=0;i<n;++i){
            for(int j=0;j<m;++j){
                if(grid[i][j]!='0'){
                    grid[i][j]='0';
                    ++cnt;
                    dfs(i,j,grid);
                }
            }
        }
        return cnt;
    }
};