量子网络穿梭
题意
给一个 的二维网格，包含以下元素：
0：标准通道，可以自由通行1：防火墙，不可通行2：量子纠缠门，成对出现。进入一个纠缠门后可以瞬间（0 时间）传送到配对的另一个纠缠门S：起点E：终点
每次向上下左右移动消耗 1 个时间单位。求从 S 到 E 的最短时间，不可达输出 -1。
思路
拿到这题，第一反应是 BFS 求最短路——网格上每次移动代价为 1，这是 BFS 的经典场景。
但量子纠缠门怎么处理？进入一个纠缠门后，传送到另一个纠缠门的代价是 0。也就是说，走到纠缠门的代价是 1（普通移动），但从纠缠门 A 到纠缠门 B 的代价是 0。
这正是 0-1 BFS 的适用场景。 边权只有 0 和 1 两种，用双端队列（deque）代替普通队列：权为 0 的边加到队首，权为 1 的边加到队尾。这样就能保证队列里的元素始终按距离单调排列，不需要用优先队列。
具体做法：
- 预处理纠缠门的配对关系。 按出现顺序，每两个
2配成一对，用哈希表存映射。 - 0-1 BFS。 从
S出发，每次弹出队首节点，尝试向四个方向移动：
- 如果邻居是 1（防火墙），跳过
- 否则，移动代价为 1，加到队尾
- 如果邻居是 2（纠缠门），额外把配对的纠缠门以相同代价加到队首（因为传送代价为 0）
- 第一次弹出
E时的距离就是答案。
时间复杂度 ，空间复杂度
。
代码
#include <bits/stdc++.h>
using namespace std;
int main(){
int m, n;
scanf("%d%d", &m, &n);
vector<string> grid(m);
int sr, sc, er, ec;
vector<pair<int,int>> portals;
for(int i = 0; i < m; i++){
char buf[1010];
scanf("%s", buf);
grid[i] = buf;
for(int j = 0; j < n; j++){
if(grid[i][j] == 'S') { sr = i; sc = j; }
if(grid[i][j] == 'E') { er = i; ec = j; }
if(grid[i][j] == '2') portals.push_back({i, j});
}
}
map<pair<int,int>, pair<int,int>> portalMap;
for(int i = 0; i < (int)portals.size(); i += 2){
portalMap[portals[i]] = portals[i+1];
portalMap[portals[i+1]] = portals[i];
}
vector<vector<int>> dist(m, vector<int>(n, INT_MAX));
deque<pair<int,int>> dq;
dist[sr][sc] = 0;
dq.push_back({sr, sc});
int dx[] = {0,0,1,-1};
int dy[] = {1,-1,0,0};
while(!dq.empty()){
auto [r, c] = dq.front(); dq.pop_front();
int d = dist[r][c];
if(r == er && c == ec){
printf("%d\n", d);
return 0;
}
for(int k = 0; k < 4; k++){
int nr = r + dx[k], nc = c + dy[k];
if(nr < 0 || nr >= m || nc < 0 || nc >= n) continue;
if(grid[nr][nc] == '1') continue;
if(d + 1 < dist[nr][nc]){
dist[nr][nc] = d + 1;
if(grid[nr][nc] == '2' && portalMap.count({nr, nc})){
auto [pr, pc] = portalMap[{nr, nc}];
if(d + 1 < dist[pr][pc]){
dist[pr][pc] = d + 1;
dq.push_front({pr, pc});
}
}
dq.push_back({nr, nc});
}
}
}
printf("-1\n");
return 0;
}
import java.util.*;
public class Main {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int m = sc.nextInt(), n = sc.nextInt();
char[][] grid = new char[m][n];
int sr = 0, scc = 0, er = 0, ec = 0;
List<int[]> portals = new ArrayList<>();
for (int i = 0; i < m; i++) {
String line = sc.next();
for (int j = 0; j < n; j++) {
grid[i][j] = line.charAt(j);
if (grid[i][j] == 'S') { sr = i; scc = j; }
if (grid[i][j] == 'E') { er = i; ec = j; }
if (grid[i][j] == '2') portals.add(new int[]{i, j});
}
}
Map<Long, long[]> portalMap = new HashMap<>();
for (int i = 0; i + 1 < portals.size(); i += 2) {
int[] a = portals.get(i), b = portals.get(i + 1);
long ka = (long) a[0] * n + a[1];
long kb = (long) b[0] * n + b[1];
portalMap.put(ka, new long[]{b[0], b[1]});
portalMap.put(kb, new long[]{a[0], a[1]});
}
int[][] dist = new int[m][n];
for (int[] row : dist) Arrays.fill(row, Integer.MAX_VALUE);
Deque<int[]> dq = new ArrayDeque<>();
dist[sr][scc] = 0;
dq.addLast(new int[]{sr, scc});
int[] dx = {0, 0, 1, -1}, dy = {1, -1, 0, 0};
while (!dq.isEmpty()) {
int[] cur = dq.pollFirst();
int r = cur[0], c = cur[1], d = dist[r][c];
if (r == er && c == ec) {
System.out.println(d);
return;
}
for (int k = 0; k < 4; k++) {
int nr = r + dx[k], nc = c + dy[k];
if (nr < 0 || nr >= m || nc < 0 || nc >= n) continue;
if (grid[nr][nc] == '1') continue;
if (d + 1 < dist[nr][nc]) {
dist[nr][nc] = d + 1;
if (grid[nr][nc] == '2') {
long key = (long) nr * n + nc;
if (portalMap.containsKey(key)) {
long[] p = portalMap.get(key);
int pr = (int) p[0], pc = (int) p[1];
if (d + 1 < dist[pr][pc]) {
dist[pr][pc] = d + 1;
dq.addFirst(new int[]{pr, pc});
}
}
}
dq.addLast(new int[]{nr, nc});
}
}
}
System.out.println(-1);
}
}
import sys
from collections import deque
def main():
input_data = sys.stdin.read().split()
idx = 0
m = int(input_data[idx]); idx += 1
n = int(input_data[idx]); idx += 1
grid = []
sr = sc = er = ec = 0
portals = []
for i in range(m):
row = input_data[idx]; idx += 1
grid.append(row)
for j in range(n):
if row[j] == 'S':
sr, sc = i, j
elif row[j] == 'E':
er, ec = i, j
elif row[j] == '2':
portals.append((i, j))
portal_map = {}
for i in range(0, len(portals) - 1, 2):
a, b = portals[i], portals[i + 1]
portal_map[a] = b
portal_map[b] = a
INF = float('inf')
dist = [[INF] * n for _ in range(m)]
dist[sr][sc] = 0
dq = deque()
dq.append((sr, sc))
while dq:
r, c = dq.popleft()
d = dist[r][c]
if r == er and c == ec:
print(d)
return
for dr, dc in ((0, 1), (0, -1), (1, 0), (-1, 0)):
nr, nc = r + dr, c + dc
if 0 <= nr < m and 0 <= nc < n and grid[nr][nc] != '1':
if d + 1 < dist[nr][nc]:
dist[nr][nc] = d + 1
if grid[nr][nc] == '2' and (nr, nc) in portal_map:
pr, pc = portal_map[(nr, nc)]
if d + 1 < dist[pr][pc]:
dist[pr][pc] = d + 1
dq.appendleft((pr, pc))
dq.append((nr, nc))
print(-1)
main()
const readline = require('readline');
const rl = readline.createInterface({ input: process.stdin });
const lines = [];
rl.on('line', l => lines.push(l.trim()));
rl.on('close', () => {
const [m, n] = lines[0].split(' ').map(Number);
const grid = [];
let sr = 0, sc = 0, er = 0, ec = 0;
const portals = [];
for (let i = 0; i < m; i++) {
grid.push(lines[i + 1]);
for (let j = 0; j < n; j++) {
const ch = grid[i][j];
if (ch === 'S') { sr = i; sc = j; }
if (ch === 'E') { er = i; ec = j; }
if (ch === '2') portals.push([i, j]);
}
}
const portalMap = new Map();
for (let i = 0; i + 1 < portals.length; i += 2) {
const [ar, ac] = portals[i], [br, bc] = portals[i + 1];
portalMap.set(ar * n + ac, [br, bc]);
portalMap.set(br * n + bc, [ar, ac]);
}
const dist = Array.from({length: m}, () => new Int32Array(n).fill(0x7fffffff));
dist[sr][sc] = 0;
const dq = [];
let head = 0;
dq.push([sr, sc]);
const dx = [0, 0, 1, -1], dy = [1, -1, 0, 0];
while (head < dq.length) {
const [r, c] = dq[head++];
const d = dist[r][c];
if (r === er && c === ec) {
console.log(d);
return;
}
for (let k = 0; k < 4; k++) {
const nr = r + dx[k], nc = c + dy[k];
if (nr < 0 || nr >= m || nc < 0 || nc >= n) continue;
if (grid[nr][nc] === '1') continue;
if (d + 1 < dist[nr][nc]) {
dist[nr][nc] = d + 1;
if (grid[nr][nc] === '2') {
const key = nr * n + nc;
if (portalMap.has(key)) {
const [pr, pc] = portalMap.get(key);
if (d + 1 < dist[pr][pc]) {
dist[pr][pc] = d + 1;
dq.splice(head, 0, [pr, pc]);
}
}
}
dq.push([nr, nc]);
}
}
}
console.log(-1);
});
京公网安备 11010502036488号