956. Sliding Tiles
A pocket puzzle is a tray with 2 rows and 3 columns holding five numbered tiles 1 to 5 and one empty gap, written 0. In one move you slide a tile that touches the gap (sharing a side, up, down, left or right) into the gap, so the gap moves to where that tile was.
The puzzle is solved when board reads [[1,2,3],[4,5,0]]. Given a starting board (a 2 x 3 grid that is a permutation of 0..5), return the minimum number of moves needed to solve it, or -1 if no sequence of moves can ever reach the solved layout. A board that is already solved needs 0 moves.
Example 1
- Input:
- board = [[1,2,3],[0,4,5]]
- Output:
- 2
- Explanation:
Slide 4 into the gap, then 5 into the new gap: two moves reach the target.
Example 2
- Input:
- board = [[2,1,3],[4,5,0]]
- Output:
- -1
- Explanation:
Only tiles 1 and 2 are swapped; a lone swap changes the permutation parity, which no sequence of slides can fix, so it is unsolvable.
Example 3
- Input:
- board = [[0,1,2],[4,5,3]]
- Output:
- 3
- Explanation:
The gap slides right twice and then down once, which restores the order in three moves.
Constraints
board.length == 2andboard[i].length == 3- The six cells hold each of the values 0, 1, 2, 3, 4, 5 exactly once.
How this problem is judged
- Answers
- Your answer must match exactly. Numbers compare by value, so 2 and 2.0 are equal.
- Time per case
- Python 600 msC++ 150 msJava 300 msJavaScript 300 msTypeScript 300 ms
Expected complexity
- Time
- O(1) (at most 720 states)
- Space
- O(1)