BFS（广度优先搜索）

广度优先搜索（或称宽度优先搜索)：一般用队列(queue)这种你数据结构来具体实现BFS，甚至可以说“BFS=队列”。

一、Red and Black

#include <iostream>
#include <queue>
using namespace std;
char room[23][23];
int dir[4][2]={
	{-1,0},
	{1,0},
	{0,-1},
	{0,1}
};
int Wx,Hy,num;
#define CHECK(x,y) (x<Wx&&x>=0&&y<Hy&&y>=0)
struct node {int x,y;};

void BFS(int dx,int dy)
{
	num=1;
	queue <node> q;
	node start,next;
	start.x=dx;
	start.y=dy;
	q.push(start);
	while(!q.empty()){
		start=q.front();
		q.pop();
		for(int i=0;i<4;i++){
			next.x=start.x+dir[i][0];
			next.y=start.y+dir[i][1];
			if(CHECK(next.x,next.y)&&room[next.x][next.y]=='.'){
				room[next.x][next.y]='#';
				num++;
				q.push(next);
			}
		}
	}
}

int main(){
	int x,y,dx,dy;
	while(cin>>Wx>>Hy){
		if(Wx==0&&Hy==0) break;
		for(y=0;y<Hy;y++){
			for(x=0;x<Wx;x++){
				cin>>room[x][y];
				if(room[x][y]=='@'){
					dx=x;
					dy=y;
				}
			}
		}
		num=0;
		BFS(dx,dy);
		cout<<num<<endl;
	}	
	return 0;
}

二、迷宫寻路

#include <iostream>
#include <queue>
using namespace std;

char room[100][100];
int dir[4][2]={
	{-1,0},
	{1,0},
	{0,-1},
	{0,1}
};

#define CHECK(x,y) (x<=n&&x>0&&y<=m&&y>0)
struct node{int x,y;};

int BFS(int n,int m){
	int flag=0;
	room[1][1]='#';
	queue <node> q;
	node start,next;
	start.x=1;
	start.y=1;
	q.push(start);
	while(!q.empty()){
		start=q.front();
		q.pop();
		for(int i=0;i<4;i++){
			next.x=start.x+dir[i][0];
			next.y=start.y+dir[i][1];
			if(CHECK(next.x,next.y)&&room[next.x][next.y]=='.'){
				room[next.x][next.y]='#';
				if(next.x==n&&next.y==m) flag++;
				q.push(next);
			}
		}
	}
	return flag;
}

int main(){
	int x,y,n,m;
	while(cin>>n>>m){
		
		if(n==0&&m==0) break;
		for(x=1;x<=n;x++){
			for(y=1;y<=m;y++){
				cin>>room[x][y];
			}
		}
		if(BFS(n,m)) cout<<"Yes";
		else cout<<"No";
	}
}

三、填涂颜色

#include <bits/stdc++.h>
using namespace std;
int room[35][35];
int bigroom[35][35];
int hhh[35][35];
int dir[4][2]={
	{-1,0},
	{1,0},
	{0,-1},
	{0,1}
};
int n;

#define CHECK(x,y) (x>=1&&x<=n&&y>=1&&y<=n)
#define CHECKPRO(x,y) (x==1||x==n||y==1||y==n)
struct node{int x,y;};

void BFS(int k,int l){
	for(int i=1;i<=n;i++){
		for(int j=1;j<=n;j++){
			room[i][j]=bigroom[i][j];
		}
	}
	int flag=0;
	queue <node> q;
	node start,next;
	start.x=k;
	start.y=l;
	room[k][l]=3;
	q.push(start);
	while(!q.empty()){
		start=q.front();
		q.pop();
		for(int i=0;i<4;i++){
			next.x=start.x+dir[i][0];
			next.y=start.y+dir[i][1];
			if(CHECK(next.x,next.y)&&room[next.x][next.y]==0){
				room[next.x][next.y]=3;
				q.push(next);
				
				//cout<<next.x<<"     "<<next.y<<endl;
				
				if(CHECKPRO(next.x,next.y)) flag++;
			}
		}
	}
	if(!flag&&bigroom[k][l]==0) hhh[k][l]=1;
	return;
}


int main(){
	cin>>n;
	for(int i=1;i<=n;i++){
		for(int j=1;j<=n;j++){
			cin>>bigroom[i][j];
		}
	}
	for(int i=1;i<=n;i++){
		for(int j=1;j<=n;j++){
			BFS(i,j);
		}
	}	
	
	for(int i=1;i<=n;i++){
		for(int j=1;j<=n;j++){
			//BFS(i,j);
			if(hhh[i][j]==1&&!(bigroom[i][j]==0&&CHECKPRO(i,j))) bigroom[i][j]=2;
			//if(bigroom[i][j]==0&&CHECKPRO(i,j)) bigroom[i][j]=0;
			cout<<bigroom[i][j]<<" ";
		}
		cout<<endl;
	}
	return 0;
}

四、 [USACO10OCT] Lake Counting S

#include <bits/stdc++.h>
using namespace std;
char room[120][120];
int dir[8][2]={
	{-1,-1},
	{-1,0},
	{-1,1},
	{0,-1},
	{0,1},
	{1,-1},
	{1,0},
	{1,1}
};
int wx,hy,num=0;

#define CHECK(x,y) (x>=1&&x<=wx&&y>=1&&y<=hy)
struct node {int x,y;};

int BFS(int dx,int dy){
	int flag=0;
	queue <node> q;
	node start,next;
	start.x=dx;
	start.y=dy;
	room[dx][dy]='.';
	q.push(start);
	while(!q.empty()){
		flag++;
		start=q.front();
		q.pop();
		for(int i=0;i<8;i++){
			next.x=start.x+dir[i][0];
			next.y=start.y+dir[i][1];
			if(CHECK(next.x,next.y)&&room[next.x][next.y]=='W'){
				q.push(next);
				room[next.x][next.y]='.';
			}
		}
	}
	return flag;
}


int main(){
	cin>>wx>>hy;
	int tem,num=0;
	for(int i=1;i<=wx;i++){
		for(int j=1;j<=hy;j++){
			cin>>room[i][j];
		}
	}
	for(int i=1;i<=wx;i++){
		for(int j=1;j<=hy;j++){
			if(room[i][j]=='W'){
				BFS(i,j);
				num++;
			}
		}
	}	
	cout<<num;
	return 0;
}