Rescue

Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 65536/32768 K (Java/Others)
Total Submission(s): 29263 Accepted Submission(s): 10342

Problem Description

Angel
was caught by the MOLIGPY! He was put in prison by Moligpy. The prison
is described as a N * M (N, M <= 200) matrix. There are WALLs, ROADs,
and GUARDs in the prison.
Angel's friends want to save Angel.
Their task is: approach Angel. We assume that "approach Angel" is to get
to the position where Angel stays. When there's a guard in the grid, we
must kill him (or her?) to move into the grid. We assume that we moving
up, down, right, left takes us 1 unit time, and killing a guard takes 1
unit time, too. And we are strong enough to kill all the guards.
You
have to calculate the minimal time to approach Angel. (We can move only
UP, DOWN, LEFT and RIGHT, to the neighbor grid within bound, of
course.)

Input

First line contains two integers stand for N and M.
Then
N lines follows, every line has M characters. "." stands for road, "a"
stands for Angel, and "r" stands for each of Angel's friend.
Process to the end of the file.

Output

For
each test case, your program should output a single integer, standing
for the minimal time needed. If such a number does no exist, you should
output a line containing "Poor ANGEL has to stay in the prison all his
life."

Sample Input

7 8

#.#####.

#.a#..r.

#..#x...

..#..#.#

#...##..

.#......

........

Sample Output

Author

CHEN, Xue

Source

ZOJ Monthly, October 2003

题意：一个公主被抓公主有很多个朋友在图上 a代表公主 r 代表公主的朋友 #代表墙 .代表路 x代表守卫

打败守卫花费2秒其它一秒现在问你那个朋友能最快解救公主

因为朋友不止一个我们可以BFS从公主开始搜由于打败守卫花的时间长我们选择优先队列每次去最小

这题目数据很水错的代码都能过 dfs应该也能过

 #include<iostream>

 #include<cstdio>

 #include<cmath>

 #include<cstring>

 #include<algorithm>

 #include<queue>

 #include<map>

 #include<set>

 #include<vector>

 #include<cstdlib>

 #include<string>

 #define eps 0.000000001

 typedef long long ll;

 typedef unsigned long long LL;

 using namespace std;

 const int N=+;

 int vis[N][N];

 int n,m;

 char mp[N][N];

 int _x[]={,,-,};

 int _y[]={,,,-};

 struct node{

     int x,y;

     int time;

     friend bool operator < (node a,node b){

         return a.time>b.time;

     }

 }a,b;

 priority_queue<node>q;

 int judge(int x,int y){

     if(x<||x>=n||y<||y>=m)return ;

     if(vis[x][y]==)return ;

     if(mp[x][y]=='#')return ;

     return ;

 }

 int BFS(int x,int y){

     a.time=;

     a.x=x;a.y=y;

     q.push(a);

     vis[x][y]=;

     while(!q.empty()){

         b=q.top();

         q.pop();

         for(int i=;i<;i++){

             int xx=b.x+_x[i];

             int yy=b.y+_y[i];

             if(judge(xx,yy)){

                 vis[xx][yy]=;

                 if(mp[xx][yy]=='x')a.time=b.time+;

                 else if(mp[xx][yy]=='r')return (b.time+);

                 else

                     a.time=b.time+;

                 a.x=xx;

                 a.y=yy;

                 q.push(a);

             }

         }

     }

     return -;

 }

 int main(){

     while(scanf("%d%d",&n,&m)!=EOF){

         while(!q.empty())q.pop();

         memset(vis,,sizeof(vis));

         int x,y;

         for(int i=;i<n;i++)

         for(int j=;j<m;j++){

             cin>>mp[i][j];

             if(mp[i][j]=='a'){

                 x=i;y=j;

                 //a.x=x;a.y=y;a.time=0;

             }

         }

         int ans=BFS(x,y);

         if(ans==-)

             printf("Poor ANGEL has to stay in the prison all his life.\n" );

         else

             printf("%d\n",ans);

     }

 }

巴特西

hdu 1242(BFS+优先队列）

Rescue

最新文章

热门文章