結果

問題 No.340 雪の足跡
ユーザー gew1fw
提出日時 2025-06-12 19:34:28
言語 PyPy3
(7.3.15)
結果
TLE  
実行時間 -
コード長 2,329 bytes
コンパイル時間 184 ms
コンパイル使用メモリ 82,824 KB
実行使用メモリ 116,256 KB
最終ジャッジ日時 2025-06-12 19:34:58
合計ジャッジ時間 6,192 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge4
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
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())

    # Initialize direction grids
    north = [[False] * W for _ in range(H)]
    east = [[False] * W for _ in range(H)]
    south = [[False] * W for _ in range(H)]
    west = [[False] * W for _ in range(H)]

    for _ in range(N):
        M_i = int(sys.stdin.readline())
        B = list(map(int, sys.stdin.readline().split()))
        for j in range(M_i):
            prev = B[j]
            curr = B[j+1]
            x1 = prev % W
            y1 = prev // W
            x2 = curr % W
            y2 = curr // W

            if x1 == x2:
                # Vertical movement (north or south)
                start_y = min(y1, y2)
                end_y = max(y1, y2) - 1
                for y in range(start_y, end_y + 1):
                    north[y][x1] = True
                    south[y+1][x1] = True
            else:
                # Horizontal movement (east or west)
                start_x = min(x1, x2)
                end_x = max(x1, x2) - 1
                for x in range(start_x, end_x + 1):
                    east[y1][x] = True
                    west[y1][x+1] = True

    # BFS setup
    distance = [[-1] * W for _ in range(H)]
    q = deque()
    distance[0][0] = 0
    q.append((0, 0))

    # Directions: check each possible move
    while q:
        x, y = q.popleft()
        if y == H-1 and x == W-1:
            break

        # North
        if north[y][x] and y + 1 < H:
            if distance[y+1][x] == -1:
                distance[y+1][x] = distance[y][x] + 1
                q.append((x, y+1))
        # South
        if south[y][x] and y - 1 >= 0:
            if distance[y-1][x] == -1:
                distance[y-1][x] = distance[y][x] + 1
                q.append((x, y-1))
        # East
        if east[y][x] and x + 1 < W:
            if distance[y][x+1] == -1:
                distance[y][x+1] = distance[y][x] + 1
                q.append((x+1, y))
        # West
        if west[y][x] and x - 1 >= 0:
            if distance[y][x-1] == -1:
                distance[y][x-1] = distance[y][x] + 1
                q.append((x-1, y))

    goal = distance[H-1][W-1]
    if goal == -1:
        print("Odekakedekinai..")
    else:
        print(goal)

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