結果
問題 | No.697 池の数はいくつか |
ユーザー |
👑 ![]() |
提出日時 | 2020-06-02 15:56:59 |
言語 | PyPy3 (7.3.15) |
結果 |
MLE
|
実行時間 | - |
コード長 | 931 bytes |
コンパイル時間 | 148 ms |
コンパイル使用メモリ | 82,240 KB |
実行使用メモリ | 1,166,724 KB |
最終ジャッジ日時 | 2024-11-25 16:12:48 |
合計ジャッジ時間 | 72,473 ms |
ジャッジサーバーID (参考情報) |
judge1 / judge2 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | MLE * 3 |
other | AC * 20 TLE * 5 MLE * 7 |
ソースコード
from collections import dequedef BFS(V,E):Q=deque([V[0]])S={v:False for v in V}S[V[0]]=TrueT=[V[0]]while Q:v=Q.popleft()N=[w for w in V if ((v,w) in E) and (not S[w])]for w in N:Q.append(w)T.append(w)S[w]=Truereturn TH,W=map(int,input().split())def f(x,y):return y*(W+2)+xdef g(n):return (n%(W+2),n//(W+2))A=[[0]*(W+2)]for i in range(H):A.append([0]+list(map(int,input().split()))+[0])A+=[[0]*(W+2)]V=[]for y in range(H+2):for x in range(W+2):if A[y][x]==1:V.append(f(x,y))E=set()for n in V:(x,y)=g(n)if A[y][x]==1:if A[y][x+1]==1:E|={(f(x,y),f(x+1,y)),(f(x+1,y),f(x,y))}if A[y+1][x]==1:E|={(f(x,y),f(x,y+1)),(f(x,y+1),f(x,y))}U=set()W=set(V)k=0while U!=W:k+=1U|=set(BFS(list(W-U),E))print(k)