博客

1.题目如下：

给你一个由 ‘1’（陆地）和 ‘0’（水）组成的的二维网格，请你计算网格中岛屿的数量。

岛屿总是被水包围，并且每座岛屿只能由水平方向和/或竖直方向上相邻的陆地连接形成。

此外，你可以假设该网格的四条边均被水包围。

示例 1：

输入：grid = [
  ["1","1","1","1","0"],
  ["1","1","0","1","0"],
  ["1","1","0","0","0"],
  ["0","0","0","0","0"]
]
输出：1

示例 2：

输入：grid = [
  ["1","1","0","0","0"],
  ["1","1","0","0","0"],
  ["0","0","1","0","0"],
  ["0","0","0","1","1"]
]
输出：3

提示：

m == grid.length

n == grid[i].length

1 <= m, n <= 300

grid[i][j] 的值为 ‘0’ 或 ‘1’

2.代码如下：

class Solution {
public:
//思路一：经典的回溯、dfs
/**广度遍历所有能够相连的点连成岛屿，并标记被遍历过的点。*/

    int numIslands(vector<vector<char>>& grid) {
        /**mark用来记录已经被遍历过的元素*/
        vector<vector<int>> mark(grid.size(),vector<int>(grid[0].size(),0));
        vector<pair<int,int>> s={{-1,0},{0,-1},{0,1},{1,0}};
        int num=0;
        for(int i=0;i<grid.size();i++){
            for(int j=0;j<grid[0].size();j++){
                if(grid[i][j]=='1' && mark[i][j]==0){
                    bp(grid,s,mark,num,i,j);
                    num++;
                }
            }
        }
        return num;
    }

    void bp(vector<vector<char>>& grid,vector<pair<int,int>> &s, vector<vector<int>> &mark,int &num,int i,int j){
        if(grid[i][j]=='0'){
            return ;
        }
        else if(mark[i][j]==1){
            return ;
        }
        mark[i][j]=1;
        for(auto x:s){
            int newI=x.first+i;
            int newJ=x.second+j;
            if(newI>=0 && newI<grid.size() && newJ>=0 && newJ<grid[0].size()){
                bp(grid,s,mark,num,newI,newJ);
            }
        }
    }
};