迷宫,只可以上下左右走，要求从左上角到右下角到最短路径

6 6
0 1 0 0 1 0
0 0 0 1 0 0
0 1 0 0 0 0
0 1 1 0 1 0
1 0 0 0 0 1
1 1 0 0 0 0

解题思路

1. 获取迷宫图，由左到右 由上到下标点(如：[0,0])
2. 从入口点开始走一步（上下左右），列出所有可能的下一步 加入队列，并在迷宫图上标记
3. 一直走，知道走到当前点等于结束点

go语言解法

package main
import (
    "fmt"
    "os"
)

// 获取迷宫图
func readBfs(filename string) [][]int {
    file, err := os.Open(filename)
    if err != nil {
        panic(err)
    }
    var row, col int
    fmt.Fscanf(file,"%d %d",&row, &col) //读取前两个数字，赋值给row col
    bfs := make([][]int,row) // 6行
    for i := range bfs {
        bfs[i] = make([]int,col) //6列
        for j := range bfs[i] {
            fmt.Fscanf(file, "%d", &bfs[i][j])
        }
    }
    return bfs
}


// 定义点的结构 (当前点，下一点)
type point struct {
    i, j int
}

// 定义上左下右四步
var dirs = [4]point {
    {-1,0}, {0,-1},{1,0},{0,1}
}

// 点移动到下一点到位置
func (p point) add(r point) point {
    return point{p.i+r.i,p.j+r.j}
}

// 判断点是否在迷宫途中,在就返回迷宫图对应到点值，不再返回false
func (p point) at(grid [][]int) {int, bool} {
    if p.i < 0 || p.i >= len(gird) {
        return 0,false
    }
    if p.j < 0 || p.j >= len(grid[p.i]) {
        return 0,false
    }
    return grid[p.i][p.j],true
}

// 返回走过的步骤图
func walk(bfs [][]int, start, end point) [][]int {
    steps := make([][]int, len(bfs))
    for i := range bfs {
        steps[i] = make([]int, len(bfs[i]))
    }
    queue := []point{start} //入口加入队列

    for len(queue) > 0 {
        cur := queue[0]
        queue = queue[1:]
        if cur == end { //走到出口
            break
        }
        for _,dir := range dirs {
            next := cur.add(dir)
            val, ok := next.at(bfs)
            if !ok || val == 1 {
                continue
            }
            if next == start {
                continue
            }
            curStep, _ := cur.at(steps)
            steps[next.i][next.j] = curStep + 1
            queue = append(queue, next)
        }
    }
    return steps
}


func main() {
    bfs := readBfs("bfs/bfs.ini")
    steps := walk(bfs, point{0,0},point{len(bfs)-1,len(bfs[0])-1})
    for _, row := range steps {
        fmt.Println(row)
    }
}

心得，回溯法强于穷举法。回溯法需要队列配合，符合条件的加入队列