Submission #24913693

Source Code Expand

H,W=map(int,input().split())
F=[input()for _ in range(H)]
#DFS/BFS 非再帰
from collections import deque
i_init,v_init,v_yet=0,0,H*W
D=deque()
D.appendleft([i_init,v_init])
V=[v_yet]*(H*W)
V[i_init]=v_init
#探索
while D:
  i,v=D.popleft()
  h,w=i//W,i%W
  for dh in range(-2,3):
    for dw in range(-2,3):
      d=abs(dh)+abs(dw)
      nh,nw=h+dh,w+dw
      ni=nh*W+nw
      if 0<=nh<H and 0<=nw<W:
        if d==1 and V[ni]>v and F[nh][nw]=='.':
          V[ni]=v
          D.appendleft([ni,v])
        elif 0<d<4 and V[ni]>v+1:
          V[ni]=v+1
          D.append([ni,v+1])
print(V[-1])

Submission Info

Submission Time
Task E - Stronger Takahashi
User Pandruant
Language PyPy3 (7.3.0)
Score 500
Code Size 595 Byte
Status AC
Exec Time 399 ms
Memory 110848 KiB

Judge Result

Set Name Sample All
Score / Max Score 0 / 0 500 / 500
Status
AC × 3
AC × 21
Set Name Test Cases
Sample sample_01.txt, sample_02.txt, sample_03.txt
All hand_01.txt, random_01.txt, random_02.txt, random_03.txt, random_04.txt, random_05.txt, random_06.txt, random_07.txt, random_08.txt, random_09.txt, random_10.txt, random_11.txt, random_12.txt, random_13.txt, random_14.txt, random_15.txt, random_16.txt, random_17.txt, sample_01.txt, sample_02.txt, sample_03.txt
Case Name Status Exec Time Memory
hand_01.txt AC 72 ms 64952 KiB
random_01.txt AC 208 ms 80720 KiB
random_02.txt AC 399 ms 110848 KiB
random_03.txt AC 137 ms 75064 KiB
random_04.txt AC 372 ms 103120 KiB
random_05.txt AC 184 ms 82568 KiB
random_06.txt AC 328 ms 99092 KiB
random_07.txt AC 159 ms 76056 KiB
random_08.txt AC 254 ms 81460 KiB
random_09.txt AC 112 ms 74476 KiB
random_10.txt AC 239 ms 80012 KiB
random_11.txt AC 113 ms 74840 KiB
random_12.txt AC 216 ms 79380 KiB
random_13.txt AC 56 ms 64552 KiB
random_14.txt AC 86 ms 74056 KiB
random_15.txt AC 84 ms 74128 KiB
random_16.txt AC 334 ms 99760 KiB
random_17.txt AC 326 ms 99608 KiB
sample_01.txt AC 56 ms 65280 KiB
sample_02.txt AC 64 ms 68692 KiB
sample_03.txt AC 65 ms 68916 KiB