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):
from collections import deque

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

def bfs(maze,visited,gx,gy):
    stack = deque([[0,0]])
    if maze[0][0] == '
        visited[0][0] = 1 
    else:
        visited[0][0] = 0 
    while stack:
        y,x = stack.pop()
        count = visited[y][x]
        
        for j,k in ([1,0],[0,1]):
            new_y,new_x = y+j,x+k
            if  new_x >= gx or  new_y >= gy:
                continue
            elif maze[new_y][new_x] == "
                visited[new_y][new_x] = count+1
                stack.appendleft([new_y, new_x])
            elif maze[new_y][new_x] == "
                continue
            elif visited[new_y][new_x] > count:
                visited[new_y][new_x] = count
                stack.appendleft([new_y, new_x])
    return visited[gy-1][gx-1]

inf = float('inf')
visited = [[inf]*W for _ in range(H)]
print(bfs(maze,visited,W,H))

Solution (Python):
from heapq import heappush,heappop,heapify
from collections import deque,defaultdict,Counter
from itertools import permutations,combinations,groupby
import sys,bisect,string,math,time,functools,random
def Golf():*a,=map(int,open(0))
def I():return int(input())
def S_():return input()
def IS():return input().split()
def LS():return [i for i in input().split()]
def LI():return [int(i) for i in input().split()]
def LI_():return [int(i)-1 for i in input().split()]
def NI(n):return [int(input()) for i in range(n)]
def NI_(n):return [int(input())-1 for i in range(n)]
def StoLI():return [ord(i)-97 for i in input()]
def ItoS(n):return chr(n+97)
def LtoS(ls):return ''.join([chr(i+97) for i in ls])
def GI(V,E,Directed=False,index=0):
    org_inp=[];g=[[] for i in range(n)]
    for i in range(E):
        inp=LI();org_inp.append(inp)
        if index==0:inp[0]-=1;inp[1]-=1
        if len(inp)==2:
            a,b=inp;g[a].append(b)
            if not Directed:g[b].append(a)
        elif len(inp)==3:
            a,b,c=inp;aa=(inp[0],inp[2]);bb=(inp[1],inp[2]);g[a].append(bb)
            if not Directed:g[b].append(aa)
    return g,org_inp
def GGI(h,w,search=None,replacement_of_found='.',mp_def={'

    mp=[1]*(w+2);found={}
    for i in range(h):
        s=input()
        for char in search:
            if char in s:
                found[char]=((i+1)*(w+2)+s.index(char)+1)
                mp_def[char]=mp_def[replacement_of_found]
        mp+=[1]+[mp_def[j] for j in s]+[1]
    mp+=[1]*(w+2)
    return h+2,w+2,mp,found
def TI(n):return GI(n,n-1)
def bit_combination(k,n=2):return [[tb//(n**bt)%n for bt in range(k)] for tb in range(n**k)]
def show(*inp,end='\n'):
    if show_flg:print(*inp,end=end)

YN=['YES','NO'];Yn=['Yes','No']
mo=10**9+7
inf=float('inf')
l_alp=string.ascii_lowercase

input=lambda: sys.stdin.readline().rstrip()

def ran_input():
    n=random.randint(4,16)
    rmin,rmax=1,10
    a=[random.randint(rmin,rmax) for _ in range(n)]
    return n,a

show_flg=False
show_flg=True

ans=0

h,w=LI()

h,w,g,sg=GGI(h,w,search=['S','G'],replacement_of_found='.',mp_def={'
dp=[10**6]*(h*w)
dp[1]=0
g[1]=0

for j in range(h*w-h):
    r,c=j//w,j%w
    if j==1 or (1<=r<=h-2 and 1<=c<=w-2):
        pass
    else:
        continue

    dp[j+1]=min(dp[j]+1 if (g[j],g[j+1])==(0,1) else dp[j],dp[j+1])
    dp[j+w]=min(dp[j]+1 if (g[j],g[j+w])==(0,1) else dp[j],dp[j+w])


print(dp[(h-2)*w+w-2])

Solution (Python):
H,W = map(int,input().split(' '))
move_list = [ list(input()) for _ in range(H) ]
possible_list = [[10**9]*W  for _ in range(H)]

def dfs(x,y,score,is_sequence):
    if x < 0 or H <= x or y < 0 or W <= y: 
        return
    if is_sequence == False and move_list[x][y] == '
        score +=1
        is_sequence = True
    elif move_list[x][y] == '.':
        is_sequence = False
    if possible_list[x][y] <= score:
        return
    possible_list[x][y] = score
    dfs(x+1,y,score,is_sequence)
    dfs(x,y+1,score,is_sequence)
dfs(0,0,0,False)

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

Solution (Python):
from collections import deque

H, W = map(int,input().split())
S = [input() for i in range(H)]
dp = [[0 for _ in range(W)] for _ in range(H)]
dp[0][0] = 1 if S[0][0] == "
for i in range(1, H):
    if S[i][0] == "
        if S[i-1][0] == "
            dp[i][0] =  dp[i-1][0]
        else:
             dp[i][0] = dp[i-1][0] + 1
    else:
        dp[i][0] =  dp[i-1][0]

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

for i in range(1,H):
    for j in range(1,W):
        up = dp[i-1][j] + (1 if S[i-1][j] != "
        left = dp[i][j-1] + (1 if S[i][j-1] != "
        dp[i][j] = min(up, left)
print(dp[-1][-1])

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

STEPS = [
    (0, 1),
    (1, 0)
]
BLACK = '
WHITE = '.'
CHECKED = 't'
INF = float('INF')

def main():
    H, W = map(int, input().split())
    board = [list(input().strip()) for _ in range(H)]
    scores = [[INF] * W for _ in range(H)]


    if board[0][0] == WHITE:
        scores[0][0] = 0
    else:
        scores[0][0] = 1

    que = deque([[0, 0, board[0][0]]])


    while que:
        y, x, color = que.popleft()
        score = scores[y][x]

        for (i,j) in STEPS:
            ny, nx = y + i, x + j
            if ny >= H or nx >= W:
                continue

            target = board[ny][nx]
            n_score = score

            if color == WHITE and target == BLACK:
                n_score += 1

            if n_score < scores[ny][nx]:
                scores[ny][nx] = n_score
                que.append([ny, nx, target])

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


if __name__ == "__main__":
    main()

Solution (Python):
def main():
    import collections
    H, W = map(int, input().split())
    s = [list(input()) for i in range(H)]
    t = [[0]*W for i in range(H)]
    if s[0][0] == "
        t[0][0] = 1

    for i in range(1, W):
        t[0][i] = t[0][i-1]
        if s[0][i] == "
            t[0][i] += 1
    for i in range(1, H):
        t[i][0] = t[i-1][0]
        if s[i][0] == "
            t[i][0] += 1

    for i in range(1, H):
        for j in range(1, W):
            k = 0
            l = 0
            if s[i][j] == "
                if s[i-1][j] != "
                    k += 1
                if s[i][j-1] != "
                    l += 1
            t[i][j] = min(t[i-1][j] + k, t[i][j-1]+l)

    print(t[-1][-1])


main()

Solution (Python):
from heapq import heappush,heappop,heapify
from collections import deque,defaultdict,Counter
from itertools import permutations,combinations,groupby
import sys,bisect,string,math,time,functools,random
def Golf():*a,=map(int,open(0))
def I():return int(input())
def S_():return input()
def IS():return input().split()
def LS():return [i for i in input().split()]
def LI():return [int(i) for i in input().split()]
def LI_():return [int(i)-1 for i in input().split()]
def NI(n):return [int(input()) for i in range(n)]
def NI_(n):return [int(input())-1 for i in range(n)]
def StoLI():return [ord(i)-97 for i in input()]
def ItoS(n):return chr(n+97)
def LtoS(ls):return ''.join([chr(i+97) for i in ls])
def GI(V,E,Directed=False,index=0):
    org_inp=[];g=[[] for i in range(n)]
    for i in range(E):
        inp=LI();org_inp.append(inp)
        if index==0:inp[0]-=1;inp[1]-=1
        if len(inp)==2:
            a,b=inp;g[a].append(b)
            if not Directed:g[b].append(a)
        elif len(inp)==3:
            a,b,c=inp;aa=(inp[0],inp[2]);bb=(inp[1],inp[2]);g[a].append(bb)
            if not Directed:g[b].append(aa)
    return g,org_inp
def GGI(h,w,search=None,replacement_of_found='.',mp_def={'

    mp=[1]*(w+2);found={}
    for i in range(h):
        s=input()
        for char in search:
            if char in s:
                found[char]=((i+1)*(w+2)+s.index(char)+1)
                mp_def[char]=mp_def[replacement_of_found]
        mp+=[1]+[mp_def[j] for j in s]+[1]
    mp+=[1]*(w+2)
    return h+2,w+2,mp,found
def TI(n):return GI(n,n-1)
def bit_combination(k,n=2):return [[tb//(n**bt)%n for bt in range(k)] for tb in range(n**k)]
def show(*inp,end='\n'):
    if show_flg:print(*inp,end=end)

YN=['YES','NO'];Yn=['Yes','No']
mo=10**9+7
inf=float('inf')
l_alp=string.ascii_lowercase

input=lambda: sys.stdin.readline().rstrip()

def ran_input():
    n=random.randint(4,16)
    rmin,rmax=1,10
    a=[random.randint(rmin,rmax) for _ in range(n)]
    return n,a

show_flg=False
show_flg=True

ans=0

h,w=LI()

h,w,g,sg=GGI(h,w,search=['S','G'],replacement_of_found='.',mp_def={'



dp=[10**6]*(h*w)

dp[1]=0
g[1]=0

'''
for i in range(h):
    show(g[i*w:(i+1)*w])
'''

for j in range(h*w-h):
    r,c=j//w,j%w
    
    if 1<=r<=h-2 and 1<=c<=w-2:
        pass
    else:
        if j==1:
            pass
        else:
            continue
    
    
    
    dp[j+1]=min(dp[j]+1 if (g[j],g[j+1])==(0,1) else dp[j],dp[j+1])
    dp[j+w]=min(dp[j]+1 if (g[j],g[j+w])==(0,1) else dp[j],dp[j+w])


print(dp[(h-2)*w+w-2])

Solution (Python):
H,W=map(int,input().split())
S=[input() for i in range(H)]
from collections import deque
q=deque([(0,0,0)])
v=[[-1]*W for i in range(H)]
v[0][0]=0
x=[(0,1),(1,0)]
while q:
    i,j,d=q.popleft()
    for a,b in x:
        if 0<=i+a<H and 0<=j+b<W and v[i+a][j+b]<0:
            if S[i+a][j+b]==S[i][j]:
                q.appendleft((i+a,j+b,d))
                v[i+a][j+b]=d
            else:
                q.append((i+a,j+b,d+1))
                v[i+a][j+b]=d+1
print(v[-1][-1]//2+(S[0][0]=='

Solution (Python):
H,W = map(int,input().split())
INF = 10000000000
grid = [["." for _ in range(W+1)]]
for _ in range(H):
    in_list = list("." + input())
    grid.append(in_list)

dp = [[INF for _ in range(W+1)] for _ in range(H+1)]
dp[1][0] = 0
dp[0][1] = 0

for j in range(1,W+1):
    for i in range(1,H+1):
        if grid[i][j] == ".": 
            dp[i][j] = min(dp[i-1][j],dp[i][j-1])
        else: 
            if grid[i-1][j] == "
                route_top = dp[i-1][j]
            else:
                route_top = dp[i-1][j] + 1
            if grid[i][j-1] == "
                route_left = dp[i][j-1]
            else:
                route_left = dp[i][j-1] + 1
            dp[i][j] = min(route_top,route_left)
print(dp[-1][-1])

Solution (Python):
def main():
    h,w = map(int, input().split())
    s = []
    for i in range(h):
        ss = list(input())
        s.append(ss)

    now = [0,0]
    cnt = 0
    if s[0][0] == '
        cnt += 1
        
    

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

    for i in range(h):
        for j in range(w):
            tmp_up = 100000
            tmp_left = 100000
            change  = 0
            if s[i][j] == '
                change = 1
            if i == 0 and j == 0:
                continue
            if i != 0:
                if s[i-1][j] == '
                    tmp_up = dp[i-1][j]
                else:
                    tmp_up = dp[i-1][j] + change
            if j != 0:
                if s[i][j-1] == '
                    tmp_left = dp[i][j-1]
                else:

                    tmp_left = dp[i][j-1] + change

            dp[i][j] = min(tmp_up,tmp_left)


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

if __name__ == '__main__':
    main()

Solution (Python):
import sys

h, w = map(int, sys.stdin.readline().split())
grid = [sys.stdin.readline().rstrip() for _ in range(h)]

def main():
    cost = [[0] * w for _ in range(h)]
    cost[0][0] = 1 if grid[0][0] == '
    for j in range(1, w):
        cost[0][j] = cost[0][j-1]
        if grid[0][j] == '
            if grid[0][j-1] == '.':
                cost[0][j] += 1
    
    for i in range(1, h):
        cost[i][0] = cost[i-1][0]
        if grid[i][0] == '
            if grid[i-1][0] == '.':
                cost[i][0] += 1
    
    for i in range(1, h):
        for j in range(1, w):
            c1 = cost[i][j-1]
            if grid[i][j] == '
                if grid[i][j-1] == '.':
                    c1 += 1
            c2 = cost[i-1][j]
            if grid[i][j] == '
                if grid[i-1][j] == '.':
                    c2 += 1
            
            cost[i][j] = min(c1, c2)
    return cost[h-1][w-1]

if __name__ == "__main__":
    ans = main()
    print(ans)

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

dp = [[0 for _ in range(w)] for _ in range(h)] 
for i in range(h):
    for j in range(w):
        if i==0 and j==0:
            if arr[i][j]=='
                dp[i][j] = 1            
        elif arr[i][j]=='
            if i==0:
                if arr[i][j-1]=='
                    dp[i][j] = dp[i][j-1]
                else:
                    dp[i][j] = dp[i][j-1]+1
            elif j==0:
                if arr[i-1][j]=='
                    dp[i][j] = dp[i-1][j]
                else:
                    dp[i][j] = dp[i-1][j]+1
            else:
                if arr[i][j-1]=='
                    ans1 = dp[i][j-1]
                else:
                    ans1 = dp[i][j-1]+1
                if arr[i-1][j]=='
                    ans2 = dp[i-1][j]
                else:
                    ans2 = dp[i-1][j]+1
                dp[i][j] = min(ans1,ans2)
        else:
            if i==0:
                dp[i][j] = dp[i][j-1]
            elif j==0:
                dp[i][j] = dp[i-1][j]
            else:
                dp[i][j] = min(dp[i][j-1],dp[i-1][j])
print(dp[-1][-1])

Solution (Python):
from collections import deque
from math import ceil
H, W = [int(i) for i in input().split()]
s = [input() for _ in range(H)]

dq = deque()
D = [[999999999999]*W for _ in range(H)]
if s[0][0] == '.':
    D[0][0] = 0
else:
    D[0][0] = 1
dq.append((0, 0, s[0][0]))

while len(dq):
    h, w, m = dq.popleft()
    d = D[h][w]

    for nh, nw in ((h+1, w), (h, w+1)):
        if nh < H and nw < W:
            if D[nh][nw] == 999999999999:
                dq.append((nh, nw, s[nh][nw]))
            if s[nh][nw] != m:
                D[nh][nw] = min(D[nh][nw], d+1)
            else:
                D[nh][nw] = min(D[nh][nw], d)

print(ceil(D[-1][-1]/2))

Solution (Python):

import bisect
import heapq
import math
import random
import sys
from collections import Counter, defaultdict, deque
from decimal import ROUND_CEILING, ROUND_HALF_UP, Decimal
from functools import lru_cache, reduce
from itertools import combinations, combinations_with_replacement, product, permutations
from operator import add, mul, sub

sys.setrecursionlimit(100000)
input = sys.stdin.readline
INF = 2**62-1

def read_int():
    return int(input())


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


def read_float():
    return float(input())


def read_float_n():
    return list(map(float, input().split()))


def read_str():
    return input().strip()


def read_str_n():
    return list(map(str, input().split()))


def error_print(*args):
    print(*args, file=sys.stderr)


def mt(f):
    import time

    def wrap(*args, **kwargs):
        s = time.time()
        ret = f(*args, **kwargs)
        e = time.time()

        error_print(e - s, 'sec')
        return ret

    return wrap


def BellmanFord(g, s):
    V = list(g.keys())
    for v in g.values():
        V.extend(list(v.keys()))
    V = set(V)

    dist = defaultdict(lambda: sys.maxsize)
    pred = defaultdict(lambda: -1)

    dist[s] = 0

    N = len(V)
    for i in range(N+1):
        for u in g:
            for v in g[u]:
                if dist[v] > dist[u] + g[u][v]:
                    if i == N:
                        return 'inf'
                    dist[v] = dist[u] + g[u][v]
                    pred[v] = u
    return dist



@mt
def slv(H, W, S):
    g = defaultdict(dict)
    for i in range(H):
        for j in range(W):
            for x, y in ((0, 1), (1, 0)):
                if 0 <= i + x < H and 0 <= j+y < W:
                    if S[i][j] == '.' and S[i+x][j+y] == '
                        c = 1
                    else:
                        c = 0
                    g[(i, j)][(i+x, j+y)] = c
    g[0][(0, 0)] = 1 if S[0][0] == '

    def bfs(s=0):
        q = deque()
        q.append(s)
        d = defaultdict(lambda: sys.maxsize)
        d[s] = 0
        while q:
            u = q.popleft()
            for v, c in g[u].items():
                if d[u] + c < d[v]:
                    d[v] = d[u] + c
                    if c == 0:
                        q.appendleft(v)
                    else:
                        q.append(v)

        return d

    return bfs()[(H-1, W-1)]


def main():
    H, W = read_int_n()
    S = [read_str() for _ in range(H)]
    print(slv(H, W, S))

    
    
    
    


if __name__ == '__main__':
    main()

Solution (Python):
from collections import deque
h,w = map(int,input().split())
s = []
for i in range(h):
    s0 = list(input())
    s.append(s0)
d = deque()
rl = [[h*w+1 for i in range(w)] for i in range(h)]
if s[0][0] == ".":
    d.append([0,0,0])
    rl[0][0] = 0
else:
    d.append([0,0,1])
    rl[0][0] = 1
while len(d):
    a,b,c = d.popleft()
    
    if a == h-1:
        if b < w-1:
            if rl[a][b+1] == h*w+1:
                if s[a][b+1] == "
                    if c > 0:
                        rl[a][b+1] = rl[a][b]
                        d.append([a,b+1,1])
                    else:
                        rl[a][b+1] = rl[a][b]+1
                        d.append([a,b+1,0])
                else:
                    rl[a][b+1] = rl[a][b]
                    d.append([a,b+1,0])
            else:
                if s[a][b+1] == "
                    if c > 0:
                        rl[a][b+1]= min(rl[a][b+1],rl[a][b])
                    else:
                        rl[a][b+1]= min(rl[a][b+1],rl[a][b]+1)
                else:
                    rl[a][b+1] = min(rl[a][b+1],rl[a][b])
    else:
        if b == w-1:
            if rl[a+1][b] == h*w+1:
                if s[a+1][b] == "
                    if c > 0:
                        rl[a+1][b] = rl[a][b]
                        d.append([a+1,b,1])
                    else:
                        rl[a+1][b] = rl[a][b]+1
                        d.append([a+1,b,1])
                else:
                    rl[a+1][b] = rl[a][b]
                    d.append([a+1,b,0])
            else:
                if s[a+1][b] == "
                    if c > 0:
                        rl[a+1][b]= min(rl[a+1][b],rl[a][b])
                    else:
                        rl[a+1][b]= min(rl[a+1][b],rl[a][b] + 1)
                else:
                    rl[a+1][b] = min(rl[a+1][b],rl[a][b])
        else:
            if rl[a][b+1] == h*w+1:
                if s[a][b+1] == "
                    if c > 0:
                        rl[a][b+1] = rl[a][b]
                        d.append([a,b+1,1])
                    else:
                        rl[a][b+1] = rl[a][b]+1
                        d.append([a,b+1,0])
                else:
                    rl[a][b+1] = rl[a][b]
                    d.append([a,b+1,0])
            else:
                if s[a][b+1] == "
                    if c > 0:
                        rl[a][b+1]= min(rl[a][b+1],rl[a][b])
                    else:
                        rl[a][b+1]= min(rl[a][b+1],rl[a][b]+1)
                else:
                    rl[a][b+1] = min(rl[a][b+1],rl[a][b])
            if rl[a+1][b] == h*w+1:
                if s[a+1][b] == "
                    if c > 0:
                        rl[a+1][b] = rl[a][b]
                        d.append([a+1,b,1])
                    else:
                        rl[a+1][b] = rl[a][b]+1
                        d.append([a+1,b,1])
                else:
                    rl[a+1][b] = rl[a][b]
                    d.append([a+1,b,0])
            else:
                if s[a+1][b] == "
                    if c > 0:
                        rl[a+1][b]= min(rl[a+1][b],rl[a][b])
                    else:
                        rl[a+1][b]= min(rl[a+1][b],rl[a][b] + 1)
                else:
                    rl[a+1][b] = min(rl[a+1][b],rl[a][b])
print(rl[h-1][w-1])

Solution (Python):
H,W=map(int,input().split())
A=[]
for i in range(H):
  d=list(input())
  A.append(d)
D=[[1000]*W for i in range(H)]
if A[0][0]=='.':
  D[0][0]=0
else:
  D[0][0]=1
cnt=D[0][0]
for i in range(1,W):
  if A[0][i]==A[0][i-1]:
    D[0][i]=D[0][i-1]
  else:
    D[0][i]=D[0][i-1]+1
for i in range(1,H):
  if A[i][0]==A[i-1][0]:
    D[i][0]=D[i-1][0]
  else:
    D[i][0]=D[i-1][0]+1
for i in range(1,H):
  for j in range(1,W):
    if A[i][j]==A[i-1][j]:
      a=D[i-1][j]
    else:
      a=D[i-1][j]+1
      
    if A[i][j]==A[i][j-1]:
      b=D[i][j-1]
    else:
      b=D[i][j-1]+1
    D[i][j]=min(a,b) 
e=D[-1][-1]
if e%2==0:
  print(e//2)
else:
  print((e+1)//2)

Solution (Python):

from __future__ import division, print_function

import os
import sys
from io import BytesIO, IOBase

if sys.version_info[0] < 3:
    from __builtin__ import xrange as range
    from future_builtins import ascii, filter, hex, map, oct, zip


def main():
    h, w = [int(s) for s in input().strip().split()]
    grid = [input().strip() for _ in range(h)]
    dp = [[0] * w for _ in range(h)]
    dp[0][0] = 1 if grid[0][0] == "
    for i in range(1, h):
        dp[i][0] = dp[i - 1][0] + (grid[i - 1][0] == "." and grid[i][0] == "
    for j in range(1, w):
        dp[0][j] = dp[0][j - 1] + (grid[0][j - 1] == "." and grid[0][j] == "
    for i in range(1, h):
        for j in range(1, w):
            dp[i][j] = min(
                dp[i - 1][j] + (grid[i - 1][j] == "." and grid[i][j] == "
                dp[i][j - 1] + (grid[i][j - 1] == "." and grid[i][j] == "
            )
    result = dp[-1][-1]
    print(result)




BUFSIZE = 8192


class FastIO(IOBase):
    newlines = 0

    def __init__(self, file):
        self._fd = file.fileno()
        self.buffer = BytesIO()
        self.writable = "x" in file.mode or "r" not in file.mode
        self.write = self.buffer.write if self.writable else None

    def read(self):
        while True:
            b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
            if not b:
                break
            ptr = self.buffer.tell()
            self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr)
        self.newlines = 0
        return self.buffer.read()

    def readline(self):
        while self.newlines == 0:
            b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
            self.newlines = b.count(b"\n") + (not b)
            ptr = self.buffer.tell()
            self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr)
        self.newlines -= 1
        return self.buffer.readline()

    def flush(self):
        if self.writable:
            os.write(self._fd, self.buffer.getvalue())
            self.buffer.truncate(0), self.buffer.seek(0)


class IOWrapper(IOBase):
    def __init__(self, file):
        self.buffer = FastIO(file)
        self.flush = self.buffer.flush
        self.writable = self.buffer.writable
        self.write = lambda s: self.buffer.write(s.encode("ascii"))
        self.read = lambda: self.buffer.read().decode("ascii")
        self.readline = lambda: self.buffer.readline().decode("ascii")


def print(*args, **kwargs):
    """Prints the values to a stream, or to sys.stdout by default."""
    sep, file = kwargs.pop("sep", " "), kwargs.pop("file", sys.stdout)
    at_start = True
    for x in args:
        if not at_start:
            file.write(sep)
        file.write(str(x))
        at_start = False
    file.write(kwargs.pop("end", "\n"))
    if kwargs.pop("flush", False):
        file.flush()


if sys.version_info[0] < 3:
    sys.stdin, sys.stdout = FastIO(sys.stdin), FastIO(sys.stdout)
else:
    sys.stdin, sys.stdout = IOWrapper(sys.stdin), IOWrapper(sys.stdout)

input = lambda: sys.stdin.readline().rstrip("\r\n")



if __name__ == "__main__":
    main()

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


def F(h, w, f):
    if f == -1:
        if S[h][w] == ".":
            return False
        else:
            return True
    if S[h][w] == "
        return False
    else:
        return True


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

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

print((min(dp[H - 1][W - 1]) + 1) // 2)

Solution (Python):
import sys
def input(): return sys.stdin.readline().rstrip()
sys.setrecursionlimit(10 ** 7)

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

INF = 1001001001

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

for r in range(H):
    for c in range(W):
        if r:
            if S[r][c] == '
                dp[r][c] = min(dp[r][c], dp[r-1][c]+1)
            else:
                dp[r][c] = min(dp[r][c], dp[r-1][c])
        if c:
            if S[r][c] == '
                dp[r][c] = min(dp[r][c], dp[r][c-1]+1)
            else:
                dp[r][c] = min(dp[r][c], dp[r][c-1])

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

Solution (Python):
H,W = map(int,input().split())
place = []
for i in range(H):
    S = input()
    place.append(S)
ans_list = []
for i in range(H):
    Z = [0] * W
    ans_list.append(Z)
for i in range(H):
    if i == 0:
        count = 0
        for j in range(W):
            if place[0][j] == "
                if j == 0:
                    count += 1
                else:
                    if place[0][j-1] != "
                        count += 1
            ans_list[0][j] = count
    else:
        for j in range(W):
            chk = 0
            if j == 0 :
                count = ans_list[i-1][j]
            else:
                count = ans_list[i][j-1]
            if place[i][j] == "
                if j == 0:
                    if place[i-1][j] != "
                        count += 1
                else:
                    if place[i][j-1] != "
                        count += 1
            if place[i][j] == "
                if place[i][j] != place[i-1][j]:
                    chk += 1
            ans_list[i][j] = min(count,ans_list[i-1][j]+chk)
print(ans_list[H-1][W-1])

Solution (Python):
import sys

sr = lambda: sys.stdin.readline().rstrip()
ir = lambda: int(sr())
lr = lambda: list(map(int, sr().split()))

from collections import deque

def bfs(sy, sx, gy, gx):
    INF = 10 ** 5
    d = [[INF] * W for _ in range(H)]
    dy = [0, 1]
    dx = [1, 0]
    que = deque()
    que.append((sy, sx))
    d[sy][sx] = 0
    if grid[sy][sx] == '
        d[sy][sx] = 1
    while que:
        y, x = que.popleft()
        if y == gy and x == gx:
            break
        for i in range(2):
            ny = y + dy[i]
            nx = x + dx[i]
            if ny >= H or nx >= W:
                continue
            if grid[y][x] == grid[ny][nx]:
                if d[ny][nx] > d[y][x]:
                    d[ny][nx] = d[y][x]
                    que.append((ny, nx))
            elif grid[y][x] == '
                if d[ny][nx] > d[y][x]:
                    d[ny][nx] = d[y][x]
                    que.append((ny, nx))
            else:
                if d[ny][nx] > d[y][x] + 1:
                    d[ny][nx] = d[y][x] + 1
                    que.append((ny, nx))
    return d[gy][gx]

H, W = lr()
grid = [list(sr()) for _ in range(H)]
answer = bfs(0, 0, H-1, W-1)
print(answer)

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

INF = 10000000000

grid = [["." for _ in range(W+1)]]

for _ in range(H):
    in_list = list("." + input())
    grid.append(in_list)


dp = [[INF for _ in range(W+1)] for _ in range(H+1)]
dp[1][0] = 0
dp[0][1] = 0







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

            
            if grid[i][j-1] == "
                route_left = dp[i][j-1]
            else:
                route_left = dp[i][j-1] + 1
            
            dp[i][j] = min(route_top,route_left)
print(dp[-1][-1])

Solution (Python):
import sys
sys.setrecursionlimit(100000)

h,w=map(int,input().split())
INF=10**10
s_org=[list(input()) for _ in range(h)]
s=[[0]*w for _ in range(h)]
for i in range(h):
  for j in range(w):
    if s_org[i][j]=="
      s[i][j]=1
dp=[[-1]*w for _ in range(h)]
dp[0][0]=s[0][0]
def func(i,j):
  if i<0 or j<0: return INF
  if dp[i][j]!=-1:return dp[i][j]
  a=func(i,j-1)+s[i][j]
  b=func(i-1,j)+s[i][j]
  if s[i][j]==1 and s[i][j-1]==1:
    a-=1
  if s[i][j]==1 and s[i-1][j]==1:
    b-=1
  val=min(a,b)
  
  
  dp[i][j]=val
  return val
print(func(h-1,w-1))