結果

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

ソースコード

diff # 

import sys
from collections import deque

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

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

    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):
            a = B[j]
            b = B[j+1]
            x1 = a % W
            y1 = a // W
            x2 = b % W
            y2 = b // W

            if x1 == x2 and y1 == y2:
                continue  # as per problem statement, but input ensures B_ij != B_ij+1

            if y1 == y2:  # same row
                if x2 > x1:
                    for x in range(x1, x2):
                        east[x][y1] = True
                        west[x+1][y1] = True
                else:
                    for x in range(x1, x2, -1):
                        west[x][y1] = True
                        east[x-1][y1] = True
            else:  # same column
                if y2 > y1:
                    for y in range(y1, y2):
                        north[x1][y] = True
                        south[x1][y+1] = True
                else:
                    for y in range(y1, y2, -1):
                        south[x1][y] = True
                        north[x1][y-1] = True

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

    target_x = W - 1
    target_y = H - 1

    while queue:
        x, y = queue.popleft()
        current_dist = dist[x][y]

        if x == target_x and y == target_y:
            print(current_dist)
            return

        # Check east
        if east[x][y] and x + 1 < W:
            if dist[x+1][y] == -1:
                dist[x+1][y] = current_dist + 1
                queue.append((x+1, y))
        # Check west
        if west[x][y] and x - 1 >= 0:
            if dist[x-1][y] == -1:
                dist[x-1][y] = current_dist + 1
                queue.append((x-1, y))
        # Check north
        if north[x][y] and y + 1 < H:
            if dist[x][y+1] == -1:
                dist[x][y+1] = current_dist + 1
                queue.append((x, y+1))
        # Check south
        if south[x][y] and y - 1 >= 0:
            if dist[x][y-1] == -1:
                dist[x][y-1] = current_dist + 1
                queue.append((x, y-1))

    print("Odekakedekinai..")

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