結果

問題 No.340 雪の足跡
ユーザー tktk_snsntktk_snsn
提出日時 2021-01-15 12:27:18
言語 PyPy3
(7.3.15)
結果
WA  
実行時間 -
コード長 1,301 bytes
コンパイル時間 391 ms
コンパイル使用メモリ 82,408 KB
実行使用メモリ 108,636 KB
最終ジャッジ日時 2024-05-04 03:40:01
合計ジャッジ時間 8,729 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge1
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 35 ms
53,888 KB
testcase_01 AC 35 ms
53,888 KB
testcase_02 AC 34 ms
54,168 KB
testcase_03 AC 35 ms
53,888 KB
testcase_04 AC 36 ms
54,144 KB
testcase_05 AC 35 ms
53,888 KB
testcase_06 WA -
testcase_07 AC 35 ms
54,144 KB
testcase_08 AC 35 ms
54,016 KB
testcase_09 AC 35 ms
54,400 KB
testcase_10 AC 35 ms
54,144 KB
testcase_11 AC 50 ms
67,584 KB
testcase_12 AC 57 ms
71,552 KB
testcase_13 WA -
testcase_14 WA -
testcase_15 WA -
testcase_16 WA -
testcase_17 AC 113 ms
79,776 KB
testcase_18 AC 111 ms
79,744 KB
testcase_19 AC 114 ms
79,548 KB
testcase_20 AC 267 ms
103,088 KB
testcase_21 AC 136 ms
76,660 KB
testcase_22 AC 83 ms
99,456 KB
testcase_23 AC 258 ms
101,868 KB
testcase_24 AC 228 ms
101,648 KB
testcase_25 AC 234 ms
101,904 KB
testcase_26 AC 95 ms
77,440 KB
testcase_27 WA -
testcase_28 WA -
testcase_29 AC 302 ms
97,112 KB
testcase_30 WA -
testcase_31 WA -
testcase_32 AC 363 ms
108,636 KB
testcase_33 AC 329 ms
107,756 KB
testcase_34 AC 368 ms
108,136 KB
testcase_35 AC 284 ms
102,012 KB
testcase_36 AC 269 ms
101,540 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

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


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


for _ in range(n):
    m = int(input())
    bs, *B = tuple(map(int, input().split()))
    sx, sy = divmod(bs, w)
    for bt in B:
        tx, ty = divmod(bt, w)
        if sx == tx:
            hori[sx][min(sy, ty)] += 1
            hori[sx][max(sy, ty)] -= 1
        elif sy == ty:
            vert[min(sx, tx)][sy] += 1
            vert[max(sx, tx)][sy] -= 1
        sx, sy = tx, ty
   
for i in range(h):
    for j in range(w - 1):
        hori[i][j + 1] += hori[i][j]
for j in range(w):
    for i in range(h - 1):
        vert[i + 1][j] += vert[i][j]

dist = [-1] * (h * w)
dist[0] = 0
que = deque([0])



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

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

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