結果
問題 |
No.971 いたずらっ子
|
ユーザー |
![]() |
提出日時 | 2025-03-31 17:59:03 |
言語 | PyPy3 (7.3.15) |
結果 |
MLE
|
実行時間 | - |
コード長 | 2,609 bytes |
コンパイル時間 | 227 ms |
コンパイル使用メモリ | 82,080 KB |
実行使用メモリ | 1,464,148 KB |
最終ジャッジ日時 | 2025-03-31 17:59:48 |
合計ジャッジ時間 | 7,057 ms |
ジャッジサーバーID (参考情報) |
judge3 / judge4 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | -- * 4 |
other | MLE * 1 -- * 20 |
ソースコード
import sys from collections import deque H, W = map(int, sys.stdin.readline().split()) grid = [] for _ in range(H): line = sys.stdin.readline().strip() grid.append(list(line)) # Original BFS avoiding all 'k's def original_bfs(): visited = [[False]*(W+1) for _ in range(H+1)] q = deque() q.append((1, 1)) visited[1][1] = True distance = [[-1]*(W+1) for _ in range(H+1)] distance[1][1] = 0 while q: r, c = q.popleft() if r == H and c == W: return distance[r][c] for dr, dc in [(1, 0), (0, 1)]: nr = r + dr nc = c + dc if nr <= H and nc <= W: if grid[nr-1][nc-1] == '.' and not visited[nr][nc]: visited[nr][nc] = True distance[nr][nc] = distance[r][c] + 1 q.append((nr, nc)) return -1 original_distance = original_bfs() if original_distance != -1: print(original_distance) sys.exit() # Find all reachable 'k's reachable_k = [] visited = [[False]*(W+1) for _ in range(H+1)] q = deque() q.append((1, 1)) visited[1][1] = True while q: r, c = q.popleft() for dr, dc in [(0, 1), (1, 0)]: nr = r + dr nc = c + dc if nr > H or nc > W: continue if visited[nr][nc]: continue cell = grid[nr-1][nc-1] if cell == '.' or cell == 'k': visited[nr][nc] = True q.append((nr, nc)) if cell == 'k': reachable_k.append((nr, nc)) min_total = float('inf') for (i, j) in reachable_k: mod_distance = [[-1]*(W+1) for _ in range(H+1)] mod_q = deque() mod_q.append((1, 1)) mod_distance[1][1] = 0 found = False while mod_q and not found: r, c = mod_q.popleft() if r == H and c == W: found = True break for dr, dc in [(0, 1), (1, 0)]: nr = r + dr nc = c + dc if nr > H or nc > W: continue if mod_distance[nr][nc] != -1: continue # Check if current cell is the modified 'k' or a '.' if (nr == i and nc == j) or grid[nr-1][nc-1] == '.': mod_distance[nr][nc] = mod_distance[r][c] + 1 mod_q.append((nr, nc)) if nr == H and nc == W: found = True break if found: break if found: total = (i + j - 2) + mod_distance[H][W] if total < min_total: min_total = total print(min_total)