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):
from sys import stdin, stdout

int_in = lambda: int(stdin.readline())
arr_in = lambda: [int(x) for x in stdin.readline().split()]
mat_in = lambda rows: [arr_in() for y in range(rows)]
str_in = lambda: stdin.readline().strip()
out = lambda o: stdout.write("{}\n".format(o))
arr_out = lambda o: out(" ".join(map(str, o)))
bool_out = lambda o: out("YES" if o else "NO")
tests = lambda: range(1, int_in() + 1)


def solve(h, w, matrix):
    dp = [[[0, False] for x in range(w)] for y in range(h)]
    for row in range(h):
        for col in range(w):
            dp[row][col][1] = matrix[row][col] == "
            prev = False
            if row > 0 and col > 0:
                if dp[row-1][col][0] < dp[row][col-1][0]:
                    prev = dp[row-1][col][1]
                    dp[row][col][0] = dp[row-1][col][0]
                elif dp[row-1][col][0] > dp[row][col-1][0]:
                    prev = dp[row][col-1][1]
                    dp[row][col][0] = dp[row][col-1][0]
                else:
                    prev = dp[row-1][col][1] or dp[row][col-1][1]
                    dp[row][col][0] = dp[row][col-1][0]
            elif row > 0:
                prev = dp[row-1][col][1]
                dp[row][col][0] = dp[row-1][col][0]
            elif col > 0:
                prev = dp[row][col-1][1]
                dp[row][col][0] = dp[row][col-1][0]
            if dp[row][col][1] and not prev:
                dp[row][col][0] += 1
    return dp[h-1][w-1][0]


if __name__ == "__main__":
    h, w = arr_in()
    matrix = [str_in() for x in range(h)]
    out(solve(h, w, matrix))

Solution (Python):
h,w=map(int,input().split())
m=[]
grid=[]
nextdfsstart=set()
nextdfsstart.add(0)
def dfs(x,y,colour):
  global grid
  global nextdfsstartcopy
  global visited
  grid[y][x]=depth
  visited.add(x+w*y)
  if x<w-1 and not x+1+y*w in visited:
    if m[y][x+1]==colour :
      dfs(x+1,y,colour)
    else:
      nextdfsstartcopy.add(x+1+y*w)
  if y<h-1 and not x+(y+1)*w in visited:
    if m[y+1][x]==colour :
      dfs(x,y+1,colour)
    else:
      nextdfsstartcopy.add(x+(y+1)*w)
for i in range(h):
  m.append(input())
  grid.append([])
  for j in range(w):
      grid[i].append(-1)
visited=set()
depth=0
while grid[h-1][w-1]==-1:
  nextdfsstartcopy=set()
  for i in nextdfsstart:
    if i in visited:
      continue
    k=i//w
    if (k+1)*w<=i:
      k+=1
    dfs(i%w,k,m[k][i%w])
  depth+=1
  nextdfsstart=nextdfsstartcopy.copy()
ans=grid[h-1][w-1]//2
if m[0][0]=='
  ans+=1
print(ans)

Solution (Python):
h, w = map(int, input().split())
s = [input() for _i in range(h)]
visit = [[float("inf") for _ in range(w)] for _j in range(h)]
visit[0][0] = 0
for i in range(h):
    for j in range(w):
        if i-1 >= 0:
            visit[i][j] = visit[i-1][j]+(s[i][j]!=s[i-1][j])
        if j-1 >= 0:
            visit[i][j] = min(visit[i][j], visit[i][j-1]+(s[i][j]!=s[i][j-1]))

if s[0][0]==s[h-1][w-1]==".":
    print(visit[h-1][w-1]//2)
elif s[0][0]==s[h-1][w-1]=="
    print(visit[h-1][w-1]//2 +1) 
else:
    print(visit[h-1][w-1]//2 +1)

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

ans = [[0 for i in range(w)] for j in range(h)]
for i, row in enumerate(s):
    for j, index in enumerate(row):
        if i == j == 0:
            if s[i][j] == "
                ans[i][j] = 1
        elif i == 0:
            if s[i][j] == s[i][j - 1]:
                ans[i][j] = ans[i][j - 1]
            else:
                ans[i][j] = ans[i][j - 1] + 1
        elif j == 0:
            if s[i][j] == s[i - 1][j]:
                ans[i][j] = ans[i - 1][j]
            else:
                ans[i][j] = ans[i - 1][j] + 1
        else:
            if s[i][j] == s[i - 1][j]:
                a1 = ans[i - 1][j]
            else:
                a1 = ans[i - 1][j] + 1
            if s[i][j] == s[i][j - 1]:
                a2 = ans[i][j - 1]
            else:
                a2 = ans[i][j - 1] + 1
            ans[i][j] = min(a1, a2)

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

Solution (Python):
h,w=map(int,input().split())
s=list()
for i in range(h):
    line=str(input())
    s.append(line)


result=list()
for i in range(h):
    line=list()
    for j in range(w):
        line.append(0)
    result.append(line)
def se(x,y):
    if x==0 and y==0:
        if s[0][0]=="
            result[x][y]=1
        else:
            result[x][y]=0
    elif x==0:
        if s[x][y-1]!=s[x][y]:
            result[x][y]=result[x][y-1]+1
        else:
            result[x][y]=result[x][y-1]
    elif y==0:
        if s[x-1][y]!=s[x][y]:
            result[x][y]=result[x-1][y]+1
        else:
            result[x][y]=result[x-1][y]
    else:
        if s[x][y-1]!=s[x][y]:
            a=result[x][y-1]+1
        else:
            a=result[x][y-1]
        if s[x-1][y]!=s[x][y]:
            b=result[x-1][y]+1
        else:
            b=result[x-1][y]
        result[x][y]=min(a,b)
        
for i in range(h):
    for j in range(w):
        se(i,j)
        
if s[h-1][w-1]=="
    result[h-1][w-1]+=1
else:
    pass


print(int(result[h-1][w-1]/2))

Solution (Python):
H, W = map(int, input().split())
data = [list(map(str, input())) for _ in range(H)]


def g(m):
    if data[0][0] == '.':
        a = 0
    else:
        a = 1

    for i in range(1, m, 1):
        if data[0][i] == '.':
            continue
        elif data[0][i] == '
            a += 1
        else:
            continue
    return a


def h(n):
    if data[0][0] == '.':
        a = 0
    else:
        a = 1

    for i in range(1, n, 1):
        if data[i][0] == '.':
            continue
        elif data[i][0] == '
            a += 1
        else:
            continue
    return a

A = [0] + [g(i) for i in range(1,W+1)]
B = [0] + [h(i) for i in range(1,H+1)]
C = [[0]*(W+1) for i in range(H+1)]

for n in range(1,H+1):
    for m in range(1,W+1):
        if n == 1:
            C[n][m] = A[m]
        elif m == 1:
            C[n][m] = B[n]
        else:
            if data[n - 1][m - 1] == '.':
                C[n][m] = min(C[n - 1][m], C[n][m - 1])
            elif data[n - 2][m - 1] == '.':
                if data[n - 1][m - 2] == '.':
                    C[n][m] = min(C[n - 1][m] + 1, C[n][m - 1] + 1)
                else:
                    C[n][m] =  min(C[n - 1][m] + 1, C[n][m - 1])
            else:
                if data[n - 1][m - 2] == '.':
                    C[n][m] = min(C[n - 1][m], C[n][m - 1] + 1)
                else:
                    C[n][m] = min(C[n - 1][m], C[n][m - 1])


print(C[H][W])

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

Solution (Python):
import sys
import re
import math
import collections
import decimal
import bisect
import itertools
import fractions
import functools
import copy
import heapq
import decimal
import statistics
import queue

sys.setrecursionlimit(10000001)
INF = 10 ** 10
MOD = 10 ** 9 + 7

ni = lambda: int(sys.stdin.readline())
ns = lambda: map(int, sys.stdin.readline().split())
na = lambda: list(map(int, sys.stdin.readline().split()))



def main():
    h, w = ns()
    mat = [list(input()) for _ in range(h)]

    ans_mat = [[INF for _ in range(w)] for _ in range(h)]
    if mat[0][0] == "
        ans_mat[0][0] = 1
    else:
        ans_mat[0][0] = 0

    for y in range(h):
        for x in range(w):
            if x + 1 < w:
                if mat[y][x] != mat[y][x + 1]:
                    ans_mat[y][x + 1] = min(ans_mat[y][x + 1], ans_mat[y][x] + 1)
                else:
                    ans_mat[y][x + 1] = min(ans_mat[y][x + 1], ans_mat[y][x])

            if y + 1 < h:
                if mat[y][x] != mat[y + 1][x]:
                    ans_mat[y + 1][x] = min(ans_mat[y + 1][x], ans_mat[y][x] + 1)
                else:
                    ans_mat[y + 1][x] = min(ans_mat[y + 1][x], ans_mat[y][x])

    tmp = ans_mat[h - 1][w - 1]
    print(tmp - tmp // 2)


if __name__ == '__main__':
    main()

Solution (Python):
import sys
readline = sys.stdin.buffer.readline
sys.setrecursionlimit(10 ** 8)
INF = float('inf')
MOD = 10 ** 9 + 7

def main():
    H, W = map(int, readline().split())
    S = list(readline().decode('utf-8').strip() for _ in range(H))
    dp = [[INF] * (W) for _ 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:
                if S[i][j]=='.' and S[i+1][j]=='
                    dp[i+1][j] = min(dp[i+1][j],dp[i][j]+1)
                else:
                    dp[i+1][j] = min(dp[i+1][j],dp[i][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+1],dp[i][j])


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

if __name__ == '__main__':
    main()

Solution (Python):
import sys
readline = sys.stdin.buffer.readline
sys.setrecursionlimit(10 ** 8)
INF = float('inf')
MOD = 10 ** 9 + 7

def main():
    H, W = map(int, readline().split())
    S = list(readline().decode('utf-8').strip() for _ in range(H))
    dp = [[INF] * (W) for _ 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 j==W-1:
                if S[i][j]=='.' and S[i+1][j]=='
                    dp[i+1][j] = min(dp[i+1][j],dp[i][j]+1)
                else:
                    dp[i+1][j] = min(dp[i+1][j],dp[i][j])
            elif i == H-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+1],dp[i][j])
            else:
                if S[i][j]=='.' and S[i+1][j]=='
                    dp[i+1][j] = min(dp[i+1][j],dp[i][j]+1)
                else:
                    dp[i+1][j] = min(dp[i+1][j],dp[i][j])
                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+1],dp[i][j])


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

if __name__ == '__main__':
    main()

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

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

for i in range(H):
    for j in range(W):
        if i == j == 0:
            if s[i][j] == '
                dp[i][j] = 1
            continue
        c = []
        if 0 <= i - 1 < H:
            c.append(dp[i - 1][j]
                     + (1 if s[i - 1][j] == '.' and s[i][j] == '
        if 0 <= j - 1 < W:
            c.append(dp[i][j - 1]
                     + (1 if s[i][j - 1] == '.' and s[i][j] == '
        if len(c) > 0:
            dp[i][j] = min(c)

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

Solution (Python):
INF=10**18
H,W=map(int,input().split())
G=[list(input()) for i in range(H)]

dp=[[INF]*W for i in range(H)]
dp[0][0]=0
dx=[0,1]
dy=[1,0]

for i in range(H):
    for j in range(W):
        for x,y in zip(dx,dy):
            if i+x>=H or j+y>=W:
                continue
            if G[i][j]=='.' and G[i+x][j+y]=='
                dp[i+x][j+y]=min(dp[i][j]+1,dp[i+x][j+y])
            else:
                dp[i+x][j+y]=min(dp[i][j],dp[i+x][j+y])
ans=dp[H-1][W-1]
print(ans if G[0][0]!='

Solution (Python):
import itertools,sys
def S(): return sys.stdin.readline().rstrip()
def LI(): return list(map(int,sys.stdin.readline().rstrip().split()))
H,W = LI()
S = [S() for _ in range(H)]
dp = [[float('INF')]*W for _ in range(H)]
for i,j in itertools.product(range(H),range(W)):
    if i==0:
        if j==0:
            dp[i][j] = 1 if S[i][j]=='
        else:
            dp[i][j] = dp[i][j-1]+(1 if S[i][j]=='
    else:
        if i==0:
            dp[i][j] = dp[i-1][j]+(1 if S[i][j]=='
        else:
            dp[i][j] = min(dp[i][j],dp[i][j-1]+(1 if S[i][j]=='
            dp[i][j] = min(dp[i][j],dp[i-1][j]+(1 if S[i][j]=='
print(dp[-1][-1])

Solution (Python):
import sys
sys.stdin.readline

H, W = map(int, input().split())
board = [[[0,1][a == "
Y = [[0]*W for _ in range(H)]

for i in range(H):
    for j in range(W):
        a = []
        if j == 0:
            pass
        else:
            if board[i][j-1] == False and board[i][j] == True:
                a.append(Y[i][j-1] + 1)
            else:
                a.append(Y[i][j-1])
        if i == 0:
            pass
        else:
            if board[i-1][j] == False and board[i][j] == True:
                a.append(Y[i-1][j] + 1)
            else:
                a.append(Y[i-1][j])
        if i + j == 0:
            if board[i][j]:
                a.append(1)
            else:
                continue
        Y[i][j] = min(a)


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

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

Solution (Python):
from sys import stdin, stdout
from collections import deque, defaultdict
import math as m

rl = lambda: stdin.readline()
rll = lambda: stdin.readline().split()
rli = lambda: map(int, stdin.readline().split())

INF, NINF = float('inf'), float('-inf')

def main():
	H, W = rli()
	M = []
	
	for _ in range(H):
		row = list(rll()[0])
		row = list(map(lambda x: 0 if x == "." else 1, row))
		M.append(row)

	dp = [[INF if i != 0 and j != 0 else 0 for j in range(W)] for i in range(H)]
	dp[0][0] = 1 if M[0][0] == 1 else 0
	
	for c in range(1, W):
		if M[0][c-1] == 0 and M[0][c] == 1:
			dp[0][c] = dp[0][c-1] + 1
		else:
			dp[0][c] = dp[0][c-1]
	for r in range(1, H):
		if M[r-1][0] == 0 and M[r][0] == 1:
			dp[r][0] = dp[r-1][0] + 1
		else:
			dp[r][0] = dp[r-1][0]

	for r in range(1, H):
		for c in range(1, W):
			c1, c2 = INF, INF
			if M[r-1][c] == 0 and M[r][c] == 1:
				c1 = dp[r-1][c] + 1
			if M[r][c-1] == 0 and M[r][c] == 1:
				c2 = dp[r][c-1] + 1
			c1 = dp[r-1][c] if c1 == INF else c1 
			c2 = dp[r][c-1] if c2 == INF else c2
			dp[r][c] = min(c1, c2)
	print(dp[-1][-1])
	stdout.close()

if __name__ == "__main__":
	main()

Solution (Python):
import sys

H, W = map(int, input().split())
G = [list(sys.stdin.readline().strip()) for _ in range(H)]

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

DP[0][0] = int(G[0][0] == "
for i in range(1, H):
    DP[i][0] = DP[i - 1][0] + int(G[i][0] == "
for j in range(1, W):
    DP[0][j] = DP[0][j - 1] + int(G[0][j] == "

for i in range(1, H):
    for j in range(1, W):
        t = int(G[i][j] == "
        DP[i][j] = min(DP[i - 1][j] + int(t and G[i - 1][j] == "."), DP[i][j - 1] + int(t and G[i][j - 1] == "."))

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

Solution (Python):
H, W = map(int, input().split())
s = []
for _ in range(H):
  s.append(input())
  
def main(H, W, s):
  
  
  INF = float('inf')
  dp = [[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 + dx[dir_]
        nj = j + dy[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)

  return dp[H-1][W-1]

print(main(H, W, s))

Solution (Python):
h,w = map(int,input().split())
B = [input() for _ in range(h)]
dp=[]
def ch(x1,y1,x2,y2):
    if B[x1][y1]=='.' and B[x2][y2]=='
        return 1
    else:
        return 0
dp = [[0 for j in range(w)] for i in range(h)]
for i in range(h):
    for j in range(w):
        if i==0 and j==0 and B[i][j]=='
            dp[i][j]+=1
        elif i==0:
            dp[i][j] = dp[i][j-1]+ch(i,j-1,i,j)
        elif j==0:
            dp[i][j] = dp[i-1][j]+ch(i-1,j,i,j)
        else:
            dp[i][j] = min(dp[i][j-1]+ch(i,j-1,i,j),dp[i-1][j]+ch(i-1,j,i,j))
print(dp[h-1][w-1])

Solution (Python):
import sys


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

    for y in range(H):
        for x in range(W):
            if x == 0 and y == 0:
                if s[0][0] == "
                    dp[0][0] = 1
            elif x == 0:
                if s[y][x] == "
                    dp[y][x] = dp[y - 1][x] + 1
                else:
                    dp[y][x] = dp[y - 1][x]
            elif y == 0:
                if s[y][x] == "
                    dp[y][x] = dp[y][x - 1] + 1
                else:
                    dp[y][x] = dp[y][x - 1]
            else:
                if s[y][x] == "
                    dp[y][x] = min(dp[y][x - 1], dp[y - 1][x]) + 1
                elif s[y][x] == "
                    dp[y][x] = min(dp[y][x - 1] + 1, dp[y - 1][x])
                elif s[y][x] == "
                    dp[y][x] = min(dp[y][x - 1], dp[y - 1][x] + 1)
                else:
                    dp[y][x] = min(dp[y][x - 1], dp[y - 1][x])

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


if __name__ == "__main__":
    H, W = map(int, sys.stdin.readline().split())
    s = [list(sys.stdin.readline().rstrip()) for _ in range(H)]
    main()

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

dp = [[10 ** 9 for i in range(W)] for j in range(H)]
dp[0][0] = 0 if s[0][0] == '.' else 1

for i in range(H):
    for j in range(W):
        if i + 1 < H:
            cost = int(s[i][j] == '.' and s[i + 1][j] == '
            dp[i + 1][j] = min(dp[i + 1][j], dp[i][j] + cost)
        if j + 1 < W:
            cost = int(s[i][j] == '.' and s[i][j + 1] == '
            dp[i][j + 1] = min(dp[i][j + 1], dp[i][j] + cost)

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

Solution (Python):
def main():

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

    dp = [[float('inf') for _ in range(W+1)] for _ in range(H+1)]

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



if __name__ == '__main__':
    print(main())

Solution (Python):
import sys
def input(): return sys.stdin.readline().rstrip()
def main():
    h,w=map(int,input().split())
    S=[input() for _ in range(w)]
    DP=[[0]*w for _ in range(h)]
    if S[0][0]=='
        DP[0][0]=1
    for j in range(1,w):
        if S[0][j-1]=='.' and S[0][j]=='
            DP[0][j]=DP[0][j-1]+1
        else:
            DP[0][j]=DP[0][j-1]
    for i in range(1,h):
        if S[i-1][0]=='.' and S[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 S[i-1][j]=='.' and S[i][j]=='
                d=DP[i-1][j]+1
            else:
                d=DP[i-1][j]
            if S[i][j-1]=='.' and S[i][j]=='
                r=DP[i][j-1]+1
            else:
                r=DP[i][j-1]
            DP[i][j]=min(d,r)
    print(DP[-1][-1])

if __name__=='__main__':
    main()

Solution (Python):
import sys
def input(): return sys.stdin.readline().rstrip()
def main():
    h,w=map(int,input().split())
    S=[input() for _ in range(w)]
    DP=[[0]*w for _ in range(h)]
    if S[0][0]=='
        DP[0][0]=1
    for j in range(1,w):
        if S[0][j-1]=='.' and S[0][j]=='
            DP[0][j]=DP[0][j-1]+1
        else:
            DP[0][j]=DP[0][j-1]
    for i in range(1,h):
        if S[i-1][0]=='.' and S[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 S[i-1][j]=='.' and S[i][j]=='
                d=DP[i-1][j]+1
            else:
                d=DP[i-1][j]
            if S[i][j-1]=='.' and S[i][j]=='
                r=DP[i][j-1]+1
            else:
                r=DP[i][j-1]
            DP[i][j]=min(d,r)
    print(DP[-1][-1])

if __name__=='__main__':
    main()

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

cnt = [[float('inf')]*w for _ in range(h)]
if s[0][0] == '.':
    cnt[0][0] = 0
else:
    cnt[0][0] = 1

for i in range(h):
    for j in range(w):
        for dy, dx in [[1, 0], [0, 1]]:
            x = j+dx
            y = i+dy
            if x >= w or y >= h:
                continue
            if s[i][j] == s[y][x]:
                cnt[y][x] = min(cnt[y][x], cnt[i][j])
            else:
                cnt[y][x] = min(cnt[y][x], cnt[i][j] + 1)

if s[-1][-1] == '
    cnt[-1][-1] += 1
print(cnt[-1][-1]//2)

Solution (Python):
h,w = map(int, input().split())
s = [input()+"." for i in range(h)] + ["."*(w+1)]
INF = 10 ** 18
dp = [[INF]*(w+1) for i in range(h+1)]
dp[0][0] = 1 if s[0][0] == "
for i in range(h):
  for j in range(w):
    if s[i][j] == "
      dp[i+1][j] = min(dp[i+1][j], dp[i][j])
      dp[i][j+1] = min(dp[i][j+1], dp[i][j])
    else:
      vi = 1 if s[i+1][j] == "
      vj = 1 if s[i][j+1] == "
      dp[i+1][j] = min(dp[i+1][j], dp[i][j]+vi)
      dp[i][j+1] = min(dp[i][j+1], dp[i][j]+vj)
print(dp[h-1][w-1])

Solution (Python):
h, w = map(int, input().split())
S = [input() for i in range(h)]
DP = [[0 for j in range(w)] for i in range(h)]
if S[0][0] == '
    DP[0][0] = 1
for j in range(1, w):
    if S[0][j - 1] == '.' and S[0][j] == '
        DP[0][j] = DP[0][j - 1] + 1
    else:
        DP[0][j] = DP[0][j - 1]
for i in range(1, h):
    if S[i - 1][0] == '.' and S[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 S[i - 1][j] == '.' and S[i][j] == '
            up = DP[i - 1][j] + 1
        else:
            up = DP[i - 1][j]
        if S[i][j - 1] == '.' and S[i][j] == '
            left = DP[i][j - 1] + 1
        else:
            left = DP[i][j - 1]
        DP[i][j] = min(up, left)
print(DP[-1][-1])

Solution (Python):
import sys

readline = sys.stdin.readline
inf = float('inf')

def main():
    H, W = map(int, readline().split())
    grid = []
    grid.append(['*'] * (W+2))
    for _ in range(H):
        grid.append(['*'] + list(readline()[:-1]) + ['*'])
    grid.append(['*']*(W+2))

    DP = [[inf] * (W+2) for _ in range(H+2)]
    DP[1][1] = (grid[1][1] == '

    for i in range(1, H+1):
        for j in range(1, W+1): 
            if i == 1 and j == 1:
                continue
            k = i
            gridkj = grid[k][j]
            if gridkj == '.':
                DP[k][j] = min(DP[k][j-1], DP[k-1][j])
            if gridkj == '
                DP[k][j] = min(DP[k][j-1]+(grid[k][j-1] in ['.', '*']), DP[k-1][j] + (grid[k-1][j] in ['.', '*']))
    ans = DP[H][W]
    print(ans)

if __name__ == "__main__":
    main()

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

S = [input() for _ in range(H)]

INF = 10 ** 5
dp = [[INF] * (W + 1) for _ in range(H + 1)]
dp[0][0] = int(S[0][0] == '

for i in range(H):
    for j in range(W):

        
        if j == 0:
            v1 = INF
        else:
            v1 = int(S[i][j - 1] == '.' and S[i][j] == '

        
        if i == 0:
            v2 = INF
        else:
            v2 = int(S[i - 1][j] == '.' and S[i][j] == '

        dp[i][j] = min(v1, v2, dp[i][j])
ans = dp[H - 1][W - 1]
print(ans)

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

dp = [[0]*W for _ in range(H)]
if S[0][0] == "
    dp[0][0] = 1

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

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


for i in range(1, H):
    for j in range(1, W):
        if S[i][j] == S[i-1][j]:
            a = dp[i-1][j]
        else:
            a = dp[i-1][j]+1
        if S[i][j] == S[i][j-1]:
            b = dp[i][j-1]
        else:
            b = dp[i][j-1]+1
        dp[i][j] = min(a, b)

print((dp[H-1][W-1]+1)//2)

Solution (Python):
from collections import deque


H,W = map(int, input().split())

S = [input() for _ in range(H)]


"""
移動先の色が同じであれば、その部分は一回の操作でひっくり返せるので、黒から黒へ連続で移動していても操作回数は一回でOK

"""
INF = float("inf")
costs = [[INF for _ in range(W)] for _ in range(H)]

costs[0][0] = 0 if S[0][0] == "." else 1

q = deque()
q.append((costs[0][0], 0, 0))

while q:
    curr_cost, y, x = q.popleft()
    for dy, dx in [(1,0), (0,1)]:
        if y + dy >= H or x + dx >= W:
            continue
        nxt_cost = curr_cost if S[y][x] == S[y+dy][x+dx] else curr_cost + 1
        if nxt_cost < costs[y+dy][x+dx]:
            costs[y+dy][x+dx] = nxt_cost
            q.append((nxt_cost, y+dy, x+dx))


print((costs[-1][-1] + 1) // 2)

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

def pl(x1,y1,x2,y2):
    if s[x1][y1] == "." and s[x2][y2] == "
        return 1
    else:
        return 0

dp = [[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 and s[i][j] == "
            dp[i][j] += 1
        elif i == 0:
            dp[i][j] = dp[i][j-1]+pl(i,j-1,i,j)
        elif j == 0:
            dp[i][j] = dp[i-1][j]+pl(i-1,j,i,j)
        else:
            dp[i][j] = min(dp[i][j-1]+pl(i,j-1,i,j),dp[i-1][j]+pl(i-1,j,i,j))

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

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):
h,w=map(int,input().split())
s=[]
for i in range(h):
    s.append(list(input()))

dp=[[99999999 for i 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(s[i][j-1] != s[i][j]):
            left = dp[i][j-1]+1
        else:
            left = dp[i][j-1]

        if(s[i-1][j] != s[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())
 
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):
from statistics import median


from fractions import gcd
from itertools import combinations 
from collections import deque
from collections import defaultdict
import bisect










import sys
sys.setrecursionlimit(10000000)
mod = 10**9 + 7

def readInts():
  return list(map(int,input().split()))
def main():
    dx = [1,0]
    dy = [0,1]
    INF = float('inf')
    h,w = readInts()
    dp = [[INF]*w for _ in range(h)]
    FIELD = [input() for _ in range(h)]
    
    
    if FIELD[0][0] == '
        dp[0][0] = 1
    else:
        dp[0][0] = 0
    for i in range(w):
        for j in range(h):
            for x,y in dx,dy:
                ny = j + y
                nx = i + x
                if ny >= h or nx >= w:
                    continue
                add = 0
                if FIELD[ny][nx] == '
                    add = 1
                dp[ny][nx] = min(dp[ny][nx], dp[j][i] + add)
    print(dp[h-1][w-1])
if __name__ == '__main__':
  main()