hdu 1026 Ignatius and the Princess I(bfs)
Ignatius and the Princess I
Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 65536/32768 K (Java/Others)
Total Submission(s): 14677 Accepted Submission(s): 4653
Special Judge
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.
5 6
.XX.1.
..X.2.
2...X.
...XX.
XXXXX.
5 6
.XX.1.
..X.2.
2...X.
...XX.
XXXXX1
5 6
.XX...
..XX1.
2...X.
...XX.
XXXXX.
It takes 13 seconds to reach the target position, let me show you the way.
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:FIGHT AT (1,4)
9s:FIGHT AT (1,4)
10s:(1,4)->(1,5)
11s:(1,5)->(2,5)
12s:(2,5)->(3,5)
13s:(3,5)->(4,5)
FINISH
It takes 14 seconds to reach the target position, let me show you the way.
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:FIGHT AT (1,4)
9s:FIGHT AT (1,4)
10s:(1,4)->(1,5)
11s:(1,5)->(2,5)
12s:(2,5)->(3,5)
13s:(3,5)->(4,5)
14s:FIGHT AT (4,5)
FINISH
God please help our poor hero.
FINISH
#include <iostream>
#include <cstdio>
#include <cstring>
#include <queue>
using namespace std; struct node
{
int x,y,step;
friend bool operator < (node n1,node n2) //优先队列,队列从小到大排序
{
return n1.step>n2.step;
}
} s1,s2,ss[][]; //ss数组记录走的所有路径
char map[][];
int visit[][],n,m,t,p;
int f[][]= {,,,-,,,-,}; void BFS()
{
priority_queue <node> q; //优先队列的定义
while(!q.empty())
q.pop();
s1.x=;
s1.y=;
s1.step=;
visit[][]=;
ss[s1.x][s1.y].x=; //起点为左上角
ss[s1.x][s1.y].y=;
q.push(s1);
while(!q.empty())
{
s1=q.top();
q.pop();
if(s1.x==n-&&s1.y==m-) //终点为右下角
{
p=s1.step;
return;
}
for(int i=; i<; i++)
{
s2=s1;
s2.x=s1.x+f[i][];
s2.y=s1.y+f[i][];
if(s2.x>=&&s2.x<n&&s2.y>=&&s2.y<m&&map[s2.x][s2.y]!='X'&&!visit[s2.x][s2.y])
{
visit[s2.x][s2.y]=;
s2.step=s1.step+;
if(map[s2.x][s2.y]>=''&&map[s2.x][s2.y]<='') //遇到怪物的时候需要耗得时间
s2.step=s2.step+map[s2.x][s2.y]-'';
ss[s2.x][s2.y].x=s1.x; //记录走到这一步的上一步坐标
ss[s2.x][s2.y].y=s1.y;
q.push(s2);
}
}
}
p=-; //到不了的标记
return;
} void print(int x,int y) //深搜输出,从终点开始往前搜
{
if(x==&&y==) return; //找到起点,返回上一次
print(ss[x][y].x,ss[x][y].y);
printf("%ds:(%d,%d)->(%d,%d)\n",t++,ss[x][y].x,ss[x][y].y,x,y);
if(map[x][y]>=''&&map[x][y]<='') //如果遇到怪兽,多呆几秒的输出
{
int w=map[x][y]-'';
for(int i=w; i>; i--)
printf("%ds:FIGHT AT (%d,%d)\n",t++,x,y);
}
}
int main()
{
int i,j;
while(~scanf("%d%d",&n,&m))
{
for(i=; i<n; i++)
scanf("%s",&map[i]);
memset(visit,,sizeof(visit));
BFS();
t=;
if(p==-) //到不了的特定输出
printf("God please help our poor hero.\n");
else
{
printf("It takes %d seconds to reach the target position, let me show you the way.\n",p); //输出一共需要多少秒
print(n-,m-);
}
printf("FINISH\n"); //别忘了需要输出的最后一句话
}
return ;
}
最新文章
- java 装饰者模式与继承的区别
- Java中系统属性Properties介绍 System.getProperty()参数大全
- canvas滤镜之简单的取反
- PHP输出表格的方法
- Hadoop概念学习系列之分布式数据集的容错性(二十七)
- Android四大组件之一:Activity
- Tomcat部署问题,Tomcat集群部署问题。
- IIS7 性能(内存、CPU、当前请求耗时)监测
- Android开发手记(32) 使用摄像头拍照
- 使用commons-fileupload进行上传
- JQuery实战——页面进度条效果
- vim编辑器的使用技巧
- Effective Java 之-----返回零长度的数组或集合而不是null
- 洛谷 [P2024] 食物链
- Django学习笔记(http协议与django安装)
- vue引入JQ的方法
- c++ cin cin.getline() getline()用法
- Linux 驱动——Button驱动6(mutex、NBLOCK、O_NONBLOCK)互斥信号量、阻塞、非阻塞
- MySQL Execution Plan--EXPLAIN用法
- SSM文件上传