結果
問題 | No.2928 Gridpath |
ユーザー |
![]() |
提出日時 | 2024-10-12 16:27:58 |
言語 | PyPy3 (7.3.15) |
結果 |
AC
|
実行時間 | 175 ms / 2,000 ms |
コード長 | 888 bytes |
コンパイル時間 | 149 ms |
コンパイル使用メモリ | 82,368 KB |
実行使用メモリ | 78,588 KB |
最終ジャッジ日時 | 2024-10-12 16:28:12 |
合計ジャッジ時間 | 2,638 ms |
ジャッジサーバーID (参考情報) |
judge / judge5 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 20 |
ソースコード
import collectionsimport syssys.setrecursionlimit(10**5)H,W = map(int,input().split())Si,Sj = map(int,input().split())Gi,Gj = map(int,input().split())ans = 0S = set()WW = 100S.add(Si*WW+Sj)D = collections.deque()D.append([Si,Sj])X = [1,0,-1,0]Y = [0,1,0,-1]ans = 0def dfs():global ansif D[-1]==[Gi,Gj]:ans+=1else:i,j = D[-1]for x,y in zip(X,Y):ni = i+xnj = j+yif 1<=ni<=H and 1<=nj<=W and not ni*WW+nj in S:S.remove(i*WW+j)if not (ni*WW+nj+1 in S or (ni+1)*WW+nj in S or (ni-1)*WW+nj in S or ni*WW+nj-1 in S):S.add(i*WW+j)D.append([ni,nj])S.add(ni*WW+nj)dfs()D.pop()S.remove(ni*WW+nj)S.add(i*WW+j)dfs()print(ans)