結果
問題 | No.2928 Gridpath |
ユーザー |
![]() |
提出日時 | 2024-10-20 13:03:25 |
言語 | PyPy3 (7.3.15) |
結果 |
AC
|
実行時間 | 123 ms / 2,000 ms |
コード長 | 1,105 bytes |
コンパイル時間 | 475 ms |
コンパイル使用メモリ | 82,440 KB |
実行使用メモリ | 78,836 KB |
最終ジャッジ日時 | 2024-10-20 13:03:28 |
合計ジャッジ時間 | 3,084 ms |
ジャッジサーバーID (参考情報) |
judge3 / judge1 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 20 |
ソースコード
mod=998244353 #N,Q=map(int, input().split()) import heapq from heapq import heappop,heappush,heapify from sys import stdin, setrecursionlimit input = stdin.readline readline = stdin.readline H,W=map(int, input().split()) sy,sx=map(int, input().split()) gy,gx=map(int, input().split()) sy-=1;sx-=1;gy-=1;gx-=1 from collections import deque d=deque() C=[0]*(H*W) s=sy*W+sx C[s]=1 d.append((C,sy,sx)) dx,dy=[1,-1,0,0],[0,0,1,-1] ans=0 for t in range(230): nd=deque() while d: C,y,x=d.popleft() for i in range(4): ny,nx=y+dy[i],x+dx[i] if 0<=ny<H and 0<=nx<W: if C[ny*W+nx]==1: continue f=1 for j in range(4): nny,nnx=ny+dy[j],nx+dx[j] if 0<=nny<H and 0<=nnx<W: if y==nny and x==nnx: continue c=nny*W+nnx if C[c]==1: f=0 if f==0: break if f==1: if ny==gy and nx==gx: ans+=1 else: c=ny*W+nx CC=C.copy() CC[c]=1 nd.append((CC,ny,nx)) d=nd print(ans)