結果

問題 No.340 雪の足跡
ユーザー lam6er
提出日時 2025-04-15 23:39:57
言語 PyPy3
(7.3.15)
結果
TLE  
実行時間 -
コード長 2,332 bytes
コンパイル時間 328 ms
コンパイル使用メモリ 82,392 KB
実行使用メモリ 100,044 KB
最終ジャッジ日時 2025-04-15 23:42:19
合計ジャッジ時間 5,618 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge5
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 5
other AC * 15 TLE * 1 -- * 16
権限があれば一括ダウンロードができます

ソースコード

diff # 

import sys
from collections import deque

def main():
    W, H, N = map(int, sys.stdin.readline().split())
    east_edges = [[False] * (W - 1) for _ in range(H)]
    north_edges = [[False] * W for _ in range(H - 1)]

    for _ in range(N):
        M_i = int(sys.stdin.readline())
        B = list(map(int, sys.stdin.readline().split()))
        for j in range(M_i):
            B_prev = B[j]
            B_current = B[j + 1]
            h_prev = B_prev // W
            w_prev = B_prev % W
            h_current = B_current // W
            w_current = B_current % W
            if h_prev == h_current:
                # Horizontal movement
                start_w = min(w_prev, w_current)
                end_w = max(w_prev, w_current)
                for w in range(start_w, end_w):
                    east_edges[h_prev][w] = True
            else:
                # Vertical movement
                start_h = min(h_prev, h_current)
                end_h = max(h_prev, h_current)
                for h in range(start_h, end_h):
                    north_edges[h][w_prev] = True

    # BFS initialization
    visited = [[-1 for _ in range(W)] for _ in range(H)]
    q = deque()
    q.append((0, 0))
    visited[0][0] = 0
    target_h = H - 1
    target_w = W - 1

    while q:
        h, w = q.popleft()
        current_dist = visited[h][w]
        if h == target_h and w == target_w:
            print(current_dist)
            return

        # Check east direction
        if w < W - 1 and east_edges[h][w]:
            if visited[h][w + 1] == -1:
                visited[h][w + 1] = current_dist + 1
                q.append((h, w + 1))

        # Check west direction
        if w > 0 and east_edges[h][w - 1]:
            if visited[h][w - 1] == -1:
                visited[h][w - 1] = current_dist + 1
                q.append((h, w - 1))

        # Check north direction
        if h < H - 1 and north_edges[h][w]:
            if visited[h + 1][w] == -1:
                visited[h + 1][w] = current_dist + 1
                q.append((h + 1, w))

        # Check south direction
        if h > 0 and north_edges[h - 1][w]:
            if visited[h - 1][w] == -1:
                visited[h - 1][w] = current_dist + 1
                q.append((h - 1, w))

    print("Odekakedekinai..")

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