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):

def IsvalidStep(arr,row1,col1,row2,col2):
    if arr[row2][col2]=="
        return 1
    return 0    

def solve(arr,matrix,n,m):
    maxx=0
    if n>0:
        if arr[0][0]=="
            matrix[0][0]=1
        for col in range(1,m):
            matrix[0][col]=matrix[0][col-1]
            if arr[0][col]=="
                matrix[0][col]+=1

        for row in range(1,n):    
            matrix[row][0]=matrix[row-1][0]
            if arr[row][0]=="
                matrix[row][0]+=1
          
        for row in range(1,n):
            for col in range(1,m):
                matrix[row][col]=min(matrix[row-1][col]+IsvalidStep(arr,row-1,col,row,col),matrix[row][col-1]+IsvalidStep(arr,row,col-1,row,col))
        return matrix[n-1][m-1]        



n,m=map(int,input().split())
arr=[int(0) for i in range(n)]
matrix=[int(0) for i in range(n)]
for i in range(n):
    arr[i]=list(input())
    matrix[i]=[int(0) for _ in range(m)]



print(solve(arr,matrix,n,m))       


"""
def solve(arr,n,m,row,col,count):
    if row>=n or col>=m:
        return 1e9
    elif row==n-1 and col==m-1:
        if arr[row][col]=="
            count+=1
        return count
    else:
        if arr[row][col]=="
            count+=1
        return min(solve(arr,n,m,row+1,col,count),solve(arr,n,m,row,col+1,count))        
"""

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

mat = [[] for _ in range(h)]

for i in range(h):
    mat[i] = input()

dp = [[float("inf")] * w for _ in range(h)]

if mat[0][0] == "
    dp[0][0] = 1
else:
    dp[0][0] = 0

for i in range(h):
    for j in range(w):

        if mat[i][j - 1] != mat[i][j]:
            left = dp[i][j - 1] + 1
        else:
            left = dp[i][j - 1]

        if mat[i - 1][j] != mat[i][j]:
            top = dp[i - 1][j] + 1
        else:
            top = dp[i - 1][j]

        dp[i][j] = min(dp[i][j], left, top)

print((dp[h - 1][w - 1] + 1) // 2)

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

def cnt(i0, j0, i1, j1):
  if S[i0][j0] == "." and S[i1][j1] == "
    return 1
  else:
    return 0

for i in range(H):
  for j in range(W):
    if i == 0 and j == 0:
      dp[0][0] = 0 if S[0][0] == "." else 1
    elif i == 0:
      dp[i][j] = dp[i][j-1] + cnt(i, j-1, i, j)
    elif j == 0:
      dp[i][j] = dp[i-1][j] + cnt(i-1, j, i, j)
    else:
      dp[i][j] = min(dp[i][j-1] + cnt(i, j-1, i, j), dp[i-1][j] + cnt(i-1, j, i, j))

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

Solution (Python):
import math,string,itertools,fractions,heapq,collections,re,array,bisect,sys,copy,functools
import time,random

sys.setrecursionlimit(10**7)
inf = 10**20
eps = 1.0 / 10**10
mod = 10**9+7
mod2 = 998244353
dd = [(-1,0),(0,1),(1,0),(0,-1)]
ddn = [(-1,0),(-1,1),(0,1),(1,1),(1,0),(1,-1),(0,-1),(-1,-1)]

def LI(): return list(map(int, sys.stdin.readline().split()))
def LLI(): return [list(map(int, l.split())) for l in sys.stdin.readlines()]
def LI_(): return [int(x)-1 for x in sys.stdin.readline().split()]
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def I(): return int(sys.stdin.readline())
def F(): return float(sys.stdin.readline())
def S(): return input()
def pf(s): return print(s, flush=True)
def pe(s): return print(str(s), file=sys.stderr)
def JA(a, sep): return sep.join(map(str, a))
def JAA(a, s, t): return s.join(t.join(map(str, b)) for b in a)


def main():
    h,w = LI()
    aa = [[0 if c == '.' else 1 for c in S()] for _ in range(h)]

    dp = [[[inf]*2 for _ in range(w)] for __ in range(h)]
    dp[0][0][aa[0][0]] = aa[0][0]
    for i in range(h):
        for j in range(w):
            k = aa[i][j]
            if i > 0:
                dp[i][j][k] = min(dp[i][j][k], dp[i-1][j][k])
                dp[i][j][k] = min(dp[i][j][k], dp[i-1][j][1-k]+1)
            if j > 0:
                dp[i][j][k] = min(dp[i][j][k], dp[i][j-1][k])
                dp[i][j][k] = min(dp[i][j][k], dp[i][j-1][1-k]+1)

    return min(dp[-1][-1][0] + 1, dp[-1][-1][1] + 2) // 2


print(main())

Solution (Python):
h, w = map(int, input().split())
M = [list(input()) for _ in range(h)]
count = [[int(1e18) for _ in range(w)] for _ in range(h)]
count[0][0] = 1 if M[0][0] == '


for i in range(h):
    for j in range(w):
        if i + 1 < h:
            v = 1 if M[i][j] != M[i + 1][j] else 0
            count[i + 1][j] = min(count[i + 1][j], count[i][j] + v)
        if j + 1 < w:
            v = 1 if M[i][j] != M[i][j + 1] else 0
            count[i][j + 1] = min(count[i][j + 1], count[i][j] + v)

print((count[h - 1][w - 1] + 1) // 2)

Solution (Python):
import numpy as np

H,W = input().split()
H,W=int(H),int(W)
P=[0]*H
for i in range(H):
    P[i] = input()

dp=np.zeros((H,W),dtype='u8')
if P[0][0]=='
    dp[0][0]=1
else:
    dp[0][0]=0

def DP(y,x):
    global dp
    if 0<=x<=W-1 and 0<=y<=H-1:
        return dp[y][x]
    else:
        return 9999999

for l in range(1,H+W):
    for i in range(l+1):
        if i<H and l-i<W:
            if P[i][l-i]=='
                a=DP(i-1,l-i)
                b=DP(i,l-i-1)
                if a < 9999999:
                    if P[i-1][l-i]=='.':
                        a+=1
                if b <  9999999:
                    if P[i][l-i-1]=='.':
                        b+=1
                dp[i][l-i]=min(a,b)
            else:
                
                dp[i][l-i]=min(DP(i-1,l-i),DP(i,l-i-1))
print(dp[H-1][W-1])

Solution (Python):
h,w=map(int,input().split())
s=[input() for _ in range(h)]
dp=[[float('inf')]*w for _ in range(h)]
if s[0][0]=='
    dp[0][0] = 1
else:
    dp[0][0] = 0
dx=[1,0]
dy=[0,1]
for i in range(h):
    for j in range(w):
        for dir in range(2):
            ni=i+dy[dir]
            nj=j+dx[dir]
            if ni>=h or nj>=w:
                continue
            add=0
            if s[ni][nj]=='
                add=1
            dp[ni][nj] = min(dp[ni][nj], dp[i][j]+add)
print(dp[-1][-1])

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

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

for hi in range(h):
    for wi in range(w):
        if hi==0 and wi==0:
            continue
        dh = 10**9
        if hi-1>=0:
            if sl[hi][wi]=="
                dh = dp[hi-1][wi] + 1
            else:
                dh = dp[hi-1][wi]
        dw = 10**9
        if wi-1>=0:
            if sl[hi][wi]=="
                dw = dp[hi][wi-1] + 1
            else:
                dw = dp[hi][wi-1]

        dp[hi][wi] = min(dh,dw)

res = dp[h-1][w-1]
if sl[0][0]=="
    res += 1
print(res)

Solution (Python):



def main():
  h, w = map(int, input().split())
  grid = []
  for _ in range(h):
    grid.append(list(input().strip()))
  dp = [[0]*(w) for _ in range(h)]
  
  def cals_score(i, j):
    score = 10**9 + 7
    if i >= 1:
      score = dp[i-1][j] + (1 if grid[i-1][j]!=grid[i][j] else 0)
    if j >= 1:
      score = min(score, dp[i][j-1] + (1 if grid[i][j-1]!=grid[i][j] else 0))
    return score
      
  dp[0][0] = 1
  for i in range(1, w):
    dp[0][i] = cals_score(0, i)
  for i in range(1, h):
    dp[i][0] = cals_score(i, 0)

    
  for i in range(1, h):
    for j in range(1, w):
      dp[i][j] = cals_score(i, j)
  print(dp[-1][-1]//2 + dp[-1][-1]%2 * (grid[0][0]=='

if __name__=='__main__':
  main()

Solution (Python):
H, W = [int(x) for x in input().split()]

S = []
S.append('.'*105)
for h in range(H):
    r = input()
    S.append('-' + r)

A = [[float("INF")] * 105 for _ in range(105)]
A[1][1] = (1 if S[1][1] == '


for h in range(1,H+1):
    for w in range(1,W+1):
        a = A[h][w]
        if S[h][w] == '
            if S[h][w-1] == '
                a = min(a, A[h][w-1])
            else:
                a = min(a, A[h][w-1] + 1)
            if S[h-1][w] == '
                a = min(a, A[h-1][w])
            else:
                a = min(a, A[h-1][w] + 1)
            A[h][w] = a
        else:
            A[h][w] = min(A[h][w-1], A[h-1][w], A[h][w])
            
print(A[H][W])

Solution (Python):
import sys
import collections

sys.setrecursionlimit(10 ** 8)

input = sys.stdin.readline


def main():
    H, W = [int(x) for x in input().split()]
    S = [list(input().strip()) for _ in range(H)]

    dp = [[10 ** 9] * W for _ in range(H)]
    dp[0][0] = int(S[0][0] == '

    for j in range(H):
        for i in range(W):
            if j != H - 1:
                dp[j + 1][i] = min(dp[j + 1][i], dp[j][i] + int(S[j + 1][i] == '
            if i != W - 1:
                dp[j][i + 1] = min(dp[j][i + 1], dp[j][i] + int(S[j][i + 1] == '
    print(dp[-1][-1])


if __name__ == '__main__':
    main()

Solution (Python):
import sys
import collections

sys.setrecursionlimit(10 ** 8)

input = sys.stdin.readline


def main():
    H, W = [int(x) for x in input().split()]
    S = [list(input().strip()) for _ in range(H)]

    dp = [[10 ** 9] * W for j in range(H)]

    if S[0][0] == '
        dp[0][0] = 1
    else:
        dp[0][0] = 0

    for j in range(H):
        for i in range(W):
            if j != H - 1:
                x = 1 if S[j + 1][i] == '
                dp[j + 1][i] = min(dp[j + 1][i], dp[j][i] + x)
            if i != W - 1:
                x = 1 if S[j][i + 1] == '
                dp[j][i + 1] = min(dp[j][i + 1], dp[j][i] + x)

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


if __name__ == '__main__':
    main()

Solution (Python):
def main():
    h,w = map(int,input().split(" "))
    s = [list(input()) for i in range(h)]
    
    dp = [[0]*w for i in range(h)]
    dp[0][0] = 1 if s[0][0]=="

    for i in range(1,h):
        sgmdown = 1 if s[i][0]=="
        dp[i][0] = dp[i-1][0] + sgmdown
    
    for j in range(1,w):
        sgmright = 1 if s[0][j]=="
        dp[0][j] = dp[0][j-1] + sgmright

    for i in range(1,h):
        for j in range(1,w):
            sgmdown = 1 if s[i][j]=="
            sgmright = 1 if s[i][j]=="
            dp[i][j] = min(dp[i-1][j]+sgmdown, dp[i][j-1]+sgmright)

    print(dp[h-1][w-1])
main()

Solution (Python):
h,w=map(int,input().split())
s=['*'+'.'+'*'*w]+['*'+input()+'*' for i in range(h)]+['*'*(w+2)]
b=10**9
d=[[b]*(w+2)]+[[b]+[0]*w+[b] for _ in range(h)]+[[b]*(w+2)]
d[0][1]=0
for i in range(1,h+1):
  for j in range(1,w+1):
    d[i][j]=min(d[i-1][j]+(s[i][j]=='
print(d[h][w])

Solution (Python):
h,w=map(int,input().split())
field=[list(input()) for i in range(h)]
ans=[[0 for i in range(w)]for j in range(h)]
if field[0][0]=='
  ans[0][0]=1

def black(i,j,f):
  if f==1:
    if field[i][j]=='
      return 1
    else:
      return 0
  else:
    if field[i][j]=='
      return 1
    else:
      return 0
for i in range(h):
  for j in range(w):
    if i==0 and j==0:
      continue
    elif i==0:
      ans[i][j]=ans[i][j-1]+black(i,j,2)
    elif j==0:
      ans[i][j]=ans[i-1][j]+black(i,j,1)
    else:
      ans[i][j]=min(ans[i-1][j]+black(i,j,1),ans[i][j-1]+black(i,j,2))
print(ans[-1][-1])

Solution (Python):
def solve():
    h, w = map(int, input().split())
    s = [input() for _ in range(h)]
    INF = 10 ** 9
    dp = [[0]*(w+10) for _ in range(h+10)]
    dp[0][0] = 1 if s[0][0] == '

    for i in range(h):
        for j in range(w):
            if not i==j==0:
                dp[i][j] = INF
            if i>0:
                dp[i][j] = min(dp[i][j], dp[i-1][j] + (1 if s[i-1][j]=='.' and s[i][j]=='
            if j>0:
                dp[i][j] = min(dp[i][j], dp[i][j-1] + (1 if s[i][j-1]=='.' and s[i][j]=='

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


solve()

Solution (Python):


from collections import defaultdict

con = 10 ** 9 + 7

def getlist():
	return list(map(int, input().split()))
INF = float("inf")


def main():
	H, W = getlist()
	L = []
	for i in range(H):
		l = list(input())
		L.append(l)

	DP = [[INF] * W for i in range(H)]
	
	if L[0][0] == "
		DP[0][0] = 1
	else:
		DP[0][0] = 0

	for i in range(1, H):
		DP[i][0] = 0
	for i in range(1, W):
		DP[0][i] = 0

	for i in range(1, H):
		if L[i][0] != L[i - 1][0]:
			DP[i][0] += DP[i - 1][0] + 1
		else:
			DP[i][0] += DP[i - 1][0]

	for i in range(1, W):
		if L[0][i] != L[0][i - 1]:
			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(1, W):
			if L[i][j] != L[i - 1][j]:
				DP[i][j] = min(DP[i][j], DP[i - 1][j] + 1)
			else:
				DP[i][j] = min(DP[i][j], DP[i - 1][j])

			if L[i][j] != L[i][j - 1]:
				DP[i][j] = min(DP[i][j], DP[i][j - 1] + 1)
			else:
				DP[i][j] = min(DP[i][j], DP[i][j - 1])

	

	ans = int((DP[-1][-1] + 1) // 2)
	print(ans)


if __name__ == '__main__':
	main()

Solution (Python):
import numpy as np
h,w=map(int,input().split())
s=[input() for _ in range(h)]
dp=np.zeros((h,w),np.int64)
if s[0][0]=='
      dp[0,0]=1
for i in range(h):
  for j in range(w):
    if (i,j)==(0,0):
      continue
    elif i==0:
      if s[i][j-1]=='.' and 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]=='.' and s[i][j]=='
        dp[i,j]=dp[i-1,j]+1
      else:
        dp[i,j]=dp[i-1,j]
    else:
      dp[i,j]=min(dp[i,j-1]+1 if s[i][j-1]=='.' and s[i][j]=='
print(dp[-1,-1])

Solution (Python):

h, w = map(int, input().split())
matrix = []
for _ in range(h):
    row = list(input())
    matrix.append(row)

dp = [[float('inf')] * w for _ in range(h)]
dp[0][0] = 0
if matrix[0][0] == '
    dp[0][0] += 1

for i in range(h):
    for j in range(w):
        if i + 1 < h:
            if matrix[i][j] == matrix[i + 1][j]:
                dp[i + 1][j] = min(dp[i + 1][j], dp[i][j])
            else:
                dp[i + 1][j] = min(dp[i + 1][j], dp[i][j] + 1)
        if j + 1 < w:
            if matrix[i][j] == matrix[i][j + 1]:
                dp[i][j + 1] = min(dp[i][j + 1], dp[i][j])
            else:
                dp[i][j + 1] = min(dp[i][j + 1], dp[i][j] + 1)

ans = (dp[-1][-1] + 1) // 2
print(ans)

Solution (Python):
import sys
input = sys.stdin.readline
from collections import deque
def main():
    H, W = map(int, input().split())
    field = [input().rstrip("\r\n") for _ in range(H)]
    dv = 201
    counts = [[dv for _ in range(W)] for _ in range(H)]
    que = deque([(0, 0)])
    if field[0][0] == "
        counts[0][0] = 1
    else:
        counts[0][0] = 0
    while len(que) > 0:
        h, w = que.popleft()
        for dh, dw in [(1, 0), (0, 1)]:
            nh, nw = h + dh, w + dw
            if nh >= H or nw >= W:continue
            if counts[nh][nw] == dv:que.append((nh, nw))
            if field[h][w] != field[nh][nw]:
                counts[nh][nw] = min(counts[nh][nw], counts[h][w]+1)
            else:
                counts[nh][nw] = min(counts[nh][nw], counts[h][w])
    if field[-1][-1] == "
    print(counts[-1][-1]//2)
if __name__ == "__main__":
    main()

Solution (Python):
from functools import lru_cache
h,w= map(int, input().split())
maze = [[-1 for i in range(w)] for j in range(h)]

ans = 0
for i in range(h):
    maze[i] = input()

INF = 10000

@lru_cache(None)
def dfs(y,x,flg,cnt):
    if y == h-1 and x ==w-1:
        if flg ==1:
            cnt+=1
        return cnt
    ans = [INF]
    for (ny, nx) in [(y+1, x), (y, x+1)]:
        if 0 <= nx < w and 0 <= ny < h:
            if maze[ny][nx] != maze[y][x]:
                if flg == 0: ans.append(dfs(ny,nx,1,cnt))
                else: ans.append(dfs(ny,nx,0,cnt+1))
            else:
                ans.append(dfs(ny,nx,flg,cnt))
    return(min(ans))

print(dfs(0,0,(0 if maze[0][0]=='.' else 1),0))

Solution (Python):
import sys

sys.setrecursionlimit(10 ** 5 + 10)


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


def resolve():
    H, W = map(int, input().split())
    maze = [[_ for _ in input()] for _ in range(W)]
    INF = 10 ** 5
    
    
    dp = [[INF] * W for _ in range(H)]
    
    if maze[0][0] == '
        dp[0][0] = 1
    else:
        dp[0][0] = 0
    
    for i in range(H):
        for j in range(W):
            for [dy, dx] in [[1, 0], [0, 1]]:
                ny, nx = i + dy, j + dx
                if ny >= H or nx >= W:
                    continue
                else:
                    if maze[i][j] == '.' and maze[ny][nx] == '
                        dp[ny][nx] = min(dp[ny][nx], dp[i][j] + 1)
                    else:
                        dp[ny][nx] = min(dp[ny][nx], dp[i][j])
    print(dp[H - 1][W - 1])


resolve()

Solution (Python):
import sys

sys.setrecursionlimit(10 ** 5 + 10)


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


def resolve():
    H, W = map(int, input().split())
    maze = [[_ for _ in input()] for _ in range(W)]
    INF = 10 ** 5
    
    dp = [[INF] * W for _ in range(H)]

    if maze[0][0] == '
        dp[0][0] = 1
    else:
        dp[0][0] = 0

    for i in range(H):
        for j in range(W):
            for [dy, dx] in [[1, 0], [0, 1]]:
                ny, nx = i + dy, j + dx
                if ny >= H or nx >= W:
                    continue
                else:
                    if maze[i][j] == '.' and maze[ny][nx] == '
                        dp[ny][nx] = min(dp[ny][nx], dp[i][j] + 1)
                    else:
                        dp[ny][nx] = min(dp[ny][nx], dp[i][j])
    print(dp[H - 1][W - 1])


resolve()

Solution (Python):
import sys
import fractions

sr = lambda: sys.stdin.readline().rstrip()
ir = lambda: int(sr())
lr = lambda: list(map(int, sr().split()))

H, W = lr()
dp = [[0 for _ in range(W)] for _ in range(H)]
masu = [sr() for _ in range(H)]
dp[0][0] = 1 if masu[0][0] == "
for h, m in enumerate(masu):
    for w, s in enumerate(m):
        if w == 0 and h == 0:
            continue
        if w == 0:
            if masu[h-1][w] != s and s == "
                dp[h][w] += dp[h-1][w] + 1
            else:
                dp[h][w] += dp[h-1][w]
            continue
        if h == 0:
            if masu[h][w-1] != s and s == "
                dp[h][w] += dp[h][w-1] + 1
            else:
                dp[h][w] += dp[h][w-1]
            continue
        if masu[h-1][w] != s and s == "
            cand1 = dp[h][w] + dp[h-1][w] + 1
        else:
            cand1 = dp[h][w] + dp[h-1][w]
        if masu[h][w-1] != s and s == "
            cand2 = dp[h][w] + dp[h][w-1] + 1
        else:
            cand2 = dp[h][w] + dp[h][w-1]
        dp[h][w] = min(cand1, cand2)
print(dp[H-1][W-1])

Solution (Python):
def solve(H, W, s):
    scores = [[float('inf') for _ in range(W)] for _ in range(H)]
    scores[0][0] = 0 if s[0][0] == '.' else 1

    for i in range(H):
        for j in range(W):
            for x, y in [(i - 1, j), (i, j - 1)]:
                if x < 0 or y < 0:
                    continue
                if s[i][j] == '.' or s[x][y] == '
                    scores[i][j] = min(scores[i][j], scores[x][y])
                else:
                    scores[i][j] = min(scores[i][j], scores[x][y] + 1)

    return scores[H - 1][W - 1]

if __name__ == '__main__':
    H, W = map(int, input().split())
    s = []
    for _ in range(H):
        s.append(list(input()))

    print(solve(H, W, s))

Solution (Python):
h,w=map(int,input().split())
grid=[[1 if s=='

maxi=10**5
from collections import deque
visited=[[maxi]*w for _ in range(h)]
def bfs(s):
    q=deque()
    q.append(s)
    visited[s[0]][s[1]]=grid[s[0]][s[1]]
    for r in range(h):
        for c in range(w):
            if r>=1:
                visited[r][c]=min(visited[r][c],visited[r-1][c]+grid[r][c])
                if grid[r-1][c]==1:
                    visited[r][c]=min(visited[r][c],visited[r-1][c])
            if c>=1:
                visited[r][c]=min(visited[r][c],visited[r][c-1]+grid[r][c])
                if grid[r][c-1]==1:
                    visited[r][c]=min(visited[r][c],visited[r][c-1])
            

bfs([0,0])
print(visited[-1][-1])

Solution (Python):
H, W = map(int, input().split())


black = [[0 for c in range(W)] for r in range(H)]

dp = [[int(1e18) for c in range(W)] for r in range(H)]

for r in range(H):
    line = input()
    for c in range(W):
        black[r][c] = (line[c] == '

dp[0][0] = black[0][0] 

for r in range(H):
    for c in range(W):
        if r >= 1:
            
            dp[r][c] = min(dp[r][c], dp[r-1][c] + (black[r][c] and not black[r-1][c]))
        if c >= 1:
            
            dp[r][c] = min(dp[r][c], dp[r][c-1] + (black[r][c] and not black[r][c-1]))

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

Solution (Python):
h,w = map(int,input().split())
a = [[(i == "
dp = [[float("inf")]*w for _ in range(h)]
dp[0][0] = a[0][0]
def cnt(i0,j0,i1,j1):
  if a[i0][j0] == 0 and a[i1][j1] == 1:
    return 1
  return 0

for s in range(h+w):
  for i in range(s+1):
    j = s - i
    if i >= h or j >= w:
      continue
    if i < h-1:
      dp[i+1][j] = min(dp[i+1][j],dp[i][j]+cnt(i,j,i+1,j))
    if j < w-1:
      dp[i][j+1] = min(dp[i][j+1],dp[i][j]+cnt(i,j,i,j+1))
print(dp[-1][-1])

Solution (Python):
import sys
from collections import deque

sys.setrecursionlimit(10 ** 7)
f_inf = float('inf')
mod = 10 ** 9 + 7


def resolve():
    H, W = map(int, input().split())
    S = [list(input()) for _ in range(H)]

    
    flip = [[f_inf for _ in range(W)] for _ in range(H)]

    if S[0][0] == "
        flip[0][0] = 1
    else:
        flip[0][0] = 0

    que = deque([[0, 0]])
    while que:
        h, w = que.popleft()
        for dh, dw in ((0, 1), (1, 0)):
            next_h, next_w = h + dh, w + dw
            if next_h >= H or next_w >= W:
                continue

            if flip[next_h][next_w] == f_inf:
                que.append([next_h, next_w])

            
            if S[h][w] != S[next_h][next_w]:
                flip[next_h][next_w] = min(flip[next_h][next_w], flip[h][w] + 1)
            else:
                flip[next_h][next_w] = min(flip[next_h][next_w], flip[h][w])

    if S[H - 1][W - 1] == "
        flip[H - 1][W - 1] += 1

    
    print(flip[H - 1][W - 1] // 2)


if __name__ == '__main__':
    resolve()

Solution (Python):
H,W=map(int,input().split())

s=[]

for r in range(H):
    s.append(list(input()))

c=[[200]*W for i in range(H)]
if s[0][0]==".":
    c[0][0]=0
else:
    c[0][0]=1

def rec(y,x):
    if c[y][x]!=200:
        return c[y][x]
    elif y==0 and x!=0:
        temp=rec(y,x-1)
        if s[y][x]!=s[y][x-1]:
            if s[y][x]=="
                temp+=1
        c[y][x]=temp
        return temp
    elif y!=0 and x==0:
        temp=rec(y-1,x)
        if s[y][x]!=s[y-1][x]:
            if s[y][x]=="
                temp+=1
        c[y][x]=temp
        return temp
    else:
        temp1 = rec(y, x - 1)
        if s[y][x] != s[y][x-1]:
            if s[y][x] == "
                temp1 += 1
        temp2 = rec(y - 1, x)
        if s[y][x] != s[y - 1][x]:
            if s[y][x] == "
                temp2 += 1
        temp=min(temp1,temp2)
        c[y][x]=temp
        return temp

ans=rec(H-1,W-1)

print(ans)

Solution (Python):
from queue import deque

h,w = map(int,input().split())
li = [input() for _ in range(h)]

inf = 10**10
dx = [1,0]
dy = [0,1]
que = deque()


flip_count = [[inf for i in range(w)]for j in range(h)]

if li[0][0] == "
    flip_count[0][0] = 1
else:
    flip_count[0][0] = 0

que.append([0,0])

while que:
    k = que.popleft()
    x = k[0]
    y = k[1]
    for i,j in zip(dx,dy):
        nx = x + i
        ny = y + j
        if nx >= w or ny >= h:
            continue
        if flip_count[ny][nx] == inf:
            que.append([nx,ny])
        if li[ny][nx] != li[y][x]:
            flip_count[ny][nx] = min(flip_count[ny][nx],flip_count[y][x]+1)
        else:
            flip_count[ny][nx] = min(flip_count[ny][nx],flip_count[y][x])

if li[-1][-1] == "
    flip_count[-1][-1] += 1

print(flip_count[-1][-1]//2)

Solution (Python):
from queue import deque

h,w = map(int,input().split())
li = [input() for _ in range(h)]

inf = 10**10
dx = [1,0]
dy = [0,1]
que = deque()


flip_count = [[inf for i in range(w)]for j in range(h)]

if li[0][0] == "
    flip_count[0][0] = 1
else:
    flip_count[0][0] = 0

que.append([0,0])

while que:
    k = que.popleft()
    x = k[0]
    y = k[1]
    for i,j in zip(dx,dy):
        nx = x + i
        ny = y + j
        if nx >= w or ny >= h:
            continue
        if flip_count[ny][nx] == inf:
            que.append([nx,ny])
        if li[ny][nx] != li[y][x]:
            flip_count[ny][nx] = min(flip_count[ny][nx],flip_count[y][x]+1)
        else:
            flip_count[ny][nx] = min(flip_count[ny][nx],flip_count[y][x])

if li[-1][-1] == "
    flip_count[-1][-1] += 1

print(flip_count[-1][-1]//2)

Solution (Python):
INF = 10**9

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


dp = [[INF for j in range(W)] for i in range(H)]

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

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

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

Solution (Python):
import numpy as np
import sys
read = sys.stdin.read
readline = sys.stdin.readline
readlines = sys.stdin.readlines
H, W = map(int, input().split())

I = [list(map(str, input())) for _ in range(H)]

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

for i in range(H):
	for j in range(W):
		if i == 0 and j == 0:
			continue
		if i == 0:
			dp[i][j] = dp[i][j-1] if I[i][j] == I[i][j-1] else dp[i][j-1] + 1
			continue
		if j == 0:
			dp[i][j] = dp[i-1][j] if I[i][j] == I[i-1][j] else dp[i-1][j] + 1
			continue

		dp[i][j] = dp[i][j-1] if I[i][j] == I[i][j-1] else dp[i][j-1] + 1
		if I[i][j] == I[i-1][j]:
			dp[i][j] = min(dp[i][j], dp[i-1][j])
		else:
			dp[i][j] = min(dp[i][j], dp[i-1][j] + 1)	

t = dp[-1][-1]
if I[0][0] == "
	t += 1
ans = -(-t//2)

print(ans)

Solution (Python):
import numpy as np

def func(x,y):
    if y-x == 2:
        return 1
    else:
        return 0


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

d = np.zeros((H,W))
dp = np.zeros((H,W))

for i in range(H):
    for j in range(W):
        if l[i][j] == "
            d[i][j] = 1
        else:
            d[i][j] = -1



for i in range(H-1):
    dp[i+1][0] = dp[i][0]+func(d[i][0],d[i+1][0])

for i in range(W-1):
    dp[0][i+1] = dp[0][i]+func(d[0][i],d[0][i+1])

for i in range(H-1):
    for j in range(W-1):
        dp[i+1][j+1]=min(dp[i][j+1]+func(d[i][j+1],d[i+1][j+1]),dp[i+1][j]+func(d[i+1][j],d[i+1][j+1]))

a = int(dp[-1][-1])
if d[0][0] == 1:
    a +=1
print(a)

Solution (Python):
h, w = map(int,input().split())
s_l = []
for i in range(h):
    s_l.append(list(input()))
    for j in range(w):
        if s_l[i][j] == '.':
            s_l[i][j] = 0
        else:
            s_l[i][j] = 1

dp = []
for _ in range(h):
    dp.append([0] * w)

if s_l[0][0] != 0:
    dp[0][0] += 1

for i in range(1,h):
    if dp[i-1][0]%2 != s_l[i][0]:
        dp[i][0] = dp[i-1][0] + 1
    else:
        dp[i][0] = dp[i-1][0]
for j in range(1,w):
    if dp[0][j-1]%2 != s_l[0][j]:
        dp[0][j] = dp[0][j-1] + 1
    else:
        dp[0][j] = dp[0][j-1]

for i in range(1,h):
    for j in range(1,w):
        if dp[i-1][j]%2 != s_l[i][j]:
            plus_i = 1
        else:
            plus_i = 0
        if dp[i][j-1]%2 != s_l[i][j]:
            plus_j = 1
        else:
            plus_j = 0
        dp[i][j] = min(dp[i-1][j] + plus_i, dp[i][j-1] + plus_j)


print((dp[h-1][w-1]+1)//2)

Solution (Python):
H,W,*L = open(0).read().split()
H,W = map(int, (H,W))
dp = [[0]*W for i in range(H)]
for i in range(1,H):
  if L[i][0]!=L[i-1][0]:
    dp[i][0] = dp[i-1][0]+1
  else:
    dp[i][0] = dp[i-1][0]
for j in range(1,W):
  if L[0][j]!=L[0][j-1]:
    dp[0][j] = dp[0][j-1]+1
  else:
    dp[0][j] = dp[0][j-1]
for i in range(1,H):
  for j in range(1,W):
    if L[i][j]!=L[i-1][j] and L[i][j]!=L[i][j-1]:
      dp[i][j] = min(dp[i-1][j],dp[i][j-1])+1
    elif L[i][j]!=L[i-1][j]:
      dp[i][j] = min(dp[i-1][j]+1,dp[i][j-1])
    elif L[i][j]!=L[i][j-1]:
      dp[i][j] = min(dp[i-1][j],dp[i][j-1]+1)
    else:
      dp[i][j] = min(dp[i-1][j],dp[i][j-1])
if L[0][0]=='.':
  ans = (dp[H-1][W-1]+1)//2
else:
  ans = (dp[H-1][W-1]+2)//2
print(ans)

Solution (Python):
h,w=map(int,input().split())
dp=[[0]*w for i in range(h)]
s=[input()for i in range(h)]
if s[0][0]=="
    dp[0][0]=1
for i in range(1,w):
    if 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(w):
        if j==0:
            if s[i][j]=="
                dp[i][j]=dp[i-1][j]+1
            else:
                dp[i][j]=dp[i-1][j]
            continue
        if s[i][j]=="
            p,q=0,0
            if s[i-1][j]=="
                p=1
            if s[i][j-1]=="
                q=1
            dp[i][j]=min(dp[i-1][j]-p,dp[i][j-1]-q)+1
        else:
            dp[i][j]=min(dp[i-1][j],dp[i][j-1])
print(dp[-1][-1])

Solution (Python):
from heapq import heappush, heappop

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

dist = [[float('inf')] * W for _ in range(H)]
dist[0][0] = 0

h = [(0, 0, 0)]
while h :
  cc, cy, cx = heappop(h)
  for dy, dx in ((1, 0), (0, 1)) :
    ny, nx = cy + dy, cx + dx
    if 0 <= ny < H and 0 <= nx < W :
      nc = cc + (s[ny][nx] != s[cy][cx])
      if nc < dist[ny][nx] :
        heappush(h, (nc, ny, nx))
        dist[ny][nx] = nc
        
print((dist[H-1][W-1] + 2 - s[0][0] - s[-1][-1]) // 2)