1329：【例8.2】细胞 【广度优先搜索】

首先你需要知道什么是队列：

由于手搓数组队列比较浪费初学者的时间，建议优先掌握STL大法中的queue队列模板

具体实现：

#include<bits/stdc++.h>
using namespace std;

int main()
{
    queue<int> q;//申请了一个名叫q的队列
	//请问此时q的大小是多少？ 
	cout<<q.size()<<endl;
	//是否为空？ 返回真   size()返回非0不空，返回0就是空 
	cout<<q.empty()<<endl;
	q.push(66); //  从尾部压入66
	q.push(88);//   66 88
	q.push(1);//    66 88 1
	cout<<q.front()<<" "<<q.back()<<endl;
	//输出（弹出）队列中的所有元素 
	while( q.size() ){ //!q.empty()
		cout<<q.front()<<" ";
		q.pop();//从头部弹出 
	}
	cout<<"此时队列为空";  
	return 0;
}

课堂练习：

#include<bits/stdc++.h>
using namespace std;
int main()
{
	queue<char> q;//创建一个字符队列
	q.push('A');
	cout<<q.size()<<endl;//输出1
	q.pop(); //将头部的'A'弹出 
	q.push('B');
 	q.push('B');
	q.push('C');
	q.pop();
	q.push('V');
	//BCV  
	while( q.size() ){//弹出所有元素 并打印 
		cout<<q.front();
		q.pop();
	}
	return 0;
}

例题：1329：【例8.2】细胞

#include<bits/stdc++.h>
using namespace std;
const int N=100;
char mp[N][N];
int n,m,cnt,vis[4][2]={1,0,-1,0,0,-1,0,1}; 
bool st[N][N];//st[i][j]==1 表示第i行第j列的细胞被染色了（烧过了） 
struct node{
	int x,y;
};

void bfs(int x,int y){
	queue<node> q;
	q.push({x,y});//起点入队
	while( q.size() ){
		node tp=q.front();//将队头取出
		q.pop();
		//将当前这个点能够波及到的所有点入队
		for(int i=0;i<4;i++)
		{
			int tx=tp.x+vis[i][0],ty=tp.y+vis[i][1];
			//当前这个是否可以被波及 
			//没越界+是细胞      &&   没染过色 
			if(mp[tx][ty]>='1'&&mp[tx][ty]<='9' && st[tx][ty]==0 ){
				st[tx][ty]=1;
				q.push({tx,ty});//入队！ 
			} 
		 } 
	} 
}

int main()
{
	cin>>n>>m;//行 列 
	for(int i=1;i<=n;i++)//二维数字矩阵的读入 
	    for(int j=1;j<=m;j++)
	        cin>>mp[i][j];
    //非零 并且 未染色st[][]==0 
    for(int i=1;i<=n;i++)
	   for(int j=1;j<=m;j++)
	   {
	   	    if(mp[i][j]!='0' && st[i][j]==0 ){
	   	    	cnt++;//出现了一块新的未染过色的细胞区域
				bfs(i,j);//广度优先搜索：从i，j这个位置开始染色 
            }
		} 
	cout<<cnt<<endl; 
	return 0;
}