結果

問題 No.2928 Gridpath
ユーザー timitimi
提出日時 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
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 41 ms
54,692 KB
testcase_01 AC 39 ms
55,292 KB
testcase_02 AC 99 ms
77,496 KB
testcase_03 AC 42 ms
54,700 KB
testcase_04 AC 40 ms
54,656 KB
testcase_05 AC 48 ms
63,276 KB
testcase_06 AC 80 ms
76,420 KB
testcase_07 AC 42 ms
55,004 KB
testcase_08 AC 40 ms
54,992 KB
testcase_09 AC 69 ms
74,260 KB
testcase_10 AC 43 ms
55,636 KB
testcase_11 AC 41 ms
56,224 KB
testcase_12 AC 42 ms
55,732 KB
testcase_13 AC 40 ms
54,988 KB
testcase_14 AC 40 ms
54,916 KB
testcase_15 AC 91 ms
77,056 KB
testcase_16 AC 90 ms
76,924 KB
testcase_17 AC 88 ms
76,820 KB
testcase_18 AC 99 ms
77,028 KB
testcase_19 AC 94 ms
76,972 KB
testcase_20 AC 39 ms
55,096 KB
testcase_21 AC 123 ms
78,836 KB
testcase_22 AC 95 ms
76,968 KB
権限があれば一括ダウンロードができます

ソースコード

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