输出迷宫路径
题目：http://acm.hdu.先说下题意，给个图，'.'代表可走，'X'代表墙，数字(1-9)代表怪物，只能上下左右走。从一个'.'走到另一个'.'花费1秒，如果当前所在处有n只怪物，需要停留n秒来消灭怪物。求从图的左上点走到右下点花费的最小时间以及其路线。
莫名奇妙的Runtime Error
CODE:
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
int dx[4]={-1,0,1,0};
int dy[4]={0,1,0,-1};
int visit[200][200];
int father[200][200][2];
int min=999999;
int judge(int x,int y,int n,int m,char map[200][200])
{
if(x>=0&&x<n&&y>=0&&y<m&&map[x][y]!='X')
return 1;
return 0;
}
void print(int x,int y,int step,char map[200][200])
{
if(x==0&&y==0)
return ;
if(map[x][y]>='1'&&map[x][y]<='9')
{
map[x][y]--;
print(x,y,step-1,map);
printf("%ds:FIGHT AT (%d,%d)\n",step,x,y);
}
else
{
print(father[x][y][0],father[x][y][1],step-1,map);
printf("%ds:(%d,%d) -> (%d,%d)\n",step,father[x][y][0],father[x][y][1],x,y);
}
}
void bfs(char map[200][200],int n,int m,int startx,int starty,int endx,int endy)
{
int head=0,tail=1;
int i,x,y,step,xx,yy;
int queue[40000][3];
memset(queue,0,sizeof(queue));
queue[0][0]=startx;
queue[0][1]=starty;
queue[0][2]=0;
visit[startx][starty]=0;
while(head<tail)
{
x=queue[head][0];
y=queue[head][1];
step=queue[head][2];
if(x==endx&&y==endy)
{
if(step<min)
min=step;
}
head++;
//printf("%d %d %d\n",x+1,y+1,step);
for(i=0;i<4;i++)
{
xx=x+dx[i];
yy=y+dy[i];
if(judge(xx,yy,n,m,map)==1&&step<visit[xx][yy])
{
if(map[xx][yy]>='1'&&map[xx][yy]<='9')
{
queue[tail][0]=xx;
queue[tail][1]=yy;
queue[tail][2]=step+map[xx][yy]-'0'+1;
father[xx][yy][0]=x;
father[xx][yy][1]=y;
visit[xx][yy]=step+map[xx][yy]-'0'+1;
tail++;
}
else
{
queue[tail][0]=xx;
queue[tail][1]=yy;
queue[tail][2]=step+1;
father[xx][yy][0]=x;
father[xx][yy][1]=y;
visit[xx][yy]=step+1;
tail++;
}
}
}
}
}
int main()
{
char map[200][200];
int i,j,startx,starty,endx,endy,n,m;
while(scanf("%d %d",&n,&m)!=EOF)
{
min=999999;
memset(map,0,sizeof(map));
memset(father,0,sizeof(father));
for(i=0;i<n;i++)
for(j=0;j<m;j++)
visit[i][j]=999999;
for(i=0;i<n;i++)
{
scanf("\n");
for(j=0;j<m;j++)
scanf("%c",&map[i][j]);
}
startx=0,starty=0;
endx=n-1,endy=m-1;
bfs(map,n,m,startx,starty,endx,endy);
if(min==999999)
{
printf("God please help our poor hero.\n");
printf("FINISH\n");
}
else
{
printf("It takes %d seconds to reach the target position, let me show you the way.\n",min);
print(n-1,m-1,min,map);
printf("FINISH\n");
}
}
//system("pause");
return 0;
}
[ 本帖最后由 sunyh1999 于 2011-6-18 16:22 编辑 ]
