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

def input(): return sys.stdin.readline().strip()
def list2d(a, b, c): return [[c] * b for i in range(a)]
def list3d(a, b, c, d): return [[[d] * c for j in range(b)] for i in range(a)]
def list4d(a, b, c, d, e): return [[[[e] * d for j in range(c)] for j in range(b)] for i in range(a)]
def ceil(x, y=1): return int(-(-x // y))
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(N=None): return list(MAP()) if N is None else [INT() for i in range(N)]
def Yes(): print('Yes')
def No(): print('No')
def YES(): print('YES')
def NO(): print('NO')
sys.setrecursionlimit(10 ** 9)
INF = 10 ** 18
MOD = 10 ** 9 + 7

def build_grid(H, W, intv, _type, space=True, padding=False):
    
    if space:
        _input = lambda: input().split()
    else:
        _input = lambda: input()
    _list = lambda: list(map(_type, _input()))
    
    if padding:
        offset = 1
    else:
        offset = 0
    grid = list2d(H+offset*2, W+offset*2, intv)
    for i in range(offset, H+offset):
        row = _list()
        for j in range(offset, W+offset):
            grid[i][j] = row[j-offset]
    return grid

H, W = MAP()
grid = build_grid(H, W, '*', str, space=0, padding=1)

dp = list2d(H+2, W+2, INF)
if grid[1][1] == '.':
    dp[1][1] = 0
else:
    dp[1][1] = 1
for i in range(H+1):
    for j in range(W+1):
        if grid[i][j] == '.' and grid[i][j+1] == '
            dp[i][j+1] = min(dp[i][j+1], dp[i][j] + 1)
        else:
            dp[i][j+1] = min(dp[i][j+1], dp[i][j])  
        if grid[i][j] == '.' and grid[i+1][j] == '
            dp[i+1][j] = min(dp[i+1][j], dp[i][j] + 1)
        else:
            dp[i+1][j] = min(dp[i+1][j], dp[i][j])
ans = dp[H][W]
print(ans)

Solution (Python):
def main():
    h, w = map(int, input().split())
    s = [[i == "." for i in input()] for _ in range(h)]
    dp = [[10000] * w for _ in range(h)]
    dp[0][0] = 1 - s[0][0]
    for r in range(1, h):
        dp[r][0] = dp[r - 1][0] + (s[r - 1][0] and not s[r][0])
    for c in range(1, w):
        dp[0][c] = dp[0][c - 1] + (s[0][c - 1] and not s[0][c])
    for r in range(1, h):
        for c in range(1, w):
            dp[r][c] = min(dp[r - 1][c] + (s[r - 1][c] and not s[r][c]), dp[r][c - 1] + (s[r][c - 1] and not s[r][c]))
    print(dp[-1][-1])


if __name__ == '__main__':
    main()

Solution (Python):

from collections import defaultdict,deque
from heapq import heappush, heappop
from bisect import bisect_left, bisect_right
import sys, random, itertools, math
sys.setrecursionlimit(10**5)
input = sys.stdin.readline
sqrt = math.sqrt
def LI(): return list(map(int, input().split()))
def LF(): return list(map(float, input().split()))
def LI_(): return list(map(lambda x: int(x)-1, input().split()))
def II(): return int(input())
def IF(): return float(input())
def LS(): return list(map(list, input().split()))
def S(): return list(input().rstrip())
def IR(n): return [II() for _ in range(n)]
def LIR(n): return [LI() for _ in range(n)]
def FR(n): return [IF() for _ in range(n)]
def LFR(n): return [LI() for _ in range(n)]
def LIR_(n): return [LI_() for _ in range(n)]
def SR(n): return [S() for _ in range(n)]
def LSR(n): return [LS() for _ in range(n)]
mod = 1000000007
inf = float("INF")


def solve():
    h,w = LI()
    s = SR(h)
    b = [[inf] * w for i in range(h)]
    q = [(s[0][0] == "
    b[0][0] = s[0][0] == "
    while q:
        p, xy = heappop(q)
        y, x = xy
        z = s[y][x]
        for mx, my in [(0, 1), (1, 0)]:
            mx += x
            my += y
            if 0 <= mx < w and 0 <= my < h:
                if b[my][mx] > p + (z != s[my][mx] and s[my][mx] != "."):
                    b[my][mx] = p + (z != s[my][mx] and s[my][mx] != ".")
                    heappush(q, (p + (z != s[my][mx] and s[my][mx] != "."), (my, mx)))

    print(b[-1][-1] if b[-1][-1] else 0)

    return



if __name__ == '__main__':
    solve()

Solution (Python):
h, w = map(int, input().split())
s = []
for _ in range(h):
    s.append(input())
mem = [[None]*w for _ in range(h)]
def next(r, c):
    if r==h-1 and c==w-1:
        return 0 if s[0][0]=='.' else 1
    if mem[r][c] is not None:
        return mem[r][c]
    tmp = 10000
    if c<w-1:
        if s[r][c]=='.' and s[r][c+1]=='
            tmp = next(r, c+1) + 1
        else:
            tmp = next(r, c+1)
    if r<h-1:
        if s[r][c]=='.' and s[r+1][c]=='
            tmp = min(next(r+1, c) + 1, tmp)
        else:
            tmp = min(next(r+1, c), tmp)
    mem[r][c] = tmp
    return tmp
print(next(0, 0))

Solution (Python):
H, W = map(int,input().split())
MAP = []
INF = 10 ** 8
for _ in range(H):
    MAP.append(input())

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

for i in range(H):
    for j in range(W):
        if i == 0 and j == 0:
            if MAP[i][j] == "
                dp[i][j] = 1
        elif i == 0:
            flag = 0
            if MAP[i][j] == "
                flag = 1
            dp[i][j] = flag + dp[i][j-1]
        elif j == 0:
            flag = 0
            if MAP[i][j] == "
                flag = 1
            dp[i][j] = flag + dp[i-1][j]
        else:
            flag1 = 0
            flag2 = 0
            if MAP[i][j] == "
                flag1 = 1
            if MAP[i][j] == "
                flag2 = 1
            dp[i][j] = min(dp[i][j-1]+flag1,dp[i-1][j]+flag2)
        

print(dp[H-1][W-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())
ls = []
for i in range(h):
    ls.append(list(input()))
ma = [[(10**9)]*w for i in range(h)]
if ls[0][0] == "." :
    ma[0][0] = 0
else:
    ma[0][0] =1
delta = [(-1,0),(0,-1)]
for y in range(h):
    for x in range(w):
        for dy,dx in delta:
            if 0<=y+dy<=h-1 and 0<=x+dx<=w-1 :
                if ls[y][x] == ls[y+dy][x+dx]:
                    ma[y][x] = min(ma[y+dy][x+dx],ma[y][x])
                else:
                    if ls[y][x] =="
                        cnt = 1
                    else:
                        cnt =0
                    ma[y][x] = min(ma[y][x],ma[y+dy][x+dx]+cnt)
print(ma[h-1][w-1])

Solution (Python):






import sys
input = sys.stdin.readline

import math
from collections import deque
from fractions import gcd
from functools import lru_cache






MOD = 10**9 +7
INF = float('inf')






def inputI(): return int(input().strip())
def inputS(): return input().strip()
def inputIL(): return list(map(int,input().split()))
def inputSL(): return list(map(str,input().split()))
def inputILs(n): return list(int(input()) for _ in range(n))
def inputSLs(n): return list(input().strip() for _ in range(n))
def inputILL(n): return [list(map(int, input().split())) for _ in range(n)]
def inputSLL(n): return [list(map(str, input().split())) for _ in range(n)]


def inv(n): return pow(n, MOD-2, MOD)


kaijo_memo = []
def kaijo(n):
  if(len(kaijo_memo) > n):
    return kaijo_memo[n]
  if(len(kaijo_memo) == 0):
    kaijo_memo.append(1)
  while(len(kaijo_memo) <= n):
    kaijo_memo.append(kaijo_memo[-1] * len(kaijo_memo) % MOD)
  return kaijo_memo[n]

gyaku_kaijo_memo = []
def gyaku_kaijo(n):
  if(len(gyaku_kaijo_memo) > n):
    return gyaku_kaijo_memo[n]
  if(len(gyaku_kaijo_memo) == 0):
    gyaku_kaijo_memo.append(1)
  while(len(gyaku_kaijo_memo) <= n):
    gyaku_kaijo_memo.append(gyaku_kaijo_memo[-1] * pow(len(gyaku_kaijo_memo),MOD-2,MOD) % MOD)
  return gyaku_kaijo_memo[n]

def nCr(n,r):
  if(n == r):
    return 1
  if(n < r or r < 0):
    return 0
  ret = 1
  ret = ret * kaijo(n) % MOD
  ret = ret * gyaku_kaijo(r) % MOD
  ret = ret * gyaku_kaijo(n-r) % MOD
  return ret


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

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


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





H,W = inputIL()
s = []
for i in range(H):
  s.append(list(inputS()))

dp = [[INF for __ in range(W)] for ___ in range(H)]

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


if s[0][0] == ".":
  print((dp[-1][-1]+1)//2)
else:
  print((dp[-1][-1])//2+1)

Solution (Python):
def flip_count_mem(r, c):
  if memory[r][c] < 0:
    memory[r][c] = flip_count(r, c)
  return memory[r][c]

def flip_count (r, c):
  if r == H - 1 and c == W - 1:
    if s[r][c] == "
      return 1
    else:
      return 0
  
  if c == W - 1:
    count_right = 10000
  else:
    count_right = flip_count_mem (r, c + 1)
    if s[r][c] == "
      count_right += 1
  
  if r == H - 1:
    count_down = 10000
  else:
    count_down = flip_count_mem (r + 1, c)
    if s[r][c] == "
      count_down += 1
  return min(count_right, count_down)

H, W = input().split()
W = int (W)
H = int (H)
s = []
for i in range(H):
  s.append(input())
memory = [[-1 for i in range(W)] for j in range(H)]
print (flip_count(0, 0))

Solution (Python):
def main():
    H, W = map(int, input().split())
    S = [input() for _ in range(H)]
    if S[0][0] == '.':
        c, f = 0, False
    else:
        c, f = 1, True
    v = [(c, f)]
    for s in S[0][1:]:
        sf = s == '
        if sf != f:
            c, f = c + 1, not f
        v.append((c, f))
    u = v
    for ss in S[1:]:
        c, f = u[0]
        sf = ss[0] == '
        if sf != f:
            c, f = c + 1, not f
        v = [(c, f)]
        for i, s in enumerate(ss[1:], 1):
            uc, uf = u[i]
            sf = s == '
            if uf != sf:
                uc, uf = uc + 1, not uf
            if f != sf:
                c, f = c + 1, not f
            if uc < c:
                c, f = uc, uf
            v.append((c, f))
        u = v
    return (u[-1][0] + 1) // 2

print(main())

Solution (Python):
from math import ceil
from collections import defaultdict

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

n = h * w
INF = 100 * 100

dp = defaultdict(lambda: INF)
if s[0][0] == "
    dp[(1, 1, 1)] = 1
else:
    dp[(1, 1, 0)] = 0

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

idx = 1 if s[h-1][w-1] == "
ans = dp[(h, w, idx)]
ans = ceil(ans / 2)
print(ans)

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

dp = [[[0, False] for _ in range(W)] for _ in range(H)]


if S[0][0] == "
    dp[0][0][0] = 1
    dp[0][0][1] = True
for j in range(1,W):
    dp[0][j] = dp[0][j-1].copy()
    if not dp[0][j-1][1]:
        if S[0][j] == "
            dp[0][j][0] += 1
            dp[0][j][1] = True
    else:
        if S[0][j] == ".":
            dp[0][j][1] = False
for i in range(1,H):
    dp[i][0] = dp[i-1][0].copy()
    if not dp[i-1][0][1]:
        if S[i][0] == "
            dp[i][0][0] += 1
            dp[i][0][1] = True
    else:
        if S[i][0] == ".":
            dp[i][0][1] = False

def which(i,j):
    """
    True -> 上
    False -> 左
    """
    if dp[i-1][j][0] > dp[i][j-1][0]:
        return False
    elif dp[i-1][j][0] < dp[i][j-1][0]:
        return True
    else:
        if S[i][j] == "
            if dp[i-1][j][1]:
                return True
            else:
                return False
        else:
            if not dp[i-1][j][1]:
                return True
            else:
                return False


for i in range(1,H):
    for j in range(1,W):
        if which(i,j): 
            dp[i][j] = dp[i-1][j].copy()
            if not dp[i-1][j][1]:
                if S[i][j] == "
                    dp[i][j][0] += 1
                    dp[i][j][1] = True
            else:
                if S[i][j] == ".":
                    dp[i][j][1] = False
        else: 
            dp[i][j] = dp[i][j-1].copy()
            if not dp[i][j-1][1]:
                if S[i][j] == "
                    dp[i][j][0] += 1
                    dp[i][j][1] = True
            else:
                if S[i][j] == ".":
                    dp[i][j][1] = False

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

Solution (Python):
from collections import deque
h,w = map(int,input().split())
data = [input() for _ in range(h)]
pena = [[10**10]*w for _ in range(h)]
queue = deque()
if data[0][0] == ".":
    pena[0][0] = 0
else:
    pena[0][0] = 1
queue.append([0,0])
while queue:
    x,y = queue.popleft()
    if x+1<h:
        c = False
        if pena[x+1][y] == 10**10:
            c = True
        if data[x+1][y] == '
            pena[x+1][y] = min(pena[x+1][y],pena[x][y] + 1)
        else:
            pena[x+1][y] = min(pena[x+1][y],pena[x][y])
        if c:
            queue.append([x+1,y])

    if y+1<w:
        c = False
        if pena[x][y+1] == 10 ** 10:
            c = True
        if data[x][y+1] == '
            pena[x][y+1] = min(pena[x][y+1],pena[x][y] + 1)
        else:
            pena[x][y + 1] = min(pena[x][y+1], pena[x][y])
        if c:
            queue.append([x,y+1])

print(pena[-1][-1])

Solution (Python):

import sys
sys.setrecursionlimit(1 << 25)
read = sys.stdin.readline


def read_ints():
    return list(map(int, read().split()))


def read_a_int():
    return int(read())


def read_tuple(H):
    '''
    H is number of rows
    '''
    ret = []
    for _ in range(H):
        ret.append(tuple(map(int, read().split())))
    return ret


def read_col(H, n_cols):
    '''
    H is number of rows
    n_cols is number of cols
    A列、B列が与えられるようなとき
    '''
    ret = [[] for _ in range(n_cols)]
    for _ in range(H):
        tmp = list(map(int, read().split()))
        for col in range(n_cols):
            ret[col].append(tmp[col])
    return ret


def read_matrix(H):
    '''
    H is number of rows
    '''
    ret = []
    for _ in range(H):
        ret.append(list(map(int, read().split())))
    return ret
    


def read_map(H):
    '''
    H is number of rows
    文字列で与えられた盤面を読み取る用
    '''
    return [read()[:-1] for _ in range(H)]


def read_map_as_int(H):
    '''
    
    '''
    ret = []
    for _ in range(H):
        ret.append([1 if s == '
        
        
    return ret


MOD = 10**9 + 7

from itertools import product, permutations, combinations
H, W = read_ints()
S = read_map_as_int(H)  

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

dp[0][0] = S[0][0]

for i, j in product(range(H), range(W)):
    if i == 0 and j == 0:
        continue
    if i != 0:
        dp[i][j] = min(dp[i][j], dp[i - 1][j]
                       + (1 if S[i][j] == 1 and S[i - 1][j] == 0 else 0))
    if j != 0:
        dp[i][j] = min(dp[i][j], dp[i][j - 1]
                       + (1 if S[i][j] == 1 and S[i][j - 1] == 0 else 0))

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

Solution (Python):
H, W = map(int, input().split())
S = ['' for _ in range(H)]
for i in range(H):
    S[i] = input()
DP = [[0 for _ in range(W)] for _ in range(H)]
if S[0][0] == '
    DP[0][0] = 1
for i in range(1,W):
    if S[0][i] == '
        DP[0][i] = DP[0][i-1] + 1
    else:
        DP[0][i] = DP[0][i-1]
for h in range(1,H):
    for w in range(W):
        if w == 0:
            if S[h][w] == '
                DP[h][w] = DP[h-1][w] + 1
            else:
                DP[h][w] = DP[h-1][w]
        else:
            if S[h][w] == '
                r = DP[h-1][w] + 1
            else:
                r = DP[h-1][w]
            if S[h][w] == '
                c = DP[h][w-1] + 1
            else:
                c = DP[h][w-1]
            DP[h][w] = min(r, c)
print(DP[H-1][W-1])

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

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

for i in range(h):
    for j in range(w-1):
        if i > 0:
            dp[i][0] = dp[i-1][0] if s[i][0] == s[i-1][0] else dp[i-1][0]+1
            above = dp[i-1][j+1]
            left  = dp[i][j]
            if s[i-1][j+1] != s[i][j+1]:
                above += 1
            if s[i][j] != s[i][j+1]:
                left += 1
            dp[i][j+1] = min(above,left)
        else:
            left  = dp[i][j]
            if s[i][j] != s[i][j+1]:
                left += 1
            dp[i][j+1] = left

n = dp[-1][-1]
if s[0][0] == '.' and s[-1][-1] == '.':
    print(n//2)
elif s[0][0] == '
    print(n//2+1)
else:
    print((n+1)//2)

Solution (Python):
input = raw_input
h, w = map(int, input().split(" "))
gh = h - 1
gw = w - 1








        
maps = [list(input()) for _ in range(h)]
num_maps = [[None for _ in range(w)] for _ in range(h)]

count = 0
def find(sx, sy, cur_cost, color):
    next_cost_coord = []
    global count
    num_r = 1
    found = False
    routes = [(sx, sy)]
    num_maps[sy][sx] = cur_cost
    count += 1

    pre = False
    if sx == 1 and sy == 1:
        pre = True

    while num_r >= 1 and not found:
        x, y = routes[0]
        routes = routes[1:]
        num_r -= 1

        for nx, ny in [(x+1, y), (x, y+1)]:
            if pre:
                pass
                
                
                

            if nx <= gw and ny <= gh:
                if num_maps[ny][nx] is None:
                    if maps[ny][nx] == color:
                        num_maps[ny][nx] = cur_cost
                        if nx == gw and ny == gh:
                            found = True
                            return next_cost_coord, found
                        else:
                            routes.append((nx, ny))
                            num_r += 1
                    else:
                        next_cost_coord.append((nx, ny))
    return next_cost_coord, found

cur_coords = [(0, 0)]
if maps[0][0] == ".":
    cur_cost = 0
else:
    cur_cost = 1

while True:   
    color = "." if cur_cost % 2 == 0 else "
    
    next_coords = []

    in_cost = cur_cost // 2 if cur_cost % 2 == 0 else cur_cost // 2 + 1
    for sx, sy in cur_coords:
        cur_nc_coord, found = find(sx, sy, in_cost, color)
        next_coords += cur_nc_coord
        
        found = num_maps[gh][gw] is not None
        if found:
            break
    
    if found:
        break
    else:
        
        cur_coords = set(next_coords)
        assert len(cur_coords) >= 1
        cur_cost += 1
        

out = num_maps[gh][gw]
print(out)

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

mat=[]
for i in range(H):
  array=[x=='.' for x in input()]
  mat.append(array)


dist=[]
for i in range(H):
  dist.append([-1]*W)

if mat[0][0]:
  dist[0][0]=0
else:
  dist[0][0]=1
  
for i in range(1,H):
  if mat[i-1][0] and not mat[i][0]:
    dist[i][0]=dist[i-1][0]+1
  else:
    dist[i][0]=dist[i-1][0]
    
for j in range(1,W):
  if mat[0][j-1] and not mat[0][j]:
    dist[0][j]=dist[0][j-1]+1
  else:
    dist[0][j]=dist[0][j-1]
    
for i in range(1,H):
  for j in range(1,W):
    if mat[i-1][j] and not mat[i][j]:
      dist1=dist[i-1][j]+1
    else:
      dist1=dist[i-1][j]
    
    if mat[i][j-1] and not mat[i][j]:
      dist2=dist[i][j-1]+1
    else:
      dist2=dist[i][j-1]
      
    dist[i][j]=min(dist1,dist2)
    

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

Solution (Python):
def main():
    H, W = map( int, input().split())
    S = [ list( input()) for _ in range(H)]
    
    
    
    
    
    
    
    dp = [[10**5]*W for _ in range(H)]
    
    
    
    
    dp[0][0] = 0
    for i in range(H):
        for j in range(W):
            if i > 0:
                if S[i-1][j] == S[i][j]:
                    if dp[i-1][j] < dp[i][j]:
                        dp[i][j] = dp[i-1][j]
                else:
                    if dp[i-1][j]+1 < dp[i][j]:
                        dp[i][j] = dp[i-1][j]+1
            if j > 0:
                if S[i][j-1] == S[i][j]:
                    if dp[i][j-1] < dp[i][j]:
                        dp[i][j] = dp[i][j-1]
                else:
                    if dp[i][j-1]+1 < dp[i][j]:
                        dp[i][j] = dp[i][j-1]+1
    
    ans = dp[H-1][W-1]
    ans //= 2
    if S[0][0] == "
        ans += 1
    print(ans)
                
if __name__ == '__main__':
    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)])
while q:
	cy,cx=q.popleft()
	for ny,nx in ((cy+1,cx),(cy,cx+1)):
		if not not (0<=ny<h and 0<=nx<w) and vis[cy][cx]+(g[cy][cx]!=g[ny][nx]=="
			vis[ny][nx]=vis[cy][cx]+(g[cy][cx]!=g[ny][nx]=="
			q.append((ny,nx))
print(vis[-1][-1])

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

road_count = 0
lis = [list('
for _ in range(h):
    li = input()
    for i in li:
        if i == '.':
            road_count += 1
    li = '
    lis.append(list(li))
lis.append(list('


dp = [[999]*(w+2) for _ in range(h+2)]

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



step = [[1,1]]
while len(step)>0:
    x,y = step.pop(0)
    if x > h:
        continue
    if y > w:
        continue
    
    if dp[x+1][y] == 999:
        step.append([x+1,y])
        if lis[x+1][y] != '
            dp[x+1][y] = min(dp[x][y],dp[x+1][y-1])
        else:
            if lis[x][y] == '
                dp[x+1][y] = min(dp[x][y],dp[x+1][y-1])
            elif lis[x][y] == '
                dp[x+1][y] = min(dp[x][y],dp[x+1][y-1]+1)
            elif lis[x+1][y-1] == '
                dp[x+1][y] = min(dp[x][y]+1,dp[x+1][y-1])
            else:
                dp[x+1][y] = min(dp[x][y],dp[x+1][y-1])+1
    if dp[x][y+1] == 999:
        step.append([x,y+1])
        if lis[x][y+1] != '
            dp[x][y+1] = min(dp[x][y],dp[x-1][y+1])
        else:
            if lis[x][y] == '
                dp[x][y+1] = min(dp[x][y],dp[x-1][y+1])
            elif lis[x][y] == '
                dp[x][y+1] = min(dp[x][y],dp[x-1][y+1]+1)
            elif lis[x-1][y+1] == '
                dp[x][y+1] = min(dp[x][y]+1,dp[x-1][y+1])
            else:
                dp[x][y+1] = min(dp[x][y],dp[x-1][y+1])+1


print(dp[h][w])

Solution (Python):
import heapq

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

mat=[]
for i in range(H):
  array=[x=='.' for x in input()]
  mat.append(array)


dist=[]
for i in range(H):
  dist.append([-1]*W)

if mat[0][0]:
  dist[0][0]=0
else:
  dist[0][0]=1
  
for i in range(1,H):
  if mat[i-1][0] and not mat[i][0]:
    dist[i][0]=dist[i-1][0]+1
  else:
    dist[i][0]=dist[i-1][0]
    
for j in range(1,W):
  if mat[0][j-1] and not mat[0][j]:
    dist[0][j]=dist[0][j-1]+1
  else:
    dist[0][j]=dist[0][j-1]
    
for i in range(1,H):
  for j in range(1,W):
    if mat[i-1][j] and not mat[i][j]:
      dist1=dist[i-1][j]+1
    else:
      dist1=dist[i-1][j]
    
    if mat[i][j-1] and not mat[i][j]:
      dist2=dist[i][j-1]+1
    else:
      dist2=dist[i][j-1]
      
    dist[i][j]=min(dist1,dist2)
    

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

Solution (Python):


iim = lambda: map(int, input().rstrip().split())

def resolve():
    H, W = iim()
    S = [input() for i in range(H)]
    c1 = "
    H1, W1 = H-1, W-1

    inf = H*W+1
    dq = [0]*W
    dq0 = [(inf, True)]*W
    dq0[0] = (0, True)

    for y in range(H):
        (co, good0) = dq0[0]

        good = not S[y][0] == c1
        if not good:
            if good0:
                co += 1
        dq1 = dq[0] = (co, good)
        for x in range(1, W):
            (co0, good0) = dq0[x]
            (co1, good1) = dq1
            good = not S[y][x] == c1
            if not good:
                if good0:
                    co0 += 1
                if good1:
                    co1 += 1
            dq1 = dq[x] = (min(co0, co1), good)
        dq, dq0 = dq0, dq
        
    print(dq0[-1][0])

if __name__ == "__main__":
    resolve()

Solution (Python):
def bw(a):
    c=0
    if a=="
        c=1
    return c

def bw2(a,b): 
    c=0
    if a=="." and b=="
        c=1
    return c

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

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

M=[[1000 for j in range(W)] for i in range(H) ]

M[0][0] = bw(s[0][0])


for i in range(H-1):
    M[i+1][0] = M[i][0] + bw2(s[i][0],s[i+1][0]) 

    
for j in range(W-1):
    M[0][j+1] = M[0][j]+ bw2(s[0][j],s[0][j+1])

    

for i in range(H-1):
    for j in range(W-1):
        
        M[i+1][j+1] = min(M[i][j+1] + bw2(s[i][j+1],s[i+1][j+1]) , M[i+1][j]+ bw2(s[i+1][j],s[i+1][j+1]) )
print(M[H-1][W-1])

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


unsearched_nodes = list(range(1,H*W+1)) 
distance= [10000]*(W*H+1)

previous_move = [[-1]*(W+2) for _ in range(H+2)] 
previous_color = [''] * (H*W+1)
distance[1] = 0 
if S[1][1]=='
  distance[1] = 1
while len(unsearched_nodes) != 0: 
    
  posible_min_distance = 10001 
  for node_index in unsearched_nodes: 
    
    if posible_min_distance > distance[node_index]: 
      posible_min_distance = distance[node_index] 
      target_min_index = node_index
  
  unsearched_nodes.remove(target_min_index) 
	
  dh = [0,1]
  dw = [1,0]
  target_h = (target_min_index-1) // W + 1
  target_w = target_min_index % W
  if target_w == 0:
    target_w = W
  for i in range(2):
    h = target_h + dh[i]
    w = target_w + dw[i]
    ind = (h-1)*W+w
    route_dis = 0
    if S[h][w]=='*':
      continue
    if S[h][w]=='
      if S[target_h][target_w]=='.':
        route_dis = 1
    if distance[ind] > distance[target_min_index] + route_dis:
      distance[ind] = distance[target_min_index] + route_dis 
      previous_color[ind] =  S[target_h][target_w]
      
  
print(distance[-1])

Solution (Python):
import bisect
import collections
import sys

sys.setrecursionlimit(100000)
input = sys.stdin.readline
ACMOD = 1000000007
INF = 1 << 32


def lmi():
    return list(map(int, input().split()))


def llmi(n):
    return [lmi() for _ in range(n)]


H, W = lmi()
S = [input().strip() for _ in range(W)]

import functools


@functools.lru_cache(maxsize=None)
def solve(h, w, last_b=False):
    if h < 0 or w < 0:
        return INF
    if h == 0 and w == 0:
        return int(S[0][0] == '
    b = bool(S[h][w] == '
    if b:
        return min(solve(h - 1, w, last_b=True) + (not last_b),
                   solve(h, w - 1, last_b=True) + (not last_b),
                   )
    return min(
        solve(h - 1, w, last_b=False),
        solve(h, w - 1, last_b=False),
        solve(h - 1, w, last_b=True) + 1,
        solve(h, w - 1, last_b=True) + 1,
        
        
    )


print(solve(H - 1, W - 1))

Solution (Python):
import copy
H, W = map(int, input().split())
fields = []


def black_white(x):
    if x == '.':  
        return 0
    elif x == '
        return 1  


for i in range(H):
    fields.append(list(map(black_white, list(input()))))

DP_map = [[0 for i in range(W)] for j in range(H)]

if fields[0][0] == 1:
    DP_map[0][0] = 1
for h in range(H):
    for w in range(W):
        if h == 0 and w == 0:
            continue
        elif h == 0:
            if fields[h][w] - fields[h][w-1] == 1:
                DP_map[h][w] = DP_map[h][w-1] + 1
            else:
                DP_map[h][w] = DP_map[h][w-1]
            
        elif w == 0:
            if fields[h][w] - fields[h-1][w] == 1:
                DP_map[h][w] = DP_map[h-1][w] + 1
            else:
                DP_map[h][w] = DP_map[h-1][w]
        else:
            if fields[h][w] - fields[h][w-1] == 1:
                horizontal_cnt = DP_map[h][w-1] + 1
            else:
                horizontal_cnt = DP_map[h][w-1]
            if fields[h][w] - fields[h-1][w] == 1:
                vertical_cnt = DP_map[h-1][w] + 1
            else:
                vertical_cnt = DP_map[h-1][w]
            DP_map[h][w] = min(horizontal_cnt, vertical_cnt)
print(DP_map[H-1][W-1])