diff options
author | Jack Sangdahl <[email protected]> | 2024-11-24 21:10:51 -0700 |
---|---|---|
committer | Jack Sangdahl <[email protected]> | 2024-11-24 21:10:51 -0700 |
commit | db0a6037953626a1a919f975b57ad10e21d7fa1b (patch) | |
tree | a35d18b6dccaa60f70baa2c351438013b897369a /sliding_puzzle.py | |
parent | e4e8f133e01edbacdb2683cca3730a1ba2475479 (diff) | |
download | leetcode-db0a6037953626a1a919f975b57ad10e21d7fa1b.tar.gz leetcode-db0a6037953626a1a919f975b57ad10e21d7fa1b.zip |
773. sliding puzzle
Diffstat (limited to 'sliding_puzzle.py')
-rw-r--r-- | sliding_puzzle.py | 46 |
1 files changed, 46 insertions, 0 deletions
diff --git a/sliding_puzzle.py b/sliding_puzzle.py new file mode 100644 index 0000000..cfa7b5f --- /dev/null +++ b/sliding_puzzle.py @@ -0,0 +1,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]])) |