golang 实现广度优先算法(走迷宫)

概述maze.go package mainimport ( "fmt" "os")/** * 广度优先算法 *//** * 从文件中读取数据 */func readMaze(filename string) [][]int { file, err := os.Open(filename) if err != ni

maze.go

package mainimport (    "fmt"    "os")/** * 广度优先算法 *//** * 从文件中读取数据 */func readMaze(filename string) [][]int {    file,err := os.Open(filename)    if err != nil {        panic(err)    }    var cols,rows int    fmt.Fscanf(file,"%d %d",&rows,&cols)    maze := make([][]int,rows)    for i := range maze {        maze[i] = make([]int,cols)        for j := range maze[i] {            fmt.Fscanf(file,"%d",&maze[i][j])        }    }    return maze}/** * 定义要走的节点下标 */type point struct {    i,j int}/** * 定义,四个方向,上左下右 */var dirs = [4]point{point{-1,0},point{0,-1},point{1,1},}//走的节点//走迷宫/** * maze 迷宫地址 * strt 开始位置 * end 走出迷宫位置 */func walk(maze [][]int,start,end point) [][]int {    steps := make([][]int,len(maze))    for i := range steps {        steps[i] = make([]int,len(maze[i]))    }    Q := []point{start}    for len(Q) > 0 {        cur := Q[0] //取一个第一个位置        Q = Q[1:]        //fmt.Printf("Q=%v ",Q)        //发现终点就退出        if cur == end {            break        }        for _,dir := range dirs { //开始进行 上 左 下 右 的行走路线            next := cur.add(dir) //拿到下个节点的值            //撞墙检测            val,ok := next.at(maze)            if !ok || val == 1 {                continue            }            //检测是否走过了            val,ok = next.at(steps)            if !ok || val != 0 {                continue            }            //检测是否回到原点了不能探索            if next == start {                continue            }            //开始探索,将值存入 steps            curStep,_ := cur.at(steps)            steps[next.i][next.j] = curStep + 1            Q = append(Q,next)        }    }    return steps}func (p point) at(grID [][]int) (int,bool) {    //往上越界,往下越界    if p.i < 0 || p.i >= len(grID) {        return 0,false    }    if p.j < 0 || p.j >= len(grID[p.i]) {        return 0,false    }    return grID[p.i][p.j],true}// 添加节点func (p point) add(r point) point {    return point{p.i + r.i,p.j + r.j}}func main() {    maze := readMaze("maze.in") //读取地图数据    steps := walk(maze,point{len(maze) - 1,len(maze[0]) - 1})    for _,rows := range steps {        for _,val := range rows {            fmt.Printf("%3d ",val)        }        fmt.Println()    }}

 

maze.in

6 50 1 0 0 00 0 0 1 00 1 0 1 01 1 1 0 00 1 0 0 10 1 0 0 0

总结

以上是内存溢出为你收集整理的golang 实现广度优先算法(走迷宫)全部内容，希望文章能够帮你解决golang 实现广度优先算法(走迷宫)所遇到的程序开发问题。

如果觉得内存溢出网站内容还不错，欢迎将内存溢出网站推荐给程序员好友。