问题：
在一个 2 x 3 的板上（board）有 5 块砖瓦，用数字 1~5 来表示, 以及一块空缺用 0 来表示。一次移动定义为选择 0 与一个相邻的数字（上下左右）进行交换.
最终当板 board 的结果是 [[1,2,3],[4,5,0]] 谜板被解开。
给出一个谜板的初始状态 board ，返回最少可以通过多少次移动解开谜板，如果不能解开谜板，则返回 -1 。
示例 1
输入：board = [[1,2,3],[4,0,5]]
输出：1
解释：交换 0 和 5 ，1 步完成
示例 2
输入：board = [[1,2,3],[5,4,0]]
输出：-1
解释：没有办法完成谜板
示例 3
输入：board = [[4,1,2],[5,0,3]]
输出：5
解释：
最少完成谜板的最少移动次数是 5 ，
一种移动路径:
尚未移动: [[4,1,2],[5,0,3]]
移动 1 次: [[4,1,2],[0,5,3]]
移动 2 次: [[0,1,2],[4,5,3]]
移动 3 次: [[1,0,2],[4,5,3]]
移动 4 次: [[1,2,0],[4,5,3]]
移动 5 次: [[1,2,3],[4,5,0]]
提示
- board.length == 2
- board[i].length == 3
- 0 <= board[i][j] <= 5
- board[i][j] 中每个值都 不同
题解：
package main
/*
* @lc app=leetcode.cn id=773 lang=golang
*
* [773] 滑动谜题
*/
// @lc code=start
func slidingPuzzle(board [][]int) int {
var b [2][3]int
for i, v := range board {
for j, v1 := range v {
b[i][j] = v1
}
}
type item struct {
value [2][3]int
step int
str string
}
var tostr = func(arr [2][3]int) string {
var res []byte
for _, v := range arr {
for _, v1 := range v {
res = append(res, byte(v1+'0'))
}
}
return string(res)
}
queue := make([]item, 0)
queue = append(queue, item{
b,
0,
tostr(b),
})
sead := make(map[string]bool)
var addSead = func(arr [2][3]int) {
str := tostr(arr)
if !sead[str] {
sead[str] = true
}
}
for len(queue) > 0 {
b := queue[0]
if b.str == "123450" {
return b.step
}
addSead(b.value)
queue = queue[1:]
zeroX := 0
zeroY := 0
for i, v := range b.value {
for j, v1 := range v {
if v1 == 0 {
zeroX = i
zeroY = j
break
}
}
}
if zeroX == 0 {
//0向下移
c := b.value
t := c[zeroX+1][zeroY]
c[zeroX+1][zeroY] = 0
c[zeroX][zeroY] = t
str := tostr(c)
if str == "123450" {
return b.step + 1
}
if !sead[str] {
queue = append(queue, item{
c,
b.step + 1,
str,
})
}
} else {
//向上移
c := b.value
t := c[zeroX-1][zeroY]
c[zeroX-1][zeroY] = 0
c[zeroX][zeroY] = t
str := tostr(c)
if str == "123450" {
return b.step + 1
}
if !sead[str] {
queue = append(queue, item{
c,
b.step + 1,
str,
})
}
}
//向左
if zeroY > 0 {
c := b.value
t := c[zeroX][zeroY-1]
c[zeroX][zeroY-1] = 0
c[zeroX][zeroY] = t
str := tostr(c)
if str == "123450" {
return b.step + 1
}
if !sead[str] {
queue = append(queue, item{
c,
b.step + 1,
str,
})
}
}
//向右
if zeroY < 2 {
c := b.value
t := c[zeroX][zeroY+1]
c[zeroX][zeroY+1] = 0
c[zeroX][zeroY] = t
str := tostr(c)
if str == "123450" {
return b.step + 1
}
if !sead[str] {
queue = append(queue, item{
c,
b.step + 1,
str,
})
}
}
}
return -1
}
// @lc code=end
成绩：
- 32⁄32 cases passed (0 ms)
- Your runtime beats 100 % of golang submissions
- Your memory usage beats 13.64 % of golang submissions (4.5 MB)
「真诚赞赏，手留余香」
Maolong’s Blog
真诚赞赏，手留余香
使用微信扫描二维码完成支付
