結果

問題 No.340 雪の足跡
ユーザー gew1fw
提出日時 2025-06-12 15:51:15
言語 PyPy3
(7.3.15)
結果
TLE  
実行時間 -
コード長 4,041 bytes
コンパイル時間 258 ms
コンパイル使用メモリ 82,944 KB
実行使用メモリ 171,108 KB
最終ジャッジ日時 2025-06-12 15:51:38
合計ジャッジ時間 6,974 ms
ジャッジサーバーID
（参考情報） 		judge1 / 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

    if N == 0:
        if W * H == 1:
            print(0)
        else:
            print("Odekakedekinai..")
        return

    can_east = [[False for _ in range(H)] for _ in range(W)]
    can_west = [[False for _ in range(H)] for _ in range(W)]
    can_north = [[False for _ in range(H)] for _ in range(W)]
    can_south = [[False for _ in range(H)] for _ in range(W)]

    def get_coords(u):
        x = u % W
        y = u // W
        return (x, y)

    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):
            u = B[j]
            v = B[j+1]
            x1, y1 = get_coords(u)
            x2, y2 = get_coords(v)
            # Generate path
            path = []
            if x1 == x2:
                if y1 <= y2:
                    for y in range(y1, y2 + 1):
                        path.append((x1, y))
                else:
                    for y in range(y1, y2 - 1, -1):
                        path.append((x1, y))
            else:
                if x1 <= x2:
                    for x in range(x1, x2 + 1):
                        path.append((x, y1))
                else:
                    for x in range(x1, x2 - 1, -1):
                        path.append((x, y1))
            # Process each consecutive pair
            for k in range(len(path) - 1):
                a_x, a_y = path[k]
                b_x, b_y = path[k + 1]
                if a_x < b_x:
                    can_east[a_x][a_y] = True
                    can_west[b_x][b_y] = True
                elif a_x > b_x:
                    can_west[a_x][a_y] = True
                    can_east[b_x][b_y] = True
                elif a_y < b_y:
                    can_north[a_x][a_y] = True
                    can_south[b_x][b_y] = True
                else:
                    can_south[a_x][a_y] = True
                    can_north[b_x][b_y] = True

    # BFS setup
    start_x, start_y = 0, 0
    end_x, end_y = W - 1, H - 1

    if start_x == end_x and start_y == end_y:
        print(0)
        return

    distance = [[-1 for _ in range(H)] for _ in range(W)]
    queue = deque()
    distance[start_x][start_y] = 0
    queue.append((start_x, start_y))

    found = False
    while queue:
        x, y = queue.popleft()
        current_dist = distance[x][y]

        # East
        if x < W - 1 and can_east[x][y]:
            nx, ny = x + 1, y
            if distance[nx][ny] == -1:
                distance[nx][ny] = current_dist + 1
                queue.append((nx, ny))
                if nx == end_x and ny == end_y:
                    found = True
                    break
        # West
        if x > 0 and can_west[x][y]:
            nx, ny = x - 1, y
            if distance[nx][ny] == -1:
                distance[nx][ny] = current_dist + 1
                queue.append((nx, ny))
                if nx == end_x and ny == end_y:
                    found = True
                    break
        # North
        if y < H - 1 and can_north[x][y]:
            nx, ny = x, y + 1
            if distance[nx][ny] == -1:
                distance[nx][ny] = current_dist + 1
                queue.append((nx, ny))
                if nx == end_x and ny == end_y:
                    found = True
                    break
        # South
        if y > 0 and can_south[x][y]:
            nx, ny = x, y - 1
            if distance[nx][ny] == -1:
                distance[nx][ny] = current_dist + 1
                queue.append((nx, ny))
                if nx == end_x and ny == end_y:
                    found = True
                    break

    if distance[end_x][end_y] == -1:
        print("Odekakedekinai..")
    else:
        print(distance[end_x][end_y])

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