結果
問題 |
No.340 雪の足跡
|
ユーザー |
![]() |
提出日時 | 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 |
ソースコード
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()