Buggy python submission (verdict: Time Limit Exceeded):
def dijkstra(s, n, cost):
    # 始点sから各頂点への最短距離
    # n:頂点数, cost[u][v] : 辺uvのコスト(存在しないときはinf)
    d = [float("inf")] * n
    used = [False] * n
    d[s] = 0
    R = {}

    while True:
        v = -1
        # まだ使われてない頂点の中から最小の距離のものを探す
        for i in range(n):
            if (not used[i]) and (v == -1):
                v = i
            elif (not used[i]) and d[i] < d[v]:
                v = i
        if v == -1:
            break
        used[v] = True

        for j in range(n):
            if d[j] > d[v]+cost[v][j]:
                R[j] = (v, j)
            d[j] = min(d[j], d[v]+cost[v][j])

    result = []
    result.append(n-1)
    cur = n-1
    while True:
        cur_next = R[cur][0]
        result.append(cur_next)
        cur = cur_next
        if cur == 0:
            break
    return result[::-1]
    # return d[n-1]


def _dijkstra():
    # n, w = map(int, input().split())  # n:頂点数　w:辺の数
    H, W = list(map(int, input().split()))
    A = []
    for _ in range(H):
        s = input()
        A.append(s)

    n = H * W

    cost = [[float("inf") for i in range(n)] for i in range(n)]
    # cost[u][v] : 辺uvのコスト(存在しないときはinf この場合は10**10)
    for i in range(H):
        for j in range(W):
            id = i * W + j
            # right
            if j != W-1:
                if A[i][j+1] == '.':
                    cost[id][id+1] = 1
                elif A[i][j+1] == '#':
                    cost[id][id+1] = 100000
                else:
                    raise Exception
            # down
            if i != H-1:
                if A[i+1][j] == '.':
                    cost[id][id+W] = 1
                elif A[i+1][j] == '#':
                    cost[id][id+W] = 100000
                else:
                    raise Exception
    route = dijkstra(0, n, cost)

    result = 0
    now_mark = A[0][0]
    if(now_mark) == '#':
        result += 1

    for id in route[1:]:

        i = id // W
        j = id % W
        next_mark = A[i][j]
        if now_mark == '.' and next_mark == '#':
            result += 1
        now_mark = next_mark
    print(result)


if __name__ == "__main__":
    _dijkstra()


Fixed submission:
if __name__ == "__main__":
    H, W = list(map(int, input().split()))
    A = []
    for _ in range(H):
        s = input()
        A.append(s)

    cost = [[float("inf") for i in range(W)] for i in range(H)]

    cost[0][0] = 1 if A[0][0] == '#' else 0

    for i in range(H)[1:]:
        if A[i-1][0] == '.' and A[i][0] == '#':
            cost[i][0] = cost[i-1][0] + 1
        else:
            cost[i][0] = cost[i-1][0]

    for j in range(W)[1:]:
        if A[0][j-1] == '.' and A[0][j] == '#':
            cost[0][j] = cost[0][j-1] + 1
        else:
            cost[0][j] = cost[0][j-1]

    for i in range(H)[1:]:
        for j in range(W)[1:]:

            # right
            if A[i][j-1] == '.' and A[i][j] == '#':
                cost_right = cost[i][j-1] + 1
            else:
                cost_right = cost[i][j-1]

            # down
            if A[i-1][j] == '.' and A[i][j] == '#':
                cost_down = cost[i-1][j] + 1
            else:
                cost_down = cost[i-1][j]

            cost[i][j] = min(cost_down, cost_right)

    # print(cost)
    print(cost[H-1][W-1])