結果

問題 No.340 雪の足跡
コンテスト
ユーザー gew1fw
提出日時 2025-06-12 14:34:51
言語 PyPy3
(7.3.15)
結果
TLE  
実行時間 -
コード長 2,394 bytes
コンパイル時間 166 ms
コンパイル使用メモリ 82,816 KB
実行使用メモリ 88,348 KB
最終ジャッジ日時 2025-06-12 14:35:34
合計ジャッジ時間 6,365 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge2
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 5
other AC * 15 TLE * 1 -- * 16
権限があれば一括ダウンロードができます

ソースコード

diff #
raw source code 

from collections import deque

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

    # Initialize edge matrices
    h_edges = [[False]*(W-1) for _ in range(H)]  # horizontal edges (same row)
    v_edges = [[False]*W for _ in range(H-1)]    # vertical edges (same column)

    for _ in range(N):
        M_i = int(input[idx]); idx +=1
        B = list(map(int, input[idx:idx+M_i+1]))
        idx += M_i+1
        for j in range(M_i):
            current = B[j]
            next_node = B[j+1]
            x1 = current % W
            y1 = current // W
            x2 = next_node % W
            y2 = next_node // W

            if y1 == y2:
                # Same row, process horizontal edges
                start_x = min(x1, x2)
                end_x = max(x1, x2)
                for x in range(start_x, end_x):
                    h_edges[y1][x] = True
            else:
                # Same column, process vertical edges
                start_y = min(y1, y2)
                end_y = max(y1, y2)
                for y in range(start_y, end_y):
                    v_edges[y][x1] = True

    # BFS setup
    dist = [[-1 for _ in range(W)] for _ in range(H)]
    q = deque()
    if W == 0 or H == 0:
        print("Odekakedekinai..")
        return

    dist[0][0] = 0
    q.append((0, 0))
    found = False

    while q:
        x, y = q.popleft()
        if x == W-1 and y == H-1:
            print(dist[y][x])
            found = True
            break

        # Check East
        if x + 1 < W and h_edges[y][x]:
            if dist[y][x+1] == -1:
                dist[y][x+1] = dist[y][x] + 1
                q.append((x+1, y))
        # Check West
        if x - 1 >= 0 and h_edges[y][x-1]:
            if dist[y][x-1] == -1:
                dist[y][x-1] = dist[y][x] + 1
                q.append((x-1, y))
        # Check North
        if y + 1 < H and v_edges[y][x]:
            if dist[y+1][x] == -1:
                dist[y+1][x] = dist[y][x] + 1
                q.append((x, y+1))
        # Check South
        if y - 1 >= 0 and v_edges[y-1][x]:
            if dist[y-1][x] == -1:
                dist[y-1][x] = dist[y][x] + 1
                q.append((x, y-1))

    if not found:
        print("Odekakedekinai..")

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