【LeetCode】463. 岛屿的周长（Java）

【LeetCode】463. 岛屿的周长（Java）

给定一个包含 0 和 1 的二维网格地图，其中 1 表示陆地 0 表示水域。

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

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

解法一

迭代，最容易想到的解法。

class Solution {public int islandPerimeter(int[][] grid) {// 迭代// 这道岛屿问题之所以是简单类型的题目，是因为题目已经把难度降低了很多了，如只有一个岛屿，并且岛屿中没有湖。int constexpr = 0;// 遍历数组for (int i = 0; i < grid.length; i++) {for (int j = 0; j < grid[i].length; j++) {// 如果当前为陆地，判断前后左右是否为水域或者边界，如果是，周长加1if (grid[i][j] == 1) {// 判断陆地上边if (i == 0 || grid[i - 1][j] == 0)  constexpr++;// 判断陆地下边if (i == grid.length - 1 || grid[i + 1][j] == 0)  constexpr++;// 判断陆地左边if (j == 0 || grid[i][j - 1] == 0)  constexpr++;// 判断陆地右边if (j == grid[i].length - 1 || grid[i][j + 1] == 0)  constexpr++;}}}return constexpr;}
}

这道岛屿问题之所以是简单类型的题目，是因为题目已经把难度降低了很多了，如只有一个岛屿，并且岛屿中没有湖。

解法二

dfs，深度优先遍历。

class Solution {public int islandPerimeter(int[][] grid) {// dfsfor (int i = 0; i < grid.length; i++) {for (int j = 0; j < grid[i].length; j++) {// 因为只有一个岛屿，所以只要碰到陆地，即可返回结果if (grid[i][j] == 1) {return dfs(grid, i, j);}}}return 0;}private int dfs(int[][] grid, int c, int r) {// 判断当前是否越界，如果是，返回1（周长加1）if (c < 0 || c >= grid.length || r < 0 || r >= grid[c].length) {return 1;}// 判断是否为水域，如果是返回1（周长加1）if (grid[c][r] == 0) {return 1;}// 判断是否已走过，如果是返回0（已走过，不加）if (grid[c][r] == 2) {return 0;}// 把当前陆地1污染为2，代表已走过grid[c][r] = 2;// 返回前后左右的递归返回值的总和return dfs(grid, c - 1, r) + dfs(grid, c, r - 1) + dfs(grid, c + 1, r) + dfs(grid, c, r + 1);}
}

解法三

量子纠缠解法，由画家王铁男大佬提供思路。

class Solution {public int islandPerimeter(int[][] grid) {// 量子纠缠解法，在北面有一条边，对应的南面也会有一条边，东西同理，才能形成闭环int constexpr = 0;for (int i = 0; i < grid.length; i++) {for (int j = 0; j < grid[i].length; j++) {// 是陆地if (grid[i][j] == 1) {// 上一个不是陆地（和水域相接或边界），有一条边，那么下边也有一条边与其对应if (i == 0 || grid[i - 1][j] == 0) {// 因为上下都有一条边，所以是加二constexpr += 2;}if (j == 0 || grid[i][j - 1] == 0) {// 同理constexpr += 2;}}}}return constexpr;}
}

解法四

公式：岛屿周长 = 陆地数 * 4 - 陆地接壤边数 * 2，由笨猪爆破组大佬提供思路。

class Solution {public int islandPerimeter(int[][] grid) {// 公式 岛屿周长 = 陆地数 * 4 - 陆地接壤边数 * 2int constexpr = 0;for (int i = 0; i < grid.length; i++) {for (int j = 0; j < grid[i].length; j++) {// 是陆地，加4if (grid[i][j] == 1) {constexpr += 4;// 先判断是否当最下边，然后再判断下一个是否也是陆地，如果是既有一条接壤边，减2if (i < grid.length - 1 && grid[i + 1][j] == 1) {constexpr -= 2;}// 判断右边，同上（只判断两边，避免重复）if (j < grid[i].length - 1 && grid[i][j + 1] == 1) {constexpr -= 2;}}}}return constexpr;}
}