zzuli-1726：迷宫（语文功底题。。。）

题目链接

题目描述：

在很多 RPG (Role-playing Games) 游戏中，迷宫往往是非常复杂的游戏环节。通常来说，我们在走迷宫的时候都需要花非常多的时间来尝试不同的路径。但如果有了算法和计算机的帮助，我们能不能有更快的方式来解决这个问题？我们可以进行一些尝试。
现在我们有一个 N 行 M 列的迷宫。迷宫的每个格子如果是空地则可以站人，如果是障碍则不行。在一个格子上，我们可以一步移动到它相邻的 8 个空地上，但不能离开地图的边界或者跨过两个障碍的夹缝。下图是一个移动规则的示例。

为了离开迷宫，我们还需要触发迷宫中所有的机关。迷宫里总共有 K 个机关，每个机关都落在一个不同的空地上。如果我们到达了某个机关所在的格子时，这个机关就会被自动触发，并在触发之后立即消失。我们的目标是按顺序触发所有的 K 个机关，而当最后一个机关被触发时，我们就可以离开迷宫了。
现在我们已经拿到了迷宫地图，并且知道所有障碍、机关的位置。初始时我们位于迷宫的某个非障碍格子上，请你计算我们最少需要移动多少步才能离开迷宫？

输入：

输入的第一行是测试数据的组数 T (T ≤ 20)。
对于每组测试数据：第一行包含地图的行数 N (2 ≤ N ≤ 100)，列数 M(2 ≤ M ≤ 100) 和机关的数量 K(1 ≤ K ≤10)。接下来 N 行，每行包含 M 个字符，其中字符 ‘#’ 表示障碍，而 ‘.’ 表示空地。接下来一行描述了我们的初始位置 (x, y)，表示我们一开始在第 x 行第 y 列的格子上。这个格子保证是个空地。接下来 K 行，每行给出了一个机关的位置。所有的机关都不会出现在障碍上，并且任意两个机关不会出现在同一个空地上。我们需要按输入给定的顺序触发所有的 K 个机关。

输出：

对于每组测试数据，输出离开迷宫所需要的最少步数。如果无论如何都不能离开迷宫，输出 -1。

样例输入：

3
3 3 2
…
…
…
1 1
1 3
2 2
3 3 1
…
.#.
…
1 1
3 3
2 3 1
..#
.#.
1 1
2 3

样例输出

3
3
-1

思路：

• 因为要按顺序触发所有机关才能出去，所以没有轮到的机关，不能走那一格（题目中说：自动触发，立即消失）
• 虽然起点不会是障碍，但是可能是机关。如果是机关1就继续搜索，如果是其他机关就注定走不出迷宫。

ac代码：

#include<iostream> #include<string.h> #include<queue> #include<cmath> #define N 105 using namespace std; int n, m, k; char g[N][N]; struct ac{int x, y, step; }a[N]; int now_x, now_y; int vis[N][N]; int dx[8]={0, 0, -1, 1, -1, -1, 1, 1}; int dy[8]={1, -1, 0, 0, 1, -1, 1, -1}; int bfs(char target){queue<ac> que;que.push((ac) {now_x, now_y, 0});memset(vis, 0, sizeof(vis));vis[now_x][now_y] = 1;while(!que.empty()) {ac t;t = que.front();que.pop();for(int i = 0; i < 8; i++) {int xx = t.x + dx[i];int yy = t.y + dy[i];if(!vis[xx][yy] && xx >= 1 && xx <= n && yy >= 1 && yy <=m && (g[xx][yy] == '.' || g[xx][yy] == target)) { //判断下一个点是否越界，合理 if(abs(dx[i]) + abs(dy[i]) == 2 && g[xx][t.y] == '#' && g[t.x][yy] == '#') { //判断夹缝 continue;}if(g[xx][yy] == target) { //找到机关now_x = xx, now_y =yy; //更新当前点 g[xx][yy] = '.'; //触发过的机关变成陆地 return t.step + 1; //返回步数 }else{que.push((ac){xx, yy, t.step + 1});vis[xx][yy] = 1;}}} }return -1; //找不到目标，返回 -1 } int main (){ios::sync_with_stdio(false);cin.tie(0);int t;cin >> t;while(t--){cin >> n >> m >> k;for(int i = 1; i <= n; i++) {for(int j = 1; j <= m; j++){cin >> g[i][j];} } cin >> now_x >> now_y; //现在的位置 for(int i = 1; i <= k; i++) {int x, y;cin >> x >> y;g[x][y] = i + '0'; //将机关标记在地图上 } int ans = 0;for(int i = 1; i <= k; i++) {if(i == 1 && g[now_x][now_y] != '.'){ //如果起点是机关，分两种情况 if(g[now_x][now_y] == '1'){ //起点为第一个机关，则直接触发，并继续搜索 g[now_x][now_y] = '.';continue;}else{ //起点是其他机关，则不可能按顺序触发所有机关 ans = -1; //直接退出 break;}} int tt = bfs(i + '0');if(tt == -1){ //找不到机关就退出 ans = -1;break;}ans += tt;} cout << ans << endl; } return 0; }

总结

以上是生活随笔为你收集整理的zzuli-1726：迷宫（语文功底题。。。）的全部内容，希望文章能够帮你解决所遇到的问题。

如果觉得生活随笔网站内容还不错，欢迎将生活随笔推荐给好友。