题解 | #量子网络穿梭#

题目链接

量子网络穿梭

题目描述

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

标准通道 (0): 数据包可以在相邻的标准通道节点之间自由移动，每次移动消耗 1 个时间单位。
防火墙 (1): 这些节点是损坏的或被设置为不可通行，数据包无法进入。
量子纠缠门 (2): 网络中存在成对的纠缠门。当数据包进入一个纠缠门时，它可以瞬间、不耗费任何时间地传送到与之配对的另一个纠缠门所在的位置。
起点 (S): 是数据包的初始位置。
终点 (E): 是数据包的目标位置。

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

解题思路

这是一个典型的图论最短路问题，发生在二维网格上。由于移动的代价（时间消耗）有两种：普通移动代价为 1，通过量子纠缠门传送的代价为 0，这是一个边权仅为 0 或 1 的图。

对于这类问题，最适合的算法是 0-1 广度优先搜索 (0-1 BFS)。0-1 BFS 是 Dijkstra 算法的一种特殊情况，它使用双端队列 (deque) 来代替优先队列，从而将时间复杂度优化到线性时间。

算法步骤如下：

预处理：
- 遍历整个 $N \cdot M$ 网格，找到起点 $S$ 、终点 $E$ 的坐标。
- 同时，找到所有量子纠缠门 2 的坐标，并将它们成对存储起来。例如，可以使用一个 map 来记录每个门对应的另一个门的位置。
- 创建一个距离数组 $dist[N][M]$ ，初始化所有位置的距离为无穷大，表示尚未访问。
0-1 BFS 执行：
- 创建一个双端队列 $dq$ ，并将起点 $S$ 的坐标和初始距离 0 加入队列。同时，更新起点的 $dist$ 值为 0。
- 当 $dq$ 不为空时，从队首取出一个状态 $(d, r, c)$ ，表示到达坐标 $(r, c)$ 的当前最短距离为 $d$ 。
- 如果 $d > dist[r][c]$ ，说明已经有更短的路径到达该点，直接跳过。
- 对于当前点 $(r, c)$ ，探索所有可能的移动：
  - 普通移动：向上下左右四个方向移动到相邻点 $(nr, nc)$ 。如果新位置合法（未越界、不是防火墙），并且 $d + 1 < dist[nr][nc]$ ，则更新 $dist[nr][nc] = d + 1$ ，并将新状态 $(d + 1, nr, nc)$ 加入队尾。
  - 量子门传送：如果当前点 $(r, c)$ 是一个量子门，找到其配对门的位置 $(pr, pc)$ 。如果 $d < dist[pr][pc]$ ，则更新 $dist[pr][pc] = d$ ，并将新状态 $(d, pr, pc)$ 加入队首。

将代价为 0 的移动（量子门）放入队首，可以保证我们总是优先处理距离更近的节点，这与 Dijkstra 算法的思想一致，但由于边权只有 0 和 1，使用双端队列效率更高。

结果：
- BFS 结束后， $dist$ 数组中终点坐标对应的值就是从起点到终点的最短时间。如果终点不可达，其距离值将保持为无穷大，此时应返回 -1。

代码

cpp
java
python

#include <iostream>
#include <vector>
#include <string>
#include <deque>
#include <map>
#include <tuple>

using namespace std;

const int INF = 1e9;

int main() {
    int n, m;
    cin >> n >> m;
    vector<string> grid(n);
    int start_r, start_c, end_r, end_c;
    vector<pair<int, int>> gates;
    for (int i = 0; i < n; ++i) {
        cin >> grid[i];
        for (int j = 0; j < m; ++j) {
            if (grid[i][j] == 'S') {
                start_r = i;
                start_c = j;
            } else if (grid[i][j] == 'E') {
                end_r = i;
                end_c = j;
            } else if (grid[i][j] == '2') {
                gates.push_back({i, j});
            }
        }
    }

    map<pair<int, int>, pair<int, int>> gate_pairs;
    for (size_t i = 0; i < gates.size(); i += 2) {
        gate_pairs[gates[i]] = gates[i + 1];
        gate_pairs[gates[i + 1]] = gates[i];
    }

    vector<vector<int>> dist(n, vector<int>(m, INF));
    deque<tuple<int, int, int>> dq;

    dist[start_r][start_c] = 0;
    dq.push_front({0, start_r, start_c});

    int dr[] = {-1, 1, 0, 0};
    int dc[] = {0, 0, -1, 1};

    while (!dq.empty()) {
        auto [d, r, c] = dq.front();
        dq.pop_front();

        if (d > dist[r][c]) {
            continue;
        }

        if (r == end_r && c == end_c) {
            cout << d << endl;
            return 0;
        }

        // 普通移动
        for (int i = 0; i < 4; ++i) {
            int nr = r + dr[i];
            int nc = c + dc[i];
            if (nr >= 0 && nr < n && nc >= 0 && nc < m && grid[nr][nc] != '1') {
                if (dist[r][c] + 1 < dist[nr][nc]) {
                    dist[nr][nc] = dist[r][c] + 1;
                    dq.push_back({dist[nr][nc], nr, nc});
                }
            }
        }

        // 量子门
        if (grid[r][c] == '2') {
            auto [pr, pc] = gate_pairs[{r, c}];
            if (dist[r][c] < dist[pr][pc]) {
                dist[pr][pc] = dist[r][c];
                dq.push_front({dist[pr][pc], pr, pc});
            }
        }
    }

    cout << -1 << endl;

    return 0;
}

import java.util.*;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int m = sc.nextInt();
        char[][] grid = new char[n][m];
        int startR = -1, startC = -1, endR = -1, endC = -1;
        List<int[]> gates = new ArrayList<>();

        for (int i = 0; i < n; i++) {
            String row = sc.next();
            for (int j = 0; j < m; j++) {
                grid[i][j] = row.charAt(j);
                if (grid[i][j] == 'S') {
                    startR = i;
                    startC = j;
                } else if (grid[i][j] == 'E') {
                    endR = i;
                    endC = j;
                } else if (grid[i][j] == '2') {
                    gates.add(new int[]{i, j});
                }
            }
        }

        Map<String, int[]> gatePairs = new HashMap<>();
        for (int i = 0; i < gates.size(); i += 2) {
            int[] g1 = gates.get(i);
            int[] g2 = gates.get(i + 1);
            gatePairs.put(g1[0] + "," + g1[1], g2);
            gatePairs.put(g2[0] + "," + g2[1], g1);
        }

        int[][] dist = new int[n][m];
        for (int[] row : dist) {
            Arrays.fill(row, Integer.MAX_VALUE);
        }

        Deque<int[]> dq = new ArrayDeque<>();
        dist[startR][startC] = 0;
        dq.addFirst(new int[]{0, startR, startC});

        int[] dr = {-1, 1, 0, 0};
        int[] dc = {0, 0, -1, 1};

        while (!dq.isEmpty()) {
            int[] curr = dq.pollFirst();
            int d = curr[0];
            int r = curr[1];
            int c = curr[2];

            if (d > dist[r][c]) {
                continue;
            }

            if (r == endR && c == endC) {
                System.out.println(d);
                return;
            }

            // 普通移动
            for (int i = 0; i < 4; i++) {
                int nr = r + dr[i];
                int nc = c + dc[i];
                if (nr >= 0 && nr < n && nc >= 0 && nc < m && grid[nr][nc] != '1') {
                    if (dist[r][c] + 1 < dist[nr][nc]) {
                        dist[nr][nc] = dist[r][c] + 1;
                        dq.addLast(new int[]{dist[nr][nc], nr, nc});
                    }
                }
            }

            // 量子门
            if (grid[r][c] == '2') {
                String key = r + "," + c;
                if (gatePairs.containsKey(key)) {
                    int[] pair = gatePairs.get(key);
                    int pr = pair[0];
                    int pc = pair[1];
                    if (dist[r][c] < dist[pr][pc]) {
                        dist[pr][pc] = dist[r][c];
                        dq.addFirst(new int[]{dist[pr][pc], pr, pc});
                    }
                }
            }
        }

        System.out.println(-1);
    }
}

import collections

def main():
    n, m = map(int, input().split())
    grid = [input() for _ in range(n)]

    start_pos, end_pos = None, None
    gates = []
    for r in range(n):
        for c in range(m):
            if grid[r][c] == 'S':
                start_pos = (r, c)
            elif grid[r][c] == 'E':
                end_pos = (r, c)
            elif grid[r][c] == '2':
                gates.append((r, c))

    gate_pairs = {}
    for i in range(0, len(gates), 2):
        gate_pairs[gates[i]] = gates[i+1]
        gate_pairs[gates[i+1]] = gates[i]

    dist = [[float('inf')] * m for _ in range(n)]
    dq = collections.deque()

    start_r, start_c = start_pos
    dist[start_r][start_c] = 0
    dq.appendleft((0, start_r, start_c))

    dr = [-1, 1, 0, 0]
    dc = [0, 0, -1, 1]

    while dq:
        d, r, c = dq.popleft()

        if d > dist[r][c]:
            continue

        if (r, c) == end_pos:
            print(d)
            return

        # 普通移动
        for i in range(4):
            nr, nc = r + dr[i], c + dc[i]
            if 0 <= nr < n and 0 <= nc < m and grid[nr][nc] != '1':
                if dist[r][c] + 1 < dist[nr][nc]:
                    dist[nr][nc] = dist[r][c] + 1
                    dq.append((dist[nr][nc], nr, nc))

        # 量子门
        if grid[r][c] == '2':
            pr, pc = gate_pairs[(r, c)]
            if dist[r][c] < dist[pr][pc]:
                dist[pr][pc] = dist[r][c]
                dq.appendleft((dist[pr][pc], pr, pc))

    print(-1)

if __name__ == "__main__":
    main()

算法及复杂度

算法：0-1 广度优先搜索 (0-1 BFS)
时间复杂度： $\mathcal{O}(N \cdot M)$ - 每个网格节点最多被访问一次，并以常数时间处理其邻居和可能的量子门传送。
空间复杂度： $\mathcal{O}(N \cdot M)$ - 主要用于存储距离数组 $dist$ 和双端队列 $dq$ 。