网格结构问题集锦

发表于 Artalk： loading...
深度优先搜索 广度优先搜索 并查集

集中记录一下涉及在网格结构上搜索的题目及其各种解法，例如各种「岛屿」问题

前言

这里的网格结构，也可以称为棋盘结构，在其之上做搜索跟图结构很像，本文做一次简单总结

在网格结构上搜索时，有些细节需要注意

以下，mm 表示网格的纵向长度，nn 表示网格的横向高度，即网格尺寸 m×nm\times n

坐标移动

对于任何一点 (i,j)(i, j) ，从此出发的搜索方向有四种：上、下、左、右，在代码实现上，目前自己使用的有两种方式

第一种

搜索方向的顺序依次是上、右、下、左

1
2
3
4
5
6
7
static final int[][] dirs  = new int[][]{{-1,0}, {1,0}, {0, 1}, {0, -1}};
//...
int x0 = 1, y0 = 2;
for (int[] dir : dirs) {
    int xx = x0 + dir[0];
    int yy = x0 + dir[1];
}

第二种

改用一维数组，更省空间

1
2
3
4
5
6
7
static final int[] dirs = new int[]{0, -1, 0, 1, 0};
//...
int x0 = 1, y0 = 2;
for (int i = 0; i < 4; ++i) {
    int xx = x0 + dirs[i];
    int yy = y0 + dirs[i + 1];
}

边界控制

保证坐标在合法范围内，x∈[0,m)x\isin[0,m) ，y∈[0,n)y\isin[0,n)

1
2
3
boolean valid(int m, int n, int x, int y) {
    return x >= 0 && x < m && y >= 0 && y < n;
}

访问控制

搜索的时候，可能会搜索到重复（已经遍历过的）的陆地，需要通过一些标识来避免重复访问

  1. 可以改变网格数组 grid 的值，用 2 表示已经遍历过的陆地，则 1 表示尚未遍历的陆地，0表示海洋
  2. 或者新建一个二维数组 st[m][n] 来保存每个网格的访问状态，这样会有额外开销

如何选取需要结合题目要求具体分析

200. 岛屿数量

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

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

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

示例

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

简要分析

如果把彼此相连的1视作一个连通块的话，求岛屿的数量就相当于求网格结构中连通块的数量。这样首先想到的，其实是用并查集去做。

深度优先搜索

DFS采用递归实现，代码比较简短。

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
class Solution {
    static final int[][] dirs = new int[][]{{-1,0}, {0,1}, {1,0}, {0,-1}};
    int m, n;
    public int numIslands(char[][] grid) {
        int res = 0;
        m = grid.length; n = grid[0].length;

        for (int i = 0; i < m; ++i) {
            for (int j = 0; j < n; ++j) {
                if (grid[i][j] == '1') {
                    dfs(i, j, grid);
                    res++;
                }
            }
        }
        return res;
    }
    public void dfs(int x, int y, char[][] grid) {
        grid[x][y] = '2';
        for (int[] dir : dirs) {
            int xx = x + dir[0], yy = y + dir[1];
            if (xx >= 0 && xx <m && yy >= 0 && yy < n && grid[xx][yy] == '1') {
                dfs(xx, yy, grid);
            }
        }
    }
}

广度优先搜索

BFS同深搜一样，都是从某块陆地出发向四周搜索，直到到达海洋或者边界，一轮结束，则连通块数量加一，即岛屿数量加一

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
class Solution {
    static final int[][] dirs  = new int[][]{{-1,0}, {1,0}, {0, 1}, {0, -1}};
    int m, n;
    public int numIslands(char[][] grid) {
        m = grid.length;
        n = grid[0].length;
        int res = 0;
        for (int i = 0; i < m; ++i) {
            for (int j = 0; j < n; ++j) {
                if (grid[i][j] == '1') {
                    bfs(grid, i, j);
                    res++;
                }
            }
        }
        return res;
    }
    void bfs(char[][] grid, int x, int y) {
        grid[x][y] = '2';
        Queue<int[]> q = new LinkedList<>();
        q.offer(new int[]{x, y});
        while (!q.isEmpty()) {
            int[] cur = q.poll();
            int x0 = cur[0], y0 = cur[1];
            for (int[] dir : dirs) {
                int xx = x0 + dir[0], yy = y0 + dir[1];
                if (xx >= 0 && xx < m && yy >= 0 && yy < n && grid[xx][yy] == '1') {
                    q.offer(new int[]{xx, yy});
                    grid[xx][yy] = '2';
                }
            }
        }
    }
}

并查集

并查集天生就是用来求连通块数量这种问题

从某个1陆地出发，分别向右侧、下方合并相邻的陆地即可

为什么只合并右边和下方的陆地呢？

因为整体的遍历顺序是外层 i→[0,m)i\to[0,m) ，内层 j→[0,n)j\to [0,n) ，每次向右下合并，就可以保证所有的相邻陆地都可以被合并到一起

在合并的过程中，统计遇到的海洋网格数量 oceanCnt ，每将一个新的陆地合并进当前的连通块，总网格数量 allCnt 减一，最终的 allCnt-oceanCnt 就是连通块的数量

代码实现上，一般是用 idx=i∗n+jidx=i * n + j 表示当前坐标 (i,j)(i,j) ，这样所有的坐标都可以用一个整数唯一标识，不会冲突

数组模拟的并查集

包含了路径压缩和按秩合并

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
44
45
46
47
48
49
50
class Solution {
    static final int N = 100000;
    static int[] p = new int[N];
    static int[] rank = new int[N];
    public int find(int u) {
        if (p[u] != u) p[u] = find(p[u]);
        return p[u];
    }

    // 属于同一个连通块则返回true
    public boolean union(int x, int y) {
        int xx = find(x), yy = find(y);
        if (xx == yy) return true;
        if (rank[xx] <= rank[yy]) p[xx] = yy;
        else p[yy] = xx;
        if (rank[xx] == rank[yy]) rank[yy]++;
        return false;
    }

    public int numIslands(char[][] grid) {
        // 尝试并查集做法
        int m = grid.length, n = grid[0].length;
        for (int i = 0; i < m; ++i) {
            for (int j = 0; j < n; ++j) {
                int idx = i * n + j;
                rank[idx] = 1;
                p[idx] = idx;
            }
        }
        // 向右下合并
        int allCnt = m * n, oceanCnt = 0;
        for (int i = 0; i < m; ++i) {
            for (int j = 0; j < n; ++j) {
                if (grid[i][j] == '0') {
                    oceanCnt++; continue;
                }
                else {
                    int cur = i * n + j;
                    if (j + 1 < n && grid[i][j + 1] == '1') {
                        if (!union(cur, i * n + j + 1)) allCnt--;
                    }
                    if (i + 1 < m && grid[i + 1][j] == '1') {
                        if (!union(cur, (i + 1) * n + j)) allCnt--;
                    }
                }
            }
        }
        return allCnt - oceanCnt;
    }
}

java内部类实现的并查集

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
44
45
46
47
48
49
50
51
class Solution {
    class DSU {
        int[] p, rank;
        int cnt;
        public DSU(int n) {
            this.p = new int[n];
            this.rank = new int[n];
            for (int i = 0; i < n; ++i) {
                p[i] = i;
                rank[i] = 1;
            }
            this.cnt = n;
        }
        int find(int u) {
            if (p[u] != u) p[u] = find(p[u]);
            return p[u];
        }
        void union(int x, int y) {
            int xx = find(x), yy = find(y);
            if (xx == yy) return; 
            this.cnt--;
            if (rank[xx] <= rank[yy]) p[xx] = yy;
            else p[yy] = xx;
            if (rank[xx] == rank[yy]) rank[yy]++;
        }
    }

    public int numIslands(char[][] grid) {
        // 尝试并查集做法
        int m = grid.length, n = grid[0].length;
        DSU dsu = new DSU(m * n);
        // 向右下合并
        for (int i = 0; i < m; ++i) {
            for (int j = 0; j < n; ++j) {
                if (grid[i][j] == '0') {
                    dsu.cnt--; continue;
                }
                else {
                    int cur = i * n + j;
                    if (j + 1 < n && grid[i][j + 1] == '1') {
                        dsu.union(cur, i * n + j + 1);
                    }
                    if (i + 1 < m && grid[i + 1][j] == '1') {
                        dsu.union(cur, (i + 1) * n + j);
                    }
                }
            }
        }
        return dsu.cnt;
    }
}

827. 最大人工岛

本题属于 200.岛屿数量 的进阶题目

给你一个大小为 n x n 二进制矩阵 grid 。最多 只能将一格 0 变成 1 。

返回执行此操作后，grid 中最大的岛屿面积是多少？

岛屿 由一组上、下、左、右四个方向相连的 1 形成。

示例

1
2
3
输入: grid = [[1, 0], [0, 1]]
输出: 3
解释: 将一格0变成1，最终连通两个小岛得到面积为 3 的岛屿。

简要分析

大致思路是，先遍历所有的陆地，得到所有的连通块（岛屿）的大小，并保存下来；再搜索海洋网格，如果相邻周围有不同连通块，则尝试将当前海洋变成陆地，比较新岛屿的面积

  1. 具体实现上，需要在搜索过程中，记录当前陆地所属连通块的编号

新建一个二维数组 int[][] tag ，存储当前陆地的连通块编号，并且还可以起到访问控制的作用：如果 tag[x][y] != 0 说明陆地 (x,y)尚未被访问到

为避免含义模糊，对于坐标的整数标识，就需要从 11 开始计算，idx=i∗n+j+1idx = i * n + j + 1 ，nn 为网格的横向长度

  1. 搜索海洋时，需要创建一个临时的哈希集合，来判断相邻的岛屿是否为同一个

下面是代码实现

深度优先搜索

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
44
45
46
47
48
49
50
51
52
53
54
55
56
57
class Solution {
    static final int[] dirs = new int[]{0, -1, 0, 1, 0};
    public int largestIsland(int[][] grid) {
        // dfs 
        int n = grid.length;
        int[][] tag = new int[n][n];
        int res = 0;
        Map<Integer, Integer> area = new HashMap<>();
        for (int i = 0; i < n; ++i) {
            for (int j = 0; j < n; ++j) {
                if (grid[i][j] == 1 && tag[i][j] == 0) { // 防止重复访问
                    int curIdx = i * n + j + 1; // idx 从1开始
                    int curArea = dfs(grid, tag, i, j, curIdx);
                    area.put(curIdx, curArea); // 存储当前连通块的大小
                    res = Math.max(res, curArea); // 比较结果
                }
            }
        }
        for (int i = 0; i < n; ++i) {
            for (int j = 0; j < n; ++j) {
                if (grid[i][j] == 0) {
                    int curIdx = i * n + j + 1; // idx 从1开始
                    int cur = 1;
                    Set<Integer> set = new HashSet<>(); // 来存储当前海洋周围的岛屿编号
                    for (int k = 0; k < 4; ++k) {
                        int x = i + dirs[k], y = j + dirs[k + 1];
                        if (valid(n, x, y) && grid[x][y] == 1) {
                            int idx = tag[x][y];
                            if (set.contains(idx)) continue; // 如果是相同岛屿，则跳过
                            cur += area.get(idx);
                            set.add(idx);
                        }
                    }
                    res = Math.max(res, cur);
                }
            }
        }
        return res;
    }
    int dfs(int[][] grid, int[][] tag, int x, int y, int idx) {
        int res = 1, n = grid.length;
        tag[x][y] = idx;
        for (int k = 0; k < 4; ++k) {
            int xx = x + dirs[k], yy = y + dirs[k + 1];
            // tag[][] 数组有俩作用
            // 1. 标记当前陆地属于哪块岛屿
            // 2. 标记当前陆地是否被访问过
            if (valid(n, xx, yy) && grid[xx][yy] == 1 && tag[xx][yy] == 0) {
                res += dfs(grid, tag, xx, yy, idx);
            }
        }
        return res;
    }
    boolean valid(int n, int x, int y) {
        return x >= 0 && x < n && y >= 0 && y < n;
    }
}

广度优先搜索

主体代码和深搜没有什么区别，这里主要放出BFS部分代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
int bfs(int[][] grid, int[][] tag, int x, int y, int idx) {
    int n = grid.length, res = 0;
    tag[x][y] = idx;
    Queue<int[]> q = new LinkedList<>();
    q.offer(new int[]{x, y});
    while (!q.isEmpty()) {
        int[] loc = q.poll();
        res++;
        for (int i = 0; i < 4; ++i) {
            int xx = loc[0] + dirs[i], yy = loc[1] + dirs[i + 1];
            if (valid(n, xx, yy) && tag[xx][yy] == 0 && grid[xx][yy] == 1) {
                q.offer(new int[]{xx, yy});
                tag[xx][yy] = idx;
            }
        }
    }
    return res;
}

BFS方案完整代码

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
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
class Solution {
    static final int[] dirs = new int[]{0, -1, 0, 1, 0};
    public int largestIsland(int[][] grid) {
        // BFS 
        int n = grid.length;
        int[][] tag = new int[n][n];
        int res = 0;
        Map<Integer, Integer> area = new HashMap<>();
        for (int i = 0; i < n; ++i) {
            for (int j = 0; j < n; ++j) {
                if (grid[i][j] == 1 && tag[i][j] == 0) { // 防止重复访问
                    int curIdx = i * n + j + 1; // idx 从1开始
                    int curArea = bfs(grid, tag, i, j, curIdx);
                    area.put(curIdx, curArea);
                    res = Math.max(res, curArea);
                }
            }
        }
        for (int i = 0; i < n; ++i) {
            for (int j = 0; j < n; ++j) {
                if (grid[i][j] == 0) {
                    int curIdx = i * n + j + 1; // idx 从1开始
                    int cur = 1;
                    Set<Integer> set = new HashSet<>(); // 来存储当前海洋周围的岛屿编号
                    for (int k = 0; k < 4; ++k) {
                        int x = i + dirs[k], y = j + dirs[k + 1];
                        if (valid(n, x, y) && grid[x][y] == 1) {
                            int idx = tag[x][y];
                            if (set.contains(idx)) continue; 
                            cur += area.get(idx);
                            set.add(idx);
                        }
                    }
                    res = Math.max(res, cur);
                }
            }
        }
        return res;
    }
    int bfs(int[][] grid, int[][] tag, int x, int y, int idx) {
        int n = grid.length, res = 0;
        tag[x][y] = idx;
        Queue<int[]> q = new LinkedList<>();
        q.offer(new int[]{x, y});
        while (!q.isEmpty()) {
            int[] loc = q.poll();
            res++;
            for (int i = 0; i < 4; ++i) {
                int xx = loc[0] + dirs[i], yy = loc[1] + dirs[i + 1];
                if (valid(n, xx, yy) && tag[xx][yy] == 0 && grid[xx][yy] == 1) {
                    q.offer(new int[]{xx, yy});
                    tag[xx][yy] = idx;
                }
            }
        }
        return res;
    }
    boolean valid(int n, int x, int y) {
        return x >= 0 && x < n && y >= 0 && y < n;
    }
}

并查集

并查集应该是本题最优解，多增添一个cnt数组，在合并的时候处理一下，就可以保存每一个连通块的大小，即岛屿的面积

并查集的代码实现

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
class DSU {
    int[] p, rank, cnt;
    public DSU(int n) {
        this.p = new int[n];
        this.rank = new int[n];
        this.cnt = new int[n];
        for (int i = 0; i < n; ++i) {
            p[i] = i;
            rank[i] = 1;
            cnt[i] = 1;
        }
    }
    int find(int u) {
        if (p[u] != u) p[u] = find(p[u]);
        return p[u];
    }
    void unite(int a, int b) {
        int pa = find(a), pb = find(b);
        if (pa == pb) return ;
        if (rank[pa] <= rank[pb]) {
            p[pa] = pb;
            cnt[pb] += cnt[pa];
        }
        else {
            p[pb] = pa;
            cnt[pa] += cnt[pb];
        }
        if (rank[pa] == rank[pb]) rank[pb]++;
    }
    int getCnt(int root) {
        return this.cnt[find(root)];
    }
}

并查集方案完整代码

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
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
class Solution {
    class DSU {
        int[] p, rank, cnt;
        public DSU(int n) {
            this.p = new int[n];
            this.rank = new int[n];
            this.cnt = new int[n];
            for (int i = 0; i < n; ++i) {
                p[i] = i;
                rank[i] = 1;
                cnt[i] = 1;
            }
        }
        int find(int u) {
            if (p[u] != u) p[u] = find(p[u]);
            return p[u];
        }
        void unite(int a, int b) {
            int pa = find(a), pb = find(b);
            if (pa == pb) return ;
            if (rank[pa] <= rank[pb]) {
                p[pa] = pb;
                cnt[pb] += cnt[pa];
            }
            else {
                p[pb] = pa;
                cnt[pa] += cnt[pb];
            }
            if (rank[pa] == rank[pb]) rank[pb]++;
        }
        int getCnt(int root) {
            return this.cnt[find(root)];
        }
    }
    static final int[] dirs = new int[]{0, -1, 0, 1, 0};
    public int largestIsland(int[][] grid) {
        int m = grid.length, n = grid[0].length;
        DSU dsu = new DSU(m * n);
        // 先合并岛屿
        for (int i = 0; i < m; ++i) {
            for (int j = 0; j < n; ++j) {
                if (grid[i][j] == 1) {
                    int cur = i * n + j;
                    if (j + 1 < n && grid[i][j + 1] == 1) dsu.unite(cur, i * n + j + 1);
                    if (i + 1 < m && grid[i + 1][j] == 1) dsu.unite(cur, (i + 1) * n + j);
                }
            }
        }
        int res = 0;
        for (int i = 0; i < m; ++i) {
            for (int j = 0; j < n; ++j) {
                if (grid[i][j] == 1) {
                    res = Math.max(res, dsu.getCnt(i * n + j));
                    continue;
                }
                int tmp = 1; // 如果当前是海洋，尝试进行转换
                Set<Integer> set = new HashSet<>();
                for (int k = 0; k < 4; ++k) {
                    int x = i + dirs[k], y = j + dirs[k + 1];
                    if (valid(m, n, x, y) && grid[x][y] == 1) {
                        int idx = x * n + y;
                        int root = dsu.find(idx);
                        if (set.contains(root)) continue;
                        tmp += dsu.getCnt(idx);
                        set.add(root);
                    }
                }
                res = Math.max(res, tmp);
            }
        }
        return res;
    }
    public boolean valid(int m, int n, int x, int y) {
        return x >= 0 && x < m && y >= 0 && y < n;
    }
}

接下来放几道简单的网格结构题目

其他例题

695. 岛屿的最大面积

给你一个大小为 m x n 的二进制矩阵 grid 。

岛屿 是由一些相邻的 1 (代表土地) 构成的组合，这里的「相邻」要求两个 1 必须在 水平或者竖直的四个方向上 相邻。你可以假设 grid 的四个边缘都被 0（代表水）包围着。

岛屿的面积是岛上值为 1 的单元格的数目。

计算并返回 grid 中最大的岛屿面积。如果没有岛屿，则返回面积为 0 。

示例：

图片来自Leetcode

1
2
3
输入：grid = [[0,0,1,0,0,0,0,1,0,0,0,0,0],[0,0,0,0,0,0,0,1,1,1,0,0,0],[0,1,1,0,1,0,0,0,0,0,0,0,0],[0,1,0,0,1,1,0,0,1,0,1,0,0],[0,1,0,0,1,1,0,0,1,1,1,0,0],[0,0,0,0,0,0,0,0,0,0,1,0,0],[0,0,0,0,0,0,0,1,1,1,0,0,0],[0,0,0,0,0,0,0,1,1,0,0,0,0]]
输出：6
解释：答案不应该是 11 ，因为岛屿只能包含水平或垂直这四个方向上的 1 。

解题思路跟之前200.岛屿数量如出一辙，不再赘述

DFS方案代码

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
class Solution {
    static final int[] dirs = new int[]{0, -1, 0, 1, 0};
    int m, n;
    public int maxAreaOfIsland(int[][] grid) {
        m = grid.length; n = grid[0].length;
        int res = 0;
        for (int i = 0; i < m; ++i) {
            for (int j = 0; j < n; ++j) {
                if (grid[i][j] == 1) res = Math.max(res, dfs(grid, i, j));
            }
        }
        return res;
    }
    int dfs(int[][] grid, int x, int y) {
        int res = 1;
        grid[x][y] = 2;
        for (int i = 0; i < 4; ++i) {
            int xx = x + dirs[i], yy = y + dirs[i + 1];
            if (xx >= 0 && xx < m && yy >= 0 && yy < n && grid[xx][yy] == 1) {
                res += dfs(grid, xx, yy);
            }
        }
        return res;
    }
}

BFS方案代码

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
class Solution {
    static final int[] dirs = new int[]{0, -1, 0, 1, 0};
    int m, n;
    public int maxAreaOfIsland(int[][] grid) {
        m = grid.length; n = grid[0].length;
        int res = 0;
        for (int i = 0; i < m; ++i) {
            for (int j = 0; j < n; ++j) {
                if (grid[i][j] == 1) res = Math.max(res, bfs(grid, i, j));
            }
        }
        return res;
    }
    int bfs(int[][] grid, int x, int y) {
        int res = 0;
        grid[x][y] = 2;
        Queue<int[]> q = new LinkedList<>();
        q.offer(new int[]{x, y});
        while (!q.isEmpty()) {
            int[] loc = q.poll();
            res++;
            int x0 = loc[0], y0 = loc[1];
            for (int i = 0; i < 4; ++i) {
                int xx = x0 + dirs[i], yy = y0 + dirs[i + 1];
                if (xx >= 0 && xx < m && yy >= 0 && yy < n && grid[xx][yy] == 1) {
                    q.offer(new int[]{xx, yy});
                    grid[xx][yy] = 2;
                }
            }
        }
        return res;
    }
}

并查集方案代码

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
44
45
46
47
48
49
50
51
52
53
54
55
56
57
class Solution {
    static final int[] dirs = new int[]{0, -1, 0, 1, 0};
    class DSU {
        int[] p, rank, cnt;
        public DSU(int n) {
            this.p = new int[n]; this.rank = new int[n];
            this.cnt = new int[n];
            for (int i = 0; i < n; ++i) {
                p[i] = i;
                rank[i] = 1;
                cnt[i] = 1;
            }
        }
        int find(int u) {
            if (p[u] != u) p[u] = find(p[u]);
            return p[u];
        }
        void unite(int a, int b) {
            int pa = find(a), pb = find(b);
            if (pa == pb) return ;
            if (rank[pa] <= rank[pb]) {
                p[pa] = pb;
                cnt[pb] += cnt[pa];
            }
            else {
                p[pb] = pa;
                cnt[pa] += cnt[pb];
            }
            if (rank[pa] == rank[pb]) rank[pb]++;
        }
        int getCnt(int u) {
            return this.cnt[find(u)];
        }
    }
    public int maxAreaOfIsland(int[][] grid) {
        int m = grid.length, n = grid[0].length;
        int res = 0;
        DSU dsu = new DSU(m * n);
        for (int i = 0; i < m; ++i) {
            for (int j = 0; j < n; ++j) {
                if (grid[i][j] == 1) {
                    int curIdx = i * n + j;
                    if (i + 1 < m && grid[i + 1][j] == 1) dsu.unite(curIdx, (i + 1) * n + j);
                    if (j + 1 < n && grid[i][j + 1] == 1) dsu.unite(curIdx, i * n + j + 1);
                }
            }
        }
        for (int i = 0; i < m; ++i) {
            for (int j = 0; j < n; ++j) {
                if (grid[i][j] == 1) {
                    res = Math.max(res, dsu.getCnt(i * n + j));
                } 
            }
        }
        return res;
    }
}

463. 岛屿的周长

给定一个 row x col 的二维网格地图 grid ，其中：grid[i][j] = 1 表示陆地， grid[i][j] = 0 表示水域。

网格中的格子 水平和垂直 方向相连（对角线方向不相连）。整个网格被水完全包围，但其中恰好有一个岛屿（或者说，一个或多个表示陆地的格子相连组成的岛屿）。

岛屿中没有“湖”（“湖” 指水域在岛屿内部且不和岛屿周围的水相连）。格子是边长为 1 的正方形。网格为长方形，且宽度和高度均不超过 100 。计算这个岛屿的周长。

示例：

img

图片来自Leetcode

1
2
3
输入：grid = [[0,1,0,0],[1,1,1,0],[0,1,0,0],[1,1,0,0]]
输出：16
解释：它的周长是上面图片中的 16 个黄色的边

本题其实没必要用深搜，直接数学计算更简单

DFS方案

搜索过程中，遇到海洋，贡献 11 边长，越过网格边界，也会贡献 11 个边长，而遇到已经遍历过的陆地，贡献 00 边长

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
class Solution {
    static final int[] dirs = new int[]{0, -1, 0, 1, 0};
    int m, n;
    public int islandPerimeter(int[][] grid) {
        m = grid.length; n = grid[0].length;
        for (int i = 0; i < m; ++i) {
            for (int j = 0; j < n; ++j) {
                if(grid[i][j] == 1) {
                    return dfs(grid, i, j);
                }
            }
        }
        return 0;
    }
    int dfs(int[][] grid, int x, int y) {
        if (!valid(m, n, x, y)) return 1;
        if (grid[x][y] == 2) return 0;
        if (grid[x][y] == 0) return 1;
        grid[x][y] = 2;
        int res = 0;
        for (int i = 0; i < 4; ++i) {
            int xx = x + dirs[i], yy = y + dirs[i + 1];
            res += dfs(grid, xx, yy);
        }
        return res;
    }
    boolean valid(int m, int n, int x, int y) {
        return x >= 0 && x < m && y >= 0 && y < n;
    }
}

只有和海洋网格或者边界相邻的陆地的部分边长，才会构成岛屿的周长

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class Solution {
    static final int[] dirs = new int[]{0, -1, 0, 1, 0};
    public int islandPerimeter(int[][] grid) {
        int m = grid.length, n = grid[0].length;
        int res = 0;
        for (int i = 0; i < m; ++i) {
            for (int j = 0; j < n; ++j) {
                if(grid[i][j] == 1) {
                    int cur = 0;
                    for (int k = 0; k < 4; ++k) {
                        int x = i + dirs[k], y = j + dirs[k + 1];
                        if (x >= m || x < 0 || y < 0 || y >= n || grid[x][y] == 0) cur++;
                    }
                    res += cur;
                }
            }
        }
        return res;
    }
}