算法
BFS,DFS
首先BFS将所有和海域相邻的岛屿边角转化为*,接着DFS一遍含*和#的岛屿,并且如果遍历到#表明此岛屿没有完全淹没,记cnt++
C++ 代码
#include<iostream>
#include<set>
#include<cstring>
#include<map>
#include<algorithm>
using namespace std;
const int maxn=1000+5;
int n;
string m[maxn];
int vis[maxn][maxn];
bool flag=false;
void dfs(int x, int y){
if(x<0||y<0||x>=n||y>=n||vis[x][y]||m[x][y]=='.') return;
vis[x][y]=1;
if(m[x][y]=='#') flag=false;
dfs(x+1,y);
dfs(x-1,y);
dfs(x,y+1);
dfs(x,y-1);
}
int main(){
cin>>n;
for(int i=0;i<n;i++) cin>>m[i];
for(int i=0;i<n;i++){
for(int j=0;j<n;j++){
if(m[i][j]=='.')continue;
int dx[4]={0,0,1,-1}, dy[4]={1,-1,0,0};
for(int k=0;k<4;k++){
int xt=i+dx[k];
int yt=j+dy[k];
if(xt<0||yt<0||xt>=n||yt>=n||m[xt][yt]!='.') continue;
m[i][j]='*';
}
}
}
int cnt=0;
for(int i=0;i<n;i++){
for(int j=0;j<n;j++){
if(vis[i][j]||m[i][j]=='.') continue;
flag=true;
dfs(i,j);
if(flag) cnt++;
}
}
cout<<cnt;
return 0;
}
cnt 按逻辑应该是统计 不被淹没的呀,题目求的是 被淹没的!
if(vis[i][j]||m[i][j]==’.’) continue;
flag=true;
dfs(i,j);
if(flag) cnt++; 这里的flag = true为什么要先置为true呢??
先设置为true表示一开始假设他会被淹没,然后再dfs遍历,这时候如果发现原来的岛屿还有’.’也就是没被淹没,则flag=false,当dfs完如果还为true,则表明被淹没了,cnt++
你好,flag的作用是判断什么的,还有就是cnt1和cnt2的作用是什么
flag用来判断原来的岛屿是否全部被淹没,如果没全被淹没则flag=true。cnt1,cnt2是之前写的忘记删了。。。马上删掉