（BFS）题解 | 量子网络穿梭

from collections import deque
import sys

# 0: 数据包可以在相邻的标准通道节点之间自由移动，每次移动消耗 1 个时间单位
# 1: 防火墙，不可通行
# 2: 量子纠缠门, 瞬间、不耗费任何时间直接传送到另一个纠缠门（DFS到所有其他纠缠门？）

# S: 起点
# E: 终点

def main():
    input = sys.stdin.readline
    m, n = list(map(int, input().split()))
    arr = []

    # 获取起点和传送门
    start_pos = (-1, -1)
    gates = []
    for i in range(m):
        s = input().strip()
        tmp = []
        for j in range(n):
            ch = s[j]
            if ch == 'S':
                start_pos = (i, j)
            elif ch == '2':
                gates.append([i, j])    # 记录所有传送门的位置
            
            tmp.append(ch)
        arr.append(tmp)
    
    # 传送门成对出现
    gates_pair = {}
    for k in range(0, len(gates), 2):
        x1, y1 = gates[k]
        x2, y2 = gates[k+1]
        gates_pair[(x1, y1)] = (x2, y2)
        gates_pair[(x2, y2)] = (x1, y1)

    # BFS遍历
    visited = set()
    q = deque()
    q.append((start_pos, 0))
    visited.add(start_pos)

    # 上右下左
    dirs = [[-1, 0], [0, 1], [1, 0], [0, -1]]
    while q:
        pos, time = q.popleft()
        x, y = pos
        
        # 遍历四个方向
        for d in dirs:
            dx, dy = d
            nx, ny = x + dx, y + dy
            if (nx < 0 or nx >= m or ny < 0 or ny >= n or 
                arr[nx][ny] == '1' or (nx, ny) in visited):
                continue
            
            visited.add((nx, ny))
            ch = arr[nx][ny]
            if ch == 'E':   # 终端
                return time + 1
            
            if ch == '0':
                q.append(((nx, ny), time+1))
                continue
            elif ch == '2':
                # 量子纠缠门成对, 瞬间传送到对应位置
                new_pos = gates_pair[(nx, ny)]
                if new_pos in visited:
                    continue
                visited.add(new_pos)
                q.append((new_pos, time+1))
    return -1

print(main())