AcWing 844. 走迷宫--Golang
原题链接
简单
作者:
迷弟
,
2024-07-25 15:28:36
,
所有人可见
,
阅读 6
package main
import(
"fmt"
"bufio"
"os"
)
type PII struct{
first int
second int
}
func main(){
var reader = bufio.NewReader(os.Stdin)
var n,m int
fmt.Fscan(reader, &n, &m)
//fmt.Println(n)
g := make([][]int, n)
for i := range g {
g[i] = make([]int, m)
}
for i := 0; i < n; i++{
for j := 0; j <m; j++{
fmt.Fscan(reader, &g[i][j])
}
}
dx := [4]int{-1, 0, 1, 0}
dy := [4]int{0, 1, 0, -1}
head := 0
tail := 0
q := make([]PII, (n+2)*(n+2))
q[0]= PII{0,0}
d := make([][]int, n) //distance距离起点距离
for i := range d{
d[i] = make([]int, m)
for j := range d[i]{
d[i][j] = -1
}
}
d[0][0]=0
var bfs func(g [][]int) int
bfs = func(g [][]int) int{
for head <=tail {
t := q[head]
head ++
for i := 0; i < 4; i++{
x := t.first + dx[i]
y := t.second + dy[i]
if x >=0 && x < n && y >= 0 && y < m && d[x][y] == -1 && g[x][y] == 0{
d[x][y] = d[t.first][t.second] + 1
tail ++
q[tail] = PII{x, y}
}
}
}
return d[n - 1][m - 1]
}
//result := bfs(g)
fmt.Println(bfs(g))
}