在知乎上看到一道数学题觉得有点意思:
从数学角度想了一下,以我的数学水平肯定搞不定,为了预防自己老年痴呆,于是决定编程来解决之。
从程序员的视角来看,这就是一个搜索问题,可以使用深度优先暴力搜索。
既然要搜索就得使用一种数据结构来表示上图中的九宫格,我们会很自然的想到用一个4 X 4的二维数组来表示这个九宫格,数组的每一个元素代表九宫格中的一个点,一条直线上的4个点构成3条边。
有了这么个数组,那么数组中的每个元素记录什么数据呢?因为题目要求每条边只能走一次,所以需要记录两点之间的边是否走过,而每一点又跟上下左右的四条边相连(九宫格四周的12个点其实并没有4条边,4个角上的点只有2条边,其它8个点只有3条边,但为了代码的简洁,我们可以把这12个点也看成有4条边与其相连,只不过初始化的时候某些边就已经算做走过了),因此每个点我们又需要用一个包含4个元素的一维数组来记录其状态。如下图表示九宫格的初始状态。其中图中的数字100表示某个点的某个方向走不通因为对面是墙,而0表示可以从这个方向走到对面去。
下面是按这个思路用Go语言写成的程序,最终求得从A点走到B点一共有800种不同的走法。
package main
import (
"fmt"
)
//这个顺序主要是为了方便求反方向,比如UP(0)的反方向是3-0=3即DOWN,LEFT(2)的反方向是3-2=1即RIGHT
const (
UP = iota //0,向上走
RIGHT //1,向右走
LEFT //2,向左走
DOWN //3,向下走
)
type dir struct { //方向偏移,比如向上走:i=1,j=0;向右:i=0, j=1
i, j int
}
var dirs = [4]dir {
UP: {1, 0}, //向上走,行+1,列不变
RIGHT: {0, 1}, //向右走,行不变,列+1
LEFT: {0, -1}, //向左走,行不变,列-1
DOWN: {-1, 0}, //向下走,行-1,列不变
}
type pos struct {
i, j int
}
const wall = 100 //某个方向是墙
const walked = 1 //某个方向已经走过
//迷宫上的每一点都记录着4个方向的边是否走过,走过就不能再走了
//state数组元素的取值范围:0表示某个方向的边没有走过,walked(1)表示走过,wall(100)表示对面是墙
type posState struct {
state [4]int
}
//题目中的3 X 3的边可以看成是一个4 * 4的点组成的一个迷宫
//每个点都要记录与其相邻的边是否已经走过
type gameMap struct {
board [4][4]posState
}
var count = 0 //记录有多少种走法
func main() {
//迷宫初始化状态
var gMap = gameMap {[...][4]posState{
{{[...]int{0, 0, wall, wall}}, {[...]int{0, 0, 0, wall}}, {[...]int{0, 0, 0, wall}}, {[...]int{0, wall, 0, wall}}},
{{[...]int{0, 0, wall, 0}}, {[...]int{0, 0, 0, 0}}, {[...]int{0, 0, 0, 0}}, {[...]int{0, wall, 0, 0}}},
{{[...]int{0, 0, wall, 0}}, {[...]int{0, 0, 0, 0}}, {[...]int{0, 0, 0, 0}}, {[...]int{0, wall, 0, 0}}},
{{[...]int{wall, 0, wall, 0}}, {[...]int{wall, 0, 0, 0}}, {[...]int{wall, 0, 0, 0}}, {[...]int{wall, wall, 0, 0}}},
},}
//从(0,0)走到(3,3)
gMap.moveFromTo(pos{0,0}, pos{3,3})
fmt.Printf("found %d paths\n", count)
}
func (m *gameMap)moveFromTo(from, to pos) {
if from == to { //起点和终点位置相同,说明找到一条路径
count++
return
}
//分别尝试向 上 右 左 下 四个方向移动
for i := UP; i <= DOWN; i++ {
if m.board[from.i][from.j].state[i] == 0 {
//方向i没有走过,计算从这个方向走过去下一点的坐标
next := pos{from.i + dirs[i].i, from.j + dirs[i].j}
//标记from的i方向的边已经走过,该边对端的反方向也需要标记
m.board[from.i][from.j].state[i] = walked
m.board[next.i][next.j].state[3-i] = walked
m.moveFromTo(next, to)
//清除走过标记
m.board[from.i][from.j].state[i] = 0
m.board[next.i][next.j].state[3-i] = 0
}
}
return
}
最后,如果你觉得本文对你有帮助的话,麻烦帮忙点一下文末右下角的 在看 或转发到朋友圈,非常感谢!