AtCoder Grand Contest 043 A – Range Flip Find Route をPython3で解く

Share

AtCoder上にある問題のうち、AtCoder Problemsでdiff 800以上と判定されているものを順番に解いていく企画。
基本的な考え方は全てコード中のコメントに入れてあるので、参照のこと。

出典:
AtCoder Grand Contest 043 A – Range Flip Find Route

一風変わった経路探索。

まとめて反転できるということはどういうことなのか、きちんと考察してから解いていけば、コードそのものは難しくない。

# AtCoder Grand Contest 043 A - Range Flip Find Route
# https://atcoder.jp/contests/agc043/tasks/agc043_a
# tag: グリッド 経路探索 範囲操作 考察 DP

# 黒のマスを通る場合についてのみ考えてみる。
# ある黒マス A から、ある黒マス B まで黒で経路がつながっている場合、
# A#..   A.##
# .##. → #..#
# ..#B   ##.B
# 上記のような感じになるが、黒マス A, B を含む四角い領域を
# まとめて反転することで、A, B 間につながった白いマスの経路を
# 作成することができる。
# また、上記の経路外の領域が反転後どうなっていたとしても、
# 右か下にのみ移動するという条件から、その前後には影響を
# 及ぼさない。

# したがって、経路上で白マスから黒マスに入るときのみ反転させる
# 回数が増える。逆に、それ以外の場合は回数を増やす必要はない。
# 例えば 白マス経路 → 黒マス経路 → 白マス経路 → 黒マス経路(終点)
# なら、各黒マス経路の部分をまとめて反転すればよく、2回になる。

# よって、最終的には白マス → 黒マスと変わる回数が最小の経路を
# 求めてやることになる。
# これは単純な DP で、最小回数を管理してやればいい。

def main():
    H, W = map(int, input().split())
    field = [input() for _ in range(H)]

    # 初期値は適当に大きめの数
    dpt = [[10**5] * W for _ in range(H)]

    # スタートが黒マスなら、1 回から始める
    if field[0][0] == '.':
        dpt[0][0] = 0
    else:
        dpt[0][0] = 1

    # ここでは、配るDPで書いている。
    # 現在のマス目の数字に対し、次のマス目に数字を配っていく。
    # 白 → 黒 の移動の場合のみ、今のマス目の数字に 1 足したものと、
    # それ以外の場合は今のマス目の数字と、次のマス目の値とを比べ、
    # 小さい数字を採用し、次のマスの数字とする。
    for y in range(H):
        for x in range(W):
            # 横方向
            if x < W - 1:
                if field[y][x] == '.' and field[y][x+1] == '#':
                    w_diff = 1
                else:
                    w_diff = 0
                dpt[y][x+1] = min(dpt[y][x+1], dpt[y][x] + w_diff)

            # 縦方向
            if y < H - 1:
                if field[y][x] == '.' and field[y+1][x] == '#':
                    h_diff = 1
                else:
                    h_diff = 0
                dpt[y+1][x] = min(dpt[y+1][x], dpt[y][x] + h_diff)

    print(dpt[-1][-1])
main()
Share

コメントを残す

メールアドレスが公開されることはありません。