题目描述
在一个 3×3 的网格中,1∼8 这 8 个数字和一个 x 恰好不重不漏地分布在这 3×3 的网格中。
例如:
1 2 3
x 4 6
7 5 8
在游戏过程中,可以把 x 与其上、下、左、右四个方向之一的数字交换(如果存在)。
我们的目的是通过交换,使得网格变为如下排列(称为正确排列):
1 2 3
4 5 6
7 8 x
例如,示例中图形就可以通过让 x 先后与右、下、右三个方向的数字交换成功得到正确排列。
交换过程如下:
1 2 3 1 2 3 1 2 3 1 2 3
x 4 6 4 x 6 4 5 6 4 5 6
7 5 8 7 5 8 7 x 8 7 8 x
现在,给你一个初始网格,请你求出得到正确排列至少需要进行多少次交换。
输入格式
输入占一行,将 3×3 的初始网格描绘出来。
例如,如果初始网格如下所示:
1 2 3
x 4 6
7 5 8
则输入为:1 2 3 x 4 6 7 5 8
输出格式
输出占一行,包含一个整数,表示最少交换次数。
如果不存在解决方案,则输出 −1。
样例
输入样例:
2 3 4 1 5 x 7 6 8
输出样例
19
Go 代码
package main
import (
"fmt"
"strings"
"bufio"
"os"
)
const N = 362880 // 直接9!太暴力了...
var q = [N]string{}
var h = map[string]int{}
var dx = [4]int{-1, 0, 1, 0}
var dy = [4]int{0, -1, 0, 1}
func find(s string) int {
for i := 0; i < 9; i ++ {
if s[i] == 'x' {
return i
}
}
return 0
}
func bfs(s string) int {
hh, tt := 0, 0
end := "12345678x"
h[s] = 0
q[0] = s
for hh <= tt {
t := q[hh]
hh ++
dist := h[t]
if t == end {
return dist
}
k := find(t)
x, y := k / 3, k % 3
for i := 0; i < 4; i ++ {
a, b := x + dx[i], y + dy[i]
if a >= 0 && a < 3 && b >= 0 && b < 3 {
temp := []byte(t)
temp[k], temp[a * 3 + b] = temp[a * 3 + b], temp[k]
if _, ok := h[string(temp)]; !ok {
h[string(temp)] = dist + 1
tt ++
q[tt] = string(temp)
}
temp[k], temp[a * 3 + b] = temp[a * 3 + b], temp[k]
t = string(temp)
}
}
}
return -1
}
func main(){
reader := bufio.NewReader(os.Stdin)
text, _ := reader.ReadString('\n')
text = strings.Replace(text, "\n", "", -1)
text = strings.Replace(text, " ", "", -1)
fmt.Println(bfs(text))
}