LeetCode-200-岛屿数量

给定一个由 ‘1’（陆地）和 ‘0’（水）组成的的二维网格，计算岛屿的数量。一个岛被水包围，并且它是通过水平方向或垂直方向上相邻的陆地连接而成的。你可以假设网格的四个边均被水包围。

示例 1:

输入:
11110
11010
11000
00000

输出: 1

示例 2:

输入:
11000
11000
00100
00011

输出: 3

Code

//思路：遍历二维数组，遇到为1的就利用dfs向四周扩散，将该岛沉没，并将岛数量加1
class Solution {
public:
    int numIslands(vector<vector<char>>& grid) {
        int count=0;
        int i,j;
        //从左至右，从上到下遍历数组
        for(i=0;i<grid.size();i++){
            for(j=0;j<grid[0].size();j++){
                //遇到1就沉没这个小岛，计数+1
                if(grid[i][j]=='1'){
                    count++;
                    //递归的沉没小岛
                    DFS(i,j,grid);
                }
            }
        }

        return count;
    }

    void DFS(int row,int col,vector<vector<char>>& grid){
        if(row<0||row>=grid.size()||col<0||col>=grid[row].size()||grid[row][col]=='0')
            return;
        //沉没
        grid[row][col]='0';
        //上
        DFS(row-1,col,grid);
        //下
        DFS(row+1,col,grid);
        //左
        DFS(row,col-1,grid);
        //右
        DFS(row,col+1,grid);
    }
};