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())
g = []
for _ in range(H):
    g.append(list(input()))

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

dp[0][0] = 1 if g[0][0] == '
d = ([0,1], [1,0])
for ix in range(H):
    for jx in range(W):
        for dx,dy in d:
            ni = ix + dx
            nj = jx + dy
            if ni >= H or nj >= W:
                continue
            add = 0
            if g[ix][jx] == '.' and g[ni][nj] == '
                add += 1
            dp[ni][nj] = min(dp[ni][nj], dp[ix][jx] + add)


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

Solution (Python):
import sys
from copy import copy
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline

in_n = lambda: int(readline())
in_nn = lambda: map(int, readline().split())
in_nl = lambda: list(map(int, readline().split()))
in_na = lambda: map(int, read().split())
in_s = lambda: readline().rstrip().decode('utf-8')

INF = 10**9 + 7


def main():
    H, W = in_nn()
    s = [list(in_s()) for _ in range(H)]

    dp = [INF] * W
    if s[0][0] == '
        dp[0] = 1
    else:
        dp[0] = 0

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

    for y in range(1, H):
        next_dp = [INF] * W
        for x in range(W):
            if s[y - 1][x] == '.' and s[y][x] == '
                next_dp[x] = min(next_dp[x], dp[x] + 1)
            else:
                next_dp[x] = min(next_dp[x], dp[x])
        for x in range(1, W):
            if s[y][x - 1] == '.' and s[y][x] == '
                next_dp[x] = min(next_dp[x], next_dp[x - 1] + 1)
            else:
                next_dp[x] = min(next_dp[x], next_dp[x - 1])

        dp = next_dp

    print(dp[-1])


if __name__ == '__main__':
    main()

Solution (Python):
H, W = map(int, input().split())
L = [input() for _ in range(H)]
 
inf = 10**9
dp = [[inf] * W for _ in range(H)]
 

if (L[0][0] == '.'):
    dp[0][0] = 0
else:
    dp[0][0] = 1
 
for i in range(H):
    for j in range(W):
 
        
        if (i == 0 and j == 0):
            continue
        
        a = dp[i][j - 1]
        
        b = dp[i - 1][j]
 
        
        if (L[i][j - 1] == "." and L[i][j] == "
            a += 1
        if (L[i - 1][j] == '.' and L[i][j] == '
            b += 1
 
        
        dp[i][j] = min(a, b)
 
print(dp[-1][-1])

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

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


if (L[0][0] == '.'):
    dp[0][0] = 0
else:
    dp[0][0] = 1

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

        
        if (i == 0 and j == 0):
            continue
        
        a = dp[i][j - 1]
        
        b = dp[i - 1][j]

        
        if (L[i][j - 1] == "." and L[i][j] == "
            a += 1
        if (L[i - 1][j] == '.' and L[i][j] == '
            b += 1

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

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

Solution (Python):

import sys
sys.setrecursionlimit(10**7)

readline = sys.stdin.buffer.readline
def readstr():return readline().rstrip().decode()
def readstrs():return list(readline().decode().split())
def readint():return int(readline())
def readints():return list(map(int,readline().split()))
def printrows(x):print('\n'.join(map(str,x)))
def printline(x):print(' '.join(map(str,x)))

from math import ceil

h,w = readints()

s = [readstr() for i in range(h)]

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

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

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

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

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

H, W = map(int, input().split())
s = [input()[:-1] for _ in range(H)]
dp = [[10**18]*W for _ in range(H)]

if s[0][0]=='.':
    dp[0][0] = 0
else:
    dp[0][0] = 1
    
for i in range(H):
    for j in range(W):
        if i>0:
            if s[i-1][j]=='.' and s[i][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 j>0:
            if s[i][j-1]=='.' and s[i][j]=='
                dp[i][j] = min(dp[i][j], dp[i][j-1]+1)
            else:
                dp[i][j] = min(dp[i][j], dp[i][j-1])

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

Solution (Python):
from collections import deque
h,w=map(int,input().split())
l=['@'*(w+2)]
for i in range(h):
    l.append('@'+input()+'@')
l.append('@'*(w+2))
s=[[-1 for i in j] for j in l]
s[1][1]=l[1][1]=='
q=deque([[1,1]])
while len(q)>0:
    x,y=q.popleft()
    for i,j in [[1,0],[0,1]]:
        if l[i+x][j+y]!='@' and s[i+x][j+y]==-1:
            if l[x][y]==l[i+x][j+y]:
                q.appendleft([i+x,j+y])
                s[i+x][j+y]=s[x][y]
            else:
                q.append([i+x,j+y])
                s[i+x][j+y]=s[x][y]+1
print(-s[h][w]//2*-1)

Solution (Python):
INF = 10**9
def solve(h, w, s):
    dp = [[INF] * w for r in range(h)]
    dp[0][0] = int(s[0][0] == "
    for r in range(h):
        for c in range(w):
            for dr, dc in [(-1, 0), (0, -1)]:
                nr, nc = r+dr, c+dc
                if (0 <= nr < h) and (0 <= nc < w):
                    dp[r][c] = min(dp[r][c], dp[nr][nc] + (s[r][c] != s[nr][nc]))
    return (dp[h-1][w-1] + 1) // 2

h, w = map(int, input().split())
s = [input() for r in range(h)]
print(solve(h, w, s))

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

inf = 10**9 + 7
dp = [[inf] * W for _ in range(H)]
if (L[0][0] == '.'):
    dp[0][0] = 0
else:
    dp[0][0] = 1

for i in range(H):
    for j in range(W):
        if (i == 0 and j == 0):
            continue
        a = dp[i][j - 1]
        b = dp[i - 1][j]
        if (L[i - 1][j] == '.' and L[i][j] == '
            b += 1
        if (L[i][j - 1] == '.' and L[i][j] == '
            a += 1
        dp[i][j] = min(dp[i][j], a, b)

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

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

nowblack=False
dp=[[float("INF")]*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):
        if 0<=h-1<H:
            if S[h][w]==".":
                dp[h][w]=min(dp[h][w], dp[h-1][w])
            else:
                if S[h-1][w]=="
                    dp[h][w]=min(dp[h][w], dp[h-1][w])
                else:
                    dp[h][w]=min(dp[h][w], dp[h-1][w]+1)


        if 0<=w-1<W:
            if S[h][w]==".":
                dp[h][w]=min(dp[h][w], dp[h][w-1])
            else:
                if S[h][w-1]=="
                    dp[h][w]=min(dp[h][w], dp[h][w-1])
                else:
                    dp[h][w]=min(dp[h][w], dp[h][w-1]+1)

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):
H,W = map(int,input().split())
S = [list(input()) for _ in range(H)]
INF=10001
dp = [[INF]*W for _ in range(H)]
dp[0][0] = 0 if S[0][0] == "." else 1
 
for i in range(H):
  for j in range(W):
    m,n=INF,INF
    if i != 0:
      m = dp[i-1][j] + (S[i-1][j] == "." and S[i][j] == "
    if j != 0:
      n = dp[i][j-1] + (S[i][j-1] == "." and S[i][j] == "
 
    dp[i][j] = min(m, n, dp[i][j])
  
print(dp[H-1][W-1])

Solution (Python):

from queue import Queue

def II(): return int(input())
def MII(): return map(int, input().split())
def LII(): return list(map(int, input().split()))


def main():
    H, W = MII()
    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(dp[i][j], a, b)
                 
    print(dp[H-1][W-1])


if __name__ == '__main__':
    main()

Solution (Python):



def main():
    H, W = map(int,input().split())
    sth, stw = 0, 0
    glh, glw = H-1, W-1

    INF = 10000
    Gmap = [list(input()) for _ in range(H)]
    Dist = [[INF]*W for _ in range(H)]
    direc = {(1,0), (0,1)}

    if Gmap[0][0]=='
        Dist[0][0]=1
    else:
        Dist[0][0]=0

    for h in range(H):
        for w in range(W):
            nw = Gmap[h][w]
            for d in direc:
                hs, ws = h + d[0], w + d[1]
                if 0<=hs<H and 0<=ws<W:
                    cr = Gmap[hs][ws]
                    Dist[hs][ws] = min(Dist[hs][ws], Dist[h][w] + (cr=='
    print(Dist[glh][glw])

if __name__ == '__main__':
    main()

Solution (Python):





import math
import fractions
import sys
import bisect
import heapq  
import collections
from collections import Counter
from collections import deque
import pprint

sr = lambda: input()
ir = lambda: int(sr())
lr = lambda: list(map(int, sr().split()))

"""nを素因数分解"""
"""2以上の整数n => [[素因数, 指数], ...]の2次元リスト"""


def factorization(n):
    arr = []
    temp = n
    if n == 1:
        return arr

    for i in range(2, int(-(-n ** 0.5 // 1)) + 1):
        if temp % i == 0:
            cnt = 0
            while temp % i == 0:
                cnt += 1
                temp //= i
            arr.append([i, cnt])

    if temp != 1:
        arr.append([temp, 1])

    if arr == []:
        arr.append([n, 1])

    return arr



def power(a, n, mod):
    x = 1
    while n:
        if n & 1:
            x *= a % mod
        n >>= 1
        a *= a % mod
    return x % mod



def kaijo(n, l, mod):
    if n == 0:
        return 1
    a = n
    tmp = n - 1
    while (tmp >= l):
        a = a * tmp % mod
        tmp -= 1
    return a


inf = 10 ** 18
mod = 10 ** 9 + 7

h,w = lr()
s = [input() for i in range(h)]
dis = [[0 for i in range(w+1)]for j in range(h+1)] 
for i in range(2,w+1):
    dis[0][i] = inf
for i in range(2,h+1):
    dis[i][0] = inf
for i in range(h):
    for j in range(w):
        if s[i][j] == '.':
            dis[i+1][j+1] = min(dis[i][j+1], dis[i+1][j])
        else:
            if i>0 and j>0 and s[i-1][j]=='
                dis[i+1][j+1] = min(dis[i][j+1], dis[i+1][j])
            elif i>0 and s[i-1][j]=='
                dis[i+1][j+1] = min(dis[i][j+1], dis[i+1][j]+1)
            elif j>0 and s[i][j-1]=='
                dis[i+1][j+1] = min(dis[i][j+1]+1, dis[i+1][j])
            else:
                dis[i+1][j+1] = min(dis[i][j+1]+1, dis[i+1][j]+1)
print(dis[h][w])

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

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

dp=[[10**9]*(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):
        for d in range(2):
            new_i=i+dx[d]
            new_j=j+dy[d]
            if h<=new_i or w<=new_j:
                continue
            add=0
            if s[new_i][new_j]=='
                add=1
            dp[new_i][new_j]=min(dp[new_i][new_j], dp[i][j]+add)

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

Solution (Python):
H,W=map(int,input().split())
s=[]
dp=[[10**9]*W for _ in range(H)]
dp[0][0]=0
for _ in range(H):
    s.append(list(input()))
for i in range(H):
    for j in range(W):
        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])
        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])
ans=dp[H-1][W-1]
if s[0][0]=="
    ans+=1
print(ans)

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

INF = 10**9
dp = [[INF]*w for _ in range(h)]

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

for i in range(h):
    for j in range(w):
        d, r = INF, INF

        if i != 0:
            d = dp[i - 1][j] + (s[i - 1][j] == "." and s[i][j] == "
        if j != 0:
            r = dp[i][j - 1] + (s[i][j - 1] == "." and s[i][j] == "

        dp[i][j] = min(r, d, dp[i][j])

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

Solution (Python):
import sys
from collections import deque

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

def main():
    H,W = map(int,input().split())
    S = [list(input()) for _ in range(H)]
    dp = [[float('inf') for _ in range(W)] for _ in range(H)]

    def bfs(x,y):
        que = deque()
        que.append((x,y))
        if S[y][x] == '.':
            dp[y][x] = 0
        else:
            dp[y][x] = 1
        while que.__len__():
            x,y = que.popleft()
            for dx,dy in ((1,0),(0,1)):
                sx = x + dx
                sy = y + dy
                if sx == W or sy == H:
                    continue
                if S[y][x] == '.' and S[sy][sx] == '
                    tmp = 1
                else:
                    tmp = 0
                dp[sy][sx] = min(dp[y][x]+tmp,dp[sy][sx])
                if (sx,sy) not in que:
                    que.append((sx,sy))
    bfs(0,0)
    print(dp[H-1][W-1])
if __name__ == "__main__":
    main()

Solution (Python):
import sys
readline = sys.stdin.readline
sys.setrecursionlimit(10**8)
mod = 10**9+7

INF = 10**18
eps = 10**-7

H,W = map(int,readline().split())
s = [readline().rstrip() for i in range(H)]

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

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

for i in range(H):
    ii = max(0,i-1)
    for j in range(W):
        jj = max(0,j-1)
        dp[i][j] = min(dp[ii][j] + (s[i][j] != s[ii][j]), dp[i][jj] + (s[i][j] != s[i][jj]))

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

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

inf=float("inf")
ans=[[inf]*W for _ in range(H)]

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

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

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

Solution (Python):
t='.'
b=t*101
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):
_,*s=open(i:=0)
t='.'
b=t*101
q=range(101)
for s in s:
 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):
import math,itertools,fractions,heapq,collections,bisect,sys,queue,copy

sys.setrecursionlimit(10**7)
inf=10**20
mod=10**9+7
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 [int(x) for x in sys.stdin.readline().split()]

def I(): return int(sys.stdin.readline())
def F(): return float(sys.stdin.readline())
def LS(): return sys.stdin.readline().split()
def S(): return input()

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

  l=[]
  l.append('.'*(w+1))
  for _ in range(h):
    x='.'
    x+=S()
    l.append(x)

  dp=[[inf]*(w+10) for _ in range(h+10)]
  if l[1][1]=='
    dp[1][1]=1
  else:
    dp[1][1]=0

  for i in range(1,h+1):
    for j in range(1,w+1):
      if i==1 and j==1:
        continue
      if l[i][j]=='
        if 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-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])
      else:
        dp[i][j]=min(dp[i-1][j],dp[i][j-1])

  
  
  return dp[h][w]


print(main())

Solution (Python):

from collections import deque, Counter
from heapq import heappop, heappush
from bisect import bisect_right

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

dp = [[0]*(W+1) for _ in range(H+1)]
if s[0][0] == '
    dp[1][1] += 1
for i in range(H):
    for j in range(W):
        if (i,j) == (0,0):
            continue
        tmp = []
        if i > 0:
            if s[i][j] == '
                tmp.append(dp[i][j+1]+1)
            else:
                tmp.append(dp[i][j+1])
        if j > 0:
            if s[i][j] == '
                tmp.append(dp[i+1][j]+1)
            else:
                tmp.append(dp[i+1][j])

        dp[i+1][j+1] = min(tmp)
print(dp[H][W])

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

table[0][0] = int(S[0][0]=='
for i in range(1, H):
    table[i][0] = table[i-1][0] + int(S[i-1][0]=='.' and S[i][0]=='
for j in range(1, W):
    table[0][j] = table[0][j-1] + int(S[0][j-1]=='.' and S[0][j]=='
for i in range(1, H):
    for j in range(1, W):
        table[i][j] = min(table[i-1][j] + int(S[i-1][j]=='.' and S[i][j]=='
         table[i][j-1] + int(S[i][j-1]=='.' and S[i][j]=='

print(table[-1][-1])

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

m=[input() for i in range(h)]


cnt=[[1000000 for i in range(w)] for j in range(h)]

if m[0][0]=="
    cnt[0][0]=1
else:
    cnt[0][0]=0

for y in range(h):
    for x in range(w):
        if x>0:
            if m[y][x-1]=="." and m[y][x]=="
                cnt[y][x]=min(cnt[y][x],cnt[y][x-1]+1)
            else:
                cnt[y][x]=min(cnt[y][x],cnt[y][x-1])
        if y>0:
            if m[y-1][x]=="." and m[y][x]=="
                cnt[y][x]=min(cnt[y][x],cnt[y-1][x]+1)
            else:
                cnt[y][x]=min(cnt[y][x],cnt[y-1][x])


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

Solution (Python):
import copy
import heapq
H, W = map(int, input().split())
S = [['.'] * (W+1)]
for _ in range(H):
    s = list(input())
    s.insert(0,'.')
    S.append(s)

inf = float('inf')

dp = []
for _ in range(H+1):
    dp.append([inf] * (W+1))

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

for i in range(1,H+1):
    for j in range(1,W+1):
        right = dp[i][j-1]
        down = dp[i-1][j]
        if S[i][j] == '
            if S[i-1][j] == '.':
                down += 1
            if S[i][j-1] == '.':
                right += 1

        dp[i][j] = min(dp[i][j],right,down)

print(dp[H][W])

Solution (Python):
H, W = map(int, input().split())
Maze = [[1 if a == "

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

if Maze[0][0] == 1:
    DP[0][0] = 1
else:
    DP[0][0] = 0

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

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

Solution (Python):






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





dp = [[1000 for i in range(W+1)] for j in range(H+1)]
dp[0][1] = 0
dp[1][0] = 1

for h in range(H):
    for w in range(W):
        dp[h+1][w+1] = min(
            dp[h][w+1] + (s_mat[h][w] == "
            dp[h+1][w] + (s_mat[h][w] == "
        )
        
print(dp[-1][-1])

Solution (Python):

h,w = map(int,input().split())
s= [None for i in range(h)]
for i in range(h):
    s[i] = input()
    
dp = [[0]*w for i in range(h)]

dp[0][0] = int(s[0][0]=="
for i in range(1,w):
    dp[0][i]=dp[0][i-1] + (s[0][i-1]=="." and s[0][i]=="

for i in range(1,h):
    dp[i][0]=dp[i-1][0] + (s[i-1][0]=="." and s[i][0]=="

for i in range(1,h):
    for j in range(1,w):
        cand1 = dp[i-1][j] + (s[i-1][j]=="." and s[i][j]=="
        cand2 = dp[i][j-1] + (s[i][j-1]=="." and s[i][j]=="
        dp[i][j]=min(cand1,cand2)
        
print(dp[-1][-1])

Solution (Python):

h,w = map(int,input().split())
s= [None for i in range(h)]
for i in range(h):
    s[i] = input()
    
dp = [[0]*w for i in range(h)]

now=0
if s[0][0]=="
    now+=1
    dp[0][0]=now
for i in range(1,w):
    if s[0][i-1]=="." and s[0][i]=="
        now+=1
    dp[0][i]=now
        
now=0
if s[0][0]=="
    now+=1
for i in range(1,h):
    if s[i-1][0]=="." and s[i][0]=="
        now+=1
    dp[i][0]=now

for i in range(1,h):
    for j in range(1,w):
        cand1 = dp[i-1][j] + (s[i-1][j]=="." and s[i][j]=="
        cand2 = dp[i][j-1] + (s[i][j-1]=="." and s[i][j]=="
        dp[i][j]=min(cand1,cand2)
        
print(dp[-1][-1])

Solution (Python):
h,w=map(int,input().split())
m=[[1 if c=="

n=[i[:] for i in m]


for i in range(1,h):
    n[i][0]=n[i-1][0]+int(m[i-1][0]-m[i][0]==-1)
for j in range(1,w):
    n[0][j]=n[0][j-1]+int(m[0][j-1]-m[0][j]==-1)

for i in range(1,h):
    for j in range(1,w):
        n[i][j]=min(n[i-1][j]+int(m[i-1][j]-m[i][j]==-1),n[i][j-1]+int(m[i][j-1]-m[i][j]==-1))

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

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

Solution (Python):

import sys


def solve(H: int, W: int, s: "List[str]"):
    dp = [[0 for w in range(W)] for h in range(H)] 
    if s[0][0] == '
        dp[0][0] = 1

    for w in range(W-1): 
        if s[0][w+1] == '.': 
            dp[0][w+1] = dp[0][w]
        elif s[0][w] == '.' and s[0][w+1] == '
            dp[0][w+1] = dp[0][w] + 1
        elif s[0][w] == '
            dp[0][w+1] = dp[0][w]

    for h in range(H-1): 
        if s[h+1][0] == '.':
            dp[h+1][0] = dp[h][0]
        elif s[h][0] == '.' and s[h+1][0] == '
            dp[h+1][0] = dp[h][0] + 1
        elif s[h][0] == '
            dp[h+1][0] = dp[h][0]

    for h in range(1, H):
        for w in range(W-1):
            if s[h][w+1] == '.':
                dp[h][w+1] = min(dp[h][w], dp[h-1][w+1])
            elif s[h][w] == '.' and s[h][w+1] == '
                if s[h-1][w+1] == '.':
                    dp[h][w+1] = min(dp[h][w]+1, dp[h-1][w+1]+1)
                elif s[h-1][w+1] == '
                    dp[h][w+1] = min(dp[h][w]+1, dp[h-1][w+1])
            elif s[h][w] == '
                if s[h-1][w+1] == '.':
                    dp[h][w+1] = min(dp[h][w], dp[h-1][w+1]+1)
                elif s[h-1][w+1] == '
                    dp[h][w+1] = min(dp[h][w], dp[h-1][w+1])
    print(dp[H-1][W-1])
    return



def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    H = int(next(tokens))  
    W = int(next(tokens))  
    s = [next(tokens) for _ in range(H)]  
    solve(H, W, s)

if __name__ == '__main__':
    main()

Solution (Python):
import sys

readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
read = sys.stdin.buffer.read
sys.setrecursionlimit(10 ** 7)
INF = float('inf')

H, W = map(int, readline().split())
masu = []
for _ in range(H):
    masu.append(readline().rstrip().decode('utf-8'))


dp = [[INF]*W for _ in range(H)]
dp[0][0] = int(masu[0][0] == "

dd = [(1, 0), (0, 1)]


for i in range(H):
    for j in range(W):
        for dx, dy in dd:
            ni = i + dy
            nj = j + dx
            
            if (ni >= H or nj >= W):
                continue
            add = 0
            if masu[ni][nj] == "
                add = 1
            dp[ni][nj] = min(dp[ni][nj], dp[i][j] + add)

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

Solution (Python):

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

dp = [[1000]*w for _ in range(h)]
dp[0][0] = 1 if grid[0][0] == "

d = [(-1, 0), (0, -1)]

for i in range(h):
    for j in range(w):
        if i == 0 and j == 0:
            pass
        else:
            tmp = 1000
            for k in d:
                bx,by = j+k[0],i+k[1]
                if 0 <= bx <w and 0 <= by < h:
                    if grid[i][j] == '
                        tmp = dp[by][bx] + 1
                    else:
                        tmp = dp[by][bx]
                dp[i][j] = min(dp[i][j],tmp)
                
print(dp[-1][-1])

Solution (Python):
from collections import deque
printn = lambda x: print(x,end='')
inn = lambda : int(input())
inl   = lambda: list(map(int, input().split()))
inm   = lambda:      map(int, input().split())
ins = lambda : input().strip()
DBG = True 
BIG = 10**7
R = 10**9 + 7

def ddprint(x):
  if DBG:
    print(x)

h,w = inm()
s = []
for i in range(h):
    s.append(ins())
d = [[BIG]*w for i in range(h)]
z = 1 if s[0][0]=='
q = deque([(0,0,z)])
while len(q)>0:
    x,y,z = q.popleft()
    
    if z>=d[x][y]:
        continue
    
    d[x][y] = z
    incx = 1 if x<h-1 and s[x+1][y]=='
    incy = 1 if y<w-1 and s[x][y+1]=='
    if x<h-1 and d[x+1][y]>z+incx:
        q.append((x+1,y,z+incx))
    if y<w-1 and d[x][y+1]>z+incy:
        q.append((x,y+1,z+incy))
print(d[h-1][w-1])

Solution (Python):
def main():
  import sys
  input=sys.stdin.buffer.readline
  h,w=map(int,input().split())
  b,q=b'.'*w,range(w)
  for i in range(h):
    s=input()
    a=[]
    a_add=a.append
    for x,y,z,c in zip(b,b'.'+s,s,q):
      if x==46>z:c+=1
      if y==46>z:i+=1
      if i>c:i=c
      a_add(i)
    b,q=s,a
  print(i)
main()

Solution (Python):
h, w = map(int, input().split())
s = [list(input()) for i in range(h)]
dp = [[float("inf")] * w for i in range(h)]
dp[0][0] = 1 if s[0][0] == "
d = [(-1, 0), (0, -1)]
for i in range(h):
    for j in range(w):
        if i == 0 and j == 0:
            pass
        else:
            m = float("inf")
            for k in d:
                x = i + k[0]
                y = j + k[1]
                if 0 <= x < h and 0 <= y < w:
                    if s[i][j] == "
                        m = dp[x][y] + 1
                    else:
                        m = dp[x][y]
                dp[i][j] = min(dp[i][j], m)
print(dp[h - 1][w - 1])

Solution (Python):

H,W = map(int,input().split())
INF = 1000000
s = [input() for _ in range(H)]
a = [[INF]*(W+1) for _ in range(H+1)]
for i in range(1,H+1):
    for j in range(1,W+1):
        if (i,j)==(1,1):
            a[i][j] = int(s[0][0]=='
        elif i==1:
            a[i][j] = a[i][j-1]+int(s[i-1][j-2]=='.' and s[i-1][j-1]=='
        elif j==1:
            a[i][j] = a[i-1][j]+int(s[i-2][j-1]=='.' and s[i-1][j-1]=='
        else:
            a[i][j] = min(
                a[i][j-1]+int(s[i-1][j-2]=='.' and s[i-1][j-1]=='
                a[i-1][j]+int(s[i-2][j-1]=='.' and s[i-1][j-1]=='
            )
print(a[H][W])

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

inf = 10**18

dp = [[inf] * W for _ in range(H)]
if grid[0][0] == "
    dp[0][0] = 1
else:
    dp[0][0] = 0

for i in range(H):
    for j in range(W):
        if i != 0: 
            
            tmp = dp[i - 1][j] + int(grid[i][j]=="
            dp[i][j] = min(dp[i][j], tmp)
        if j != 0: 
            
            tmp = dp[i][j - 1] + int(grid[i][j]=="
            dp[i][j] = min(dp[i][j], tmp)
        

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

Solution (Python):
def read_int():
    return int(input())


def read_ints():
    return map(int, input().split(' '))


r, c = read_ints()
s = []
for i in range(r):
    s.append(input())
inf = int(1e9)
dp = [[inf for j in range(c)] for i in range(r)]
dp[0][0] = 1 if s[0][0] == '
for i in range(r):
    for j in range(c):
        if i > 0:
            dp[i][j] = dp[i - 1][j]
            if s[i][j] == '
                dp[i][j] += 1
        if j > 0:
            another = dp[i][j - 1]
            if s[i][j] == '
                another += 1
            dp[i][j] = min(dp[i][j], another)
print(dp[r - 1][c - 1])

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

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