水池数目

没啥好解释的

思想和最大岛屿的广搜一样

代码

#include<stdio.h>
#include<queue>
using namespace std;
int m,n,f[4][2]={0,-1,-1,0,0,1,1,0},a[505][505];
struct node
{
int x;
int y;
};
queue<node>Q;
void bfs(int x,int y)
{
node q;
q.x=x;
q.y=y;
Q.push(q);
a[x][y]=0;
while(!Q.empty())
{
node e,w;
e=Q.front();
for(int i=0;i<4;i++)
{
w.x=e.x+f[i][0];
w.y=e.y+f[i][1];
if(w.x>=0&&w.y>=0&&w.x<m&&w.y<n&&a[w.x][w.y]==1)
{
Q.push(w);
a[w.x][w.y]=0;
}
}
Q.pop();
}
}
int main()
{
int N,count =0;
scanf("%d",&N);
while(N--)
{
scanf("%d%d",&m,&n);
for(int i=0;i<m;i++)
{
for(int j=0;j<n;j++)
{
scanf("%d",&a[i][j]);
}
}
for(int i=0;i<m;i++)
{
for(int j=0;i<n;i++)
{
if(a[i][j]==1)
{
bfs(i,j);
count ++;
}
}
}
printf("%d ",count);
}
}