結果

問題 No.2928 Gridpath
ユーザー timi
提出日時 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
権限があれば一括ダウンロードができます

ソースコード

diff #

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)
0