题解 | 迷宫问题

package main

import (
    "fmt"
)

type Node struct{
    x,y int
    path [][]int // 从起点到该点的路径
}

func main() {
    var h,w int 
    fmt.Scanf("%d %d", &h, &w)
    var k = make([][]int, h)
    var v = make([][]bool,h)
    for i:=0;i<h;i++{
        k[i] = make([]int, w)
        v[i] = make([]bool, w)
        for j:=0;j<w;j++{
            fmt.Scanf("%d", &k[i][j])
        }
    }

    queue := []Node{{0,0,[][]int{{0,0}}}}
    v[0][0] = true
    var dist [][]int = [][]int{{1,0}, {-1,0}, {0,-1}, {0,1}}
    for len(queue) > 0 {
        cur := queue[0]
        queue = queue[1:]
        if cur.x == h-1 && cur.y == w-1 {
            for _, d := range cur.path {
                fmt.Printf("(%d,%d)\n", d[0],d[1])
            }
            return
        }

        for _, d := range dist {
            ni, nj := cur.x + d[0], cur.y + d[1]
            if ni<0 || ni>=h || nj<0 || nj>=w || v[ni][nj] || k[ni][nj] == 1 {
                continue
            }
            v[ni][nj] = true
            // 创建新路径：复制 cur.path
            newPath := make([][]int, len(cur.path))
            copy(newPath, cur.path)
            newPath = append(newPath, []int{ni,nj})
            /* 
                注意：append(cur.path,[]int{ni,nj})是使用同一个底层数组，不是深复制
                所有path实际共用同一个底层数组，这是不正确的
             */
            queue = append(queue, Node{ni,nj, newPath})
        }
    }
}