結果

問題 No.3504 Insert Maze
コンテスト
ユーザー ID 21712
提出日時 2026-04-18 22:02:30
言語 Go
(1.26.1)
コンパイル:
env GOCACHE=/tmp go build _filename_
実行:
./Main
結果
AC  
実行時間 634 ms / 2,000 ms
コード長 2,390 bytes
記録
記録タグの例:
初AC ショートコード 純ショートコード 純主流ショートコード 最速実行時間
コンパイル時間 14,149 ms
コンパイル使用メモリ 274,772 KB
実行使用メモリ 140,620 KB
最終ジャッジ日時 2026-04-18 22:03:06
合計ジャッジ時間 30,891 ms
ジャッジサーバーID
（参考情報） 		judge3_1 / judge2_0
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 85
権限があれば一括ダウンロードができます

ソースコード

diff #
raw source code 

package main

import . "fmt"
import . "os"
import bf "bufio"

func main() {
	rd := bf.NewReader(Stdin)
	var h,w int
	Fscan(rd,&h,&w)
	field := make([]string, h)
	for i := range field {
		Fscan(rd,&field[i])
	}
	
	ans := solve(h, w, field)
	
	Println(ans)
}
	
func solve(h, w int, field []string) int {
	ans := h+w
	
	dist1 := make([][]int, h)
	dist2 := make([][]int, h)
	for i := range field {
		dist1[i] = make([]int, w)
		dist2[i] = make([]int, w)
	}
	mv := []*P{ &P{1,0},&P{0,1},&P{-1,0},&P{0,-1} }

	ps := []*P{ &P{ 0, 0 } }
	dist1[0][0] = -1
	for i := 1; len(ps) > 0; i++ {
		tmp := []*P{}
		for _, p := range ps {
			for _, m := range mv {
				row,col := p.row+m.row,p.col+m.col
				if row<0||row>=h||col<0||col>=w {
					continue
				}
				if field[row][col] == '#' {
					continue
				}
				if dist1[row][col] == 0 {
					dist1[row][col] = i
					tmp = append(tmp, &P{row, col})
				}
			}
		}
		ps = tmp
	}
	for row := 0; row < h; row++ {
		for col := 0; col < w; col++ {
			if p := &dist1[row][col]; *p == 0 {
				*p = 1e9
			}
		}
	}
	dist1[0][0] = 0
	
	if d := dist1[h-1][w-1]; d > 0 {
		ans = min(ans, d)
	}

	ps = []*P{ &P{h-1,w-1} }
	dist2[h-1][w-1] = -1
	for i := 1; len(ps) > 0; i++ {
		tmp := []*P{}
		for _, p := range ps {
			for _, m := range mv {
				row,col := p.row+m.row,p.col+m.col
				if row<0||row>=h||col<0||col>=w {
					continue
				}
				if field[row][col] == '#' {
					continue
				}
				if dist2[row][col] == 0 {
					dist2[row][col] = i
					tmp = append(tmp, &P{row, col})
				}
			}
		}
		ps = tmp
	}
	for row := 0; row < h; row++ {
		for col := 0; col < w; col++ {
			if p := &dist2[row][col]; *p == 0 {
				*p = 1e9
			}
		}
	}
	dist2[h-1][w-1] = 0
	
	col1 := make([]int, w)
	col2 := make([]int, w)
	for i := range col1 {
		col1[i] = 1e9
		col2[i] = 1e9
	}
	row1 := make([]int, h)
	row2 := make([]int, h)
	for i := range row1 {
		row1[i] = 1e9
		row2[i] = 1e9
	}
	for row := 0; row < h; row++ {
		for col := 0; col < w; col++ {
			col1[col] = min(col1[col], dist1[row][col]-row)
			col2[col] = min(col2[col], dist2[row][col]+row)
			row1[row] = min(row1[row], dist1[row][col]-col)
			row2[row] = min(row2[row], dist2[row][col]+col)
		}
	} 
	
	for col := 0; col+1 < w; col++ {
		ans = min(ans, col1[col]+col2[col+1]+2)
	}
	
	for row := 0; row+1 < h; row++ {
		ans = min(ans, row1[row]+row2[row+1]+2)
	}
	
	return ans
}

type P struct {
	row, col int
}
0