//思路:将整个地图向外扩大一圈,从外部开始搜,将能搜到的0均置为2,这样在环内的海水是0,其余海水均为2
//然后找元素为1的联通块的个数,同时判断该联通块能否到达置为2的海水,若无法到达则可以确定是环内的岛屿,不需要统计
算法1
(dfs+八连通)
C++ 代码
#include <iostream>
#include <algorithm>
#include <cstring>
#include <cmath>
#include <queue>
using namespace std;
typedef long long ll;
typedef pair<int,int> PII;
int n,m;
char g[55][55];
bool st[55][55];
int dx4[]={-1,0,1,0};
int dy4[]={0,1,0,-1};
int dx8[]={-1,-1,0,1,1,1,0,-1};//搜海水是八联通,陆地是四联通
int dy8[]={0,1,1,1,0,-1,-1,-1};
int ans;
bool flag;
void dfs1(int x,int y)
{
g[x][y]='2';
for(int k=0;k<8;k++)
{
int x0=x+dx8[k];
int y0=y+dy8[k];
if(x0<0||y0<0||x0>n+1||y0>m+1||g[x0][y0]!='0') continue;
dfs1(x0,y0);
}
}
void dfs2(int x,int y)
{
st[x][y]=true;
for(int k=0;k<4;k++)
{
int x0=x+dx4[k];
int y0=y+dy4[k];
if(g[x0][y0]=='2') flag=true;//在这个联通块的外部可以搜到置为2的海水,则可以确定是不在环内的岛屿,因为在环内的岛屿一定搜不到2
if(x0<=0||y0<=0||x0>n||y0>m||st[x0][y0]||g[x0][y0]!='1') continue;
dfs2(x0,y0);
}
}
void solve()
{
ans=0;
memset(st,false,sizeof st);
cin>>n>>m;
for(int i=0;i<=n+1;i++) g[i][0]='0';
for(int i=0;i<=m+1;i++) g[0][i]='0';
for(int i=0;i<=m+1;i++) g[n+1][i]='0';
for(int i=0;i<=n+1;i++) g[i][m+1]='0';
for(int i=1;i<=n;i++)
for(int j=1;j<=m;j++)
cin>>g[i][j];
dfs1(0,0);//将外部海水均置为2
for(int i=1;i<=n;i++)
{
for(int j=1;j<=m;j++)
{
if(g[i][j]=='1'&&!st[i][j])
{
flag=false;
dfs2(i,j);
if(flag) ans++;
}
}
}
cout<<ans<<endl;
}
int main()
{
ios::sync_with_stdio(0);
cin.tie(0);
int t; cin>>t;
while(t--) solve();
return 0;
}