結果

問題 No.3504 Insert Maze
コンテスト
ユーザー Shiny
提出日時 2026-04-18 01:34:00
言語 PyPy3
(7.3.17)
コンパイル:
pypy3 -mpy_compile _filename_
実行:
pypy3 _filename_
結果
AC  
実行時間 327 ms / 2,000 ms
コード長 2,496 bytes
記録
記録タグの例:
初AC ショートコード 純ショートコード 純主流ショートコード 最速実行時間
コンパイル時間 229 ms
コンパイル使用メモリ 85,632 KB
実行使用メモリ 86,764 KB
最終ジャッジ日時 2026-04-18 01:34:27
合計ジャッジ時間 17,516 ms
ジャッジサーバーID
（参考情報） 		judge3_1 / judge1_0
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 85
権限があれば一括ダウンロードができます

ソースコード

diff #
raw source code 

import sys


def main():
    input = sys.stdin.readline
    h, w = map(int, input().split())

    inf = 10 ** 9
    prev_s = '#' * (w + 1)
    prev_cell = [inf] * (w + 1)
    prev_row_gap = [inf] * (w + 1)
    prev_col_gap = [inf] * (w + 1)
    prev_cross = [inf] * (w + 1)

    ans = inf

    for i in range(1, h + 1):
        s = ' ' + input().strip()

        cell = [inf] * (w + 1)
        row_gap = [inf] * (w + 1)
        col_gap = [inf] * (w + 1)
        cross = [inf] * (w + 1)

        for j in range(1, w + 1):
            if s[j] != '#':
                best = inf
                if i == 1 and j == 1:
                    best = 0
                if j > 1 and s[j - 1] != '#':
                    v = cell[j - 1]
                    if v < best:
                        best = v
                if i > 1 and prev_s[j] != '#':
                    v = prev_cell[j]
                    if v < best:
                        best = v
                if j > 1:
                    v = col_gap[j - 1]
                    if v < best:
                        best = v
                if i > 1:
                    v = prev_row_gap[j]
                    if v < best:
                        best = v
                cell[j] = best

            if i < h:
                best = inf
                if s[j] != '#' and cell[j] < inf:
                    best = cell[j] + 1
                if j > 1:
                    v = row_gap[j - 1]
                    if v < best:
                        best = v
                    v = cross[j - 1]
                    if v < best:
                        best = v
                row_gap[j] = best

            if j < w:
                best = inf
                if s[j] != '#' and cell[j] < inf:
                    best = cell[j] + 1
                if i > 1:
                    v = prev_col_gap[j]
                    if v < best:
                        best = v
                    v = prev_cross[j]
                    if v < best:
                        best = v
                col_gap[j] = best

            if i < h and j < w:
                a = row_gap[j]
                b = col_gap[j]
                cross[j] = (a if a < b else b) + 1

        if i == h:
            ans = cell[w]

        prev_s = s
        prev_cell = cell
        prev_row_gap = row_gap
        prev_col_gap = col_gap
        prev_cross = cross

    if ans >= inf:
        print(-1)
    else:
        print(ans + h + w - 2)


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