起因

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.

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

思考

其实最开始的想法就是遍历，然后检测四个邻居的条件。这样保证可以对于每一个 land cell 都得出它对于最后总周长的贡献。

但是这个方法并不是特别高效，现在想到的方法就是如下的测算方法。

对于每一个 land cell 可以贡献 4 个周长，然后只需要测算两个方向就能够得到最后的总周长，首先是左侧方向，然后是上侧方向。这个其实是利用了对称性，首先每个cell它真实需要考虑的只有左和上两个方向。因为如果下方，右方还是有 land cell 那在遍历的时候其实属于另外的 land cell 来考虑。

所以由于对称性，只需要考虑四个方向的两个。

代码

class Solution {
    public int islandPerimeter(int[][] grid) {
        if (grid == null || grid.length == 0 || grid[0].length == 0) return 0;
        
        int totalLen = 0;
        
        for ( int i = 0; i < grid.length; i++)
        {
            for ( int j = 0; j < grid[i].length; j++)
            {
                if ( grid[i][j] == 1) 
                {
                    totalLen += 4;
                    if ( i > 0 && grid[i-1][j] == 1 ) totalLen -= 2;
                    if ( j > 0 && grid[i][j-1] == 1 ) totalLen -= 2;
                }
            }
        }
        
        return totalLen;
    }
}