题目描述 LeetCode 463

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:

题目解读

• 计算小岛的面积，面积示意如上图中的黄色线段

解题思路

• 遍历数组每一块，如果该块为 1, 则计算它上下左右是否为 0，还要考虑边界，如果上下左右有为 0 的边，或者越界，则小岛面积加 1
• 示意：
  • 开始遍历，进入第一块，为 0 放弃，进入第二块
  • 进入第 2 块，为 1，则看上下左右;　(1) 向上，越界，面积加 1; (2) 向下，下面块为 1，则不是边界;　(3) 向左，左面块为 0，则面积加 1;　(4) 向右，右面块为 0，面接加 １
  • 依次遍历...

Code

# include<stdio.h>

int islandPerimeter(int** grid, int gridRowSize, int gridColSize) 
{
    int i, j;
    int sum = 0;

    for(i = 0; i < gridRowSize; i ++)
    {
        for (j = 0; j < gridColSize; j ++)
        {
            if( *(*(grid + i) + j) == 1)
            {
                // up
                if ( i - 1 < 0 || *(*(grid + i - 1) + j) == 0){
                    sum ++;
                }

                // down
                if ( i + 1 == gridRowSize || *(*(grid + i + 1) + j) == 0){
                    sum ++;
                }

                // left
                if ( j - 1 < 0 || *(*(grid + i) + j - 1) == 0){
                    sum ++;
                }

                // right
                if ( j + 1 == gridColSize || *(*(grid + i) + j + 1) == 0){
                    sum ++; 
                }
            }
            else 
            {
                // *(*(grid + i) + j) == 0 
            }
        }
    }

    return sum;
}

int main()
{   
    int i;
    int island[100][100] = {{0,1,0,0},{1,1,1,0},
            {0,1,0,0},{1,1,0,0}};
    int *tmp[100];

    for (i = 0; i < 4; i ++){
        tmp[i] = island[i];
    }

    printf("%d \n", islandPerimeter(tmp,4, 4));
}