bfs.go

package main

import (
	"fmt"
	"strings"
)

type Pair struct {
	x, y int
}

// ↑→↓←
var dy [4]int = [4]int{-1, 0, 1, 0}
var dx [4]int = [4]int{0, 1, 0, -1}

func main() {
	// 入力を受け取る
	var r, c, sy, sx, gy, gx int
	fmt.Scan(&r, &c, &sy, &sx, &gy, &gx)
	stage := make([][]string, r)
	for i := 0; i < r; i++ {
		var tmp string
		fmt.Scan(&tmp)
		stage[i] = strings.Split(tmp, "")
	}

	// Queue
	que := make([]Pair, 0)
	que = append(que, Pair{x: sx - 1, y: sy - 1})

	// 最短路を記録する配列
	var dist [49][49]int // R(1≦R≦50), C(1≦C≦50)

	// BFS
	for len(que) > 0 {
		// Queueからひとつ取り出す
		point := que[0]
		que = que[1:]

		for i := 0; i < 4; i++ {
			nx, ny := point.x+dx[i], point.y+dy[i]

			// nx, nyがマイナス値など想定しない数値になった時、
			// または次の場所が壁か探索済みの時はスキップ
			if (nx < 0 && c <= nx && ny < 0 && r <= ny) ||
				(stage[ny][nx] == "#" || dist[ny][nx] != 0) {
				continue
			}

			que = append(que, Pair{x: nx, y: ny})
			dist[ny][nx] = dist[point.y][point.x] + 1
		}
	}

	// 結果を出力
	fmt.Println(dist[gy-1][gx-1])
}