結果

問題 No.340 雪の足跡
コンテスト
ユーザー lam6er
提出日時 2025-03-20 21:16:22
言語 PyPy3
(7.3.15)
結果
RE  
実行時間 -
コード長 4,003 bytes
コンパイル時間 219 ms
コンパイル使用メモリ 82,224 KB
実行使用メモリ 89,956 KB
最終ジャッジ日時 2025-03-20 21:17:08
合計ジャッジ時間 6,759 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge5
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 5
other AC * 6 RE * 9 TLE * 1 -- * 16
権限があれば一括ダウンロードができます

ソースコード

diff #
raw source code 

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 flags: east, west, north, south
    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 = int(input[ptr]); ptr +=1
        B = list(map(int, input[ptr:ptr+M+1]))
        ptr += M+1

        for i in range(M):
            current = B[i]
            next_node = B[i+1]

            w1 = current % W
            h1 = current // W
            w2 = next_node % W
            h2 = next_node // W

            if h1 == h2:
                # East or West movement
                if w1 < w2:
                    # East
                    for w in range(w1, w2):
                        east[w][h1] = True
                        west[w+1][h1] = True
                else:
                    # West
                    for w in range(w1, w2, -1):
                        west[w][h1] = True
                        east[w-1][h1] = True
            else:
                # North or South movement
                if h1 < h2:
                    # North
                    for h in range(h1, h2):
                        north[h][w1] = True
                        south[h+1][w1] = True
                else:
                    # South
                    for h in range(h1, h2, -1):
                        south[h][w1] = True
                        north[h-1][w1] = True

    # BFS setup
    size = W * H
    start = 0
    goal = W * H - 1
    if start == goal:
        print(0)
        return

    visited = [-1] * size
    q = deque([start])
    visited[start] = 0
    found = False

    while q and not found:
        current = q.popleft()
        current_dist = visited[current]
        current_w = current % W
        current_h = current // W

        # Check East
        if current_w < W - 1:
            next_w = current_w + 1
            next_h = current_h
            next_node = next_w + next_h * W
            if east[current_w][current_h] and visited[next_node] == -1:
                if next_node == goal:
                    print(current_dist + 1)
                    found = True
                    break
                visited[next_node] = current_dist + 1
                q.append(next_node)
        # Check West
        if not found and current_w > 0:
            next_w = current_w - 1
            next_h = current_h
            next_node = next_w + next_h * W
            if west[current_w][current_h] and visited[next_node] == -1:
                if next_node == goal:
                    print(current_dist + 1)
                    found = True
                    break
                visited[next_node] = current_dist + 1
                q.append(next_node)
        # Check North
        if not found and current_h < H - 1:
            next_h = current_h + 1
            next_w = current_w
            next_node = next_w + next_h * W
            if north[current_h][current_w] and visited[next_node] == -1:
                if next_node == goal:
                    print(current_dist + 1)
                    found = True
                    break
                visited[next_node] = current_dist + 1
                q.append(next_node)
        # Check South
        if not found and current_h > 0:
            next_h = current_h - 1
            next_w = current_w
            next_node = next_w + next_h * W
            if south[current_h][current_w] and visited[next_node] == -1:
                if next_node == goal:
                    print(current_dist + 1)
                    found = True
                    break
                visited[next_node] = current_dist + 1
                q.append(next_node)

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

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