大家可以在 华为刷题 牛客官方练习集刷题

量子网络穿梭 在一个未来的量子计算中心，您需要引导一个数据包（Data Packet）通过一个复杂的量子网络。该网络可以被抽象为一个 m×nm×n 的二维矩阵。网络中的每个节点都有其特定的功能：

• 标准通道 (Standard Channel) : 用数字 00 表示，数据包可以在相邻的标准通道节点之间自由移动，每次移动消耗 11 个时间单位。
• 防火墙 (Firewall) : 用数字 11 表示，这些节点是损坏的或被设置为不可通行，数据包无法进入。
• 量子纠缠门 (Quantum Entanglement Gate) : 用数字 22 表示。网络中存在成对的纠缠门。当数据包进入一个纠缠门时，它可以瞬间、不耗费任何时间地传送到与之配对的另一个纠缠门所在的位置。
• 起点 (Source) : 用符号 SS 表示，是数据包的初始位置。
• 终点 (Destination) : 用符号 EE 表示，是数据包的目标位置。

您的任务是计算出数据包从起点 SS 到达终点 EE 所需的最短时间。数据包只能在网络的上下左右四个方向上移动，不能移出网络边界，也不能穿过防火墙。如果数据包无法到达终点，则返回 −1−1。

时间限制：C/C++ 1秒，其他语言2秒 空间限制：C/C++ 256M，其他语言512M 输入描述：

输入的第一行包含两个正整数 m 和 n (1 \le m, n \le 50)，分别代表量子网络的行数和列数。

接下来的 m 行，每行包含 n 个字符，描述了量子网络每个节点的类型。字符集为 {'0', '1', '2', 'S', 'E'}。

输出描述：

输出一个整数，表示数据包从起点到终点所需的最短时间。如果无法到达，则输出 -1。

补充说明：

本题由牛友@Charles 整理上传

示例1 输入例子：

4 9
001010000
00000000S
0100E0001
100000001

输出例子：

5

题解

这道题本质上是在一个带有特殊传送机制的网格图上求最短路径。

核心思路是使用BFS（广度优先搜索）来解决。因为BFS天然保证了第一次到达目标点时就是最短路径，这正是我们需要的。

关键处理传送门的逻辑：

1. 首先要找到所有传送门的位置，并建立它们之间的对应关系
2. 当BFS过程中遇到传送门时，不仅要考虑四个方向的普通移动，还要考虑传送到对应传送门的可能性
3. 传送不消耗步数，所以传送后的步数和传送前相同

具体算法步骤：

1. 读入迷宫，找到起点、终点和所有传送门位置
2. 建立传送门之间的对应关系（第一个和第二个对应，第三个和第四个对应，以此类推）
3. 使用BFS从起点开始搜索，维护一个队列存储 的状态
4. 对于每个位置，尝试四个方向的移动；如果当前位置是传送门，还要尝试传送
5. 使用visited数组避免重复访问
6. 第一次到达终点时就找到了最短路径

时间复杂度是 ，因为每个格子最多被访问一次，对于给定的数据范围完全可以接受。

传送门机制看似复杂，实际上只是在普通BFS的基础上增加了额外的移动选项，本质思想没有改变。

参考代码

• Python

import sys
from collections import deque
input = lambda: sys.stdin.readline().strip()

def solve():
    # 读取迷宫大小
    m, n = map(int, input().split())
    
    # 读取迷宫地图
    maze = []
    for i in range(m):
        maze.append(input())
    
    # 找到起点、终点和传送门
    start = None
    end = None
    portals = []  # 存储所有传送门位置
    
    for i in range(m):
        for j in range(n):
            if maze[i][j] == 'S':
                start = (i, j)
            elif maze[i][j] == 'E':
                end = (i, j)
            elif maze[i][j] == '2':
                portals.append((i, j))
    
    # 建立传送门对应关系
    portal_map = {}
    for k in range(0, len(portals), 2):
        if k + 1 < len(portals):
            p1, p2 = portals[k], portals[k + 1]
            portal_map[p1] = p2
            portal_map[p2] = p1
    
    # BFS搜索最短路径
    queue = deque([(start[0], start[1], 0)])
    visited = set()
    visited.add(start)
    
    # 四个方向：上下左右
    dirs = [(-1, 0), (1, 0), (0, -1), (0, 1)]
    
    while queue:
        x, y, steps = queue.popleft()
        
        # 到达终点
        if (x, y) == end:
            return steps
        
        # 尝试四个方向移动
        for dx, dy in dirs:
            nx, ny = x + dx, y + dy
            
            # 检查边界和墙壁
            if 0 <= nx < m and 0 <= ny < n and maze[nx][ny] != '1':
                if (nx, ny) not in visited:
                    visited.add((nx, ny))
                    queue.append((nx, ny, steps + 1))
        
        # 如果当前位置是传送门，尝试传送
        if (x, y) in portal_map:
            tx, ty = portal_map[(x, y)]
            if (tx, ty) not in visited:
                visited.add((tx, ty))
                queue.append((tx, ty, steps))  # 传送不消耗步数
    
    return -1

print(solve())

• Cpp

#include <bits/stdc++.h>
using namespace std;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    
    int m, n;
    cin >> m >> n;
    
    // 读取迷宫地图
    vector<string> maze(m);
    for (int i = 0; i < m; i++) {
        cin >> maze[i];
    }
    
    // 找到起点、终点和传送门
    pair