package main import ( "fmt" "os" ) func createMaze(filename string) [][]int { file, err := os.Open(filename) if err != nil { fmt.Println("文件打开错误", err) } // 读取文件第一行 var row, col int fmt.Fscanf(file, "%d %d", &row, &col) //读取文件第一行 maze := make([][]int, row) for i:= range maze { maze[i] = make([]int, col) for j := range maze[i] { fmt.Fscanf(file, "%d", &maze[i][j]) } } return maze } 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} } 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 walk(maze [][]int, start, end point) [][] int { // 创建一个step (走过的路) steps := make([][]int, len(maze)) for i := range steps { steps[i] = make([]int, len(maze[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) // 碰见1不行 (1 代表墙) val, ok := next.at(maze) if !ok || val == 1 { continue } // 在steps中走过了 val, ok = next.at(steps) if !ok || val != 0 { continue } //走回start了 if next == start { continue } at, _ := cur.at(steps) steps[next.i][next.j] = at + 1 queue = append(queue, next) } } return steps } func main() { maze := createMaze("maze/maze.in") steps := walk(maze, point{0, 0}, point{len(maze) - 1, len(maze[0]) - 1}) for _, i := range steps { for _, j := range i { fmt.Printf("%2d ", j) } fmt.Println() } }
6 5 //6行5列
0 1 0 0 0
0 0 0 1 0
0 1 0 1 0
1 1 1 0 0
0 1 0 0 1
0 1 0 0 0
其中1代表路不通,无法通行
程序运行结果如下:
标签:point,int,迷宫,len,queue,steps,搜索,Go,maze From: https://www.cnblogs.com/xiaowenwen/p/17132674.html