实现结果

结果.png

迷宫地图文件

第一行为行列标识此迷宫为6行5列
1为墙 0为路

思路

从起点开始，朝四个方向探索，每个方向只探索一格，如果那一格合法（未走过且未越界）则记录从起点到达这个点所需步数并加入探索队列，探索完四个方向后从探索队列中取一个出来继续探索，以此类推，直到找到终点。探索完毕后将会得到一个新的地图，地图中记录了所有可到达区域，并标识了到达指定点所需步数。

func work(maze [][]int, start, end point) [][]int {
    // 记录一下可以走的地方
    steps := make([][]int, len(maze))

    for i := range steps{
        steps[i] = make([]int, len(maze[i]))
    }

    // 从起点开始走
    queue := []point{start}

    // 开始探索
    for len(queue) > 0 {
        // 取出当前走的坐标
        current := queue[0]
        queue = queue[1:]

        if current == end {
            break
        }

        // 探索各个方向
        for _, dir := range dirs{
            next := current.add(dir)
            val, ok := next.at(maze)

            // 越界或碰到墙则跳过
            if !ok || val == 1 {
                continue
            }

            val, ok = next.at(steps)

            // 走过了或者回到起点了跳过
            if !ok || val != 0 || next == start {
                continue
            }

            currentStep, _ := current.at(steps)
            // 记录一下多少步能到这
            steps[next.i][next.j] = currentStep + 1

            // 加入探索队列
            queue = append(queue, next)
        }
    }

    return steps
}

根据新的地图从终点开始逆向探索，得出无重复路程的路线

// 从终点开始逆向查找
	curr := end
	currStep, _ := curr.at(steps)
	route := []point{curr}
	for curr != start {
		for _, dir := range dirs{
			next := curr.add(dir)
			step, ok := next.at(steps)

			// 越界或不是当前这一步的上一步  跳过
			if !ok || step != currStep - 1 {
				continue
			}

			// 可以继续往下走
			currStep = step
			route = append(route, next)
			curr = next
			break
		}
	}

	// 打印路线坐标
	for i := len(route) - 1; i >= 0 ; i-- {
		fmt.Printf("%v ", route[i])
	}

完整代码

package main

import (
	"os"
	"fmt"
)

type point struct {
	i, j int
}

// 移动一步
func (p point) add(dir point) point {
	return point{p.i + dir.i, p.j + dir.j}
}

// 当前点校验
func (p point) at(grid [][]int) (int, bool) {
	// 越界
	if p.i < 0 || p.j < 0 || p.i >= len(grid) || p.j >= len(grid[p.i]) {
		return 0, false
	}

	// 返回从起点到这个点需要走多少步， 未记录的则返回0
	return grid[p.i][p.j], true
}

// 实现 Stringer 接口 格式化输出
func (p point) String() string {
	return fmt.Sprintf("(%d,%d)", p.i, p.j)
}

var dirs = [4]point{
	{-1, 0},	// 上移
	{0, -1},	// 左移
	{1, 0},	// 下移
	{0, 1},	// 右移
}

// read maze
func readMaze(filename string) (maze [][]int) {
	var row, col int
	file, err := os.Open(filename)

	if err != nil {
		panic(err)
	}

	_, err = fmt.Fscanf(file, "%d %d", &row, &col)

	if err != nil {
		panic(err)
	}

	maze = make([][]int, row)
	for i := range maze{
		maze[i] = make([]int, col)
		fmt.Fscanf(file, "%d")
		for j := range maze[i] {
			fmt.Fscanf(file, "%d", &maze[i][j])
		}
	}

	return maze
}

func work(maze [][]int, start, end point) [][]int {
	// 记录一下可以走的地方
	steps := make([][]int, len(maze))

	for i := range steps{
		steps[i] = make([]int, len(maze[i]))
	}

	// 从起点开始走
	queue := []point{start}

	// 开始探索
	for len(queue) > 0 {
		// 取出当前走的坐标
		current := queue[0]
		queue = queue[1:]

		if current == end {
			break
		}

		// 探索各个方向
		for _, dir := range dirs{
			next := current.add(dir)
			val, ok := next.at(maze)

			// 越界或碰到墙则跳过
			if !ok || val == 1 {
				continue
			}

			val, ok = next.at(steps)

			// 走过了或者回到起点了跳过
			if !ok || val != 0 || next == start {
				continue
			}

			currentStep, _ := current.at(steps)
			// 记录一下多少步能到这
			steps[next.i][next.j] = currentStep + 1

			// 加入探索队列
			queue = append(queue, next)
		}
	}

	return steps
}

func main()  {
	// 读取迷宫地图
	maze := readMaze("maze.map")
	start, end := point{0, 0}, point{len(maze) - 1, len(maze[0]) - 1}

	// 打印一下
	for _, row := range maze {
		for _, val := range row {
			fmt.Printf("%d ", val)
		}
		fmt.Println()
	}

	fmt.Println("----------------------------------------")

	// 开始计算，传入地图、起点、终点
	// steps 标识了迷宫中所有可以去的坐标，以及去对应坐标所需步数
	steps := work(maze, start, end)

	for _, row := range steps {
		for _, val := range row {
			fmt.Printf("%3d ", val)
		}
		fmt.Println()
	}

	fmt.Println("----------------------------------------")

	// 从终点开始逆向查找
	curr := end
	currStep, _ := curr.at(steps)
	route := []point{curr}
	for curr != start {
		for _, dir := range dirs{
			next := curr.add(dir)
			step, ok := next.at(steps)

			// 越界或不是当前这一步的上一步  跳过
			if !ok || step != currStep - 1 {
				continue
			}

			// 可以继续往下走
			currStep = step
			route = append(route, next)
			curr = next
			break
		}
	}

	// 打印路线坐标
	for i := len(route) - 1; i >= 0 ; i-- {
		fmt.Printf("%v ", route[i])
	}
}

广度优先算法走迷宫

分类