No.1 【hdu 1312】
#include<queue>
#include<iostream>
#define check(x,y)(x<wx&&x>=0&&y>=0&&y<hy)
using namespace std;
char room[23][23];
int dir[5][3]={
{-1,0},{0,-1},{1,0},{0,1}
};int wx,hy,sum=0;struct node{int x,y;};void bfs(int dx,int dy);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;}}}}bfs(dx,dy);cout<<sum<<endl;}void bfs(int dx,int dy)
{sum=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]='#';q.push(next);}}}
}No2. 【poj 3278】
#include<iostream>
#include<queue>
#include<cstring>
#include<cstdio>
using namespace std;bool vis[1000];int step[1000];queue<int> q;int bfs(int n,int k)
{int head,next;q.push(n);step[n]=0;vis[n]=true;while(!q.empty()){head=q.front();q.pop();for(int i=1;i<=3;i++){if(i==1) next=head-1;else if(i==2) next=head+1;else if(i==3) next=head*2;if(!vis[next]){q.push(next);step[next]=step[head]+1;vis[next]=true;}if(next==k) return step[next];}}}
int main()
{int n,k;while(cin>>n>>k){memset(step,0,sizeof(step));memset(vis,false,sizeof(vis));if(n>=k) cout<<n-k;else cout<<bfs(n,k);} return 0;
}
No3 【课本练习】
/*给定一个大小为N*M的迷宫。迷宫由通道和
墙壁组成，每一步可以向邻接的上下左右四
格的通道移动。请求出从起点到终点所需的
最小步数。# . S G 分别表示墙壁，通道，
起点和终点*/ #include<iostream>
#include<queue>
#include<cstring>
#include<cstdio>
using namespace std;char maze[1000][1000];
bool maze_[1000][1000];
int step[1000][1000];
int n,m;int dir[5][3]={
{-1,0},{0,-1},{1,0},{0,1}
};struct node{int x,y;};queue<node> q;int bfs(int dx,int dy)
{memset(step,0,sizeof(step));node head,next;head.x=dx;head.y=dy;q.push(head);while(!q.empty()){head=q.front();q.pop();for(int i=0;i<4;i++){next.x=head.x+dir[i][0];next.y=head.y+dir[i][1];if(next.x>n||next.x<1||next.y>m||next.y<1) continue;if(maze[next.x][next.y]=='.'&&maze_[next.x][next.y]==false){maze_[next.x][next.y]=true;q.push(next);step[next.x][next.y]=step[head.x][head.y]+1;}if(maze[next.x][next.y]=='G') return step[next.x-dir[i][0]][next.y-dir[i][1]]+1;}}
}int main()
{int dx,dy;cin>>n>>m;memset(maze_,false,sizeof(maze_));for(int i=1;i<=n;i++){for(int j=1;j<=m;j++){cin>>maze[i][j];if(maze[i][j]=='S'){dx=i;dy=j;maze_[i][j]=true;}}}cout<<bfs(dx,dy);
}