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):
inputs = [s.strip() for s in open(0).readlines()]
import numpy as np
class Grid():
    def __init__(self, grid, w=0, h=0, function=lambda x: x):
        self.w = w = w if w else len(grid[0])
        self.h = h = h if h else len(grid)
        dtype = type(function(grid[0][0]))
        self.grid = np.empty((h, w), dtype=dtype)
        for i, row in zip(range(h), grid):
            for j, val in zip(range(w), row):
                self.grid[i][j] = function(val)
    
    def is_valid_x(self, x):
        return 0 <= x < self.w
    def is_valid_y(self, y):
        return 0 <= y < self.h
    def is_valid_xy(self, x, y):
        return self.is_valid_x(x) and self.is_valid_y(y) 
    
    def __iter__(self):
        return iter(self.grid)
    def __repr__(self):
        return '\n'.join([' '.join(map(str, row)) for row in self.grid])
    def __getitem__(self, x):
        return self.grid[x]
    def __setitem__(self, x, val):
        self.grid[x] = val

h, w = map(int, inputs[0].split())
grid = Grid(inputs[1:]).grid

dp = np.zeros((h, w), np.int)
if grid[0][0] == '
    dp[0, 0] = 1
for i in range(1, w):
    dp[0, i] = dp[0, i-1] + int(grid[0, i-1] + grid[0, i] == '.
for i in range(1, h):
    dp[i, 0] = dp[i-1, 0] + int(grid[i-1, 0] + grid[i, 0] == '.
x = y = 1
while not (x == w-1 and y == h-1):
    for i in range(x, w):
        dp[y, i] = min(dp[y, i-1] + int(grid[y, i-1] + grid[y, i] == '.
                       dp[y-1, i] + int(grid[y-1, i] + grid[y, i] == '.
    for i in range(y+1, h):
        dp[i, x] = min(dp[i-1, x] + int(grid[i-1, x] + grid[i, x] == '.
                       dp[i, x-1] + int(grid[i, x-1] + grid[i, x] == '.
    x, y = min(x+1, w-1), min(y+1, h-1)
print(min(dp[y-1, x] + int(grid[y-1, x] + grid[y, x] == '.
          dp[y, x-1] + int(grid[y, x-1] + grid[y, x] == '.

Solution (Python):
import sys
import numpy as np
H, W = map(int, input().split())
I = np.array([list(map(str, input())) for _ in range(H)])
grid = np.zeros([H,W], np.int16)
grid[np.where(I=='
inf = np.inf
dp = np.full([H,W], inf)
if grid[0,0] == 1:
    dp[0,0] = 1
else:
    dp[0,0] = 0

for i in range(H):
    for j in range(W):
        if i + 1 < H:
            if grid[i,j] == grid[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 + 1 < W:
            if grid[i,j] == grid[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)
if grid[-1,-1] == 1:
    dp[-1,-1,] += 1
ans = dp[-1,-1]//2
print(int(ans))

Solution (Python):
'''input
5 5
.

.

.
'''

import sys
import math
from collections import Counter

debug = 0
readln = sys.stdin.readline


def write(s):
    sys.stdout.write(str(s))

def writeln(s):
    sys.stdout.write(str(s))
    sys.stdout.write('\n')

def readint():
    return int(readln().strip())

def readints():
    return map(int, readln().split())

def readstr():
    return readln().strip()

def readstrs():
    return readln().split()

def dbg(*args):
    if debug: print(' '.join(map(str, args)))


h,w = readints()
mat = []
dp = [[0] * w for _ in xrange(h)]
for _ in xrange(h):
    mat.append(readstr())

def getdp(r, c, cur):
    if r < 0 and c == 0 or c < 0 and r == 0:
        old = 0
        oldc = '.'
    elif r < 0 or c < 0:
        return 2**31
    else:
        old = dp[r][c]
        oldc = mat[r][c]

    if cur == '
        return old + 1
    else:
        return old

def solve(h, w):
    global dp
    for r in xrange(h):
        for c in xrange(w):
            cur = mat[r][c]
            dp[r][c] = min(getdp(r-1, c, cur), getdp(r, c-1, cur))
    dbg(dp)
    return dp[h-1][w-1]

print solve(h, w)

Solution (Python):
import sys


INF = sys.maxsize
H, W = map(int, input().split())
m = []

for i in range(H):
  m.append([x for x in input()])

dp = [[INF] * W for _ in range(H)]
dp[0][0] = 0 if m[0][0] == '.' else 1

for i in range(H):
  for j in range(W):    
    for di, dj in [(0, 1), (1, 0)]:
      ni = i + di
      nj = j + dj
      if ni < H and nj < W:
        dp[ni][nj] = min(
          dp[ni][nj],
          dp[i][j] + 1 if m[i][j] == '.' and m[ni][nj] == '
        )

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

Solution (Python):
import itertools
import os
import sys

if os.getenv("LOCAL"):
    sys.stdin = open("_in.txt", "r")

sys.setrecursionlimit(10 ** 9)
INF = float("inf")
IINF = 10 ** 18
MOD = 10 ** 9 + 7



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


dp = [[INF] * W for _ in range(H)]
dp[0][0] = 1 if S[0][0] == '
for h, w in itertools.product(range(H), range(W)):
    for ph, pw in [(h - 1, w), (h, w - 1)]:
        if 0 <= ph < H and 0 <= pw < W:
            d = int(S[ph][pw] == '.' and S[h][w] == '
            dp[h][w] = min(dp[h][w], dp[ph][pw] + d)
print(dp[-1][-1])

Solution (Python):
H, W = map(int, input().split())
board = [list(input()) for _ in range(H)]
INF = float('inf')
dp = [[INF] * W for _ in range(H)]
if board[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 board[i][j] == board[i-1][j]:
            dp[i][j] = min(dp[i][j], dp[i-1][j])
        else:
            dp[i][j] = min(dp[i][j], dp[i-1][j] + 1)
        if board[i][j] == board[i][j-1]:
            dp[i][j] = min(dp[i][j], dp[i][j-1])
        else:
            dp[i][j] = min(dp[i][j], dp[i][j-1] + 1)
if board[H-1][W-1] == '
    dp[H-1][W-1] += 1
print(dp[H-1][W-1] // 2)

Solution (Python):
import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
sys.setrecursionlimit(10 ** 7)

from math import ceil

h, w = map(int, readline().split())
s = [input() for i in range(h)]
dp = [[float('inf')] * w for j in range(h)]
if s[0][0] == '
    dp[0][0] = 1
else:
    dp[0][0] = 0
for i in range(h):
    for j in range(w):
        if w - 1 != j:
            cnt = 0
            if s[i][j + 1] != s[i][j]:
                cnt += 1
            dp[i][j + 1] = min(dp[i][j + 1], dp[i][j] + cnt)
        if h - 1 != i:
            cnt = 0
            if s[i + 1][j] != s[i][j]:
                cnt += 1
            dp[i + 1][j] = min(dp[i + 1][j], dp[i][j] + cnt)
print(ceil(dp[-1][-1] / 2))

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

INF = 10 ** 18
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 S[i][j] == ".":
            dp[i][j] = min(dp[i][j], dp[i - 1][j], dp[i][j - 1])
        else:
            dp[i][j] = min(dp[i][j],
                            dp[i - 1][j] if S[i - 1][j] == "
                            dp[i][j - 1] if S[i][j - 1] == "

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

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

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

if S[0][0] == "
    dp[0][0] = 1
else:
    dp[0][0] = 0

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

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

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

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

Solution (Python):
def main():
    H, W = (int(i) for i in input().split())
    c = [input() for i in range(H)]
    dp = [[10**3]*W for _ in range(H)]
    if c[0][0] == "
        dp[0][0] = 1
    else:
        dp[0][0] = 0
    for h in range(H):
        for w in range(W):
            if c[h][w] == ".":
                if w < W-1 and c[h][w+1] == ".":
                    dp[h][w+1] = min(dp[h][w+1], dp[h][w])
                elif w < W-1 and c[h][w+1] == "
                    dp[h][w+1] = min(dp[h][w+1], dp[h][w] + 1)
                if h < H-1 and c[h+1][w] == ".":
                    dp[h+1][w] = min(dp[h+1][w], dp[h][w])
                elif h < H-1 and c[h+1][w] == "
                    dp[h+1][w] = min(dp[h+1][w], dp[h][w] + 1)
            else:
                if w < W-1:
                    dp[h][w+1] = min(dp[h][w+1], dp[h][w])
                if h < H-1:
                    dp[h+1][w] = min(dp[h+1][w], dp[h][w])
    print(dp[H-1][W-1])
    


if __name__ == '__main__':
    main()

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

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

dp = [[10**18 for i in range(w)] for j in range(h)]

dp[0][0] = 0

for i in range(w-1):
    if sij[0][i+1] != sij[0][i]:
        dp[0][i+1] = dp[0][i]+1
    else:
        dp[0][i+1] = dp[0][i]
        
for i in range(h-1):
    if sij[i+1][0] != sij[i][0]:
        dp[i+1][0] = dp[i][0]+1
    else:
        dp[i+1][0] = dp[i][0]

for i in range(1,h):
    for j in range(1,w):
        
        if sij[i-1][j] != sij[i][j]:
            sita = dp[i-1][j]+1
        else:
            sita = dp[i-1][j]
        if sij[i][j-1] != sij[i][j]:
            yoko = dp[i][j-1]+1
        else:
            yoko = dp[i][j-1]
        
        dp[i][j] = min(sita,yoko)

add = 0


if sij[0][0] == '
    add = 1
"""
if dp[h-1][w-1] == 1:
    print(1)
else:
    print(dp[h-1][w-1]//2+add)
""" 
if dp[h-1][w-1] % 2 == 1:
    print(dp[h-1][w-1]//2+1)
else:
    print(dp[h-1][w-1]//2+add)

Solution (Python):
import math
h,w = map(int,input().split())
g = [list(input()) for _ in range(h)]
dp = [[float('inf')]*w for _ in range(h)]
if g[0][0] == '.':
    dp[0][0] = 0
else:
    dp[0][0] = 1

for i in range(h):
    for j in range(w):
        for di, dj in zip((0,1), (1, 0)):
            ni, nj = i+di, j+dj
            if ni>=h or nj>=w:
                continue
            if g[ni][nj]!=g[i][j]:
                dp[ni][nj] = min(dp[ni][nj], dp[i][j]+1)
            else:
                dp[ni][nj] = min(dp[ni][nj], dp[i][j])
print(math.ceil(dp[h-1][w-1]/2))

Solution (Python):
H, W = map(int, input().split())
board = [list(input()) for _ in range(H)]
INF = float('inf')
dp = [[INF] * W for _ in range(H)]
if board[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 board[i][j] == board[i-1][j]:
            dp[i][j] = min(dp[i][j], dp[i-1][j])
        else:
            dp[i][j] = min(dp[i][j], dp[i-1][j] + 1)
        if board[i][j] == board[i][j-1]:
            dp[i][j] = min(dp[i][j], dp[i][j-1])
        else:
            dp[i][j] = min(dp[i][j], dp[i][j-1] + 1)
if board[H-1][W-1] == '
    dp[H-1][W-1] += 1
print(dp[H-1][W-1] // 2)

Solution (Python):
def main():
    height, width = map(int, input().split())
    grid = [list(input()) for _ in range(height)]
    dp = [[float("inf") for _ in range(width)] for _ in range(height)]
    if grid[0][0] == "
        dp[0][0] = 1
    else:
        dp[0][0] = 0
    delta = [[0, 1], [1, 0]]
    for i in range(height):
        for j in range(width):
            for dx, dy in delta:
                if i + dy >= height or j + dx >= width:
                    continue
                else:
                    add = 0
                    if grid[i][j] == "." and grid[i + dy][j + dx] == "
                        add = 1
                    dp[i + dy][j + dx] = min(dp[i + dy][j + dx], dp[i][j] + add)
    print(dp[-1][-1])


if __name__ == '__main__':
    main()

Solution (Python):
import numpy as np

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




dp = [[0]*W for i in range(H)]
if masu[0][0] == "
    dp[0][0] = 1

for i in range(0,H):
    for j in range(0,W):
        if i == 0:
            a = 100000
        else:
            if masu[i][j] == "
                a = dp[i-1][j] + 1
            else:
                a = dp[i-1][j]
        if j == 0:
            b = 100000
        else:
            if masu[i][j] == "
                b = dp[i][j-1] + 1
            else:
                b = dp[i][j-1]
        if a != 100000 or b != 100000:
            dp[i][j] = min([a, b])
print(int(dp[H-1][W-1]))

Solution (Python):


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




dp = [[0]*W for i in range(H)]
if masu[0][0] == "
    dp[0][0] = 1

for i in range(0,H):
    for j in range(0,W):
        if i == 0:
            a = 100000
        else:
            if masu[i][j] == "
                a = dp[i-1][j] + 1
            else:
                a = dp[i-1][j]
        if j == 0:
            b = 100000
        else:
            if masu[i][j] == "
                b = dp[i][j-1] + 1
            else:
                b = dp[i][j-1]
        if a != 100000 or b != 100000:
            dp[i][j] = min([a, b])
print(int(dp[H-1][W-1]))

Solution (Python):
import numpy as np

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



dp = np.zeros((H, W))
if masu[0][0] == "
    dp[0][0] = 1

for i in range(0,H):
    for j in range(0,W):
        if i == 0:
            a = 100000
        else:
            if masu[i][j] == "
                a = dp[i-1][j] + 1
            else:
                a = dp[i-1][j]
        if j == 0:
            b = 100000
        else:
            if masu[i][j] == "
                b = dp[i][j-1] + 1
            else:
                b = dp[i][j-1]
        if a != 100000 or b != 100000:
            dp[i][j] = min([a, b])
print(int(dp[H-1][W-1]))

Solution (Python):
import numpy as np

H, W = map(int, input().split())
temp = [list(input().replace("
masu = [[int(temp[i][j]) for j in range(W)] for i in range(H)]

dp = np.zeros((H, W))
if masu[0][0] == 0:
    dp[0][0] = 1

for i in range(0,H):
    for j in range(0,W):
        if i == 0:
            a = 100000
        else:
            if masu[i][j] == 0 and masu[i-1][j] == 1:
                a = dp[i-1][j] + 1
            else:
                a = dp[i-1][j]
        if j == 0:
            b = 100000
        else:
            if masu[i][j] == 0 and masu[i][j-1] == 1:
                b = dp[i][j-1] + 1
            else:
                b = dp[i][j-1]
        if a != 100000 or b != 100000:
            dp[i][j] = min([a, b])
print(int(dp[H-1][W-1]))

Solution (Python):
H,W = (int(x) for x in input().split())
lines = [input() for i in range(H)]
dp = [[0] * W for _ in range(H)]
if lines[0][0] == "
    dp[0][0] = 1
q = r = dp[0][0]
for i in range(H):
    for j in range(W):
        if i == j == 0: continue
        if j > 0:
            q = dp[i][j-1]
            if lines[i][j] == "
                q = dp[i][j-1] + 1
        if i > 0:
            r = dp[i-1][j]
            if lines[i][j] == "
                r = dp[i-1][j] + 1
        if j == 0: 
            dp[i][j] = r
        elif i == 0:
            dp[i][j] = q
        else:
            dp[i][j] = min(q,r)
print(dp[H-1][W-1])

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

dist = [[10**7] * W for _ in range(H)]
dist[0][0] = 0

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

if S[0][0] == '
    dist[H-1][W-1] += 1
print(dist[H-1][W-1])

Solution (Python):
import collections
from collections import deque

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


for i in range(h):
    s[i]=['
s=[['

dp=[[0]*(w+1) for i in range(h+1)]

for i in range(w+1):
    dp[0][i]+=1
for i in range(h+1):
    dp[i][0]+=1


for i in range(1,h+1):
    for j in range(1,w+1):
        if i==1 and j==1:
            if s[i][j]=='
                dp[i][j]+=1

        elif i==1:
            if s[i][j]=='
                dp[i][j]+=dp[i][j-1]+1
            else:
                dp[i][j]=dp[i][j-1]
        elif j==1:
            if s[i][j]=='
                dp[i][j]=dp[i-1][j]+1
            else:
                dp[i][j]=dp[i-1][j]

        elif dp[i-1][j]==dp[i][j-1]:
            if s[i][j]=='
                dp[i][j]=dp[i-1][j]+1
            else:
                dp[i][j]=dp[i-1][j]

        elif dp[i-1][j]<dp[i][j-1]:
            if s[i][j]=='
                dp[i][j]=dp[i-1][j]+1
            else:
                dp[i][j]=dp[i-1][j]
        else:
            if s[i][j]=='
                dp[i][j]=dp[i][j-1]+1
            else:
                dp[i][j]=dp[i][j-1]




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

Solution (Python):
import sys

sys.setrecursionlimit(10 ** 6)
int1 = lambda x: int(x) - 1
p2D = lambda x: print(*x, sep="\n")
def II(): return int(sys.stdin.readline())
def MI(): return map(int, sys.stdin.readline().split())
def LI(): return list(map(int, sys.stdin.readline().split()))
def LLI(rows_number): return [LI() for _ in range(rows_number)]
def SI(): return sys.stdin.readline()[:-1]

def main():
    inf=10**9
    h,w=MI()
    ss=[SI() for _ in range(h)]
    cc=[[0]*w for _ in range(h)]
    if ss[0][0]=="
    for i in range(h):
        for j in range(w):
            if (i,j)==(0,0):continue
            u=l=inf
            if i-1>=0:
                u=cc[i-1][j]
                if ss[i][j]=="
            if j-1>=0:
                l=cc[i][j-1]
                if ss[i][j]=="
            cc[i][j]=min(u,l)
    print(cc[h-1][w-1])

main()

Solution (Python):
from heapq import heappop, heappush

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

def dijkstra(graph, n, s):
    d = [float("inf")] * n
    d[s] = 0
    q = []
    heappush(q, (0, s))
    while q:
        dist, v = heappop(q)
        if d[v] < dist: continue
        for nv, cost in graph[v]:
            if d[nv] > d[v] + cost:
                d[nv] = d[v] + cost
                heappush(q, (d[nv], nv))
    return d

n = h*w+1
g = [list() for _ in range(n)]
for i in range(h):
    for j in range(w-1):
        cid = i*w + j
        g[cid].append((cid+1, int(s[i][j] == "." and s[i][j+1] == "
for i in range(h-1):
    for j in range(w):
        cid = i*w + j
        g[cid].append((cid+w, int(s[i][j] == "." and s[i+1][j] == "
g[n-1].append((0, int(s[0][0] == "

print(dijkstra(g, n, n-1)[n-2])

Solution (Python):

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

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

for h in range(1,H):
  if S[h-1][0] == '
    grid[h][0] = grid[h-1][0] + 1
  else:
    grid[h][0] = grid[h-1][0]
    
for w in range(1,W):
  if S[0][w-1] == '
    grid[0][w] = grid[0][w-1] + 1
  else:
    grid[0][w] = grid[0][w-1]
for w in range(1,W):
  for h in range(1,H):
    if S[h-1][w] == '
      next_h = grid[h-1][w] + 1
    else:
      next_h = grid[h-1][w]      
    if S[h][w-1] == '
      next_w = grid[h][w-1] + 1
    else:
      next_w = grid[h][w-1]
    grid[h][w] = min([next_w, next_h])
if S[H-1][W-1] == '
  grid[H-1][W-1] += 1
print(grid[H-1][W-1])

Solution (Python):
import collections

h,w=map(int,input().split())
board=[list(input()) for _ in range(h)]
q=collections.deque()
if board[0][0]=='
  q.append((0,0,1,1))
else:
  q.append((0,0,0,0))
dp=[[10**18]*w for _ in range(h)]
ans=10**18
while len(q)!=0:
  x,y,cnt,flag=q.popleft()
  if x==w-1 and y==h-1:
    ans=min(ans,cnt)
  else:
    if x!=w-1:
      if flag==0:
        if board[y][x+1]=='
          if dp[y][x+1]>cnt+1:
            q.append((x+1,y,cnt+1,1))
            dp[y][x+1]=cnt+1
        else:
          if dp[y][x+1]>cnt:
            q.append((x+1,y,cnt,0))
            dp[y][x+1]=cnt
      else:
        if board[y][x+1]=='
          if dp[y][x+1]>cnt:
            q.append((x+1,y,cnt,1))
            dp[y][x+1]=cnt
        else:
          if dp[y][x+1]>cnt:
            q.append((x+1,y,cnt,0))
            dp[y][x+1]=cnt
    if y!=h-1:
      if flag==0:
        if board[y+1][x]=='
          if dp[y+1][x]>cnt+1:
            q.append((x,y+1,cnt+1,1))
            dp[y+1][x]=cnt+1
        else:
          if dp[y+1][x]>cnt:
            q.append((x,y+1,cnt,0))
            dp[y+1][x]=cnt
      else:
        if board[y+1][x]=='
          if dp[y+1][x]>cnt:
            q.append((x,y+1,cnt,1))
            dp[y+1][x]=cnt
        else:
          if dp[y+1][x]>cnt:
            q.append((x,y+1,cnt,0))
            dp[y+1][x]=cnt
print(dp[-1][-1])

Solution (Python):
import sys
from heapq import heapify, heappush, heappop

read = sys.stdin.read
readline = sys.stdin.readline

H, W = map(int, readline().split())
s = tuple(map(str, read().split()))
INF = 10 ** 10
grid = [[INF] * W for _ in range(H)]
if s[0][0] == '
    start = (1, (0, 0))
else:
    start = (0, (0, 0))
heap = [start]
heapify(heap)
while heap:
    d, (x, y) = heappop(heap)
    if grid[x][y] != INF:
        continue
    grid[x][y] = d
    for i, j in ((0, 1), (1, 0)):
        new_x = x + i
        new_y = y + j
        if new_x == H or new_y == W:
            continue
        if grid[new_x][new_y] <= d:
            continue
        if s[x][y] == '.' and s[new_x][new_y] == '
            heappush(heap, (d + 1, (new_x, new_y)))
        else:
            heappush(heap, (d, (new_x, new_y)))

print(grid[-1][-1])

Solution (Python):
import sys
from heapq import heapify, heappush, heappop

read = sys.stdin.read
readline = sys.stdin.readline

H, W = map(int, readline().split())
s = tuple(map(str, read().split()))
INF = 10 ** 10
grid = [[INF] * W for _ in range(H)]
if s[0][0] == '
    grid[0][0] = 1
else:
    grid[0][0] = 0
start = (grid[0][0], (0, 0))
heap = [start]
heapify(heap)
while heap:
    d, (x, y) = heappop(heap)
    for i, j in ((0, 1), (1, 0)):
        new_x = x + i
        new_y = y + j
        if new_x == H or new_y == W:
            continue
        if grid[new_x][new_y] <= d:
            continue
        if s[x][y] == '.' and s[new_x][new_y] == '
            grid[new_x][new_y] = d + 1
            heappush(heap, (d + 1, (new_x, new_y)))
        else:
            grid[new_x][new_y] = d
            heappush(heap, (d, (new_x, new_y)))

print(grid[-1][-1])

Solution (Python):
import sys
from collections import deque

read = sys.stdin.read
readline = sys.stdin.readline

H, W = map(int, readline().split())
s = tuple(map(str, read().split()))
INF = 10 ** 10
grid = [[INF] * W for _ in range(H)]
start = (0, 0)
queue = deque([start])
grid[0][0] = 0
while queue:
    x, y = queue.pop()
    for i, j in ((0, 1), (1, 0)):
        new_x = x + i
        new_y = y + j
        if new_x >= H or new_y >= W:
            continue
        else:
            if s[x][y] == '.' and s[new_x][new_y] == '
                cnt = grid[x][y] + 1
                if grid[new_x][new_y] > cnt:
                    grid[new_x][new_y] = cnt
                    queue.append((new_x, new_y))
            else:
                if grid[new_x][new_y] > grid[x][y]:
                    grid[new_x][new_y] = grid[x][y]
                    queue.append((new_x, new_y))

answer = grid[H - 1][W - 1]
if s[0][0] == '
    answer += 1
print(answer)

Solution (Python):
H,W=map(int,input().split())
s=[]
count=[[10**9 for _ in range(W)] for i in range(H)]
for i in range(H):
    S=input()
    s.append(S)
if s[0][0]=="
    count[0][0]=1
else:
    count[0][0]=0
for i in range(H):
    for j in range(W):
        if i==0 and j==0:
            continue
        val1=10**9
        val2=10**9
        if i==0:
            pass
        else:
            val1=count[i-1][j]
            if s[i][j]=="
                val1+=1
        if j==0:
            pass
        else:
            val2=count[i][j-1]
            if s[i][j]=="
                val2+=1
        count[i][j]=min(val1,val2)
print(count[-1][-1])

Solution (Python):
INF = int(1e9) + 7
h, w = map(int, input().split())
s = []
for i in range(h):
    s.append(list(input()))

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


for i in range(h):
    for j in range(w):
        if i == 0 and j == 0:
            continue
        val1 = dp[i-1][j]
        if s[i][j] == '
            val1 += 1
        val2 = dp[i][j-1]
        if s[i][j] == '
            val2 += 1
        dp[i][j] = min(val1, val2)
        
print(dp[h-1][w-1])

Solution (Python):
h, w = map(int, input().split())
s = []
score = [[0] * w for i in range(h)]
for i in range(h):
  s.append(list(input()))
  for j in range(w):
    if i == 0:
      if j == 0:
        score[0][0] = 1 if s[0][0] == '
      else:
        score[0][j] = score[0][j-1]
        if s[0][j] == '
          score[0][j] += 1
    else:
      if j == 0:
        score[i][0] = score[i-1][0]
        if s[i][0] == '
          score[i][0] += 1
      else:
        r = score[i][j-1]
        if s[i][j] == '
          r += 1
        d = score[i-1][j]
        if s[i][j] == '
          d += 1
        score[i][j] += min(r, d)
print(score[-1][-1])

Solution (Python):
from collections import deque

def solve():
    H, W = map(int, input().split())
    A = [list(input()) for _ in range(H)]
    INF = 10 ** 9
    d = [[INF] * W for i in range(H)]
    d[0][0] = 1 if A[0][0] == '

    prepare = 1 if A[0][0] == '
    q = deque([(prepare, 0, 0)])
    while q:
        c, x, y = q.popleft()
        for a, b in [(1,0), (0,1)]:
            nx, ny = x+a, y+b
            if nx >= W or ny >= H: continue
            k = 1 if A[y][x] != A[ny][nx] else 0
            if c+k >= d[ny][nx]: continue
            d[ny][nx] = c+k
            q.append((c+k, nx, ny))

    return (d[H-1][W-1]+1)//2

print(solve())

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

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

if grid[0][0] == "
    ans[0][0] = 1

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

        r = H*W
        d = H*W
        if j > 0 and grid[i][j] != grid[i][j-1] and grid[i][j-1] == ".":
            r = 1 + ans[i][j-1]
        elif j > 0:
            r = ans[i][j-1]

        if i > 0 and grid[i][j] != grid[i-1][j] and grid[i-1][j] == ".":
            d = 1 + ans[i-1][j]
        elif i > 0:
            d = ans[i-1][j]
        ans[i][j] = min(r, d)

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

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

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

if S[0][0] == '.':
    DP[0][0] = 0
else:
    DP[0][0] = 1

ren = False
if DP[0][0] == 1:
    ren = True

for i in range(1,h):
    if S[i][0] == '.':
        DP[i][0] = DP[i-1][0]
        ren = False
    elif ren == False and S[i][0] == '
        DP[i][0] = DP[i-1][0] + 1
        ren = True
    elif ren == True and S[i][0] == '
        DP[i][0] = DP[i-1][0]
        ren = True

ren = False
if DP[0][0] == 1:
    ren = True
for j in range(1,w):
    if S[0][j] == '.':
        DP[0][j] = DP[0][j-1]
        ren = False
    elif ren == False and S[0][j] == '
        DP[0][j] = DP[0][j-1] + 1
        ren = True
    elif ren == True and S[0][j] == '
        DP[0][j] = DP[0][j-1]
        ren = True

for i in range(1,h):
    for j in range(1,w):
        if S[i][j] == '.':
            DP[i][j] = min(DP[i-1][j], DP[i][j-1])
        elif S[i][j] == '
            res_i = 0
            res_j = 0
            if S[i-1][j] == '.':
                res_i = 1
            if S[i][j-1] == '.':
                res_j = 1
            DP[i][j] = min(DP[i-1][j] + res_i, DP[i][j-1] + res_j)

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

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

inf = 10**18
dp = [[inf] * W for _ in range(H)]
if grid[0][0] == "
    dp[0][0] = 1
else:
    dp[0][0] = 0

for i in range(H):
    for j in range(W):
        if i != 0:
            tmp = dp[i - 1][j] + int(grid[i][j]=="
            dp[i][j] = min(dp[i][j], tmp)
        if j != 0:
            tmp = dp[i][j - 1] + int(grid[i][j]=="
            dp[i][j] = min(dp[i][j], tmp)

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

Solution (Python):
h, w = map(int, input().split())
s_list = []  
dp_dict = {}
for i in range(h):
    s = input()
    temp_list = []
    for temp in s:
        if temp == "
            temp_list.append(1)
        else:
            temp_list.append(0)
    s_list.append(temp_list)


def search(x, y, black):
    res = 0
    if (x, y, black) in dp_dict:
        return dp_dict[(x, y, black)]
    if x == w-1 and y == h-1:
        if s_list[y][x] == 1:
            if black:
                res = 0
            else:
                res = 1
        else:
            res = 0
    elif x == w-1:
        if s_list[y][x] == 1:
            if black:
                res = search(x, y+1, True)
            else:
                res = search(x, y+1, True)+1
        else:
            res = search(x, y+1, False)
    elif y == h-1:
        if s_list[y][x] == 1:
            if black:
                res = search(x+1, y, True)
            else:
                res = search(x+1, y, True)+1
        else:
            res = search(x+1, y, False)
    else:
        if s_list[y][x] == 1:
            if black:
                res = min([search(x+1, y, True), search(x, y+1, True)])
            else:
                res = min([search(x+1, y, True), search(x, y+1, True)])+1
        else:
            res = min([search(x+1, y, False), search(x, y+1, False)])
    dp_dict[(x, y, black)] = res
    return res


print(search(0, 0, False))