岛屿问题

岛屿问题

1. 求岛屿面积或最大面积

就是深度搜索，递归4个方向，统计每个岛的面积。

1. 求岛屿周长

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

普通方法：

就是只有一个岛屿的情况！

class Solution {
public:
    int islandPerimeter(vector<vector<int>>& grid) {
        // 遍历每一个空格，遇到岛屿，计算其上下左右的情况
        int row = grid.size();
        int col = grid[0].size();
        int ret = 0;
        for (int i = 0; i < row; ++i) {
            for (int j = 0; j < col; ++j) {
                if (grid[i][j] == 1) {
                    if (j - 1 == -1 || grid[i][j-1] == 0) ++ret;
                    if (j + 1 == col || grid[i][j+1] == 0) ++ret;
                    if (i - 1 == -1 || grid[i - 1][j] == 0) ++ret;
                    if (i + 1 == row || grid[i + 1][j] == 0) ++ret;
                }
            }
        }
        return ret;
    }
};

3. 拓展：求最大周长

如果存在多个岛屿呢？

这里我想的是同样深度搜索，遍历每一个岛屿，不过在遍历过程中维护两个变量：

a：当前岛屿单元格数目；

b：公共边的数目；

这样当前岛屿周长就是：4a - 2b

代码如下：

class Solution {
public:
    int islandPerimeter(vector<vector<int>>& grid) {
        return perimeterOfMaxArea(grid);
    }
private:
    vector<vector<int>> dir{{-1, 0}, {1, 0}, {0, -1}, {0, 1}};
    // 共用边的数目
    int same_cnt = 0;

    int perimeterOfMaxArea(vector<vector<int>>& map) {
        int rows = map.size();
        if (rows == 0) return 0;
        int cols = map[0].size();

        int ret = 0;
        for (int i = 0; i < rows; ++i) {
            for (int j = 0; j < cols; ++j) {
                same_cnt = 0;  // 表示相邻的共用边的个数；
                int one_cnt = dfs(map, i, j);
                ret = max(ret, one_cnt * 4 - same_cnt * 2);
            }
        }

        return ret;
    }

    // 统计阻挡区域个数，返回陆地格子的数目（陆地面积）
    int dfs(vector<vector<int>>& map, int i, int j) {
        int rows = map.size();
        int cols = map[0].size();

        if (i < 0 || i >= rows || j < 0 || j >= cols) return 0;

        if (map[i][j] == 0) return 0;

        int one_cnt = 1;

        // 先查看4个方向是否有相同边 **重点**
        for (auto& d : dir) {
            int row = i + d[0], col = j + d[1];
            if (row < 0 || row >= rows || col < 0 || col >= cols || map[row][col] == 0)
                continue;
            ++same_cnt;
        }
        map[i][j] = 0; // 用后置0
        // 再递归4个方向
        for (auto& d : dir) {
            int row = i + d[0], col = j + d[1];
            one_cnt += dfs(map, row, col);
        }

        return one_cnt;
    }
};

4.其它

dfs的时候注意访问过的打标记，不要重复访问；

递归的时候，定义好方向数组挺方便的；