結果
問題 | No.340 雪の足跡 |
ユーザー | mkawa2 |
提出日時 | 2020-04-29 01:39:10 |
言語 | Python3 (3.12.2 + numpy 1.26.4 + scipy 1.12.0) |
結果 |
TLE
|
実行時間 | - |
コード長 | 1,945 bytes |
コンパイル時間 | 70 ms |
コンパイル使用メモリ | 12,800 KB |
実行使用メモリ | 97,152 KB |
最終ジャッジ日時 | 2024-05-04 19:16:26 |
合計ジャッジ時間 | 20,979 ms |
ジャッジサーバーID (参考情報) |
judge4 / judge5 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 26 ms
10,880 KB |
testcase_01 | AC | 26 ms
10,880 KB |
testcase_02 | AC | 25 ms
11,008 KB |
testcase_03 | AC | 27 ms
10,880 KB |
testcase_04 | AC | 26 ms
10,880 KB |
testcase_05 | AC | 27 ms
11,008 KB |
testcase_06 | AC | 25 ms
10,880 KB |
testcase_07 | AC | 26 ms
11,008 KB |
testcase_08 | AC | 26 ms
11,008 KB |
testcase_09 | AC | 25 ms
10,880 KB |
testcase_10 | AC | 26 ms
10,880 KB |
testcase_11 | AC | 32 ms
11,008 KB |
testcase_12 | AC | 30 ms
10,880 KB |
testcase_13 | AC | 32 ms
10,880 KB |
testcase_14 | AC | 123 ms
12,672 KB |
testcase_15 | AC | 137 ms
12,800 KB |
testcase_16 | AC | 88 ms
11,776 KB |
testcase_17 | AC | 167 ms
12,928 KB |
testcase_18 | AC | 149 ms
12,928 KB |
testcase_19 | AC | 164 ms
13,056 KB |
testcase_20 | AC | 999 ms
41,124 KB |
testcase_21 | AC | 442 ms
11,008 KB |
testcase_22 | AC | 215 ms
34,304 KB |
testcase_23 | TLE | - |
testcase_24 | AC | 785 ms
34,688 KB |
testcase_25 | AC | 986 ms
50,304 KB |
testcase_26 | AC | 138 ms
11,520 KB |
testcase_27 | AC | 45 ms
11,008 KB |
testcase_28 | AC | 143 ms
12,160 KB |
testcase_29 | TLE | - |
testcase_30 | AC | 890 ms
23,012 KB |
testcase_31 | TLE | - |
testcase_32 | TLE | - |
testcase_33 | TLE | - |
testcase_34 | TLE | - |
testcase_35 | TLE | - |
testcase_36 | TLE | - |
ソースコード
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()