走迷宫-BFS-golang

golang

package main
import (
    "fmt"
    "bufio"
    "os"
    "strings"
    "strconv"
    )

var n, m int   //n行, m列
var g [][]int   //地图
var d [][]int  //地图上每个点到启点距离

var q []pair

//当前队列中位置
type pair struct{
    first int
    second int
}

func main(){
    fmt.Scanf("%d%d", &n, &m)
    g, d = make([][]int, n), make([][]int, n)
    scan := bufio.NewScanner(os.Stdin)
    //初始化
    for i := 0; i < n; i++{
        scan.Scan()
        data := strings.Split(scan.Text(), " ")
        g[i], d[i] = make([]int, m), make([]int, m)
        for j := 0; j < m; j++{
            num, _ := strconv.Atoi(data[j])
            g[i][j] = num
            d[i][j] = -1
        }
    }
    d[0][0] = 0
    fmt.Println(bfs())

}

func bfs()int{
    q := make([]pair, 0)
    //起点
    q = append(q, pair{0, 0})

    dx := []int{-1, 0, 1, 0} // 向量表示向上或向下
    dy := []int{0, 1, 0, -1} // 向量表示向左或向右

    for len(q) > 0{
        t := q[0]
        q = q[1:]
        a, b := t.first, t.second
        for i := 0; i < 4; i++{
            lx := a + dx[i]
            ly := b + dy[i]
            if lx >= 0 && lx < n && ly >= 0 && ly < m && d[lx][ly] == -1 && g[lx][ly] == 0{
                d[lx][ly] = d[a][b] + 1
                q = append(q, pair{lx, ly})
            }
        }
    }
    return d[n-1][m-1]
}