0463.岛屿的周长.md

欢迎大家参与本项目，贡献其他语言版本的代码，拥抱开源，让更多学习算法的小伙伴们收益！

# 463. 岛屿的周长

力扣题目链接

思路

岛屿问题最容易让人想到BFS或者DFS，但是这道题还真的没有必要，别把简单问题搞复杂了。

解法一：

遍历每一个空格，遇到岛屿，计算其上下左右的情况，遇到水域或者出界的情况，就可以计算边了。

如图：

C++代码如下：（详细注释）

class Solution {
public:
    int direction[4][2] = {0, 1, 1, 0, -1, 0, 0, -1};
    int islandPerimeter(vector<vector<int>>& grid) {
        int result = 0;
        for (int i = 0; i < grid.size(); i++) {
            for (int j = 0; j < grid[0].size(); j++) {
                if (grid[i][j] == 1) {
                    for (int k = 0; k < 4; k++) {       // 上下左右四个方向
                        int x = i + direction[k][0];
                        int y = j + direction[k][1];    // 计算周边坐标x,y
                        if (x < 0                       // i在边界上
                                || x >= grid.size()     // i在边界上
                                || y < 0                // j在边界上
                                || y >= grid[0].size()  // j在边界上
                                || grid[x][y] == 0) {   // x,y位置是水域
                            result++;
                        }
                    }
                }
            }
        }
        return result;
    }
};

解法二：

计算出总的岛屿数量，因为有一对相邻两个陆地，边的总数就减2，那么在计算出相邻岛屿的数量就可以了。

result = 岛屿数量 * 4 - cover * 2;

如图：

C++代码如下：（详细注释）

class Solution {
public:
    int islandPerimeter(vector<vector<int>>& grid) {
        int sum = 0;    // 陆地数量
        int cover = 0;  // 相邻数量
        for (int i = 0; i < grid.size(); i++) {
            for (int j = 0; j < grid[0].size(); j++) {
                if (grid[i][j] == 1) {
                    sum++;
                    // 统计上边相邻陆地
                    if(i - 1 >= 0 && grid[i - 1][j] == 1) cover++;
                    // 统计左边相邻陆地
                    if(j - 1 >= 0 && grid[i][j - 1] == 1) cover++;
                    // 为什么没统计下边和右边？ 因为避免重复计算
                }
            }
        }
        return sum * 4 - cover * 2;
    }
};

其他语言版本

Java：

// 解法一
class Solution {
    // 上下左右 4 个方向
    int[] dirx = {-1, 1, 0, 0};
    int[] diry = {0, 0, -1, 1};

    public int islandPerimeter(int[][] grid) {
        int m = grid.length;
        int n = grid[0].length;
        int res = 0; // 岛屿周长
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (grid[i][j] == 1) {
                    for (int k = 0; k < 4; k++) {
                        int x = i + dirx[k];
                        int y = j + diry[k];
                        // 当前位置是陆地，并且从当前位置4个方向扩展的“新位置”是“水域”或“新位置“越界，则会为周长贡献一条边
                        if (x < 0 || x >= m || y < 0 || y >= n || grid[x][y] == 0) {
                            res++;
                            continue;
                        }
                    }
                }
            }
        }
        return res;
    }
}

Python：

Go：

JavaScript：

//解法一
var islandPerimeter = function(grid) {
    // 上下左右 4 个方向
    const dirx = [-1, 1, 0, 0], diry = [0, 0, -1, 1];
    const m = grid.length, n = grid[0].length;
    let res = 0; //岛屿周长
    for(let i = 0; i < m; i++){
        for(let j = 0; j < n; j++){
            if(grid[i][j] === 1){
                for(let k = 0; k < 4; k++){ //上下左右四个方向
                    // 计算周边坐标的x,y
                    let x = i + dirx[k];
                    let y = j + diry[k];
                    // 四个方向扩展的新位置是水域或者越界就会为周长贡献1
                    if(x < 0  // i在边界上
                    || x >= m // i在边界上
                    || y < 0  // j在边界上
                    || y >= n // j在边界上
                    || grid[x][y] === 0){ // (x,y)位置是水域
                        res++;
                        continue;
                    }
                }
            }
        }
    }
    return res;
};

//解法二
var islandPerimeter = function(grid) {
    let sum = 0; // 陆地数量
    let cover = 0; // 相邻数量
    for(let i = 0; i < grid.length; i++){
        for(let j = 0; j <grid[0].length; j++){
            if(grid[i][j] === 1){
                sum++;
                // 统计上边相邻陆地
                if(i - 1 >= 0 && grid[i-1][j] === 1) cover++;
                // 统计左边相邻陆地
                if(j - 1 >= 0 && grid[i][j-1] === 1) cover++;
                // 为什么没统计下边和右边？ 因为避免重复计算
            }
        }
    }
    return sum * 4 - cover * 2;
};

---

• 作者微信：程序员Carl
• B站视频：代码随想录
• 知识星球：代码随想录