题解 | #迷宫问题#

package main

import (
	"fmt"
)

func main() {
	// m行 n列
	var m, n int
	fmt.Scan(&m, &n)
	vals := make([][]int, m)
	for i := range vals {
		vals[i] = make([]int, n)
		for j := range vals[i] {
			fmt.Scan(&vals[i][j])
		}
	}
	// 最短路径，广搜即可
	queue := []*MyPoint{{
		x: 0, y: 0,
	}}
	// 记忆化
	visited := make(map[struct{ x, y int }]struct{}, 0)
	for len(queue) > 0 {
		p := queue[0]
		queue = queue[1:]
		// 越界判断
		if p.x < 0 || p.x >= m || p.y < 0 || p.y >= n {
			continue
		}
		if _, exist := visited[struct {
			x int
			y int
		}{
			p.x, p.y,
		}]; exist {
			continue
		}
		visited[struct {
			x int
			y int
		}{
			p.x, p.y,
		}] = struct{}{}
		// 墙判断
		if vals[p.x][p.y] == 1 {
			continue
		}
		// 判断是否到达
		if p.x == m-1 && p.y == n-1 {
			// 到达了，从当前结点遍历至初始结点
			link := make([]*MyPoint, 0)
			for p != nil {
				link = append(link, p)
				p = p.parent
			}
			// 逆序打印
			for i := len(link) - 1; i >= 0; i-- {
				fmt.Printf("(%d,%d)\n", link[i].x, link[i].y)
			}
			return
		}
		// 上
		queue = append(queue, &MyPoint{
			x: p.x, y: p.y - 1, parent: p,
		})
		// 下
		queue = append(queue, &MyPoint{
			x: p.x, y: p.y + 1, parent: p,
		})
		// 左
		queue = append(queue, &MyPoint{
			x: p.x - 1, y: p.y, parent: p,
		})
		// 右
		queue = append(queue, &MyPoint{
			x: p.x + 1, y: p.y, parent: p,
		})
	}
}

type MyPoint struct {
	x, y   int
	parent *MyPoint
}