什么是BFS

BFS又称为广度优先搜索。举个例子：一群老鼠走迷宫。假设老鼠是无限多的，这群老鼠进去后，在每个路口派出部分老鼠探索所有没走过的路。走某条路的老鼠，如果碰壁无法前行，就停下；如果到达的路口已经有其他老鼠探索过了，也停下。很显然，所有的道路都会走到，而且不会重复。这个思路就是BFS。BFS看起来像“并行计算”，不过，由于程序是单机顺序运行的，所以可以把BFS看成是并行计算的模拟。

如何实现BFS

在具体编程时，一般用队列这种数据结构来具体实现BFS，甚至可以说“BFS=队列”。

代码如下：

#include<iostream>
#include<queue>
#define CHECK(x,y)(x>=0&&x<=wx&&y>=0&&y<=hy)
using namespace std;

int wx,hy,num;
char room[23][23];
int dir[4][2]={{-1,0},{0,-1},{1,0},{0,1}};
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()){
        next=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.y,next.y)&&room[next.x][next.y]=='.'){
                room[next.x][next.y]='#';
                num++;
                q.push(next);
            }
        }
    }
}

int main(){
    int dx,dy,x,y;
    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;
}