Submission #48410290

---

Source Code Expand

from collections import deque
from copy import deepcopy

H, W = map(int, input().split())
A = [list(map(int, input().split())) for _ in range(H)]
B = [list(map(int, input().split())) for _ in range(H)]


def to_tuple(a):
    return tuple(tuple(row) for row in a)


dist = {to_tuple(A): 0}
q = deque([A])
while q:
    a = q.popleft()
    for i in range(H - 1):
        b = deepcopy(a)
        b[i], b[i + 1] = b[i + 1], b[i]
        if to_tuple(b) not in dist:
            dist[to_tuple(b)] = dist[to_tuple(a)] + 1
            q.append(b)
    for j in range(W - 1):
        b = deepcopy(a)
        for i in range(H):
            b[i][j + 1], b[i][j] = b[i][j], b[i][j + 1]
        if to_tuple(b) not in dist:
            dist[to_tuple(b)] = dist[to_tuple(a)] + 1
            q.append(b)
if to_tuple(B) not in dist:
    print(-1)
else:
    print(dist[to_tuple(B)])

Submission Info

Judge Result