463.岛屿的周长

【LetMeFly】463.岛屿的周长

力扣题目链接：https://leetcode.cn/problems/island-perimeter/

给定一个 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

方法一：广搜

要知道：

每个“1”能提供$4$条边，如果其相邻有个“1”，那么其提供的边数就要少一条。

因此，我们只需要从任意一个“1”开始进行广搜，搜到一个新的“1”答案边数就加4

同时，搜到一个“1”（不管是否被搜到过）就将答案边数减1

框架：

int islandPerimeter(vector<vector<int>>& grid) {
    int n = grid.size(), m = grid[0].size();
    int ans = 0;
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            if (grid[i][j]) {
                /*
                    找到一个1，决定从这个1开始进行广搜
                    // 这里是广搜部分
                */
                goto loop;
            }
        }
    }
    loop:;
    return ans;
}

广搜部分：

queue<pii> q;
grid[i][j] = -1;
q.push({i, j});
ans += 4;
while (q.size()) {
    pii thisNode = q.front();
    q.pop();
    for (int d = 0; d < 4; d++) {
        int tx = thisNode.first + directions[d][0];
        int ty = thisNode.second + directions[d][1];
        if (tx >= 0 && tx < n && ty >= 0 && ty < m) {
            if (grid[tx][ty]) {
                ans--;
                // dbg(ans);  //********
                if (grid[tx][ty] == 1) {
                    grid[tx][ty] = -1;
                    q.push({tx, ty});
                    ans += 4;
                }
            }
        }
    }
}

• 时间复杂度$O(n\times m)$，其中地图大小为$n\times m$
• 空间复杂度$O(n\times m)$

AC代码

C++

typedef pair<int, int> pii;
const int directions[4][2] = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}};
class Solution {
public:
    int islandPerimeter(vector<vector<int>>& grid) {
        int n = grid.size(), m = grid[0].size();
        int ans = 0;
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                if (grid[i][j]) {
                    queue<pii> q;
                    grid[i][j] = -1;
                    q.push({i, j});
                    ans += 4;
                    while (q.size()) {
                        pii thisNode = q.front();
                        q.pop();
                        for (int d = 0; d < 4; d++) {
                            int tx = thisNode.first + directions[d][0];
                            int ty = thisNode.second + directions[d][1];
                            if (tx >= 0 && tx < n && ty >= 0 && ty < m) {
                                if (grid[tx][ty]) {
                                    ans--;
                                    // dbg(ans);  //********
                                    if (grid[tx][ty] == 1) {
                                        grid[tx][ty] = -1;
                                        q.push({tx, ty});
                                        ans += 4;
                                    }
                                }
                            }
                        }
                    }

                    goto loop;
                }
            }
        }
        loop:;
        return ans;
    }
};

同步发文于CSDN，原创不易，转载请附上原文链接哦~
Tisfy：https://letmefly.blog.csdn.net/article/details/127510967