結果

問題 No.971 いたずらっ子
コンテスト
ユーザー gew1fw
提出日時 2025-06-12 16:25:41
言語 PyPy3
(7.3.15)
結果
MLE  
実行時間 -
コード長 1,171 bytes
コンパイル時間 183 ms
コンパイル使用メモリ 82,772 KB
実行使用メモリ 687,872 KB
最終ジャッジ日時 2025-06-12 16:26:09
合計ジャッジ時間 10,242 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge5
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample -- * 4
other WA * 1 MLE * 5 -- * 15
権限があれば一括ダウンロードができます

ソースコード

diff # 

import sys
from collections import deque

def main():
    H, W = map(int, sys.stdin.readline().split())
    grid = []
    for _ in range(H):
        line = sys.stdin.readline().strip()
        grid.append(list(line))
    
    INF = float('inf')
    dist = [[[INF] * 2 for _ in range(W + 1)] for __ in range(H + 1)]
    
    dist[1][1][0] = 0
    q = deque()
    q.append((1, 1, 0))
    
    dirs = [(0, 1), (1, 0)]  # east, south
    
    while q:
        r, c, s = q.popleft()
        current_dist = dist[r][c][s]
        
        for dr, dc in dirs:
            nr = r + dr
            nc = c + dc
            if nr > H or nc > W:
                continue
            
            new_dist = current_dist + 1
            if grid[nr-1][nc-1] == 'k':
                new_s = 1
                if new_dist < dist[1][1][new_s]:
                    dist[1][1][new_s] = new_dist
                    q.append((1, 1, new_s))
            else:
                if new_dist < dist[nr][nc][s]:
                    dist[nr][nc][s] = new_dist
                    q.append((nr, nc, s))
    
    x = min(dist[H][W][0], dist[H][W][1])
    print(x)

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