[LeetCode] 463. Island Perimeter

You are given row x col grid representing a map where grid[i][j] = 1 represents land and grid[i][j] = 0 represents water.

Grid cells are connected horizontally/vertically (not diagonally). The grid is completely surrounded by water, and there is exactly one island (i.e., one or more connected land cells).

The island doesn’t have “lakes”, meaning the water inside isn’t connected to the water around the island. One cell is a square with side length 1. The grid is rectangular, width and height don’t exceed 100. Determine the perimeter of the island.

Example 1:

Input: grid = [[0,1,0,0],[1,1,1,0],[0,1,0,0],[1,1,0,0]]
Output: 16
Explanation: The perimeter is the 16 yellow stripes in the image above.

Example 2:
Input: grid = [[1]]
Output: 4

Example 3:
Input: grid = [[1,0]]
Output: 4

Constraints:
row == grid.length
col == grid[i].length
1 <= row, col <= 100
grid[i][j] is 0 or 1.
There is exactly one island in grid.

岛屿的周长。

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

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

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

思路

题意是给一个二维矩阵，只有 0 和 1。1 表示岛屿，0 表示水。请返回岛屿的周长。这个题虽然是 200 题的 followup，但是其实跟 BFS 或者 DFS 没什么关系。思路是遍历 input，如果当前坐标的值是 1，说明是岛屿，周长 * 4；同时判断当前坐标的右边一个位置和下面一个位置是否也是岛屿，如果是，则减去两条边，因为两个邻居各自都失去一条边。

复杂度

时间O(mn)
空间O(1)

代码

Java实现

class Solution {
    public int islandPerimeter(int[][] grid) {
        int count = 0;
        int nei = 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) {
                    count++;
                    if (i + 1 < m && grid[i + 1][j] == 1) {
                        nei++;
                    }
                    if (j + 1 < n && grid[i][j + 1] == 1) {
                        nei++;
                    }
                }
            }
        }
        return count * 4 - nei * 2;
    }
}

JavaScript实现

/**
 * @param {number[][]} grid
 * @return {number}
 */
var islandPerimeter = function (grid) {
	let m = grid.length;
	let n = grid[0].length;
	let islands = 0;
	let neighbors = 0;
	for (let i = 0; i < m; i++) {
		for (let j = 0; j < n; j++) {
			if (grid[i][j] == 1) {
				islands++;
				if (i < m - 1 && grid[i + 1][j] == 1) {
					neighbors++;
				}
				if (j < n - 1 && grid[i][j + 1] == 1) {
					neighbors++;
				}
			}
		}
	}
	return islands * 4 - neighbors * 2;
};