岛屿的周长

发表于
本文字数： 2k 阅读时长 ≈ 2 分钟

LeetCode每日一题，463. Island Perimeter

先看题目描述

BY5KC6.png

大意就是给定一个只包含 0 和 1 的二维网格地图，0 表示水域而 1 表示陆地，让我们计算岛屿的周长

算法和思路

DFS

看到岛屿的题目，第一反应就是使用深度优先搜索。在 DFS 遍历时求岛屿的周长，有个很简单的思路就是：岛屿的周长就是岛屿方格和非岛屿方格相邻的边的数量，这里的非岛屿方格，既包括水域方格，也包括网格的边界，可以见下图

BYTlvT.png

具体实现上，我们对于已访问过的岛屿，我们将其值置为 2，代表已访问过，以避免递归陷入死循环。当遇到网格边界或水域方格时，便返回 1；当遇到以访问过的岛屿时，则返回 0

迭代

这道题上使用深度优先搜索的算法效率并不是很高，后来去看运行效率高的代码，发现这道题直接使用迭代的效率很高

大致思路就是初始化 res = 0，然后逐行的遍历方格，若遇到岛屿，则将 res + 4，若该岛屿的上方有岛屿，则将 res - 2，因为有部分边重复；若该岛屿的左边有岛屿，则同样将 res - 2，因为有部分边重复。最后遍历结束后返回 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
class Solution {
    public int islandPerimeter(int[][] grid) {
        int m = grid.length;
        int 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;
    }

    private int dfs(int[][] grid, int i, int j) {
        if (i < 0 || i >= grid.length || j < 0 || j >= grid[0].length || grid[i][j] == 0) {
            return 1 ;
        }
        if (grid[i][j] == 2) {
            return 0;
        }
        grid[i][j] = 2;
        return dfs(grid, i + 1, j) + dfs(grid, i - 1, j) + dfs(grid, i, j + 1) + dfs(grid, i, j - 1);
    }
}

迭代

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