hdu 1026 广搜

【鈺仯爺】 — Tue, 17 Aug 2010 02:20:00 GMT

自己写的 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");
    }
}

【鈺仯爺】 2010-08-17 10:20 发表评论

C++博客-【鈺仯爺】的 ACM博客

hdu 1026 广搜