我要评论
题目描述
校园里有一些小河和一些湖泊，现在，我们把它们通一看成水池，假设有一张我们学校的某处的地图，这个地图上仅标识了此处是否是水池，现在，你的任务来了，请用计算机算出该地图中共有几个水池。
输入
第一行输入一个整数N，表示共有N组测试数据
每一组数据都是先输入该地图的行数n(0<n<100)与列数m(0<m<100)，然后，输入接下来的m行每行输入n个数，表示此处有水还是没水（1表示此处是水池，0表示此处是地面）
输出
输出该地图中水池的个数。
要注意，每个水池的旁边（上下左右四个位置）如果还是水池的话的话，它们可以看做是同一个水池。
样例输入
2 3 4 1 0 0 0 0 0 1 1 1 1 1 0 5 5 1 1 1 1 0 0 0 1 0 1 0 0 0 0 0 1 1 1 0 0 0 0 1 1 1 样例输出
2 3 #include<bits/stdc++.h> using namespace std; int n,m; const int maxn=1000; int a[maxn][maxn]; int inq[maxn][maxn];//判断是否入过队 int X[4]={0,0,1,-1}; int Y[4]={1,-1,0,0}; struct node{ int x; int y; }Node; bool judge(int x,int y){ if(x<0||y<0||x>=n||y>=m)return false; if(a[x][y]==0||inq[x][y]==1)return false; return true; } void bfs(int x,int y){ queue<node>s; Node.x=x,Node.y=y; s.push(Node); inq[x][y]=true; while(s.empty()!=1){ node t=s.front(); s.pop(); for(int i=0;i<4;i++){ int newx=t.x+X[i]; int newy=t.y+Y[i]; if(judge(newx,newy)){ Node.x=newx,Node.y=newy; s.push(Node); inq[newx][newy]=true; } } } } int main(){ ios::sync_with_stdio(false); cin.tie(0); cout.tie(0); int T; cin>>T; while(T--){ cin>>n>>m; for(int i=0;i<n;i++){ for(int j=0;j<m;j++){ cin>>a[i][j]; inq[i][j]=false;//这里是多组输入，所以一定要初始化，不然容易出错 } } int ans=0; for(int i=0;i<n;i++){ for(int j=0;j<m;j++){ if(a[i][j]==1&&inq[i][j]==0){ ans++; bfs(i,j); } } } cout<<ans<<endl; } return 0; } 本文地址：https://blog.csdn.net/tutoua/article/details/107909098
您可能感兴趣的文章:
如您对本文有疑问或者有任何想说的，请点击进行留言回复，万千网友为您解惑！
网友评论