leetcode解题: Island Perimeter (463)

发表于 | 分类于

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:
[[0,1,0,0],
[1,1,1,0],
[0,1,0,0],
[1,1,0,0]]

Answer: 16
Explanation: The perimeter is the 16 yellow stripes in the image below:

解法1：O(N^2) Time

一开始观察可以注意到边界上的岛屿需要特殊处理，每一个边界周长都有效。对于每一个岛屿，要判断每一条边界是否有效，如果是在grid的边界上则直接有效，否贼考虑是否上下左右为0，如果是则为有效边界。
C++

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(vector<vector<int>>& grid) {
        int perimeter = 0;
        int row = grid.size();
        int col = grid[0].size();
        for (int i = 0; i < row; ++i) {
            for (int j = 0; j < col; ++j) {
                // check left boundary
                if (grid[i][j] != 0) {
                    if (j == 0) ++perimeter;
                    if (j == col - 1) ++perimeter;
                    if (j != 0 && grid[i][j - 1] == 0) ++perimeter;
                    if (j != col - 1 && grid[i][j + 1] == 0) ++perimeter;
                    if (i == 0) ++perimeter;
                    if (i == row - 1) ++perimeter;
                    if (i != 0 && grid[i - 1][j] == 0) ++perimeter;
                    if (i != row - 1 && grid[i + 1][j] == 0) ++perimeter;
                }                
            }
        }
        return perimeter;
    }
};

Java

1