1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
|
# 773. Sliding Puzzle
from collections import deque
"""
on an empty 2 x 3 board there are five tiles labeled from 1 to 5 and an empty
square represented by 0. a move consists of choosing 0 and a 4-directionall
adjacent number and swapping it. the state of the board is solved if and only
if the board is '[[1,2,3],[4,5,0]]'. given the puzzle 'board', return the
least number of moves required so that the state of the board is solved. if
it is impossible for the state of the board to be solved, return -1
"""
class Solution(object):
def slidingPuzzle(self, board):
"""
:type board: List[List[int]]
:rtype: int
"""
s = "".join(str(n) for r in board for n in r)
dq, vis = deque(), {s}
dq.append((s, s.index("0")))
steps, height, width = 0, len(board), len(board[0])
while dq:
for _ in range(len(dq)):
t, i = dq.popleft()
if t == "123450":
return steps
x, y = i // width, i % width
for r, c in (x, y + 1), (x, y - 1), (x + 1, y), (x - 1, y):
if height > r >= 0 <= c < width:
ch = [n for n in t]
ch[i], ch[r * width + c] = ch[r * width + c], "0"
s = "".join(ch)
if s not in vis:
vis.add(s)
dq.append((s, r * width + c))
steps += 1
return -1
if __name__ == "__main__":
obj = Solution()
print(obj.slidingPuzzle(board=[[1, 2, 3], [4, 0, 5]]))
print(obj.slidingPuzzle(board=[[1, 2, 3], [5, 4, 0]]))
print(obj.slidingPuzzle(board=[[4, 1, 2], [5, 0, 3]]))
|