773. Sliding Puzzle
## 思路
BFS
记录0的位置跟目前state (1D tuple, 方便存seen set)
每个step移动0 直到state == (1,2,3,4,5,0)
## Code
```python
class Solution:
def slidingPuzzle(self, board: List[List[int]]) -> int:
moves = {
0: {1, 3},
1: {0, 2, 4},
2: {1, 5},
3: {0, 4},
4: {1, 3, 5},
5: {2, 4}
}
idx = 0
curr = []
for i in range(6):
curr.append(board[i//3][i%3])
if curr[-1] == 0:
idx = i
curr = tuple(curr)
queue = deque([(idx, curr)])
seen = {curr}
step = 0
while queue:
for _ in range(len(queue)):
idx, curr = queue.popleft()
if curr == (1, 2, 3, 4, 5, 0):
return step
curr = list(curr)
for i in moves[idx]:
curr[i], curr[idx] = curr[idx], curr[i]
next_ = tuple(curr)
if next_ not in seen:
seen.add(next_)
queue.append((i, next_))
curr[i], curr[idx] = curr[idx], curr[i]
step += 1
return -1
```