結果

問題 No.3504 Insert Maze
コンテスト
ユーザー ID 21712
提出日時 2026-04-18 18:09:10
言語 Go
(1.26.1)
コンパイル:
env GOCACHE=/tmp go build _filename_
実行:
./Main
結果
TLE  
実行時間 -
コード長 1,766 bytes
記録
記録タグの例:
初AC ショートコード 純ショートコード 純主流ショートコード 最速実行時間
コンパイル時間 16,137 ms
コンパイル使用メモリ 269,532 KB
実行使用メモリ 205,568 KB
最終ジャッジ日時 2026-04-18 18:10:37
合計ジャッジ時間 22,773 ms
ジャッジサーバーID
（参考情報） 		judge3_0 / judge1_0
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 27 TLE * 2 -- * 56
権限があれば一括ダウンロードができます

ソースコード

diff #
raw source code 

package main

import . "fmt"

func main() {
	var h,w int
	Scan(&h,&w)
	hh, ww := h+h-1, w+w-1
	field := make([][]byte, hh)
	dist := make([][]int, hh)
	for i := range field {
		field[i] = make([]byte, ww)
		dist[i] = make([]int, ww)
	}
	for i := 0; i < h; i++ {
		var s string
		Scan(&s)
		for j, ch := range s {
			if ch == '#' {
				field[i*2][j*2] = 1
			}
		}
	}
	dist[0][0] = -1
	ps := []*P{ &P { 0, 0 } }
	for i := 1; len(ps) > 0 ; i++ {
		tmp := []*P{}
		for _, p := range ps {
			r1 := p.move(0, 1)
			if r1.ok(field, dist, i) {
				tmp = append(tmp, r1)
			}
			l1 := p.move(0, -1)
			if l1.ok(field, dist, i) {
				tmp = append(tmp, l1)
			}
			if p.col % 2 == 0 {
				r2 := p.move(0, 2)
				if r2.ok(field, dist, i) {
					tmp = append(tmp, r2)
				}
				l2 := p.move(0, -2)
				if l2.ok(field, dist, i) {
					tmp = append(tmp, l2)
				}
			}
			u1 := p.move(-1, 0)
			if u1.ok(field, dist, i) {
				tmp = append(tmp, u1)
			}
			d1 := p.move(1, 0)
			if d1.ok(field, dist, i) {
				tmp = append(tmp, d1)
			}
			if p.row % 2 == 0 {
				u2 := p.move(-2, 0)
				if u2.ok(field, dist, i) {
					tmp = append(tmp, u2)
				}
				d2 := p.move(2, 0)
				if d2.ok(field, dist, i) {
					tmp = append(tmp, d2)
				}
			}
		}
		ps = tmp
	}
	if ans := dist[hh-1][ww-1]; ans == 0 {
		Println(-1)
	} else {
		Println(ans)
	}
}

type P struct {
	row, col int
}

func (p *P)in(h, w int) bool {
	return 0 <= p.row && p.row < h && 
		0 <= p.col && p.col < w
}

func (p *P)ok(field [][]byte, dist [][]int, x int) bool {
	if !p.in(len(field), len(field[0])) {
		return false
	}
	if field[p.row][p.col] == 0 &&
			dist[p.row][p.col] == 0 {
		dist[p.row][p.col] = x
		return true
	} else {
		return false
	}
}

func (p *P)move(dr, dc int) *P {
	return &P{p.row+dr,p.col+dc}
}
0