Ignatius and the Princess I
Time Limit: 2000/1000 MS (Java/Others)Memory Limit: 65536/32768 K (Java/Others)
Total Submission(s): 6305Accepted Submission(s): 1882
Special JudgeProblem Description
The Princess has been abducted by the BEelzebub feng5166, our hero Ignatius has to rescue our pretty Princess. Now he gets into feng5166's castle. The castle is a large labyrinth. To make the problem simply, we assume the labyrinth
is a N*M two-dimensional array which left-top corner is (0,0) and right-bottom corner is (N-1,M-1). Ignatius enters at (0,0), and the door to feng5166's room is at (N-1,M-1), that is our target. There are some monsters in the castle, if Ignatius meet them,
he has to kill them. Here is some rules:
1.Ignatius can only move in four directions(up, down, left, right), one step per second. A step is defined as follow: if current position is (x,y), after a step, Ignatius can only stand on (x-1,y), (x+1,y), (x,y-1) or (x,y+1).
2.The array is marked with some characters and numbers. We define them like this:
. : The place where Ignatius can walk on.
X : The place is a trap, Ignatius should not walk on it.
n : Here is a monster with n HP(1<=n<=9), if Ignatius walk on it, it takes him n seconds to kill the monster.
Your task is to give out the path which costs minimum seconds for Ignatius to reach target position. You may assume that the start position and the target position will never be a trap, and there will never be a monster at the start position.
Input
The input contains several test cases. Each test case starts with a line contains two numbers N and M(2<=N<=100,2<=M<=100) which indicate the size of the labyrinth. Then a N*M two-dimensional array follows, which describe the whole
labyrinth. The input is terminated by the end of file. More details in the Sample Input.
Output
For each test case, you should output "God please help our poor hero." if Ignatius can't reach the target position, or you should output "It takes n seconds to reach the target position, let me show you the way."(n is the minimum
seconds), and tell our hero the whole path. Output a line contains "FINISH" after each test case. If there are more than one path, any one is OK in this problem. More details in the Sample Output.
Sample Input
56
.XX.1.
..X.2.
2...X.
...XX.
XXXXX.
56
.XX.1.
..X.2.
2...X.
...XX.
XXXXX1
56
.XX...
..XX1.
2...X.
...XX.
XXXXX.
SampleOutput
Ittakes13secondstoreachthetargetposition,letmeshowyoutheway.
1s:(0,0)->(1,0)
2s:(1,0)->(1,1)
3s:(1,1)->(2,1)
4s:(2,1)->(2,2)
5s:(2,2)->(2,3)
6s:(2,3)->(1,3)
7s:(1,3)->(1,4)
8s:FIGHTAT(1,4)
9s:FIGHTAT(1,4)
10s:(1,4)->(1,5)
11s:(1,5)->(2,5)
12s:(2,5)->(3,5)
13s:(3,5)->(4,5)
FINISH
Ittakes14secondstoreachthetargetposition,letmeshowyoutheway.
1s:(0,0)->(1,0)
2s:(1,0)->(1,1)
3s:(1,1)->(2,1)
4s:(2,1)->(2,2)
5s:(2,2)->(2,3)
6s:(2,3)->(1,3)
7s:(1,3)->(1,4)
8s:FIGHTAT(1,4)
9s:FIGHTAT(1,4)
10s:(1,4)->(1,5)
11s:(1,5)->(2,5)
12s:(2,5)->(3,5)
13s:(3,5)->(4,5)
14s:FIGHTAT(4,5)
FINISH
Godpleasehelpourpoorhero.
FINISH
#include<stdio.h>
#include<queue>
using namespace std;
int m,n;
char a[105][105];
int d[4][2]={{-1,0},{0,-1},{1,0},{0,1}};
struct haha
{
int x1;
int y1;
int ti;
friend bool operator < (haha a, haha b)
{
return a.ti > b.ti; //重载小于号使得小的先出队列
}
}q,temp;
int flag[105][105];
struct xixi
{
int x2;
int y2;
}pre[105][105];
void BFS()
{
int i,x,y,time,x0,y0,xi,yi,j,tm;
q.x1=n-1;q.y1=m-1;q.ti=0;
if(a[n-1][m-1]>=48&&a[n-1][m-1]<=57)
q.ti=a[n-1][m-1]-'0';
priority_queue<haha>duilie;//这个要放进来 每次都要进行从新分配一个队列 不然的话 就会造成上一次的数据无法清空
duilie.push(q);
while(!duilie.empty())
{
temp=duilie.top();
duilie.pop();
if(temp.x1==0&&temp.y1==0)
{
printf ("It takes %d seconds to reach the target position, let me show you the way.\n",temp.ti);
xi=0;yi=0;tm=1;
while(pre[xi][yi].x2!=-1)
{
x0=pre[xi][yi].x2;
y0=pre[xi][yi].y2;
printf("%ds:(%d,%d)->(%d,%d)\n",tm++,xi,yi,x0,y0);
if(a[x0][y0]>=48&&a[x0][y0]<=57)//这里不小心 把xo写成了x WA了 10多次 哎 这就是不细心的下场啊 耽误我3个多小时啊
{
for(j=0;j<a[x0][y0]-'0';j++)////
printf ("%ds:FIGHT AT (%d,%d)\n",tm++,x0,y0);
}
xi=x0;
yi=y0;
}
return ;
}
for(i=0;i<4;i++)
{
x=temp.x1+d[i][0];
y=temp.y1+d[i][1];
if(x<0||y<0||x>=n||y>=m||a[x][y]=='X'||flag[x][y]!=0) continue;
if(a[x][y]>=48&&a[x][y]<=57)
{ time=temp.ti+a[x][y]-'0'; time=time+1;}
else
time=temp.ti+1;
q.ti=time;q.x1=x;q.y1=y;
flag[x][y]=1;
pre[x][y].x2=temp.x1; pre[x][y].y2=temp.y1;
duilie.push(q);
}
}
puts("God please help our poor hero.");
}
int main()
{
int i;
while (scanf ("%d %d", &n, &m)!=EOF)
{
for(i=0;i<n;i++)
scanf("%s",a[i]);
memset(flag,0,sizeof(flag));
flag[n-1][m-1]=1;
pre[n-1][m-1].x2=-1;
BFS();
puts("FINISH");
}
return 0;
}
/*参考了 大牛的代码 一开始按照自己的方法弄了个runtime error 郁闷死了 这个方法简便 很好的一种思想 记每一步都要标记上一步的xy
并且 倒着去搜索 很方便按题意的要求 输出数据 帅呆了 */
分享到:
相关推荐
hdu 3085 一道bfs题 一点值得注意的,鬼魅先走,mm与gg后走,直接模拟这个这个场景,突出时间的先后性,一秒与一秒的区别。。。这样模拟很难出错
一个十分简单的程序,能够ac杭电hdu的第2050题,无注释,简单明了
离线OJ题库(HDU ZJU等,部分有答案),需联网。
HDU的一题........HDU DP动态规
ACM HDU题目分类,我自己总结的大概只有十来个吧
收集的部分HDOJ杭电ACM题的代码 大牛勿下 全是基础供初级acmer使用
HDU的1250,主要是利用高精度加法,但是代码有点繁琐,效率不是很高
杭电ACMhdu1163
The least common multiple (LCM) of a set of positive integers is the smallest positive integer which is divisible by all the numbers in the set. For example, the LCM of 5, 7 and 15 is 105. Input Input...
HDU1059的代码
hdu1001解题报告
hdu 1574 passed sorce
HDU 动态规划(46道题目
100道 acm C语言 hdu 解题报告
hdu2101AC代码
hdu acm 教案 搜索入门 hdu acm 教案 搜索入门
HDU 1022 Train Problem I 附详细思路
hdu-acm源代码(上百题)hdu-acm源代码、hdu-acm源代码hdu-acm源代码
搜索 dfs 解题代码 hdu1241
我写的hdu上的一些题AC的题的代码 也许你会有用