岛屿个数
#include<iostream>
#include<queue>
#include<cstring>
#define x first
#define y second
using namespace std;
typedef pair<int,int> PII;
const int N=55;
int n,m;
char graph[N][N];//存储格子地图
bool vis[N][N];
bool used[N][N];
int dx[]={0,1,-1,0,1,1,-1,-1};
int dy[]={1,0,0,-1,1,-1,1,-1};
void bfs(int x,int y){//遍历点(x,y)所在的连通块中的所有点
queue<PII> q;
q.push({x,y});
vis[x][y]=true;
while(q.size()){
PII u=q.front();
q.pop();
for(int i=0;i<4;i++){
int nx=u.x+dx[i],ny=u.y+dy[i];
if(nx<1||nx>n||ny<1||ny>m||vis[nx][ny]||graph[nx][ny]=='0')continue;
vis[nx][ny]=true;
q.push({nx,ny});
}
}
}
bool escape(int x,int y){//判断点(x,y)所在的岛屿是不是子岛屿
queue<PII> q;
q.push({x,y});
used[x][y]=true;
while(q.size()){
PII u=q.front();
q.pop();
for(int i=0;i<8;i++){
int nx=u.x+dx[i],ny=u.y+dy[i];
if(nx<1||nx>n||ny<1||ny>m)return true;//能到边界,即不会被其他的连通块阻挡
if(used[nx][ny]||graph[nx][ny]=='1')continue;
used[nx][ny]=true;
q.push({nx,ny});
}
}
return false;//不能到边界,是子岛屿
}
int main(){
ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
int t;
cin>>t;
while(t--){
memset(vis,false,sizeof vis);//每次都要重置vis数组
int res=0;//记录一共有多少个连通块,初始化几个连通块就有几个岛屿
cin>>n>>m;
for(int i=1;i<=n;i++)
for(int j=1;j<=m;j++)
cin>>graph[i][j];
vector<PII> v;//记录每个岛屿的第一个点的坐标
for(int i=1;i<=n;i++)
for(int j=1;j<=m;j++){
if(!vis[i][j]&&graph[i][j]=='1'){
bfs(i,j);//遍历当前连通块中的所有点
res++;//连通块的个数加一
v.push_back({i,j});
}
}
for(int i=0;i<v.size();i++){
memset(used,false,sizeof used);
//如果当前连通块被其他的连通块包围着,即当前连通块往外扩展到不了地图的边界
if(!escape(v[i].x,v[i].y))//不能到边界,是子岛屿,则岛屿个数减一
res--;
}
cout<<res<<endl;
}
return 0;
}