2020安徽省大学生程序设计大赛题解——J 飞奔的战士_ccpc大学生程序设计题目安徽省java解题

2020安徽省大学生程序设计大赛题解——J 飞奔的战士

J 飞奔的战士

题目

众所周知，$TeutonicKnight$ 是某 $RTS$ 游戏中，移动速度最快的单位。而且他热衷于参加赛跑比赛。现在他想知道他最快需要用多长时间才可以到达终点，假设他没有开加速挂。起初，他站在第 $1$ 张图的某个位置（用$S$标识），终点在第 $k$ 张图的某个位置（用$E$标识），在除最后一张图外，每一张图上有且仅有一个传送点（用$T$标识），可以将他传送到下一张图的某个位置，用$t$标识。传送不需要任何时间，可以理解为瞬间完成。每次移动一个单位距离耗时 $1$ 秒。现在 $TeutonicKnight$ 想知道他在全程狂奔的情况下，最快需要多长时间才能到达终点。

标签

数组，队列，图的BFS，迷宫问题

分析

这道题是一道迷宫求最短路径问题。直接思路是图的$BFS$算法，设置一个$d[i][j]$的二维数组来存储从起点到坐标$(i,j)$的最短距离，但与一般的迷宫问题所不同的是该题涉及多个迷宫，依次进行$n$次$BFS$,最后将$n$次的时间累加起来。

首先从题目的条件入手，题目要求输出最快能够发现一个圣物的秒数，每秒向上下左右四个方向各移动一个单位，因此问题转化为求从起点到达其中一个圣物的最短路径问题。

用数组$charg[k][i][j];$存储用户输入的迷宫符号，表示第$k$张图的第$(i,j)$个位置，
一行一行的读入每张迷宫地图的各状态，然后从起点开始$BFS$算法。

然后是$BFS$算法：
找到从起点到终点的最短路径其实就是一个建立队列的过程：
1.从起点开始，将其加入队列，设置距离为$0$;
2.从队列首端取出位置，将从这个位置能够到达的位置加入队列，并且让这些位置的距离为上一个位置的距离加上$1$;
3.一轮探索至无法继续向队列中添加元素，即当前所在点的四周情况全部考虑完成后，循环第二步，直到将传送点$T$/终点添加到队列中。说明此时已经找到了最短路径；

完整的$BFS$代码如下：

int bfs(int p, int sx, int sy) { //从人当前开始广度优先搜索遍历
    memset(d, -1, sizeof(d));
    queue<Node> Q;
    Q.push({ sx,sy }); //放入第一个人的当前状态入队
    d[sx][sy] = 0;
    while (!Q.empty()) {
        auto t = Q.front();
        Q.pop();
        int x = t.x, y = t.y;
        int dd = d[x][y];
        for (int i = 0; i < 4; i++) {
            int nx = x + dx[i], ny = y + dy[i];
            if (!vaild(nx, ny)) continue;
            if (g[p][nx][ny] == '#') continue;
            if (g[p][nx][ny] == 'E' || g[p][nx][ny] == 'T') return dd + 1;
            if (g[p][nx][ny] == '.') {
                if (d[nx][ny] != -1) continue;
                d[nx][ny] = dd + 1;
                Q.push({ nx,ny });
            }
        }
    }
    return -1;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

最后，将每张地图搜索到的$BFS$路径相加，即为总的最短路径
（若有一张图走不通就输出$"TrappedMaze!!!"$）

参考答案（C++）

#include<bits/stdc++.h>
using namespace std;
const int N = 30;
const int dx[] = { 1,-1,0,0 }, dy[] = { 0,0,1,-1 };                    //人行进的方向
int k, n, m;
char g[100][100][100];                                                 //迷宫
int d[100][100];                                                       //到当前状态的最小距离
bool vaild(int x, int y) { return x > 0 && x <= n && y > 0 && y <= m; }//判断是否在迷宫中
bool flag = true;
struct Node {             //记录当前的状态
    int  x, y; //x,y表示当前的位置 id表示当前是第几张图
    Node() {}
    Node(int x, int y) : x(x), y(y) {}
};

int bfs(int p, int sx, int sy) { //从人当前开始广度优先搜索遍历
    memset(d, -1, sizeof(d));
    queue<Node> Q;
    Q.push({ sx,sy }); //放入第一个人的当前状态入队
    d[sx][sy] = 0;
    while (!Q.empty()) {
        auto t = Q.front();
        Q.pop();
        int x = t.x, y = t.y;
        int dd = d[x][y];
        for (int i = 0; i < 4; i++) {
            int nx = x + dx[i], ny = y + dy[i];
            if (!vaild(nx, ny)) continue;
            if (g[p][nx][ny] == '#') continue;
            if (g[p][nx][ny] == 'E' || g[p][nx][ny] == 'T') return dd + 1;
            if (g[p][nx][ny] == '.') {
                if (d[nx][ny] != -1) continue;
                d[nx][ny] = dd + 1;
                Q.push({ nx,ny });
            }
        }
    }
    return -1;
}
int main() {
    cin >> k >> n >> m;                          //输入迷宫的个数与行列
    for (int p = 1; p <= k; p++)
        for (int i = 1; i <= n; i++)
            cin >> g[p][i] + 1;                  //输入迷宫各状态，由于数据是一行一行的给的，故
    int sx = 0, sy = 0, path = 0;
    for (int p = 1; p <= k; p++) {
        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= m; j++) {
                if (g[p][i][j] == 'S' || g[p][i][j] == 't') {
                    sx = i, sy = j;    //标记人
                    int ans = bfs(p, sx, sy);
                    if (ans == -1) {
                        flag = false;
                        cout << "Trapped Maze!!!";
                    }
                    else path += ans;
                }
            }
        }
    }
    if(flag)
        cout << path << endl;
    return 0;
}
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