結果

問題 No.3504 Insert Maze
コンテスト
ユーザー ID 21712
提出日時 2026-04-18 21:40:34
言語 Go
(1.26.1)
コンパイル:
env GOCACHE=/tmp go build _filename_
実行:
./Main
結果
WA  
実行時間 -
コード長 1,524 bytes
記録
記録タグの例:
初AC ショートコード 純ショートコード 純主流ショートコード 最速実行時間
コンパイル時間 16,029 ms
コンパイル使用メモリ 286,160 KB
実行使用メモリ 95,404 KB
最終ジャッジ日時 2026-04-18 21:42:36
合計ジャッジ時間 37,154 ms
ジャッジサーバーID
（参考情報） 		judge2_1 / judge3_1
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 83 WA * 2
権限があれば一括ダウンロードができます

ソースコード

diff #
raw source code 

package main

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

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 := h+w
	
	ans = min(ans, solve(h, w, field))
	
	c1 := make([]string, h)
	for i, s := range field {
		c1[i] = s[:1]+"." + s[1:]
	}
	ans = min(ans, solve(h,w+1,c1))
	
	cw := make([]string, h)
	for i, s := range field {
		cw[i] = s[:w-1]+"." + s[w-1:]
	}
	ans = min(ans, solve(h,w+1,cw))
	
	r1 := make([]string, h+1)
	r1[0] = field[0]
	r1[1] = Repeat(".", w)
	copy(r1[2:], field[1:])
	ans = min(ans, solve(h+1,w,r1))
	
	rh := make([]string, h+1)
	copy(rh[:h-1], field[:h-1])
	rh[h-1] = Repeat(".",w)
	rh[h] = field[h-1]
	ans = min(ans, solve(h+1,w,rh))

	if ans == 1e9 {
		ans = -1
	}
	Println(ans)
}
	
func solve(h, w int, field []string) int {
	dist := make([][]int, h)
	for i := range field {
		dist[i] = make([]int, w)
	}
	ps := []*P{ &P{ 0, 0 } }
	dist[0][0] = -1
	mv := []*P{ &P{1,0},&P{0,1},&P{-1,0},&P{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 dist[row][col] == 0 {
					dist[row][col] = i
					tmp = append(tmp, &P{row, col})
				}
			}
		}
		ps = tmp
	}
	
	if d := dist[h-1][w-1]; d > 0 {
		return d
	} else {
		return 1e9
	}
}

type P struct {
	row, col int
}
0