hdu 1026 Ignatius and the Princess I BFS

题意：给定一个n*m的迷宫，起点在(0,0)，终点在(n-1,m-1)；规则如下：

1）每次移动只能上下左右方向移动一格，耗时1秒，不能到迷宫外。

2）迷宫上的各个字符意义为：

‘.’，表示可以走的路。

‘X’，表示不可以走的陷阱。

‘n’，n为数字，(1<=n<=9)，表示这个区域有一格HP值为n的怪物，需要耗时n秒时间打败，才能继续前进。

题解：

典型的BFS题目，只是加了怪物的设定以及需要输出路径。

路径用pre[i]记录前驱，由于n<=100,m<=100所以一格点(i,j)可以表示为i*100+j,最后递归输出路径即可。

而路过标志vis[i][j]，不像以前那样只是表示是否路过，因为可能绕远路的时间更短。所以vis[i][j]表示的是到达(i,j)最少需要的时间，比vis[i][j]大的路径都可以省去。

代码：

#include <iostream>
#include <cstdio>
#include <cstring>
#include <ctime>
#include <algorithm>
#include <cmath>
#include <queue>
#include <vector>
using namespace std;

const int maxn=101;
const int INF=1e8;
int pre[maxn*maxn];//记录路径
int vis[maxn][maxn];//vis[i][j]记录到(i,j)的所需要的最短时间
char e[maxn][maxn];
int ans,MinDis;
int dir[4][2]={{-1,0},{1,0},{0,-1},{0,1}};//转移方向
struct node{
    int x,y,num;
};
void show(int i)//结果输出
{
    if(pre[i]==-1)
    {
        if(e[i/100][i%100]!='.')
        {
            for(int k=0;k<e[i/100][i%100]-'0';k++)
                printf("%ds:FIGHT AT (%d,%d)\n",++ans,i/100,i%100);
        }
        return ;
    }
    show(pre[i]);
    printf("%ds:(%d,%d)->(%d,%d)\n",++ans,pre[i]/100,pre[i]%100,i/100,i%100);
    if(e[i/100][i%100]!='.')
    {
        for(int k=0;k<e[i/100][i%100]-'0';k++)
            printf("%ds:FIGHT AT (%d,%d)\n",++ans,i/100,i%100);
    }
}
void bfs(int n,int m)
{
    int i,j,k,xx,yy,num;
    node f,g;
    memset(pre,-1,sizeof(vis));
    for(i=0;i<n;i++)
        for(j=0;j<m;j++)
        vis[i][j]=INF;
    vis[0][0]=0;
    queue<node>q;
    f.x=0;f.y=0;f.num=0;
    MinDis=INF;
    q.push(f);
    while(!q.empty())
    {
        f=q.front();
        q.pop();
        if(f.x==n-1&&f.y==m-1)
        MinDis=min(MinDis,f.num);
        for(i=0;i<4;i++)
        {
            xx=f.x+dir[i][0];
            yy=f.y+dir[i][1];
            if(e[f.x][f.y]=='.')num=f.num+1;
            else num=f.num+1+(e[f.x][f.y]-'0');
            if(xx<0||yy<0||xx>=n||yy>=m||e[xx][yy]=='X')continue;
            if(num>=vis[xx][yy])continue;
            vis[xx][yy]=num;
            pre[xx*100+yy]=f.x*100+f.y;
            g.x=xx;
            g.y=yy;
            g.num=num;
            q.push(g);
        }
    }
    if(pre[(n-1)*100+m-1]==-1)printf("God please help our poor hero.\nFINISH\n");
    else
    {
        if(e[n-1][m-1]!='.')
            MinDis+=(e[n-1][m-1]-'0');
        printf("It takes %d seconds to reach the target position, let me show you the way.\n",MinDis);
        ans=0;
        show((n-1)*100+(m-1));
        printf("FINISH\n");
    }
}
int main()
{
    int n,m;
    while(scanf("%d%d",&n,&m)!=EOF)
    {
        int i,j,k;
        for(i=0;i<n;i++)
            scanf("%s",e[i]);
        if(e[0][0]=='X'||e[n-1][m-1]=='X')
        {
            printf("God please help our poor hero.\nFINISH\n");
            continue;
        }
        bfs(n,m);
    }
    return 0;
}