Buggy python submission (verdict: Time Limit Exceeded):
import itertools
#import copy

input = raw_input
h, w = map(int, input().split(" "))
gh = h - 1
gw = w - 1

#dot_coords = []
#for hi in range(h):
#    wi = 0
#    for c in input():
#        if c == ".":
#            dot_coords.append((wi, hi))
#        wi += 1
        
maps = [list(input()) for _ in range(h)]
#num_maps = [[None for _ in range(w)] for _ in range(h)]

full_count = h+w-2
org_downs = [False for _ in range(h+w-2)]

def main(pattern):
    #down_flags = copy.deepcopy(org_downs)
    #for hi in pattern[:h-1]:
    #    down_flags[hi] = True

    cur_count = 0

    x = 0
    y = 0
    ret = 0
    if maps[y][x] == ".":
        batu_count = 0
    else:
        batu_count = 1

    cur_count += 1
    max_done_down = h-1
    down_count = 0
    down_indexs = pattern
    next_down = down_indexs[down_count] 
    for cur_count in range(full_count):
        isdown = False
        if cur_count == next_down:
            isdown = True
            down_count += 1
            if down_count < max_done_down:
                next_down = down_indexs[down_count] 
            else:
                next_down = None

                

        if isdown:
            y += 1
        else:
            x += 1
        #print(y, x)
        if maps[y][x] == ".":
            if batu_count >= 1:
                ret += 1
                batu_count = 0
        else:
            batu_count += 1
        cur_count += 1

    if batu_count >= 1:
        ret += 1
        batu_count = 0
    return ret



patterns = itertools.combinations(range(h+w-2), h-1)
pi = 0
for pattern in patterns:
    ret = main(pattern)
    if pi == 0:
        out = ret
    else:
        out = min(out, ret)
    pi += 1

print(out)

Fixed submission:
input = raw_input
h, w = map(int, input().split(" "))
gh = h - 1
gw = w - 1

#dot_coords = []
#for hi in range(h):
#    wi = 0
#    for c in input():
#        if c == ".":
#            dot_coords.append((wi, hi))
#        wi += 1
        
maps = [list(input()) for _ in range(h)]
num_maps = [[None for _ in range(w)] for _ in range(h)]

count = 0
def find(sx, sy, cur_cost, color):
    next_cost_coord = []
    global count
    num_r = 1
    found = False
    routes = [(sx, sy)]
    num_maps[sy][sx] = cur_cost
    count += 1

    pre = False
    if sx == 1 and sy == 1:
        pre = True

    while num_r >= 1 and not found:
        x, y = routes[0]
        routes = routes[1:]
        num_r -= 1

        for nx, ny in [(x+1, y), (x, y+1)]:
            if pre:
                pass
                #print("lennummap", len(num_maps))
                #print(num_maps, ny, nx)
                #print(x, y, nx, ny, num_maps[ny][nx], gw, gh, "routes", routes)

            if nx <= gw and ny <= gh:
                if num_maps[ny][nx] is None:
                    if maps[ny][nx] == color:
                        num_maps[ny][nx] = cur_cost
                        if nx == gw and ny == gh:
                            found = True
                            return next_cost_coord, found
                        else:
                            routes.append((nx, ny))
                            num_r += 1
                    else:
                        next_cost_coord.append((nx, ny))
    return next_cost_coord, found

cur_coords = [(0, 0)]
if maps[0][0] == ".":
    cur_cost = 0
else:
    cur_cost = 1

while True:   
    color = "." if cur_cost % 2 == 0 else "#"
    #print("cur_cost", cur_cost, "cur_coords", cur_coords)
    next_coords = []

    in_cost = cur_cost // 2 if cur_cost % 2 == 0 else cur_cost // 2 + 1
    for sx, sy in cur_coords:
        cur_nc_coord, found = find(sx, sy, in_cost, color)
        next_coords += cur_nc_coord
        #print(cur_nc_coord, num_maps)
        found = num_maps[gh][gw] is not None
        if found:
            break
    #print("cur_cost", cur_cost,"num_maps", num_maps)
    if found:
        break
    else:
        #print("test")
        cur_coords = set(next_coords)
        assert len(cur_coords) >= 1
        cur_cost += 1
        #print("cur_cost", cur_cost)

out = num_maps[gh][gw]
print(out)
#print(count)

Buggy python submission (verdict: Time Limit Exceeded):
import itertools
import copy

input = raw_input
h, w = map(int, input().split(" "))
gh = h - 1
gw = w - 1

#dot_coords = []
#for hi in range(h):
#    wi = 0
#    for c in input():
#        if c == ".":
#            dot_coords.append((wi, hi))
#        wi += 1
        
maps = [list(input()) for _ in range(h)]
#num_maps = [[None for _ in range(w)] for _ in range(h)]

org_downs = [False for _ in range(h+w-2)]

def main(pattern):
    down_flags = copy.deepcopy(org_downs)
    for hi in pattern[:h-1]:
        down_flags[hi] = True
    #print("down_flags", down_flags)

    cur_count = 0

    x = 0
    y = 0
    ret = 0
    if maps[y][x] == ".":
        batu_count = 0
    else:
        batu_count = 1
    for isdown in down_flags:
        if isdown:
            y += 1
        else:
            x += 1
        #print(y, x)
        if maps[y][x] == ".":
            if batu_count >= 1:
                ret += 1
                batu_count = 0
        else:
            batu_count += 1

    if batu_count >= 1:
        ret += 1
        batu_count = 0
    return ret



patterns = itertools.permutations(range(h+w-2))
pi = 0
for pattern in patterns:
    ret = main(pattern)
    if pi == 0:
        out = ret
    else:
        out = min(out, ret)
    pi += 1

print(out)

Fixed submission:
input = raw_input
h, w = map(int, input().split(" "))
gh = h - 1
gw = w - 1

#dot_coords = []
#for hi in range(h):
#    wi = 0
#    for c in input():
#        if c == ".":
#            dot_coords.append((wi, hi))
#        wi += 1
        
maps = [list(input()) for _ in range(h)]
num_maps = [[None for _ in range(w)] for _ in range(h)]

count = 0
def find(sx, sy, cur_cost, color):
    next_cost_coord = []
    global count
    num_r = 1
    found = False
    routes = [(sx, sy)]
    num_maps[sy][sx] = cur_cost
    count += 1

    pre = False
    if sx == 1 and sy == 1:
        pre = True

    while num_r >= 1 and not found:
        x, y = routes[0]
        routes = routes[1:]
        num_r -= 1

        for nx, ny in [(x+1, y), (x, y+1)]:
            if pre:
                pass
                #print("lennummap", len(num_maps))
                #print(num_maps, ny, nx)
                #print(x, y, nx, ny, num_maps[ny][nx], gw, gh, "routes", routes)

            if nx <= gw and ny <= gh:
                if num_maps[ny][nx] is None:
                    if maps[ny][nx] == color:
                        num_maps[ny][nx] = cur_cost
                        if nx == gw and ny == gh:
                            found = True
                            return next_cost_coord, found
                        else:
                            routes.append((nx, ny))
                            num_r += 1
                    else:
                        next_cost_coord.append((nx, ny))
    return next_cost_coord, found

cur_coords = [(0, 0)]
if maps[0][0] == ".":
    cur_cost = 0
else:
    cur_cost = 1

while True:   
    color = "." if cur_cost % 2 == 0 else "#"
    #print("cur_cost", cur_cost, "cur_coords", cur_coords)
    next_coords = []

    in_cost = cur_cost // 2 if cur_cost % 2 == 0 else cur_cost // 2 + 1
    for sx, sy in cur_coords:
        cur_nc_coord, found = find(sx, sy, in_cost, color)
        next_coords += cur_nc_coord
        #print(cur_nc_coord, num_maps)
        found = num_maps[gh][gw] is not None
        if found:
            break
    #print("cur_cost", cur_cost,"num_maps", num_maps)
    if found:
        break
    else:
        #print("test")
        cur_coords = set(next_coords)
        assert len(cur_coords) >= 1
        cur_cost += 1
        #print("cur_cost", cur_cost)

out = num_maps[gh][gw]
print(out)
#print(count)

Buggy python submission (verdict: Time Limit Exceeded):
input = raw_input
h, w = map(int, input().split(" "))
gh = h - 1
gw = w - 1

#dot_coords = []
#for hi in range(h):
#    wi = 0
#    for c in input():
#        if c == ".":
#            dot_coords.append((wi, hi))
#        wi += 1
        
maps = [input() for _ in range(h)]
num_maps = [[None for _ in range(w)] for _ in range(h)]

count = 0
next_cost_coord = []
def find(sx, sy, cur_cost):
    num_r = 1
    found = False
    routes = [(sx, sy)]
    num_maps[sy][sx] = cur_cost

    pre = False
    if sx == 1 and sy == 1:
        pre = True

    while num_r >= 1 and not found:
        x, y = routes[0]
        routes = routes[1:]
        num_r -= 1

        for nx, ny in [(x+1, y), (x, y+1)]:
            if pre:
                pass
                #print("lennummap", len(num_maps))
                #print(num_maps, ny, nx)
                #print(x, y, nx, ny, num_maps[ny][nx], gw, gh, "routes", routes)

            if nx <= gw and ny <= gh and num_maps[ny][nx] is None:
                #print(x, y, nx, ny, num_maps[ny][nx], gw, gh, "routes", routes)
                #print("nxny", nx, ny, cur_cost)
                if maps[ny][nx] == ".":
                    num_maps[ny][nx] = cur_cost
                    if nx == gw and ny == gh:
                        found = True
                    else:
                        routes.append((nx, ny))
                        num_r += 1
                else:
                    next_cost_coord.append((nx, ny))
    return next_cost_coord, found

cur_coords = [(0, 0)]
if maps[0][0] == ".":
    cur_cost = 0
else:
    cur_cost = 1

while True:   
    #print("cur_cost", cur_cost, "cur_coords", cur_coords)
    next_coords = []
    for sx, sy in cur_coords:
        cur_nc_coord, found = find(sx, sy, cur_cost)
        next_coords += cur_nc_coord
        #print(cur_nc_coord)
        found = num_maps[gh][gw] is not None
        if found:
            break
    #print("cur_cost", cur_cost,"num_maps", num_maps)
    if found:
        break
    else:
        #print("test")
        cur_coords = next_coords
        assert len(cur_coords) >= 1
        cur_cost += 1
        #print("cur_cost", cur_cost)

out = num_maps[gh][gw]
print(out)

Fixed submission:
input = raw_input
h, w = map(int, input().split(" "))
gh = h - 1
gw = w - 1

#dot_coords = []
#for hi in range(h):
#    wi = 0
#    for c in input():
#        if c == ".":
#            dot_coords.append((wi, hi))
#        wi += 1
        
maps = [list(input()) for _ in range(h)]
num_maps = [[None for _ in range(w)] for _ in range(h)]

count = 0
def find(sx, sy, cur_cost, color):
    next_cost_coord = []
    global count
    num_r = 1
    found = False
    routes = [(sx, sy)]
    num_maps[sy][sx] = cur_cost
    count += 1

    pre = False
    if sx == 1 and sy == 1:
        pre = True

    while num_r >= 1 and not found:
        x, y = routes[0]
        routes = routes[1:]
        num_r -= 1

        for nx, ny in [(x+1, y), (x, y+1)]:
            if pre:
                pass
                #print("lennummap", len(num_maps))
                #print(num_maps, ny, nx)
                #print(x, y, nx, ny, num_maps[ny][nx], gw, gh, "routes", routes)

            if nx <= gw and ny <= gh:
                if num_maps[ny][nx] is None:
                    if maps[ny][nx] == color:
                        num_maps[ny][nx] = cur_cost
                        if nx == gw and ny == gh:
                            found = True
                            return next_cost_coord, found
                        else:
                            routes.append((nx, ny))
                            num_r += 1
                    else:
                        next_cost_coord.append((nx, ny))
    return next_cost_coord, found

cur_coords = [(0, 0)]
if maps[0][0] == ".":
    cur_cost = 0
else:
    cur_cost = 1

while True:   
    color = "." if cur_cost % 2 == 0 else "#"
    #print("cur_cost", cur_cost, "cur_coords", cur_coords)
    next_coords = []

    in_cost = cur_cost // 2 if cur_cost % 2 == 0 else cur_cost // 2 + 1
    for sx, sy in cur_coords:
        cur_nc_coord, found = find(sx, sy, in_cost, color)
        next_coords += cur_nc_coord
        #print(cur_nc_coord, num_maps)
        found = num_maps[gh][gw] is not None
        if found:
            break
    #print("cur_cost", cur_cost,"num_maps", num_maps)
    if found:
        break
    else:
        #print("test")
        cur_coords = set(next_coords)
        assert len(cur_coords) >= 1
        cur_cost += 1
        #print("cur_cost", cur_cost)

out = num_maps[gh][gw]
print(out)
#print(count)