結果

問題 No.157 2つの空洞
コンテスト
ユーザー tnoda_
提出日時 2015-03-21 20:15:43
言語 Go
(1.23.4)
結果
MLE  
実行時間 -
コード長 1,322 bytes
コンパイル時間 11,433 ms
コンパイル使用メモリ 233,932 KB
実行使用メモリ 576,532 KB
最終ジャッジ日時 2024-10-10 03:29:21
合計ジャッジ時間 15,245 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge1
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 4
other AC * 13 MLE * 1 -- * 2
権限があれば一括ダウンロードができます

ソースコード

diff # 

package main

import "fmt"

type pos struct {
	h, w, d int
}

func newPos(h, w, d int) *pos {
	return &pos{h, w, d}
}

var dw = []int{1, 0, -1, 0}
var dh = []int{0, 1, 0, -1}

//width
var W int

//height
var H int

//board
var B [30][30]rune

func bfs1(q []*pos, to rune) {
	for len(q) > 0 {
		p0 := q[0]
		q = q[1:]
		h0, w0 := p0.h, p0.w
		B[h0][w0] = to
		for i := 0; i < 4; i++ {
			w1, h1 := w0+dw[i], h0+dh[i]
			if w1 < 0 || W <= w1 || h1 < 0 || H <= h1 || B[h1][w1] != '.' {
				continue
			}
			q = append(q, newPos(h1, w1, 0))
		}
	}
}

func main() {
	fmt.Scan(&W, &H)
	for i := 0; i < H; i++ {
		var row string
		fmt.Scan(&row)
		for j, r := range row {
			B[i][j] = r
		}
	}

	n := '1'
	for i := 0; i < H; i++ {
		for j := 0; j < W; j++ {
			if B[i][j] == '.' {
				bfs1([]*pos{newPos(i, j, 0)}, n)
				n++
			}
		}
	}

	var q []*pos
	for i := 0; i < H; i++ {
		for j := 0; j < W; j++ {
			if B[i][j] == '1' {
				q = append(q, newPos(i, j, 0))
			}
		}
	}
	for len(q) > 0 {
		q0 := q[0]
		q = q[1:]
		h0, w0, d0 := q0.h, q0.w, q0.d
		for i := 0; i < 4; i++ {
			h1, w1 := h0+dh[i], w0+dw[i]
			if h1 < 0 || H <= h1 || w1 < 0 || W <= w1 {
				continue
			}
			switch B[h1][w1] {
			case '2':
				fmt.Println(d0)
				return
			case '#':
				B[h1][w1] = '1'
				q = append(q, newPos(h1, w1, d0+1))
			}
		}
	}
}
0