从 0 开始按上左下右的顺序一层一层往外探索
代码实现
package main
import (
"fmt"
"os"
)
// ReadMaze 读取迷宫
func ReadMaze(filename string) [][]int {
var row, col int // 行,列
file, err := os.Open(filename) // 打开文件
if err != nil {
panic(err)
}
defer file.Close()
// 读取文件头部获取行列 6行5列
fmt.Fscanf(file, "%d %d", &row, &col)
// 为每行创建空间
maze := make([][]int, row)
for i := range maze {
// 为列创建空间
maze[i] = make([]int, col)
fmt.Fscanf(file, "%v") // 把每行最后的 \n 读取出来,避免数据错误
// 将每列的数据读取到 slice中
for j := range maze[i] {
fmt.Fscanf(file, "%d", &maze[i][j])
}
}
return maze
}
// 点结构体 用于存放点为
type point struct {
// i 行; j 列
i, j int
}
var directions = [4]point{
// 上左下右的顺序
{-1, 0},
{0, -1},
{1, 0},
{0, 1},
}
// 两个point 相加
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) {
// 判断 point 点是否越界,是否走出了 grid 之外
// 判断 行是否越界
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
}
// Walk
// start 从那个点开始
// end 到那个点结束
func Walk(maze [][]int, start, end point) [][]int {
// 维护一个和 maze 一样大小的 slice 存放走过的路径
steps := make([][]int, len(maze))
for i := range steps {
steps[i] = make([]int, len(maze[i]))
}
queue := []point{start} // 将起点放入队列里
// 当队列为空时退出
for len(queue) > 0 {
// pop 队列中第一个元素
current := queue[0]
queue = queue[1:]
if current == end { // 发现终点-结束
break
}
for _, dir := range directions { // 按上左下右的顺序查找
next := dir.add(current) // 新点的点位
// 走迷宫 越界的,或者遇到 1 (撞墙)
at, ok := next.at(maze)
if !ok || at == 1 {
continue
}
// 如果 steps 不等于 0 则说明走过了
at, ok = next.at(steps)
if !ok || at != 0 {
continue
}
// 新的点不能是start(回到原点)
if next == start {
continue
}
// 使用新点去探索 steps 获取走的步骤数
curStep, _ := current.at(steps)
steps[next.i][next.j] = curStep + 1
// 将当前探索到的点 加入队列中
queue = append(queue, next)
}
}
return steps
}
func main() {
// 读取迷宫文本
maze := ReadMaze("maze/maze.in")
// 设置迷宫开始位置和结束位置
steps := Walk(maze, point{0, 0}, point{len(maze) - 1, len(maze[0]) - 1})
for _, row := range steps {
for _, col := range row {
fmt.Printf("%3d", col)
}
fmt.Println()
}
}