#1056704 (PyPy3) No.340 雪の足跡

• 問題: 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

ソースコード

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
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()
 
 
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX