http://acm.sdut.edu.cn/sdutoj/problem.php?action=showproblem&problemid=2465
题目描述
由于前两次的打击，ZYJ同学不再喜欢密码学，他喜欢上了游戏。某一 天，他要玩魔塔这个游戏，游戏规则是这样的，游戏地图的大小为N*M，一开始，ZYJ处于（0，0）点，ZYJ想去（N-1,M-1）点。但是通往目标的 路上有很多妖怪，每个妖怪都会打掉ZYJ不同数量的血量。现在ZYJ希望能够耗费最少的血量到达目的地。
但是他必须遵循以下规则：
1 他只能走上下左右四个方向。
2 每一个格可能为“.”“X”或者数字，“.”表示可以走，但是由于ZYJ身体虚弱，走的时候要扣掉1点血量值，“X”表示墙壁不可以走，数字表示这个怪物（数字大于等于1小于等于9）会打掉ZYJ的血量值。
而现在你的任务就是计算怎么样才能耗费最小的血量到达目的地。（毕竟ZYJ也不容易，连着受了两次打击，千万别再让他耗费过多的血量了，祖国需要这样的栋梁啊。。。。）
输入
输入包含多组数据，每一组数据第一行都有两个整数N，M，他们表示N*M的地图，接下来就是N行，长为M的迷宫。 (2<=N<=100,2<=M<=100)，当输入的n=0，m=0的时候结束。
输出
如果无法到达目的地，就输出"GAME OVER."，如果可以找到，那么就把路径以样例的形式显示出来。输出的s代表的是耗费的血量的单位。不管能不能找到，在最后都输出一个"FINISH".
示例输入
5 6
.XX.1.
..X.2.
2...X.
...XX.
XXXXX.
0 0
示例输出
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
坑爹的题啊：
为么jx[]={0,0,1,-1},jy[]={1,-1,0,0}就A;jx[]={1,-1,0,0},jy[]={0,0,1,-1}就WA;什么后台数据??
这题是参考大神的代码，之前没思路就忍不住看了，要改啊，要努力思考，C++学的还是渣，感觉C++略难啊，不懂思想，回溯路径的思想还需加强。
#include <cstdio>
#include <cstring>
#include <iostream>
#include <queue>
using namespace std;
typedef struct node
{
int x,y,ans,num,pre;
friend bool operator<(struct node a,struct node b)//现在还不懂啊
{
return a.ans>b.ans;
}
} st;
st qq[];
int n,m;
char map[][];
int v[][],kj[];
int jx[]= {,,,-};
int jy[]= {,-,,};
int judge(int x,int y)
{
if(x>=n||y>=m||x<||y<)
return ;
if(map[x][y]=='X')
return ;
return ;
}
void bfs()
{
int flag=;
int tt=;
memset(v,,sizeof(v));
priority_queue <st> q;
st t,f;
t.x=;
t.y=;
t.ans=;
t.num=;
t.pre=;
q.push(t);
qq[tt]=t;
v[][]=;
while(!q.empty())
{
t=q.top();
q.pop();
if(t.x==n-&&t.y==m-)
{
flag=;
break;
}
for(int i=; i<; i++)
{
f.x=t.x+jx[i];
f.y=t.y+jy[i];
if(v[f.x][f.y]==&&judge(f.x,f.y))
{
if(map[f.x][f.y]=='.')
{
f.ans=t.ans+;
v[f.x][f.y]=;
tt++;
f.num=tt;
f.pre=t.num;
qq[tt]=f;
q.push(f);
}
else
{
f.ans=t.ans+map[f.x][f.y]-''+;
v[f.x][f.y]=;
tt++;
f.num=tt;
f.pre=t.num;
qq[tt]=f;
q.push(f);
}
}
}
}
if(flag==)
printf("GAME OVER.\n");
else
{
int ww=;
for(int i=t.num; i!=; i=qq[i].pre)
{
kj[ww++]=i;
}
for(int i=ww-; i>=; i--)
{
int y=kj[i];
if(map[qq[y].x][qq[y].y]=='.')
{
printf("%ds:(%d,%d)->(%d,%d)\n",qq[y].ans,qq[qq[y].pre].x,qq[qq[y].pre].y,qq[y].x,qq[y].y);
}
else
{
int nn = map[qq[y].x][qq[y].y]-'';
printf("%ds:(%d,%d)->(%d,%d)\n",qq[y].ans-nn,qq[qq[y].pre].x,qq[qq[y].pre].y,qq[y].x,qq[y].y);
for(int jj = ; jj <= nn ; jj++)
printf("%ds:FIGHT AT (%d,%d)\n",qq[y].ans-nn+jj,qq[y].x,qq[y].y);
} }
}
}
int main()
{
int i,j;
while(cin>>n>>m)
{
if(n==&&m==) break;
getchar();
for(i = ; i < n ; i++)
for(j = ; j < m ; j++)
cin>>map[i][j];
bfs();
printf("FINISH\n");
}
return ;
}