题意：最短时间的深搜。
方法：优先队列+递归输出
网上参考：
#include<stdio.h>
#include<string.h>
#include<queue>
using namespace std;
struct Coordinate
{
int x,y,step;
// 优先队列
friend bool operator<(Coordinate c1,Coordinate c2)
{
return c2.step<c1.step;
}
};
// 存储路径
struct Path
{
int x,y,step;
}path[101][101];
int m,n,ans;
bool isfind; // 判断能否走到终点
int dis[4][2]={{0,1},{1,0},{0,-1},{-1,0}}; // 四个方向
char map[101][101]; // 存储地图
bool visit[101][101]; // 判断是否走过
// 判断越界、墙、是否已经经过 等问题
bool inmap(int x,int y)
{
if(x<0 || y<0 || x>=m || y>=n) return 1;
if(visit[x][y]==1 || map[x][y]=='X') return 1;
return 0;
}
// 输出
void show(int a,int b,int t)
{
if(t==1) printf("%ds:(%d,%d)->(%d,%d)\n",t,path[a][b].x,path[a][b].y,a,b);
else if(path[a][b].step==1)
{
show(path[a][b].x,path[a][b].y,t-1);
printf("%ds:(%d,%d)->(%d,%d)\n",t,path[a][b].x,path[a][b].y,a,b);
}
else
{
--path[a][b].step;
show(a,b,t-1);
printf("%ds:FIGHT AT (%d,%d)\n",t,a,b);
}
}
// BFS 广搜
void bfs(void)
{
memset(visit,0,sizeof(visit));
priority_queue <Coordinate> cd;
Coordinate p,next;
int i;
p.x=0,p.y=0,p.step=0;
visit[p.x][p.y]=1;
cd.push(p);
while(!cd.empty())
{
p=cd.top(); // 优先队列，所以这块不是cd.front()了
cd.pop();
if(p.x==m-1 && p.y==n-1)
{
ans=p.step;
isfind=1;
return;
}
for(i=0;i<4;++i)
{
next.x=p.x+dis[i][0];
next.y=p.y+dis[i][1];
if(inmap(next.x,next.y)) continue;
else if(map[next.x][next.y]=='.')
{
// 记录之前该点之前的点
path[next.x][next.y].x=p.x;
path[next.x][next.y].y=p.y;
path[next.x][next.y].step=1;
next.step=p.step+1;
visit[next.x][next.y]=1;
cd.push(next);
}
else
{
// 记录之前该点之前的点
path[next.x][next.y].x=p.x;
path[next.x][next.y].y=p.y;
path[next.x][next.y].step=map[next.x][next.y]-'0'+1;
next.step=p.step+map[next.x][next.y]-'0'+1;
visit[next.x][next.y]=1;
cd.push(next);
}
}
}
}
int main()
{
int i,j;
while(scanf("%d%d",&m,&n)!=EOF)
{
isfind=0;
for(i=0;i<m;++i)
scanf("%s",&map[i]);
bfs();
if(!isfind)
printf("God please help our poor hero.\nFINISH\n");
else
{
printf("It takes %d seconds to reach the target position, let me show you the way.\n",ans);
show(m-1,n-1,ans);
printf("FINISH\n");
}
}
return 0;
}
java超时
import java.util.Comparator;
import java.util.Queue;
import java.util.Scanner;
import java.util.PriorityQueue;
public class Main {
/*
* n表示行
* m表示列
* nodes，记录每一个结点
* Node用来保存地图数据与其他变量的
* isFind判断英雄是否可以到达目的地
* dir记录四个方向,分别为上下左右，
* 这个初学者是会搞错的。
* --{a,b}，a表示行,b表示列
*/
static int n = 0;
static int m = 0;
static Node[][] nodes = new Node[101][101];
static boolean isFind;
static int dir[][] = { { -1, 0 }, { 1, 0 }, { 0, -1 }, { 0, 1 } };
/*
* java是极其耗内存的，
* 所以我只用101*101个对象
*/
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
for (int i = 0; i < nodes.length; i++) {
for (int j = 0; j < nodes[0].length; j++) {
nodes[i][j] = new Node();
}
}
while (sc.hasNext()) {
n = sc.nextInt();
m = sc.nextInt();
for (int i = 0; i < n; i++) {
String str = sc.next();
for (int j = 0; j < m; j++) {
/*
* 每次都初始化数据
* 每个结点初始化步数为-1，
* 因为要是第一个结点往下步行动，
* 那么他的邻接点要小于他的步数，
* 也就是时间。
*/
nodes[i][j].set(i, j, str.charAt(j), Integer.MAX_VALUE,
null);
}
}
/*
* isFind初始认为英雄不能到达目的地
*/
isFind = false;
breadthFirstSearch();
if (isFind) {
System.out
.println("It takes "
+ nodes[n - 1][m - 1].time
+ " seconds to reach the target position, let me show you the way.");
printAnswer(nodes[n - 1][m - 1]);
} else {
System.out.println("God please help our poor hero.");
}
System.out.println("FINISH");
}
}
/*
* 这道题，答案的输出其实要用到树的知识，
* 因为我纪录的一条最短路，只要从根节点找到父节点，
* 就可以输出答案了。
* 这个要逆序输出，
* 那么就用递归输出把！
*/
private static void printAnswer(Node nod) {
/*
* 1）鸿沟
* 2）递归
* 3）回退
*/
if (nod.parent == null) {
return;
}
printAnswer(nod.parent);
if (nod.time - nod.parent.time == 1) {
System.out.println(nod.time + "s:(" + nod.parent.x + ","
+ nod.parent.y + ")->(" + nod.x + "," + nod.y + ")");
} else {
System.out.println(nod.parent.time + 1 + "s:(" + nod.parent.x + ","
+ nod.parent.y + ")->(" + nod.x + "," + nod.y + ")");
for (int i = nod.parent.time + 2; i <= nod.time; i++) {
System.out.println(i + "s:FIGHT AT (" + nod.x + "," + nod.y
+ ")");
}
}
}
/*
* breadthFirstSearch-广度优先搜索
* 这题使用优先队列+广度优先搜索做
*/
private static void breadthFirstSearch() {
/*
* 入口是搜索源，
* 起点的初始时间为0。
* 这里只要引用就行，不要深拷贝
* PriorityQueue-优先队列，节约内存
* 把搜索源加入队列
*/
nodes[0][0].time = 0;
Queue<Node> priQue = new PriorityQueue<Node>(100, new MyComparator());
priQue.add(nodes[0][0]);
while (!priQue.isEmpty()) {
/*
* 优先弹出最小的time值的结点
* 这个队列是自己写的，感觉用的比较爽。
* 搜索四个方向，
* 剪枝。
*/
Node no = priQue.poll();
int i = no.x;
int j = no.y;
/*
* 到达出口,就需要回退，
* 只要所有的元素都出队列了，
* 那么就可以把最短路径纪录了。
*/
if (i == n - 1 && j == m - 1) {
/*
* 纪录时间，每一次进入这条语句，
* 都表明时间更快，不可能慢，或则快。
* 如果进不来就表明无法到达终点。
*/
isFind = true;
return;
}
for (int k = 0; k < 4; k++) {
i = no.x + dir[k][0];
j = no.y + dir[k][1];
// 越界
if (i < 0 || j < 0 || i >= n || j >= m) {
continue;
}
// 碰到障碍
if (nodes[i][j].ch == 'X') {
continue;
}
/*
* 这题是可以重复落脚的。
* 重要剪枝，
* 如果下次落脚点的时间小于原先的，
* 就可以落脚。
* 如果大于等于，那么就不可以落脚，
* 初始化时应该把值赋值为最大的数。
*/
if (nodes[i][j].time <= no.time) {
continue;
}
/*
* 搜索到可行的结点，
* 复制时间，且加1，
* 纪录父节点，
* 并且该节点被标记为，已被访问。
* 把搜索到的结点加入队列。
*/
// 遇到小怪
nodes[i][j].time = no.time + 1;
if (nodes[i][j].ch <= '9' && nodes[i][j].ch >= '1') {
nodes[i][j].time += (int) (nodes[i][j].ch - '0');
}
nodes[i][j].parent = no;
priQue.add(nodes[i][j]);
}
}
}
}
class Node {
int x;
int y;
char ch;
int time;
Node parent;
public Node() {
}
public void set(int x, int y, char ch, int time, Node parent) {
this.x = x;
this.y = y;
this.ch = ch;
this.time = time;
this.parent = parent;
}
}
class MyComparator implements Comparator<Node> {
public int compare(Node n1, Node n2) {
if (n1.time > n2.time) {
return 1;
} else if (n1.time < n2.time) {
return -1;
} else {
return 0;
}
}
}
Ignatius and the Princess I
伊格内修斯和公主1
Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 65536/32768 K (Java/Others)Total Submission(s): 14498 Accepted Submission(s): 4586
Special Judge
Problem Description
The Princess has been abducted by the BEelzebub feng5166, our hero Ignatius has to rescue our pretty Princess.
公主被恶魔冯5166诱拐了，我们的英雄Igntius必须去解救这位可爱的公主。
Now he gets into feng5166's castle. The castle is a large labyrinth.
现在他已经进入了冯5166的城堡。这个城堡是一个巨大的迷宫。
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).
为了使问题变得简单，我们可以假设迷宫是由N*M大小的二维数组组成，左上角是（0，0），右下角是（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.
Ignatius从（0，0）进入，feng5166的房间在(N-1，M-1)，他的房间就是目标。
There are some monsters in the castle, if Ignatius meet them, he has to kill them.
在这个城堡中有许多的怪物，如果Ignatius遇到这些怪物，那么他必须解决这些怪物。
Here is some rules:
你懂得，英雄都是这样的。
1.Ignatius can only move in four directions(up, down, left, right), one step per second.
1.Ignatius can only move in four directions(up, down, left, right), one step per second.
Ignatius只能一秒移动一步，且只能在（上，下，左，右）四个方向移动。
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).
移动定义如下：如果目前的位置是（x,y)，那么下步可以是(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:
2.The array is marked with some characters and numbers. We define them like this:
数组被字符和号码表示。我们的定义如下。
. : The place where Ignatius can walk on.
. : The place where Ignatius can walk on.
“。”表示什么都没有，Ignatius 可以安全的行走；
X : The place is a trap, Ignatius should not walk on it.
X : The place is a trap, Ignatius should not walk on it.
“X"表示一个陷阱，Ignatius应该绕开他；
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.
"n"表示怪物的生命值，
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.
"n"表示怪物的生命值，
如果Ignatius要从这里走过，那么他需要n秒才可以杀死他。
Your task is to give out the path which costs minimum seconds for Ignatius to reach target position.
你的任务是输出最短时间路径。
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.
每一个测试事件的起始行包含两个数字n和m(2<=N<=100,2<=M<=100)，表明迷宫的大小。
Then a N*M two-dimensional array follows, which describe the whole labyrinth.
然后输入n行m列的数据，表示整个迷宫。
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,
对于每一个测试事件，如果Ignatius不能到达目标地点，那么输出"God please help our poor hero." （上帝！请帮组可怜的伊格内修斯吧！）
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.
每一个测试事件由"FINISH"字符串表示结束。
If there are more than one path, any one is OK in this problem.
如果路径超过多条，请你放心，每一条语句都是没问题的。
More details in the Sample Output.
更多的细节请看下面的案例。
Sample Input
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.
Sample Output
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
Author
Ignatius.L