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

sys.setrecursionlimit(10**6)

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

INF=1000
mymap=list()

for i in range(H):
    mymap.append(input().rstrip())



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


def make_costmap(i,j,prev_state,c):
    
    state=mymap[i][j]
    if (prev_state == "." and state=="
        c+=1
    if costmap[i][j] == INF or costmap[i][j]>c:
        costmap[i][j]=c
    else:
        return
        
    if (i<H-1):
        make_costmap(i+1,j,state,c)
    if (j<W-1):        
        make_costmap(i,j+1,state,c)
    return

make_costmap(0,0,".",0)






print(costmap[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) )
'''

     ['.', 'S', 'S', '.'],
     ['.', '.', 'S', '.'],
     ['.', '.', '.', '.']]
'''
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):
def f(c):
    if c == "
        ret = 1
    else:
        ret = 0

    return ret


h, w = map(int, input().split())
s = [list(map(f, "
for _ in range(h):
    s.append([1] + list(map(f, input())))
INF = 100 * 100

dp = [[[INF] * 2 for _ in range(w + 1)] for _ in range(h + 1)]
dp[1][1][s[1][1]] = s[1][1]

for i, (row_u, row) in enumerate(zip(s, s[1:]), 1):
    for j, (el, eu, e) in enumerate(zip(row, row_u[1:], row[1:]), 1):
        dp[i][j][e] = min(dp[i][j][e], dp[i-1][j][eu] + (eu + e) % 2, dp[i][j-1][el] + (el + e) % 2)

ans = dp[h][w][s[h][w]]
ans = (ans + 1) // 2
print(ans)

Solution (Python):
def main():
  import sys
  b=sys.stdin.buffer
  h,w=map(int,b.readline().split())
  x=w+1
  s=[c>>3for c in b.read()]
  dp=[10000]*h*x
  a=p=s[0]
  dp[0]=b=q=5-a
  for i in range(w):
    t=s[i]
    b+=a^t
    dp[i]=b
    a=t
  for i in range(x,h*x,x):
    t=s[i]
    q+=p^t
    dp[i]=b=q
    a=p=t
    k=i-w
    for j in range(i+1,i+w):
      sj=s[j]
      b+=a^sj
      t=dp[k]+(s[k]^sj)
      k+=1
      if b>t:b=t
      dp[j]=b
      a=sj
  print(b+1>>1)
main()

Solution (Python):
def main():
  import sys
  b=sys.stdin.buffer
  h,w=map(int,b.readline().split())
  x=w+1
  s=[c>>3for c in b.read()]
  dp=[10000]*h*x
  a=p=s[0]
  dp[0]=b=q=5-a
  for i in range(w):
    t=s[i]
    b+=a^t
    dp[i]=b
    a=t
  for i in range(x,h*x,x):
    t=s[i]
    q+=p^t
    dp[i]=b=q
    a=p=t
    k=i-x
    for j in range(i+1,i+w):
      sj=s[j]
      b+=a^sj
      k+=1
      t=dp[k]+(s[k]^sj)
      if b>t:b=t
      dp[j]=b
      a=sj
  print(b+1>>1)
main()

Solution (Python):
def main():
  import sys
  b=sys.stdin.buffer
  h,w=map(int,b.readline().split())
  x=w+1
  s=[5-c//8for c in b.read()]
  dp=[10000]*h*x
  dp[0]=a=b=p=q=s[0]
  for i in range(w):
    t=s[i]
    b+=a^t
    dp[i]=b
    a=t
  for i in range(x,h*x,x):
    t=s[i]
    q+=p^t
    dp[i]=b=q
    a=p=t
    for j in range(i+1,i+w):
      sj=s[j]
      b+=a^sj
      k=j-x
      t=dp[k]+(s[k]^sj)
      if b>t:b=t
      dp[j]=b
      a=sj
  print(b+1>>1)
main()

Solution (Python):
def main():
  import sys
  b=sys.stdin.buffer
  h,w=map(int,b.readline().split())
  x=w+1
  s=[c>>3for c in b.read()]
  dp=[10000]*h*x
  a=p=s[0]
  dp[0]=b=q=5-a
  for i in range(w):
    t=s[i]
    b+=a^t
    dp[i]=b
    a=t
  for i in range(x,h*x,x):
    t=s[i]
    q+=p^t
    dp[i]=b=q
    a=p=t
    for j in range(i+1,i+w):
      sj=s[j]
      b+=a^sj
      k=j-x
      t=dp[k]+(s[k]^sj)
      if b>t:b=t
      dp[j]=b
      a=sj
  print(b+1>>1)
main()

Solution (Python):
def main():
  import sys
  b=sys.stdin.buffer
  h,w=map(int,b.readline().split())
  x=w+1
  s=[c>>3for c in b.read()]
  dp=[10000]*h*x
  a=p=s[0]
  dp[0]=b=q=5-a
  r=range(1,w)
  for i in r:
    t=s[i]
    b+=a^t
    dp[i]=b
    a=t
  for i in range(x,h*x,x):
    t=s[i]
    q+=p^t
    dp[i]=b=q
    a=p=t
    for _ in r:
      i+=1
      si=s[i]
      b+=a^si
      j=i-x
      t=dp[j]+(s[j]^si)
      if b>t:b=t
      dp[i]=b
      a=si
  print(b+1>>1)
main()

Solution (Python):
def main():
  import sys
  b=sys.stdin.buffer
  h,w=map(int,b.readline().split())
  x=w+1
  s=[c>>3for c in b.read()]
  dp=[10000]*h*x
  a=p=s[0]
  dp[0]=b=q=5-a
  r=range(1,w)
  for i in r:
    t=s[i]
    b+=a^t
    dp[i]=b
    a=t
  for i in range(x,h*x,x):
    t=s[i]
    q+=p^t
    dp[i]=b=q
    a=p=t
    for j in r:
      k=i+j
      sk=s[k]
      b+=a^sk
      l=k-x
      t=dp[l]+(s[l]^sk)
      if b>t:b=t
      dp[k]=b
      a=sk
  print(b+1>>1)
main()

Solution (Python):
def main():
  import sys
  b=sys.stdin.buffer
  h,w=map(int,b.readline().split())
  x=w+1
  s=[c>>3for c in b.read()]
  dp=[10000]*h*x
  a=p=s[0]
  dp[0]=b=q=5-a
  for i in range(1,w):
    t=s[i]
    b+=a^t
    dp[i]=b
    a=t
  for i in range(x,h*x,x):
    t=s[i]
    q+=p^t
    dp[i]=b=q
    a=p=t
    for j in range(1,w):
      k=i+j
      sk=s[k]
      b+=a^sk
      l=k-x
      t=dp[l]+(s[l]^sk)
      if b>t:b=t
      dp[k]=b
      a=sk
  print(b+1>>1)
main()

Solution (Python):
def main():
  import sys
  b=sys.stdin.buffer
  h,w=map(int,b.readline().split())
  x=w+1
  s=[c>>3for c in b.read()]
  dp=[10000]*h*x
  a=p=s[0]
  dp[0]=b=q=5-a
  for i in range(1,w):
    t=s[i]
    dp[i]=b=b+(a^t)
    a=t
  for i in range(x,h*x,x):
    t=s[i]
    dp[i]=b=q=q+(p^t)
    a=p=t
    for j in range(1,w):
      k=i+j
      sk=s[k]
      b+=a^sk
      l=k-x
      t=dp[l]+(s[l]^sk)
      if b>t:b=t
      dp[k]=b
      a=sk
  print(b+1>>1)
main()

Solution (Python):
def main():
  import sys
  b=sys.stdin.buffer
  h,w=map(int,b.readline().split())
  x=w+1
  s=[c>>3for c in b.read()]
  dp=[10000]*h*x
  a=p=s[0]
  dp[0]=b=q=5-a
  for i in range(1,w):
    t=s[i]
    dp[i]=b=b+(a^t)
    a=t
  for i in range(x,h*x,x):
    t=s[i]
    dp[i]=b=q=q+(p^t)
    a=p=t
    for j in range(1,w):
      k=i+j
      sk=s[k]
      t=b+(a^sk)
      l=k-x
      u=dp[l]+(s[l]^sk)
      if t>u:t=u
      dp[k]=b=t
      a=sk
  print(b+1>>1)
main()

Solution (Python):
def main():
  import sys
  b=sys.stdin.buffer
  h,w=map(int,b.readline().split())
  x=w+1
  s=[c>>3for c in b.read()]
  dp=[10000]*h*x
  a=p=s[0]
  dp[0]=b=q=5-a
  for i in range(1,w):
    t=s[i]
    dp[i]=b=b+(a^t)
    a=t
  for i in range(x,h*x,x):
    t=s[i]
    dp[i]=q=q+(p^t)
    p=t
    for j in range(1,w):
      k=i+j
      sk=s[k]
      l=k-1
      t=dp[l]+(s[l]^sk)
      l=k-x
      u=dp[l]+(s[l]^sk)
      if t>u:t=u
      dp[k]=t
  print(dp[-2]+1>>1)
main()

Solution (Python):
def main():
  import sys
  b=sys.stdin.buffer
  h,w=map(int,b.readline().split())
  x=w+1
  s=[c>>3for c in b.read()]
  dp=[10000]*h*x
  a=s[0]
  dp[0]=b=5-a
  for i in range(1,w):
    t=s[i]
    dp[i]=b=b+(a^t)
    a=t
  a=s[0]
  b=dp[0]
  for i in range(x,h*x,x):
    t=s[i]
    dp[i]=b=b+(a^t)
    a=t
    for j in range(1,w):
      k=i+j
      sk=s[k]
      l=k-1
      t=dp[l]+(s[l]^sk)
      l=k-x
      u=dp[l]+(s[l]^sk)
      if t>u:t=u
      dp[k]=t
  print(dp[-2]+1>>1)
main()

Solution (Python):
def main():
  import sys
  b=sys.stdin.buffer
  h,w=map(int,b.readline().split())
  x=w+1
  s=[c>>3for c in b.read()]
  dp=[10000]*h*x
  dp[0]=b=5-s[0]
  for i in range(1,w):
    dp[i]=b=b+(s[i-1]^s[i])
  for i in range(x,h*x,x):
    l=i-x
    dp[i]=dp[l]+(s[l]^s[i])
    for j in range(1,w):
      k=i+j
      sk=s[k]
      l=k-1
      t=dp[l]+(s[l]^sk)
      l=k-x
      u=dp[l]+(s[l]^sk)
      if t>u:t=u
      dp[k]=t
  print(dp[-2]+1>>1)
main()

Solution (Python):
def main():
  import sys
  b=sys.stdin.buffer
  h,w=map(int,b.readline().split())
  x=w+1
  s=[c>>3for c in b.read()]
  dp=[10000]*h*x
  dp[0]=5-s[0]
  for i in range(1,w):
    dp[i]=dp[i-1]+(s[i-1]^s[i])
  for i in range(x,h*x,x):
    l=i-x
    dp[i]=dp[l]+(s[l]^s[i])
    for j in range(1,w):
      k=i+j
      sk=s[k]
      l=k-1
      t=dp[l]+(s[l]^sk)
      l=k-x
      u=dp[l]+(s[l]^sk)
      if t>u:t=u
      dp[k]=t
  print(dp[-2]+1>>1)
main()

Solution (Python):
def main():
  import sys
  b=sys.stdin.buffer
  h,w=map(int,b.readline().split())
  x=w+1
  s=[c>>3for c in b.read()]
  dp=[10000]*h*x
  dp[0]=5-s[0]
  for i in range(1,w):
    dp[i]=dp[i-1]+(s[i-1]^s[i])
  for i in range(x,h*x,x):
    l=i-x
    dp[i]=dp[l]+(s[l]^s[i])
    for j in range(1,w):
      k=i+j
      l=k-1
      t=dp[l]+(s[l]^s[k])
      l=k-x
      u=dp[l]+(s[l]^s[k])
      if t>u:t=u
      dp[k]=t
  print(dp[-2]+1>>1)
main()

Solution (Python):
def main():
  import sys
  b=sys.stdin.buffer
  h,w=map(int,b.readline().split())
  x=w+1
  s=[c>>3for c in b.read()]
  dp=[10001]*h*x
  dp[0]=5-s[0]
  for i in range(1,w):
    dp[i]=dp[i-1]+(s[i-1]^s[i])
  for i in range(x,h*x,x):
    dp[i]=dp[i-x]+(s[i-x]^s[i])
    for j in range(1,w):
      k=i+j
      t=dp[k-1]+(s[k-1]^s[k])
      u=dp[k-x]+(s[k-x]^s[k])
      if t>u:t=u
      dp[k]=t
  print(dp[-2]+1>>1)
main()

Solution (Python):
def main():
  import sys
  input=sys.stdin.buffer.readline
  h,w=map(int,input().split())
  x=w+1
  s=[c>>3for _ in range(h)for c in input()]
  dp=[10001]*h*x
  dp[0]=5-s[0]
  for i in range(1,w):
    dp[i]=dp[i-1]+(s[i-1]^s[i])
  for i in range(x,h*x,x):
    dp[i]=dp[i-x]+(s[i-x]^s[i])
    for j in range(1,w):
      k=i+j
      t=dp[k-1]+(s[k-1]^s[k])
      u=dp[k-x]+(s[k-x]^s[k])
      if t>u:t=u
      dp[k]=t
  print(dp[-2]+1>>1)
main()

Solution (Python):
def main():
  import sys
  input=sys.stdin.buffer.readline
  h,w=map(int,input().split())
  s=[c>>3for _ in range(h)for c in input()[:w]]
  dp=[10001]*h*w
  dp[0]=5-s[0]
  for i in range(1,w):
    dp[i]=dp[i-1]+(s[i-1]^s[i])
  for i in range(w,h*w,w):
    dp[i]=dp[i-w]+(s[i-w]^s[i])
  for i in range(1,h):
    for j in range(1,w):
      k=i*w+j
      t=dp[k-1]+(s[k-1]^s[k])
      u=dp[k-w]+(s[k-w]^s[k])
      if t>u:t=u
      dp[k]=t
  print(dp[-1]+1>>1)
main()

Solution (Python):
def main():
  import sys
  input=sys.stdin.buffer.readline
  h,w=map(int,input().split())
  s=[c>>3for _ in range(h)for c in input()]
  dp=[10001]*h*(w+1)
  dp[0]=5-s[0]
  for i in range(h):
    for j in range(w):
      k=i*(w+1)+j
      dpk=dp[k]
      sk=s[k]
      l=k+1
      t=dpk+(sk^s[l])
      if dp[l]>t:dp[l]=t
      if i+1<h:
        l=k-~w
        t=dpk+(sk^s[l])
        if dp[l]>t:dp[l]=t
  print(dp[-2]+1>>1)
main()

Solution (Python):
def main():
  import sys
  input=sys.stdin.buffer.readline
  h,w=map(int,input().split())
  s=[c//8for _ in range(h)for c in input()]
  dp=[10001]*h*(w+1)
  dp[0]=5-s[0]
  for i in range(h):
    for j in range(w):
      k=i*(w+1)+j
      dpk=dp[k]
      sk=s[k]
      l=k+1
      t=dpk+(sk^s[l])
      if dp[l]>t:dp[l]=t
      if i+1<h:
        l=k-~w
        t=dpk+(sk^s[l])
        if dp[l]>t:dp[l]=t
  print(dp[-2]+1>>1)
main()

Solution (Python):
def main():
  import sys
  input=sys.stdin.buffer.readline
  h,w=map(int,input().split())
  s=[c//8for _ in range(h)for c in input()[:w]]
  dp=[10**9]*h*w
  dp[0]=5-s[0]
  for i in range(h):
    for j in range(w):
      k=i*w+j
      if j+1<w:
        t=dp[k]+(s[k]^s[k+1])
        if dp[k+1]>t:dp[k+1]=t
      if i+1<h:
        t=dp[k]+(s[k]^s[k+w])
        if dp[k+w]>t:dp[k+w]=t
  print(dp[-1]+1>>1)
main()

Solution (Python):
def main():
  import sys
  input=sys.stdin.buffer.readline
  h,w=map(int,input().split())
  s=[c<46and 1or 0for _ in range(h)for c in input()[:w]]
  dp=[10**9]*h*w
  dp[0]=s[0]
  for i in range(h*w):
    j,k=i//w,i%w
    for y,x in((j+1,k),(j,k+1)):
      if y<h and x<w:
        z=y*w+x
        t=dp[i]+(s[i]^s[z])
        if dp[z]>t:dp[z]=t
  print(dp[-1]+1>>1)
main()

Solution (Python):
from collections import *
from heapq import *
H,W=map(int,input().split())
S=[input() for i in range(H)]
if S[0][0]=="
    count=1
else:
    count=0
idlemax=10**5
visited=[[idlemax for w in range(W)] for h in range(H)]
stack=deque([[0,0,bool(S[0][0]=="
while stack:

    h,w,m,flag=stack.popleft()
    if m>visited[h][w]:
        continue
    for y,x in [[0,1],[1,0]]:
        Y=h+y;X=w+x
        if Y<H and X<W:
            if flag:
                if visited[Y][X]>m:
                    if S[Y][X]==".":
                        nflag=0
                    else:
                        nflag=1
                    visited[Y][X]=m
                    stack.append([Y,X,m,nflag])
            else:
                if S[Y][X]=="
                    nflag=1
                    M=m+1
                else:
                    nflag=0
                    M=m
                if visited[Y][X]>M:
                    visited[Y][X]=M
                    stack.append([Y,X,M,nflag])

print(visited[-1][-1])

Solution (Python):
import heapq
def A():
    H, W = map(int, input().split())
    maze = []
    for i in range(H):
        maze.append(input())
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    memo = [[float('inf') for i in range(W)] for j in range(H)]
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    if maze[0][0] == '.':
        memo[0][0] = 0
    else:
        memo[0][0] = 1
    for i in range(H):
        for j in range(W):
            for r, c in [(i+1, j), (i, j+1)]:
                if r<H and c<W:
                    if maze[i][j] == '.' and maze[r][c] == '
                        temp = 1
                    else:
                        temp = 0
                    memo[r][c] = min(memo[r][c], memo[i][j]+temp)
    print(memo[-1][-1])

A()

Solution (Python):
h,*s=open(0)
h,w=map(int,h.split())
dp=[[9e9]*w for _ in s]
dp[0][0]=s[0][0]<'.'
for i in range(h*w):
  i,j=i//w,i%w
  for y,x in((i+1,j),(i,j+1)):
    if y<h and x<w:dp[y][x]=min(dp[y][x],dp[i][j]+(s[i][j]=='.'>s[y][x]))
print(dp[-1][-1])

Solution (Python):
import queue

class VInfo(object):
    def __init__(self,x,y,d,color):
        self.color=color
        self.d=d
        self.x=x
        self.y=y
    def turnColor(self):
        if self.color==".":return "
        else:return "."

h,w=map(int,input().split())
a=[[str(i) for i in input()] for j in range(h)]
sx,sy=0,0
gx,gy=w-1,h-1
cw=0
mapA=[]
m=100000000000000
for my in range(h):
    l=[]
    for mx in range(w):
        l.append(m)
    mapA.append(l)

q=queue.Queue()
if a[0][0]==".":q.put(VInfo(0,0,0,"."))
else:q.put(VInfo(0,0,1,"
l=[]
while not q.empty():
    now=q.get()
    if now.x==gx and now.y==gy:
        if now.color=="
        else:l.append((mapA[gy][gx]+1)//2)

    if now.y+1<h and a[now.y+1][now.x]==now.color and mapA[now.y+1][now.x]>now.d:
            mapA[now.y+1][now.x]=now.d
            q.put(VInfo(now.x,now.y+1,now.d,now.color))
    if now.y+1<h and a[now.y+1][now.x]!=now.color and mapA[now.y+1][now.x]>now.d:
            mapA[now.y+1][now.x]=now.d
            q.put(VInfo(now.x,now.y+1,now.d+1,now.turnColor()))
    if now.x+1<w and a[now.y][now.x+1]==now.color and mapA[now.y][now.x+1]>now.d:
            mapA[now.y][now.x+1]=now.d
            q.put(VInfo(now.x+1,now.y,now.d,now.color))
    if now.x+1<w and a[now.y][now.x+1]!=now.color and mapA[now.y][now.x+1]>now.d:
            mapA[now.y][now.x+1]=now.d
            q.put(VInfo(now.x+1,now.y,now.d+1,now.turnColor()))
print(min(l))

Solution (Python):
h, w = map(int, input().split())
mapping = [input().strip() for i in range(h)]
dp = [[123012302103120310]*w for i in range(h)]

for i in range(h):
    for j in range(w):
        if i == 0 and j == 0:
            dp[i][j] = int('
 
        if j != 0:
            if mapping[i][j] == '
                dp[i][j] = min(dp[i][j-1] + 1, dp[i][j])
            else:
                dp[i][j] = min(dp[i][j-1], dp[i][j])
        if i != 0:
            if mapping[i][j] == '
                dp[i][j] = min(dp[i-1][j] + 1, dp[i][j])
            else:
                dp[i][j] = min(dp[i-1][j], dp[i][j])
print(dp[-1][-1])

Solution (Python):
h,w = [int(i) for i in input().split()]
s = []
for i in range(h):
  array = list(input())
  s.append(array)
d = [[float("inf")] * (w) for i in range(h)]
d[0][0]=0
if s[0][0]=='
  d[0][0]=1
for i in range(1,w):
  if s[0][i]!=s[0][i-1] and s[0][i]!=s[0][0]:
    d[0][i]=d[0][i-1]+1
  else:
    d[0][i]=d[0][i-1]
for i in range(1,h):
  for j in range(w):
    k=0
    u=0
    if j != 0 :
      if s[i][j]=="
        k=1
      if s[i][j]=="
        u=1
      d[i][j] = min(d[i-1][j]+k,d[i][j-1]+u)
    elif j == 0 :
      if s[i][0]=="
        k=1
      d[i][0] = d[i-1][0]+k

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

Solution (Python):
from decimal import *
from heapq import heappush, heappop, heapify
from collections import deque, defaultdict, Counter
import itertools
from itertools import permutations, combinations, accumulate
import sys
import bisect
import string
import math
import time


def I(): return int(input())


def S(): return input()


def MI(): return map(int, input().split())


def MS(): return map(str, input().split())


def LI(): return [int(i) for i in input().split()]


def LI_(): return [int(i)-1 for i in input().split()]


def StoI(): return [ord(i)-97 for i in input()]


def ItoS(nn): return chr(nn+97)


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


def show(*inp, end='\n'):
    if show_flg:
        print(*inp, end=end)


YNL = {False: 'No', True: 'Yes'}
YNU = {False: 'NO', True: 'YES'}
MOD = 10**9+7
inf = float('inf')
IINF = 10**10
l_alp = string.ascii_lowercase
u_alp = string.ascii_uppercase
ts = time.time()
sys.setrecursionlimit(10**6)
nums = ['1', '2', '3', '4', '5', '6', '7', '8', '9', '10']

show_flg = False


BLOCK = '
ROAD = '.'


def print_matrix(mat):
    for i in range(len(mat)):
        print(*mat[i])


def main():
    H, W = MI()
    graph = [None] * H

    for i in range(H):
        graph[i] = list(S())

    dp = [[IINF] * W for i in range(H)]
    dp[0][0] = 0 if graph[0][0] == ROAD else 1

    for i in range(H):
        for j in range(W):
            for p in [(1, 0), (0, 1)]:
                ni = i + p[0]
                nj = j + p[1]
                if ni >= 0 and ni < H and nj >= 0 and nj < W:
                    cost = 0
                    if graph[i][j] == ROAD and graph[ni][nj] == BLOCK:
                        cost = dp[i][j] + 1
                    else:
                        cost = dp[i][j]
                    dp[ni][nj] = min(cost, dp[ni][nj])

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


if __name__ == '__main__':
    main()

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,boundary=1,search=[],replacement_of_found='.',mp_def={'

    mp=[boundary]*(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+=[boundary]+[mp_def[j] for j in s]+[boundary]
    mp+=[boundary]*(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)
def show2d(g,h,w):
    for i in range(h):show(g[i*w:i*w+w])

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,_=GGI(h,w,boundary=-1)
dp=[1e6]*(h*w)
dp[w+1]=g[w+1]

for j in range(h*w-w):
    if g[j]==-1:continue
    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):
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

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

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

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

print(dp[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

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

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

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

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

Solution (Python):
import copy
n,m=map(int,input().split())
l=[]
for i in range(n):
    s=list(input())
    l.append(s)
flag=0
s=copy.deepcopy(l)

if(l[0][0]=="
    l[0][0]=1 
else:
    l[0][0]=0;
for i in range(1,n):
    if(l[i][0]=="
        if s[i-1][0]=="
            l[i][0]=l[i-1][0]
        else:
            l[i][0]=l[i-1][0]+1
            
    else:
        l[i][0]=l[i-1][0]
for i in range(1,m):
    if( l[0][i]=="
        if s[0][i-1]=="
            l[0][i]=l[0][i-1]
        else:
            l[0][i]=l[0][i-1]+1
    else:
        l[0][i]=l[0][i-1]

for i in range(1,n):
    for j in range(1,m):
        if(l[i][j]=="
            a1=l[i][j-1]
            a2=l[i-1][j]
            if s[i][j-1]==".":
                a1+=1
            if s[i-1][j]==".":
                a2+=1
            l[i][j]=min(a1,a2)
        else:
            l[i][j]=min(l[i-1][j],l[i][j-1])

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

Solution (Python):
h, w = map(int, input().split())
a = lambda x: 1 if x=="
S = [list(map(a, list(input()))) for _ in range(h)]
inf = 10*3
dp = [[inf]*w for _ in range(h)]
dp[0][0] = S[0][0]
for i in range(1, w):
    dp[0][i] = dp[0][i-1] + S[0][i]*(S[0][i]!=S[0][i-1])
for i in range(1, h):
    dp[i][0] = dp[i-1][0] + S[i][0]*(S[i][0]!=S[i-1][0])
for i in range(1, h):
    for j in range(1, w):
        dp[i][j] = min(dp[i-1][j]+S[i][j]*(S[i-1][j]!=S[i][j]), dp[i][j-1]+S[i][j]*(S[i][j]!=S[i][j-1]))
print(dp[-1][-1])

Solution (Python):
from decimal import *
from heapq import heappush, heappop, heapify
from collections import deque, defaultdict, Counter
import itertools
from itertools import permutations, combinations, accumulate
import sys
import bisect
import string
import math
import time


def I(): return int(input())


def S(): return input()


def MI(): return map(int, input().split())


def MS(): return map(str, input().split())


def LI(): return [int(i) for i in input().split()]


def LI_(): return [int(i)-1 for i in input().split()]


def StoI(): return [ord(i)-97 for i in input()]


def ItoS(nn): return chr(nn+97)


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


def show(*inp, end='\n'):
    if show_flg:
        print(*inp, end=end)


YNL = {False: 'No', True: 'Yes'}
YNU = {False: 'NO', True: 'YES'}
MOD = 10**9+7
inf = float('inf')
IINF = 10**10
l_alp = string.ascii_lowercase
u_alp = string.ascii_uppercase
ts = time.time()
sys.setrecursionlimit(10**6)
nums = ['1', '2', '3', '4', '5', '6', '7', '8', '9', '10']

show_flg = False


BLOCK = '
ROAD = '.'


def print_matrix(mat):
    for i in range(len(mat)):
        print(*mat[i])


def bfs(graph, initial, goal, H, W):
    options = [(1, 0), (0, 1)]
    q = deque([initial])
    dist = [[10**9 for i in range(W)] for i in range(H)]
    dist[initial[0]][initial[1]] = 0 if graph[initial[0]][initial[1]] == ROAD else 1

    while len(q) != 0:
        p = q.popleft()

        for d in options:
            i = p[0] + d[0]
            j = p[1] + d[1]

            if i >= 0 and i < H and j >= 0 and j < W:
                if dist[i][j] == 10**9 or dist[p[0]][p[1]] < dist[i][j]:
                    q.append((i, j))
                    if graph[p[0]][p[1]] != BLOCK and graph[i][j] == BLOCK:
                        dist[i][j] = dist[p[0]][p[1]] + 1
                    else:
                        dist[i][j] = dist[p[0]][p[1]]

    
    return dist[goal[0]][goal[1]]


def main():
    H, W = MI()
    graph = [None] * H

    for i in range(H):
        graph[i] = list(S())

    ret = bfs(graph, (0, 0), (H-1, W-1), H, W)
    print(ret)


if __name__ == '__main__':
    main()

Solution (Python):
ii = lambda : int(input())
mi = lambda : map(int,input().split())
li = lambda : list(map(int,input().split()))

h,w = mi()

a = []
for i in range(h):
    k = input()
    a.append([1 if k[j]=='

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


if a[0][0] == 0:
    dp[0][0] = 0
else:
    dp[0][0] = 1

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

            if a[i][j-1] == 1:
                l = dp[i][j-1]
            else:
                l = dp[i][j-1] +1

            dp[i][j] = min(u,l)


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

Solution (Python):
h, w = map(int,input().split())
g = [input() for i in range(h)]
 
d = [[200] * w for i in range(h)]

d[0][0] = ( g[0][0] == "
for i in range(h):
    for j in range(w):
        if i + 1 < h:
            d[i+1][j] = min(d[i+1][j], d[i][j]+(g[i+1][j] == '
        if j + 1 < w:
            d[i][j+1] = min(d[i][j+1], d[i][j]+(g[i][j+1] == '

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

Solution (Python):
import sys
from collections import deque as dq
input = sys.stdin.readline
H, W = map(int, input().split())
S = [list(input())[: -1] for _ in range(H)]
Q = dq([0])
d = [1, 0]
dp = [float("inf")] * (H * W)
dp[0] = int(S[0][0] == "
while len(Q):
  p = Q.popleft()
  for k in range(2):
    y = p // W + d[k]
    x = p % W + d[-1 - k]
    if y in range(H) and (x in range(W)):
      f = (S[p // W][p % W] == ".") and (S[y][x] == "
      if dp[y * W + x] > dp[p] + f:
        dp[y * W + x] = dp[p] + f
        if f: Q.append(y * W + x)
        else: Q.appendleft(y * W + x)
print(dp[-1])

Solution (Python):
import numpy as np

H, W = map(int, input().split(' '))
S = []
for i in range(H):
  S.append([x=='

S = np.array(S)
C = np.zeros_like(S, dtype=np.int)
for h in range(H):
  for w in range(W):
    if h == 0 and w == 0:
      C[0, 0] = S[0, 0]
      continue
    candidates = []
    if h > 0:
      if S[h, w] and not S[h-1, w]:
        candidates.append(C[h-1, w] + 1)
      else:
        candidates.append(C[h-1, w])
    if w > 0:
      if S[h, w] and not S[h, w-1]:
        candidates.append(C[h, w-1] + 1)
      else:
        candidates.append(C[h, w-1])
    C[h, w] = min(candidates)

print(C[H-1, W-1])

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

inf = 10**5

cost = [[inf]*w for _ in range(h)]
if s[-1][-1]==".":
    cost[-1][-1]=0
else:
    cost[-1][-1]=1

for i in range(h-1,-1,-1):
    for j in range(w-1,-1,-1):
        if i==h-1 and j==w-1:
            continue
        if s[i][j]=="
            if j==w-1:
                pass
            else:
                if s[i][j+1]=="
                    cost[i][j]=cost[i][j+1]
                else:
                    cost[i][j]=cost[i][j+1]+1
            if i==h-1:
                pass
            else:
                if s[i+1][j]=="
                    cost[i][j]=min(cost[i][j],cost[i+1][j])
                else:
                    cost[i][j]=min(cost[i][j],cost[i+1][j]+1)
        else:
            if j<w-1:
                cost[i][j]=cost[i][j+1]
            if i<h-1:
                cost[i][j]=min(cost[i][j],cost[i+1][j])
print(cost[0][0])