题目

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

示例 1:

输入:
11110
11010
11000
00000
输出: 1

示例 2:
输入:
11000
11000
00100
00011
输出: 3

解题思路

使用DFS深度优先算法

代码

class Solution {
public:
    int numIslands(vector<vector<char>>& grid) {
        if(grid.size() == 0) return 0;
        vector<vector<char>> temp = grid;
        int count = 0;
        for(int i=0; i < temp.size(); i++){   //遍历grid
            for(int j=0; j < temp[0].size(); j++){
                if(temp[i][j] == '1'){    //如果发现是‘1’，那么找到边缘，这样就访问了一个land
                    visitland(temp, i, j); //访问一个land
                    count++;
                }
            }
        }
        
        return count;
    }
    
    void visitland(vector<vector<char>>& grid, int i, int j){
        if(i >= 0 && j >= 0 && i < grid.size() && j < grid[0].size()){
            if(grid[i][j] == '1'){
                grid[i][j] = '0';  //把访问过的变为'0'，表示已经访问过了
                visitland(grid, i+1, j);
                visitland(grid, i-1, j);
                visitland(grid, i, j+1);
                visitland(grid, i, j-1);
            }
        }
    }
};