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())
S=[]
for i in range(h):
    S.append(input())
    
cnt=0
D=[[10**9]*w for _ in range(h)]
D[0][0]=0
for i in range(h):
    for j in range(w):
        for x,y in [(0,1),(1,0)]:
            if i+x>=h or j+y>=w:
                continue
            if S[i][j]!=S[i+x][j+y]:
                D[i+x][j+y]=min(D[i][j]+1,D[i+x][j+y])
            else:
                D[i+x][j+y]=min(D[i][j],D[i+x][j+y])
                
                
if S[0][0]=='
    print(1+D[h-1][w-1]//2)
else:
    print(D[h-1][w-1]//2+(S[0][0]!=S[h-1][w-1]))

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

cnt=0
D=[[10**9]*w for _ in range(h)]
D[0][0]=0
for i in range(h):
    for j in range(w):
        if j>0:
            D[i][j]=D[i][j-1]+(S[i][j]!=S[i][j-1])
        if i>0:
            D[i][j]=min(D[i][j],D[i-1][j]+(S[i][j]!=S[i-1][j]))   
                
                
if S[0][0]=='
    print(1+D[h-1][w-1]//2)
else:
    print(D[h-1][w-1]//2+(S[0][0]!=S[h-1][w-1]))

Solution (Python):

import sys
def p(*_a):
  _s=" ".join(map(str,_a))
  
  sys.stderr.write(_s+"\n")


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

M = list( list(input()) for _ in range(H) )


INF  = float("inf") 
L = [[[INF,-1] for _c in range(W)] for _r in range(H)]


if M[0][0]=='.':
	L[0][0]=[0,0]
else:
	L[0][0]=[1,1]

h=0
w=0

for h in range(1,H):
	l = [ L[h-1][0][0], 0]
	if M[h][0]=='
		l[0] += (0 if L[h-1][0][1] else 1)
		l[1] = 1
	L[h][0] = l

for w in range(1,W):
	l = [ L[0][w-1][0], 0]
	if M[0][w]=='
		l[0] += (0 if L[0][w-1][1] else 1)
		l[1] = 1
	L[0][w] = l





for h in range(1,H):
	for w in range(1,W):
		l = [ L[h][w-1][0], 0]
		t = [ L[h-1][w][0], 0]
		if M[h][w]=='
			l[0] += (0 if L[h][w-1][1] else 1)
			t[0] += (0 if L[h-1][w][1] else 1)
			l[1] = t[1] = 1
		
		L[h][w] = (l if l[0]<t[0] else t)





print(L[H-1][W-1][0])

Solution (Python):


import numpy as np



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


def main():
    dp = np.zeros((H, W), dtype=int)
    if S[0][0] == "
        dp[0][0] = 1
    
    INF = 10 ** 5
    for i in range(H):
        for j in range(W):
            if i == 0 and j == 0:
                continue
            if i == 0:
                a = INF
            else:
                a = dp[i-1][j]
                if S[i-1][j] == "." and S[i][j] == "
                    a += 1
            if j == 0:
                b = INF
            else:
                b = dp[i][j-1]
                if S[i][j-1] == "." and S[i][j] == "
                    b += 1
            dp[i][j] = min(a, b)
        
    print(dp[-1][-1])


if __name__ == "__main__":
    main()

Solution (Python):

INF = 10 ** 9
H, W = map(int, input().split())
s = [list(input()) for _ in range(H)]
dp = [[INF for _ in range(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 j != 0:
            cnt = 0
            if s[i][j] == '
                cnt += 1
            dp[i][j] = min(dp[i][j], dp[i][j - 1] + cnt)

        if i != 0:
            cnt = 0
            if s[i][j] == '
                cnt += 1
            dp[i][j] = min(dp[i][j], dp[i - 1][j] + cnt)

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

Solution (Python):



import sys
sys.setrecursionlimit(10000000)


dxdy=((1,0),(0,1))

def pin(type=int):
    return map(type,input().rstrip().split())
    



def sx(h,w,ans=0):
    from collections import deque as DQ
    q=DQ()
    q.append((h,w,ans,0))
    
    flag=0
    while (len(q) >0):
        temp=q.pop()
        s,t,z,flag=temp
        
        if s>=H or t>=W:continue
        
        if maze[s][t]=="
            z+=1-flag
            flag=1
        elif maze[s][t]==".":
            flag=0
        
        if z<dp[s][t]:
            dp[s][t]=z
            for d in dxdy:
                q.append((s+d[0],t+d[1],z,flag))

def resolve():
    
    global anss ,dp,H,W,maze
    global res
    res=0
    H,W=pin()
    dp=[[(H+W)]*W for _ in range(H)]
    
    maze=tuple(tuple(input())for i in range(H))
    sx(0,0)
    
    print(dp[H-1][W-1])
    

"""         


"""
"""
お前カッコ閉じるの忘れてるだろ
"""

import sys
from io import StringIO
import unittest


class TestClass(unittest.TestCase):
    def assertIO(self, input, output):
        stdout, stdin = sys.stdout, sys.stdin
        sys.stdout, sys.stdin = StringIO(), StringIO(input)
        resolve()
        sys.stdout.seek(0)
        out = sys.stdout.read()[:-1]
        sys.stdout, sys.stdin = stdout, stdin
        self.assertEqual(out, output)

    def test_入力例_1(self):
        input = """3 3
.
.

        output = """1"""
        self.assertIO(input, output)

    def test_入力例_2(self):
        input = """2 2

.
        output = """2"""
        self.assertIO(input, output)

    def test_入力例_3(self):
        input = """4 4
..



        output = """0"""
        self.assertIO(input, output)

    def test_入力例_4(self):
        input = """5 5
.

.

.
        output = """4"""
        self.assertIO(input, output)


if __name__=="__main__":resolve()

Solution (Python):
from heapq import heappush,heappop,heapify
from collections import deque,defaultdict,Counter
from itertools import permutations,combinations,groupby
import sys,bisect,string,math,time,functools,random
def Golf():*a,=map(int,open(0))
def I():return int(input())
def S_():return input()
def IS():return input().split()
def LS():return [i for i in input().split()]
def LI():return [int(i) for i in input().split()]
def LI_():return [int(i)-1 for i in input().split()]
def NI(n):return [int(input()) for i in range(n)]
def NI_(n):return [int(input())-1 for i in range(n)]
def StoLI():return [ord(i)-97 for i in input()]
def ItoS(n):return chr(n+97)
def LtoS(ls):return ''.join([chr(i+97) for i in ls])
def GI(V,E,Directed=False,index=0):
    org_inp=[];g=[[] for i in range(n)]
    for i in range(E):
        inp=LI();org_inp.append(inp)
        if index==0:inp[0]-=1;inp[1]-=1
        if len(inp)==2:
            a,b=inp;g[a].append(b)
            if not Directed:g[b].append(a)
        elif len(inp)==3:
            a,b,c=inp;aa=(inp[0],inp[2]);bb=(inp[1],inp[2]);g[a].append(bb)
            if not Directed:g[b].append(aa)
    return g,org_inp
def GGI(h,w,search=[],replacement_of_found='.',mp_def={'

    mp=[1]*(w+2);found={}
    for i in range(h):
        s=input()
        for char in search:
            if char in s:
                found[char]=((i+1)*(w+2)+s.index(char)+1)
                mp_def[char]=mp_def[replacement_of_found]
        mp+=[1]+[mp_def[j] for j in s]+[1]
    mp+=[1]*(w+2)
    return h+2,w+2,mp,found
def TI(n):return GI(n,n-1)
def bit_combination(k,n=2):return [[tb//(n**bt)%n for bt in range(k)] for tb in range(n**k)]
def show(*inp,end='\n'):
    if show_flg:print(*inp,end=end)

YN=['YES','NO'];Yn=['Yes','No']
mo=10**9+7
inf=float('inf')
l_alp=string.ascii_lowercase

input=lambda: sys.stdin.readline().rstrip()

def ran_input():
    n=random.randint(4,16)
    rmin,rmax=1,10
    a=[random.randint(rmin,rmax) for _ in range(n)]
    return n,a

show_flg=False
show_flg=True

h,w=LI()
h,w,g,sg=GGI(h,w)
dp=[1e6]*(h*w)
dp[w+1]=g[w+1]

for j in range(h*w-w):
  for d in (1,w):
    dp[j+d]=min(dp[j]+(g[j]*2+g[j+d]==1),dp[j+d])

print(dp[-w-2])

Solution (Python):



import sys
sys.setrecursionlimit(10000000)


dxdy=((1,0),(0,1))

def pin(type=int):
    return map(type,input().rstrip().split())
    



def sx(h,w,ans=0):
    from collections import deque as DQ
    q=DQ()
    q.append((h,w,ans,0))
    
    flag=0
    while (len(q) >0):
        temp=q.popleft()
        s,t,z,flag=temp
        
        if s>=H or t>=W:continue
        
        if maze[s][t]=="
            z+=1-flag
            flag=1
        elif maze[s][t]==".":
            flag=0
        
        if z<dp[s][t]:
            dp[s][t]=z
            for d in dxdy:
                q.append((s+d[0],t+d[1],z,flag))

def resolve():
    
    global anss ,dp,H,W,maze
    global res
    res=0
    H,W=pin()
    dp=[[(H+W)]*W for _ in range(H)]
    
    maze=tuple(tuple(input())for i in range(H))
    sx(0,0)
    
    print(dp[H-1][W-1])
    

"""         


"""
"""
お前カッコ閉じるの忘れてるだろ
"""

import sys
from io import StringIO
import unittest


class TestClass(unittest.TestCase):
    def assertIO(self, input, output):
        stdout, stdin = sys.stdout, sys.stdin
        sys.stdout, sys.stdin = StringIO(), StringIO(input)
        resolve()
        sys.stdout.seek(0)
        out = sys.stdout.read()[:-1]
        sys.stdout, sys.stdin = stdout, stdin
        self.assertEqual(out, output)

    def test_入力例_1(self):
        input = """3 3
.
.

        output = """1"""
        self.assertIO(input, output)

    def test_入力例_2(self):
        input = """2 2

.
        output = """2"""
        self.assertIO(input, output)

    def test_入力例_3(self):
        input = """4 4
..



        output = """0"""
        self.assertIO(input, output)

    def test_入力例_4(self):
        input = """5 5
.

.

.
        output = """4"""
        self.assertIO(input, output)
if __name__=="__main__":resolve()

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

dp =[[float('inf')]*W for _ in range(H)]
if field[0][0] == '
    dp[0][0] = 1
else:
    dp[0][0] = 0

for i in range(H):
    for j in range(W):
        if i>0:
            dp[i][j] = min(dp[i][j], dp[i-1][j] + (field[i-1][j]=='.' and field[i][j]=='
        if j>0:
            dp[i][j] = min(dp[i][j], dp[i][j-1] + (field[i][j-1]=='.' and field[i][j]=='
print(dp[H-1][W-1])

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

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

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

for h in range(H):
    for w in range(W):
        if h == 0:
            if w == 0:
                continue
            else:
                res[h][w] = res[h][w-1] + (1 if S[h][w] == '
        else:
            if w == 0:
                res[h][w] = res[h-1][w] + (1 if S[h][w] == '
            else:
                f_t = res[h-1][w] + (1 if S[h][w] == '
                f_l = res[h][w-1] + (1if S[h][w] == '
                res[h][w] = min(f_t, f_l)

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

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

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

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

for h in range(H):
    for w in range(W):
        if h == 0:
            if w == 0:
                continue
            else:
                res[h][w] = res[h][w-1] + (1 if S[h][w] == '
        else:
            if w == 0:
                res[h][w] = res[h-1][w] + (1 if S[h][w] == '
            else:
                f_t = res[h-1][w] + (1 if S[h][w] == '
                f_l = res[h][w-1] + (1if S[h][w] == '
                res[h][w] = min(f_t, f_l)

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

Solution (Python):
from sys import stdin, setrecursionlimit
from collections import deque

setrecursionlimit(10 ** 9)

H, W = map(int, stdin.readline().split())
field = [list(stdin.readline().rstrip()) for _ in range(H)]

inf = 10 ** 9

flip_cnt = [[inf] * W for _ in range(H)]
direction = [[0, 1], [1, 0]]

q = deque([])


def bfs(h, w):
    q.append([h, w])

    while q:

        h, w = q.popleft()

        for dh, dw in direction:
            nh = h + dh
            nw = w + dw

            if nh >= H or nw >= W:
                continue

            if field[nh][nw] == field[h][w]:
                if flip_cnt[nh][nw] <= flip_cnt[h][w]:
                    continue
                else:
                    flip_cnt[nh][nw] = flip_cnt[h][w]
                    q.append([nh, nw])
            else:
                if flip_cnt[nh][nw] <= flip_cnt[h][w] + 1:
                    continue
                else:
                    flip_cnt[nh][nw] = flip_cnt[h][w] + 1
                    q.append([nh, nw])


flip_cnt[0][0] = 0
bfs(0, 0)

if field[0][0] == field[H - 1][W - 1] == "
    flip_cnt[H - 1][W - 1] += 1

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

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

A = [[None for c in range(W)] for r in range(H)]
for i in range(H):
    line = input()
    for j in range(W):
        A[i][j] = 0 if line[j] == '.' else 1

D = [[0 for c in range(W)] for r in range(H)]
for i in range(H):
    for j in range(W):
        up_left = []
        if i >= 1:
            up_left.append([A[i-1][j], D[i-1][j]])
        if j >= 1:
            up_left.append([A[i][j-1], D[i][j-1]])
        if A[i][j] == 0:
            if not up_left:
                D[i][j] = 0
                continue
            D[i][j] = min(map(lambda x: x[1], up_left))
        else:
            if not up_left:
                D[i][j] = 1
                continue
            D[i][j] = min(map(lambda x: (1-x[0])+x[1], up_left))

print(D[-1][-1])

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

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

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

for h in range(H):
    for w in range(W):
        if h == 0:
            if w == 0:
                continue
            else:
                res[h][w] = res[h][w-1] + (1 if S[h][w] == '
        else:
            if w == 0:
                res[h][w] = res[h-1][w] + (1 if S[h][w] == '
            else:
                f_t = res[h-1][w] + 1 if S[h][w] == '
                f_l = res[h][w-1] + 1 if S[h][w] == '
                res[h][w] = min(f_t, f_l)

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

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

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

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

for h in range(H):
    for w in range(W):
        if h == 0:
            if w == 0:
                continue
            else:
                res[h][w] = res[h][w-1] + (1 if S[h][w] == '
        else:
            if w == 0:
                res[h][w] = res[h-1][w] + (1 if S[h][w] == '
            else:
                f_t = res[h-1][w] + 1 if S[h][w] == '
                f_l = res[h][w-1] + 1 if S[h][w] == '
                res[h][w] = min(f_t, f_l)

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

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 y in range(1, h):
    dp[y][0] = dp[y-1][0]+1 if S[y][0]=='

for x in range(1, w):
    dp[0][x] = dp[0][x-1]+1 if S[0][x]=='

for y in range(1, h):
    for x in range(1, w):
        a = dp[y-1][x]+1 if S[y][x]=='
        b = dp[y][x-1]+1 if S[y][x]=='
        dp[y][x] = min(a,b)

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

Solution (Python):
from collections import deque
h, w =  map(int, input().split())
s = [[i for i in list(str(input()))] for i in range(h)]
INF = 10**9
dp = [[INF for _ in range(w)] for _ in range(h)]


if s[0][0] == "
    dp[0][0] = 1
else:
    dp[0][0] = 0
que = deque()
que.append((0, 0))
is_checked = [[False for _ in range(w)] for _ in range(h)]
while len(que) > 0:
    y, x = que.popleft()
    if y + 1 < h:
        if s[y][x] != s[y+1][x]:
            dp[y+1][x] = min(dp[y+1][x], dp[y][x]+1)
        else:
            dp[y+1][x] = min(dp[y+1][x], dp[y][x])
        if not is_checked[y+1][x]:
            que.append((y+1, x))
            is_checked[y+1][x] = True
    if x + 1 < w:
        if s[y][x] != s[y][x+1]:
            dp[y][x+1] = min(dp[y][x+1], dp[y][x]+1)
        else:
            dp[y][x+1] = min(dp[y][x+1], dp[y][x])
        if not is_checked[y][x+1]:
            que.append((y, x+1))
            is_checked[y][x+1] = True
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())
s=[list(input()) for i in range(h)]
inf = h*w
d=[[inf]*w for i in range(h)]
if s[0][0]=="
    d[0][0]=1
else:
    d[0][0]=0
for j in range(1,w):
    if s[0][j]=="
        d[0][j]=d[0][j-1]+1
    else:
        d[0][j]=d[0][j-1]

for i in range(1,h):
    if s[i][0]=="
        d[i][0]=d[i-1][0]+1
    else:
        d[i][0]=d[i-1][0]

for i in range(1,h):
    for j in range(1,w):
        if s[i][j]=="
            p=d[i][j-1]+1
        else:
            p=d[i][j-1]
        if s[i][j]=="
            q=d[i-1][j]+1
        else:
            q=d[i-1][j]
        d[i][j]=min(p,q)


print(d[-1][-1])

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

Solution (Python):

import sys
from collections import deque
sys.setrecursionlimit(10**9)
INF=10**18
MOD=10**9+7
def input(): return sys.stdin.readline().rstrip()

def main():
    H,W=map(int,input().split())
    s=[[] for _ in range(H+2)]
    s[0]=s[H+1]=[-1]*(W+2)
    for i in range(1,H+1):
        s[i]=[-1]+list(map(lambda s:int(s.replace('.','0').replace('
        s[i]
    
    dp=[[INF]*(W+2) for _ in range(H+2)]
    dp[1][1]=s[1][1]
    for column in range(1,H+1):
        for row in range(1,W+1):
            if s[column-1][row]!=-1:
                if s[column][row]==s[column-1][row]+1:
                    dp[column][row]=min(dp[column][row],dp[column-1][row]+1)
                else:
                    dp[column][row]=min(dp[column][row],dp[column-1][row])
            if s[column][row-1]!=-1:
                if s[column][row]==s[column][row-1]+1:
                    dp[column][row]=min(dp[column][row],dp[column][row-1]+1)
                else:
                    dp[column][row]=min(dp[column][row],dp[column][row-1])
    print(dp[H][W])
            
    

if __name__ == '__main__':
    main()

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

p.append(["."] * (W + 1))
dp = [[10 ** 9] * (W + 1) for i in range(H + 1)]

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

for i in range(H):
    for j in range(W):
        if p[i + 1][j] == ".":
            dp[i + 1][j] = min(dp[i][j], dp[i + 1][j])
        elif p[i][j] == "
            dp[i + 1][j] = min(dp[i][j], dp[i + 1][j])
        else:
            dp[i + 1][j] = min(dp[i][j] + 1, dp[i + 1][j])

        if p[i][j + 1] == ".":
            dp[i][j + 1] = min(dp[i][j], dp[i][j + 1])
        elif p[i][j] == "
            dp[i][j + 1] = min(dp[i][j], dp[i][j + 1])
        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())
field = []

for i in range(h):
    field.append(list(input()))

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

for i in range(1, w):
    if field[0][i - 1] == field[0][i]:
        dp[0][i] = dp[0][i - 1] 

    else:
        if field[0][i - 1] == "." and field[0][i] == "
            dp[0][i] = dp[0][i - 1] + 1
        else:
            dp[0][i] = dp[0][i - 1]

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

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

print(dp[h - 1][w - 1] + (1 if field[0][0] == "

Solution (Python):
from heapq import*
def main():
  h,w=map(int,input().split())
  s=[input()for _ in range(h)]
  g=h*w+1
  e=[[]for _ in range(g)]
  for i in range(h):
    for j in range(w):
      for y,x in((i+1,j),(i,j+1)):
        if y<h and x<w:
          if s[i][j]=='.'and s[y][x]!='.':
            e[i*w+j]+=(1,y*w+x),
          else:
            e[i*w+j]+=(0,y*w+x),
  e[g-1]+=(s[0][0]!='.',0),
  q=[g-1]
  d=[10**12]*g
  while q:
    c=heappop(q)
    c,v=c//g,c%g
    if c>d[v]:continue
    d[v]=c
    for x,w in e[v]:
      x+=c
      if d[w]>x:
        d[w]=x
        heappush(q,x*g+w)
  print(d[g-2])
main()

Solution (Python):
from heapq import*
def main():
  h,w=map(int,input().split())
  s=[input()for _ in range(h)]
  g=h*w+1
  e=[[]for _ in range(g)]
  for i in range(h):
    for j in range(w):
      for y,x in((i+1,j),(i,j+1)):
        if y<h and x<w:
          if s[i][j]=='.'and s[y][x]!='.':
            e[i*w+j]+=(1,y*w+x),
          else:
            e[i*w+j]+=(0,y*w+x),
  e[g-1]+=(s[0][0]!='.',0),
  q=[g-1]
  d=[10**12]*g
  while q:
    c=heappop(q)
    c,v=c//g,c%g
    if c>d[v]:continue
    d[v]=c
    for x,w in e[v]:
      x+=c
      if d[w]>x:
        d[w]=x
        heappush(q,x*g+w)
  print(d[g-2])
main()

Solution (Python):



from collections import deque
import sys
input = sys.stdin.readline



def main():
    H,W = map(int,input().split())
    s = [ input().rstrip() for _ in range(H) ]

    INF = 10 ** 9 + 7

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

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

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

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



main()

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

dp = [[float('inf')]*(W+1)] + [[float('inf')] + [0]*W for h in range(H)]
dp[0][1] = dp[1][0] = 0
for h in range(1, H+1):
  for w in range(1, W+1):
    if S[h][w] == '.':
      dp[h][w] = min(dp[h][w-1], dp[h-1][w])
    else:
      if S[h][w-1] == S[h-1][w] == '.':
        dp[h][w] = min(dp[h-1][w], dp[h][w-1]) + 1
      elif S[h][w-1] == '
        dp[h][w] = min(dp[h][w-1], dp[h-1][w]+1)
      elif S[h][w-1] == '.' and S[h-1][w] == '
        dp[h][w] = min(dp[h][w-1]+1, dp[h-1][w])
      else:
        dp[h][w] = min(dp[h][w-1], dp[h-1][w])

print(dp[H][W])

Solution (Python):

def set_val(map, x, y, value):
    key = str(x) + " " + str(y)
    if key in map:
        if value < map[key]:
            map[key] = value
    else:
        map[key] = value
    return map


size_x, size_y = map(int, input().split())
count = size_x + size_y
temp_values = []

for i in range(size_x):
    temp_values.append(input())

values = []
for value in temp_values:
    values.append(list(value))

initial = 0
yet = True
all_same = True
if values[0][0] == "
    initial = 1

check_value = {"0 0": initial}

for i in range(count):
    check_temp_value = {}
    for key in check_value.keys():
        x, y = map(int, key.split())
        value = check_value.get(key)
        
        if x + 1 <= size_x - 1:
            if values[x + 1][y] == "
                
                check_temp_value = set_val(check_temp_value, x + 1, y, value + 1)
                yet = False
                all_same = False
            else:
                check_temp_value = set_val(check_temp_value, x + 1, y, value)
        
        if y + 1 <= size_y - 1:
            if values[x][y + 1] == "
                
                check_temp_value = set_val(check_temp_value, x, y + 1, value + 1)
                yet = False
                all_same = False
            else:
                check_temp_value = set_val(check_temp_value, x, y + 1, value)
    check_value = check_temp_value
    if len(check_value) == 1:
        
        break
    yet = True


if all_same:
    print(initial)
else:
    
    result_val_add = 0
    if values[size_x - 1][size_y - 1] == "
        result_val_add = 1
    print(list(check_value.values())[0] + result_val_add)

Solution (Python):


import sys
 
stdin = sys.stdin
inf = 1 << 60
mod = 1000000007
 
ni      = lambda: int(ns())
nin     = lambda y: [ni() for _ in range(y)]
na      = lambda: list(map(int, stdin.readline().split()))
nan     = lambda y: [na() for _ in range(y)]
nf      = lambda: float(ns())
nfn     = lambda y: [nf() for _ in range(y)]
nfa     = lambda: list(map(float, stdin.readline().split()))
nfan    = lambda y: [nfa() for _ in range(y)]
ns      = lambda: stdin.readline().rstrip()
nsn     = lambda y: [ns() for _ in range(y)]
ncl     = lambda y: [list(ns()) for _ in range(y)]
nas     = lambda: stdin.readline().split()

from collections import deque

h, w = na()
m = nsn(h)

def bfs():
    q = deque()
    al = 0
    f = False
    if m[0][0] == '
        al += 1
        f = True
    q.append((0, 0, al, f))
    d = [[inf] * w for _ in range(h)]
    res = inf
    dx, dy = [0, 1], [1, 0]
    while len(q):
        p = q.popleft()
        x, y, l, flag = p
        for i in range(2):
            nx, ny = x + dx[i], y + dy[i]
            nl = l
            if nx >= 0 and nx < w and ny >= 0 and ny < h and d[ny][nx] > nl:
                if m[ny][nx] == '
                    if not flag:
                        nl += 1
                    q.append((nx, ny, nl, True))
                else:
                    q.append((nx, ny, nl, False))
                d[ny][nx] = min(d[ny][nx], nl)
    return d[h - 1][w - 1]

print(bfs())

Solution (Python):

def set_val(map, x, y, value):
    key = str(x) + " " + str(y)
    if key in map:
        if value < map[key]:
            map[key] = value
    else:
        map[key] = value
    return map


size_x, size_y = map(int, input().split())
count = size_x + size_y
temp_values = []

for i in range(size_x):
    temp_values.append(input())

values = []
for value in temp_values:
    values.append(list(value))

initial = 0
yet = True
all_black = True
if values[0][0] == "
    initial = 1

check_value = {"0 0": initial}

for i in range(count):
    check_temp_value = {}
    for key in check_value.keys():
        x, y = map(int, key.split())
        value = check_value.get(key)
        
        if x + 1 <= size_x - 1:
            if values[x + 1][y] == "
                
                check_temp_value = set_val(check_temp_value, x + 1, y, value + 1)
                yet = False
                all_black = False
            else:
                check_temp_value = set_val(check_temp_value, x + 1, y, value)
        
        if y + 1 <= size_y - 1:
            if values[x][y + 1] == "
                
                check_temp_value = set_val(check_temp_value, x, y + 1, value + 1)
                yet = False
                all_black = False
            else:
                check_temp_value = set_val(check_temp_value, x, y + 1, value)
    check_value = check_temp_value
    if len(check_value) == 1:
        
        break
    yet = True


if all_black:
    print(1)
else:
    
    result_val_add = 0
    if values[size_x - 1][size_y - 1] == "
        result_val_add = 1
    print(list(check_value.values())[0] + result_val_add)

Solution (Python):
import heapq
import sys


def get_nums_l():
    return [ int(s) for s in input().split(" ")]

def log(*args):
    print("DEBUG:", *args, file=sys.stderr)

h,w = get_nums_l()
grid = [ input() for _ in range(h) ]
dp = [ [99999999999999999999] * w for _ in range(h)]

def bfs(cost, x, y):
    
    if dp[y][x] <= cost:
        return

    dp[y][x] = cost

    if x < w-1:
        if grid[y][x] == "." and grid[y][x+1] == "
            heapq.heappush(heap, (cost+1, x+1, y))
        else:
            heapq.heappush(heap, (cost, x+1, y))

    if y < h-1:
        if grid[y][x] =="." and grid[y+1][x] == "
            heapq.heappush(heap, (cost+1, x, y+1))
        else:
            heapq.heappush(heap, (cost, x, y+1))

heap = []

if grid[0][0] == ".":
    heapq.heappush(heap, (0,0,0))
else:
    heapq.heappush(heap, (1,0,0))

while heap:
    cost, x, y = heapq.heappop(heap)
    bfs(cost, x, y)

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

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

grid_state = []



for _ in range(h):
    temp = [int(s) for s in input().replace(".", "0").replace("
    grid_state.append(temp)

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

grid_cost[0][0] = grid_state[0][0]

for i in range(1, h + w - 1):
    j = i
    if j > w - 1:
        j = w - 1
    while((j >= 0) and (i - j < h)):
        if i - j == 0:
            if grid_state[i - j][j - 1] == 1:
                grid_cost[i - j][j] = grid_cost[i - j][j - 1]
            else:
                grid_cost[i - j][j] = grid_cost[i - j][j - 1] + grid_state[i - j][j]
        elif j == 0:
            if grid_state[i - j - 1][j] == 1:
                grid_cost[i - j][j] = grid_cost[i - j - 1][j]
            else:
                grid_cost[i - j][j] = grid_cost[i - j - 1][j] + grid_state[i - j][j]
        else:
            min_cost = min([grid_cost[i - j - 1][j], grid_cost[i - j][j - 1]])

            if grid_state[i - j][j] == 0:
                grid_cost[i - j][j] = min([grid_cost[i - j - 1][j], grid_cost[i - j][j - 1]])
            elif (grid_state[i - j - 1][j] == 1) and (grid_cost[i - j - 1][j] <= grid_cost[i - j][j - 1]):
                grid_cost[i - j][j] = min_cost
            elif (grid_state[i - j - 1][j] == 0) and (grid_cost[i - j - 1][j] < grid_cost[i - j][j - 1]):
                grid_cost[i - j][j] = min_cost + 1
            elif (grid_state[i - j][j - 1] == 1) and (grid_cost[i - j - 1][j] >= grid_cost[i - j][j - 1]):
                grid_cost[i - j][j] = min_cost
            else:
                grid_cost[i - j][j] = min_cost + 1

        j -= 1

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