要从外围海往内部dfs,碰见岛屿就加1,然后dfs岛屿,把岛屿最大连通块算出来,能碰见的岛屿都不是环内的,环内的岛屿海水是碰不到的,也就满足了环内岛屿不算数的情况
#include <iostream>
#include <cstring>
using namespace std;
const int N=60;
int g[N][N];//呜呜呜,一定要认真读题,是字符‘0’,没输出的时候考虑下输入进去没有
int t,m,n,cnt;
bool st[N][N];
int dx[]={-1,0,1,0};
int dy[]={0,1,0,-1};
int sdx[]={-1,-1,0,1,1,1,0,-1};
int sdy[]={0,1,1,1,0,-1,-1,-1};
void dfs_land(int a,int b){
st[a][b]=true;//访问过的点即不再访问
for(int i=0;i<4;i++)
{
int ax=a+dx[i];
int bx=b+dy[i];
if(st[ax][bx]||g[ax][bx]==0)continue;
dfs_land(ax,bx);
}
}
void dfs_sea(int a,int b){ //需要加一层外海
st[a][b]=true;
for(int i=0;i<8;i++){
int ax=a+sdx[i];
int bx=b+sdy[i];
if(ax<0||ax>m+1||bx<0||bx>n+1||st[ax][bx]) continue;//最好使用continue
if(g[ax][bx]==0) dfs_sea(ax,bx);//是海水的话我就继续dfs找到海水能联通的所有区域
else
{ dfs_land(ax,bx);
cnt++;
}
}
}
int main()
{
scanf("%d",&t);
while(t--){
cnt=0;
memset(g,0,sizeof g);
memset(st,false,sizeof st);//每组测试数据都必须重新初始化
scanf("%d%d",&m,&n);
for(int i=1;i<=m;i++) //为了扩展一圈,最好从1开始存
for(int j=1;j<=n;j++)
{
char c;
cin>>c;
g[i][j]=c-'0';
}
dfs_sea(0,0);
cout<<cnt<<endl;
}
return 0;
}
嗯?好像哇…
orz,大佬在此