题解 | #八数码#

package main

import (
	"bufio"
	. "fmt"
	"io"
	"os"
	"strconv"
)

type Ele struct {
	a    [3][3]int8
	opt  string
	xpos [2]int8
}

var (
	do = [4]string{"u", "r", "d", "l"}
	dx = [4]int8{-1, 0, 1, 0}
	dy = [4]int8{0, 1, 0, -1}
	T  = [3][3]int8{
		{1, 2, 3},
		{4, 5, 6},
		{7, 8, -1},
	}
	vis = make(map[[3][3]int8]bool)
)

func bfs(a [3][3]int8, xpos [2]int8) string {
	q := make([]Ele, 1)
	q[0] = Ele{a, "", xpos}
	for len(q) > 0 {
		top := q[0]
		q = q[1:]
		if top.a == T {
			return top.opt
		}
		vis[top.a] = true
		for i := 0; i < 4; i++ {
			nx := dx[i] + top.xpos[0]
			ny := dy[i] + top.xpos[1]
			if nx >= 0 && ny >= 0 && nx < 3 && ny < 3 {
				na := top.a
				na[top.xpos[0]][top.xpos[1]], na[nx][ny] = na[nx][ny], na[top.xpos[0]][top.xpos[1]]
				if _, ok := vis[na]; !ok {
					q = append(q, Ele{na, top.opt + do[i], [2]int8{nx, ny}})
				}
			}
		}
	}
	return ""
}
func NC51032(_r io.Reader, _w io.Writer) {
	in, out := bufio.NewReader(_r), bufio.NewWriter(_w)
	defer out.Flush()
	a := [3][3]int8{}
	xpos := [2]int8{}
	for i := 0; i < 9; i++ {
		var e string
		Fscan(in, &e)
		if e == "x" {
			e = "-1"
			xpos[0] = int8(i / 3)
			xpos[1] = int8(i % 3)
		}
		num, _ := strconv.Atoi(e)
		a[i/3][i%3] = int8(num)
	}
	Fprintln(out, bfs(a, xpos))
}

func main() {
	NC51032(os.Stdin, os.Stdout)
}