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
import heapq

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

def removeWalls(wallPointH,wallPointW):
  if maze[wallPointH][wallPointW]=="
    changeTo = "."
  elif maze[wallPointH][wallPointW]=="1":
    changeTo = "0"
  if maze[wallPointH][wallPointW]=="
    maze[wallPointH][wallPointW]=changeTo
    if wallPointH+1 <= H-1:
      removeWalls(wallPointH+1,wallPointW)
    if wallPointW+1 <= W-1:
      removeWalls(wallPointH,wallPointW+1)

if maze[0][0]=="
  flag=1
else:
  flag=0
      
que = [[flag,0,0]]
heapq.heapify(que)
count = 0
      
while que:
  qu = heapq.heappop(que)
  if qu[0]==1:
    heapq.heappush(que, qu)
    count += 1
    for q in que:
      q[0]=0
      removeWalls(q[1],q[2])
  else:
    nowH = qu[1]
    nowW = qu[2]
    if nowH==H-1 and nowW==W-1:
      print(count)
      sys.exit()
    else:
      
      if nowH+1 <= H-1:
        if maze[nowH+1][nowW]=="
          maze[nowH+1][nowW]="1"
          heapq.heappush(que, [1,nowH+1,nowW])
        elif maze[nowH+1][nowW]==".":
          maze[nowH+1][nowW]="0"
          heapq.heappush(que, [0,nowH+1,nowW])
      if nowW+1 <= W-1:
        if maze[nowH][nowW+1]=="
          maze[nowH][nowW+1]="1"
          heapq.heappush(que, [1,nowH,nowW+1])
        elif maze[nowH][nowW+1]==".":
          maze[nowH][nowW+1]="0"
          heapq.heappush(que, [0,nowH,nowW+1])

Solution (Python):
import math
from collections import deque
def main():
    h,w = tuple([int(t)for t in input().split()])

    s = [['.']*(w+1)]

    s.extend(([list('.'+input()) for _ in range(h)]))

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

    for i in range(h):
        if s[i+1][1] == '.':
            dp[i+1][1] = dp[i][1]
        else:
            if s[i][1]=='.':
                dp[i+1][1] = dp[i][1]+1
            else:
                dp[i+1][1] = dp[i][1]

    for j in range(w):
        if s[1][j+1] == '.':
            dp[1][j+1] = dp[1][j]
        else:
            if s[1][j]=='.':
                dp[1][j+1] = dp[1][j]+1
            else:
                dp[1][j+1] = dp[1][j]

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

    print(dp[-1][-1])
if __name__ == "__main__":
    main()

Solution (Python):
def update(i,j):

    tmp_A = 200
    tmp_B = 200
    
    if 0 < i < H and j < W:
        if table[i-1][j] == table[i][j]:
            tmp_A = colormap[i-1][j]
        else:
            if table[i-1][j]:
                tmp_A = colormap[i-1][j] + 1
            else:
                tmp_A = colormap[i-1][j]
    if i < H and 0 < j < W:
        if table[i][j-1] == table[i][j]:
            tmp_B = colormap[i][j-1]
        else:
            if table[i][j-1]:
                tmp_B = colormap[i][j-1] + 1
            else:
                tmp_B = colormap[i][j-1]
    
    colormap[i][j] = min(tmp_A, tmp_B)

H, W = map(int, input().split())
table = []
for i in range(H):
    table.append([(True if x == "." else False) for x in list(input())])

colormap = [[0 for _ in range(W)] for _ in range(H)]
colormap[0][0] = 0 if table[0][0] else 1

for i in range(H):
    for j in range(W):
        if not(i == 0 and j ==0):
            update(i, j)
    


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

Solution (Python):
import sys
from collections import deque
sys.setrecursionlimit(1000*1000)

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



dx = [1,0]
dy = [0,1]


def wdfs(h,w,grid,seen,l_b):
  
  if seen[h][w] == False and grid[h][w] == ".":
    seen[h][w] = True
    for i in range(2):
      new_h = h + dy[i]
      new_w = w + dx[i]

      
      if (new_h<0 or new_w <0 or new_h>=H or new_w >= W ):
        continue
      
      elif grid[new_h][new_w] == "
        l_b.append([new_h,new_w])
        continue
      
      elif seen[new_h][new_w] == True:
        continue
      wdfs(new_h,new_w,grid,seen,l_b)  
  
  else:
    l_b.append([h,w])           



def bdfs(h,w,grid,seen,l_w):
  if seen[h][w] == False:
    seen[h][w] = True
    
    for i in range(2):
      new_h = h + dy[i]
      new_w = w + dx[i]

      
      if (new_h<0 or new_w <0 or new_h>=H or new_w >= W ):
        continue
      
      elif grid[new_h][new_w] == ".":
        l_w.append([new_h,new_w])
        continue
      
      elif seen[new_h][new_w] == True:
        continue
      bdfs(new_h,new_w,grid,seen,l_w)  



seen = [ [False for i in range(W)] for i in range(H) ]
cnt = 0
l_w =deque( [[0,0]] )
l_b =deque([])


while seen[H-1][W-1] == False:
  while len(l_w) > 0: 
    w = l_w.popleft()
    wdfs(w[0],w[1],grid,seen,l_b)
  if seen[H-1][W-1] == True:
    break

  cnt = cnt+1

  while len(l_b) > 0: 
    b = l_b.popleft()
    bdfs(b[0],b[1],grid,seen,l_w)
  if seen[H-1][W-1] == True:
    break


print(cnt)

Solution (Python):
import numpy as np

h, w = map(int, input().split())
grid = np.array(['*'*(w+2)] + ['*'+input()+'*' for _ in range(h)] + ['*'*(w+2)])

cnt = np.full((h+3, w+3), h+w, dtype=np.int)
MAX = h + w
for i in range(1, h+2):
    for k in range(1, w+2):
        if i == k == 1:
            cnt[i+1][k+1] = 1 if grid[i][k] == '
        else:
            if grid[i][k] == '
                if grid[i-1][k] == '
                    a = cnt[i][k+1]
                elif grid[i-1][k] == '.':
                    a = cnt[i][k+1] + 1
                else:
                    a = MAX
                if grid[i][k-1] == '
                    b = cnt[i+1][k]
                elif grid[i][k-1] == '.':
                    b = cnt[i+1][k] + 1
                else:
                    b = MAX
                cnt[i+1][k+1] = min(a, b)
            else:
                cnt[i+1][k+1] = min(cnt[i][k+1], cnt[i+1][k])

print(cnt[h+1][w+1])

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

INF = float('inf')
dp = [[[INF, s[h][w]] for w in range(W)] for h in range(H)]

def update_dp_1(c, dp):
  if dp[1] == ".":
    if c == ".":
      res = [dp[0], "."]
    else:  
      res = [dp[0]+1, "
  else:  
    if c == ".":
      res = [dp[0], "."]
    else:  
      res = [dp[0], "
  return res

def update_dp_2(c, dp_a, dp_b):
  a = update_dp_1(c, dp_a)
  b = update_dp_1(c, dp_b)
  if a[0] < b[0]:
    return a
  else:
    return b

if s[0][0] == ".":
  dp[0][0] = [0, "."]
else:  
  dp[0][0] = [1, "

for h in range(H):
  if h != 0:
    dp[h][0] = update_dp_1(dp[h][0][1], dp[h-1][0])
  for w in range(1, W):
    if h == 0:
      dp[h][w] = update_dp_1(dp[h][w][1], dp[h][w-1])
    else:
      dp[h][w] = update_dp_2(dp[h][w][1], dp[h-1][w], dp[h][w-1])

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

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

dp = np.zeros(h * w).reshape(h, w)

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

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














        



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

Solution (Python):

H, W = map(int, input().split())
HW_list = []

for i in range(H):
    HW_list.append(str(input()))

dp = [[H * W] * W] * H

dp[0][0] = 0
for i in range(H):
    for j in range(W):
        if i == 0 and j == 0:
            continue
        if i == 0:
            min_num_h = H * W
        else:
            min_num_h = dp[i - 1][j] + (0 if HW_list[i][j] == HW_list[i - 1][j] else 1)
        if j == 0:
            min_num_w = H * W
        else:
            min_num_w = dp[i][j - 1] + (0 if HW_list[i][j] == HW_list[i][j - 1] else 1)
        dp[i][j] = min(min_num_h, min_num_w)

print(dp[H - 1][W - 1] // 2 + (1 if HW_list[0][0] == "

Solution (Python):
from collections import deque

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


def bfs0(white_cells, black_cells):

    while white_cells:
        h, w = white_cells.popleft()
        if h==0 and w==0 and grid[h][w] == "
            black_cells.append((h, w))
            return black_cells

        for dy, dx in ((1, 0), (0, 1)):
            new_h = h + dy
            new_w = w + dx
            if new_h < 0 or H <= new_h or new_w < 0 or W <= new_w:
                continue
            if grid[new_h][new_w] == ".":
                if (new_h, new_w) not in white_cells:
                    white_cells.append((new_h, new_w))
            else:
                if (new_h, new_w) not in black_cells:
                    black_cells.append((new_h, new_w))
            if new_h == H-1 and new_w == W-1:
                if grid[new_h][new_w] == ".":
                    return 1
                else:
                    return 0

    return black_cells


def bfs1(black_cells, white_cells):

    while black_cells:
        h, w = black_cells.popleft()
        for dy, dx in ((1, 0), (0, 1)):
            new_h = h + dy
            new_w = w + dx
            if new_h < 0 or H <= new_h or new_w < 0 or W <= new_w:
                continue
            if grid[new_h][new_w] == "
                if (new_h, new_w) not in black_cells:
                    black_cells.append((new_h, new_w))
            else:
                if (new_h, new_w) not in white_cells:
                    white_cells.append((new_h, new_w))
            if new_h == H-1 and new_w == W-1:
                if grid[new_h][new_w] == "
                    return 1
                else:
                    return 0

    return white_cells

count = 0
ans = 0

if count == 0:
    white_cells = deque()
    white_cells.append((0, 0))
    black_cells = deque()

while black_cells != 1 and white_cells != 1 and black_cells != 0 and white_cells != 0:
    if count % 2 == 0:
        a = 1
        temp_black_cells = bfs0(white_cells, black_cells)
        black_cells = temp_black_cells
        ans += 1
    else:
        a = 0
        temp_white_cells = bfs1(black_cells, white_cells)
        white_cells = temp_white_cells
    count += 1

if black_cells == 1:
    ans -=1

print(ans)

Solution (Python):
from collections import deque

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

ans = 10**9

visited_list = [[10**9]*W for _ in range(H)]

if C[0][0] == "
    stack = deque([[0, 0, 1]])
    visited_list[0][0] = 1
else:
    stack = deque([[0, 0, 0]])
    visited_list[0][0] = 0

def dfs(town, visited_list, stack):
    global ans
    while len(stack) > 0:
        h, w, cnt = stack.pop()
        if h == H-1 and w == W-1 and ans > cnt:
            ans = cnt
            continue
        for j, k in ([1, 0], [0, 1]):
            new_h, new_w = h+j, w+k
            if new_h < 0 or new_h >= H or new_w < 0 or new_w >= W:
                continue
            if  town[new_h][new_w] != "
                visited_list[new_h][new_w] = cnt
                stack.append([new_h, new_w, cnt])
            elif town[h][w] == "
                visited_list[new_h][new_w] = cnt
                stack.append([new_h, new_w, cnt])
            elif town[new_h][new_w] == "
                visited_list[new_h][new_w] = cnt + 1
                
                stack.append([new_h, new_w, cnt+1])
    return ans

print(dfs(C, visited_list, stack))

Solution (Python):
import copy

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


change_list = copy.deepcopy(root_list)
DP_list = []

for i, line in enumerate(root_list):
    DP_line = []
    str_pt = root_list[i][0]
    if i == 0:
        DP_line.append(0) 
    else:
        if root_list[i-1][0] == line[0]: 
            DP_line.append(DP_list[i-1][0])
        else:
            DP_line.append(DP_list[i-1][0] + 1)

    for j, pt in enumerate(line[1:], 1): 
        if i == 0: 
            if str_pt == pt: 
                DP_line.append(DP_line[j-1]) 
            else:
                DP_line.append(DP_line[j-1] + 1) 
                str_pt = pt
        else: 
            
            if str_pt == pt:
                yoko_pt = DP_line[j-1]
            else:
                yoko_pt = DP_line[j-1] + 1
            
            
            if pt == root_list[i-1][j]:
                tate_pt = DP_list[i-1][j]
            else:
                tate_pt = DP_list[i-1][j] + 1
            
            DP_line.append(min(yoko_pt, tate_pt))
            str_pt = pt

    DP_list.append(DP_line)

result = DP_list[H-1][W-1] // 2

if root_list[0][0] == "
    result += 1
if root_list[H-1][W-1] == "
    result += 1
if  root_list[0][0] == "
    if result == 2 or (H == 1 and W == 1):
        result = 1
    else:
        result -= 1

print(result)

Solution (Python):
H,W = map(int,input().split())
A = []
for i in range(H):
	s = list(input())
	A.append([0 if c == "." else 1 for c in s])
dist = [[0 if r == 0 and c == 0 else 1000 for c in range(W)] for r in range(H)]
for r in range(H):
	for c in range(W):
		if c == 0 and r == 0:
			continue
		if r == 0:
			dist[r][c] = dist[r][c-1] + int(abs(A[r][c] - A[r][c-1]))
		elif c == 0:
			dist[r][c] = dist[r-1][c] + int(abs(A[r][c] - A[r-1][c]))
		else:
			dist[r][c] = min(dist[r][c-1] + int(abs(A[r][c] - A[r][c-1])), dist[r-1][c] + int(abs(A[r][c] - A[r-1][c])))
ans = (dist[H-1][W-1] + 1) // 2
if A[0][0] == 1 and A[H-1][W-1] == 1:
	print(ans + 1)
else:
	print(ans)

Solution (Python):


h,w=map(int,input().split())
infi=10**10
D=[list(input()) for i in range(h)]
kotae=[[infi]*(w) for _ in range(h)]


cnt=0
if D[0][0]=='.':
    kotae[0][0]=0
else:
    kotae[0][0]=1
    cnt+=1
for i in range(1,h):
    if D[i][0]=='
        cnt+=1
    kotae[i][0]=cnt

cnt=0
if D[0][0]=='.':
    kotae[0][0]=0
else:
    kotae[0][0]=1
    cnt+=1
for j in range(1,w):
    if D[0][j]=='
        cnt+=1
    kotae[0][j]=cnt
for i in range(h-1):
    for j in range(w-1):
        kouho1 = kotae[i][j+1]
        if D[i][j+1]=='.' and D[i+1][j+1]=='
            kouho1+=1
        kouho2=kotae[i+1][j]
        if D[i+1][j]=='.' and D[i+1][j+1]=='
            kouho2+=1
        kotae[i+1][j+1]=min(kouho1,kouho2)
print(kotae[h-1][w-1])

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

for h in range(H):
    for w in range(W):
        if h==0:
            if w==0: 
                if s[h][w]=="
                    M[h][w]=1
            elif w>0: 
                if s[h][w]==".":
                    M[h][w]=M[h][w-1]
                else:
                    if s[h][w-1]=="
                        M[h][w]=M[h][w-1]
                    else:
                        M[h][w]=M[h][w-1]+1
        elif w==0: 
            if s[h][w]==".":
                M[h][w]=M[h-1][w]
            else:
                if s[h-1][w]=="
                    M[h][w]=M[h-1][w]
                else:
                    M[h][w]=M[h-1][w]+1
        else: 
            if s[h][w]==".":
                M[h][w]=min(M[h-1][w],M[h][w-1])
            else:
                if s[h-1][w]=="." and s[h][w-1]==".":
                    M[h][w]=min(M[h-1][w],M[h][w-1])+1
                elif s[h-1][w]=="
                    M[h][w]=min(M[h-1][w],M[h][w-1]+1)
                elif s[h-1][w]=="." and s[h][w-1]=="
                    M[h][w]=min(M[h-1][w]+1,M[h][w-1])
                else:
                    M[h][w]=min(M[h-1][w],M[h][w-1])

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

Solution (Python):
from collections import deque
import math
import sys

h,w = map(int,input().split())
s = [0] * h
for i in range(h):
     s[i] = [i for i in str(input())]
memo = [[300] * w for _ in range(h)]
memo[0][0] = 0
box=[deque([]) for _ in range(w+h-1)]
box[0].append([0,0])
ans = 0
for i in range(w+h-1):
     while box[i]:

          y,x = box[i].popleft()
          if y == h-1 and x == w-1:
               if s[y][x] == '.' and s[0][0] == '.':
                    print(ans//2)
               elif s[y][x] == '.' and s[0][0] == '
                    print((ans+1)//2)
               elif s[y][x] == '
                    print((ans + 1) // 2)
               else:
                    print(ans//2 + 1)
               sys.exit()
          for k, j in [(1, 0), (0, 1)]:
               nexty, nextx = y + k, x + j
               if nexty < h and nextx < w:
                    if memo[nexty][nextx] > 250:
                         memo[nexty][nextx] = ans
                         if s[nexty][nextx] == s[y][x]:
                              box[i].append([nexty, nextx])

                         elif s[nexty][nextx] != s[y][x]:
                              box[i + 1].append([nexty, nextx])


     ans += 1

Solution (Python):
from collections import deque

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

todo = deque([(0,0)])
seen = [[200 for j in range(w)] for i in range(h)]
sx = 0
sy = 0
if hw[0][0] == '.':
    seen[0][0] = 0
else:
    seen[0][0] = 1




while todo:
    sx,sy = todo.popleft()
    if sx + 1 < h and seen[sx+1][sy] == 200:
        todo.append((sx+1,sy))
    if sx + 1 < h and hw[sx+1][sy] == '.' and seen[sx+1][sy] > seen[sx][sy]:
        seen[sx+1][sy] = seen[sx][sy]
    if sx + 1 < h and hw[sx+1][sy] == '
        seen[sx+1][sy] = seen[sx][sy]+1
    if sx + 1 < h and hw[sx+1][sy] == '
        seen[sx+1][sy] = seen[sx][sy]
    if sy+1 < w and seen[sx][sy+1] == 200:
        todo.append((sx,sy+1))
    if sy + 1 < w and hw[sx][sy+1] == '.' and seen[sx][sy+1] > seen[sx][sy]:
        seen[sx][sy+1] = seen[sx][sy]
    if sy + 1 < w and hw[sx][sy+1] == '
        seen[sx][sy+1] = seen[sx][sy]+1
    if sy + 1 < w and hw[sx][sy+1] == '
        seen[sx][sy+1] = seen[sx][sy]



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

Solution (Python):
import sys
from heapq import heappop, heappush
sys.setrecursionlimit(10000000)

h, w = map(int, input().split())
c = [input() for _ in range(h)]
d = [[10000]*w for _ in range(h)]

que = []
if c[0][0] == '.':
    heappush(que, (0, 0, 0))
    d[0][0] = 0
else:
    heappush(que, (1, 0, 0))
    d[0][0] = 1

while len(que):
    dist, px, py = heappop(que)
    if d[h-1][w-1] < dist:
        break
    for dx, dy in [(0, 1), (1, 0)]:
        qx, qy = px + dx, py + dy
        if not (0 <= qx < h and 0 <= qy < w):
            continue
        if d[qx][qy] > dist:
            if c[px][py]=='.' and c[qx][qy]=='
                d[qx][qy] = dist + 1
                heappush(que, (d[qx][qy], qx, qy))
            else:
                d[qx][qy] = dist
                heappush(que, (d[qx][qy], qx, qy))
print(d[h-1][w-1])

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

H,W = map(int,readline().split())
S = ''.join(read().decode().split())

INF = 10 ** 9
N = H*W
U = 250
dp = [[INF] * U for _ in range(N)]

dp[0] = list(range(U))
for n in range(H*W):
    for i in range(U-1,0,-1):
        if dp[n][i-1]> dp[n][i]:
            dp[n][i-1] = dp[n][i]
    for i in range(1,U):
        if dp[n][i-1] + 1 < dp[n][i]:
            dp[n][i] = dp[n][i-1] + 1
    s = S[n]
    if s == '
        for i in range(0,U,2):
            dp[n][i] = INF
    else:
        for i in range(1,U,2):
            dp[n][i] = INF
    x,y = divmod(n,W)
    to = []
    if y < W - 1:
        to.append(n+1)
    if x < H - 1:
        to.append(n+W)
    for m in to:
        for i in range(U):
            if dp[m][i] > dp[n][i]:
                dp[m][i] = dp[n][i]

print(min(dp[-1]))

Solution (Python):
from collections import deque

h,w = map(int,input().split())
base = []

for i in range(h):
  base.append(input())
  
seen = [-1]*(h*w)
q = deque([])
q.append([0,0])
now_ini = base[0][0]

if now_ini == ".":
  seen[0] = 0
elif now_ini == "
  seen[0] = 1

while q:
  r,c = q.popleft()
  now = base[r][c]
  
      

      
  if (r+1<h) and (seen[(r+1)*w+c] == -1):
    if now == base[r+1][c]:
      sign = 0
    elif (now != base[r+1][c]) and (now == "."):
      sign = 1
    elif (now != base[r+1][c]) and (now == "
      sign = 2
      
    if sign == 0:
      q.appendleft([r+1,c])
      seen[(r+1)*w+c] = seen[r*w+c]
    elif sign == 1:
      q.append([r+1,c])
      seen[(r+1)*w+c] = seen[r*w+c] + 1
    elif (sign == 2):
      q.append([r+1,c])
      seen[(r+1)*w+c] = seen[r*w+c]
      
  if (c+1<w) and (seen[r*w+c+1] == -1):
    if now == base[r][c+1]:
      sign = 0
    elif now != base[r][c+1] and (now == "."):
      sign = 1
    elif (now != base[r][c+1]) and (now == "
      sign = 2
      
    if sign == 0:
      q.appendleft([r,c+1])
      seen[r*w+c+1] = seen[r*w+c]
    elif sign == 1:
      q.append([r,c+1])
      seen[r*w+c+1] = seen[r*w+c] + 1
    elif (sign == 2):
      q.append([r,c+1])
      seen[r*w+c+1] = seen[r*w+c]
      
      
print(seen[w*h-1])

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

dp[0][0] = 1 if lines[0][0] == '

for i in range(1, W):
  if lines[0][i-1] != '
    dp[0][i] = dp[0][i-1] + 1
  else:
    dp[0][i] = dp[0][i-1]

for i in range(1, H):
  if lines[i-1][0] != '
    dp[i][0] = dp[i-1][0] + 1
  else:
    dp[i][0] = dp[i-1][0]

for i in range(1, H):
  for j in range(1, W):
    if lines[i-1][j] != '
      a = dp[i-1][j] + 1
    else:
      a = dp[i-1][j]

    if lines[i][j-1] != '
      b = dp[i][j-1] + 1
    else:
      b = dp[i][j-1]

    dp[i][j] = min(a, b)



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

Solution (Python):
def main():
    from collections import deque

    WHITE = 0
    BLACK = 1

    CHAR = '.', '

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

    h = deque()
    x = CHAR.index(s[0][0])
    h.append((x, 0, 0, x))

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

    while h:
        cnt, r, c, mode = h.popleft()
        if cnt > cost[r][c]:
            continue
        if r == H - 1 and c == W - 1:
            print(cnt)
            return

        delta = int(mode == WHITE)
        ncnt = cnt + delta

        if r < H - 1:
            if s[r + 1][c] == CHAR[mode]:
                if cnt < cost[r + 1][c]:
                    cost[r + 1][c] = cnt
                    h.appendleft((cnt, r + 1, c, mode))
            else:
                if delta:
                    if ncnt < cost[r + 1][c]:
                        cost[r + 1][c] = ncnt
                        h.append((ncnt, r + 1, c, 1 - mode))
                else:
                    if ncnt < cost[r + 1][c]:
                        cost[r + 1][c] = ncnt
                        h.appendleft((ncnt, r + 1, c, 1 - mode))

        if c < W - 1:
            if s[r][c + 1] == CHAR[mode]:
                if cnt < cost[r][c + 1]:
                    cost[r][c + 1] = cnt
                    h.appendleft((cnt, r, c + 1, mode))
            else:
                if delta:
                    if ncnt < cost[r][c + 1]:
                        cost[r][c + 1] = ncnt
                        h.append((ncnt, r, c + 1, 1 - mode))
                else:
                    if ncnt < cost[r][c + 1]:
                        cost[r][c + 1] = ncnt
                        h.appendleft((ncnt, r, c + 1, 1 - mode))


if __name__ == '__main__':
    main()

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

dp = {}





def rec(y, x, f):
    if (y, x, f) in dp:
        return dp[(y, x, f)]
    if y == h - 1 and x == w - 1:
        return 0
    if y < 0 or h <= y or x < 0 or w <= x:
        print(10.0 / 0)
    ret = 10**8
    steps = [0, 1, 0]
    for i in range(2):
        next_x, next_y = x + steps[i], y + steps[i + 1]
        if 0 <= next_y < h and 0 <= next_x < w:
            if table[next_y][next_x] == "
                if f == True:
                    ret = min(rec(next_y, next_x, True), ret)
                else:
                    ret = min(rec(next_y, next_x, True) + 1, ret)
            else:
                ret = min(rec(next_y, next_x, False), ret)
        else:
            continue
    dp[(y, x, f)] = ret
    return ret


ans = rec(0, 0, True) + 1 if table[0][0] == "
print(ans)
"""
問題文読み違えてた？
3 3
.


だと
2
じゃなくて
1
が正解？

ADD: やっぱり読み違えてたみたいだ 1時間以上ロスしたんだけど 日本語のおべんきょうをやりなおそうね
"""

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):
import bisect, collections
 
 
 
def solution():
    h, w = [int(x) for x in input().strip().split(" ")]
    b, dp = [], []
    for _ in range(h):
        b.append(input().strip())
        dp.append([0]*w)

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

def main():    
    
    for _ in range(1):
        solution()

if __name__ == "__main__":
    main()

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

dp = {}





def rec(y, x, f):
    if (y, x, f) in dp:
        return dp[(y, x, f)]
    if y == h - 1 and x == w - 1:
        
        return 0
    if y < 0 or h <= y or x < 0 or w <= x:
        print(10.0 / 0)
    ret = 10**8
    steps = [0, 1, 0]
    for i in range(2):
        next_x, next_y = x + steps[i], y + steps[i + 1]
        if 0 <= next_y < h and 0 <= next_x < w:
            if table[next_y][next_x] == "
                
                if f == True:
                    ret = min(rec(next_y, next_x, True), ret)
                else:
                    ret = min(rec(next_y, next_x, True) + 1, ret)
            else:
                
                ret = min(rec(next_y, next_x, False), ret)
        else:
            continue
    
    dp[(y, x, f)] = ret
    return ret


ans = rec(0, 0, True) + 1 if table[0][0] == "
print(ans)
"""
問題文読み違えてた？
3 3
.


だと
2
じゃなくて
1
が正解？
"""

Solution (Python):
H,W=map(int,input().split())
s=[input() for i in range(H)]
m=[[None]*W for i in range(H)]
if s[0][0]==".":
    m[0][0]=0
    t=0
else:
    m[0][0]=1
    t=1
for i in range(1,W):
    if s[0][i-1]!=s[0][i]:
        t+=1
    m[0][i]=t
t=m[0][0]
for i in range(1,H):
    if s[i-1][0]!=s[i][0]:
        t+=1
    m[i][0]=t
for i in range(1,H):
    for j in range(1,W):
        if s[i][j]==s[i-1][j] and s[i][j]==s[i][j-1]:
            m[i][j]=min(m[i-1][j],m[i][j-1])
        elif s[i][j]==s[i-1][j]:
            m[i][j]=min(m[i-1][j],m[i][j-1]+1)
        elif s[i][j]==s[i][j-1]:
            m[i][j]=min(m[i][j-1],m[i-1][j]+1)
        else:
            m[i][j]=min(m[i-1][j],m[i][j-1])+1
print((m[-1][-1]+1)//2)