結果
問題 | No.340 雪の足跡 |
ユーザー | mkawa2 |
提出日時 | 2020-04-29 01:39:31 |
言語 | PyPy3 (7.3.15) |
結果 |
AC
|
実行時間 | 516 ms / 1,000 ms |
コード長 | 1,945 bytes |
コンパイル時間 | 803 ms |
コンパイル使用メモリ | 86,708 KB |
実行使用メモリ | 108,128 KB |
最終ジャッジ日時 | 2023-08-17 12:37:55 |
合計ジャッジ時間 | 11,822 ms |
ジャッジサーバーID (参考情報) |
judge12 / judge14 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 95 ms
71,656 KB |
testcase_01 | AC | 93 ms
71,760 KB |
testcase_02 | AC | 93 ms
71,500 KB |
testcase_03 | AC | 91 ms
71,636 KB |
testcase_04 | AC | 93 ms
71,712 KB |
testcase_05 | AC | 93 ms
71,536 KB |
testcase_06 | AC | 93 ms
71,684 KB |
testcase_07 | AC | 93 ms
71,636 KB |
testcase_08 | AC | 92 ms
71,524 KB |
testcase_09 | AC | 91 ms
71,664 KB |
testcase_10 | AC | 94 ms
71,560 KB |
testcase_11 | AC | 119 ms
77,656 KB |
testcase_12 | AC | 113 ms
77,736 KB |
testcase_13 | AC | 117 ms
77,728 KB |
testcase_14 | AC | 148 ms
80,452 KB |
testcase_15 | AC | 154 ms
80,460 KB |
testcase_16 | AC | 136 ms
79,504 KB |
testcase_17 | AC | 160 ms
80,832 KB |
testcase_18 | AC | 156 ms
80,796 KB |
testcase_19 | AC | 161 ms
80,604 KB |
testcase_20 | AC | 339 ms
102,664 KB |
testcase_21 | AC | 226 ms
78,280 KB |
testcase_22 | AC | 116 ms
99,980 KB |
testcase_23 | AC | 392 ms
102,740 KB |
testcase_24 | AC | 306 ms
103,300 KB |
testcase_25 | AC | 353 ms
103,244 KB |
testcase_26 | AC | 168 ms
78,044 KB |
testcase_27 | AC | 127 ms
77,664 KB |
testcase_28 | AC | 154 ms
79,468 KB |
testcase_29 | AC | 429 ms
97,484 KB |
testcase_30 | AC | 336 ms
89,164 KB |
testcase_31 | AC | 472 ms
100,504 KB |
testcase_32 | AC | 505 ms
108,064 KB |
testcase_33 | AC | 452 ms
108,092 KB |
testcase_34 | AC | 516 ms
108,128 KB |
testcase_35 | AC | 410 ms
107,928 KB |
testcase_36 | AC | 410 ms
108,096 KB |
ソースコード
from collections import * import sys sys.setrecursionlimit(10 ** 6) def MI(): return map(int, sys.stdin.readline().split()) def LI(): return list(map(int, sys.stdin.readline().split())) def SI(): return sys.stdin.readline()[:-1] def main(): w,h,n=MI() if (w,h)==(1,1): print(0) exit() # lrは左右移動、udは上下移動。いもす法の要領で移動可能な区間を記録していく lr=[0]*(w*h+1) ud=[0]*(w*h+1) for _ in range(n): SI() bb=LI() # 区間の始点に+1、終点に-1をしていく for b0,b1 in zip(bb,bb[1:]): if b0>b1:b0,b1=b1,b0 # 左右移動の場合 if b0//w==b1//w: lr[b0+1]+=1 lr[b1+1]-=1 # 上下移動の場合 else: j0=b0%w*h+b0//w j1=b1%w*h+b1//w ud[j0+1]+=1 ud[j1+1]-=1 # 累積和をとって移動可能な区間を求める for i in range(w*h):lr[i+1]+=lr[i] for j in range(w*h):ud[j+1]+=ud[j] #print(lr) #print(ud) q=deque() q.append((0,0)) first=[True]*w*h def finish(d): print(d+1) exit() while q: d,i=q.popleft() j=i%w*h+i//w # 左への移動 if lr[i] and first[i-1]: if i-1==h*w-1:finish(d) first[i-1]=False q.append((d+1,i-1)) # 右への移動 if lr[i+1] and first[i+1]: if i+1==h*w-1:finish(d) first[i+1]=False q.append((d+1,i+1)) # 上への移動 if ud[j+1] and first[i+w]: if i+w==h*w-1:finish(d) first[i+w]=False q.append((d+1,i+w)) # 下への移動 if ud[j] and first[i-w]: if i-w==h*w-1:finish(d) first[i-w]=False q.append((d+1,i-w)) print("Odekakedekinai..") main()