智能书签

数据构造-队列-广搜的根柢使用。

【题目问题形容】

一个n * m的方格图，一些格子被涂成为了黑涩，正在方格图中被标为1，皂涩格子标为0。问有几多多个四连通的黑涩格子连通块。四连通的黑涩格子连通块指的是一片由黑涩格子构成的区域，此中的每个黑涩格子能通过四连通的走法（高下摆布），只走黑涩格子，达到该联通块中的其他黑涩格子。

【输入】

第一止两个整数n,m(1≤n,m≤100)，默示一个n * m的方格图。

接下来n止，每止m个整数，划分为0或1，默示那个格子是黑涩还是皂涩。

【输出】

一止一个整数ans，默示图中有ans个黑涩格子连通块。

【输入样例】

3 3
1 1 1
0 1 0
1 0 1
【输出样例】

3

【试题阐明】

原题是广搜（队列）典型题，必须把握清楚。威力更好的使用于广搜问题。

#include<iostream> using namespace std; const int N=110; const int flag[4][2]={{0,1},{0,-1},{1,0},{-1,0}}; int a[N][N],queue[N*N][2]; int n,m,ans; bool p[N][N]; ZZZoid bfs(int V,int y) //队列广搜典型题 { int front=0,rear=1; //队列初始化：队头为0，队尾为1入队 queue[1][0]=V,queue[1][1]=y; //入队 while(front<rear) //曲到f=r 队列为空；一次扩展收配完毕 { front++; V=queue[front][0]; y=queue[front][1]; for(int i=0;i<4;i++) { int V1=V+flag[i][0]; //扩展节点 int y1=y+flag[i][1]; //满足边界条件，2个表的条件 为入队作筹备。 if(V1<1||y1<1||V1>n||y1>m||!a[V1][y1]||p[V1][y1]) continue; p[V1][y1]=true; // 对应作符号 rear++; //队尾++为下次入队作筹备 queue[rear][0]=V1; //入队 queue[rear][1]=y1; //入队 } } } int main() { cin>>n>>m; for(int i=1;i<=n;i++) for(int j=1;j<=m;j++) cin>>a[i][j]; for(int i=1;i<=n;i++) //搜寻初步 for(int j=1;j<=m;j++) if(a[i][j]&&!p[i][j]) { ++ans;bfs(i,j);} //几屡次队列收配等于几多个解 cout<<ans<<'\n'; return 0; }