day11 岛屿数量

前两天忙组会，今天继续。
不懂一点拓扑，组会前试图速通结果大失败。

读题

给你一个由 '1'（陆地）和 '0'（水）组成的的二维网格，请你计算网格中岛屿的数量。
岛屿总是被水包围，并且每座岛屿只能由水平方向和/或竖直方向上相邻的陆地连接形成。
此外，你可以假设该网格的四条边均被水包围。
输入是一个二维 vector grid，意思应该是要判断连通的 1 的个数。

思路

第一思路

首先是简单粗暴的遍历。
对于任意一个是 1 的点：向右向下搜索是否还有直接与其相连的 1；如果有，则将其标记为 0。
如果直接两个循环嵌套，时间复杂度大概是 O(nm)，n 是总数，m 是岛屿个数，也可能是 O(n^2)。

---

仔细想想，感觉有点像之前的最大正方形，做所谓动态规划，保存”状态”。在之前的最大正方形，状态是目前边长；现在，状态应该是岛屿个数？如果遇到不连通的 1，那么岛屿个数自增。或者，是岛屿的序号，记为 island_num，从 1 开始，标记目前走到了哪一个岛屿。

有什么情况会令岛屿断开？局部的话：

1, 0
0, 1(or 0)

是的，上面这种可以确定为边界；但是怎么判断这两个岛屿在其他地方不是连通的？
是否应该考虑使用树等数据结构？

---

使用一个等大的数组 island_num_matrix 标记 1 在哪一个岛屿中，一次判断一个岛屿。假设岛屿有 m 个，数有 n 个，那么需要判断 m+1 次才能遍历完成（m+1 次是判断已经全部遍历完成）。

---

按照上面的思路，例如，在该次循环中，我从左上角开始，向右下走。

• 如果当前是 1：
  • 如果 island_num 是 0，设置为 1。
  • 右边是 1 吗？若是，标记为 island_num
  • 下面是 1 吗？若是，标记为 island_num
  • 若都是，右下角的是 1 吗？若是，标记为 island_num
• 如果当前是 0，或者该位置 island_num_matrix 有值：
  • 不操作
• 向右/向下移动

然后循环 n 次。
于是有代码：

class Solution {
public:
    int numIslands(vector<vector<char>>& grid) {
        int m = grid.size();
        int n = grid[0].size();
        int island_num = 0;
        vector<vector<char>> island_num_matrix(m, vector<char>(n, 0));
        while(1){
            int last_num = island_num;
            for(int i=0;i<m;i++){
                for(int j=0;j<n;j++){
                    if(grid[i][j]=='0') continue;
                    if(i==m-1) continue;
                    if(j==n-1) continue;
                    if(island_num_matrix[i][j]!=0) continue;
                    if(last_num==island_num) island_num++;
                    
                    if(grid[i+1][j]=='1'){
                        island_num_matrix[i+1][j]=island_num;
                    }
                    if(grid[i][j+1]=='1'){
                        island_num_matrix[i][j+1]=island_num;
                    }
                    if(grid[i+1][j]=='1' && grid[i][j+1]=='1'){
                        if(grid[i+1][j+1]=='1'){
                            island_num_matrix[i+1][j+1]=island_num;
                        }
                    }
                }
            }
            if(last_num==island_num) break;
        }
        return island_num;
    }
};

---

写得什么玩意儿？
重写！

首先，向右向下判断联通是不科学不合理的。当然也可能会出现：

0, 1
1, 0

右上和左下是两个不同的岛屿。
其次，while 1 跟 last_num == island_num 真的是唐完了。
而且边界处理得也不对。
而且标记岛屿序号时也有可能重复标记。

优化后的思路

首先，联通要判断上下左右四个方向。
遍历时，如果遇到非 1 或者边界，直接跳过。
遍历过的点直接修改原矩阵感觉还省点空间；如果不想改变原矩阵，也可以复制一份矩阵来操作。因为没有为岛屿编号的任务，所以编号其实可有可无，只需要最终一个计数就可以。
可以使用递归而非循环，更简洁（大概）。
当然，外层循环还是需要的，但是不要使用 while 1，太丑陋。也没有必要使用循环岛屿次数次，直接遍历所有格子一次即可；每次把连通的全部标记为 0，然后计数器加一。
代码

class Solution {
private:
    int m, n;
    void fun(vector<vector<char>>& grid, int i, int j) {
        if (i < 0 || i >= m || j < 0 || j >= n || grid[i][j] != '1') {
            return;
        }
        grid[i][j] = '0';
        fun(grid,i+1,j);
		fun(grid,i-1,j);
		fun(grid,i,j+1);
		fun(grid,i,j-1);
		return;
    }
    
public:
    int numIslands(vector<vector<char>>& grid) {
        m = grid.size();
        if (m == 0) return 0;
        n = grid[0].size();
        int island_num = 0;
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (grid[i][j] == '1') {
                    island_num++;
                    fun(grid, i, j);
                }
            }
        }
        return island_num;
    }
};

结果

25 ms，16.00 MB 使用。时间复杂度 空间复杂度 均为 O(mn)。

官方题解

我好像逐渐理解 dfs 和 bfs 了。
两种不同的思考方式，解决的问题是同一类。

方法一：深度优先搜索

是的，我的做法就是 dfs。遍历矩阵中所有点，以此点为新根，出发进行搜索。

方法二：广度优先搜索

题解语：
同样地，我们也可以使用广度优先搜索代替深度优先搜索。
为了求出岛屿的数量，我们可以扫描整个二维网格。如果一个位置为 1，则将其加入队列，开始进行广度优先搜索。在广度优先搜索的过程中，每个搜索到的 1 都会被重新标记为 0。直到队列为空，搜索结束。
最终岛屿的数量就是我们进行广度优先搜索的次数。

有代码：

class Solution {
public:
    int numIslands(vector<vector<char>>& grid) {
        int nr = grid.size();
        if (!nr) return 0;
        int nc = grid[0].size();

        int num_islands = 0;
        for (int r = 0; r < nr; ++r) {
            for (int c = 0; c < nc; ++c) {
                if (grid[r][c] == '1') {
                    ++num_islands;
                    grid[r][c] = '0';
                    queue<pair<int, int>> neighbors;
                    neighbors.push({r, c});
                    while (!neighbors.empty()) {
                        auto rc = neighbors.front();
                        neighbors.pop();
                        int row = rc.first, col = rc.second;
                        if (row - 1 >= 0 && grid[row-1][col] == '1') {
                            neighbors.push({row-1, col});
                            grid[row-1][col] = '0';
                        }
                        if (row + 1 < nr && grid[row+1][col] == '1') {
                            neighbors.push({row+1, col});
                            grid[row+1][col] = '0';
                        }
                        if (col - 1 >= 0 && grid[row][col-1] == '1') {
                            neighbors.push({row, col-1});
                            grid[row][col-1] = '0';
                        }
                        if (col + 1 < nc && grid[row][col+1] == '1') {
                            neighbors.push({row, col+1});
                            grid[row][col+1] = '0';
                        }
                    }
                }
            }
        }

        return num_islands;
    }
};

有点无法理解。笨脑瓜子。
大概就是先记录，吊着不搜，之后再回过头来慢慢搜？感觉空间复杂度可能比较高？

---

过程大致是：

1. 遍历，将为 1 的点入队
2. 遍历完成后，

方法三：并查集

太神奇了并查集。