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



Sample input:
3 3
.##
.#.
##.


Sample output:
1

Submission status: Accepted

Solution code:
import copy
h, w = map(int, input().split())
S = []
for i in range(h):
  S.append(input())
#print(S)
single = [-1] * w
A = []
for i in range(h):
  A.append(copy.copy(single))
#print(A)

counter = 0
memory = "."
for i in range(w):
  if memory == "." and S[0][i] == "#":
    counter += 1
  A[0][i] = counter
  memory = S[0][i]

counter = 0
memory = "."
for i in range(h):
  if memory == "." and S[i][0] == "#":
    counter += 1
  A[i][0] = counter
#  print(i, A, counter, memory, S[i][0])
  memory = S[i][0]

for i in range(1, h):
  for j in range(1, w):
    #A[i][j]
    tate_counter = A[i-1][j]
    if S[i-1][j] == "." and S[i][j] == "#":
      tate_counter += 1
    yoko_counter = A[i][j-1]
    if S[i][j-1] == "." and S[i][j] =="#":
      yoko_counter += 1
    A[i][j] = min(tate_counter, yoko_counter)
  
print(A[-1][-1])

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(10**6)
h,w = map(int, input().split())
grid = []
for i in range(h):
    grid.append(list(input()))
#色が変わるところでコスト
inf = 10**9
#x,y渡すと、（ｈ、ｗ）に入ってるかどうか判定
#graph => そこまでの距離を保存した二次元配列　grid=>与えられた迷路
adjacent_list = [[] for i in range(h*w+1)]
for i in range(h):
    for j in range(w):
        if i == (h-1) and j == (w-1):
            continue
        if j != (w-1):
            if grid[i][j] != grid[i][j+1] and grid[i][j] == '#':
                adjacent_list[w*i + (j + 1)].append([w*(i) + (j + 2), 1])
            else:
                adjacent_list[w*i + (j + 1)].append([w*(i) + (j + 2), 0])
        if i != (h-1):
            if grid[i][j] != grid[i+1][j] and grid[i][j] == '#':
                adjacent_list[w*i + (j + 1)].append([w*(i + 1) + (j + 1), 1])
            else:
                adjacent_list[w*i + (j + 1)].append([w*(i + 1) + (j + 1), 0])
finished = set()
def dfs(node,cost):
    finished.add(node)
    for i in adjacent_list[node]:
        if dist[node] + i[1] < dist[i[0]]:
            dist[i[0]] = dist[node] + i[1]
            dfs(i[0],i[1])
dist = [inf for i in range(h*w+1)]
dist[1] = 0
dfs(1,0)
if grid[-1][-1] == '#':
    dist[-1] += 1
print(dist[-1])

Submission status: Accepted

Solution code:
import sys
import math
import string
import fractions
import random
from operator import itemgetter
import itertools
from collections import deque
import copy
import heapq
from bisect import bisect, bisect_left, bisect_right

MOD = 10 ** 9 + 7
INF = float('inf')
input = lambda: sys.stdin.readline().strip()

sys.setrecursionlimit(10 ** 8)


def search(y, x, depth):
    global ans
    if s[y][x] == ".":
        if y == H and x == W:
            if depth < ans:
                ans = depth
        if s[y + 1][x] == ".":
            if check[y + 1][x] > depth:
                pos.append([y + 1, x, depth])
                check[y + 1][x] = depth
        elif s[y + 1][x] == "#":
            if check[y + 1][x] > depth:
                search(y + 1, x, depth)
                check[y + 1][x] = depth
        if s[y][x + 1] == ".":
            if check[y][x + 1] > depth:
                pos.append([y, x + 1, depth])
                check[y][x + 1] = depth
        elif s[y][x + 1] == "#":
            if check[y][x + 1] > depth:
                search(y, x + 1, depth)
                check[y][x + 1] = depth
    else:
        if y == H and x == W:
            if depth < ans:
                ans = depth + 1
        if s[y + 1][x] == ".":
            if check[y + 1][x] > depth + 1:
                pos.append([y + 1, x, depth + 1])
                check[y + 1][x] = depth + 1
        elif s[y + 1][x] == "#":
            if check[y + 1][x] > depth:
                search(y + 1, x, depth)
                check[y + 1][x] = depth
        if s[y][x + 1] == ".":
            if check[y][x + 1] > depth + 1:
                pos.append([y, x + 1, depth + 1])
                check[y][x + 1] = depth + 1
        elif s[y][x + 1] == "#":
            if check[y][x + 1] > depth:
                search(y, x + 1, depth)
                check[y][x + 1] = depth


H, W = map(int, input().split())
s = [["$" for _ in range(W + 2)]]
for i in range(H):
    s.append(["$"] + list(input()) + ["$"])
s.append(["$" for _ in range(W + 2)])
check = [[INF] * (W + 2) for _ in range(H + 2)]

ans = INF
pos = deque()
if s[1][1] == ".":
    pos.append([1, 1, 0])
else:
    search(1, 1, 0)
while len(pos) > 0:
    y, x, depth = pos.popleft()
    search(y, x, depth)
print(ans)

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
"""
Created on Sat Mar 21 20:57:37 2020

@author: naoki
"""
import math
#f = open("C:/Users/naoki/Desktop/Atcoder/input.txt")
H,W = map(int,input().split())
tizu = [list(str(input().replace('\n',''))) for _ in range(H)]

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

if tizu[0][0] == "#":
    memo[0][0] = 1
else:
    memo[0][1] = 0

for i in range(1,W):
    if tizu[0][i] == tizu[0][i-1]:
        memo[0][i] = memo[0][i-1]
    else:
        memo[0][i] = memo[0][i-1] + 1

for k in range(1,H):
    for j in range(W):
        if tizu[k][j] == tizu[k-1][j]:
            memo[k][j] = memo[k-1][j]
        else:
            memo[k][j] = memo[k-1][j] + 1
    for j in range(1,W):
        if tizu[k][j] == tizu[k][j-1]:
            temp = memo[k][j-1]
        else:
            temp = memo[k][j-1] + 1
        if temp < memo[k][j]:
            memo[k][j] = temp
for k in range(H):
    for j in range(W):
        memo[k][j] = int(math.ceil(memo[k][j]/2))


print(memo[-1][-1])

Submission status: Accepted

Solution code:
#!/usr/bin/env python3

import sys

sys.setrecursionlimit(10 ** 6)


def main():
	h, w = map(int, sys.stdin.readline().split())
	s = [list(sys.stdin.readline().rstrip())[::-1] for i in [0]*h][::-1]
	cost = [[0]*w for i in [0]*h]
	for y in range(h):
		for x in range(w):
			if y == 0 and x == 0:
				if s[y][x] == "#":
					cost[y][x] = 1
			elif y == 0:
				if s[y][x] == "#" and s[y][x-1] != "#":
					cost[y][x] = cost[y][x-1] + 1
				else:
					cost[y][x] = cost[y][x-1]
			elif x == 0:
				if s[y][x] == "#" and s[y-1][x] != "#":
					cost[y][x] = cost[y-1][x] + 1
				else:
					cost[y][x] = cost[y-1][x]
			else:
				if s[y][x] == "#" and s[y-1][x] != "#":
					cost[y][x] = cost[y-1][x] + 1
				else:
					cost[y][x] = cost[y-1][x]
				if s[y][x] == "#" and s[y][x-1] != "#":
					cost[y][x] = min(cost[y][x], cost[y][x-1] + 1)
				else:
					cost[y][x] = min(cost[y][x], cost[y][x-1])
	print(cost[h-1][w-1])

main()

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(1000000)
h, w = map(int, input().split())
grid = []
grid.append('#' * (w+2))
for _ in range(h):
    grid.append('#' + input().rstrip() + '#')
grid.append('#' * (w+2))
             
inf = float("inf")
step = [[inf] * (w+2) for _ in range(h+2)]

if grid[1][1] == "#":
    step[1][1] = 1
else:
    step[1][1] = 0
    
for i in range(1,h+2):
    for j in range(1,w+2):
        if i == 1 and j == 1:
            continue
        if grid[i-1][j] == "#":
            y_flag = 0
        else:
            y_flag = 1 
        if grid[i][j-1] == "#":
            x_flag = 0
        else:
            x_flag = 1
        if grid[i][j] == ".":
            step[i][j] = min(step[i-1][j], step[i][j-1])
        else:
            step[i][j] = min(step[i-1][j]+y_flag, step[i][j-1]+x_flag)

print(step[h][w])

Submission status: Accepted

Solution code:
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] == "#" and maze[y][x] == '.' and visited[new_y][new_x] > count+1:
                visited[new_y][new_x] = count+1
                stack.appendleft([new_y, new_x])
            elif maze[new_y][new_x] == "#" and maze[y][x] == '.' and visited[new_y][new_x] <= count+1:
                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))

Submission status: Accepted

Solution code:
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={'#':1,'.':0}):
#h,w,g,sg=GGI(h,w,search=['S','G'],replacement_of_found='.',mp_def={'#':1,'.':0}) # sample usage
    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
#sys.setrecursionlimit(10**7)
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={'#':1,'.':0})
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])

Submission status: Accepted

Solution code:
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: #対象idxがareaの外にいる場合は対象外
        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)
print(possible_list[H-1][W-1])

Submission status: Accepted

Solution code:
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] == "#" else 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] != "#" and S[i][j] == "#" else 0) 
        left = dp[i][j-1] + (1 if S[i][j-1] != "#" and S[i][j] == "#" else 0)
        dp[i][j] = min(up, left)
print(dp[-1][-1])

Submission status: Accepted

Solution code:
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()

Submission status: Accepted

Solution code:
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] == "#" and s[0][i-1] == ".":
            t[0][i] += 1
    for i in range(1, H):
        t[i][0] = t[i-1][0]
        if s[i][0] == "#" and s[i-1][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()

Submission status: Accepted

Solution code:
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={'#':1,'.':0}):
#h,w,g,sg=GGI(h,w,search=['S','G'],replacement_of_found='.',mp_def={'#':1,'.':0}) # sample usage
    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
#sys.setrecursionlimit(10**7)
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={'#':1,'.':0}) # sample usage
#show(g,h,w,sg)


dp=[10**6]*(h*w)
#dp[1*w+1]=0
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
    
    #if dp[j]>=10**6: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])

Submission status: Accepted

Solution code:
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]=='#' or S[-1][-1]=='#'))

Submission status: Accepted

Solution code:
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])

Submission status: Accepted

Solution code:
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
        # s[0][0] = '.'
    

    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] == '#' and s[i][j] == '#':
                    tmp_up = dp[i-1][j]
                else:
                    tmp_up = dp[i-1][j] + change
            if j != 0:
                if s[i][j-1] == '#' and s[i][j] == '#':
                    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()

Submission status: Accepted

Solution code:
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] == '#' else 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)

Submission status: Accepted

Solution code:
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])

Submission status: Accepted

Solution code:
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))

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
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] == '#' else 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))

    # H = 100
    # W = 100
    # S = [''.join(random.choices('.#', k=W)) for _ in range(H)]
    # print(slv(H, W, S))


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
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()
    #print(a,b,rl)
    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])

Submission status: Accepted

Solution code:
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)