Skip to main content

463. 岛屿的周长

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

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

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

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

  • 输入：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

思路​

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

解法一：​

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

如图：

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

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++代码如下：（详细注释）

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;
    }
}

// 解法二
class Solution {
    public int islandPerimeter(int[][] grid) {
        // 计算岛屿的周长
        // 方法二 : 遇到相邻的陆地总周长就-2
        int landSum = 0; // 陆地数量
        int cover = 0; // 相邻陆地数量
        for (int i = 0; i < grid.length; i++) {
            for (int j = 0; j < grid[0].length; j++) {
                if (grid[i][j] == 1) {
                    landSum++;
                    // 统计上面和左边的相邻陆地
                    if(i - 1 >= 0 && grid[i-1][j] == 1) cover++;
                    if(j - 1 >= 0 && grid[i][j-1] == 1) cover++;
                }
            }
        }
        return landSum * 4 - cover * 2;
    }
}
// 延伸 - 傳統DFS解法(使用visited數組)（遇到邊界 或是 海水 就edge ++）
class Solution {
    int dir[][] ={
        {0, 1},
        {0, -1},
        {1, 0},
        {-1, 0}
    };

    boolean visited[][];
    int res = 0;

    public int islandPerimeter(int[][] grid) {
        int row = grid.length;
        int col = grid[0].length;
        visited = new boolean[row][col];

        int result = 0;

        for(int i = 0; i < row; i++){
            for(int j = 0; j < col; j++){
                if(visited[i][j] == false && grid[i][j] == 1)
                    result += dfs(grid, i, j);
            }
        }
        return result;
    }

    private int dfs(int[][] grid, int x, int y){
        //如果遇到 邊界（x < 0 || y < 0 || x >= grid.length || y >= grid[0].length）或是 遇到海水(grid[x][y] == 0)就return 1（edge + 1）
        if(x < 0 || y < 0 || x >= grid.length || y >= grid[0].length || grid[x][y] == 0)
            return 1;
        //如果該地已經拜訪過，就return 0 避免重複計算
        if(visited[x][y])
            return 0;
        int temp = 0;
        visited[x][y] = true;
        for(int i = 0; i < 4; i++){
            int nextX = x + dir[i][0];
            int nextY = y + dir[i][1];
            //用temp 把edge存起來
            temp +=dfs(grid, nextX, nextY);
        }
        return temp;
    }
}