Buggy python submission (verdict: Time Limit Exceeded):
from collections import deque

H, W = map(int, input().split())
s = [list(input()) for _ in range(H)]

def next_positions(current_position):
    output = []
    for udrl in [[0,1],[1,0]]:
        y = current_position[0]+udrl[0]
        x = current_position[1]+udrl[1]
        if 0 <= y <= H-1 and 0 <= x <= W-1:
            output.append([y,x,s[y][x]])
    if len(output) == 2:
        if output[0][2] == current_position[2] and output[1][2] != current_position[2]:
            del output[1]
        elif output[0][2] != current_position[2] and output[1][2] == current_position[2]:
            del output[0]
    return output

d = deque([[0,0,s[0][0]]])
distance = [[float("inf")]*W for _ in range(H)]
if s[0][0] == ".":
    distance[0][0] = 0
else:
    distance[0][0] = 1

while d:
    current_position = d.popleft()
    for q in next_positions(current_position):
        if s[int(q[0])][int(q[1])] == s[0][0] and current_position[2] != s[0][0]:
            distance[int(q[0])][int(q[1])] = min(distance[int(q[0])][int(q[1])], distance[current_position[0]][current_position[1]] + 1)
        else:
            distance[int(q[0])][int(q[1])] = min(distance[int(q[0])][int(q[1])], distance[current_position[0]][current_position[1]])
        d.append(q)

print(distance[H-1][W-1])

Fixed submission:
from collections import deque

H, W = map(int, input().split())
s = [list(input()) for _ in range(H)]

d = deque([[0,0,s[0][0]]])
distance = [[float("inf")]*W for _ in range(H)]
if s[0][0] == ".":
    distance[0][0] = 0
else:
    distance[0][0] = 1

while d:
    y, x, c = d.popleft()
    for new_y, new_x in ([int(y)+1, int(x)], [int(y), int(x)+1]):
        if 0 <= new_y <= H-1 and 0 <= new_x <= W-1:
            if c == "." and s[new_y][new_x] == "#":
                new_cost = distance[y][x] + 1
            else:
                new_cost = distance[y][x]
            if new_cost < distance[new_y][new_x]:
                distance[new_y][new_x] = new_cost
                d.append([new_y, new_x, s[new_y][new_x]])

print(distance[H-1][W-1])

Buggy python submission (verdict: Time Limit Exceeded):
from collections import deque

H, W = map(int, input().split())
s = [list(input()) for _ in range(H)]

def next_positions(current_position):
    output = []
    for udrl in [[0,1],[1,0]]:
        y = current_position[0]+udrl[0]
        x = current_position[1]+udrl[1]
        if 0 <= y <= H-1 and 0 <= x <= W-1:
            output.append([y,x])
    return output

d = deque([[0,0]])
distance = [[float("inf")]*W for _ in range(H)]
if s[0][0] == ".":
    distance[0][0] = 0
else:
    distance[0][0] = 1

while d:
    current_position = d.popleft()
    for q in next_positions(current_position):
        if s[q[0]][q[1]] == ".":
            distance[q[0]][q[1]] = min(distance[q[0]][q[1]], distance[current_position[0]][current_position[1]])
        else:
            distance[q[0]][q[1]] = min(distance[q[0]][q[1]], distance[current_position[0]][current_position[1]] + 1)
        d.append(q)

print(distance[H-1][W-1])

Fixed submission:
from collections import deque

H, W = map(int, input().split())
s = [list(input()) for _ in range(H)]

d = deque([[0,0,s[0][0]]])
distance = [[float("inf")]*W for _ in range(H)]
if s[0][0] == ".":
    distance[0][0] = 0
else:
    distance[0][0] = 1

while d:
    y, x, c = d.popleft()
    for new_y, new_x in ([int(y)+1, int(x)], [int(y), int(x)+1]):
        if 0 <= new_y <= H-1 and 0 <= new_x <= W-1:
            if c == "." and s[new_y][new_x] == "#":
                new_cost = distance[y][x] + 1
            else:
                new_cost = distance[y][x]
            if new_cost < distance[new_y][new_x]:
                distance[new_y][new_x] = new_cost
                d.append([new_y, new_x, s[new_y][new_x]])

print(distance[H-1][W-1])

Buggy python submission (verdict: Time Limit Exceeded):
from collections import deque

H, W = map(int, input().split())
s = [list(input()) for _ in range(H)]

def next_positions(current_position):
    output = []
    for udrl in [[0,1],[1,0]]:
        y = current_position[0]+udrl[0]
        x = current_position[1]+udrl[1]
        if 0 <= y <= H-1 and 0 <= x <= W-1:
            output.append([y,x])
    return output

d = deque([[0,0]])
distance = [[float("inf")]*W for _ in range(H)]
if s[0][0] == ".":
    distance[0][0] = 0
else:
    distance[0][0] = 1

while d:
    current_position = d.popleft()
    for q in next_positions(current_position):
        if s[q[0]][q[1]] == ".":
            distance[q[0]][q[1]] = min(distance[q[0]][q[1]], distance[current_position[0]][current_position[1]])
        else:
            distance[q[0]][q[1]] = min(distance[q[0]][q[1]], distance[current_position[0]][current_position[1]] + 1)
        d.append(q)

print(distance[H-1][W-1])

Fixed submission:
from collections import deque

H, W = map(int, input().split())
s = [list(input()) for _ in range(H)]

d = deque([[0,0,s[0][0]]])
distance = [[float("inf")]*W for _ in range(H)]
if s[0][0] == ".":
    distance[0][0] = 0
else:
    distance[0][0] = 1

while d:
    y, x, c = d.popleft()
    for new_y, new_x in ([int(y)+1, int(x)], [int(y), int(x)+1]):
        if 0 <= new_y <= H-1 and 0 <= new_x <= W-1:
            if c == "." and s[new_y][new_x] == "#":
                new_cost = distance[y][x] + 1
            else:
                new_cost = distance[y][x]
            if new_cost < distance[new_y][new_x]:
                distance[new_y][new_x] = new_cost
                d.append([new_y, new_x, s[new_y][new_x]])

print(distance[H-1][W-1])