Buggy python submission (verdict: Time Limit Exceeded):
# import bisect
from collections import Counter, deque
# import copy
# from heapq import heappush, heappop, heapify
# from fractions import gcd
# import itertools
# from operator import attrgetter, itemgetter
# import math

import sys

# import numpy as np

readline = sys.stdin.readline
MOD = 10 ** 9 + 7
INF = float('INF')
sys.setrecursionlimit(10 ** 5)


def main():
    h, w = list(map(int, readline().split()))

    s = [input() for _ in range(h)]
    n = [[INF] * w for _ in range(h)]

    if s[0][0] == "#":
        wall = 1
        state = True
    else:
        wall = 0
        state = False

    que = deque()
    que.append((0, 0, wall, state))

    while que:
        y, x, wall, state = que.popleft()
        n[y][x] = min(n[y][x], wall)
        ny = y + 1
        nx = x + 1

        if state:
            if ny < h:
                if s[ny][x] == "#":
                    que.append((ny, x, wall, True))
                elif s[ny][x] == ".":
                    que.append((ny, x, wall, False))

            if nx < w:
                if s[y][nx] == "#":
                    que.append((y, nx, wall, True))
                elif s[y][nx] == ".":
                    que.append((y, nx, wall, False))
        else:
            if ny < h:
                if s[ny][x] == "#":
                    que.append((ny, x, wall + 1, True))
                elif s[ny][x] == ".":
                    que.append((ny, x, wall, False))

            if nx < w:
                if s[y][nx] == "#":
                    que.append((y, nx, wall + 1, True))
                elif s[y][nx] == ".":
                    que.append((y, nx, wall, False))

    print(n[h - 1][w - 1])


if __name__ == '__main__':
    main()


Fixed submission:
# import bisect
from collections import Counter, deque
# import copy
# from heapq import heappush, heappop, heapify
# from fractions import gcd
# import itertools
# from operator import attrgetter, itemgetter
# import math

import sys

# import numpy as np

readline = sys.stdin.readline
MOD = 10 ** 9 + 7
INF = float('INF')
sys.setrecursionlimit(10 ** 5)


def main():
    h, w = list(map(int, readline().split()))

    s = [input() for _ in range(h)]
    n = [[INF] * w for _ in range(h)]

    que1 = deque()
    que2 = deque()

    if s[0][0] == "#":
        n[0][0] = 1
        que2.append((0, 0))
    else:
        n[0][0] = 0
        que1.append((0, 0))

    wall = 0
    while True:
        while que1:
            y, x = que1.popleft()
            ny = y + 1
            nx = x + 1
            if y == h - 1 and x == w - 1:
                print(wall)
                sys.exit()

            if ny < h and n[ny][x] == INF:
                if s[ny][x] == "#":
                    n[ny][x] = min(n[ny][x], wall + 1)
                    que2.append((ny, x))
                elif s[ny][x] == ".":
                    n[ny][x] = min(n[ny][x], wall)
                    que1.append((ny, x))

            if nx < w and n[y][nx] == INF:
                if s[y][nx] == "#":
                    n[y][nx] = min(n[y][nx], wall + 1)
                    que2.append((y, nx))
                elif s[y][nx] == ".":
                    n[y][nx] = min(n[y][nx], wall)
                    que1.append((y, nx))

        wall += 1
        while que2:
            y, x = que2.popleft()
            ny = y + 1
            nx = x + 1
            if y == h - 1 and x == w - 1:
                print(wall)
                sys.exit()

            if ny < h and n[ny][x] == INF:
                if s[ny][x] == "#":
                    n[ny][x] = min(n[ny][x], wall)
                    que2.append((ny, x))
                elif s[ny][x] == ".":
                    n[ny][x] = min(n[ny][x], wall)
                    que1.append((ny, x))

            if nx < w and n[y][nx] == INF:
                if s[y][nx] == "#":
                    n[y][nx] = min(n[y][nx], wall + 1)
                    que2.append((y, nx))
                elif s[y][nx] == ".":
                    n[y][nx] = min(n[y][nx], wall)
                    que1.append((y, nx))

    print(n[h - 1][w - 1])


if __name__ == '__main__':
    main()