Leetcode-463 Island Perimeter

463 Island Perimeter

给出岛屿地图，求解岛屿的周长。岛屿可能有多个块组成，所有的块连接成为一个大岛。

[0,1,0,0]
[1,1,1,0]
[0,1,0,0]
[1,1,0,0]

1. 解决思路

1.1 两次遍历

根据岛屿的特征，只有出现0-1跳变的位置才存在边界，因此按照行序、列序进行两次遍历，对所有的跳变位置进行统计，即可得到最终的周长。

该方法的时间复杂度为O(n²)，空间复杂度为O(1)，但进行列序遍历时，由于Cache命中的问题，效率较低。

int islandPerimeter(int** grid, int gridSize, int* gridColSize){
    if (grid == NULL || gridColSize == NULL || gridSize == 0) {
        return 0;
    }
    int result = 0;

    // for vertical borders
    for (int row = 0 ; row < gridSize ; ++ row) {
        if (**(grid + row) == 1) {
            ++ result;
        }
        for (int col = 0 ; col < *(gridColSize + row) - 1 ; ++ col) {
            if (*(*(grid + row) + col) != *(*(grid + row) + col + 1)) {
                ++ result;
            }
        }
        if (*(*(grid + row) + *(gridColSize + row) - 1) == 1) {
            ++ result;
        }
    }

    // for horizontal borders
    for (int col = 0 ; col < *gridColSize ; ++ col) {
        if (*(*grid + col) == 1) {
            ++ result;
        }
        for (int row = 0 ; row < gridSize - 1; ++ row) {
            if (*(*(grid + row) + col) != *(*(grid + row + 1) + col)) {
                ++ result;
            }
        }
        if (*(*(grid + gridSize - 1) + col) == 1) {
            ++ result;
        }
    }

    return result;
}

1.2 关联遍历

对于单个位置来说，当没有相邻陆地时，存在4条边界。每存在一个相邻陆地，则两个陆地各减少一条边界。因此，遍历过程中，对相邻情况进行判断。按照左上角到右下角的顺序，判断是否为陆地。如果为陆地，则其右侧及下方是否为陆地。两者分别统计，得到的陆地数*4，减去相邻数*2，即为最终的边界周长。

该方法的时间复杂度为O(n²)，空间复杂度为O(1)，但遍历中Cache效率较低。

int islandPerimeter(int** grid, int gridSize, int* gridColSize){
    if (grid == NULL || gridColSize == NULL || gridSize == 0) {
        return 0;
    }
    int result = 0;
    int inside = 0;

    for (int row = 0 ; row < gridSize ; ++ row) {
        for (int col = 0 ; col < *(gridColSize + row) ; ++ col) {
            if (*(*(grid + row) + col) == 1) {
                ++ result;

                if (col < *(gridColSize + row) - 1 && *(*(grid + row) + col + 1) == 1) {
                    ++ inside;
                }
                if (row < gridSize - 1 && *(*(grid + row + 1) + col) == 1) {
                    ++ inside;
                }
            }
        }
    }

    result = result * 4 - inside * 2;

    return result;
}