题目

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

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

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

示例 1：

img

输入：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时，将result的值增加4，接下来判断当前的方格周围的方格是否为1，如果它的下方或右方有同样是1的方格时，将res减少2（分别在当前方格和相邻方格方面的边长减去）。C++代码实现如下：

class Solution {
public:
    int islandPerimeter(vector<vector<int>>& grid) {
        int res = 0; // 初始化结果
        int rows = grid.size(); // 获取行数
        int cols = grid[0].size(); // 获取列数
        // 开始遍历
        for (int i = 0; i < rows; ++i) { 
            for (int j = 0; j < cols; ++j) {
                if (grid[i][j] == 1) { // 如果当前被遍历的方格值为1
                    res += 4; // 结果增加4
                    if (i < rows - 1 && grid[i + 1][j] == 1) res -= 2; // 判断当前遍历的方格的下方的方格是否也是1
                    if (j < cols - 1 && grid[i][j + 1] == 1) res -= 2;// 判断当前遍历的方格的右方的方格是否也是1
                }
            }
        }
        return res; // 返回结果
    }
};
  • 数学方法

思路：一块土地原则上会带来 4 个周长，但岛上的土地存在接壤，每一条接壤，会减掉 2 个边长。

所以，总周长 = 4 * 土地个数 - 2 * 接壤边的条数。

遍历矩阵，遍历到土地，就 land++，如果它的右/下边也是土地，则 border++，遍历结束后代入公式。

class Solution {
public:
    int islandPerimeter(vector<vector<int>>& grid) {
        int land = 0;//土地数量
        int border = 0;//接壤边的条数

        for (int i = 0; i < grid.size(); ++i) {
            for (int j = 0; j < grid[0].size(); ++j) {
                if (grid[i][j] == 1) {
                    ++land;
                    if (i < grid.size() - 1 && grid[i + 1][j] == 1) {//该土地的下方有土地就说明下面这条边就是接壤边
                        ++border;
                    }
                    if (j < grid[0].size() - 1 && grid[i][j + 1] == 1) {//该土地的右方有土地就说明右面这条边就是接壤边
                        ++border;
                    }
                }
            }
        }
        return 4 * land - 2 * border;
    }
};
  • DFS

思路：岛就一个，我们从第一个遇到的土地开始深搜。

对于每个土地节点，做一些事情，基于它，递归上下左右四个点，做同样的事情。做什么事情呢？

从土地到土地，之间不会产生周长，但从土地迈入海洋，之间会产生 1 个周长，从土地迈出矩阵边界，也会产生 1 个周长。

dfs 的过程中，对当前点的上下左右递归，下一个递归的点又对上下左右递归，就会造成重复访问，造成周长的重复计算。

遍历过的土地节点，将值改为 2，区分于 1 和 0，代表访问过了。

总结：DFS 从一个点，向四周扩散，目标是遇到矩阵边界或海水，它们是答案已知的 base case，是位于递归树底部的 case，是递归的终止条件。

从上而下递归调用，随着递归的出栈，子问题的解自下而上地返回，最后得出大问题的解。

class Solution {
public:
    int islandPerimeter(vector<vector<int>>& grid) {
        for (int i = 0; i < grid.size(); ++i) {
            for (int j = 0; j < grid[0].size(); ++j) {
                if (grid[i][j] == 1) {
                    return dfsHelper(grid, i, j);
                }
            }
        }
        return 0;
    }

    int dfsHelper(vector<vector<int>>& grid, int i, int j) {
        int rows = grid.size();
        int cols = grid[0].size();
        if (i < 0 || i >= rows || j < 0 || j >= cols) {
            //越界的情况，直接返回1
            return 1;
        }
        if (grid[i][j] == 0) {
            // 从土地到达海水
            return 1;
        }
        if (grid[i][j] == 2) {
            // 之前已经访问过这块方格了，直接返回0
            return 0;
        }
        // 修改方格的值为2，说明已经来过了
        grid[i][j] = 2;
        return dfsHelper(grid, i - 1, j) + dfsHelper(grid, i + 1, j) + dfsHelper(grid, i, j - 1) + dfsHelper(grid, i, j + 1);
    }
};