IslandPerimeter2 [source code]

public class IslandPerimeter2 {
    public int islandPerimeter(int[][] grid) {
        int res = 0;
        for (int i = 0; i < grid.length; i++) {
            for (int j = 0; j < grid[0].length; j++) 
                if (grid[i][j] == 1) {
                    if (i == 0 || grid[i-1][j] == 0) res++;
                    if (i == grid.length - 1 || grid[i+1][j] == 0) res++;
                    if (j == 0 || grid[i][j-1] == 0) res++;
                    if (j == grid[0].length - 1 || grid[i][j+1] == 0) res++; //you can't use grid.length here;
                }
        }
        return res; 
    }

    public static void main(String[] arg) {
        int[][] input1 = {{0,1,0,0},
                         {1,1,1,0},
                         {0,1,0,0},
                         {1,1,0,0}};
        int[][] input2 = {{1}};
        int[][] input3 = {{0,1}};
        int[][] input4 =
        {
            {0,1,1,1,1},
            {0,1,1,1,1},
            {0,0,1,1,1},
            {0,0,0,0,1},
            {0,0,0,1,1},
            {0,0,1,1,1},
            {0,0,0,1,1},
            {0,0,0,0,1},
            {0,0,1,1,1},
            {1,1,1,1,1}
        };
        IslandPerimeter2 tester = new IslandPerimeter2();
        System.out.println(tester.islandPerimeter(input4));

    }
}

这个算法的核心思路是:

The basic premise is that every perimeter unit is a water-land boundary. So simply check for these in the 4 cardinal directions.
Note that even at matrix boundaries( edge-cases ) , there is a boundary at the outer edge.

也就是说每一个1cell, 如果比如他上边也是一个1, 那么这个1cell 自己的upper side就不对总的 count 做出贡献.

这个思路看起来还可以, 不过最后跑出来的速度感人, 167ms, 还不如前面那个算法;

看了一下其他的算法, 感觉最终的思路都是差不多的, 不知道那些最优解到底是怎么写的. 因为这个算法目前已经能够做到O( mn), 所以想要加速就很难.

TODO:
目前有两个思路:

1. 因为没有 lake, 所以是否可以找到一个算法, 能够不 visit 中间的1, 也就是只扫描到两头就 ok 了 .
2. 虽然 visit 的 cell 的数量是O(mn), 但是我们目前每一个grid[i][j]的过程当中, 也要完成至少四次 access(周边四个),能不能用什么算法减少每个 ij 的过程当中的 access 的数量? maybe this is where hashtable is meant to come
   into play?

Problem Description

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:

Hide Tags Hash Table