1
# Runtime: 93 ms (Top 39.62%) | Memory: 14.1 MB (Top 16.60%)
2

3

4
class Solution:
5
    def slidingPuzzle(self, board: List[List[int]]) -> int:
6
        def findNei(board):
7
            directs = [[0, 1], [0, -1], [1, 0], [-1, 0]]
8
            boards = []
9
            for i in range(2):
10
                for j in range(3):
11
                    if board[i][j] == 0:
12
                        for dr, dc in directs:
13
                            tmp = [row.copy() for row in board]
14
                            r, c = i + dr, j + dc
15
                            if r in range(2) and c in range(3):
16
                                tmp[r][c], tmp[i][j] = tmp[i][j], tmp[r][c]
17
                                boards.append(tmp)
18
            return boards
19

20
        visited = set()
21
        target = [[1, 2, 3], [4, 5, 0]]
22
        if board == target:
23
            return 0
24
        rows, cols = len(board), len(board[0])
25
        q = collections.deque()
26
        step = 1
27

28
        for row in range(rows):
29
            for col in range(cols):
30
                if board[row][col] == 0:
31
                    boards = findNei(board)
32
                    for b in boards:
33
                        if b == target:
34
                            return step
35
                        visited.add(tuple([tuple(row) for row in b]))
36
                        q.append(b)
37
                    break
38

39
        while q:
40
            step += 1
41
            for _ in range(len(q)):
42
                b = q.popleft()
43
                boards = findNei(b)
44
                for b in boards:
45
                    if b == target:
46
                        return step
47
                    t = tuple([tuple(row) for row in b])
48
                    if t not in visited:
49
                        visited.add(t)
50
                        q.append(b)
51

52
        return -1