题解 | 走一个大整数迷宫

python3超时用Pypy3运行

from collections import deque

n,m,p = map(int,input().split())
A = [list(map(int,input().split())) for _ in range(n)]
B = [list(map(int,input().split())) for _ in range(n)]
C = [[0]*m for _ in range(n)]

# 预处理数组C
MOD = p-1
for i in range(n):
    for j in range(m):
        exp = pow(2, B[i][j], MOD)
        C[i][j] = A[i][j] * pow(p, exp, MOD) % MOD

# 三维，否已经到达过位置 x,y, 且此时计数器模值为 mod_val
visited = [[[False] * MOD for _ in range(m)] for _ in range(n)]
q = deque()

start_val = C[0][0] % MOD
visited[0][0][start_val] = True
q.append((0, 0, start_val, 0))  # (x, y, mod_val, steps)

dirs = [(-1,0),(1,0),(0,-1),(0,1)]

res = -1
while q:
    x, y, mod_val, steps = q.popleft()

    # 到达终点且满足条件
    if x == n - 1 and y == m - 1 and mod_val % MOD == 0:
        res = steps
        break

    for dx, dy in dirs:
        nx, ny = x + dx, y + dy
        if 0 <= nx < n and 0 <= ny < m:
            new_val = (mod_val + C[nx][ny]) % MOD
            if not visited[nx][ny][new_val]:
                visited[nx][ny][new_val] = True
                q.append((nx, ny, new_val, steps + 1))
print(res)