http://acm.hdu.edu.cn/showproblem.php?pid=1242
bfs求最短路径，不同的是如果点上是‘X’则花费为2，搜索的时候注意这一点即可。
#include <iostream> #include <stdio.h> #include <algorithm> #include <string.h> #include <queue> using namespace std; struct node { int x,y,d; }; int dir[4][2]={{1,0},{-1,0},{0,1},{0,-1}}; int m,n; bool flag[205][205]; char mm[205][205]; int x1,y1,x2,y2; int bfs() { node p,q; queue<node>Q; p.x=x1; p.y=y1; p.d=0; Q.push(p); flag[x1][y1]=true; while(!Q.empty()) { p=Q.front(); Q.pop(); if(mm[p.x][p.y]=='a') { return p.d; } else if(mm[p.x][p.y]=='x') { mm[p.x][p.y]='.'; p.d+=1; Q.push(p); continue; } for(int i=0;i<4;i++) { q.x=p.x+dir[i][0]; q.y=p.y+dir[i][1]; q.d=p.d; if(q.x>=0&&q.x<m&&q.y>=0&&q.y<n) { if(mm[q.x][q.y]!='#'&&!flag[q.x][q.y]) { flag[q.x][q.y]=true; q.d+=1; Q.push(q); } } } } return -1; } int main() { while(scanf("%d%d",&m,&n)!=EOF) { int i,j; memset(flag,0,sizeof(flag)); for(i=0;i<m;i++) { for(j=0;j<n;j++) { cin>>mm[i][j]; if(mm[i][j]=='r') { x1=i; y1=j; } if(mm[i][j]=='a') { x2=i; y2=j; } } } int z=bfs(); if(z!=-1)cout<<z<<endl; else cout<<"Poor ANGEL has to stay in the prison all his life."<<endl; } return 0; }
