Re: [閒聊] 每日leetcode
看板Marginalman作者enmeitiryous (enmeitiryous)時間1年前 (2024/08/28 17:48)推噓0(0推 0噓 0→)留言0則, 0人參與討論串777/1554 (看更多)
下周開學不能再廢了
題目:
1905. Count Sub Islands
給兩個二元的二維矩陣a,b其中1代表的是存在的島嶼，求b完全包含於a的島嶼的數目
思路:
本來想說可以用union find然後求出兩個矩陣的島嶼再遍歷島嶼比較，但想了下保底
複雜度會要跑10**8次肯定不是答案，看了下提示後應該是要用b的島嶼去找，在比較過程
中找過的要修改成0避免重複尋找
bool easycheck(int i,int j,vector<vector<int>>& grid1, vector<vector<int>>&
grid2){
bool tar=true;
grid2[i][j] = 0;
if(grid1[i][j]==0){
tar=false;
}
if(i>0 &&grid2[i-1][j]){
tar&=easycheck(i-1,j,grid1,grid2);
}
if(i<grid2.size()-1 && grid2[i+1][j]){
tar&=easycheck(i+1,j,grid1,grid2);
}
if(j>0 && grid2[i][j-1]){
tar&=easycheck(i,j-1,grid1,grid2);
}
if(j<grid2[0].size()-1&& grid2[i][j+1]){
tar&=easycheck(i,j+1,grid1,grid2);
}
return tar;
}
int countSubIslands(vector<vector<int>>& grid1, vector<vector<int>>&
grid2) {
int m=grid1.size();
int n=grid1[0].size();
int ans=0;
for(int i=0;i<m;++i){
for(int j=0;j<n;++j){
if(grid2[i][j]){
if(easycheck(i,j,grid1,grid2)){
++ans;
}
}
}
}
return ans;
}
--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 36.227.205.129 (臺灣)
※ 文章網址: https://www.ptt.cc/bbs/Marginalman/M.1724838533.A.7DD.html
討論串 (同標題文章)
完整討論串 (本文為第 777 之 1554 篇)：