LeetCode 1905 Count Sub Islands
题目分析
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;
}
};