自己写的 393MS 用的是简单的广搜过的
#include<queue>
#include<iostream>
using namespace std;
#define INF 999999
int n,m;
int dir[4][2]={1,0,0,1,-1,0,0,-1};
int mark[101][101];
char map[101][101];
struct node
{
short x,y,f[500];//这如果用int定就会变成九百多毫秒
int t;
}v;
void bfsprintf()
{
int i,j,x=0,y=0;
for(i=0;i<mark[n-1][m-1];i++)
{
if(v.f[i]!=-1)
{
printf("%ds:(%d,%d)->",i+1,x,y);
x+=dir[v.f[i]][0];
y+=dir[v.f[i]][1];
printf("(%d,%d)\n",x,y);
}
else
printf("%ds:FIGHT AT (%d,%d)\n",i+1,x,y);
}
}
void bfs()
{
int i,j;
node a,b;
queue<node>q;
a.x=0;a.y=0;a.t=0;
memset(a.f,-1,sizeof(a.f));
q.push(a);
while(!q.empty())
{
b=q.front();
q.pop();
for(i=0;i<4;i++)
{
a=b;
a.x+=dir[i][0];
a.y+=dir[i][1];
if(a.x>=0&&a.x<n&&a.y>=0&&a.y<m&&map[a.x][a.y]!='X')
{
a.f[a.t]=i;
a.t++;
if(map[a.x][a.y]>='1'&&map[a.x][a.y]<='9')
a.t+=map[a.x][a.y]-'0';
if(a.x==n-1&&a.y==m-1&&mark[a.x][a.y]>a.t)v=a;
if(mark[a.x][a.y]>a.t)
{
mark[a.x][a.y]=a.t;
q.push(a);
}
}
}
}
if(mark[n-1][m-1]==INF)
printf("God please help our poor hero.\n");
else
{
printf("It takes %d seconds to reach the target position, let me show you the way.\n",mark[n-1][m-1]);
bfsprintf();
}
}
int main()
{
while(scanf("%d%d",&n,&m)!=-1)
{
int i,j;
for(i=0;i<n;i++)
{
scanf("%s",map[i]);
for(j=0;j<m;j++)
mark[i][j]=INF;
}
bfs();
printf("FINISH\n");
}
}
posted on 2010-08-17 10:20
【鈺仯爺】 阅读(182)
评论(0) 编辑 收藏 引用 所属分类:
搜索