競技プログラミング

AGC043A Range Flip Find Route

問題

https://atcoder.jp/contests/agc043/tasks/agc043_a

方針

公式の解説にもあるように、
どのような操作をしても必ず1しか減らせず、1減らすような操作は必ず存在します。
そこで、動的計画法を用いる。

ポイント

  • スタートマスの1マス左および上のバスはコスト0、それ以外のマスは十分大きい値(1000)とする
  • 白マスから黒マスに移動する際にコストを+1する、ただしスタートマスが黒マスの場合も+1する

そこで、窓の和を求める際に窓の中の要素を全て足すのではなく、一つ隣の窓の和との差分を計算することで、計算量を削減する。

コード

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
H, W = map(int,input().split())
board = []
for h in range(H):
    board.append(input())

dp=[[1000 for i in range(W+1)] for j in range(H+1)]
dp[0][1] = 0
dp[1][0] = 0

for h in range(H):
    for w in range(W):
        dp[h+1][w+1] = min(
            dp[h][w+1] + (board[h][w]=='#' and (h==0 or board[h-1][w]=='.')),
            dp[h+1][w] + (board[h][w]=='#' and (w==0 or board[h][w-1]=='.'))
        )

print (dp[-1][-1])

記事情報

  • 投稿日：2020年3月22日
  • 最終更新日：2020年3月22日