leetcode [#463]

目录

• 1. 题目
• 2. 解决方案
• 3. 注意事项

题目

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:

---

解决方案

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

---

注意事项

1. 遍历二维数组，统计陆地块总个数islandNum
2. 统计的同时，如果当前块为陆地，则考察其右边或者下边（也可以左边或者上边）的情况，如果是陆地，则rightOrBottomNum加1
3. 最后，周长的计算，如果各个陆地块是分开的，那么周长为islandNum*4，现在由于有一些合并，且每合并一次，减少两条边，减去 rightOrBottomNum*2即可。