zihuyishi
231 天前
我写了一个深搜，算的 13 步能跑完，不知道对不对
```golang
package main
import "fmt"
const N = 5
type Status [N][N]bool
func (s Status) Click(x, y int) Status {
s[x][y] = !s[x][y]
if x > 0 {
s[x-1][y] = !s[x-1][y]
}
if x < N-1 {
s[x+1][y] = !s[x+1][y]
}
if y > 0 {
s[x][y-1] = !s[x][y-1]
}
if y < N-1 {
s[x][y+1] = !s[x][y+1]
}
return s
}
func (s Status) IsAllOn() bool {
for i := 0; i < N; i++ {
for j := 0; j < N; j++ {
if !s[i][j] {
return false
}
}
}
return true
}
func (s Status) Hash() int64 {
h := int64(0)
for i := 0; i < N; i++ {
for j := 0; j < N; j++ {
h = h * 2
if s[i][j] {
h += 1
}
}
}
return h
}
type Node struct {
Status Status
Step int
}
func search(s Status) (int, bool) {
searched := make(map[int64]bool)
queue := make([]Node, 0)
queue = append(queue, Node{Status: s, Step: 0})
searched[s.Hash()] = true
for len(queue) > 0 {
cur := queue[0]
queue = queue[1:]
if cur.Status.IsAllOn() {
return cur.Step, true
}
for i := 0; i < N; i++ {
for j := 0; j < N; j++ {
next := cur.Status.Click(i, j)
if next.IsAllOn() {
return cur.Step + 1, true
}
if !searched[next.Hash()] {
queue = append(queue, Node{Status: next, Step: cur.Step + 1})
searched[next.Hash()] = true
}
}
}
}
return 0, false
}
func main() {
s := Status{
{false, true, false, false, false},
{true, true, true, false, false},
{false, true, false, true, false},
{false, false, true, true, true},
{false, false, false, true, false},
}
step, ok := search(s)
fmt.Println(step, ok)
}
```