核心思路

使用 广度优先搜索（BFS） 求解迷宫最短路径问题。BFS 自然保证第一次到达某状态时即为最短步数。

1. 预处理 扫描整个地图，记录：

   • 起点 $S$ 的坐标；
   • 终点 $E$ 的坐标（可选，仅用于判断何时结束）；
   • 所有虫洞 '2' 的坐标，按出现顺序两两配对，建立映射表 teleport，使得每个虫洞能瞬时传送至其配对位置。

2. BFS 初始化

   • 构造队列 q，存放 (x,y,steps) 三元组；
   • 构造访问标记 vis[m][n]，标记哪些格子已访问；
   • 从起点入队，steps=0，并标记其为已访问。

3. BFS 过程

   • 当队列非空时，弹出 (x,y,dist)；
   • 若当前是终点，直接返回 dist；
   • 遍历四个方向的新坐标 (nx,ny)，若在边界内、未被访问、且不是墙壁，则入队 (nx,ny,dist+1)，并标记访问；
   • 若当前格子是虫洞 '2'，且其配对位置 (tx,ty) 未被访问，则将 (tx,ty,dist) 入队（不消耗步数），并标记访问。

4. 无法到达 BFS 结束后仍未返回，则说明终点不可达，返回 -1。

复杂度分析

• 时间复杂度：

  • 扫描地图 $O(mn)$；
  • BFS 最多访问每个格子一次，且每次扩展常量条边（4 个方向 + 1 条虫洞），故 $O(mn)$。 合计 $O(mn)$。

• 空间复杂度：

  • 地图与访问标记数组各 $O(mn)$；
  • 队列最坏情况也存放 $O(mn)$ 个元素。 合计 $O(mn)$。

代码实现

Python

from collections import deque

def shortest_path(grid):
    m, n = len(grid), len(grid[0])
    # 方向数组：上、下、左、右
    dirs = [(-1,0),(1,0),(0,-1),(0,1)]
    # 记录虫洞配对
    holes = []
    for i in range(m):
        for j in range(n):
            if grid[i][j] == '2':
                holes.append((i,j))
            elif grid[i][j] == 'S':
                sx, sy = i, j
    teleport = {}
    # 两两配对
    for i in range(0, len(holes), 2):
        a, b = holes[i], holes[i+1]
        teleport[a] = b
        teleport[b] = a

    vis = [[False]*n for _ in range(m)]
    q = deque()
    q.append((sx, sy, 0))
    vis[sx][sy] = True

    while q:
        x, y, d = q.popleft()
        if grid[x][y] == 'E':
            return d
        # 四向移动
        for dx, dy in dirs:
            nx, ny = x+dx, y+dy
            if 0 <= nx < m and 0 <= ny < n \
               and not vis[nx][ny] and grid[nx][ny] != '1':
                vis[nx][ny] = True
                q.append((nx, ny, d+1))
        # 跨越虫洞
        if grid[x][y] == '2':
            tx, ty = teleport[(x,y)]
            if not vis[tx][ty]:
                vis[tx][ty] = True
                q.append((tx, ty, d))
    return -1

# 读取输入并输出
if __name__ == '__main__':
    m, n = map(int, input().split())
    grid = [list(input().strip()) for _ in range(m)]
    print(shortest_path(grid))

Java

import java.util.*;

public class Main {
    static int m, n;
    static char[][] g;
    static boolean[][] vis;
    static int[][] dirs = {{-1,0},{1,0},{0,-1},{0,1}};
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        m = in.nextInt();
        n = in.nextInt();
        g = new char[m][n];
        int sx=0, sy=0;
        List<int[]> holes = new ArrayList<>();
        for (int i = 0; i < m; i++) {
            String line = in.next();
            for (int j = 0; j < n; j++) {
                g[i][j] = line.charAt(j);
                if (g[i][j] == 'S') {
                    sx = i; sy = j;
                } else if (g[i][j] == '2') {
                    holes.add(new int[]{i,j});
                }
            }
        }
        // 建立虫洞映射
        Map<String, String> tel = new HashMap<>();
        for (int i = 0; i < holes.size(); i += 2) {
            int[] a = holes.get(i), b = holes.get(i+1);
            tel.put(a[0]+","+a[1], b[0]+","+b[1]);
            tel.put(b[0]+","+b[1], a[0]+","+a[1]);
        }
        vis = new boolean[m][n];
        Queue<int[]> q = new LinkedList<>();
        q.offer(new int[]{sx, sy, 0});
        vis[sx][sy] = true;
        int ans = -1;
        while (!q.isEmpty()) {
            int[] cur = q.poll();
            int x = cur[0], y = cur[1], d = cur[2];
            if (g[x][y] == 'E') { ans = d; break; }
            // 四向
            for (int[] dir : dirs) {
                int nx = x + dir[0], ny = y + dir[1];
                if (nx>=0 && nx<m && ny>=0 && ny<n
                    && !vis[nx][ny] && g[nx][ny] != '1') {
                    vis[nx][ny] = true;
                    q.offer(new int[]{nx, ny, d+1});
                }
            }
            // 虫洞
            if (g[x][y] == '2') {
                String key = x+","+y;
                String[] p = tel.get(key).split(",");
                int tx = Integer.parseInt(p[0]), ty = Integer.parseInt(p[1]);
                if (!vis[tx][ty]) {
                    vis[tx][ty] = true;
                    q.offer(new int[]{tx, ty, d});
                }
            }
        }
        System.out.println(ans);
    }
}

C++

#include <bits/stdc++.h>
using namespace std;
using pii = pair<int,int>;

int main(){
    int m,n;
    cin >> m >> n;
    vector<string> g(m);
    for(int i=0;i<m;i++) cin >> g[i];
    vector<pii> holes;
    int sx=0, sy=0;
    for(int i=0;i<m;i++){
        for(int j=0;j<n;j++){
            if(g[i][j]=='S'){ sx=i; sy=j; }
            else if(g[i][j]=='2'){
                holes.emplace_back(i,j);
            }
        }
    }
    // 建立虫洞映射
    map<pii,pii> tel;
    for(int i=0;i<holes.size();i+=2){
        pii a = holes[i], b = holes[i+1];
        tel[a] = b;
        tel[b] = a;
    }
    vector<vector<bool>> vis(m, vector<bool>(n,false));
    queue<tuple<int,int,int>> q;
    q.emplace(sx, sy, 0);
    vis[sx][sy] = true;
    int ans = -1;
    int dx[4] = {-1,1,0,0}, dy[4] = {0,0,-1,1};
    while(!q.empty()){
        auto [x,y,d] = q.front(); q.pop();
        if(g[x][y]=='E'){
            ans = d;
            break;
        }
        // 四向
        for(int k=0;k<4;k++){
            int nx = x+dx[k], ny = y+dy[k];
            if(nx>=0 && nx<m && ny>=0 && ny<n
               && !vis[nx][ny] && g[nx][ny] != '1'){
                vis[nx][ny] = true;
                q.emplace(nx, ny, d+1);
            }
        }
        // 虫洞
        if(g[x][y]=='2'){
            pii to = tel[{x,y}];
            int tx = to.first, ty = to.second;
            if(!vis[tx][ty]){
                vis[tx][ty] = true;
                q.emplace(tx, ty, d);
            }
        }
    }
    cout << ans << "\n";
    return 0;
}

题目内容

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

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

输入描述

第一行包含两个整数 $m,n(1≤m,n≤50)$ ，表示迷宫的行数和列数。

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

$0$：表示通道

$1$：表示墙壁

$2$：表示虫洞

$S$：表示起点

$E$：表示终点

输出描述

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

样例1

输入

5 5
S0000
11110
01010
01010
0000E

输出

8

说明

在这个例子中，最短的路径如下所示：

$S ->(0,1)->(0,2)->(0,3)->(0,4)->(1,4)->(2,4)->(3,4)->E$

共8步。

样例2

输入

3 3
S00
111
E00

输出

-1

说明

在这个例子中，起点 $5$ 和终点 $E$ 被墙壁阻隔，因此无法到达终点，输出 $-1$ 。

样例3

输入

3 3
S02
111
E02

输出

4

说明

在这个例子中，最短的路径如下所示：

$S ->(0,1)->(0,2)->(2,1)->E$ 共 $4$ 步。

$(0,2)$ 进入虫洞后，可直接从 $(2,1)$ 出来，不消耗步数