LeetCode 1905 Count Sub Islands

标签: 岛屿问题 LeetCode 发布于:2022-02-02 17:32:43 编辑于:2022-02-05 16:54:48 浏览量:1060

题目分析

https://leetcode.com/problems/count-sub-islands/

首先我们需要找出 grid2 中所有的岛屿,其次这些岛屿要满足其是 grid1 中某一个岛屿的一部分。

实际上其也不可能是由两个或多个岛屿分割而来,因为这样的话这些岛屿必然连在一起,因此也谈不上两个或多个了。

那问题就转换为,找出 grid2 中所有岛屿时,顺便判断其对应的元素在 grid1 上是否也是陆地。

深度优先搜索

class Solution {
public:
    int countSubIslands(vector<vector<int>>& grid1, vector<vector<int>>& grid2) {
        int count = 0;
        for (int i = 0; i < grid2.size(); i++) {
            for (int j = 0; j < grid2[0].size(); j++) {
                if (grid2[i][j] == 1) {
                    if (travelIsland(i, j, grid1, grid2)) {
                        count++;
                    }
                }
            }
        }
        return count;
    }
    
    bool travelIsland(int i, int j, vector<vector<int>>& grid1, vector<vector<int>>& grid2) {
        if (i < 0 || j < 0 || i >= grid2.size() || j >= grid2[0].size()) return true;
        if (grid2[i][j] == 1) {
            grid2[i][j] = 2; // mark as visited land
            bool f0 = grid1[i][j] == 1;
            bool f1 = travelIsland(i+1, j, grid1, grid2);
            bool f2 = travelIsland(i-1, j, grid1, grid2);
            bool f3 = travelIsland(i, j+1, grid1, grid2);
            bool f4 = travelIsland(i, j-1, grid1, grid2);
            return f0 && f1 && f2 && f3 && f4;
        }
        return true;
    }
};

未经允许,禁止转载,本文源站链接:https://iamazing.cn/