link:http://acm.hdu.edu.cn/showproblem.php?pid=1026

偶然做到这道题,发现是一个很好的搜索练习题,它不像以前那种广搜题,只让求出
最小值,这题在求出最小值的同时还必须输出其走的路劲,也就说要在搜索的同时进行记录。
题意很明确,从起点出发到终点所需的最短时间,'.'表能通过,'X'表示不能通过,'数字'
表示正在fight,其实这题难得就是如何去记录上一个路劲,我们可以利用结构体,在搜寻下一个
的同时,记录上一个的坐标即可~~有意者可以做一下~~~
下面是我的代码,仅供参考;
code:
#include <cstdio>
#include <cstring>
#include <queue>
#define INF 0x7f7f7f7f
using namespace std;
struct road
{
    char c;
    int x;
    int y;
    int prex;
    int prey;
    int step;
} path[101][101],t,p;
int n,m;
int x[]= {-1,0,1,0};
int y[]= {0,-1,0,1};
void output()
{
    int cas=1,x=0,y=0,i;
    if(path[0][0].step==INF)
    {
        printf("God please help our poor hero.\n");
        printf("FINISH\n");
        return;
    }
    printf("It takes %d seconds to reach the target position, let me show you the way.\n",path[0][0].step);
    while(x!=n-1||y!=m-1)
    {
        int xx=path[x][y].prex;
        int yy=path[x][y].prey;
        if(path[x][y].c>='1'&&path[x][y].c<='9')
        {
            for(i=0; i<path[x][y].c-'0'; i++)
                printf("%ds:FIGHT AT (%d,%d)\n",cas++,x,y);
        }
        printf("%ds:(%d,%d)->(%d,%d)\n",cas++,x,y,xx,yy);
        x=xx,y=yy;
    }
    if(path[x][y].c>='1'&&path[x][y].c<='9')
    {
        for(i=0; i<path[x][y].c-'0'; i++)
            printf("%ds:FIGHT AT (%d,%d)\n",cas++,x,y);
    }
    printf("FINISH\n");
}
void bfs()
{
    int i;
    queue<road>q;
    path[n-1][m-1].step=0;
    if(path[n-1][m-1].c>='1'&&path[n-1][m-1].c<='9')
        path[n-1][m-1].step=path[n-1][m-1].c-'0';
    q.push(path[n-1][m-1]);
    while(!q.empty())
    {
        t=q.front();
        q.pop();
        for(i=0;i<4;i++)
        {
            p.x=t.x+x[i];
            p.y=t.y+y[i];
            if(p.x>=0&&p.x<n&&p.y>=0&&p.y<m&&path[p.x][p.y].c!='X')
            {
                if(path[p.x][p.y].c>='1'&&path[p.x][p.y].c<='9')
                    p.step=t.step+path[p.x][p.y].c-'0'+1;
                else
                    p.step=t.step+1;
                if(p.step<path[p.x][p.y].step)
                {
                    p.prex=t.x;
                    p.prey=t.y;
                    path[p.x][p.y].prex=t.x;
                    path[p.x][p.y].prey=t.y;
                    path[p.x][p.y].step=p.step;
                    q.push(p);
                }
            }
        }
    }
    output();
}
int main()
{
    int i,j;
    while(scanf("%d%d",&n,&m)!=EOF)
    {
        for(i=0; i<n; i++)
        {
            getchar();
            for(j=0; j<m; j++)
            {
                scanf("%c",&path[i][j].c);
                path[i][j].x=i;
                path[i][j].y=j;
                path[i][j].step=INF;
            }
        }
        if(path[0][0].c=='X')
        {
            printf("God please help our poor hero.\n");
            printf("FINISH\n");
            continue;
        }
        bfs();
    }
    return 0;
} 

发表评论

电子邮件地址不会被公开。

Post Navigation