結果
問題 | No.1588 Connection |
ユーザー |
👑 ![]() |
提出日時 | 2021-07-08 23:18:50 |
言語 | PyPy3 (7.3.15) |
結果 |
AC
|
実行時間 | 249 ms / 2,000 ms |
コード長 | 1,145 bytes |
コンパイル時間 | 185 ms |
コンパイル使用メモリ | 82,516 KB |
実行使用メモリ | 95,972 KB |
平均クエリ数 | 481.78 |
最終ジャッジ日時 | 2024-07-17 12:31:10 |
合計ジャッジ時間 | 5,271 ms |
ジャッジサーバーID (参考情報) |
judge4 / judge2 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 1 |
other | AC * 31 |
ソースコード
def question(a,b): print(a,b,flush=True) ans=input() if ans[0]=="B": return 1 elif ans[0]=="W": return 0 else: exit() def answer(ans): exit(print(ans,flush=True)) #================================================= from collections import deque N,M=map(int,input().split()) # 自明な否定 if 2*N-1>M: answer("No") X=[[-1]*(N+1) for _ in range(N+1)] X[1][1]=X[N][N]=1 Remain=M-2 Q=deque([(1,1)]) T=[(1,0),(-1,0),(0,1),(0,-1)] while Q: x,y=Q.popleft() if Remain==0: break for a,b in T: p=x+a; q=y+b if 1<=p<=N and 1<=q<=N and X[p][q]==-1 and (N-p)+(N-q)<=Remain: X[p][q]=quest=question(p,q) if quest: if (N-p)+(N-q)==1: break Q.append((p,q)) Remain-=1 F=[[0]*(N+1) for _ in range(N+1)]; F[1][1]=1 Q=deque([(1,1)]) while Q: x,y=Q.popleft() for a,b in T: p=x+a; q=y+b if 1<=p<=N and 1<=q<=N and X[p][q]==1 and F[p][q]==0: F[p][q]=1 Q.append((p,q)) answer("Yes" if F[N][N] else "No")