結果

問題 No.971 いたずらっ子
コンテスト
ユーザー stng
提出日時 2022-08-15 17:43:49
言語 PyPy3
(7.3.15)
結果
TLE  
実行時間 -
コード長 1,092 bytes
コンパイル時間 218 ms
コンパイル使用メモリ 82,428 KB
実行使用メモリ 413,984 KB
最終ジャッジ日時 2024-10-02 06:51:09
合計ジャッジ時間 7,011 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge2
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample -- * 4
other TLE * 1 -- * 20
権限があれば一括ダウンロードができます

ソースコード

diff # 

from collections import deque

h,w = map(int,input().split())
a = [input() for i in range(h)]

li = [[10**9]*w for i in range(h)]

d = deque()
d.append([0,0,0,0])
#li[0][0] = 1

ans = 10**9

while len(d):
    x,y,c,s = d.popleft()
    if x == w-1 and y == h-1:
        ans = min(ans,c)
        #print(ans)
        break
    #if a[y][x] == "k":
    #    d.append([x,y,2*c])
    #    li[y][x] = 2*c
        #print(d)
    else:
        if x+1 < w:
            if a[y][x] != "k":
                if li[y][x+1] > c+1:
                    li[y][x+1] = c+1
                    d.append([x+1,y,c+1,s+1])
            else:
                if li[y][x+1] > c+s+1:
                    li[y][x+1] = c+s+1
                    d.append([x+1,y,c+s+1,s+1])
        if y+1 < h:
            if a[y][x] != "k":
                if li[y+1][x] > c+1:
                    li[y+1][x] = c+1
                    d.append([x,y+1,c+1,s+1])
            else:
                if li[y+1][x] > c+s+1:
                    li[y+1][x] = c+s+1
                    d.append([x,y+1,c+s+1,s+1])
    #print(d)
    #exit()

print(ans)
0