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())
gridgraph = [input() for _ in range(H)]

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

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

adjacent = [[1, 0], [0, 1]]

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

Solution (Python):
import sys
H, W = map(int, input().split())
S = [list(s.rstrip()) for s in sys.stdin.readlines()]
dp = [[10**9] * W for _ in range(H)]
if S[0][0] == '
  dp[0][0] = 1
else:
  dp[0][0] = 0
for h in range(H):
  for w in range(W):
    for a, b in ((h+1, w), (h, w+1)):
      if a >= H or b >= W:
        continue
      else:
        if S[h][w] == '.' and S[a][b] == '
          dp[a][b] = min(dp[a][b], dp[h][w]+1)
        else:
          dp[a][b] = min(dp[a][b], dp[h][w])
print(dp[H-1][W-1])

Solution (Python):
import sys

h, w = map(int, input().split())
s = [list(x.rstrip()) for x in sys.stdin.readlines()]
dp = [[10**6]*w for _ 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):
        for k in range(2):
            nx, ny = i + (k + 1)%2, j + k%2
            if nx >= w or ny >= h:
                continue
            else:
                add = 0
                if s[ny][nx] == "
                    add = 1
                dp[ny][nx] = min(dp[ny][nx], dp[j][i] + add)
print(dp[h-1][w-1])

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

N = [[10**9]*W]*H
l = 0
u = 0
if S[0][0] == '
    N[0][0] = 1
else :
    N[0][0] = 0
for i in range(H) :
    for j in range(W) :
        if i == 0 and j == 0 :
            continue
        
        l = N[i][j-1]
        
        u = N[i-1][j]

        if S[i][j-1] == '.' and  S[i][j] == '
            l += 1
        if S[i-1][j] == '.' and  S[i][j] == '
            u += 1
        N[i][j] = min(l,u)

print(N[-1][-1])

Solution (Python):
import sys
import math
import copy
import heapq
from functools import cmp_to_key
from bisect import bisect_left, bisect_right
from collections import defaultdict, deque, Counter
sys.setrecursionlimit(1000000)


input = sys.stdin.readline
getS = lambda: input().strip()
getN = lambda: int(input())
getList = lambda: list(map(int, input().split()))
getZList = lambda: [int(x) - 1 for x in input().split()]

INF = float("inf")
MOD = 10**9 + 7
divide = lambda x: pow(x, MOD-2, MOD)

def nck(n, k, kaijyo):
    return (npk(n, k, kaijyo) * divide(kaijyo[k])) % MOD

def npk(n, k, kaijyo):
    if k == 0 or k == n:
        return n % MOD
    return (kaijyo[n] * divide(kaijyo[n-k])) % MOD

def fact_and_inv(SIZE):
    inv = [0] * SIZE  
    fac = [0] * SIZE  
    finv = [0] * SIZE  
    inv[1] = 1
    fac[0] = fac[1] = 1
    finv[0] = finv[1] = 1
    for i in range(2, SIZE):
        inv[i] = MOD - (MOD // i) * inv[MOD % i] % MOD
        fac[i] = fac[i - 1] * i % MOD
        finv[i] = finv[i - 1] * inv[i] % MOD

    return fac, finv

def renritsu(A, Y):
    
    
    
    A = np.matrix(A)
    Y = np.matrix(Y)
    Y = np.reshape(Y, (-1, 1))
    X = np.linalg.solve(A, Y)

    
    return X.flatten().tolist()[0]

class TwoDimGrid:
    
    def __init__(self, h, w, wall="o"):
        self.h = h
        self.w = w
        self.size = (h+2) * (w+2)
        self.wall = wall
        self.get_grid()
        self.init_cost()

    def get_grid(self):
        grid = [self.wall * (self.w + 2)]
        for i in range(self.h):
            grid.append(self.wall + getS() + self.wall)

        grid.append(self.wall * (self.w + 2))
        self.grid = grid
    def init_cost(self):
        self.cost = [INF] * self.size

    def pos(self, x, y):
        
        return y * (self.w + 2) + x
    def getgrid(self, x, y):
        return self.grid[y][x]
    def get(self, x, y):
        return self.cost[self.pos(x, y)]
    def set(self, x, y, v):
        self.cost[self.pos(x, y)] = v
        return
    def show(self):
        for i in range(self.h+2):
            print(self.cost[(self.w + 2) * i:(self.w + 2) * (i+1)])
    def showsome(self, tgt):
        for t in tgt:
            print(t)
        return
    def showsomejoin(self, tgt):
        for t in tgt:
            print("".join(t))
        return

    def search(self):
        grid = self.grid
        move = [(0, 1), (0, -1), (1, 0), (-1, 0)]
        move_eight = [(0, 1), (0, -1), (1, 0), (-1, 0), (1, 1), (1, -1), (-1, 1), (-1, -1)]
        d = deque()
        d.append((1,1))
        self.set(1,1,0)
        while(d):
            cx, cy = d.popleft()
            cc = self.get(cx, cy)
            if self.getgrid(cx, cy) == self.wall:
                continue
            for dx, dy in [(1, 0), (0, 1)]:
                nx, ny = cx + dx, cy + dy
                if self.getgrid(cx, cy) == self.getgrid(nx, ny):
                    if self.get(nx, ny) > cc:
                        d.append((nx, ny))
                        self.set(nx, ny, cc)
                else:
                    if self.get(nx, ny) > cc + 1:
                        d.append((nx, ny))
                        self.set(nx, ny, cc + 1)

        
        ans = (self.get(self.w, self.h))
        if self.getgrid(1,1) == "
            ans += 1
        print((ans + 1) // 2)

def soinsu(n):
    ret = defaultdict(int)
    for i in range(2, int(math.sqrt(n) + 2)):
        if n % i == 0:
            while True:
                if n % i == 0:
                    ret[i] += 1
                    n //= i
                else:
                    break

    if not ret:
        return {n: 1}
    return ret


def solve():
    h, w = getList()
    G = TwoDimGrid(h, w)
    G.search()




def main():
    n = getN()
    for _ in range(n):
        solve()

    return
if __name__ == "__main__":
    
    solve()

Solution (Python):
h,w=map(int,input().split())
s=[0]*h
t=[0]*h
for i in range(h):
  st=str(input())
  st=list(st)
  s[i]=st
  tt=[0]*w
  t[i]=tt
if s[0][0]=="
  t[0][0]=1
for i in range(1,h):
  t[i][0]=t[i-1][0]
  if s[i-1][0]=="." and s[i][0]=="
    t[i][0]=t[i-1][0]+1
for i in range(1,w):
  t[0][i]=t[0][i-1]
  if s[0][i-1]=="." and s[0][i]=="
    t[0][i]=t[0][i-1]+1
for i in range(1,w):
  for j in range(1,h):
    if s[j-1][i]=="." and s[j][i]=="
      t1=t[j-1][i]+1
    else:
      t1=t[j-1][i]
    if s[j][i-1]=="." and s[j][i]=="
      t2=t[j][i-1]+1
    else:
      t2=t[j][i-1]
    t[j][i]=min(t1,t2)
print(t[h-1][w-1])

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


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

for h_i in range(h):
    for w_i in range(w):
        if h_i+1 < h:
            if sl[h_i][w_i] == '.' and sl[h_i+1][w_i] == '
                dp[h_i+1][w_i] = min( dp[h_i+1][w_i], dp[h_i][w_i]+1 )
            else:
                dp[h_i+1][w_i] = min( dp[h_i+1][w_i], dp[h_i][w_i] )

        if w_i+1 < w:
            if sl[h_i][w_i] == '.' and sl[h_i][w_i+1] == '
                dp[h_i][w_i+1] = min( dp[h_i][w_i+1], dp[h_i][w_i]+1 )
            else:
                dp[h_i][w_i+1] = min( dp[h_i][w_i+1], dp[h_i][w_i] )


ans = dp[h-1][w-1]
if sl[0][0] == '
print(ans)

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

dp = [[0]*(W+1) for _ in range(H+1)]
for h in range(H+1):
    dp[h][0] = H*2
for w in range(W+1):
    dp[0][w] = W*2
dp[0][1] = 0

for h in range(1, H+1):
    for w in range(1, W+1):
        dp[h][w] = min(dp[h-1][w]+(S[h][w]!=S[h-1][w]), dp[h][w-1]+(S[h][w]!=S[h][w-1]))

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

Solution (Python):

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

inf = 10**9
dp = [[inf] * (W+1) for _ in range(H+1)]
dp[0][0] = 0 if table[0][0] == "." else 1

for h in range(H):
    for w in range(W):
        flg = table[h][w] == "." and (table[h][w+1] == "
        dp[h][w+1] = min(dp[h][w+1], dp[h][w] + 1 if flg else dp[h][w])

        flg = table[h][w] == "." and (table[h+1][w] == "
        dp[h+1][w] = dp[h][w] + 1 if flg else dp[h][w]

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

Solution (Python):
def input_li():
    return list(map(int, input().split()))

def input_int():
    return int(input())

H, W = input_li()
board = [input() for _ in range(H)]

dp = [[10 ** 9] * W for _ in range(H)]
dp[0][0] = 1 if board[0][0] == '
for h in range(H):
    for w in range(W):
        is_now_black = board[h][w] == '
        if h == 0 and w != 0:
            dp[h][w] = dp[h][w - 1] + (1 if is_now_black and board[h][w - 1] == '.' else 0)
        elif h != 0 and w == 0:
            dp[h][w] = dp[h - 1][w] + (1 if is_now_black and board[h - 1][w] == '.' else 0)
        elif h != 0 and w != 0:
            from_w = dp[h][w - 1] + (1 if is_now_black and board[h][w - 1] == '.' else 0)
            from_h = dp[h - 1][w] + (1 if is_now_black and board[h - 1][w] == '.' else 0)
            dp[h][w] = min(from_h, from_w)
print(dp[-1][-1])

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

Solution (Python):

from collections import deque

h, w = map(int, input().split())
maze = [[i == "

dx = [1, 0]
dy = [0, 1]

que = deque([])
que.append((0, 0, maze[0][0], 1 if maze[0][0] else 0))
count = [[h + w] * w for _ in range(h)]

while que:
    x, y, b, c = que.pop()
    if c >= count[x][y]:
        continue
    count[x][y] = c
    if x == h - 1 and y == w - 1:
        continue
    for i in range(2):
        nx = x + dx[i]
        ny = y + dy[i]

        if not (0 <= nx < h and 0 <= ny < w):
            continue
        que.append((nx, ny, maze[nx][ny], c + (not b and maze[nx][ny])))
print(count[h - 1][w - 1])

Solution (Python):
def resolve():
    '''
    code here
    '''
    import collections
    import numpy as np
    H, W = [int(item) for item in input().split()]

    grid = [[item for item in input()] for _ in range(H)]
    dp = [[300 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 grid[0][0] == '
                    dp[i+1][j+1] = 1
                else:
                    dp[i+1][j+1] = 0
            else:
                add_v = 0
                add_h = 0
                if grid[i][j] != grid[i][j-1]:
                    add_h = 1
        
                if grid[i][j] != grid[i-1][j]:
                    add_v = 1

                dp[i+1][j+1] = min(dp[i+1][j]+add_h, dp[i][j+1]+add_v)
    
    if grid[H-1][W-1] == '
        print(dp[H][W]//2+1)
    else:
        print(dp[H][W]//2)

if __name__ == "__main__":
    resolve()

Solution (Python):
t,*b='.'*102
q=range(101)
for s in[*open(i:=0)][1:]:
 a=i,;i+=1
 for x,y,z,c in zip(b,t+s,s,q):a+=min(c+(t>z<x),a[-1]+(t>z<y)),
 b,q=s,a[1:]
print(a[-2])

Solution (Python):
t,*b='.'*102
q=range(101)
for s in[*open(i:=0)][1:]:
 a=[i];i+=1
 for x,y,z,c in zip(b,t+s,s,q):a+=min(c+(t>z<x),a[-1]+(t>z<y)),
 b,q=s,a[1:]
print(a[-2])

Solution (Python):
h,w= map(int,input().split())
tb = [input() for _ in range(h)]
st = [[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:st[i][j]= (1 if tb[i][j]=='
        else:
            tr=td=999999999
            if i!=0:
                td=st[i-1][j]+(1 if (tb[i-1][j]=='.' and tb[i][j]=='
            if j!=0:
                tr=st[i][j-1]+(1 if (tb[i][j-1]=='.' and tb[i][j]=='
            st[i][j]=min(td,tr)
print(st[h-1][w-1])

Solution (Python):
H, W = map(int, input().split())
s = [input() for _ in range(H)]
dp = [[float('inf') for _ in range(W)] for _ in range(H)]
if s[0][0] == '
    dp[0][0] = 1
else:
    dp[0][0] = 0
dx = [0, 1]
dy = [1, 0]

for i in range(H):
    for j in range(W):
        for k in range(2):
            ni = i + dx[k]
            nj = j + dy[k]
            if ni >= H or nj >= W:
                continue
            add = 0
            
            if s[i][j] == '.' and s[ni][nj] == '
            dp[ni][nj] = min(dp[ni][nj], dp[i][j] + add)

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

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

H,W = list(map(int,input().split()))
S = [ input().rstrip() 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

for i in range(H):
    for j in range(W):
        if i == 0 and j == 0:
            continue
        a = float('inf')
        b = float('inf')
        
        if i >= 1:
            a = dp[i-1][j] + ( S[i-1][j] =='.' and S[i][j] =='
        
        if j >= j:
            b=  dp[i][j-1] + ( S[i][j-1] =='.' and S[i][j] =='

        dp[i][j] = min(a,b)
print(dp[i][j])

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

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

for i in range(H):
    for j in range(W):
        if i == j == 0: 
            continue
        if i == 0:
            cost[i][j] = cost[i][j-1] + 1*(S[i][j] != S[i][j-1])
        elif j == 0:
            cost[i][j] = cost[i-1][j] + 1*(S[i][j] != S[i-1][j])
        else:
            cost[i][j] = min(cost[i][j-1] + 1*(S[i][j] != S[i][j-1]), cost[i-1][j] + 1*(S[i][j] != S[i-1][j]))

if S[0][0] == S[-1][-1] == '.':
    ans = cost[-1][-1]//2
elif S[0][0] != S[-1][-1]:
    ans = cost[-1][-1]//2 + 1
else:
    ans = cost[-1][-1]//2 + 1

print(ans)

Solution (Python):
h, w = map(int, input().split())
g = [[0] * w for _ in range(h)]
for i in range(h):
    s = list(input())
    for j in range(w):
        if s[j] == '.':
            g[i][j] = 1
INF = 10**9
dp = [[INF] * w for _ in range(h)]
if g[0][0] == 0:
    dp[0][0] = 1
else:
    dp[0][0] = 0

for i in range(h):
    for j in range(w):
        for dx, dy in ((1, 0), (0, 1)):
            nx = j + dx
            ny = i + dy
            if ny >= h or nx >= w:
                continue
            add = 0
            if g[ny][nx] == 0 and g[i][j]  == 1:
                add = 1
            dp[ny][nx] = min(dp[ny][nx], dp[i][j] + add)
            
print(dp[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 collections import *
H,W=map(int,input().split())
S=[input() for i in range(H)]
INF=10**9
D=[[INF]*W for i in range(H)]
if S[0][0]=='.':
  D[0][0]=0
else:
  D[0][0]=1
Q=deque([(0,0)])
v=0
while len(Q):
  v=Q.popleft()
  if v[0]!=H-1:
    if S[v[0]][v[1]]=='.' and S[v[0]+1][v[1]]=='
      if D[v[0]][v[1]]+1<D[v[0]+1][v[1]]:
        D[v[0]+1][v[1]]=D[v[0]][v[1]]+1
        Q.append((v[0]+1,v[1]))
    else:
      if D[v[0]][v[1]]<D[v[0]+1][v[1]]:
        D[v[0]+1][v[1]]=D[v[0]][v[1]]
        Q.append((v[0]+1,v[1]))
  if v[1]!=W-1:
    if S[v[0]][v[1]]=='.' and S[v[0]][v[1]+1]=='
      if D[v[0]][v[1]]+1<D[v[0]][v[1]+1]:
        D[v[0]][v[1]+1]=D[v[0]][v[1]]+1
        Q.append((v[0],v[1]+1))
    else:
      if D[v[0]][v[1]]<D[v[0]][v[1]+1]:
        D[v[0]][v[1]+1]=D[v[0]][v[1]]
        Q.append((v[0],v[1]+1))
print(D[-1][-1])

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

dp = [[0 for x in range(w)] for y in range(h)]
if grid[0][0] == '
    dp[0][0] = 1
else:
    dp[0][0] = 0

for i in range(1, w):
    if grid[0][i] == '.':
        dp[0][i] = dp[0][i-1]
    else:
        if grid[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):
    if grid[i][0] == '.':
        dp[i][0] = dp[i-1][0]
    else:
        if grid[i-1][0] == '.':
            dp[i][0] = dp[i-1][0]+1
        else:
            dp[i][0] = dp[i-1][0]

for i in range(1, h):
    for j in range(1, w):
        if grid[i][j] == '.':
            dp[i][j] = min(dp[i-1][j], dp[i][j-1])
        else:
            if grid[i-1][j] == '
                dp[i][j] = min(dp[i-1][j], dp[i][j-1])
            elif grid[i-1][j] == '
                dp[i][j] = dp[i-1][j]
            elif grid[i][j-1] == '
                dp[i][j] = dp[i][j-1]
            else:
                dp[i][j] = min(dp[i-1][j], dp[i][j-1]) + 1

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

Solution (Python):


import sys
import numpy as np
int1 = lambda x: int(x) - 1
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
sys.setrecursionlimit(500000)



def adjacent_2(h, w, H, W):
    ret = []
    for (dh, dw) in [(0, 1), (1, 0)]:
        h_ = h + dh
        w_ = w + dw
        if (0 <= h_) & (h_ < H) & (0 <= w_) & (w_ < W):
            ret.append((h_, w_))
    return ret


H, W = map(int, readline().split())
A = [list(readline().decode().rstrip()) for _ in range(H)]
cnt = [[1000 for _ in range(W)] for _ in range(H)]

if A[0][0] == '.':
    cnt[0][0] = 0
else:
    cnt[0][0] = 1

for h in range(H):
    for w in range(W):
        acc = adjacent_2(h, w, H, W)
        for h_, w_ in acc:
            if (A[h][w] == ".") & (A[h_][w_] == "
                cnt[h_][w_] = min(cnt[h][w] + 1, cnt[h_][w_])
            else:
                cnt[h_][w_] = min(cnt[h][w], cnt[h_][w_])

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

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

dp = [[h * w] * w for _ in range(h)]
dp[0][0] = int(s[0][0] == '
for i in range(h):
    for j in range(w):
        if i + 1 < h:
            dp[i + 1][j] = min(dp[i + 1][j],
                               dp[i][j] + int(s[i + 1][j] != s[i][j]))
        if j + 1 < w:
            dp[i][j + 1] = min(dp[i][j + 1],
                               dp[i][j] + int(s[i][j + 1] != s[i][j]))
print((dp[-1][-1] + 1) // 2)

Solution (Python):
import sys

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


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

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

    for h in range(H):
        for w in range(W + 1):
            if w == 0:
                if h != 0:
                    continue
                next_h, next_w = h, w + 1
                if grid[h][w] == "." and grid[next_h][next_w] == "
                    dp[next_h][next_w] = min(dp[next_h][next_w], dp[h][w] + 1)
                elif grid[h][w] == "." and grid[next_h][next_w] == "
                    dp[next_h][next_w] = min(dp[next_h][next_w], dp[h][w] + 1)
                else:
                    dp[next_h][next_w] = min(dp[next_h][next_w], dp[h][w])
            else:
                for dh, dw in [(1, 0), (0, 1)]:
                    next_h, next_w = h + dh, w + dw
                    if next_h < 0 or next_h >= H or next_w < 0 or next_w >= W + 1:
                        continue
                    if grid[h][w] == "." and grid[next_h][next_w] == "
                        dp[next_h][next_w] = min(dp[next_h][next_w], dp[h][w] + 1)
                    elif grid[h][w] == "." and grid[next_h][next_w] == "
                        dp[next_h][next_w] = min(dp[next_h][next_w], dp[h][w] + 1)
                    else:
                        dp[next_h][next_w] = min(dp[next_h][next_w], dp[h][w])
    print(dp[-1][-1])


if __name__ == '__main__':
    resolve()

Solution (Python):
from collections import deque
h, w = map(int, input().split())
S = [list(input()) for _ in range(h)]
DP = [[10000]*w for _ in range(h)]
DP[0][0] = 0 if S[0][0]=='.' else 1

directs = [[0,1], [1,0]]
for hi in range(h):
    for wi in range(w):
        for dh,dw in directs:
            if not (0<=hi+dh<h and 0<=wi+dw<w): continue
            if S[hi][wi]=='.' and S[hi+dh][wi+dw]=='
                DP[hi+dh][wi+dw] = min(DP[hi+dh][wi+dw], DP[hi][wi]+1)
            else:
                DP[hi+dh][wi+dw] = min(DP[hi+dh][wi+dw], DP[hi][wi])
print(DP[-1][-1])

Solution (Python):
import sys
input = sys.stdin.readline
INF = 99999
from collections import deque

def linput(ty=int, cvt=list):
	return cvt(map(ty,input().split()))

def pad(mxy, wall="
	w = len(mxy[0])
	gp = wall*(w+2)
	re = [gp,]
	re_app = re.append
	for vx in mxy:
		re_app(wall+vx+wall)
	re_app(gp)
	return re

vD = [(0,1),(1,0)]
vQ = deque([])
vQ_app, vQ_popl = vQ.append, vQ.popleft

def main():
	H,W = linput()
	mM = [input().rstrip() for _ in [0,]*H]
	mM = pad(mM, "$")
	
	res = 0
	cnt = 0
	
	for sr in range(1,1+1):
		for sc in range(1,1+1):
			if mM[sr][sc]=="
				res += 1
			mV = [[INF,]*(W+2) for _ in [INF,]*(H+2)]
			mV[sr][sc] = res
			vQ_app((sr,sc))
			while vQ:
				r,c = vQ_popl()
				now_cost = mV[r][c]
				now_s = mM[r][c]
				for dr,dc in vD:
					nr,nc = r+dr, c+dc
					if mM[nr][nc]=="$":
						continue
					next = now_s=="."!=mM[nr][nc]
					new_cost = now_cost + next
					if new_cost < mV[nr][nc]:
						vQ_app((nr,nc))
						mV[nr][nc] = new_cost
		
				cnt += 1
				
				if cnt>999999: break
	
	
	res = mV[H][W]
	print(res)

if __name__ == "__main__":
	main()

Solution (Python):
import sys, re
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, tan, asin, acos, atan, radians, degrees, log2
from itertools import accumulate, permutations, combinations, combinations_with_replacement, product, groupby
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
from bisect import bisect, bisect_left, insort, insort_left
from fractions import gcd
from heapq import heappush, heappop
from functools import reduce
def input(): return sys.stdin.readline().strip()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
def ZIP(n): return zip(*(MAP() for _ in range(n)))
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
mod = 10**9 + 7
from decimal import *

H, W = MAP()
s = [input() for _ in range(H)]

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

if s[0][0] == ".":
	dp[0][0] = 0
else:
	dp[0][0] = 1


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

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

if s[H-1][W-1] == "
	dp[H-1][W-1] += 1


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

Solution (Python):
h,w = map(int, input().split())
grid = [list(input()) for _ in range(h)]
dpgrid = [[0]*w for _ in range(h)]
for i in range(h):
    for j in range(w):
        d = 1 if grid[i][j] == "
        if (i == 0) & (j == 0):
            dpgrid[i][j] = d
        elif (i == 0):
            a = 1 if (grid[i][j-1] == ".") & (d == 1) else 0
            dpgrid[i][j] = a + dpgrid[i][j-1]
        elif (j == 0):
            b = 1 if (grid[i-1][j] == ".") & (d == 1) else 0
            dpgrid[i][j] = b + dpgrid[i-1][j]
        else:
            a = 1 if (grid[i][j-1] == ".") & (d == 1) else 0
            b = 1 if (grid[i-1][j] == ".") & (d == 1) else 0
            dpgrid[i][j] = min(a + dpgrid[i][j-1], b + dpgrid[i-1][j])
print(dpgrid[h-1][w-1])

Solution (Python):
from math import ceil,floor,comb,factorial,gcd,pow,sqrt,log2,cos,sin,tan,acos,asin,atan,degrees,radians,pi,inf
from itertools import accumulate,permutations,combinations,product,combinations_with_replacement
from collections import deque,defaultdict,Counter
from bisect import bisect_left,bisect_right
from operator import itemgetter
from heapq import heapify,heappop,heappush
from copy import deepcopy
from time import time
import string
import sys
sys.setrecursionlimit(10 ** 7)
def input() : return sys.stdin.readline().strip()
def INT()   : return int(input())
def MAP()   : return map(int,input().split())
def LIST()  : return list(MAP())

h, w = MAP()
s = [input() for i in range(h)]
dp = [[inf]*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+1 < h:
            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+1 < w:
            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):
from math import ceil,floor,comb,factorial,gcd,pow,sqrt,log2,cos,sin,tan,acos,asin,atan,degrees,radians,pi,inf
from itertools import accumulate,permutations,combinations,product,combinations_with_replacement
from collections import deque,defaultdict,Counter
from bisect import bisect_left,bisect_right
from operator import itemgetter
from heapq import heapify,heappop,heappush
from copy import deepcopy
from time import time
import string
import sys
sys.setrecursionlimit(10 ** 7)
def input() : return sys.stdin.readline().strip()
def INT()   : return int(input())
def MAP()   : return map(int,input().split())
def LIST()  : return list(MAP())

def bfs():
    que = deque()
    que.append([0, 0])
    if s[0][0] == '
        d[0][0] = 1
    else:
        d[0][0] = 0

    while que:
        p = que.popleft()
        if p[0] == h-1 and p[1] == w-1:
            break

        for i in range(2):
            ny = p[0] + dy[i]
            nx = p[1] + dx[i]
            if 0 <= ny < h and 0 <= nx < w:
                if s[p[0]][p[1]] == '.' and  s[ny][nx] == '
                    if d[ny][nx] > d[p[0]][p[1]]+1:
                        d[ny][nx] = d[p[0]][p[1]]+1
                        que.append([ny, nx])
                else:
                    if d[ny][nx] > d[p[0]][p[1]]:
                        d[ny][nx] = d[p[0]][p[1]]
                        que.append([ny, nx])

    return d[h-1][w-1]

h, w = MAP()
s = [input() for i in range(h)]
d = [[inf]*w for i in range(h)]

dy = [1, 0]
dx = [0, 1]

print(bfs())

Solution (Python):
import sys, re
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, tan, asin, acos, atan, radians, degrees, log2, gcd
from itertools import accumulate, permutations, combinations, combinations_with_replacement, product, groupby
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
from bisect import bisect, bisect_left, insort, insort_left
from heapq import heappush, heappop
from functools import reduce
def input(): return sys.stdin.readline().strip()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
def ZIP(n): return zip(*(MAP() for _ in range(n)))
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
mod = 10 ** 9 + 7 

from decimal import *



H, W = MAP()
s = [input() for _ in range(H)]

cnt = [[-1]*W for _ in range(H)]

if s[0][0] == ".":
	cnt[0][0] = 0
else:
	cnt[0][0] = 1

dy = [0, 1]
dx = [1, 0]

q = deque([(0, 0)])
while q:
	y, x = q.popleft()
	for i in range(2):
		ny = y + dy[i]
		nx = x + dx[i]
		if ny < H and nx < W and cnt[ny][nx] == -1:
			if s[ny][nx] == s[y][x]:
				cnt[ny][nx] = cnt[y][x]
				q.appendleft((ny, nx))
			else:
				cnt[ny][nx] = cnt[y][x] + 1
				q.append((ny, nx))

if s[H-1][W-1] == "
	ans = (cnt[H-1][W-1]+1)//2
else:
	ans = (cnt[H-1][W-1])//2
print(ans)

Solution (Python):
import sys
input = sys.stdin.buffer.readline




def RD(): return sys.stdin.read()
def II(): return int(input())
def MI(): return map(int,input().split())
def MF(): return map(float,input().split())
def LI(): return list(map(int,input().split()))
def LF(): return list(map(float,input().split()))
def TI(): return tuple(map(int,input().split()))


def main():
	h,w=MI()

	S=["
	for _ in range(h):
		S.append("
	

	G=[[10**10]*(w+1) for _ in range(h+1)]

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

	for i in range(1,h+1):
		for j in range(1,w+1):
			
			if i==j==1:
				continue
			a=G[i-1][j]+(S[i-1][j]=="." and S[i][j]=="
			b=G[i][j-1]+(S[i][j-1]=="." and S[i][j]=="
			
			G[i][j]=min(a,b)

	print(G[h][w])













if __name__ == "__main__":
	main()

Solution (Python):
import sys
input = sys.stdin.buffer.readline




def RD(): return sys.stdin.read()
def II(): return int(input())
def MI(): return map(int,input().split())
def MF(): return map(float,input().split())
def LI(): return list(map(int,input().split()))
def LF(): return list(map(float,input().split()))
def TI(): return tuple(map(int,input().split()))


def main():
	h,w=MI()

	S=["
	for _ in range(h):
		S.append("
	

	G=[[10**10]*(w+1) for _ in range(h+1)]

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

	for i in range(1,h+1):
		for j in range(1,w+1):
			
			if i==j==1:
				continue
			a=G[i-1][j]+(S[i-1][j]=="." and S[i][j]=="
			b=G[i][j-1]+(S[i][j-1]=="." and S[i][j]=="
			
			G[i][j]=min(a,b)

	print(G[h][w])













if __name__ == "__main__":
	main()

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

for x0 in range(w):
    for y0 in range(h):
        for i, j in [(0, 1), (1, 0)]:
            x = x0 + i
            y = y0 + j
            if x < w and y < h:
                n = 1 if s[y0][x0] == "." and s[y][x] == "
                dp[y][x] = min(dp[y0][x0] + n, dp[y][x])

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