http://acm.hdu.edu.cn/showproblem.php?pid=1026
题目不难，属于基本的广度优先搜索题。只是需要输出路径，比较麻烦。深度优先搜索的路径可以直接写出来，而广度优先搜索的路径需要用一个表来保存，这里借鉴了别人写的程序。具体内容已经在注释里写的很清楚了。
/*******************************************\
HDOJ 1026 Ignatius and the Princess I
寻找迷宫最短路径，记忆化广度优先搜索
author: Sail
\*******************************************/
#include <iostream>
#include <queue>
#include <memory.h>
using namespace std;
char maze[101][101]; //迷宫
bool visited[101][101]; //访问标记
int n,m;
int stepx[4] = {0, 1, 0, -1}; //left down right up
int stepy[4] = {-1, 0, 1, 0}; //左 下 右 上 搜索下一节点步长
int depth;//走过路径长度，即到达终点的时间
struct point
{
int x;
int y;
int hp;
int step;
};
point path[102][102]; //用来保存路径，path[x][y] 中保存的是上一个到达此点的节点
queue<point> q; //广搜队列
bool isBound(point p)
{
if (p.x<0 || p.y<0 || p.x>=n || p.y>=m)
{
return false;
}
return true;
}
//参考别人写的，保存路径，path[x][y] 中保存的是上一个到达此点的节点
void outputPath(int x, int y, int hp)
{
if(path[x][y].x + path[x][y].y != 0) //从（0,0）开始输出
outputPath(path[x][y].x,path[x][y].y,path[x][y].hp);
int px = path[x][y].x;
int py = path[x][y].y;
cout << depth++ << "s:(" << px << "," << py << ")->(" << x << "," << y << ")" << endl;
for(int i=1 ; i<=hp; ++i)
cout << depth++ << "s:FIGHT AT ("<< x << "," << y << ")" << endl;
}
///广度优先搜索，查找最佳路径。这里这样处理：由于怪物的存在，破坏了广度优先搜索的结构，因此每次经过怪物时，将hp-1，再将值赋给
///这一点，并将此点入队列，并不直接进行扩展，直到hp减为0后，将这一点设置为'.'即一般路径，进行扩展，这样能够保证同一层次找到的
///第一个解即为最优解(因为这样处理后，所有扩展的节点代价都相等都为1)
void BFS()
{
bool rescue = false;
point curr, next;
curr.x = 0;curr.y=0;curr.step=0;curr.hp=0; //初始化起始位置
q.push(curr);
visited[0][0]=true;
while(!q.empty())
{
curr = q.front();
q.pop();
if(curr.x == n-1 && curr.y == m-1 && maze[curr.x][curr.y]=='.') //找到出口，则输出结果
{
rescue = true;
cout << "It takes " << curr.step << " seconds to reach the target position, let me show you the way." << endl;
//输出路径
depth = 1;
outputPath(curr.x,curr.y,curr.hp);
}
//若碰到怪兽，则将其hp-1并赋给这个点，不进行扩展直接入队列
if(maze[curr.x][curr.y] >= '1' && maze[curr.x][curr.y] <= '9')
{
int tmp = maze[curr.x][curr.y] - '1';
if(tmp == 0)
maze[curr.x][curr.y] = '.';
else
maze[curr.x][curr.y] = tmp + '0';
curr.step++; //记录打怪兽时间，一滴一滴的打
q.push(curr);
}
else //普通节点，进行扩展，
{
//朝着左下右上四个方向进行扩展
for(int i=0 ; i<4 ; ++i)
{
next.x = curr.x + stepx[i];
next.y = curr.y + stepy[i];
next.step = curr.step + 1;
//如果没有访问过，且不是边界，且不是墙，则将路径保存起来
if(visited[next.x][next.y]==false && isBound(next) && maze[next.x][next.y]!='X')
{
visited[next.x][next.y] = true;
//输出路径不会，参考别人的方法保存搜索的路径
path[next.x][next.y].x = curr.x;
path[next.x][next.y].y = curr.y;
path[next.x][next.y].hp = curr.hp;
//更新路径的血量（这样处理为了通用性，将怪兽点与路径点用同样方式处理，对怪兽点的扩展按照上面if方法）
if(maze[next.x][next.y] == '.')
next.hp = 0;
else
next.hp = maze[next.x][next.y] - '0';
q.push(next);
}
}
}
}
if(!rescue) //若没有找到路径
{
cout << "God please help our poor hero." << endl;
}
}
int main()
{
while(cin >> n >> m)
{
//构造迷宫并初始化visited
for(int i=0 ; i<n ; ++i)
{
for(int j=0 ; j<m ; ++j)
{
cin >> maze[i][j];
visited[i][j] = false;
}
}
memset(path,0, sizeof(path)); //初始化path路径数组
BFS();
cout << "FINISH" << endl;
}
return 0;
}