結果

問題 No.340 雪の足跡
ユーザー tktk_snsntktk_snsn
提出日時 2021-01-14 18:17:14
言語 PyPy3
(7.3.15)
結果
WA  
実行時間 -
コード長 1,402 bytes
コンパイル時間 821 ms
コンパイル使用メモリ 82,300 KB
実行使用メモリ 108,000 KB
最終ジャッジ日時 2024-05-03 10:59:07
合計ジャッジ時間 8,148 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge1
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 41 ms
54,832 KB
testcase_01 AC 40 ms
55,336 KB
testcase_02 AC 41 ms
54,624 KB
testcase_03 AC 41 ms
55,120 KB
testcase_04 AC 41 ms
54,780 KB
testcase_05 AC 40 ms
55,152 KB
testcase_06 WA -
testcase_07 AC 45 ms
55,696 KB
testcase_08 AC 39 ms
54,940 KB
testcase_09 AC 40 ms
54,304 KB
testcase_10 AC 40 ms
54,988 KB
testcase_11 AC 58 ms
70,176 KB
testcase_12 AC 72 ms
75,068 KB
testcase_13 WA -
testcase_14 WA -
testcase_15 WA -
testcase_16 WA -
testcase_17 AC 125 ms
79,556 KB
testcase_18 AC 121 ms
79,524 KB
testcase_19 AC 121 ms
79,836 KB
testcase_20 AC 290 ms
102,248 KB
testcase_21 AC 146 ms
77,096 KB
testcase_22 AC 90 ms
99,476 KB
testcase_23 WA -
testcase_24 AC 250 ms
101,752 KB
testcase_25 AC 329 ms
103,396 KB
testcase_26 AC 119 ms
77,620 KB
testcase_27 AC 59 ms
73,552 KB
testcase_28 WA -
testcase_29 AC 383 ms
97,640 KB
testcase_30 WA -
testcase_31 WA -
testcase_32 AC 446 ms
106,036 KB
testcase_33 AC 391 ms
104,384 KB
testcase_34 AC 456 ms
105,856 KB
testcase_35 AC 332 ms
107,180 KB
testcase_36 AC 333 ms
107,428 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

from collections import deque
import sys
input = sys.stdin.readline

h, w, n = map(int, input().split())
hori = [[0] * (w + 1) for _ in range(h)]
vert = [[0] * w for _ in range(h + 1)]

for _ in range(n):
    m = int(input())
    B = tuple(map(int, input().split()))
    for s, t in zip(B, B[1:]):
        hs, ws = divmod(s, w)
        ht, wt = divmod(t, w)
        if hs == ht:
            hori[hs][min(ws, wt)] += 1
            hori[hs][max(ws, wt)+1] -= 1
        elif ws == wt:
            vert[min(hs, ht)][ws] += 1
            vert[max(hs, ht)+1][ws] -= 1

for i in range(h):
    for j in range(w):
        hori[i][j + 1] += hori[i][j]
for j in range(w):
    for i in range(h):
        vert[i + 1][j] += vert[i][j]


def toID(x, y):
    return x * w + y

def push(x, y, d):
    ID = toID(x, y)
    if dist[ID] == -1:
        dist[ID] = d
        que.append(ID)

   
dist = [-1] * (h * w)
dist[0] = 0
que = deque([0])
while que:
    s = que.popleft()
    d = dist[s] + 1
    x, y = divmod(s, w)
    if x and vert[x][y] and vert[x - 1][y]:
        push(x - 1, y, d)
    if x + 1 < h and vert[x][y] and vert[x + 1][y]:
        push(x + 1, y, d)
    if y and hori[x][y] and hori[x][y - 1]:
        push(x, y - 1, d)
    if y + 1 < w and hori[x][y] and hori[x][y + 1]:
        push(x, y + 1, d)

goal = h * w - 1
if dist[goal] == -1:
    print("Odekakedekinai..")
else:
    print(dist[goal])
0