0773. Sliding Puzzle¶
题目信息¶
- 题号:
0773
- 难度:
Hard
- 主题:
矩阵、状态变换、最少移动次数
- 原题:
- 重点:
棋盘固定为
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。