By

文章目录
  1. 1. 题意
  2. 2. 分析

原题

题意

一个棋盘可以走十字，棋盘为‘X’不能走，为‘.’可以走，为数字n则需要多花ns打败怪兽才能走。问从左上到右下的最短时间。

分析

一个傻逼的BFS写了一天！！！然后一怒之下重写了一遍，然后就ac了。。。MDZZ
主要还是之前那个的结构体之类的设置的太复杂了唉。。。而且这次就深刻理解了dijkstra就是BFS嘛。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
#include <bits/stdc++.h>
#define INF 0x3f3f3f3f
using namespace std;
typedef struct node{
    int x,y,prex,prey;
    char val;
    int time;
    bool operator < (const node& b)const{
        return time>b.time;
    }
}knight;
knight peo[107][107],now,nn;
string a[107];
int mov[4][2]={-1,0,1,0,0,-1,0,1};
int p,n,m,num;
void bfs(){
    priority_queue<knight>q;
    peo[0][0].time=0;
    q.push(peo[0][0]);
    while(!q.empty()){
        now=q.top();
        q.pop();
        if(now.x==n-1&&now.y==m-1){
            p=1;
            break;
        }
        for(int i=0;i<4;i++){
            nn.x=now.x+mov[i][0];
            nn.y=now.y+mov[i][1];
            if(nn.x>=0&&nn.x<n&&nn.y>=0&&nn.y<m&&a[nn.x][nn.y]=='.'){
                if(peo[nn.x][nn.y].time>peo[now.x][now.y].time+1){
                    peo[nn.x][nn.y].time=peo[now.x][now.y].time+1;
                    //cout<<peo[nn.x][nn.y].time<<endl;
                    peo[nn.x][nn.y].prex=now.x;
                    peo[nn.x][nn.y].prey=now.y;
                    q.push(peo[nn.x][nn.y]);
                }
            }
            else if(nn.x>=0&&nn.x<n&&nn.y>=0&&nn.y<m&&a[nn.x][nn.y]>='1'&&a[nn.x][nn.y]<='9'){
                if(peo[nn.x][nn.y].time>peo[now.x][now.y].time+a[nn.x][nn.y]-'0'+1){
                    peo[nn.x][nn.y].time=peo[now.x][now.y].time+a[nn.x][nn.y]-'0'+1;
                    //cout<<peo[nn.x][nn.y].time<<endl;
                    peo[nn.x][nn.y].prex=now.x;
                    peo[nn.x][nn.y].prey=now.y;
                    q.push(peo[nn.x][nn.y]);
                }
            }
        }
    }
}
void dfs(int i,int j){
    if(i==0&&j==0){
        return;
    }
    dfs(peo[i][j].prex,peo[i][j].prey);
    if(a[i][j]=='.'){
        printf("%ds:(%d,%d)->(%d,%d)\n",peo[i][j].time,peo[i][j].prex,peo[i][j].prey,i,j);
    }
    else if(a[i][j]>='1'&&a[i][j]<='9'){
        num=a[i][j]-'0';
        printf("%ds:(%d,%d)->(%d,%d)\n",peo[i][j].time-num,peo[i][j].prex,peo[i][j].prey,i,j);
        while(--num>=0){
            printf("%ds:FIGHT AT (%d,%d)\n",peo[i][j].time-num,i,j);
        }
    }
}
int main()
{
    while(scanf("%d%d",&n,&m)!=EOF){
        p=0;
        for(int i=0;i<n;i++){
            cin>>a[i];
        }
        for(int i=0;i<n;i++){
            for(int j=0;j<m;j++){
                peo[i][j].x=peo[i][j].prex=i;
                peo[i][j].y=peo[i][j].prey=j;
                peo[i][j].val=a[i][j];
                peo[i][j].time=INF;
            }
        }
        bfs();
        if(p==1){
            printf("It takes %d seconds to reach the target position, let me show you the way.\n",peo[n-1][m-1].time);
            dfs(n-1,m-1);
            printf("FINISH\n");
        }
        else{
            printf("God please help our poor hero.\n");
            printf("FINISH\n");
        }
    }
}
文章目录
  1. 1. 题意
  2. 2. 分析