463. Island Perimeter

Leetcode Hash Table

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:

分析

最直接的方法是数一下组成岛的方块数，每个方块有四条边，检查一下方块的每条边是否和其他方块的边重合。如果重合则减去1。

public int islandPerimeter(int[][] grid) {
    if (grid == null) return 0;
    int n = grid.length, m = n > 0 ? grid[0].length : 0;
    if (n == 0 || m == 0) return 0;
    int perimeter = 0;


    for (int i = 0; i < n; i++)
        for (int j = 0; j < m; j++)
            if (grid[i][j] == 1) {
                perimeter += 4;
                if (i + 1 < n && grid[i + 1][j] == 1) perimeter--;
                if (j + 1 < m && grid[i][j + 1] == 1) perimeter--;
                if (i > 0 && grid[i - 1][j] == 1) perimeter--;
                if (j > 0 && grid[i][j - 1] == 1) perimeter--;
            }

    return perimeter;
}

或者数一下每个方块的右边和下面的边是否重合，如果重合减去2，因为每次重合会有两个方块的边减去1。这样简化了一些，不用检查每个方块的上边和左边。

public int islandPerimeter(int[][] grid) {
    if (grid == null) return 0;
    int n = grid.length, m = n > 0 ? grid[0].length : 0;
    if (n == 0 || m == 0) return 0;
    int perimeter = 0;


    for (int i = 0; i < n; i++)
        for (int j = 0; j < m; j++)
            if (grid[i][j] == 1) {
                perimeter += 4;
                if (i + 1 < n && grid[i + 1][j] == 1) perimeter -= 2;
                if (j + 1 < m && grid[i][j + 1] == 1) perimeter -= 2;
            }

    return perimeter;
}