Leetcode 787 Solution

class Solution:
    def slidingPuzzle(self, board: List[List[int]]) -> int:
        def get_key(board):
            return ",".join([str(num) for row in board for num in row])

        def is_target(board):
            return board[0][0] == 1 and board[0][1] == 2 and board[0][2] == 3 and board[1][0] == 4 and board[1][1] == 5 and board[1][2] == 0

        q = collections.deque()
        visited = set()

        visited.add(get_key(board))
        q.append(board)

        ans = 0
        while q:
            s = len(q)

            for _ in range(s):
                board = q.popleft()

                if is_target(board):
                    return ans

                for i, j in itertools.product([0, 1], [0, 1, 2]):
                    if board[i][j] == 0:
                        break

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

                for di, dj in directions:
                    neigh_i = i + di
                    neigh_j = j + dj

                    if not (0 <= neigh_i < 2 and 0 <= neigh_j < 3):
                        continue

                    newboard = [list(row) for row in board]
                    newboard[i][j], newboard[neigh_i][neigh_j] = newboard[neigh_i][neigh_j], newboard[i][j]

                    newkey = get_key(newboard)
                    if newkey in visited:
                        continue

                    q.append(newboard)
                    visited.add(newkey)

            ans += 1

        return -1