题解 | 走一个大整数迷宫

from collections import deque

# Process input
n, m, p = map(int, input().split())
ma = [list(map(int, input().split())) for _ in range(n)]
mb = [list(map(int, input().split())) for _ in range(n)]

# Aux
mc = ma
MOD = p - 1
# BFS
dx = [1, -1, 0, 0]
dy = [0, 0, 1, -1]
q = deque()
q.append((0, 0, mc[0][0], 0))
dist = [[[1e9]*MOD for _ in range(m)] for _ in range(n)]
while q:
    x, y, c, t = q.popleft()
    rem = c % MOD
    if t >= dist[x][y][rem]:
        continue
    dist[x][y][rem] = t
    if x == n-1 and y == m-1 and rem == 0:
        break
    for i in range(4):
        nx, ny = x+dx[i], y+dy[i]
        if 0 <= nx < n and 0 <= ny < m:
            q.append((nx, ny, c+mc[nx][ny], t+1))
    
# Output
res = dist[n-1][m-1][0]
print(-1 if res == 1e9 else res)