Ignatius and the Princess I

5 6
.XX.1.
..X.2.
2...X.
...XX.
XXXXX.
5 6
.XX.1.
..X.2.
2...X.
...XX.
XXXXX1
5 6
.XX...
..XX1.
2...X.
...XX.
XXXXX.

It takes 13 seconds to reach the target position, let me show you the way.
1s:(0,0)->(1,0)
2s:(1,0)->(1,1)
3s:(1,1)->(2,1)
4s:(2,1)->(2,2)
5s:(2,2)->(2,3)
6s:(2,3)->(1,3)
7s:(1,3)->(1,4)
8s:FIGHT AT (1,4)
9s:FIGHT AT (1,4)
10s:(1,4)->(1,5)
11s:(1,5)->(2,5)
12s:(2,5)->(3,5)
13s:(3,5)->(4,5)
FINISH
It takes 14 seconds to reach the target position, let me show you the way.
1s:(0,0)->(1,0)
2s:(1,0)->(1,1)
3s:(1,1)->(2,1)
4s:(2,1)->(2,2)
5s:(2,2)->(2,3)
6s:(2,3)->(1,3)
7s:(1,3)->(1,4)
8s:FIGHT AT (1,4)
9s:FIGHT AT (1,4)
10s:(1,4)->(1,5)
11s:(1,5)->(2,5)
12s:(2,5)->(3,5)
13s:(3,5)->(4,5)
14s:FIGHT AT (4,5)
FINISH
God please help our poor hero.
FINISH

题目大意：

给定1张图，走到“.”需要1步，走到数字除了需要1步，还要停留数字上那么多步，“#”不能走，问你从左上角到右下至少走多少步，并输出路径

简单的BFS，再加上记录前1步可以从终点往前来获得路径。

#include <iostream>
#include <cstdio>
#include <queue>
#include <cstring>
using namespace std;

struct node{
    int x,y,step;
    node(int x0=0,int y0=0,int step0=0){
        x=x0;y=y0;step=step0;
    }
};

const int offx[]={1,-1,0,0};
const int offy[]={0,0,-1,1};
int n,m,step[110][110],pre[110][110];
char a[110][110];

void solve(){
    memset(step,-1,sizeof(step));
    memset(pre,-1,sizeof(pre));
    queue <node> q;
    q.push(node(0,0,0));
    step[0][0]=0;
    while(!q.empty()){
        node s=q.front();
        q.pop();
        for(int i=0;i<4;i++){
            int dx=s.x+offx[i],dy=s.y+offy[i],newstep;
            if(dx<0 || dx>=n || dy<0 || dy>=m) continue;
            if(a[dx][dy]=='X') continue;
            if(a[dx][dy]=='.') newstep=s.step+1;
            else newstep=s.step+1+a[dx][dy]-'0';
            if(newstep<step[dx][dy] || step[dx][dy]==-1){
                step[dx][dy]=newstep;
                pre[dx][dy]=i;
                q.push(node(dx,dy,step[dx][dy]));
            }
        }
    }
}

void dfs(int dx,int dy){
    if(pre[dx][dy]==-1) return;
    int sx=dx-offx[pre[dx][dy]],sy=dy-offy[pre[dx][dy]];
    dfs(sx,sy);
    printf("%ds:(%d,%d)->(%d,%d)\n",step[sx][sy]+1,sx,sy,dx,dy);
    if(a[dx][dy]!='.'){
        for(int i=1;i<=a[dx][dy]-'0';i++){
            printf("%ds:FIGHT AT (%d,%d)\n",step[sx][sy]+1+i,dx,dy);
        }
    }
}

void output(){
    if(step[n-1][m-1]==-1){
        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",step[n-1][m-1]);
        dfs(n-1,m-1);
    }
    printf("FINISH\n");
}

int main(){
    while(scanf("%d%d",&n,&m)!=EOF){
        for(int i=0;i<n;i++) scanf("%s",a[i]);
        solve();
        output();
    }
    return 0;
}

HDU 1026 Ignatius and the Princess I （基本算法-BFS）,布布扣,bubuko.com

HDU 1026 Ignatius and the Princess I （基本算法-BFS）

原文：http://blog.csdn.net/a1061747415/article/details/38276655