GuilinDev
Lc0463
05 August 2008
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:
1
2
3
4
5
6
7
8
[[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代表陆地，0代表水，整个矩形边不超过100，没有湖，需要求出陆地周长。对整个二维数组遍历，每当遍历到一个陆地1时，同时判断下这块陆地的右边和下边看是否也是陆地，如果是就说明有neighbors，最后周长计算为land * 4 - neighbors * 2。时间O(m * n)，空间O(1)。
代码
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(int[][] grid) {
if (grid == null || grid.length == 0 || grid[0].length == 0) {
return 0;
}
int lands = 0;
int neighbors = 0;
for (int i = 0; i < grid.length; i++) {
for (int j = 0; j < grid[0].length; j++) {
if (grid[i][j] == 1) {
lands++;
if (i < grid.length - 1 && grid[i + 1][j] == 1) {
neighbors++;
}
if (j < grid[0].length - 1 && grid[i][j + 1] == 1) {
neighbors++;
}
}
}
}
// 每有一块陆地，周长增加4，每有一个邻居陆地，双方各自减少1的周长，所以乘以2
return lands * 4 - neighbors * 2;
}
}
强行写成DFS的作法
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
26
27
28
29
30
31
32
33
34
35
36
37
class Solution {
public int islandPerimeter(int[][] grid) {
if (grid == null) return 0;
for (int i = 0 ; i < grid.length ; i++){
for (int j = 0 ; j < grid[0].length ; j++){
if (grid[i][j] == 1) {
// 只有一个岛屿
return getPerimeter(grid,i,j);
}
}
}
return 0;
}
public int getPerimeter(int[][] grid, int i, int j){
if (i < 0 || i >= grid.length || j < 0 || j >= grid[0].length) {
return 1;
}
if (grid[i][j] == 0) {
return 1;
}
if (grid[i][j] == -1) {
return 0;
}
int count = 0;
grid[i][j] = -1; //标记访问过
count += getPerimeter(grid, i - 1, j);
count += getPerimeter(grid, i, j - 1);
count += getPerimeter(grid, i, j + 1);
count += getPerimeter(grid, i + 1, j);
return count;
}
}