結果

問題 No.157 2つの空洞
ユーザー tnoda_tnoda_
提出日時 2015-03-21 21:23:24
言語 Go
(1.22.1)
結果
AC  
実行時間 2 ms / 2,000 ms
コード長 1,340 bytes
コンパイル時間 11,418 ms
コンパイル使用メモリ 238,120 KB
実行使用メモリ 6,824 KB
最終ジャッジ日時 2024-10-10 03:30:07
合計ジャッジ時間 12,380 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge2
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 2 ms
6,820 KB
testcase_01 AC 2 ms
6,820 KB
testcase_02 AC 1 ms
6,820 KB
testcase_03 AC 2 ms
6,820 KB
testcase_04 AC 2 ms
6,816 KB
testcase_05 AC 2 ms
6,816 KB
testcase_06 AC 1 ms
6,820 KB
testcase_07 AC 1 ms
6,820 KB
testcase_08 AC 2 ms
6,816 KB
testcase_09 AC 1 ms
6,820 KB
testcase_10 AC 2 ms
6,820 KB
testcase_11 AC 1 ms
6,816 KB
testcase_12 AC 2 ms
6,816 KB
testcase_13 AC 2 ms
6,820 KB
testcase_14 AC 2 ms
6,820 KB
testcase_15 AC 2 ms
6,820 KB
testcase_16 AC 2 ms
6,824 KB
testcase_17 AC 2 ms
6,820 KB
testcase_18 AC 2 ms
6,816 KB
testcase_19 AC 2 ms
6,820 KB
権限があれば一括ダウンロードができます

ソースコード

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
			}
			B[h1][w1] = to
			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