結果

問題 No.340 雪の足跡
コンテスト
ユーザー gew1fw
提出日時 2025-06-12 14:35:49
言語 PyPy3
(7.3.15)
結果
TLE  
実行時間 -
コード長 1,974 bytes
コンパイル時間 147 ms
コンパイル使用メモリ 81,972 KB
実行使用メモリ 196,028 KB
最終ジャッジ日時 2025-06-12 14:36:29
合計ジャッジ時間 10,085 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge1
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 5
other AC * 12 TLE * 4 -- * 16
権限があれば一括ダウンロードができます

ソースコード

diff # 

from collections import deque
import sys

def main():
    input = sys.stdin.read().split()
    ptr = 0
    W = int(input[ptr])
    ptr += 1
    H = int(input[ptr])
    ptr += 1
    N = int(input[ptr])
    ptr += 1

    size = W * H
    adjacency = [set() for _ in range(size)]

    for _ in range(N):
        M_i = int(input[ptr])
        ptr += 1
        B = list(map(int, input[ptr:ptr + M_i + 1]))
        ptr += M_i + 1

        for j in range(M_i):
            prev_block = B[j]
            curr_block = B[j + 1]

            prev_w = prev_block % W
            prev_h = prev_block // W
            curr_w = curr_block % W
            curr_h = curr_block // W

            path = []
            if prev_h == curr_h:
                if prev_w <= curr_w:
                    for w in range(prev_w, curr_w + 1):
                        path.append(w + prev_h * W)
                else:
                    for w in range(prev_w, curr_w - 1, -1):
                        path.append(w + prev_h * W)
            else:
                if prev_h <= curr_h:
                    for h in range(prev_h, curr_h + 1):
                        path.append(prev_w + h * W)
                else:
                    for h in range(prev_h, curr_h - 1, -1):
                        path.append(prev_w + h * W)

            for i in range(len(path) - 1):
                a = path[i]
                b = path[i + 1]
                adjacency[a].add(b)
                adjacency[b].add(a)

    start = 0
    end = W * H - 1

    distance = [-1] * size
    distance[start] = 0
    queue = deque([start])

    while queue:
        current = queue.popleft()
        if current == end:
            print(distance[current])
            return
        for neighbor in adjacency[current]:
            if distance[neighbor] == -1:
                distance[neighbor] = distance[current] + 1
                queue.append(neighbor)

    print("Odekakedekinai..")

if __name__ == "__main__":
    main()
0