编程求解一道数学难题

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
}