Rescue
Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 65536/32768 K (Java/Others)
Total Submission(s): 5846 Accepted Submission(s): 2168
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
这题要用到优先队列来进行广搜bfs,不然会出现时间长的先到达,这题是我第一次用优先队列,看看哈。
代码:
#include <iostream>
#include <stdio.h>
#include <memory.h>
#include <queue>
using namespace std;
int xx[4] = {1, -1, 0, 0};
int yy[4] = {0, 0, 1, -1};
int map[205][205];
char a[205][205];
int N, M, x1, y1, x2, y2;
bool flag;
struct node
{
friend bool operator < (node a, node b) //优先步数少的
{
return a.step > b.step;
}
int x, y, step;
}n, m;
int main()
{
int i, j;
while(scanf("%d %d", &N, &M) != EOF)
{
for(i = 0; i < N; i++)
{
getchar();
for(j = 0; j < M; j++)
{
scanf("%c", &a[i][j]);
map[i][j] = 10000000; //初始化
if(a[i][j] == 'r')
x1 = i, y1 = j;
if(a[i][j] == 'a')
x2 = i, y2 =j;
}
}
flag = false;
n.x = x1; n.y = y1; n.step = 0;
priority_queue<node> Q; //建立优先队列
Q.push(n);
while(!Q.empty())
{
m = Q.top();
Q.pop();
if(m.x == x2 && m.y == y2) //到达目标
{
flag = true;
break;
}
for(i = 0; i < 4; i++)
{
n.x = m.x + xx[i];
n.y = m.y + yy[i];
if(n.x>=0 && n.x<N && n.y>=0 && n.y<M && a[n.x][n.y]!='#')
{
if(a[n.x][n.y] == 'x') n.step = m.step + 2; //遇到X时间加2
else n.step = m.step + 1; //否则正常加1
if(n.step >= map[n.x][n.y]) continue;
map[n.x][n.y] = n.step;
Q.push(n);
}
}
}
if(flag) printf("%d\n", m.step);
else printf("Poor ANGEL has to stay in the prison all his life.\n");
}
return 0;
}
分享到:
相关推荐
HDU的1250,主要是利用高精度加法,但是代码有点繁琐,效率不是很高
杭电ACMhdu1163
HDU1059的代码
hdu1001解题报告
hdu 1574 passed sorce
HDU的一题........HDU DP动态规
hdu acm 教案 搜索入门 hdu acm 教案 搜索入门
hdu2101AC代码
搜索 dfs 解题代码 hdu1241
hdu 5007 Post Robot 字符串枚举。 暴力一下就可以了。
hdu acm 教案 动态规划(1) hdu acm 教案 动态规划(1)
ACM HDU题目分类,我自己总结的大概只有十来个吧
hdu 1166线段树代码
HDU最全ac代码
hdu动态规划算法集锦
自己做的HDU ACM已经AC的题目
hdu题目分类
HDU图论题目分类
hdu-acm源代码(上百题)hdu-acm源代码、hdu-acm源代码hdu-acm源代码