0773. Sliding Puzzle

题目信息

题号:

0773

难度:

Hard

主题:

矩阵、状态变换、最少移动次数

原题:

LeetCode 0773

重点:

棋盘固定为 2 x 3,数字 0 表示空格;每次只能让空格与四方向相邻数字交换,目标状态固定,返回最少移动次数或 -1

题目重述

给定一个 2 x 3 棋盘,里面恰好放有数字 0 至 5,且每个数字只出现一次。数字 0 表示空格,其余数字表示方块。

一次移动只能选择与空格在上、下、左、右方向相邻的一个方块,并让它与空格交换位置。棋盘的目标状态是 [[1,2,3],[4,5,0]]。

请返回从输入状态变为目标状态所需的最少移动次数;若无论怎样移动都无法到达目标状态,返回 -1。

自建示例

两步到达目标:

输入:board = [[1,0,3],[4,2,5]]
输出:2
解释:先交换空格与下方的 2,得到 [[1,2,3],[4,0,5]];再交换空格与右侧的 5,即到达目标状态。

初始状态已经是目标状态:

输入:board = [[1,2,3],[4,5,0]]
输出:0
解释:输入棋盘与规定的目标状态完全相同,不需要执行任何移动,因此最少移动次数为 0。