HDOJ 1312
先介绍一下BFS和DFS。
深度优先搜索，它的思想是从一个顶点v0开始，沿着一条路一直走到底，如果发现不能到达目标解，就返回上一个结点，然后从另一个结点一直走到底。
对于BFS，我们假设一个节点衍生出来的相邻节点平均的个数是N个，那么当起点开始搜索的时候，队列有一个节点，当起点拿出来后，把它相邻的节点放进去，那么队列就有N个节点，当下一层的搜索中再加入元素到队列的时候，节点数达到了N2，你可以想想，一旦N是一个比较大的数的时候，这个树的层次又比较深，那这个队列就得需要很大的内存空间了。
于是广度优先搜索的缺点出来了：在树的层次较深&子节点数较多的情况下，消耗内存十分严重。广度优先搜索适用于节点的子节点数量不多，并且树的层次不会太深的情况。
那么深度优先就可以克服这个缺点，因为每次搜的过程，每一层只需维护一个节点。但回过头想想，广度优先能够找到最短路径，那深度优先能否找到呢？深度优先的方法是一条路走到黑，那显然无法知道这条路是不是最短的，所以你还得继续走别的路去判断是否是最短路？
于是深度优先搜索的缺点也出来了：难以寻找最优解，仅仅只能寻找有解。其优点就是内存消耗小，克服了刚刚说的广度优先搜索的缺点。
再说一下这道题的坑点，题目先给了列后给的行！
法一：DFS解法：
#include<iostream>
#include<string.h>
using namespace std;
int dir[4][2]={
1,0,-1,0,0,1,0,-1};
char mp[21][21];
bool vis[21][21];
int W,H;
int dx,dy; //起点和终点
int ans;//记录满足的个数void dfs(int x,int y){vis[x][y]=true;int k;for(k=0;k<4;k++){int nx=x+dir[k][0];int ny=y+dir[k][1];if(nx>=0 &&nx<H &&ny>=0 &&ny<W && !vis[nx][ny]&&mp[nx][ny]=='.'){ans++;dfs(nx,ny);}}
}
int main(){int i,j;while(cin>>W>>H){if(W==0||H==0) break;memset(vis,false,sizeof(vis));for(i=0;i<H;i++){for(j=0;j<W;j++){cin>>mp[i][j];if(mp[i][j]=='@'){dx=i,dy=j;}}}ans=1;dfs(dx,dy);cout<<ans<<endl;}return 0;
}法二：BFS解法
#include<iostream>
#include<cstdio>
#include<queue>
#include<string.h>
using namespace std;
struct node{int x,y;
}q[1010];
char mp[21][21];
int dir[4][2]={
1,0,-1,0,0,1,0,-1};//方向数组
bool vis[21][21];
int W,H;
int ans;//记录可以走的格子，起点算一次。void bfs(int a,int b){queue<node > que;node sta,end;sta.x=a;sta.y=b;que.push (sta); //压入初始值vis[a][b]=true;while(!que.empty()){int i;sta=que.front ();que.pop ();for(i=0;i<4;i++){end.x=sta.x+dir[i][0];end.y=sta.y+dir[i][1];if(end.x>=0 &&end.x<H &&end.y>=0 &&end.y<W &&!vis[end.x][end.y]&&mp[end.x][end.y]=='.'){vis[end.x][end.y]=true;ans++;que.push (end);}}}
}int main(){int i,j,dx,dy;while(cin>>W>>H &&(W||H)){memset(vis,0,sizeof(vis));for(i=0;i<H;i++)for(j=0;j<W;j++){cin>>mp[i][j];if(mp[i][j]=='@'){ //记录起点dx=i;dy=j;}}ans=1;bfs(dx,dy);cout<<ans<<endl;}return 0;
}