Re: [閒聊] 每日leetcode
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
```
--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 94.156.205.222 (臺灣)
※ 文章網址: https://www.ptt.cc/bbs/Marginalman/M.1732543285.A.C54.html
討論串 (同標題文章)
完整討論串 (本文為第 1153 之 1548 篇)：