7 8 #.#####. #.a#..r. #..#x... ..#..#.# #...##.. .#...... ........
13
#include<iostream> #include<cstring> #include<cstdlib> #include<queue> using namespace std; #define max 201 char a[max][max]; int move[4][2]={-1,0,1,0,0,1,0,-1},v[max][max];//移动方向排列在这里很重要。 int n,m,ans; struct node { int x,y,step; }; void bfs(int i,int j) { queue<node>q; node now,next; now.x=i; now.y=j; v[now.x][now.y]=1; now.step=0; q.push(now); while(!q.empty()) { now=q.front(); q.pop(); if(a[now.x][now.y]=='r') { ans=now.step; return ; } else { for(int t=0;t<4;t++) { next.x=now.x+move[t][0]; next.y=now.y+move[t][1]; if(!v[next.x][next.y]&&a[next.x][next.y]!='#'&&next.x>=0&&next.x<n&&next.y>=0&&next.y<m) { v[next.x][next.y]=1; if(a[next.x][next.y]=='.'||a[next.x][next.y]=='r') next.step=now.step+1; else if(a[next.x][next.y]=='x') next.step=now.step+2; q.push(next); } } } } return ; } int main() { int i,j; while(cin>>n>>m) { ans=0; memset(v,0,sizeof(v)); for(i=0;i<n;i++) { for(j=0;j<m;j++) { cin>>a[i][j]; } } for(i=0;i<n;i++) { for(j=0;j<m;j++) { if(a[i][j]=='a') bfs(i,j); } } if(ans) cout<<ans<<endl; else cout<<"Poor ANGEL has to stay in the prison all his life.\n"; } return 0; }
#include<iostream> #include<cstring> #include<queue> using namespace std; #define M 205 char c[M][M]; int v[M][M]; int w[4][2]={-1,0,0,-1,0,1,1,0}; int ans,n,m; struct node { int x,y,time; friend bool operator< (const node a,const node b) { return a.time>b.time; } }; void bfs(int a,int b) { node now,tmp; priority_queue<node> q; now.time=0; now.x=a; now.y=b; memset(v,0,sizeof(v)); v[a][b]=1; q.push(now); while(!q.empty()) { now=q.top(); q.pop(); if(c[now.x][now.y]=='r') { ans=now.time; return ; } for(int i=0;i<4;i++) { tmp.x=now.x+w[i][0]; tmp.y=now.y+w[i][1]; if(tmp.x>=0&&tmp.x<n&&tmp.y>=0&&tmp.y<m &&!v[tmp.x][tmp.y]&&c[tmp.x][tmp.y]!='#') { v[tmp.x][tmp.y]=1; if(c[tmp.x][tmp.y]=='r'||c[tmp.x][tmp.y]=='.') tmp.time=now.time+1; if(c[tmp.x][tmp.y]=='x') tmp.time=now.time+2; q.push(tmp); } } } return; } int main() { while(cin>>n>>m) { int i,j,x,y; for(i=0;i<n;i++) for(j=0;j<m;j++) { cin>>c[i][j]; if(c[i][j]=='a') x=i,y=j; } ans=0; bfs(x,y); if(ans) cout<<ans<<endl; else cout<<"Poor ANGEL has to stay in the prison all his life.\n"; } return 0; }
杭电 1242 Rescue(广搜),布布扣,bubuko.com
原文:http://blog.csdn.net/u012766950/article/details/38146917