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())
INF = H+W+W

grid = [[v for v in input()] for _ in range(H)]

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

DX = [0, 1]
DY = [1, 0]

dp[0][0] = 0

for x in range(H):
    for y in range(W):
        for dx, dy in zip(DX, DY):
            nx = x+dx
            ny = y+dy
            if 0 <= nx < H and 0 <= ny < W:
                if grid[x][y] == "." and grid[x][y] != grid[nx][ny]:
                    dp[nx][ny] = min(dp[nx][ny], dp[x][y]+1)
                else:
                    dp[nx][ny] = min(dp[nx][ny], dp[x][y])
if grid[0][0] == "
    dp[-1][-1] += 1
print(dp[-1][-1])

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

for i in range(1, W):
    dp[0][i] = dp[0][i-1] + (int(s[0][i]=="
for h in range(1,H):
  dp[h][0] = dp[h-1][0] + (int(s[h][0]=="
  for w in range(1,W):
    dp[h][w] = min(dp[h-1][w]+(int(s[h][w]=="
    dp[h][w-1]+(int(s[h][w]=="
print(dp[-1][-1])

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

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

    ans = [[0]*W for _ in range(H)]
    if s[0][0]=='
        ans[0][0] = 1
    for i in range(1, W+H-1):
        for y in range(max(0, i-(W-1)), min(i+1, H)):
            x = i-y
            if y==0:
                if s[y][x-1]=='.' and s[y][x]=='
                    ans[y][x] = ans[y][x-1] + 1
                else:
                    ans[y][x] = ans[y][x-1]
            elif x==0:
                if s[y-1][x]=='.' and s[y][x]=='
                    ans[y][x] = ans[y-1][x] + 1
                else:
                    ans[y][x] = ans[y-1][x]
            else:
                if s[y][x]=='
                    ans[y][x] = min(ans[y-1][x]+(1 if s[y-1][x]=='.' else 0), ans[y][x-1]+(1 if s[y][x-1]=='.' else 0))
                else:
                    ans[y][x] = min(ans[y-1][x], ans[y][x-1])
    print(ans[-1][-1])

if __name__ == '__main__':
    resolve()

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

domain[0][0]= int(s[0][0]=="

for x in range(1,h):
    domain[x][0] = domain[x-1][0] + (int(s[x][0]=="
for y in range(1, w):
    domain[0][y] = domain[0][y-1] + int(s[0][y]=="
    for x in range(1,h):
        domain[x][y]= min(
            domain[x-1][y] + int(s[x][y]=="
            domain[x][y-1] + int(s[x][y]=="
        )

print(domain[-1][-1])

Solution (Python):
inp = list(map(lambda x: int(x), input().split(" ")))
H = inp[0]
W = inp[1]

field = [""]*H

for i in range(H):
    field[i] = input()

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

if (field[0][0] == "
    dp[0][0] = 1

for i in range(H):
    for j in range(W):
        check1 = 0
        check2 = 0
        if (i>0 and j>0):
            if (field[i][j]=="
                check1 = 1
            if (field[i][j]=="
                check2 = 1
            dp[i][j] = min(dp[i-1][j]+check1, dp[i][j-1]+check2)
        elif (i>0 and j==0):
            if (field[i][j]=="
                check1 = 1
            dp[i][j] = dp[i-1][j]+check1
        elif (i==0 and j>0):
            if (field[i][j]=="
                check2 = 1
            dp[i][j] = dp[i][j-1]+check2

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

Solution (Python):
h, w = map(int, input().split())
a0 = '.' * w
r0 = [200] * w
for i in range(h):
  a = input()
  r = [i and 200]
  for x, y, z, u in zip(a0, '.' + a, a, r0):
    r.append(min(u + (x + z == '.
  a0 = a
  r0 = r[1:]
print(r[-1])

Solution (Python):
h, w = map(int, input().split())
a0 = '.' * w
r0 = [200] * w
for i in range(h):
  a = input()
  r = [i * 200]
  for x, y, z, u in zip(a0, '.' + a, a, r0):
    r.append(min(u + (x + z == '.
  a0 = a
  r0 = r[1:]
print(r[-1])

Solution (Python):
def main():
    H, W = map(int, input().split())
    s = []
    for _ in range(H):
        S = input()
        s.append(S)
    dp = [[0] * W for _ in range(H)]
    dp[0][0] = 1 if s[0][0] == '
    for i in range(1, W):
        dp[0][i] = dp[0][i-1] + 1 if s[0][i] == '
    for i in range(1, H):
        dp[i][0] = dp[i-1][0] + 1 if s[i][0] == '
    for i in range(1, H):
        for j in range(1, W):
            if s[i][j] == '.':
                dp[i][j] = min(dp[i][j-1], dp[i-1][j])
            else:
                u = dp[i-1][j]
                r = dp[i][j-1]
                if s[i-1][j] == '.':
                    u += 1
                if s[i][j-1] == '.':
                    r += 1
                dp[i][j] = min(u, r)
    return dp[-1][-1]
print(main())

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

grid = [[v for v in input()] for _ in range(H)]

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

DX = [0, 1]
DY = [1, 0]

dp[0][0] = 0

for x in range(H):
    for y in range(W):
        for dx, dy in zip(DX, DY):
            nx = x+dx
            ny = y+dy
            if 0 <= nx < H and 0 <= ny < W:
                if grid[x][y] == "." and grid[x][y] != grid[nx][ny]:
                    dp[nx][ny] = min(dp[nx][ny], dp[x][y]+1)
                else:
                    dp[nx][ny] = min(dp[nx][ny], dp[x][y])
if grid[0][0] == "
    dp[-1][-1] += 1
print(dp[-1][-1])

Solution (Python):
from collections import deque

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

dp=[[1000]*(w+1) for _ in range(h+1)]

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-1>=0:
            dp[i][j]=dp[i-1][j]+(1 if s[i-1][j]=='.' and s[i][j]=='
        if j-1>=0:
            dp[i][j]=min(dp[i][j],dp[i][j-1]+(1 if s[i][j-1]=='.' and s[i][j]=='

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

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

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

for h in range(H):
    for w in range(W):
        dp[h+1][w+1] = min(dp[h][w+1] + (board[h][w]=='
 
            

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

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

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

dp[0][0] = int(s[0][0] == "

for i in range(H):
    for j in range(W):
        if j:
            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])
        if i:
            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])

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

Solution (Python):
H, W = map(int, input().split())
def change(x):   
    if x == '
        return 1
    else:
        return 0
field = list()
for i in range(H):
    field.append(list(map(change,[i for i in input()])))


vector = [[1, 0], [0, 1]]


check_list = [[0 for _ in range(W)] for _ in range(H)]
check_list[0][0] = 1


count_list = [[0 for _ in range(W)] for _ in range(H)]
count_list[0][0] = field[0][0]


zahyo_front = [[0] * W] * H
zahyo_front[0][0] = [0, 0]



zahyo_search = [[(0, 0)]]


for i in range(H+W-2):
    zahyo = zahyo_search[i]   
    zahyo_kari = list()       
    for (y, x) in zahyo:
        for (dy, dx) in vector:
            count = count_list[y][x]  
            y_k = y + dy
            x_k = x + dx
            try:               
                
                if field[y_k][x_k] == 1 and field[y][x] == 0: 
                    
                    count += 1
                    
                
                if check_list[y_k][x_k] == 0:        
                    count_list[y_k][x_k] = count
                    zahyo_front[y_k][x_k] = [y, x]
                    check_list[y_k][x_k] = 1
                    zahyo_kari.append((y_k, x_k))    
                    
                else:                                
                    if count < count_list[y_k][x_k]:  
                        count_list[y_k][x_k] = count
                        zahyo_front[y_k][x_k] = [y, x]
                        
            except:
                pass
            
    zahyo_search.append(zahyo_kari) 

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

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

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

    dp[0][0] = int(s[0][0] == '

    for r in range(H):
        for c in range(W):
            if r > 0:
                dp[r][c] = min(dp[r][c], dp[r - 1][c] + int(s[r][c] == '
            if c > 0:
                dp[r][c] = min(dp[r][c], dp[r][c - 1] + int(s[r][c] == '

    res = dp[H - 1][W - 1]
    print(res)
    return


if __name__ == '__main__':
    main()

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

Solution (Python):



import numpy as np





def getIntList(inp):
	return [int(_) for _ in inp]


from sys import stdin
import sys
sys.setrecursionlimit(10**8)

def getInputs():
	inputs=[]
	for line in stdin:
		line=line.split()
		inputs.append(line)
	return inputs



def main(inputs):
	h,w=getIntList(inputs[0])
	colors=np.empty((h,w),np.bool)
	for hi in range(h):
		for wi in range(w):
			colors[hi,wi]=inputs[1+hi][0][wi]=="."












			

	
	flipSize=np.empty((h,w), np.int32)
	
	if colors[0,0]: flipSize[0,0]=0
	else: flipSize[0,0]=1
	
	for hi in range(h):
		for wi in range(w):
			if hi==0 and wi==0: continue
			c=colors[hi,wi]
			fs=[]
			if hi>0:
				d=int(colors[hi-1,wi] and (not c))
				s=flipSize[hi-1, wi]+d
				fs.append(s)
				
			if wi>0:
				d=int(colors[hi,wi-1] and (not c))
				s=flipSize[hi, wi-1]+d
				fs.append(s)
			
			fs=min(fs)
			flipSize[hi,wi]=fs
	
	print(flipSize[h-1,w-1])
	

if __name__=="__main__":
	inputs=getInputs()

	main(inputs)

Solution (Python):
import heapq

h, w = map(int, input().split())

field = [input() for _ in range(h)]

todo = [[0, 0, 0, '.']]
seen = [[10**5] * w for _ in range(h)]
while todo:
    count, y, x, color = heapq.heappop(todo)
    if field[y][x] == color:
        pass
    else:
        if color == '.':
            count += 1
        color = field[y][x]

    if seen[y][x] <= count:
        continue
    seen[y][x] = count

    slide_right = [count, y, x+1, color]
    slide_down = [count, y+1, x, color]
    if x+1 < w:
        heapq.heappush(todo, slide_right)
    if y+1 < h:
        heapq.heappush(todo, slide_down)

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

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

h,w = map(int,readline().split())

maze = []
for i in range(h):
    maze.append(readline().rstrip().decode('utf-8'))

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

if maze[0][0] == "
    dp[0][0] = 1

for i in range(h):
    for j in range(w):
        if i == 0:
            if j == 0:
                continue
            res = 1 if maze[i][j] != maze[i][j-1] else 0

            dp[i][j] = dp[i][j-1] + res

        elif j == 0:
            res = 1 if maze[i][j] != maze[i-1][j] else 0

            dp[i][j] = dp[i-1][j] + res

        else:
            res_h = 1 if maze[i][j] != maze[i-1][j] else 0
            res_w = 1 if maze[i][j] != maze[i][j-1] else 0
            
            dp[i][j] = min(dp[i][j-1] + res_w,dp[i-1][j] + res_h)

print((dp[i][j]+1)//2)

Solution (Python):
h,w = map(int,input().split())
map1 = [list(input()) for _ in range(h)]
check_board = [[9e9]*w for _ in range(h)]
for x in range(h):
	for y in range(w):
		map1[x][y] = 1 if map1[x][y] =="
check_board[0][0] = map1[0][0]
def cal_ans(a,b,x,y):
	return ((map1[a][b]^map1[x][y])&map1[a][b])+check_board[x][y]
for x in range(h):
	for y in range(w):
		if x < h-1:
			check_board[x+1][y] = min(check_board[x+1][y],cal_ans(x+1,y,x,y))
		if y < w-1:
			check_board[x][y+1] = min(check_board[x][y+1],cal_ans(x,y+1,x,y))
print(check_board[-1][-1])

Solution (Python):
def main():
  h,t,*s=open(0)
  h,w=map(int,h.split())
  a=b=x=y=t[0]=='
  d=[(b,a)]
  d_add=d.append
  for i in range(1,w):
    f=t[i]=='
    b+=a^f
    a=f
    d_add((b,a))
  for s in s:
    f=s[0]=='
    y+=x^f
    b=y
    a=x=f
    p=[(b,a)]
    p_add=p.append
    for i in range(1,w):
      f=s[i]=='
      b+=a^f
      c,g=d[i]
      c+=f^g
      if b>c:b=c
      a=f
      p_add((b,a))
    d=p
  print(b+1>>1)
main()

Solution (Python):



h, w = map(int, input().split())
s_board = [['']*w for i in range(h)]
for i in range(h):
    s = list(input())
    for j in range(w):
        s_board[i][j] = s[j]


INF = 10**5
dp = [[INF]*w for i in range(h)]
if s_board[0][0]=='
    dp[0][0] = 1
else:
    dp[0][0] = 0


for i in range(h):
    for j in range(w):
        
        if i==0 and j==0:
            continue

        
        if j-1>=0:
            if s_board[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])

        
        if i-1>=0:
            if s_board[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])


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

Solution (Python):
def main():
  h,w=map(int,input().split())
  s=input()
  a=b=x=y=s[0]=='
  d=[(b,a)]
  d_add=d.append
  for i in range(1,w):
    f=s[i]=='
    b+=a^f
    a=f
    d_add((b,a))
  for _ in range(h-1):
    s=input()
    f=s[0]=='
    y+=x^f
    b=y
    a=x=f
    p=[(b,a)]
    p_add=p.append
    for i in range(1,w):
      f=s[i]=='
      b+=a^f
      c,g=d[i]
      c+=f^g
      if b>c:b=c
      a=f
      p_add((b,a))
    d=p
  print(b+1>>1)
main()

Solution (Python):
def main():
  import sys
  input=sys.stdin.buffer.readline
  h,w=map(int,input().split())
  s=input()
  a=b=x=y=s[0]==35
  d=[(b,a)]
  d_add=d.append
  for i in range(1,w):
    f=s[i]==35
    b+=a^f
    a=f
    d_add((b,a))
  for _ in range(h-1):
    s=input()
    f=s[0]==35
    y+=x^f
    b=y
    a=x=f
    p=[(b,a)]
    p_add=p.append
    for i in range(1,w):
      f=s[i]==35
      b+=a^f
      c,g=d[i]
      c+=f^g
      if b>c:b=c
      a=f
      p_add((b,a))
    d=p
  print(b+1>>1)
main()

Solution (Python):
def main():
  import sys
  input=sys.stdin.buffer.readline
  h,w=map(int,input().split())
  s=input()
  a=x=s[0]==35
  b=y=a and 1or 0
  d=[(b,a)]
  d_add=d.append
  for i in range(1,w):
    f=s[i]==35
    b+=a^f and 1or 0
    a=f
    d_add((b,a))
  for _ in range(h-1):
    s=input()
    f=s[0]==35
    y+=x^f and 1or 0
    b=y
    a=x=f
    p=[(b,a)]
    p_add=p.append
    for i in range(1,w):
      f=s[i]==35
      b+=a^f and 1or 0
      c,g=d[i]
      c+=f^g and 1or 0
      if b>c:b=c
      a=f
      p_add((b,a))
    d=p
  print(b+1>>1)
main()

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

dp = [[float("INF")]*w for i 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):
        a = dp[i-1][j]
        b = dp[i][j-1] 
        if l[i-1][j] == "." and l[i][j] == "
            a += 1
        if l[i][j-1] == "." and l[i][j] == "
            b += 1
        dp[i][j] = min(a,b,dp[i][j])
print(dp[-1][-1])

Solution (Python):
def main():
  import sys
  input=sys.stdin.buffer.readline
  h,w=map(int,input().split())
  s=input()
  a=b=x=y=s[0]==35
  d=[(b,a)]
  d_add=d.append
  for i in range(1,w):
    f=s[i]==35
    b+=a^f and 1or 0
    a=f
    d_add((b,a))
  for _ in range(h-1):
    s=input()
    f=s[0]==35
    y+=x^f and 1or 0
    b=y
    a=x=f
    p=[(b,a)]
    p_add=p.append
    for i in range(1,w):
      f=s[i]==35
      b+=a^f and 1or 0
      c,g=d[i]
      c+=f^g and 1or 0
      if b>c:b=c
      a=f
      p_add((b,a))
    d=p
  print(b+1>>1)
main()

Solution (Python):
def main():
  import sys
  buf=sys.stdin.buffer
  h,w=map(int,buf.readline().split())
  s=buf.readline()
  a=b=x=y=s[0]==35
  d=[(b,a)]
  d_add=d.append
  for i in range(1,w):
    f=s[i]==35
    b+=a^f
    a=f
    d_add((b,a))
  for s in buf.read().split():
    f=s[0]==35
    y+=x^f
    b=y
    a=x=f
    p=[(b,a)]
    p_add=p.append
    for i in range(1,w):
      f=s[i]==35
      b+=a^f
      c,g=d[i]
      c+=f^g
      if b>c:b=c
      a=f
      p_add((b,a))
    d=p
  print(b+1>>1)
main()

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

dp = [[-1]*w for i 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

        if i == 0:
            if l[i][j-1] == "." and l[i][j] == "
                dp[i][j] = dp[i][j-1]+1
            else:
                dp[i][j] = dp[i][j-1]
        elif j == 0:
            if l[i-1][j] == "." and l[i][j] == "
                dp[i][j] = dp[i-1][j]+1
            else:
                dp[i][j] = dp[i-1][j]
        else:
            a = dp[i-1][j]
            b = dp[i][j-1] 
            if l[i-1][j] == "." and l[i][j] == "
                a += 1
            if l[i][j-1] == "." and l[i][j] == "
                b += 1
            dp[i][j] = min(a,b)
print(dp[-1][-1])

Solution (Python):
def main():
  import sys
  buf=sys.stdin.buffer
  h,w=map(int,buf.readline().split())
  s=buf.readline()
  a=b=x=y=s[0]==35
  d,e=[b],[a]
  d_add,e_add=d.append,e.append
  for i in range(1,w):
    f=s[i]==35
    b+=a^f
    a=f
    d_add(b)
    e_add(a)
  for s in buf.read().split():
    f=s[0]==35
    y+=x^f
    b=y
    a=x=f
    p,q=[b],[a]
    p_add,q_add=p.append,q.append
    for i in range(1,w):
      f=s[i]==35
      b+=a^f
      c=d[i]+(f^e[i])
      if b>c:b=c
      a=f
      p_add(b)
      q_add(a)
    d,e=p,q
  print(b+1>>1)
main()

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

dp = [[-1]*w for i 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

        if i == 0:
            if l[i][j-1] == "." and l[i][j] == "
                dp[i][j] = dp[i][j-1]+1
            else:
                dp[i][j] = dp[i][j-1]
        elif j == 0:
            if l[i-1][j] == "." and l[i][j] == "
                dp[i][j] = dp[i-1][j]+1
            else:
                dp[i][j] = dp[i-1][j]
        else:
            a = dp[i-1][j]
            b = dp[i][j-1] 
            if l[i-1][j] == "." and l[i][j] == "
                a += 1
            if l[i][j-1] == "." and l[i][j] == "
                b += 1
            dp[i][j] = min(a,b)
print(dp[-1][-1])

Solution (Python):
def main():
  import sys
  buf=sys.stdin.buffer
  h,w=map(int,buf.readline().split())
  s=buf.readline()
  a=b=x=y=s[0]==35
  d=[b]
  e=[a]
  for i in range(1,w):
    f=s[i]==35
    b+=a^f
    a=f
    d+=b,
    e+=a,
  for s in buf.read().split():
    f=s[0]==35
    y+=x^f
    b=y
    a=x=f
    p=[b]
    q=[a]
    for i in range(1,w):
      f=s[i]==35
      b+=a^f
      c=d[i]+(f^e[i])
      if b>c:b=c
      a=f
      p+=b,
      q+=a,
    d=p
    e=q
  print(b+1>>1)
main()

Solution (Python):
def main():
  import sys
  buf=sys.stdin.buffer
  h,w=map(int,buf.readline().split())
  c,*s,_=buf.readline()
  a=b=x=y=c==35
  d=[(b,a)]
  for c in s:
    f=c==35
    b+=a^f
    a=f
    d+=(b,a),
  for c,*s in buf.read().split():
    f=c==35
    y+=x^f
    b=y
    a=x=f
    p=[(b,a)]
    for i,c in enumerate(s,1):
      f=c==35
      b+=a^f
      c,g=d[i]
      c+=f^g
      if b>c:b=c
      a=f
      p+=(b,a),
    d=p
  print(b+1>>1)
main()

Solution (Python):
def main():
  import sys
  buf=sys.stdin.buffer
  h,w=map(int,buf.readline().split())
  s=buf.readline()
  a=b=x=y=s[0]==35
  d=[(b,a)]
  for i in range(1,w):
    f=s[i]==35
    b+=a^f
    a=f
    d+=(b,a),
  for s in buf.read().split():
    f=s[0]==35
    y+=x^f
    b=y
    a=x=f
    p=[(b,a)]
    for i in range(1,w):
      f=s[i]==35
      b+=a^f
      c,g=d[i]
      c+=f^g
      if b>c:b=c
      a=f
      p+=(b,a),
    d=p
  print(b+1>>1)
main()

Solution (Python):
def main():
  import sys
  input=sys.stdin.buffer.readline
  h,w=map(int,input().split())
  s=input()
  a=b=x=y=s[0]==35
  d=[(b,a)]
  for i in range(1,w):
    f=s[i]==35
    b+=a^f
    a=f
    d+=(b,a),
  for _ in range(1,h):
    s=input()
    f=s[0]==35
    y+=x^f
    b=y
    a=x=f
    p=[(b,a)]
    for i in range(1,w):
      f=s[i]==35
      b+=a^f
      c,g=d[i]
      c+=f^g
      if b>c:b=c
      a=f
      p+=(b,a),
    d=p
  print(b+1>>1)
main()

Solution (Python):
def main():
  import sys
  input=sys.stdin.buffer.readline
  h,w=map(int,input().split())
  s=input()
  a=x=s[0]>>3
  b=y=5-a
  d=[(b,a)]
  for i in range(1,w):
    f=s[i]>>3
    b+=a^f
    a=f
    d+=(b,a),
  for _ in range(1,h):
    s=input()
    f=s[0]>>3
    y+=x^f
    b=y
    a=x=f
    p=[(b,a)]
    for i in range(1,w):
      f=s[i]>>3
      b+=a^f
      c,g=d[i]
      c+=f^g
      if b>c:b=c
      a=f
      p+=(b,a),
    d=p
  print(b+1>>1)
main()

Solution (Python):
import sys
h, w = list(map(int, sys.stdin.readline().split()))
graph = [list(sys.stdin.readline().rstrip()) for _ in range(h)]

dp = [[10**5 for _ in range(w)] for _ in range(h)]
dp[0][0] = 0 if graph[0][0] == '.' else 1

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

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

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

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

Solution (Python):
H, W = map(int, input().split())
maze = [list(input()) for i in range(H)]
dp = [[float('inf')]*W for i in range(H)]
dp[0][0] = 0

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

if maze[0][0] == "
    print(dp[-1][-1] + 1)
else:
    print(dp[-1][-1])

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

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

    for w in range(1,W):
        if field[0][w-1] == '.' and field[0][w] == '
            dp[0][w] = dp[0][w-1] + 1
        else:
            dp[0][w] = dp[0][w-1]
    
    for w in range(1,W):
        for h in range(1,H):
            fromUpward = dp[h-1][w]
            if field[h-1][w] == '.' and field[h][w] == '
                fromUpward += 1

            fromLeft = dp[h][w-1]
            if field[h][w-1] == '.' and field[h][w] == '
                fromLeft += 1
            
            dp[h][w] = min(fromUpward, fromLeft)
    
    ans = dp[H-1][W-1]
    if field[0][0] == '
        ans += 1

    print(ans)

if __name__ == '__main__':
    solve()

Solution (Python):
def main():
    h, w = map(int, input().split())
    grid = [input() for _ in [0]*h]
    memo = [[0]*w for _ in [0]*h]
    for k in range(h+w):
        for i in range(max(0, k-w+1), min(h, k+1)):
            j = k-i
            if i == j == 0:
                continue
            if i == 0:
                memo[i][j] = memo[i][j-1]+(grid[i][j] != grid[i][j-1])
            elif j == 0:
                memo[i][j] = memo[i-1][j]+(grid[i][j] != grid[i-1][j])
            else:
                memo[i][j] = min(memo[i][j-1]+(grid[i][j] != grid[i][j-1]),
                                 memo[i-1][j]+(grid[i][j] != grid[i-1][j]))
    print((memo[h-1][w-1]+(grid[0][0] == "


main()

Solution (Python):

import itertools


def change(val):
    
    if val == '
        return 1

    
    return 0





def main():
    h, w = map(int, input().split())
    board = [[s for s in input()] for i in range(h)]

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

    for i_row, row in enumerate(dp):
        for i_col, col in enumerate(row):
            if i_row == 0 and i_col == 0:
                dp[i_row][i_col] = change(board[i_row][i_col])
                continue

            if i_row >= 1:
                if board[i_row][i_col] == '
                    dp[i_row][i_col] = min(dp[i_row - 1][i_col] + 1, dp[i_row][i_col])
                else:
                    dp[i_row][i_col] = min(dp[i_row - 1][i_col], dp[i_row][i_col])

            if i_col >= 1:
                if board[i_row][i_col] == '
                    dp[i_row][i_col] = min(dp[i_row][i_col - 1] + 1, dp[i_row][i_col])
                else:
                    dp[i_row][i_col] = min(dp[i_row][i_col - 1], dp[i_row][i_col])

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


if __name__ == '__main__':
    main()

Solution (Python):
def main():
  import sys
  input=sys.stdin.buffer.readline
  h,w=map(int,input().split())
  t,*s,_=input()
  if t==46:c,f=0,False
  else:c,f=1,True
  p=[(c,f)]
  for t in s:
    g=t==35
    if g!=f:
      c+=1
      f=not f
    p+=(c,f),
  d=p
  for _ in range(h-1):
    t,*s,_=input()
    c,f=d[0]
    g=t==35
    if g!=f:
      c+=1
      f=not f
    p=[(c,f)]
    for i,t in enumerate(s,1):
      e,h=d[i]
      g=t==35
      if h!=g:
        e+=1
        h=not h
      if f!=g:
        c+=1
        f=not f
      if e<c:
        c,f=e,h
      p+=(c,f),
    d=p
  print(d[-1][0]+1>>1)
main()

Solution (Python):
import sys
input = sys.stdin.readline
H,W=map(int,input().split())
S=[list(input()) for i in range(H)]
dp=[0]*W
if S[0][0]=='
  dp[0]=1
for j in range(1,W):
  if S[0][j]!=S[0][j-1] and S[0][j-1]=='.':
    dp[j]=dp[j-1]+1
  else:
    dp[j]=dp[j-1]
for i in range(1,H):
  if S[i][0]!=S[i-1][0] and S[i-1][0]=='.':
    dp[0]=dp[0]+1
  for j in range(1,W):
    hidari=1 if S[i][j]!=S[i][j-1] and S[i][j-1]=='.' else 0
    ue=1 if S[i][j]!=S[i-1][j] and S[i-1][j]=='.' else 0
    dp[j]=min(dp[j-1]+hidari,dp[j]+ue)
print(dp[-1])

Solution (Python):
import sys
sys.setrecursionlimit(10**6)
h,w=map(int,input().split())
s=[list(input())for i in range(h)]
t=[[""for i in range(w)] for j in range(h)]
t[0][0]=(1 if s[0][0]=="
def f(x,y):
    if t[x][y]!="":
        return t[x][y]
    else:
        t[x][y]=min((f(x-1,y)+(s[x][y]=="
        return t[x][y]
print(f(h-1,w-1))

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

G = [['0'] * (W + 2)]
for _ in range(H):
    tmp = ['0'] + list(input()) + ['0']
    G.append(tmp)
G.append(['0'] * (W + 2))

move = [[1, 0], [0, 1]]

INF = 10 ** 6
ans = [[INF] * (W + 2) for _ in range(H + 2)]
if G[1][1] == '.':
    ans[1][1] = 0
else:
    ans[1][1] = 1


stack = [[1, 1]]
while stack:
    tmp = stack.pop()
    x, y = tmp[0], tmp[1]
    for dx, dy in move:
        nx = x + dx
        ny = y + dy
        if G[nx][ny] == '0':
            continue
        elif G[nx][ny] == '.':
            if ans[nx][ny] > ans[x][y]: 
                ans[nx][ny] = ans[x][y]
                stack.append([nx, ny])
        else:
            if G[x][y] == '.': 
                if ans[nx][ny] > ans[x][y] + 1:
                    ans[nx][ny] = ans[x][y] + 1
                    stack.append([nx, ny])
            else:
                if ans[nx][ny] > ans[x][y]: 
                    ans[nx][ny] = ans[x][y]
                    stack.append([nx, ny])
                    
print (ans[H][W])

Solution (Python):
h,w = map(int,input().split())
map1 = []
map1.append([("n") for _ in range(w+1)])
for _ in range(h):
	map1.extend([list("n"+input())])

check_board = [[0]*(w+1) for _ in range(h+1)]

def cal_ans(a,b,x,y):
	return ((map1[a][b]^map1[x][y])&map1[x][y])+check_board[a][b]

for x in range(h+1):
	for y in range(w+1):
		if map1[x][y] == "
			map1[x][y] = 1
		else:
			if map1[x][y] == "n":
				check_board[x][y] = 3000
			map1[x][y] = 0
for x in range(1,h+1):
	for y in range(1,w+1):
		if x == 1 and y == 1:
			if map1[x][y] == 1:
				check_board[x][y] = 1
			continue
		check_board[x][y] = min(cal_ans(x-1,y,x,y),cal_ans(x,y-1,x,y))
print(check_board[h][w])

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

field =[["."] * (W+1)]
for _ in range(H):
    tmp = ["."]
    tmp.extend(list(input()))
    field.append(tmp)

dp = [[10**9] * (W+1) for _ in range(H+1)]
dp[1][0] = 0
dp[0][1] = 0
for h in range(1,H+1):
    for w in range(1,W+1):
        if field[h][w] == ".":
            dp[h][w] = min(dp[h-1][w], dp[h][w-1])
        else:
            u = dp[h-1][w] if field[h-1][w] == "
            l = dp[h][w-1] if field[h][w-1] == "
            dp[h][w] = min(u,l)

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

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])