結果

問題 No.971 いたずらっ子
コンテスト
ユーザー lam6er
提出日時 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
権限があれば一括ダウンロードができます

ソースコード

diff # 

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)
0