题目描述
blablabla
样例
blab#include <iostream>
#include <algorithm>
#include <cstring>
using namespace std;
const int N=10010;
int n;
char a[N][N];//地图
int vis[N][N]={0};//是否被搜索过
int d[4][2]={0,1,0,-1,1,0,-1,0};
int flag;//用于标记这个岛屿是否被淹没
int dfs(int x,int y){
vis[x][y]=1;
if(a[x][y+1]=='#'&&a[x][y-1]=='#'&&a[x-1][y]=='#'&&a[x+1][y]=='#'){
flag=1;
}
for(int i=0;i<4;i++){//继续dfs周围陆地
int nx=x+d[i][0],ny=y+d[i][1];
if(vis[nx][ny]==0&&a[nx][ny]=='#')
dfs(nx,ny);
}
}
int main(){
cin>>n;
for(int i=0;i<n;i++){
for(int j=0;j<n;j++){
cin>>a[i][j];
}
}
int ans=0;
for(int i=0;i<n;i++){
for(int j=0;j<n;j++){
if(a[i][j]=='#'&&vis[i][j]==0){
flag=0;
dfs(i,j);
if(flag==0)
ans++;
}
}
}
cout<<ans<<endl;
return 0;
}labla
算法1
(暴力枚举) $O(n^2)$
blablabla
时间复杂度
参考文献
C++ 代码
blablabla
算法2
(暴力枚举) $O(n^2)$
blablabla
时间复杂度
参考文献
C++ 代码
blablabla