LeetCode:200.岛屿数量

题目：

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

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

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

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

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

我先来说下深度遍历DFS的思路，岛屿这类题模板都差不多，就是要掌握BFS和DFS

大致思路：我们假设grid[i][j]这块土地，从这块土地开始进行深度遍历，上下左右四个方向去找看有没有土地，如果不是土地就返回出去，如果是土地再对这个土地进行上下左右深度遍历。

有的人可能不懂什么叫做深度遍历去搜索，其实就是类比二叉树的深度遍历去递归(这里我就写的是递归代码，迭代法用栈都是同样的道理)，二叉树无论前中后序都是深度遍历不是

他们的代码我以前序为例：

void traverse(TreeNode root) {
    // 判断 base case
    if (root == null) {
        return;
    }
    //中
    
    traverse(root.left);//左
    traverse(root.right);//右
}

而岛屿这种网格题其实就是图的遍历，在衍生就是树的遍历呗

上面我说上下左右去遍历，不就类似于二叉树左子树，右子树遍历嘛

grid就是这个网格二维数组
  DFS(grid,i-1,j);
  DFS(grid,i+1,j);
  DFS(grid,i,j-1);
  DFS(grid,i,j+1);

就拿力扣给的例1，我稍微演示一下这个递归

就这么不断递归就把为1连在一起的土地找完了，这就是一个岛屿。但是你会发现这只是我从grid[0][0]开始找的，下面我就要找grid[0][1]了，但其实grid[0][1]这个土地我之前就找过了其实，所以对于这种很密集的，我们一直这样递归去遍历会发现计算了好多重复的土地

所以在写这个题的时候就要注意两个点了，一个就是越界要退出，第二个就是我们每次找到一个土地之后，就把他置为其他数字，这里我就置为'0'了，按题意说找到土地，把他拿海覆盖了哈哈哈，这么做的好处就是，你找完一轮之后，找到的就不会是'1'了，下面你在去遍历网格发现他不是'1'土地，你就不递归去找了呗，这样不就剩了好多时间

这样的话思路就出来了：

• 递归遍历上下左右找土地
• 注意越界退出
• 找到一个，把他填了

• 遍历整个二维数组，找到岛屿，count++，count是记录岛的个数的

• 最后返回count就行

下面我给出代码：

class Solution {
public:
   void DFS(vectorchar>>& grid,int i,int j)
   {
        if(i<0||i>=grid.size()||j<0||j>=grid[0].size())//越界
        {
            return ;
        }
        if(grid[i][j]!='1')//遇到水返回
        return;
        else
        grid[i][j]='0';//把已经遍历过得置为0
        //上下左右去找    
        DFS(grid,i-1,j);
        DFS(grid,i+1,j); 
        DFS(grid,i,j-1);
        DFS(grid,i,j+1);
         
    }
    int numIslands(vectorchar>>& grid) {
        int m=grid.size();
        int n=grid[0].size();
        }
        int count=0;//计数
        for(int i=0;i
        {
            for(int j=0;j
            {
                if(grid[i][j]=='1')//如果遇到岛屿
                {
                    DFS(grid,i,j);
                    count++;
                }
            }
        }
        return count;
        }
};

 

BFS写一下：

 主循环和思路一类似，不同点是在于搜索某岛屿边界的方法不同。

• bfs 方法：
  • 借助一个队列queue，判断队列首部节点(i, j)是否未越界而且为1
    • 如果是则置'0'（删除此岛屿），并将此节点上下左右节点(i+1,j),(i-1,j),(i,j+1),(i,j-1)加入队列
    • 如果不是则跳过此节点
  • 循环pop队列首节点，直到整个队列为空，此时已经遍历完此岛屿

class Solution {
    void bfs(vectorchar>>& grid, int i, int j){
        std::queueint, int>> list;
        list.push({i, j});
        while (!list.empty()){
            auto curr = list.front();
            list.pop();
            i = curr.first, 
            j = curr.second;
            if(i >= 0 && i < grid.size() && j >= 0 && j < grid[0].size() && grid[i][j] == '1'){
                grid[i][j] = '0';
                list.push({i + 1, j});
                list.push({i - 1, j});
                list.push({i , j + 1});
                list.push({i , j - 1});
            }
        }
    }
public:
    int numIslands(vectorchar>>& grid) {
        if(grid.empty() || grid[0].empty()){
            return 0;
        }
        int ans = 0, 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'){
                    ans++;
                    bfs(grid, i, j);
                }
            }
        }
 
        return ans;
    }
};

基本就是这个样子了