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

M = [[0] * W for _ in range(H)]
colors = [[''] * W for _ in range(H)]
for i in range(H):
    colors[i] = list(input())
    for j in range(W):
        if i == 0:
            if j == 0:
                M[i][j] = 0 if colors[i][j] == '.' else 1
            else:
                M[i][j] = M[i][j-1] if colors[i][j] == '.' or colors[i][j-1] == '
        else:
            if j == 0:
                M[i][j] = M[i-1][j] if colors[i][j] == '.' or colors[i-1][j] == '
            else:
                if colors[i][j] == '.':
                    M[i][j] = min([M[i-1][j], M[i][j-1]])
                else:
                    top = M[i-1][j] if colors[i-1][j] == '
                    left = M[i][j-1] if colors[i][j-1] == '
                    M[i][j] = min(top, left)

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

Solution (Python):
from collections import deque
H, W = [int(i) for i in input().split()]
Shw = [[0 if i =="." else 1 for i in input()] for _ in range(H)]

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

for j in range(H):
  for i in range(W):
    current = Shw[j][i]
    if i == 0 and j ==0:
      changes[j][i] = current
    elif i == 0:
      changes[j][i] = changes[j-1][i] + (1 if current == 1 and Shw[j-1][i] == 0 else 0)
    elif j == 0:
      changes[j][i] = changes[j][i-1] + (1 if current == 1 and Shw[j][i-1] == 0 else 0)
    else:
      upper = changes[j-1][i] + (1 if current == 1 and Shw[j-1][i] == 0 else 0)
      lower = changes[j][i-1] + (1 if current == 1 and Shw[j][i-1] == 0 else 0)
      changes[j][i] = min(upper, lower)
      
print(changes[-1][-1])

Solution (Python):
h, w = map(int, input().split())
stage = [list(map(lambda s: {'
change_dp = [[float("inf") for _ in range(w)] for _ in range(h)]
change_dp[0][0] = not stage[0][0]
attention = {(0, 0)}
while len(attention):
    next_attention = set()
    for x, y in attention:

        if x + 1 < h:
            if stage[x][y] == stage[x + 1][y]:
                parent = change_dp[x][y]
            else:
                parent = change_dp[x][y] + 1

            if parent < change_dp[x + 1][y]:
                change_dp[x + 1][y] = parent
                next_attention.add((x + 1, y))

        if y + 1 < w:
            if stage[x][y] == stage[x][y + 1]:
                parent = change_dp[x][y]
            else:
                parent = change_dp[x][y] + 1

            if parent < change_dp[x][y + 1]:
                change_dp[x][y + 1] = parent
                next_attention.add((x, y + 1))

    attention = next_attention

print((change_dp[h - 1][w - 1] + 1) // 2)

Solution (Python):
inm   = lambda:      map(int, input().split())
ins = lambda : input().strip()
BIG = 10**18

h,w = inm()
s = []
for i in range(h):
    s.append(ins())
d = [[0]*w for i in range(h)]
d[0][0] = 1 if s[0][0]=='
for i in range(h):
    for j in range(w):
        if i==0 and j==0:
            continue
        vx = BIG if i==0 else \
          d[i-1][j]+(1 if s[i-1][j]=='.' and s[i][j]=='
        vy = BIG if j==0 else \
          d[i][j-1]+(1 if s[i][j-1]=='.' and s[i][j]=='
        d[i][j] = min(vx,vy)
        
print(d[h-1][w-1])

Solution (Python):
import collections
h, w = [int(_) for _ in input().split()]
S = [list('.' * (w + 1))] + [['.'] + list(input()) for _ in range(h)]
B = [[99999] * (w + 1) for _ in range(h + 1)]
B[1][1] = 0 if S[1][1] == '.' else 1
cand = collections.deque([(1, 2), (2, 1)])
while cand:
    x, y = cand.popleft()
    if B[x][y] == 99999:
        B[x][y] = min(B[x][y - 1] + (S[x][y] == '
                      B[x - 1][y] + (S[x][y] == '
        if x < h:
            cand += [(x + 1, y)]
        if y < w:
            cand += [(x, y + 1)]
print(B[-1][-1])

Solution (Python):


def main():
    import sys
    input = sys.stdin.readline
    sys.setrecursionlimit(10000000)
    from collections import Counter, deque
    
    from itertools import combinations, permutations, accumulate
    
    from bisect import bisect_left,bisect_right
    import heapq
    from math import floor, ceil
    

    
    

    H,W = map(int, input().split())
    s = [list(input().rstrip()) for _ in range(H)]
    dp = [[0]*W for _ in range(H)]
    if s[0][0] == '
        dp[0][0] = 1
    for i in range(H):
        for j in range(W):
            if i == j == 0:
                continue
            elif i == 0:
                if s[i][j] == '
                    dp[i][j] = dp[i][j-1] + 1
                else:
                    dp[i][j] = dp[i][j-1]
            elif j == 0:
                if s[i][j] == '
                    dp[i][j] = dp[i-1][j] + 1
                else:
                    dp[i][j] = dp[i-1][j]
            else:
                p1 = dp[i-1][j]
                p2 = dp[i][j-1]
                if s[i][j] == '
                    p1 += 1
                if s[i][j] == '
                    p2 += 1
                dp[i][j] = min(p1, p2)
    print(dp[H-1][W-1])


if __name__ == '__main__':
    main()

Solution (Python):
H, W = map(int, input().split())
sL = []
for i in range(H):
    sL.append(input())
dp = [[0] * W for i in range(H)]

for h in range(H):
    for w in range(W):
        if h == 0 and w == 0:
            if sL[0][0] == ".":
                dp[0][0] = 1
            else: 
                dp[0][0] = 2
        elif h == 0:
            dp[h][w] = dp[h][w-1] + int(sL[h][w] != sL[h][w-1])
        elif w == 0:
            dp[h][w] = dp[h-1][w] + int(sL[h][w] != sL[h-1][w])
        else:
            A = dp[h-1][w] + int(sL[h][w] != sL[h-1][w])
            B = dp[h][w-1] + int(sL[h][w] != sL[h][w-1])
            dp[h][w] = min(A, B)
            
print(dp[H-1][W-1] // 2)

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


if s[0][0]=='
	cost[0][0]=1
for i in range(h):
	for j in range(w):
		if s[i][j]=='
			if i==0:
				if j!=0:
					if s[0][j-1]!='
						cost[0][j]=cost[0][j-1]+1
					else:
						cost[0][j]=cost[0][j-1]
			elif j==0:
				if s[i-1][j]!='
					cost[i][0]=cost[i-1][0]+1
				else:
					cost[i][0]=cost[i-1][0]
			else:
				cost1=cost[i-1][j]
				if s[i-1][j]!='
					cost1+=1
				cost2=cost[i][j-1]
				if s[i][j-1]!='
					cost2+=1
				cost[i][j]=min(cost1,cost2)
		else:
			if i==0:
				if j!=0:
					cost[0][j]=cost[0][j-1]
			elif j==0:
				cost[i][0]=cost[i-1][0]
			else:
				cost[i][j]=min(cost[i-1][j],cost[i][j-1])
print(cost[h-1][w-1])

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

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

for i in range(h):
    for j in range(w):
        up = None
        right = None
        if i != 0:
            up = count[i - 1][j]
            if ar[i][j] and not ar[i - 1][j]:
                up += 1

        if j != 0:
            right = count[i][j - 1]
            if ar[i][j] and not ar[i][j - 1]:
                right += 1

        if up is None:
            if right is None:
                count[i][j] = int(ar[0][0])
            else:
                count[i][j] = right
        else:
            if right is None:
                count[i][j] = up
            else:
                count[i][j] = min(right, up)

print(count[-1][-1])

Solution (Python):
h, w = map(int, input().split())
lst = [['*' for i in range(w+2)]]
for i in range(h):
    string = input()
    lsti = ['*']
    for j in range(w):
        lsti.append(string[j])
        if string[j] == 's':
            start = (i+1, j+1)
        elif string[j] == 'g':
            goal = (i+1, j+1)
    lsti.append('*')
    lst.append(lsti)
lst.append(['*' for i in range(w+2)])

lst_cnt = [[300 for i in range(w+2)] for j in range(h+2)]
if lst[1][1] == '
    lst_cnt[1][1] = -1
else:
    lst_cnt[1][1] = 0

queue_new = [(1, 1)]
while queue_new != []:
    queue = queue_new
    queue_new = []
    while queue != []:
        zahyo = queue.pop()
        i, j = zahyo[0], zahyo[1]
        if lst[i+1][j] == '
            if lst_cnt[i][j] < 0:
                if abs(lst_cnt[i][j]) < abs(lst_cnt[i+1][j]):
                    lst_cnt[i+1][j] = -abs(lst_cnt[i][j])
                    queue_new.append((i+1, j))
            else:
                if abs(lst_cnt[i][j])+1 < abs(lst_cnt[i+1][j]):
                    lst_cnt[i+1][j] = -(abs(lst_cnt[i][j])+1)
                    queue_new.append((i+1, j))
        elif lst[i+1][j] == '.':
            if abs(lst_cnt[i][j]) < abs(lst_cnt[i+1][j]):
                lst_cnt[i+1][j] = abs(lst_cnt[i][j])
                queue_new.append((i+1, j))
        
        if lst[i][j+1] == '
            if lst_cnt[i][j] < 0:
                if abs(lst_cnt[i][j]) < abs(lst_cnt[i][j+1]):
                    lst_cnt[i][j+1] = -abs(lst_cnt[i][j])
                    queue_new.append((i, j+1))
            else:
                if abs(lst_cnt[i][j])+1 < abs(lst_cnt[i][j+1]):
                    lst_cnt[i][j+1] = -(abs(lst_cnt[i][j])+1)
                    queue_new.append((i, j+1))
        elif lst[i][j+1] == '.':
            if abs(lst_cnt[i][j]) < abs(lst_cnt[i][j+1]):
                lst_cnt[i][j+1] = abs(lst_cnt[i][j])
                queue_new.append((i, j+1))
print(abs(lst_cnt[h][w]))

Solution (Python):
import sys
input=sys.stdin.readline
from math import *
n,m=map(int,input().split())
a=[]
for i in range(n):
    p=list(input().rstrip())
    a.append(p)
p=[[0 for i in range(m+1)] for j in range(n+1)]
for i in range(n):
    for j in range(m):
        if i==0 and j==0 and a[i][j]=='
            p[i][j]=1
        elif i==0:
            p[i][j]=p[i][j-1]+int(a[i][j]=='
        elif j==0:
            p[i][j]=p[i-1][j]+int(a[i][j]=='
        else:
            p[i][j]=min(p[i][j-1]+int(a[i][j]=='
print(p[n-1][m-1])

Solution (Python):
from fractions import gcd


import heapq
import math
from collections import defaultdict, Counter, deque
from bisect import *
import itertools
import fractions
import sys
sys.setrecursionlimit(10 ** 7)
MOD = 10 ** 9 + 7



def make_divisors(n):
    divisors = []
    for i in range(1, int(n**0.5)+1):
        if n % i == 0:
            divisors.append(i)
            if i != n // i:
                divisors.append(n//i)

    divisors.sort()
    return divisors


def main():

    
    
    
    
    
    
    
    
    
    
    
    
    
    
    



    h, w = map(int, input().split())
    maze = [input() for i in range(h)]
    ans = 0
    
    
    

    def Dijkstra_search(sx, sy):
        H = h
        W = w
        visited = [[False for i in range(W)] for j in range(H)]
        d = [[float("inf") for i in range(W)] for j in range(H)]  
        d[sx][sy] = 0

        queue = []
        heapq.heappush(queue, (0, (sx, sy)))
        while len(queue):
            cost, (x, y) = heapq.heappop(queue)

            if visited[x][y]:
                continue
            visited[x][y] = True

            for dx, dy in [[1, 0], [0, 1]]:
                nx = x + dx
                ny = y + dy
                if nx >= 0 and ny >= 0 and nx < H and ny < W:
                    if visited[nx][ny]:
                        continue

                    vd=cost
                    if maze[nx][ny] =="." and maze[x][y]=="
                        vd+=1
                    if d[nx][ny] > vd:
                        d[nx][ny] = vd
                        heapq.heappush(queue, (vd, (nx, ny)))

        if maze[h - 1][w - 1] == "
            d[h-1][w-1]+=1
        return d[h-1][w-1]

    ans += Dijkstra_search(0,0)
    print(ans)
 


if __name__ == '__main__':
    main()

Solution (Python):
import sys
from functools import lru_cache
sys.setrecursionlimit(10 ** 7)

read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

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


@lru_cache(maxsize=None)
def dfs(r, c, cnt, iswhite=True):
    
        

    now = '.' if iswhite == True else '

    ans = 200

    if MEIJI[r][c] != now:
        if iswhite == True:
            cnt += 1

        iswhite = not (iswhite)

    if r == H-1 and c == W - 1:
        return cnt
    if r < H-1:
        ans = min(dfs(r + 1, c, cnt, iswhite), ans)
    if c < W-1:
        ans = min(dfs(r, c + 1, cnt, iswhite), ans)

    return ans


ans = dfs(0, 0, 0, True)
print(ans)

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

from collections import deque
q=deque()
qnex=deque()

def f(r, c, num):
  math[r][c]=num
  if s[r][c]=='
    if r<H-1 and math[r+1][c]<-1:
      q.append([r+1, c, num])
      math[r+1][c]=-1
    if c<W-1 and math[r][c+1]<-1:
      q.append([r, c+1, num])
      math[r][c+1]=-1
  else:
    if r<H-1 and math[r+1][c]<-1:
      if s[r+1][c]=='.':
        q.append([r+1, c, num])
        math[r+1][c]=-1
      else:
        qnex.append([r+1, c, num+1])
    if c<W-1 and math[r][c+1]<-1:
      if s[r][c+1]=='.':
        q.append([r, c+1, num])
        math[r][c+1]=-1
      else:
        qnex.append([r, c+1, num+1])

if s[0][0]=='.':
  f(0, 0, 0)
else:
  f(0, 0, 1)
  
while math[-1][-1]<0:
  while len(q)>0:
    data=q.popleft()
    f(data[0], data[1], data[2])
    
  while len(qnex)>0:
    data=qnex.popleft()
    if math[data[0]][data[1]]<-1:
      q.append(data)
  
print(math[-1][-1])

Solution (Python):
import sys
def main():
    input = sys.stdin.readline
    H,W=map(int, input().split())
    S=[list(input()) for _ in range(H)]

    
    INF = 10**9
    dp = [[INF] * W for _ in range(H)]
    dp[0][0] = 1 if S[0][0] == '
    for i in range(H):
        for j in range(W):
            if i > 0: 
                if S[i-1][j] != '
                    dp[i][j] = min(dp[i][j], dp[i-1][j] + 1)
                else: 
                    dp[i][j] = min(dp[i][j], dp[i-1][j])
            if j > 0: 
                if S[i][j-1] != '
                    dp[i][j] = min(dp[i][j], dp[i][j-1] + 1)
                else: 
                    dp[i][j] = min(dp[i][j], dp[i][j-1])
    print(dp[H-1][W-1])

if __name__ == '__main__':
    main()

Solution (Python):

import sys

def INT(): return int(input())
def MAP(): return map(int,input().split())
def LI(): return list(map(int,input().split()))

def main():
    H,W = MAP()
    s = [input() for _ in range(H)]
    dp = [[0]*W for _ in range(H)]

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

    for i in range(H):
        for j in range(W):
            if i == 0:
                if j == 0:
                    continue

                if s[i][j] == "
                    dp[i][j] = dp[i][j-1]+1
                else:
                    dp[i][j] = dp[i][j-1] 
            else:
                if j == 0:
                    if s[i-1][j] == "." and s[i][j] == "
                        up = dp[i-1][j]+1
                    else:
                        up = dp[i-1][j]
                    dp[i][j] = up
                    continue
                else:
                    if s[i-1][j] == "." and s[i][j] == "
                        up = dp[i-1][j]+1
                    else:
                        up = dp[i-1][j]
                    
                    if s[i][j-1] == "." and s[i][j] == "
                        left = dp[i][j-1]+1
                    else:
                        left = dp[i][j-1]
                    
                    dp[i][j] = min(left,up)

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

if __name__ == '__main__':
    main()

Solution (Python):
h,w=map(int,input().split())
s=[input() for _ in range(h)]
infi=10**18
dp=[[infi]*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 s[i][j]=='.':
      if i<h-1:
        if s[i+1][j]=='.':
          dp[i+1][j]=min(dp[i+1][j],dp[i][j])
        else:
          dp[i+1][j]=min(dp[i+1][j],dp[i][j]+1)
      if j<w-1:
        if s[i][j+1]=='.':
          dp[i][j+1]=min(dp[i][j+1],dp[i][j])
        else:
          dp[i][j+1]=min(dp[i][j+1],dp[i][j]+1)
    else:
      if i<h-1:
        if s[i+1][j]=='.':
          dp[i+1][j]=min(dp[i+1][j],dp[i][j])
        else:
          dp[i+1][j]=min(dp[i+1][j],dp[i][j])
      if j<w-1:
        if s[i][j+1]=='.':
          dp[i][j+1]=min(dp[i][j+1],dp[i][j])
        else:
          dp[i][j+1]=min(dp[i][j+1],dp[i][j])
print(dp[h-1][w-1])

Solution (Python):

h, w = map(int, input().split())
mp = [list(input()) for i in range(h)]
dp = [[0]*105 for _ in range(105)]
if mp[0][0]=='
    dp[0][0]+=1
for i in range(w-1):
    plus=0
    if mp[0][i+1]!=mp[0][i] and mp[0][i+1] == '
        plus=1
    dp[0][i+1] = dp[0][i]+plus
for i in range(h-1):
    plus=0
    if mp[i+1][0]!=mp[i][0] and mp[i+1][0] == '
        plus=1
    dp[i+1][0] = dp[i][0]+plus

for i in range(1,h):
    for j in range(1,w):
        plus=0
        plus2=0
        if mp[i][j]!=mp[i-1][j] and mp[i][j]=='
            plus=1
        if mp[i][j]!=mp[i][j-1] and mp[i][j]=='
            plus2=1
        dp[i][j] = min(dp[i-1][j]+plus, dp[i][j-1]+plus2)

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

Solution (Python):
import collections
import math
import operator as op
from functools import reduce
import numpy as np
import math
import bisect
import heapq


MOD = 1000000007


def gcd(a, b):
    while b:
        a, b = b, a % b
    return a


def lcm(a, b):
    return a * b // gcd(a, b)


def get_inputs(cast_func=None):
    if cast_func is None:
        return input().split()
    else:
        return list(map(cast_func, input().split()))


def get_input(cast_func=None):
    if cast_func is None:
        return input()
    else:
        return cast_func(input())


def is_prime(n):
    if n == 1:
        return False
    for i in range(2, int(n**0.5)+1):
        if n % i == 0:
            return False
    return True


def main():
    H, W = get_inputs(int)
    
    s = np.zeros((H, W), dtype=np.int)
    req_n_ops = np.empty((H, W), dtype=np.int)
    for i in range(H):
        row = get_input(str)
        for j, r in enumerate(row):
            if r == ".":
                s[i, j] = 1

    if s[0, 0] == 0:
        req_n_ops[0, 0] = 1
    else:
        req_n_ops[0, 0] = 0

    for l in range(1, W+H-1):
        for i in range(H):
            j = l - i
            if not(i >= 0 and i < H and j >= 0 and j < W):
                continue
            
            if i >= 1:
                if s[i, j] == 0 and s[i-1, j] == 1:
                    x1 = req_n_ops[i-1, j] + 1
                else:
                    x1 = req_n_ops[i-1, j]
            else:
                x1 = 100000

            if j >= 1:
                if s[i, j] == 0 and s[i, j-1] == 1:
                    x2 = req_n_ops[i, j-1] + 1
                else:
                    x2 = req_n_ops[i, j-1]
            else:
                x2 = 100000

            req_n_ops[i, j] = min(x1, x2)


    
    print(int(req_n_ops[-1, -1]))


if __name__ == '__main__':
    main()

Solution (Python):
h,w=map(int,input().split())
l=[list(input()) for i in range(h)]
ans=[[0 for i in range(w)] for j in range(h)]
if l[0][0]=='
  ans[0][0]=1
for i in range(h):
  for j in range(w):
    if i!=0 or j!=0:
      if i!=0 and j!=0:
        if l[i][j]=='
          x=ans[i-1][j]+1
        else:
          x=ans[i-1][j]
        if l[i][j]=='
          y=ans[i][j-1]+1
        else:
          y=ans[i][j-1]
        ans[i][j]=min(x,y)
      elif i==0 and j!=0:
        if l[i][j]=='
          y=ans[i][j-1]+1
        else:
          y=ans[i][j-1]
        ans[i][j]=y
      else:
        if l[i][j]=='
          x=ans[i-1][j]+1
        else:
          x=ans[i-1][j]
        ans[i][j]=x
print(ans[h-1][w-1])

Solution (Python):


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


S0 = '.' + '
X0 = [MAX]*W
X0[0] = 0

for _ in range(H):
    S = input()
    X = [None]*W

    for i in range(W):
        sc1 = MAX
        sc2 = MAX

        if i > 0:
            sc1 = X[i-1] + (1 if S[i-1] == '.' and S[i] == '

        sc2 = X0[i] + (1 if S0[i] == '.' and S[i] == '

        X[i] = min(sc1, sc2)

    X0 = X
    S0 = S

print(X0[-1])

Solution (Python):


import sys
import math
from bisect import bisect_right as br
from bisect import bisect_left as bl
sys.setrecursionlimit(2147483647)
from heapq import heappush, heappop,heappushpop
from collections import defaultdict
from itertools import accumulate
from collections import Counter
from collections import deque
from operator import itemgetter
from itertools import permutations
mod = 10**9 + 7
inf = float('inf')
def I(): return int(sys.stdin.readline())
def LI(): return list(map(int,sys.stdin.readline().split()))

H,W = LI()
s = [input() for _ in range(H)]
dx,dy = [1,0],[0,1]
dp = [[inf]*W for _ in range(H)]


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

h = []
heappush(h, (dp[0][0],0,0))
while h:
    d,y,x = heappop(h)
    for i in range(2):
        nx,ny = x + dx[i], y +dy[i]
        if 0 <= nx < W and 0 <= ny < H:
            if s[ny][nx] == '
                dp[ny][nx] = d
                heappush(h,(dp[ny][nx],ny,nx))
            elif s[ny][nx] == '
                dp[ny][nx] = d + 1
                heappush(h, (dp[ny][nx],ny,nx))
            elif s[ny][nx] == '.' and dp[ny][nx] > d:
                dp[ny][nx] = d
                heappush(h,(dp[ny][nx],ny,nx))
print(dp[-1][-1])

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

op = [[0 for i in range(W)] for j in range(H)]
op[0][0] = int(map[0][0] == '
for i in range(1, W):
    op[0][i] = op[0][i-1] + int(map[0][i] == '
for i in range(1, H):
    op[i][0] = op[i-1][0] + int(map[i][0] == '
for i in range(1, H):
    for j in range(1, W):
        op[i][j] = min(op[i-1][j] + int(map[i][j] == '
                       op[i][j-1] + int(map[i][j] == '
print(op[H-1][W-1])

Solution (Python):

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

def main():
    mod=10**9+7
    H,W=MI()
    s=[[] for _ in range(H+2)]
    s[0]="
    for i in range(H):
        s[i+1]="
    s[-1]="
            
            
    dx=[0,1]
    dy=[1,0]
    
    inf=10**7
    
    dp=[[inf]*(W+2) for _ in range(H+2)]
    
    if s[1][1]==".":
        dp[1][1]=0
    else:
        dp[1][1]=1
        
    for i in range(1,H+1):
        for j in range(1,W+1):
            for k in range(2):
                ii=i+dx[k]
                jj=j+dy[k]
                if s[ii][jj]==s[i][j]:
                    a=0
                else:
                    a=1
                dp[ii][jj]=min(dp[ii][jj],dp[i][j]+a)
    
    print((dp[H][W]+1)//2)
    

main()

Solution (Python):
from collections import deque
t,*g=open(0)
h,w=map(int,t.split())
vis=[[1e9]*w for _ in range(h)]
vis[0][0]=int(g[0][0]=="
q=deque([(0,0,vis[0][0])])
while q:
	cy,cx,c=q.popleft()
	for ny,nx in ((cy+1,cx),(cy,cx+1)):
		cc=c
		if not (0<=ny<h and 0<=nx<w):
			continue
		if g[cy][cx]=="." and g[ny][nx]=="
			cc+=1
		if cc<vis[ny][nx]:
			vis[ny][nx]=cc
			q.append((ny,nx,cc))

print(vis[-1][-1])

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

def solve():
    dxys = [(1,0), (0,1)]

    H, W = map(int, input().split())
    Sss = ['$'*(W+2)] + ['$'+input().rstrip()+'$' for _ in range(H)] + ['$'*(W+2)]

    vWhites, vBlacks = set(), set()
    if Sss[1][1] == '.':
        vWhites.add((1, 1))
    else:
        vBlacks.add((1, 1))

    ans = 0
    while True:
        while vWhites:
            v2s = set()
            for r, c in vWhites:
                if (r, c) == (H, W):
                    return ans
                for dr, dc in dxys:
                    r2, c2 = r+dr, c+dc
                    if Sss[r2][c2] == '$': continue
                    if Sss[r2][c2] == '.':
                        v2s.add((r2, c2))
                    else:
                        vBlacks.add((r2, c2))
            vWhites = v2s
        ans += 1

        while vBlacks:
            v2s = set()
            for r, c in vBlacks:
                if (r, c) == (H, W):
                    return ans
                for dr, dc in dxys:
                    r2, c2 = r+dr, c+dc
                    if Sss[r2][c2] == '$': continue
                    if Sss[r2][c2] == '
                        v2s.add((r2, c2))
                    else:
                        vWhites.add((r2, c2))
            vBlacks = v2s



ans = solve()
print(ans)

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


from collections import deque

def solve(x,y):
    dx = [1, 0]
    dy = [0, 1]

    start = [x, y]
    dist = [[10**3]*w for i in range(h)]
    dist[y][x] = 0
    Q = deque()
    Q.append([start,l[0][0]])
    mx = 0

    while Q:
        p,color = Q.popleft()
        for i in range(2):
            nx = p[0] + dx[i]
            ny = p[1] + dy[i]

            if 0 <= nx < w and 0 <= ny < h:
                if l[ny][nx]!=color:
                    cost=1
                else:
                    cost=0
                if dist[ny][nx] > dist[p[1]][p[0]] + cost:
                    Q.append([[nx, ny],l[ny][nx]])
                    dist[ny][nx] = dist[p[1]][p[0]] + cost
    return dist

dist=solve(0,0)
if l[0][0] == "
    print(1+dist[-1][-1]//2)
else:
    print(dist[-1][-1]//2)

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

dp = [[float("inf")]*w for _ in range(h)]
dp[0][0] = 0 if A[0][0] == "." else 1
for i in range(1, w):
    dp[0][i] = dp[0][i-1]+1 if A[0][i] == "
for i in range(1, h):
    dp[i][0] = dp[i-1][0]+1 if A[i][0] == "

for i in range(1, h):
    for j in range(1, w):
        left = dp[i][j-1]+1 if A[i][j] == "
        right = dp[i-1][j]+1 if A[i][j] == "
        
        dp[i][j] = min(left, right)


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

Solution (Python):
H, W = map(int, input().split())
MAX_VAL = 10**9
cost = [[MAX_VAL]*(W+1) for _ in range(H+1)]

field = ["
for i in range(H):
    line = input()
    field.append("

if field[1][1] == "
    cost[1][1] = 1
else:
    cost[1][1] = 0

for i in range(1, H+1):
    for j in range(1, W+1):
        if i * j == 1:
            continue

        if field[i][j] == ".":
            cost[i][j] = min(cost[i-1][j], cost[i][j-1])
        else:
            top_cost = cost[i-1][j]
            left_cost = cost[i][j-1]
            
            if field[i-1][j] == ".":
                top_cost += 1
            if field[i][j-1] == ".":
                left_cost += 1
            
            cost[i][j] = min(top_cost, left_cost)

print(cost[H][W])

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


from collections import deque
cnts = [[1000] * W for i in range(H)]
q = deque()
q.append((0,0))
cnts[0][0] = 0
str_s = "."
mv = [(1,0),(0,1)]
while len(q) > 0:
    h,w = q.popleft()
    
    for dh, dw in mv:
        if h + dh < H and w + dw < W:
            
            if fields[h][w] == fields[h+dh][w+dw]:
                upd = cnts[h][w] 
            else:
                if fields[h][w] == ".":
                    upd = cnts[h][w] + 1
                else:
                    upd = cnts[h][w]
            if cnts[h+dh][w+dw] > upd:
                cnts[h+dh][w+dw] = min(cnts[h+dh][w+dw],upd)
                q.append((h+dh,w+dw))



ans = cnts[H-1][W-1]
if fields[0][0] == "
print(ans)

Solution (Python):
from heapq import heapify, heappop, heappush
from collections import defaultdict
inpl = lambda: list(map(int,input().split()))
H, W = inpl()
s = []
for h in range(H):
    s.append(input())

def dijkstra(start, goal):
    q = [(0, start)]
    done = set()
    minimum = defaultdict(lambda: None)

    while q:
        D, x = heappop(q)
        if x in done:
            continue
        elif x == goal:
            return D
        done.add(x)
        for y in {(x[0]+1,x[1]), (x[0],x[1]+1)}:
            if y[0] >= H or y[1] >= W:
                continue
            if not y in done:
                m = minimum[y]
                p = D + int(s[x[0]][x[1]] != s[y[0]][y[1]])
                if m is None or m > p:
                    heappush(q, (p, y))
                    minimum[y] = p

N = dijkstra((0,0), (H-1,W-1)) + 1
if s[0][0] == '.':
    print(N//2)
else:
    print((N+1)//2)

Solution (Python):

from collections import deque


def solve(*args: str) -> str:
    h, w = map(int, args[0].split())
    black = [[True if s == '

    inf = 10**12
    counts = [[inf]*w for _ in range(h)]
    Q = deque([(0, 0, 0, False)])
    while Q:
        x, y, n, prev = Q.popleft()
        if h <= y or w <= x:
            continue

        if black[y][x]:
            if not prev:
                n += 1
                prev = True
        else:
            prev = False

        if n < counts[y][x]:
            counts[y][x] = n
            for dx, dy in [(1, 0), (0, 1)]:
                Q.append((x+dx, y+dy, n, prev))

    return str(counts[-1][-1])


if __name__ == "__main__":
    print(solve(*(open(0).read().splitlines())))

Solution (Python):
from collections import deque
h, w = map(int, input().split())

g = []
for _ in range(h):
    tmp = list(input())
    g.append(tmp)

dp = [[1000000 for _ in range(w)] for __ in range(h)]

dp[0][0] = 0

















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

                if g[i][j] != g[i-1][j]:
                    dp[i][j] = min(dp[i][j], dp[i-1][j]+1)
                else:
                    dp[i][j] = min(dp[i][j], dp[i-1][j])


if g[0][0] == '.' and g[h-1][w-1] == '.':
    print(dp[h-1][w-1]//2)
elif g[0][0] != g[h-1][w-1]:
    print((dp[h-1][w-1]+1)//2)
else:
    print(1 + (dp[h-1][w-1]//2))