迷宫最短路径

2025.9.11 曹立

题目内容

给定一个迷官的地图，地图是一个二维矩阵，其中0表示通道，1表示墙壁，S表示起点，E表示终点。你需要从起点S出发，通过最路径到达终点E，返回最短路径的步数，如果无法到达终点，则返回-1，迷宫中会有虫洞，用数字2表示，成对出现，你走入虫洞可以穿越到另一个虫洞出口，耗费0步

你只能上下左右移动，并且不能走出迷官的边界，也不能穿越墙壁

输入描述

第一行包含两个整数m,n（1≤m,n≤50），表示迷宫的行数和列数

接下来的m行，每行包含n个字符，表示迷宫的地图。字符为：

0：表示通道

1：表示墙壁

2：表示虫洞

S：表示起点

E：表示终点

输出描述

如果能够到达终点，输出最短路径的步数。 如果无法到达终点，输出-1。

C++实现

#include <bits/stdc++.h>
using namespace std;struct Node {int x, y, step;
};int shortestPathWithWormhole(vector<vector<char>>& maze) {int n = maze.size(), m = maze[0].size();pair<int,int> start, end;vector<pair<int,int>> wormholes;// 找起点、终点、虫洞for (int i = 0; i < n; i++) {for (int j = 0; j < m; j++) {if (maze[i][j] == 'S') start = {i, j};if (maze[i][j] == 'E') end = {i, j};if (maze[i][j] == '2') wormholes.push_back({i, j});}}// 虫洞配对映射map<pair<int,int>, pair<int,int>> wormMap;if (wormholes.size() == 2) {wormMap[wormholes[0]] = wormholes[1];wormMap[wormholes[1]] = wormholes[0];}// BFSqueue<Node> q;vector<vector<bool>> vis(n, vector<bool>(m, false));q.push({start.first, start.second, 0});vis[start.first][start.second] = true;int dx[4] = {1, -1, 0, 0};int dy[4] = {0, 0, 1, -1};while (!q.empty()) {auto cur = q.front(); q.pop();int x = cur.x, y = cur.y, step = cur.step;if (x == end.first && y == end.second) return step;// 4个方向扩展for (int k = 0; k < 4; k++) {int nx = x + dx[k], ny = y + dy[k];if (nx < 0 || nx >= n || ny < 0 || ny >= m) continue;if (maze[nx][ny] == '1') continue; // 墙壁if (!vis[nx][ny]) {vis[nx][ny] = true;q.push({nx, ny, step + 1});}}// 虫洞传送if (maze[x][y] == '2') {auto it = wormMap.find({x, y});if (it != wormMap.end()) {auto [wx, wy] = it->second;if (!vis[wx][wy]) {vis[wx][wy] = true;q.push({wx, wy, step}); // 虫洞传送耗费 0 步}}}}return -1;
}int main() {vector<vector<char>> maze = {{'S','0','1','0','0'},{'1','0','1','2','1'},{'0','0','0','0','0'},{'1','2','1','0','E'}};cout << shortestPathWithWormhole(maze) << endl;return 0;
}