Buggy python submission (verdict: Time Limit Exceeded):
# coding: utf-8
import itertools
H, W = list(map(int, input().split()))
S = []
for _ in range(H):
    S.append(list(input()))

_w = list(range(H+W-2))

min_change = H * W
paths = list(itertools.combinations(_w,W-1))
for path in paths:
    state = [0, 0]
    pathway = [0] * (H+W-2)
    change = 0
    for i in path:
        pathway[i] = 1
    # init Flag
    black_flag = True if S[0][0] == '#' else False
    
    for go in pathway:
        state[go] += 1
        if S[state[0]][state[1]] == '#':
            if state == [H-1, W-1]:
                change += 1
                break
            if black_flag:
                continue
            else:
                black_flag = True
        else:
            if black_flag:
                change += 1
                black_flag = False
            else:
                continue
    if min_change > change:
        min_change = change

print(min_change)

Fixed submission:
# coding: utf-8
H, W = list(map(int, input().split()))
S = []
for _ in range(H):
    S.append(list(input()))

grid = [[0 for _ in range(W)] for _ in range(H)]

for h in range(1,H):
  if S[h-1][0] == '#' and S[h][0] == '.':
    grid[h][0] = grid[h-1][0] + 1
  else:
    grid[h][0] = grid[h-1][0]
    
for w in range(1,W):
  if S[0][w-1] == '#' and S[0][w] == '.':
    grid[0][w] = grid[0][w-1] + 1
  else:
    grid[0][w] = grid[0][w-1]
for w in range(1,W):
  for h in range(1,H):
    if S[h-1][w] == '#' and S[h][w] == '.':
      next_h = grid[h-1][w] + 1
    else:
      next_h = grid[h-1][w]      
    if S[h][w-1] == '#' and S[h][w] == '.':
      next_w = grid[h][w-1] + 1
    else:
      next_w = grid[h][w-1]
    grid[h][w] = min([next_w, next_h])
if S[H-1][W-1] == '#':
  grid[H-1][W-1] += 1
print(grid[H-1][W-1])

Buggy python submission (verdict: Time Limit Exceeded):
import itertools
H, W = list(map(int, input().split()))
S = []
for _ in range(H):
    S.append(list(input()))

_w = list(range(H+W-2))

min_change = H * W

for path in itertools.combinations(_w,W-1):
    state = [0, 0]
    pathway = [0] * (H+W-2)
    path = list(path)
    change = 0
    for i in path:
        pathway[i] = 1
    # init Flag
    black_flag = True if S[0][0] == '#' else False
    
    for go in pathway:
        state[go] += 1
        if S[state[0]][state[1]] == '#':
            if state == [H-1, W-1]:
                change += 1
                break
            if black_flag:
                continue
            else:
                black_flag = True
        else:
            if black_flag:
                change += 1
            else:
                continue
    if min_change > change:
        min_change = change
print(min_change)

Fixed submission:
# coding: utf-8
H, W = list(map(int, input().split()))
S = []
for _ in range(H):
    S.append(list(input()))

grid = [[0 for _ in range(W)] for _ in range(H)]

for h in range(1,H):
  if S[h-1][0] == '#' and S[h][0] == '.':
    grid[h][0] = grid[h-1][0] + 1
  else:
    grid[h][0] = grid[h-1][0]
    
for w in range(1,W):
  if S[0][w-1] == '#' and S[0][w] == '.':
    grid[0][w] = grid[0][w-1] + 1
  else:
    grid[0][w] = grid[0][w-1]
for w in range(1,W):
  for h in range(1,H):
    if S[h-1][w] == '#' and S[h][w] == '.':
      next_h = grid[h-1][w] + 1
    else:
      next_h = grid[h-1][w]      
    if S[h][w-1] == '#' and S[h][w] == '.':
      next_w = grid[h][w-1] + 1
    else:
      next_w = grid[h][w-1]
    grid[h][w] = min([next_w, next_h])
if S[H-1][W-1] == '#':
  grid[H-1][W-1] += 1
print(grid[H-1][W-1])

Buggy python submission (verdict: Time Limit Exceeded):
import itertools
H, W = list(map(int, input().split()))
S = []
for _ in range(H):
    S.append(list(input()))

_w = list(range(H+W-2))

changes = []
for path in itertools.combinations(_w,W-1):
    state = [0, 0]
    pathway = [0] * (H+W-2)
    path = list(path)
    change = 0
    for i in path:
        pathway[i] = 1
    # init Flag
    black_flag = True if S[0][0] == '#' else False
    
    for go in pathway:
        state[go] += 1
        if S[state[0]][state[1]] == '#':
            if state == [H-1, W-1]:
                change += 1
                break
            if black_flag:
                continue
            else:
                black_flag = True
        else:
            if black_flag:
                change += 1
            else:
                continue
    changes.append(change)
print(min(changes))
#print(changes)

Fixed submission:
# coding: utf-8
H, W = list(map(int, input().split()))
S = []
for _ in range(H):
    S.append(list(input()))

grid = [[0 for _ in range(W)] for _ in range(H)]

for h in range(1,H):
  if S[h-1][0] == '#' and S[h][0] == '.':
    grid[h][0] = grid[h-1][0] + 1
  else:
    grid[h][0] = grid[h-1][0]
    
for w in range(1,W):
  if S[0][w-1] == '#' and S[0][w] == '.':
    grid[0][w] = grid[0][w-1] + 1
  else:
    grid[0][w] = grid[0][w-1]
for w in range(1,W):
  for h in range(1,H):
    if S[h-1][w] == '#' and S[h][w] == '.':
      next_h = grid[h-1][w] + 1
    else:
      next_h = grid[h-1][w]      
    if S[h][w-1] == '#' and S[h][w] == '.':
      next_w = grid[h][w-1] + 1
    else:
      next_w = grid[h][w-1]
    grid[h][w] = min([next_w, next_h])
if S[H-1][W-1] == '#':
  grid[H-1][W-1] += 1
print(grid[H-1][W-1])