Problem:
 Score : 400 points    Problem Statement Consider a grid with H rows and W columns of squares. Let (r, c) denote the square at the r -th row from the top and the c -th column from the left.
Each square is painted black or white.  The grid is said to be good if and only if the following condition is satisfied:   From (1, 1) , we can reach (H, W) by moving one square right or down repeatedly, while always being on a white square.   Note that (1, 1) and (H, W) must be white if the grid is good.  Your task is to make the grid good by repeating the operation below. Find the minimum number of operations needed to complete the task. It can be proved that you can always complete the task in a finite number of operations.   Choose four integers r_0, c_0, r_1, c_1(1 \leq r_0 \leq r_1 \leq H, 1 \leq c_0 \leq c_1 \leq W) . For each pair r, c ( r_0 \leq r \leq r_1, c_0 \leq c \leq c_1 ), invert the color of (r, c) - that is, from white to black and vice versa.       Constraints  2 \leq H, W \leq 100         Input Input is given from Standard Input in the following format:  H  W  s_{11} s_{12} \cdots s_{1W}  s_{21} s_{22} \cdots s_{2W}  \vdots  s_{H1} s_{H2} \cdots s_{HW}   Here s_{rc} represents the color of (r, c) - # stands for black, and . stands for white.      Output Print the minimum number of operations needed.        Sample Input 1 3 3
.##
.#.
##.      Sample Output 1 1  Do the operation with (r_0, c_0, r_1, c_1) = (2, 2, 2, 2) to change just the color of (2, 2) , and we are done.       Sample Input 2 2 2
#.
.#      Sample Output 2 2       Sample Input 3 4 4
..##
#...
###.
###.      Sample Output 3 0  No operation may be needed.       Sample Input 4 5 5
.#.#.
#.#.#
.#.#.
#.#.#
.#.#.      Sample Output 4 4

Solution (Python):
H, W = map(int, input().split())
li = []
for i in range(H):
    li.append(list(input()))

class tree:
    def __init__(self):
        self.num = 0
        self.borw = 0
li2 = [[tree() for i in range(W)]for j in range(H)]
for i in range(H):
    for j in range(W):
        if li[i][j] == "
            li2[i][j].borw = 1
        else:
            li2[i][j].borw = 0
for i in range(H):
    for j in range(W):
        numA = 0
        numB = 0
        if i == 0 and j == 0:
            li2[i][j].num = 0
            if li2[i][j].borw == 1:
                li2[i][j].num = 1
        else:
            if i == 0:
                li2[i][j].num = li2[i][j-1].num
                if li2[i][j-1].borw == 0 and li2[i][j].borw == 1:
                    li2[i][j].num += 1
            if j == 0:
                li2[i][j].num = li2[i-1][j].num
                if li2[i-1][j].borw == 0 and li2[i][j].borw == 1:
                    li2[i][j].num += 1
            if i != 0 and j != 0:
                numA = li2[i][j-1].num
                if li2[i][j-1].borw == 0 and li2[i][j].borw == 1:
                    numA += 1
                numB = li2[i-1][j].num
                if li2[i-1][j].borw == 0 and li2[i][j].borw == 1:
                    numB += 1
                li2[i][j].num = min(numA, numB)

print(li2[H-1][W-1].num)

Solution (Python):
from collections import deque
import sys
input = sys.stdin.readline
import numpy as np

H, W = map(int, input().split())
c = [input() for _ in range(H)]
si = sj =0

dist = [[-1] * W for _ in range(H)]
dist[0][0] = 0
queue = deque()
queue.append((0,0))
move = [(1, 0), (0, 1)]
while queue:
    i, j = queue.popleft()
    for di, dj in move:
        ni, nj = i+di, j+dj
        if 0 <= ni < H and 0 <= nj < W and dist[ni][nj] == -1:
            if c[ni][nj] == c[i][j]:
                dist[ni][nj] =dist[i][j]
                queue.appendleft((ni,nj))
            else:
                dist[ni][nj] =dist[i][j] +1
                queue.append((ni,nj))

if dist[-1][-1]%2==1:
  ans=dist[-1][-1]//2+1
else:
  if c[0][0]==".":
    ans=dist[-1][-1]//2
  else:
    ans=dist[-1][-1]//2+1

print(ans)

Solution (Python):
import sys,collections as cl,bisect as bs
sys.setrecursionlimit(100000)
input = sys.stdin.readline
mod = 10**9+7
Max = sys.maxsize
def l(): 
    return list(map(int,input().split()))
def m(): 
    return map(int,input().split())
def onem(): 
    return int(input())
def s(x): 
    a = []
    if len(x) == 0:
        return []
    aa = x[0]
    su = 1
    for i in range(len(x)-1):
        if aa != x[i+1]:
            a.append([aa,su])
            aa = x[i+1]
            su = 1
        else:
            su += 1
    a.append([aa,su])
    return a
def jo(x): 
    return " ".join(map(str,x))
def max2(x): 
    return max(map(max,x))
def In(x,a): 
    k = bs.bisect_left(a,x)
    if k != len(a) and a[k] ==  x:
        return True
    else:
        return False
"""
def nibu(x,n,r):
    ll = 0
    rr = r
    while True:
        mid = (ll+rr)//2

    if rr == mid:
        return ll
    if (ここに評価入れる):
        rr = mid
    else:
        ll = mid+1
"""


H,W = m()

po = [list(input()) for i in range(H)]

aaa = [[[mod,0] for i in range(W)] for j in range(H)]
aa = [[[mod,0] for i in range(W)] for j in range(H)]

if po[0][0] == "
    aaa[0][0] = [1,3]
else:
    aaa[0][0] = [0,0]

for i in range(H):
    if i == 0:
        for j in range(1,W):
            if po[i][j] == "
                if aaa[i][j-1][1] == 0:
                    aaa[i][j][0] = min(aaa[i][j][0],aaa[i][j-1][0]+1)
                    aaa[i][j][1] = 3
                elif aaa[i][j-1][1] == 1 or aaa[i][j-1][1] == 3:
                    aaa[i][j][0] = min(aaa[i][j][0],aaa[i][j-1][0])
                    aaa[i][j][1] = 3
            else:
                aaa[i][j][0] = min(aaa[i][j][0],aaa[i][j-1][0])

    else:
        for j in range(W):
            if j == 0:
                if po[i][j] == "
                    if aaa[i-1][j][1] == 0:
                        aaa[i][j][0] = min(aaa[i][j][0],aaa[i-1][j][0]+1)
                        aaa[i][j][1] = 3
                    elif aaa[i-1][j][1] == 3 or aaa[i-1][j][1] == 2:
                        aaa[i][j][0] = min(aaa[i][j][0],aaa[i-1][j][0])
                        aaa[i][j][1] = 3
                else:
                    aaa[i][j][0] = min(aaa[i][j][0],aaa[i-1][j][0])
            else:
                if po[i][j] == "
                    if aaa[i-1][j][1] == 0 or aaa[i-1][j][1] == 1:
                        if aaa[i][j-1][1] == 0 or aaa[i][j-1][1] == 2:
                            aaa[i][j][0] = min(aaa[i][j][0],aaa[i][j-1][0]+1,aaa[i-1][j][0]+1)
                            aaa[i][j][1] = 3
                        elif aaa[i][j-1][1] == 1:
                            aaa[i][j][0] = min(aaa[i][j][0],aaa[i][j-1][0],aaa[i-1][j][0]+1)
                            aaa[i][j][1] = 3
                        elif aaa[i][j-1][1] == 3:
                            aaa[i][j][0] = min(aaa[i][j][0],aaa[i][j-1][0],aaa[i-1][j][0]+1)
                            aaa[i][j][1] = 3
                    elif aaa[i-1][j][1] == 2:
                        if aaa[i][j-1][1] == 0 or aaa[i][j-1][1] == 2:
                            aaa[i][j][0] = min(aaa[i][j][0],aaa[i][j-1][0]+1,aaa[i-1][j][0])
                            aaa[i][j][1] = 3
                        elif aaa[i][j-1][1] == 1:
                            aaa[i][j][0] = min(aaa[i][j][0],aaa[i][j-1][0],aaa[i-1][j][0])
                            aaa[i][j][1] = 3
                        elif aaa[i][j-1][1] == 3:
                            aaa[i][j][0] = min(aaa[i][j][0],aaa[i][j-1][0],aaa[i-1][j][0])
                            aaa[i][j][1] = 3
                    elif aaa[i-1][j][1] == 3:
                        if aaa[i][j-1][1] == 0 or aaa[i][j-1][1] == 2:
                            aaa[i][j][0] = min(aaa[i][j][0],aaa[i][j-1][0]+1,aaa[i-1][j][0])
                            aaa[i][j][1] = 3
                        elif aaa[i][j-1][1] == 1:
                            aaa[i][j][0] = min(aaa[i][j][0],aaa[i][j-1][0],aaa[i-1][j][0])
                            aaa[i][j][1] = 3
                        elif aaa[i][j-1][1] == 3:
                            aaa[i][j][0] = min(aaa[i][j][0],aaa[i][j-1][0],aaa[i-1][j][0])
                            aaa[i][j][1] = 3
                else:
                    aaa[i][j][0] = min(aaa[i][j][0],aaa[i][j-1][0],aaa[i-1][j][0])

if po[0][0] == ".":
    aa[0][0] = [2,3]
else:
    aa[0][0] = [1,0]

for i in range(H):
    if i == 0:
        for j in range(1,W):
            if po[i][j] == ".":
                if aa[i][j-1][1] == 0:
                    aa[i][j][0] = min(aa[i][j][0],aa[i][j-1][0]+1)
                    aa[i][j][1] = 3
                elif aa[i][j-1][1] == 1 or aa[i][j-1][1] == 3:
                    aa[i][j][0] = min(aa[i][j][0],aa[i][j-1][0])
                    aa[i][j][1] = 1
            else:
                aa[i][j][0] = min(aa[i][j][0],aa[i][j-1][0])

    else:
        for j in range(W):
            if j == 0:
                if po[i][j] == ".":
                    if aa[i-1][j][1] == 0:
                        aa[i][j][0] = min(aa[i][j][0],aa[i-1][j][0]+1)
                        aa[i][j][1] = 3
                    elif aa[i-1][j][1] == 3 or aa[i-1][j][1] == 2:
                        aa[i][j][0] = min(aa[i][j][0],aa[i-1][j][0])
                        aa[i][j][1] = 2
                else:
                    aa[i][j][0] = min(aa[i][j][0],aa[i-1][j][0])
            else:
                if po[i][j] == ".":
                    if aa[i-1][j][1] == 0 or aa[i-1][j][1] == 1:
                        if aa[i][j-1][1] == 0 or aa[i][j-1][1] == 2:
                            aa[i][j][0] = min(aa[i][j][0],aa[i][j-1][0]+1,aa[i-1][j][0]+1)
                            aa[i][j][1] = 3
                        elif aa[i][j-1][1] == 1:
                            aa[i][j][0] = min(aa[i][j][0],aa[i][j-1][0],aa[i-1][j][0]+1)
                            aa[i][j][1] = 3
                        elif aa[i][j-1][1] == 3:
                            aa[i][j][0] = min(aa[i][j][0],aa[i][j-1][0],aa[i-1][j][0]+1)
                            aa[i][j][1] = 3
                    elif aa[i-1][j][1] == 2:
                        if aa[i][j-1][1] == 0 or aa[i][j-1][1] == 2:
                            aa[i][j][0] = min(aa[i][j][0],aa[i][j-1][0]+1,aa[i-1][j][0])
                            aa[i][j][1] = 3
                        elif aa[i][j-1][1] == 1:
                            aa[i][j][0] = min(aa[i][j][0],aa[i][j-1][0],aa[i-1][j][0])
                            aa[i][j][1] = 3
                        elif aa[i][j-1][1] == 3:
                            aa[i][j][0] = min(aa[i][j][0],aa[i][j-1][0],aa[i-1][j][0])
                            aa[i][j][1] = 3
                    elif aa[i-1][j][1] == 3 or aa[i][j-1][1] == 2:
                        if aa[i][j-1][1] == 0:
                            aa[i][j][0] = min(aa[i][j][0],aa[i][j-1][0]+1,aa[i-1][j][0])
                            aa[i][j][1] = 3
                        elif aa[i][j-1][1] == 1:
                            aa[i][j][0] = min(aa[i][j][0],aa[i][j-1][0],aa[i-1][j][0])
                            aa[i][j][1] = 3
                        elif aa[i][j-1][1] == 3:
                            aa[i][j][0] = min(aa[i][j][0],aa[i][j-1][0],aa[i-1][j][0])
                            aa[i][j][1] = 3
                else:
                    aa[i][j][0] = min(aa[i][j][0],aa[i][j-1][0],aa[i-1][j][0])

print(min(aaa[-1][-1][0],aa[-1][-1][0]))

Solution (Python):
import numpy as np

H,W = [int(i) for i in input().split()]

s=[]

for i in range(H):
    s.append(str(input()))
    


pat_mat=[]

for i in range(H):
    if i ==0:
        if s[0][0] == ".":
            pat_mat.append([0])
        else:
            pat_mat.append([1])
        if W>1:
            for j in range(1,W):
                if s[0][j] == ".":
                    pat_mat[0].append(pat_mat[0][j-1])
                else:
                    if s[0][j-1]==s[0][j]:
                        pat_mat[0].append(int(pat_mat[0][j-1]))
                    else:
                        pat_mat[0].append(int(pat_mat[0][j-1]+1))
    else:
        if s[i][0] == ".":
            pat_mat.append([pat_mat[i-1][0]])
        else:
            if s[i-1][0]==s[i][0]:
                pat_mat.append([pat_mat[i-1][0]])
            else:
                
                pat_mat.append([pat_mat[i-1][0]+1])
        if W>1:
            for j in range(1,W):
                if s[i][j] == ".":
                    pat_mat[i].append(min(pat_mat[i][j-1],pat_mat[i-1][j]))
                else:
                    if s[i][j-1]==s[i][j]:
                        cand_l = pat_mat[i][j-1]
                    else:
                        cand_l = pat_mat[i][j-1]+1
                    if s[i][j]==s[i-1][j]:
                        cand_t= pat_mat[i-1][j]
                    else:
                        cand_t= pat_mat[i-1][j]+1

                    pat_mat[i].append(min(cand_l,cand_t))
                        
                    
print(int(pat_mat[H-1][W-1]))

Solution (Python):
H, W = map(int,input().split())
s = [input() for i in range(H)]
dp = [[0 for _ in range(W)] for _ in range(H)]

for i in range(H):
    for j in range(W):
        
        if i == 0 and j == 0:
            if s[i][j] == "
                dp[i][j] = 1
        
        elif i == 0:
            if s[i][j-1] == "
                dp[i][j] = dp[i][j-1]
            else:
                if s[i][j] == "
                    dp[i][j] = dp[i][j-1] + 1
                else:
                    dp[i][j] = dp[i][j-1]
        
        elif j == 0:
            if s[i-1][j] == "
                dp[i][j] = dp[i-1][j]
            else:
                if s[i][j] == "
                    dp[i][j] = dp[i-1][j] + 1
                else:
                    dp[i][j] = dp[i-1][j]
        else:
            
            
            if dp[i-1][j] > dp[i][j-1]:
                if s[i][j-1] == "
                    dp[i][j] = dp[i][j-1]
                else:
                    if s[i][j] == "
                        dp[i][j] = dp[i][j-1] + 1
                    else:
                        dp[i][j] = dp[i][j-1]
            
            elif dp[i-1][j] < dp[i][j-1]:
                if s[i-1][j] == "
                    dp[i][j] = dp[i-1][j]
                else:
                    if s[i][j] == "
                        dp[i][j] = dp[i-1][j] + 1
                    else:
                        dp[i][j] = dp[i-1][j]
            
            else:
                if s[i-1][j] == "
                    dp[i][j] = dp[i-1][j]
                else:
                    if s[i][j] == "
                        dp[i][j] = dp[i-1][j] + 1
                    else:
                        dp[i][j] = dp[i-1][j]

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

Solution (Python):




import sys
from io import StringIO
import unittest

def yn(b):
    print("Yes" if b==1 else "No")
    return

def resolve():
    readline=sys.stdin.readline

    
    
    
    
    
    h,w=map(int, readline().rstrip().split())
    masu=[]
    count=[[-1 for i in range(w)] for j in range(h)]
    for i in range(h):
        masu.append(readline().rstrip())

    if masu[0][0]=="
        count[0][0]=1
    else:
        count[0][0]=0

    for y in range(h):
        for x in range(w):
            if y==0 and x==0:
                continue

            left=999999
            up=999999
            if x > 0: 
                if masu[y][x]==".":
                    left=count[y][x-1]
                else: 
                    if masu[y][x-1]==".":
                        left=count[y][x-1]+1
                    else:
                        left=count[y][x-1]
            if y > 0: 
                if masu[y][x]==".":
                    up=count[y-1][x]
                else: 
                    if masu[y-1][x]==".":
                        up=count[y-1][x]+1
                    else:
                        up=count[y-1][x]
            count[y][x]=min(left,up)
    print(count[h-1][w-1])
    return

if 'doTest' not in globals():
    resolve()
    sys.exit()

Solution (Python):
h, w = map(int, input().split())
s = [list(input()) for _ in range(h)]
dp = [[float('inf') for i in range(w)] for j in range(h)]
if s[0][0] == '.':
    dp[0][0] = 0
    total = 0
else:
    dp[0][0] = 1
    total = 1
for i in range(1,w):
    if s[0][i] == '
        if s[0][i-1] == '
            dp[0][i] = total
        else:
            total += 1
            dp[0][i] = total
    else:
        dp[0][i] = total
if s[0][0] == '.':
    total = 0
else:
    total = 1
for i in range(1,h):
    if s[i][0] == '
        if s[i-1][0] == '
            dp[i][0] = total
        else:
            total += 1
            dp[i][0] = total
    else:
        dp[i][0] = total
for i in range(1,h):
    for j in range(1,w):
        if s[i][j] == '
            if s[i-1][j] == '
                dp[i][j] = min(dp[i-1][j], dp[i][j-1])
            elif s[i-1][j] == '
                dp[i][j] = min(dp[i-1][j], dp[i][j-1] + 1)
            elif s[i][j-1] == '
                dp[i][j] = min(dp[i][j-1], dp[i-1][j] + 1)
            else:
                dp[i][j] = min(dp[i-1][j] + 1, dp[i][j-1] + 1)
        else:
            dp[i][j] = min(dp[i-1][j], dp[i][j-1])
print(dp[h-1][w-1])

Solution (Python):
import sys


def input():
    return sys.stdin.readline().strip()


def main():
    H, W = map(int, input().split())

    S = [list(input()) for _ in range(H)]
    
    check = [[10 ** 9 for i in range(W)] for j in range(H)]
    if S[0][0] == "
        check[0][0] = 1
    else:
        check[0][0] = 0
    for i in range(1, W):
        left = check[0][i - 1]
        if S[0][i] == "
            if S[0][i - 1] == "
                check[0][i] = left
            else:
                check[0][i] = left + 1
        else:
            check[0][i] = left
    for i in range(1, H):
        up = check[i - 1][0]
        if S[i][0] == "
            if S[i - 1][0] == "
                check[i][0] = up
            else:
                check[i][0] = up + 1
        else:
            check[i][0] = up
    for i in range(1, H):
        for j in range(1, W):
            
            left = check[i][j - 1]
            up = check[i - 1][j]
            if S[i][j] == "
                if S[i][j - 1] == "
                    check[i][j] = min(left, up)
                elif S[i][j - 1] != "
                    check[i][j] = min(left + 1, up)
                elif S[i][j - 1] == "
                    check[i][j] = min(left, up + 1)
                else:
                    check[i][j] = min(left, up) + 1
            else:
                check[i][j] = min(left, up)
    
    print(check[-1][-1])


main()

Solution (Python):
from math import *

n, m = map(int, input().split())
a = []
for i in range(n):
    a.append([1 if j == '.' else 0 for j in input()])
dp = []
for i in range(n):
    dp.append([n*m] * m)

dp[0][0] = 1 - a[0][0]

for i in range(n):
    for j in range(m):
        
        if i == j == 0:
            continue
        if a[i][j]:
            if i > 0:
                dp[i][j] = min(dp[i][j], dp[i-1][j])
            if j > 0:
                dp[i][j] = min(dp[i][j], dp[i][j-1])
        else:
            if i > 0 and not a[i-1][j]:
                dp[i][j] = min(dp[i][j], dp[i-1][j])
            elif i > 0:
                dp[i][j] = min(dp[i][j], dp[i-1][j] + 1)
                
            if j > 0 and not a[i][j-1]:
                dp[i][j] = min(dp[i][j], dp[i][j-1])
            elif j > 0:
                dp[i][j] = min(dp[i][j], dp[i][j-1] + 1)

print(dp[n-1][m-1])

Solution (Python):
h, w= map(int, input().split())
maze = [input() for i in range(h)]
maze_num =[[0] for i in range(h)]



maze_num =[[0]*w for i in range(h)]
for i in range(h):
    for k in range(w):
        maze_num[i][k] = [float("inf"), maze[i][k]]

maze_num[0][0][0] = 0

for i in range(h):
    for k in range(w):
        if i == h-1 and k ==w-1:
            break
        if k != w-1:
            if maze_num[i][k][1] =="
                maze_num[i][k+1][0] = min(maze_num[i][k+1][0], maze_num[i][k][0]+ 1)
            else:
                maze_num[i][k+1][0] = min(maze_num[i][k+1][0], maze_num[i][k][0])
        if i != h-1:
            if maze_num[i][k][1] =="
                maze_num[i+1][k][0] = min(maze_num[i+1][k][0], maze_num[i][k][0]+ 1)
            else:
                maze_num[i+1][k][0] = min(maze_num[i+1][k][0], maze_num[i][k][0])

if maze_num[h-1][w-1][1] =="
    print(maze_num[h-1][w-1][0] + 1)
else:
    print(maze_num[h-1][w-1][0])

Solution (Python):
H,W=map(int,input().split())
s=[0 for i in range(0,H)]
for i in range(0,H):
    s[i]=input()

dp=[[-1 for i in range(W)] for j in range(H)]
if s[0][0]=='
    dp[0][0]=1
else:
    dp[0][0]=0
for i in range(1,W):
    if s[0][i-1]=='.' and s[0][i]=='
        dp[0][i]=dp[0][i-1]+1
    else:
        dp[0][i]=dp[0][i-1]

for i in range(1,H):
    for j in range(0,W):
        fromup=10**5
        fromleft=10**5
        if s[i-1][j]=='.' and s[i][j]=='
            fromup=dp[i-1][j]+1
        else:
            fromup=dp[i-1][j]
        if j!=0:
            if s[i][j-1]=='.' and s[i][j]=='
                fromleft=dp[i][j-1]+1
            else:
                fromleft=dp[i][j-1]
        dp[i][j]=min(fromup,fromleft)

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

Solution (Python):
import sys
def MI(): return map(int, sys.stdin.readline().split())

H,W = MI()
s = [list(input()) for _ in range(H)]
dp = [[0 for _ in range(W)] for _ in range(H)]

if s[0][0]=='
	dp[0][0] = 1

for i in range(W-1):
	if s[0][i+1]=='
		dp[0][i+1] = dp[0][i] + 1
	else:
		dp[0][i+1] = dp[0][i]

for i in range(H-1):
	if s[i+1][0]=='
		dp[i+1][0] = dp[i][0] + 1
	else:
		dp[i+1][0] = dp[i][0]

def next(start, goal, start_value):
	if start=='.' and goal=='
		start_value += 1
	return start_value

for i in range(1,H):
	for j in range(1,W):
		
		dp[i][j] = min(next(s[i][j-1],s[i][j],dp[i][j-1]), next(s[i-1][j],s[i][j],dp[i-1][j]))

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

Solution (Python):
h, w = map(int, input().split())
s = []
s.append(["."] * (w + 1))
for i in range(h):
    s.append(["."] + list(input()))
s2 = []
for i in range(h + 1):
    s2.append([0] * (w + 1))

for i in range(w - 1):
    if s[1][i + 1] == "
        if s[1][i] != "
            s2[0][i + 2] = s2[0][i + 1] + 1
        else:
            s2[0][i + 2] = s2[0][i + 1]
    else:
        s2[0][i + 2] = s2[0][i + 1]
for i in range(h - 1):
    if s[i + 1][1] == "
        if s[i][1] != "
            s2[i + 2][0] = s2[i + 1][0] + 1
        else:
            s2[i + 2][0] = s2[i + 1][0]
    else:
        s2[i + 2][0] = s2[i + 1][0]

for i in range(h):
    for j in range(w):
        if s[i + 1][j + 1] == ".":
            s2[i + 1][j + 1] = min(s2[i][j + 1], s2[i + 1][j])
        else:
            if s[i][j + 1] == "
                if s[i + 1][j] == "
                    s2[i + 1][j + 1] = min(s2[i][j + 1], s2[i + 1][j])
                else:
                    s2[i + 1][j + 1] = min(s2[i][j + 1], s2[i + 1][j] + 1)
            else:
                if s[i + 1][j] == "
                    s2[i + 1][j + 1] = min(s2[i][j + 1] + 1, s2[i + 1][j])
                else:
                    s2[i + 1][j + 1] = min(s2[i][j + 1], s2[i + 1][j]) + 1
print(s2[h][w])

Solution (Python):
from collections import deque
H, W = map(int, input().split())
X = [[1 if a == "

def BFS(i0=0):
    Q = deque([i0])
    D = [-1] * (H * W)
    D[i0] = X[0][0]
    while Q:
        x = Q.popleft()
        i, j = x // W, x % W
        for di, dj in ((0, 1), (1, 0)):
            ni, nj = i + di, j + dj
            if 0 <= ni < H and 0 <= nj < W:
                y = ni * W + nj
                if X[ni][nj] == X[i][j]:
                    if D[y] == -1:
                        D[y] = D[x]
                        Q.appendleft(y)
                else:
                    if D[y] == -1:
                        D[y] = D[x] + 1
                        Q.append(y)
                        
    return D

print(BFS(0)[-1] + 1 >> 1)

Solution (Python):
h,w=map(int,input().split())
s=[input() for _ in range(h)]

paint=((1,0),(0,1))
dp=[[0]*(w) for _ in range(h)] 

dp[0][0]=0
for i in range(h-1):
    dp[i+1][0]=dp[i][0]+(s[i][0]!=s[i+1][0])

for i in range(h):
    for j in range(1,w):
        if i==0:
            dp[i][j]=dp[i][j-1]+(s[i][j-1]!=s[i][j])
        else:
            dp[i][j]=min(dp[i][j-1]+(s[i][j-1]!=s[i][j]), dp[i-1][j]+(s[i][j]!=s[i-1][j]))
        
if dp[h-1][w-1]==0:
    if s[0][0]=='.':
        print(0)
    else:
        print(1)
    exit()

if s[0][0]=='.' and s[h-1][w-1]=='.':
    print(dp[h-1][w-1]//2)
    exit()
    
if (s[0][0]=='
    print((dp[h-1][w-1]+1)//2)
    exit()

if s[0][0]=='
    print(dp[h-1][w-1]//2+1)
    exit()

Solution (Python):
from itertools import product


def read():
    H, W = list(map(int, input().strip().split()))
    S = list()
    S.append(list('
    for i in range(H):
        s = list(input().strip())
        S.append(['
    S.append(list('
    return H, W, S


def solve(H, W, S, INF=10000):
    field = [[INF for j in range(W+2)] for i in range(H+2)]
    field[1][1] = 1 if S[1][1] == '
    for j in range(2, W+1):
        u = 1 if S[1][j-1] == '.' and S[1][j] == '
        field[1][j] = field[1][j-1] + u
    for i, j in product(range(2, H+1), range(1, W+1)):
        
        if S[i-1][j] == '.' and S[i][j] == '
            u = field[i-1][j] + 1  
        else:
            u = field[i-1][j]
        
        if S[i][j-1] == '.' and S[i][j] == '
            v = field[i][j-1] + 1  
        else:
            v = field[i][j-1]
        field[i][j] = min(u, v)
    return field[H][W]


if __name__ == '__main__':
    inputs = read()
    print("%s" % solve(*inputs))

Solution (Python):
h,w=map(int,input().split())
li=[[]]*h
for i in range(h):
  li[i]=[str(k) for k in input()]
  
lil=[[0 for i in range(w)] for j in range(h)]

for i in range(h):
  for j in range(w):
    if i==0 and j==0:
      if li[0][0]==".":
        lil[0][0]=0
      else:
        lil[0][0]=1
    elif i==0:
      if li[i][j]==li[i][j-1] or li[i][j]==".":
        lil[i][j]=lil[i][j-1]
      elif li[i][j]=="
        lil[i][j]=lil[i][j-1]+1
    elif j==0:
      if li[i][j]==li[i-1][j] or li[i][j]==".":
        lil[i][j]=lil[i-1][j]
      elif li[i][j]=="
        lil[i][j]=lil[i-1][j]+1
    else:
      if li[i][j]==li[i-1][j] or li[i][j]==".":
        ko=lil[i-1][j]
      elif li[i][j]=="
        ko=lil[i-1][j]+1
      if li[i][j]==li[i][j-1] or li[i][j]==".":
        ks=lil[i][j-1]
      elif li[i][j]=="
        ks=lil[i][j-1]+1
      lil[i][j]=min(ko,ks)
print(lil[h-1][w-1])

Solution (Python):
taka,yoko=map(int,input().split())

gen=[]
saisho=[]
for i in range(taka):
    s=input()
    temp=[0]*yoko
    for j in range(yoko):
        if(s[j]=="."):
            temp[j]=1
        else:
            temp[j]=-1
    gen.append(temp)
    saisho.append([-1000]*yoko)


if(gen[0][0]==1):
    saisho[0][0]=0
else:
    saisho[0][0]=1


for i in range(1,yoko):
    if(gen[0][i]==1):
        saisho[0][i]=saisho[0][i-1]
    else:
        if(gen[0][i-1]==-1):
            saisho[0][i]=saisho[0][i-1]
        else:
            saisho[0][i]=saisho[0][i-1]+1

for i in range(1,taka):
    if(gen[i][0]==1):
        saisho[i][0]=saisho[i-1][0]
    else:
        if(gen[i-1][0]==-1):
            saisho[i][0]=saisho[i-1][0]
        else:
            saisho[i][0]=saisho[i-1][0]+1


for i in range(1,taka):
    for j in range(1,yoko):
        if(gen[i][j]==1):
            saisho[i][j]=min(saisho[i][j-1],saisho[i-1][j])
        else:
            ue=saisho[i-1][j]
            hidari=saisho[i][j-1]
            if(gen[i-1][j]==1):
                ue+=1
            if(gen[i][j-1]==1):
                hidari+=1
            saisho[i][j]=min(ue,hidari)

print(saisho[taka-1][yoko-1])

Solution (Python):
def ans_dp(H,W,M):
    dp = [[0 for i in range(W)] for j in range(H)]
    flag = [[0 for i in range(W)] for j in range(H)]
    if M[0][0] == "
        dp[0][0] = 1
        flag[0][0] = 1
    else:
        dp[0][0] == 0
    for i in range(1,W):
        if M[0][i] == "
            flag[0][i] = 1
            if flag[0][i-1] == 1:
                dp[0][i] = dp[0][i-1]
            else:
                dp[0][i] = dp[0][i-1] + 1 
        else:
            dp[0][i] = dp[0][i-1]
    for j in range(1,H):
        if M[j][0] == "
            flag[j][0] = 1
            if flag[j-1][0] == 1:
                dp[j][0] = dp[j-1][0]
            else:
                dp[j][0] = dp[j-1][0] + 1 
        else:
            dp[j][0] = dp[j-1][0]
    
    for i in range(1,H):
        for j in range(1,W):
            if M[i][j] == "
                flag[i][j] = 1
                dp[i][j] = min(dp[i-1][j]+int(not flag[i-1][j]),dp[i][j-1]+int(not flag[i][j-1]))
            else:
                dp[i][j] = min(dp[i-1][j],dp[i][j-1])
    return dp[-1][-1]

def main():
    H,W = map(int,input().split())
    M = []
    for i in range(H):
        M.append(list(input()))
    print(ans_dp(H,W,M))
 
if __name__ == "__main__":
    main()

Solution (Python):
H,W=map(int,input().split())
L=[]
l=["*" for i in range(W+2)]
L.append(l)
for i in range(H):
    s=["*"]+list(input())+["*"]
    L.append(s)
L.append(l)


X=[1,0,-1,0]
Y=[0,1,0,-1]

cnt=0
if L[1][1]=="
    cnt+=1

C=[[10000 for i in range(W+2)]for j in range(H+2)]
Q=[(0,1,1)]

import heapq
heapq.heapify(Q)
for i in range(10**6):
    if len(Q)==0:
        break
    d,h,w=Q[0]
    heapq.heappop(Q)
    if C[h][w]==10000:
        C[h][w]=d
        for j in range(2):
            if C[h+X[j]][w+Y[j]]==10000 and L[h+X[j]][w+Y[j]]!="*":
                if L[h+X[j]][w+Y[j]]=="
                    heapq.heappush(Q,(d+1,h+X[j],w+Y[j]))
                else:
                    heapq.heappush(Q,(d,h+X[j],w+Y[j]))
print(C[H][W]+cnt)

Solution (Python):
H, W = map(int, input().split())
s = []
for i in range(H):
    s.append(input())

is_white = True
st = []
st.append([False, H-1, W-1, 0])
dp = [[1000] * W for i in range(H)]

for h in reversed(range(H)):
    for w in reversed(range(W)):
        if h == H-1 and w == W-1:
            if s[h][w] == '
                dp[h][w] = 1
            else:
                dp[h][w] = 0
            continue

        if w+1 < W:
            cnt = dp[h][w+1]
            if s[h][w] == '
                cnt += 1
            if cnt < dp[h][w]:
                dp[h][w] = cnt

        if h+1 < H:
            cnt = dp[h+1][w]
            if s[h][w] == '
                cnt += 1
            if cnt < dp[h][w]:
                dp[h][w] = cnt

print(dp[0][0])

Solution (Python):
h,w = map(int,input().split())

import numpy as np
dp = np.zeros((h,w),np.int32)
s = np.full((h,w),'.',np.str)
for H in range(h):
    S = input()
    for W in range(w):
        s[H][W] = S[W]
        own = s[H][W]
        if H==0 and W==0: dp[H][W] = 0 if own=='.' else 1
        elif H==0: dp[H][W] = dp[H][W-1]+1 if s[H][W-1]=='.' and own=='
        elif W==0: dp[H][W] = dp[H-1][W]+1 if s[H-1][W]=='.' and own=='
        else:
            dp[H][W] = min(dp[H][W-1], dp[H-1][W])
            if own=='
                if s[H][W-1]=='.' and s[H-1][W]=='.': dp[H][W] += 1
                elif s[H][W-1]=='
                elif s[H][W-1]=='.' and s[H-1][W]=='
print(dp[h-1,w-1])