hdu 1026 测试数据都过了，自已测也没错，可就WA
求指教~~~~~~~~~
/*1026 Ignatius and the Princess I*/
#include<stdio.h>
#include<string.h>
#include<stdlib.h>
typedef struct {
int x;
int y;
int ntime;
int s;
}elem;
int n,m;
elem d[1000000];
char str[110][110];
bool mark[110][110];
int direc[4][2]={{1,0},{0,1},{-1,0},{0,-1}};
int min;
int count;
bool prin1(int k)
{
int p;
int i;
p=d[k].s;
if(p==-1){
printf("It takes %d seconds to reach the target position, let me show you the way.\n",d[min].ntime-1);
return true;
}
prin1(p);
printf("%ds:(%d,%d)->(%d,%d)\n",d[p].ntime,d[p].x,d[p].y,d[k].x,d[k].y);
if(str[d[k].x][d[k].y]!='.'){
for(i=d[p].ntime+1;i<d[k].ntime;i++){
printf("%ds:FIGHT AT (%d,%d)\n",i,d[k].x,d[k].y);
}
}
if(k==min) printf("FINISH\n");
}
void prin2()
{
printf("God please help our poor hero.\nFINISH\n");
}
int cmp(const void *a,const void *b)
{
return (*(elem *)a).ntime-(*(elem *)b).ntime;
}
bool bfs()
{
int head,rear;
int i;
int flag;
elem now;
head=0;rear=1;
now.x=0; now.y=0; now.ntime=1; now.s=-1;
d[head]=now;
mark[now.x][now.y]=false;
while(head<rear){
flag=rear;
for(i=0;i<4;i++){
now.x=d[head].x+direc[i][0];
now.y=d[head].y+direc[i][1];
now.ntime=d[head].ntime;
now.s=head;
now.ntime++;
if(now.x>=0 && now.x<n && now.y>=0 && now.x<m && mark[now.x][now.y]){
if(str[now.x][now.y]=='X') continue;
if(now.x==n - 1 && now.y==m-1){
if(str[now.x][now.y]!='.'){
now.ntime+=str[now.x][now.y]-'0';
}
d[rear]=now;
min=rear; return true;
}
if(str[now.x][now.y]=='.'){
mark[now.x][now.y]=false;
d[rear]=now;
rear++;
}
else {
mark[now.x][now.y]=false;
now.ntime+=str[now.x][now.y]-'0';
d[rear]=now;
rear++;
}
}
}
qsort(&d[flag],rear-flag,sizeof(elem),cmp);
head++;
}
return false;
}
int main()
{
int i,j;
while(scanf("%d %d",&n,&m)==2){
getchar();
for(i=0;i<n;i++){
for(j=0;j<m;j++){
scanf("%c",&str[i][j]);
mark[i][j]=true;
}
getchar();
}
if(bfs()){
prin1(min);
}
else prin2();
}
return 0;
}
