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()