#773
Sliding Puzzle
specialist · 935 · lc hard +32 · verified · 74.3% accepted · 2,739 likes · top 85%
Description
A 2 x 3 sliding puzzle contains tiles numbered 1–5 and one empty cell represented by 0. Each move swaps the 0 with a 4-directionally adjacent tile. The puzzle is solved when the board equals [[1,2,3],[4,5,0]].
Given the initial board, return the fewest moves needed to reach the solved state, or -1 if it is impossible.
Example 1:
Input: board = [[1,2,3],[4,0,5]]
Output: 1
Explanation: Swap the 0 and the 5 in one move.
Example 2:
Input: board = [[1,2,3],[5,4,0]]
Output: -1
Explanation: No number of moves will make the board solved.
Example 3:
Input: board = [[4,1,2],[5,0,3]]
Output: 5
Explanation: 5 is the smallest number of moves that solves the board.
An example path:
After move 0: [[4,1,2],[5,0,3]]
After move 1: [[4,1,2],[0,5,3]]
After move 2: [[0,1,2],[4,5,3]]
After move 3: [[1,0,2],[4,5,3]]
After move 4: [[1,2,0],[4,5,3]]
After move 5: [[1,2,3],[4,5,0]]
Code
1
2
3