773.md

Sliding Puzzle

Description

link

---

Solution

• See Code

---

Code

Complexity T : O(n(logn)) M : -

class Solution:
    '''
    1. moves保存所有0存在点可以行动的方向
    2. used保存所有已经见到过的s，也就是状态
    3. 传统BFS，用状态记录下来当前到达的位置，当满足条件则停止
    4. 应该学习的是如何使用字符串保存状态
    '''
    def slidingPuzzle(self, board: List[List[int]]) -> int:
        moves, used, cnt = {0: {1, 3}, 1:{0, 2, 4}, 2:{1, 5}, 3:{0, 4}, 4:{1, 3, 5}, 5:{2, 4}}, set(), 0
        s = "".join(str(c) for row in board for c in row)
        q = [(s, s.index("0"))]
        while q:
            new = []
            for s, i in q:
                used.add(s)
                if s == "123450":
                    return cnt
                arr = [c for c in s]
                for move in moves[i]:
                    new_arr = arr[:]
                    new_arr[i], new_arr[move] = new_arr[move], new_arr[i]
                    new_s = "".join(new_arr)
                    if new_s not in used:
                        new.append((new_s, move))
            cnt += 1
            q = new
        return -1