[LeetCode] 463. Island Perimeter

You are given a map in form of a two-dimensional integer grid where 1 represents land and 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" (water inside that 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:

Input:
[[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 below:

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

时间O(n^2)

空间O(1)

Java实现

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

JavaScript实现

 1 /**
 2  * @param {number[][]} grid
 3  * @return {number}
 4  */
 5 var islandPerimeter = function (grid) {
 6     let m = grid.length;
 7     let n = grid[0].length;
 8     let islands = 0;
 9     let neighbors = 0;
10     for (let i = 0; i < m; i++) {
11         for (let j = 0; j < n; j++) {
12             if (grid[i][j] == 1) {
13                 islands++;
14                 if (i < m - 1 && grid[i + 1][j] == 1) {
15                     neighbors++;
16                 }
17                 if (j < n - 1 && grid[i][j + 1] == 1) {
18                     neighbors++;
19                 }
20             }
21         }
22     }
23     return islands * 4 - neighbors * 2;
24 };

LeetCode 题目总结