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 * by Moligpy. The *
is described as a N * M (N, M <= 200) matrix. There are WALLs, ROADs,
and GUARDs in the *.
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.)
was caught by the MOLIGPY! He was put in * by Moligpy. The *
is described as a N * M (N, M <= 200) matrix. There are WALLs, ROADs,
and GUARDs in the *.
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.
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 * all his
life."
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 * all his
life."
Sample Input
7 8
#.#####.
#.a#..r.
#..#x...
..#..#.#
#...##..
.#......
........
Sample Output
13
Author
CHEN, Xue
Source
题意：一个公主被抓 公主有很多个朋友 在图上 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 * all his life.\n" );
else
printf("%d\n",ans);
}
}