Buggy python submission (verdict: Time Limit Exceeded):
from math import ceil

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

n = h * w

dp = [[[float("inf")] * 2 for _ in range(n + 1)] for _ in range(n + 1)]
if s[0][0] == "#":
    dp[1][1][1] = 1
else:
    dp[1][1][0] = 0

for i in range(1, h + 1):
    for j in range(1, w + 1):
        if s[i-1][j-1] == "#":
            dp[i][j][1] = min(dp[i][j][1], dp[i-1][j][0] + 1, dp[i-1][j][1], dp[i][j-1][0] + 1, dp[i][j-1][1])
        else:
            dp[i][j][0] = min(dp[i][j][0], dp[i-1][j][0], dp[i-1][j][1] + 1, dp[i][j-1][0], dp[i][j-1][1] + 1)

idx = 1 if s[h-1][w-1] == "#" else 0
ans = dp[h][w][idx]
ans = ceil(ans / 2)
print(ans)


Fixed submission:
from math import ceil
from collections import defaultdict

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

n = h * w
INF = 100 * 100

dp = defaultdict(lambda: INF)
if s[0][0] == "#":
    dp[(1, 1, 1)] = 1
else:
    dp[(1, 1, 0)] = 0

for i in range(1, h + 1):
    for j in range(1, w + 1):
        if s[i-1][j-1] == "#":
            dp[(i, j, 1)] = min(dp[(i, j, 1)], dp[(i-1, j, 0)] + 1, dp[(i-1, j, 1)], dp[(i, j-1, 0)] + 1, dp[(i, j-1, 1)])
        else:
            dp[(i, j, 0)] = min(dp[(i, j, 0)], dp[(i-1, j, 0)], dp[(i-1, j, 1)] + 1, dp[(i, j-1, 0)], dp[(i, j-1, 1)] + 1)

idx = 1 if s[h-1][w-1] == "#" else 0
ans = dp[(h, w, idx)]
ans = ceil(ans / 2)
print(ans)

Buggy python submission (verdict: Time Limit Exceeded):
import sys
sys.setrecursionlimit(10 ** 7)

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

d = [[1, 0], [0, 1]]

ans = float("inf")


def dfs(hh, ww, c, cnt):
    if hh == h - 1 and ww == w - 1:
        global ans
        ans = min(ans, cnt)

    for dh, dw in d:
        nh = hh + dh
        nw = ww + dw
        if nh < h and nw < w:
            if c == "#":
                dfs(nh, nw, s[nh][nw], cnt)
            else:
                if s[nh][nw] == "#":
                    dfs(nh, nw, s[nh][nw], cnt + 1)
                else:
                    dfs(nh, nw, s[nh][nw], cnt)


dfs(0, 0, s[0][0], 0)
if s[0][0] == "#":
    ans += 1
print(ans)


Fixed submission:
from math import ceil
from collections import defaultdict

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

n = h * w
INF = 100 * 100

dp = defaultdict(lambda: INF)
if s[0][0] == "#":
    dp[(1, 1, 1)] = 1
else:
    dp[(1, 1, 0)] = 0

for i in range(1, h + 1):
    for j in range(1, w + 1):
        if s[i-1][j-1] == "#":
            dp[(i, j, 1)] = min(dp[(i, j, 1)], dp[(i-1, j, 0)] + 1, dp[(i-1, j, 1)], dp[(i, j-1, 0)] + 1, dp[(i, j-1, 1)])
        else:
            dp[(i, j, 0)] = min(dp[(i, j, 0)], dp[(i-1, j, 0)], dp[(i-1, j, 1)] + 1, dp[(i, j-1, 0)], dp[(i, j-1, 1)] + 1)

idx = 1 if s[h-1][w-1] == "#" else 0
ans = dp[(h, w, idx)]
ans = ceil(ans / 2)
print(ans)

Buggy python submission (verdict: Time Limit Exceeded):
import sys
sys.setrecursionlimit(10 ** 7)

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

d = [[1, 0], [0, 1]]

ans = float("inf")


def dfs(hh, ww, c, cnt):
    if hh == h - 1 and ww == w - 1:
        global ans
        ans = min(ans, cnt)

    for dh, dw in d:
        nh = hh + dh
        nw = ww + dw
        if nh < h and nw < w:
            if c == "#":
                dfs(nh, nw, s[nh][nw], cnt)
            else:
                if s[nh][nw] == "#":
                    dfs(nh, nw, s[nh][nw], cnt + 1)
                else:
                    dfs(nh, nw, s[nh][nw], cnt)


dfs(0, 0, s[0][0], 0)
if s[0][0] == "#":
    ans += 1
print(ans)


Fixed submission:
from math import ceil
from collections import defaultdict

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

n = h * w
INF = 100 * 100

dp = defaultdict(lambda: INF)
if s[0][0] == "#":
    dp[(1, 1, 1)] = 1
else:
    dp[(1, 1, 0)] = 0

for i in range(1, h + 1):
    for j in range(1, w + 1):
        if s[i-1][j-1] == "#":
            dp[(i, j, 1)] = min(dp[(i, j, 1)], dp[(i-1, j, 0)] + 1, dp[(i-1, j, 1)], dp[(i, j-1, 0)] + 1, dp[(i, j-1, 1)])
        else:
            dp[(i, j, 0)] = min(dp[(i, j, 0)], dp[(i-1, j, 0)], dp[(i-1, j, 1)] + 1, dp[(i, j-1, 0)], dp[(i, j-1, 1)] + 1)

idx = 1 if s[h-1][w-1] == "#" else 0
ans = dp[(h, w, idx)]
ans = ceil(ans / 2)
print(ans)