leetcode463：岛屿的周长（island-perimeter）

carloscn commented 1 year ago

问题描述

给定一个 row x col 的二维网格地图 grid ，其中：grid[i][j] = 1 表示陆地， grid[i][j] = 0 表示水域。

网格中的格子水平和垂直方向相连（对角线方向不相连）。整个网格被水完全包围，但其中恰好有一个岛屿（或者说，一个或多个表示陆地的格子相连组成的岛屿）。

岛屿中没有“湖”（“湖” 指水域在岛屿内部且不和岛屿周围的水相连）。格子是边长为 1 的正方形。网格为长方形，且宽度和高度均不超过 100 。计算这个岛屿的周长。

示例 1：

输入：grid = [[0,1,0,0],[1,1,1,0],[0,1,0,0],[1,1,0,0]] 输出：16 解释：它的周长是上面图片中的 16 个黄色的边

示例 2：输入：grid = [[1]] 输出：4

示例 3：输入：grid = [[1,0]] 输出：4

提示： row == grid.length col == grid[i].length 1 <= row, col <= 100 grid[i][j] 为 0 或 1

来源：力扣（LeetCode）链接：https://leetcode.cn/problems/island-perimeter

carloscn commented 1 year ago

问题分析

我们遍历二维数组，然后如果判断以这个点为中心的四个边的计数：

上面：如果是上边界则+1，或者非上边界但是上面元素是0 则 +1
下面：如果是下边界则+1，或者非下边界但是下面元素是0 则 +1
左边：如果是左边界则+1，或者非左边界但是左边元素是0 则 +1
右边：如果是有边界则+1，或者非右边界但是右边元素是0 则 +1

static int64_t metrix[4][4] = {
    {1,1,0,0},
    {1,1,1,0},
    {0,1,0,0},
    {1,1,0,0}
};

static size_t get_count(int64_t metrix[4][4], size_t x_index, size_t y_index, size_t width, size_t length)
{
    size_t count = 0;

    LOG("for j,i = (%zu, %zu):\n", x_index, y_index);

    // checking up
    if ((y_index == 0) ||
        (metrix[y_index - 1][x_index] == 0)) {
        LOG("up ++\n");
        count ++;
    }

    // checking down
    if ((y_index == length - 1) ||
        (metrix[y_index + 1][x_index] == 0)) {
        LOG("down ++\n");
        count ++;
    }

    // checking left
    if ((x_index == 0) ||
        (metrix[y_index][x_index - 1] == 0)) {
        LOG("left ++\n");
        count ++;
    }

    // checking right
    if ((x_index == width - 1) ||
        (metrix[y_index][x_index + 1] == 0)) {
        LOG("right ++\n");
        count ++;
    }

    LOG("\n");
    return count;
}

static int32_t island_perimeter(int64_t metrix[4][4], size_t width, size_t length, size_t *out)
{
    int32_t ret = 0;
    size_t i = 0, j = 0;
    size_t t_count = 0, s_count = 0;

    UTILS_CHECK_PTR(metrix);
    UTILS_CHECK_LEN(width);
    UTILS_CHECK_LEN(length);

    for (i = 0; i < width; i ++) {
        for (j = 0; j < length; j ++) {
            if (metrix[j][i]) {
                t_count = get_count(metrix, i, j, width, length);
                s_count += t_count;
            }
        }
    }

    *out = s_count;

finish:
    return ret;
}

carloscn commented 1 year ago

code:

https://github.com/carloscn/structstudy/blob/master/c_programming/array/34_island-perimeter_463.c

carloscn / structstudy