673. Sliding Puzzle — Minimum Moves

On a 2x3 board the tiles 1-5 and a blank (0) can slide: a move swaps the blank with an adjacent tile. Given the start board, return the least number of moves to reach the solved state [[1,2,3],[4,5,0]], or -1 if unsolvable. The input is JSON {board}.

Input: JSON {board}.

Output: Integer — the minimum moves, or -1.

Examples

Input: {"board":[[1,2,3],[4,0,5]]}
Output: 1
Explanation: One slide solves it.

Input: {"board":[[1,2,3],[5,4,0]]}
Output: -1
Explanation: Unsolvable configuration.

Input: {"board":[[4,1,2],[5,0,3]]}
Output: 5
Explanation: Five moves.

Constraints

• board is 2x3
• values 0-5

Asked by