072 - Loop Railway Plan（★4）
キーワード
解説
制約
より, 全ての経路を全探索が可能.
バックトラック法を用いる.
再帰関数dfsを実装する.
if y == py && x == px && visited[py][px] {
return 0
}の部分は, 初期値に戻ってきた場合の処理.
提出コード
func max(a, b int) int {
if a > b {
return a
}
return b
}
func main() {
var H, W int
scanIntVariables(&H, &W)
G := make([][]string, H)
for y := 0; y < H; y++ {
C := readString()
for j := 0; j < W; j++ {
G[y] = append(G[y], string(C[j]))
}
}
visited := make([][]bool, H)
for h := 0; h < H; h++ {
visited[h] = make([]bool, W)
}
var dfs func(y, x, py, px int) int
dfs = func(y, x, py, px int) int {
if y == py && x == px && visited[py][px] {
return 0
}
visited[py][px] = true
ret := math.MinInt
for _, d := range [][]int{{1, 0}, {-1, 0}, {0, 1}, {0, -1}} {
ny, nx := py+d[0], px+d[1]
if ny < 0 || ny >= H || nx < 0 || nx >= W {
continue
}
if G[ny][nx] == "#" {
continue
}
if (y != ny || x != nx) && visited[ny][nx] {
continue
}
v := dfs(y, x, ny, nx)
ret = max(ret, v+1)
}
visited[py][px] = false
return ret
}
ans := 0
for h := 0; h < H; h++ {
for w := 0; w < W; w++ {
ans = max(ans, dfs(h, w, h, w))
}
}
if ans <= 2 {
ans = -1
}
writeLine(ans)
}