题目描述

/*
在一个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
*/

样例

blablabla

go 实现

package main

import (
    "bufio"
    "fmt"
    "os"
    "strings"
    "time"
)

func readLine(r *bufio.Reader) string {
    s, _ := r.ReadString('\n')
    sSlice := strings.Fields(s)
    //res := make([]string, len(sSlice))
    var res string
    for _, k := range sSlice {
        res += k

    }
    return res
}
func dfs(start string) int {
    // end表示最终的结果样式
    end := "12345678x"
    // 模版第一步：创建队列
    q := make([]string, 0)
    // 创建map存放步数
    d := make(map[string]int)

    // 头部放入
    q = append(q, start)
    d[start] = 0
    // 定义交换的方向
    dx := []int{-1, 0, 1, 0} //向上向下
    dy := []int{0, -1, 0, 1} // 向左向右
    // 第二步骤：循环队列
    for len(q) > 0 {
        //拓展头部元素
        tt := q[0]
        q = q[1:]
        distance := d[tt]
        if tt == end {
            return distance
        }
        // 状态转移
        k := strings.Index(tt, "x") //找出字符串x在一维中的索引
        //将字符串x转化为2维中的索引
        x, y := k/3, k%3 // 将一维转化为二维
        //判断满足条件的点位移动
        for i := 0; i < 4; i++ {
            a, b := x+dx[i], y+dy[i]
            //判断是否在3X3的范围内
            if a >= 0 && a < 3 && b >= 0 && b < 3 {
                // 交换x的位置
                //swap(tt[k],tt[3*a+b])
                tt = swap(tt, k, 3*a+b)
                //tt[k] = tt[3*a+b]
                // 判断新的状态是否是第一次出现
                //if !d.count(tt){ // go中没有此API
                if d[tt] == 0 {
                    d[tt] = distance + 1
                    q = append(q, tt)
                }
                //恢复状态
                //swap(tt[k],tt[3*a+b])
                tt = swap(tt, k, 3*a+b)

            }
        }
    }
    return -1
}
func swap(s string, a, b int) string {
    t := []rune(s)
    t[a], t[b] = t[b], t[a]
    var ss string
    ss = string(t)
    return ss
}
func main() {
t :=time.Now()
    r := bufio.NewReader(os.Stdin)
    strat := readLine(r)
    fmt.Println(dfs(strat))
    e :=time.Since(t)
    fmt.Println(e)

}