12.2 迷宫代码实现

一、实现

1. 用循环创建二维slice

2. 使用slice来实现队列

3. 用Fscanf读取文件

4. 对Point的抽象

二、代码

package main

import (
	"fmt"
	"os"
)

// 读取文件
func readMaze(filename string) [][]int {
	// 读取文件
	file, err := os.Open(filename)
	if err != nil {
		fmt.Println(err)
		panic("文件读取失败")
	}

	// 读取内容
	var row, col int
	fmt.Fscanf(file, "%d %d", &row, &col)

	maze := make([][]int, row) // 定义类型，有几行；定义一个[]，内容是[]int
	for i := range maze {      // 遍历[][]int，定义内部的[]int长度
		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 walkByMy(maze [][]int, start point, 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:]

		// 如果到了终点，退出
		if cur == end {
			break
		}

		// 按照方向探索
		for _, dir := range dirs {
			// 下一个节点的坐标
			next := cur.add(dir)

			// 保证下一个点可通过(界限内，且不是墙)
			val, ok := next.at(maze)
			if !ok || val == 1 {
				continue
			}
            // 下个点不是外部，且没有走到过(如果走到了，就不是0，除了起点，剩下走到过的地方都不是0)
			val, ok = next.at(steps)
			if !ok || val != 0 {
				continue
			}
			// 下个点不是起点
			if next == start {
				continue
			}

			// 探索成功，记录成功的步骤
			curSteps, _ := cur.at(steps)
			steps[next.i][next.j] = curSteps + 1

			// 存入队列中
			Q = append(Q, next)
		}
	}
	return steps
}

func main() {
	// 读取文件，获取迷宫数据
	maze := readMaze("12/maze/maze.in")

	// // 输出迷宫数据，查看文件是否读取成功
	// for _, row := range maze {
	// 	for _, val := range row {
	// 		fmt.Printf("%d ", val)
	// 	}
	// 	fmt.Println()
	// }

	// 走迷宫，假如给定其实点与结束点
	steps := walkByMy(maze, point{0, 0}, point{len(maze) - 1, len(maze[0]) - 1})

	// 输出结果
	for _, row := range steps {
		for _, val := range row {
			fmt.Printf("%3d ", val) // 输出三位对齐
		}
		fmt.Println()
	}

	// TODO 输出步骤数，并且输出点位置
}