結果
問題 | No.697 池の数はいくつか |
ユーザー |
![]() |
提出日時 | 2025-01-21 22:17:09 |
言語 | PyPy3 (7.3.15) |
結果 |
AC
|
実行時間 | 1,568 ms / 6,000 ms |
コード長 | 864 bytes |
コンパイル時間 | 267 ms |
コンパイル使用メモリ | 82,656 KB |
実行使用メモリ | 289,256 KB |
最終ジャッジ日時 | 2025-01-21 22:17:36 |
合計ジャッジ時間 | 13,738 ms |
ジャッジサーバーID (参考情報) |
judge2 / judge1 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 32 |
ソースコード
def find(x):if P[x] == x: return xelse:P[x] = find(P[x]) #経路圧縮return P[x]# return find(P[x]) #経路圧縮なしdef same(x,y):return find(x) == find(y)def unite(x,y):x = find(x)y = find(y)if x == y: return 0if x > y: x,y = y,xP[y] = xdef group_count():for i in range(HW):P[i] = find(i)return len(set(P))H, W = map(int, input().split())HW = H * WA = [list(map(int, input().split())) for _ in range(H)]P = [i for i in range(HW + 1)]for h in range(H):for w in range(W):if A[h][w] == 0:unite(h * W + w, HW)continueif 0 < h and A[h][w] == A[h - 1][w]:unite(h * W + w, (h - 1) * W + w)if 0 < w and A[h][w] == A[h][w - 1]:unite(h * W + w, h * W + w - 1)print(group_count() - 1)