#48032 (Python2) No.157 2つの空洞

• 問題: No.157 2つの空洞
• ユーザー: Tawara
• 提出日時: 2015-09-06 01:14:20
• 言語: Python2 (2.7.18)
• 結果: AC
• 実行時間: 12 ms / 2,000 ms
• コード長: 464 bytes
• コンパイル時間: 92 ms
• コンパイル使用メモリ: 6,780 KB
• 実行使用メモリ: 6,148 KB
• 最終ジャッジ日時: 2023-09-26 09:17:02
• 合計ジャッジ時間: 1,357 ms
• ジャッジサーバーID （参考情報）: judge15 / judge12

入力	結果	実行時間; 実行使用メモリ
testcase_00	AC	11 ms; 5,940 KB
testcase_01	AC	12 ms; 5,832 KB
testcase_02	AC	12 ms; 5,964 KB
testcase_03	AC	12 ms; 6,148 KB
testcase_04	AC	11 ms; 6,024 KB
testcase_05	AC	11 ms; 5,972 KB
testcase_06	AC	11 ms; 5,864 KB
testcase_07	AC	11 ms; 6,076 KB
testcase_08	AC	12 ms; 5,852 KB
testcase_09	AC	11 ms; 5,844 KB
testcase_10	AC	11 ms; 5,920 KB
testcase_11	AC	12 ms; 5,920 KB
testcase_12	AC	11 ms; 5,916 KB
testcase_13	AC	11 ms; 5,912 KB
testcase_14	AC	11 ms; 6,148 KB
testcase_15	AC	11 ms; 5,980 KB
testcase_16	AC	11 ms; 5,888 KB
testcase_17	AC	12 ms; 6,040 KB
testcase_18	AC	11 ms; 5,876 KB
testcase_19	AC	11 ms; 5,992 KB

ソースコード

def dfs(hx,hy):
	C[hy][hx] = "#"
	U[UN].add((hx,hy))
	for dx,dy in dxy:
			nx = hx + dx
			ny = hy + dy
			if 0 <= nx < W and 0 <= ny < H and C[ny][nx] == ".":
				dfs(nx,ny)
dxy = ((1,0),(0,1),(-1,0),(0,-1))
W,H = map(int,raw_input().split())
C = [list(raw_input()) for i in range(H)]
U = [set(),set()]
UN = 0
for i in range(H):
	for j in range(W):
		if C[i][j] == ".":
			dfs(j,i)
			UN += 1
print min(abs(x0-x1)+abs(y0-y1) for x0,y0 in U[0] for x1,y1 in U[1])-1