Re: [閒聊] 每日leetcode
1905. Count Sub Islands
給兩個grid 求grid2的islands中是grid1的sub island的數量
思路
先從grid2每格dfs找island 找過的 找過就改掉當成visited過
過程中每格都比較看看grid1裡面對應格子是不是等於1
最後回傳結果 是的話counter +1
class Solution {
public:
const int dx[4] = {-1,0,1,0}, dy[4] = {0,1,0,-1};
bool isSubIsland(int i , int j, vector<vector<int>>& grid1, vector<vector<
int>>& grid2){
int m = grid1.size(), n = grid1[0].size();
bool result = true;
grid2[i][j] = 0;
if(grid1[i][j] == 0) result = false;
for(int k = 0; k < 4; ++k){
int ni = i + dx[k], nj= j + dy[k];
if(ni >= 0 && ni < m && nj >= 0 && nj < n && grid2[ni][nj]){
result &= isSubIsland(ni, nj, grid1, grid2);
}
}
return result;
}
int countSubIslands(vector<vector<int>>& grid1, vector<vector<int>>& grid2
) {
int m = grid1.size(), n = grid1[0].size(), ans = 0;
for(int i = 0; i < m; ++i){
for(int j =0; j < n; ++j){
if(grid2[i][j] == 1){
if(isSubIsland(i, j, grid1, grid2)) ans ++;
}
}
}
return ans;
}
};
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 114.34.222.80 (臺灣)
※ 文章網址: https://www.ptt.cc/bbs/Marginalman/M.1724805499.A.2C9.html
※ 編輯: argorok (114.34.222.80 臺灣), 08/28/2024 08:43:41
討論串 (同標題文章)
以下文章回應了本文：
完整討論串 (本文為第 774 之 1553 篇)：