题目描述

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

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

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

示例 1：

1
2
3
4
5
6
7
输入：grid = [
  ["1","1","1","1","0"],
  ["1","1","0","1","0"],
  ["1","1","0","0","0"],
  ["0","0","0","0","0"]
]
输出：1

具体见题目详解。

算法思路

最开始这个题目我还想用dp去解，大概思路是：

  1. 对于每一个坐标i,j如果grid[i]\[j] = '1',如果左边、上边均为水域，那么就让ans += 1
  2. 如果左边是陆地，那么就需要满足dp[i][j] = mind(p[i][j-1], ans)，最后让ans = dp[i][j]，这样是为了防止出现“工”字形的陆地造成的影响。同理，上边是陆地也需要这样处理，尽可能的把陆地合并

但是这样处理太复杂了，也不方便理解，后来突然想到一个奇妙的想法，我们加入陆地上有一个互相连通的水渠，如果有一个水渠进水了，那么毫无疑问，水会沿着水渠最终遍布整个陆地，这是不是相当于一种搜索策略，也就是DFS或BFS，因此最终我选择了DFS解决这个问题，算法思路如下：

  1. 对于每个没有“登陆”的陆地，我们以其为中心向四个方向搜索，并把搜索到的陆地都标记为“已登陆”，对于四个方向的陆地均作一样的处理
  2. 最终最大连通陆地的数量就是岛屿的数量，其实有一点点并查集的味道，只不过我不会想用并查集……

代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
#include <iostream>
#include <vector>
using namespace std;
int dir[4][4] = {{0, 1}, {1, 0}, {0, -1}, {-1, 0}};
class Solution {
    bool isValid(int m, int n, int x, int y) {
        if (x < 0 || y < 0 || x >= m || y >= n) {
            return false;
        }
        return true;
    }
    void dfs(int m, int n, int x, int y, vector< vector<char> >& grid) {
        visited[x][y] = 1;
        for (auto sdir : dir) {
            int tmpx = x + sdir[0];
            int tmpy = y + sdir[1];
            if (isValid(m, n, tmpx, tmpy) && !visited[tmpx][tmpy] && grid[tmpx][tmpy] == '1') {
                dfs(m, n, x + sdir[0], y + sdir[1], grid);
            }
        }
    }

public:
    int ans;
    vector< vector<int> > visited;
    int numIslands(vector< vector<char> >& grid) {
        int m = grid.size();
        int n = grid[0].size();
        visited.resize(m);
        for (int i = 0; i < m; i++) {
            visited[i].resize(n, 0);
        }
        for (int i = 0; i < m; i ++) {
            for (int j = 0; j < n; j++) {
                if (grid[i][j] == '1' && !visited[i][j]) {
                    ans += 1;
                    dfs(m, n, i, j, grid);
                }
            }
        }
        return ans;
    }
};

运行结果还算满意，效率还可以：

截屏2025-02-01 13.38.48

官方题解给出了DFS、BFS、并查集三种做法，感兴趣可以自行查看。