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:
from math import ceil,floor,comb,factorial,gcd,pow,sqrt,log2,cos,sin,tan,acos,asin,atan,degrees,radians,pi,inf
from itertools import accumulate,permutations,combinations,product,combinations_with_replacement
from collections import deque,defaultdict,Counter
from bisect import bisect_left,bisect_right
from operator import itemgetter
from heapq import heapify,heappop,heappush
from copy import deepcopy
from time import time
import string
import sys
sys.setrecursionlimit(10 ** 7)
def input() : return sys.stdin.readline().strip()
def INT()   : return int(input())
def MAP()   : return map(int,input().split())
def LIST()  : return list(MAP())

def bfs():
    que = deque()
    que.append([0, 0])
    if s[0][0] == '#':
        d[0][0] = 1
    else:
        d[0][0] = 0

    while que:
        p = que.popleft()
        if p[0] == h-1 and p[1] == w-1:
            break

        for i in range(2):
            ny = p[0] + dy[i]
            nx = p[1] + dx[i]
            if 0 <= ny < h and 0 <= nx < w:
                if s[p[0]][p[1]] == '.' and  s[ny][nx] == '#':
                    if d[ny][nx] > d[p[0]][p[1]]+1:
                        d[ny][nx] = d[p[0]][p[1]]+1
                        que.append([ny, nx])
                else:
                    if d[ny][nx] > d[p[0]][p[1]]:
                        d[ny][nx] = d[p[0]][p[1]]
                        que.append([ny, nx])

    return d[h-1][w-1]

h, w = MAP()
s = [input() for i in range(h)]
d = [[inf]*w for i in range(h)]

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

print(bfs())

Submission status: Accepted

Solution code:
import sys, re
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, tan, asin, acos, atan, radians, degrees, log2, gcd
from itertools import accumulate, permutations, combinations, combinations_with_replacement, product, groupby
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
from bisect import bisect, bisect_left, insort, insort_left
from heapq import heappush, heappop
from functools import reduce
def input(): return sys.stdin.readline().strip()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
def ZIP(n): return zip(*(MAP() for _ in range(n)))
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
mod = 10 ** 9 + 7 
#mod = 998244353
from decimal import *
#import numpy as np
#decimal.getcontext().prec = 10

H, W = MAP()
s = [input() for _ in range(H)]

cnt = [[-1]*W for _ in range(H)]

if s[0][0] == ".":
	cnt[0][0] = 0
else:
	cnt[0][0] = 1

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

q = deque([(0, 0)])
while q:
	y, x = q.popleft()
	for i in range(2):
		ny = y + dy[i]
		nx = x + dx[i]
		if ny < H and nx < W and cnt[ny][nx] == -1:
			if s[ny][nx] == s[y][x]:
				cnt[ny][nx] = cnt[y][x]
				q.appendleft((ny, nx))
			else:
				cnt[ny][nx] = cnt[y][x] + 1
				q.append((ny, nx))

if s[H-1][W-1] == "#":
	ans = (cnt[H-1][W-1]+1)//2
else:
	ans = (cnt[H-1][W-1])//2
print(ans)

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.buffer.readline

#sys.setrecursionlimit(10**9)
#from functools import lru_cache

def RD(): return sys.stdin.read()
def II(): return int(input())
def MI(): return map(int,input().split())
def MF(): return map(float,input().split())
def LI(): return list(map(int,input().split()))
def LF(): return list(map(float,input().split()))
def TI(): return tuple(map(int,input().split()))
# rstrip().decode()

def main():
	h,w=MI()

	S=["#"*(w+1)]
	for _ in range(h):
		S.append("#"+input().rstrip().decode())
	#print(S)

	G=[[10**10]*(w+1) for _ in range(h+1)]

	if S[1][1]=="#":
		G[1][1]=1
	else:
		G[1][1]=0

	for i in range(1,h+1):
		for j in range(1,w+1):
			#print(G)
			if i==j==1:
				continue
			a=G[i-1][j]+(S[i-1][j]=="." and S[i][j]=="#")
			b=G[i][j-1]+(S[i][j-1]=="." and S[i][j]=="#")
			#print(i,j,a,b)
			G[i][j]=min(a,b)

	print(G[h][w])













if __name__ == "__main__":
	main()

Submission status: Accepted

Solution code:
h, w = map(int, input().split())
s = [list(input()) for _ in range(h)]
dp = [[h * w] * w for _ in range(h)]
dp[0][0] = 0 if s[0][0] == "." else 1

for x0 in range(w):
    for y0 in range(h):
        for i, j in [(0, 1), (1, 0)]:
            x = x0 + i
            y = y0 + j
            if x < w and y < h:
                n = 1 if s[y0][x0] == "." and s[y][x] == "#" else 0
                dp[y][x] = min(dp[y0][x0] + n, dp[y][x])

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

Submission status: Accepted

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

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

dp[0][0] = 1 if g[0][0] == '#' else 0
d = ([0,1], [1,0])
for ix in range(H):
    for jx in range(W):
        for dx,dy in d:
            ni = ix + dx
            nj = jx + dy
            if ni >= H or nj >= W:
                continue
            add = 0
            if g[ix][jx] == '.' and g[ni][nj] == '#':
                add += 1
            dp[ni][nj] = min(dp[ni][nj], dp[ix][jx] + add)


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

Submission status: Accepted

Solution code:
import sys
from copy import copy
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline

in_n = lambda: int(readline())
in_nn = lambda: map(int, readline().split())
in_nl = lambda: list(map(int, readline().split()))
in_na = lambda: map(int, read().split())
in_s = lambda: readline().rstrip().decode('utf-8')

INF = 10**9 + 7


def main():
    H, W = in_nn()
    s = [list(in_s()) for _ in range(H)]

    dp = [INF] * W
    if s[0][0] == '#':
        dp[0] = 1
    else:
        dp[0] = 0

    for x in range(W - 1):
        if s[0][x] == '.' and s[0][x + 1] == '#':
            dp[x + 1] = dp[x] + 1
        else:
            dp[x + 1] = dp[x]

    for y in range(1, H):
        next_dp = [INF] * W
        for x in range(W):
            if s[y - 1][x] == '.' and s[y][x] == '#':
                next_dp[x] = min(next_dp[x], dp[x] + 1)
            else:
                next_dp[x] = min(next_dp[x], dp[x])
        for x in range(1, W):
            if s[y][x - 1] == '.' and s[y][x] == '#':
                next_dp[x] = min(next_dp[x], next_dp[x - 1] + 1)
            else:
                next_dp[x] = min(next_dp[x], next_dp[x - 1])

        dp = next_dp

    print(dp[-1])


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
H, W = map(int, input().split())
L = [input() for _ in range(H)]
 
inf = 10**9
dp = [[inf] * W for _ in range(H)]
 
#[0][0]を埋める
if (L[0][0] == '.'):
    dp[0][0] = 0
else:
    dp[0][0] = 1
 
for i in range(H):
    for j in range(W):
 
        #[0][0]の時は無視
        if (i == 0 and j == 0):
            continue
        #→の場合。一個前のマス。
        a = dp[i][j - 1]
        #↓の場合。一個前のマス。
        b = dp[i - 1][j]
 
        #.から#に移動するときだけ操作が(1回)必要
        if (L[i][j - 1] == "." and L[i][j] == "#"):
            a += 1
        if (L[i - 1][j] == '.' and L[i][j] == '#'):
            b += 1
 
        # min(dp[i][j],a,b)でもいいが結局問題になるのはa,bの比較だけでは？
        dp[i][j] = min(a, b)
 
print(dp[-1][-1])

Submission status: Accepted

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

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

#[0][0]を埋める
if (L[0][0] == '.'):
    dp[0][0] = 0
else:
    dp[0][0] = 1

for i in range(H):
    for j in range(W):

        #[0][0]の時は無視
        if (i == 0 and j == 0):
            continue
        #→の場合。一個前のマス。
        a = dp[i][j - 1]
        #↓の場合。一個前のマス。
        b = dp[i - 1][j]

        #.から#に移動するときだけ操作が(1回)必要
        if (L[i][j - 1] == "." and L[i][j] == "#"):
            a += 1
        if (L[i - 1][j] == '.' and L[i][j] == '#'):
            b += 1

        # min(dp[i][j],a,b)でもいいが結局問題になるのはa,bの比較だけでは？
        dp[i][j] = min(a, b)

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

Submission status: Accepted

Solution code:

import sys
sys.setrecursionlimit(10**7)

readline = sys.stdin.buffer.readline
def readstr():return readline().rstrip().decode()
def readstrs():return list(readline().decode().split())
def readint():return int(readline())
def readints():return list(map(int,readline().split()))
def printrows(x):print('\n'.join(map(str,x)))
def printline(x):print(' '.join(map(str,x)))

from math import ceil

h,w = readints()

s = [readstr() for i in range(h)]

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

if s[0][0] == '.':
    dp[0][0] = 0
else:
    dp[0][0] = 1

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

for i in range(1,w):
    if s[0][i] != s[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):
    for j in range(1,w):
        if s[i][j] != s[i-1][j]:
            dp[i][j] = dp[i-1][j] + 1
        else:
            dp[i][j] = dp[i-1][j]
        if s[i][j] != s[i][j-1]:
            dp[i][j] = min(dp[i][j-1] + 1,dp[i][j])
        else:
            dp[i][j] = min(dp[i][j-1],dp[i][j])

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

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline
from collections import *

H, W = map(int, input().split())
s = [input()[:-1] for _ in range(H)]
dp = [[10**18]*W for _ in range(H)]

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

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

Submission status: Accepted

Solution code:
from collections import deque
h,w=map(int,input().split())
l=['@'*(w+2)]
for i in range(h):
    l.append('@'+input()+'@')
l.append('@'*(w+2))
s=[[-1 for i in j] for j in l]
s[1][1]=l[1][1]=='#'
q=deque([[1,1]])
while len(q)>0:
    x,y=q.popleft()
    for i,j in [[1,0],[0,1]]:
        if l[i+x][j+y]!='@' and s[i+x][j+y]==-1:
            if l[x][y]==l[i+x][j+y]:
                q.appendleft([i+x,j+y])
                s[i+x][j+y]=s[x][y]
            else:
                q.append([i+x,j+y])
                s[i+x][j+y]=s[x][y]+1
print(-s[h][w]//2*-1)
#print(*l,*s,sep='\n')

Submission status: Accepted

Solution code:
INF = 10**9
def solve(h, w, s):
    dp = [[INF] * w for r in range(h)]
    dp[0][0] = int(s[0][0] == "#")
    for r in range(h):
        for c in range(w):
            for dr, dc in [(-1, 0), (0, -1)]:
                nr, nc = r+dr, c+dc
                if (0 <= nr < h) and (0 <= nc < w):
                    dp[r][c] = min(dp[r][c], dp[nr][nc] + (s[r][c] != s[nr][nc]))
    return (dp[h-1][w-1] + 1) // 2

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

Submission status: Accepted

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

inf = 10**9 + 7
dp = [[inf] * W for _ in range(H)]
if (L[0][0] == '.'):
    dp[0][0] = 0
else:
    dp[0][0] = 1

for i in range(H):
    for j in range(W):
        if (i == 0 and j == 0):
            continue
        a = dp[i][j - 1]
        b = dp[i - 1][j]
        if (L[i - 1][j] == '.' and L[i][j] == '#'):
            b += 1
        if (L[i][j - 1] == '.' and L[i][j] == '#'):
            a += 1
        dp[i][j] = min(dp[i][j], a, b)

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

Submission status: Accepted

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

nowblack=False
dp=[[float("INF")]*W for _ in range(H)]
if S[0][0]=="#":
    dp[0][0]=1
else:
    dp[0][0]=0
for h in range(H):
    for w in range(W):
        if 0<=h-1<H:
            if S[h][w]==".":
                dp[h][w]=min(dp[h][w], dp[h-1][w])
            else:
                if S[h-1][w]=="#":
                    dp[h][w]=min(dp[h][w], dp[h-1][w])
                else:
                    dp[h][w]=min(dp[h][w], dp[h-1][w]+1)


        if 0<=w-1<W:
            if S[h][w]==".":
                dp[h][w]=min(dp[h][w], dp[h][w-1])
            else:
                if S[h][w-1]=="#":
                    dp[h][w]=min(dp[h][w], dp[h][w-1])
                else:
                    dp[h][w]=min(dp[h][w], dp[h][w-1]+1)

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

Submission status: Accepted

Solution code:
h,w=map(int,input().split())
s=[input() for _ in range(h)]
dp=[[10**9]*w for _ in range(h)]
dp[0][0]=(s[0][0]=='#')+0


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

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

Submission status: Accepted

Solution code:
H,W = map(int,input().split())
S = [list(input()) for _ in range(H)]
INF=10001
dp = [[INF]*W for _ in range(H)]
dp[0][0] = 0 if S[0][0] == "." else 1
 
for i in range(H):
  for j in range(W):
    m,n=INF,INF
    if i != 0:
      m = dp[i-1][j] + (S[i-1][j] == "." and S[i][j] == "#")
    if j != 0:
      n = dp[i][j-1] + (S[i][j-1] == "." and S[i][j] == "#")
 
    dp[i][j] = min(m, n, dp[i][j])
  
print(dp[H-1][W-1])

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
from queue import Queue

def II(): return int(input())
def MII(): return map(int, input().split())
def LII(): return list(map(int, input().split()))


def main():
    H, W = MII()
    S = [input() for _ in range(H)]
    dp = [[10**9] * W for _ in range(H)]

    dp[0][0] = (S[0][0] == '#') + 0
    for i in range(H):
        for j in range(W):
            a = dp[i-1][j]
            b = dp[i][j-1]

            if S[i-1][j] == '.' and S[i][j] == '#':
                a += 1
            if S[i][j-1] == '.' and S[i][j] == '#':
                b += 1
            
            dp[i][j] = min(dp[i][j], a, b)
                 
    print(dp[H-1][W-1])


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
#!/usr/bin python3
# -*- coding: utf-8 -*-

def main():
    H, W = map(int,input().split())
    sth, stw = 0, 0
    glh, glw = H-1, W-1

    INF = 10000
    Gmap = [list(input()) for _ in range(H)]
    Dist = [[INF]*W for _ in range(H)]
    direc = {(1,0), (0,1)}

    if Gmap[0][0]=='#':
        Dist[0][0]=1
    else:
        Dist[0][0]=0

    for h in range(H):
        for w in range(W):
            nw = Gmap[h][w]
            for d in direc:
                hs, ws = h + d[0], w + d[1]
                if 0<=hs<H and 0<=ws<W:
                    cr = Gmap[hs][ws]
                    Dist[hs][ws] = min(Dist[hs][ws], Dist[h][w] + (cr=='#' and nw=='.'))
    print(Dist[glh][glw])

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
# input()
# int(input())
# map(int, input().split())
# list(map(int, input().split()))
# list(map(int, list(input()))) # スペースがない数字リストを読み込み
import math
import fractions
import sys
import bisect
import heapq  # 優先度付きキュー(最小値取り出し)
import collections
from collections import Counter
from collections import deque
import pprint

sr = lambda: input()
ir = lambda: int(sr())
lr = lambda: list(map(int, sr().split()))

"""nを素因数分解"""
"""2以上の整数n => [[素因数, 指数], ...]の2次元リスト"""


def factorization(n):
    arr = []
    temp = n
    if n == 1:
        return arr

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

    if temp != 1:
        arr.append([temp, 1])

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

    return arr


# a^n
def power(a, n, mod):
    x = 1
    while n:
        if n & 1:
            x *= a % mod
        n >>= 1
        a *= a % mod
    return x % mod


# n*(n-1)*...*(l+1)*l
def kaijo(n, l, mod):
    if n == 0:
        return 1
    a = n
    tmp = n - 1
    while (tmp >= l):
        a = a * tmp % mod
        tmp -= 1
    return a


inf = 10 ** 18
mod = 10 ** 9 + 7

h,w = lr()
s = [input() for i in range(h)]
dis = [[0 for i in range(w+1)]for j in range(h+1)] # 障害物に当たる最小数
for i in range(2,w+1):
    dis[0][i] = inf
for i in range(2,h+1):
    dis[i][0] = inf
for i in range(h):
    for j in range(w):
        if s[i][j] == '.':
            dis[i+1][j+1] = min(dis[i][j+1], dis[i+1][j])
        else:
            if i>0 and j>0 and s[i-1][j]=='#' and s[i][j-1]=='#':
                dis[i+1][j+1] = min(dis[i][j+1], dis[i+1][j])
            elif i>0 and s[i-1][j]=='#':
                dis[i+1][j+1] = min(dis[i][j+1], dis[i+1][j]+1)
            elif j>0 and s[i][j-1]=='#':
                dis[i+1][j+1] = min(dis[i][j+1]+1, dis[i+1][j])
            else:
                dis[i+1][j+1] = min(dis[i][j+1]+1, dis[i+1][j]+1)
print(dis[h][w])

Submission status: Accepted

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

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

dp=[[10**9]*(w) for _ in range(h)]
if s[0][0]=='#':
    dp[0][0]=1
else:
    dp[0][0]=0

for i in range(h):
    for j in range(w):
        for d in range(2):
            new_i=i+dx[d]
            new_j=j+dy[d]
            if h<=new_i or w<=new_j:
                continue
            add=0
            if s[new_i][new_j]=='#' and s[i][j]=='.':
                add=1
            dp[new_i][new_j]=min(dp[new_i][new_j], dp[i][j]+add)

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

Submission status: Accepted

Solution code:
H,W=map(int,input().split())
s=[]
dp=[[10**9]*W for _ in range(H)]
dp[0][0]=0
for _ in range(H):
    s.append(list(input()))
for i in range(H):
    for j in range(W):
        if j!=W-1:
            if s[i][j]=="." and s[i][j+1]=="#":
                dp[i][j+1]=min(dp[i][j]+1,dp[i][j+1])
            else:
                dp[i][j+1]=min(dp[i][j],dp[i][j+1])
        if i!=H-1:
            if s[i][j]=="." and s[i+1][j]=="#":
                dp[i+1][j]=min(dp[i][j]+1,dp[i+1][j])
            else:
                dp[i+1][j]=min(dp[i][j],dp[i+1][j])
ans=dp[H-1][W-1]
if s[0][0]=="#":
    ans+=1
print(ans)

Submission status: Accepted

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

INF = 10**9
dp = [[INF]*w for _ in range(h)]

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

for i in range(h):
    for j in range(w):
        d, r = INF, INF

        if i != 0:
            d = dp[i - 1][j] + (s[i - 1][j] == "." and s[i][j] == "#")
        if j != 0:
            r = dp[i][j - 1] + (s[i][j - 1] == "." and s[i][j] == "#")

        dp[i][j] = min(r, d, dp[i][j])

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

Submission status: Accepted

Solution code:
import sys
from collections import deque

def input():
    return sys.stdin.readline().strip()

def main():
    H,W = map(int,input().split())
    S = [list(input()) for _ in range(H)]
    dp = [[float('inf') for _ in range(W)] for _ in range(H)]

    def bfs(x,y):
        que = deque()
        que.append((x,y))
        if S[y][x] == '.':
            dp[y][x] = 0
        else:
            dp[y][x] = 1
        while que.__len__():
            x,y = que.popleft()
            for dx,dy in ((1,0),(0,1)):
                sx = x + dx
                sy = y + dy
                if sx == W or sy == H:
                    continue
                if S[y][x] == '.' and S[sy][sx] == '#':
                    tmp = 1
                else:
                    tmp = 0
                dp[sy][sx] = min(dp[y][x]+tmp,dp[sy][sx])
                if (sx,sy) not in que:
                    que.append((sx,sy))
    bfs(0,0)
    print(dp[H-1][W-1])
if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
import sys
readline = sys.stdin.readline
sys.setrecursionlimit(10**8)
mod = 10**9+7
#mod = 998244353
INF = 10**18
eps = 10**-7

H,W = map(int,readline().split())
s = [readline().rstrip() for i in range(H)]

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

dp[0][0] = 0 if s[0][0] == '.' else 1

for i in range(H):
    ii = max(0,i-1)
    for j in range(W):
        jj = max(0,j-1)
        dp[i][j] = min(dp[ii][j] + (s[i][j] != s[ii][j]), dp[i][jj] + (s[i][j] != s[i][jj]))

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

Submission status: Accepted

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

inf=float("inf")
ans=[[inf]*W for _ in range(H)]

if s[0][0]==".":
    ans[0][0]=0
else:
    ans[0][0]=1

for i in range(H):
    for j in range(W):
        if j!=W-1:
            if s[i][j]=="." and s[i][j+1]=="#":
                ans[i][j+1]=min(ans[i][j]+1,ans[i][j+1])
            else:
                ans[i][j+1]=min(ans[i][j],ans[i][j+1])
        if i!=H-1:
            if s[i][j]=="." and s[i+1][j]=="#":
                ans[i+1][j]=min(ans[i][j]+1,ans[i+1][j])
            else:
                ans[i+1][j]=min(ans[i][j],ans[i+1][j]) 

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

Submission status: Accepted

Solution code:
t='.'
b=t*101
q=range(101)
for s in[*open(i:=0)][1:]:
 a=[i];i+=1
 for x,y,z,c in zip(b,t+s,s,q):a+=min(c+(t>z<x),a[-1]+(t>z<y)),
 b,q=s,a[1:]
print(a[-2])

Submission status: Accepted

Solution code:
_,*s=open(i:=0)
t='.'
b=t*101
q=range(101)
for s in s:
 a=[i];i+=1
 for x,y,z,c in zip(b,t+s,s,q):a+=min(c+(t>z<x),a[-1]+(t>z<y)),
 b,q=s,a[1:]
print(a[-2])

Submission status: Accepted

Solution code:
import math,itertools,fractions,heapq,collections,bisect,sys,queue,copy

sys.setrecursionlimit(10**7)
inf=10**20
mod=10**9+7
dd=[(-1,0),(0,1),(1,0),(0,-1)]
ddn=[(-1,0),(-1,1),(0,1),(1,1),(1,0),(1,-1),(0,-1),(-1,-1)]

def LI(): return [int(x) for x in sys.stdin.readline().split()]
# def LF(): return [float(x) for x in sys.stdin.readline().split()]
def I(): return int(sys.stdin.readline())
def F(): return float(sys.stdin.readline())
def LS(): return sys.stdin.readline().split()
def S(): return input()

def main():
  h,w=LI()

  l=[]
  l.append('.'*(w+1))
  for _ in range(h):
    x='.'
    x+=S()
    l.append(x)

  dp=[[inf]*(w+10) for _ in range(h+10)]
  if l[1][1]=='#':
    dp[1][1]=1
  else:
    dp[1][1]=0

  for i in range(1,h+1):
    for j in range(1,w+1):
      if i==1 and j==1:
        continue
      if l[i][j]=='#':
        if l[i-1][j]=='.':
          dp[i][j]=min(dp[i][j],dp[i-1][j]+1)
        else:
          dp[i][j]=min(dp[i][j],dp[i-1][j])
        if l[i][j-1]=='.':
          dp[i][j]=min(dp[i][j],dp[i][j-1]+1)
        else:
          dp[i][j]=min(dp[i][j],dp[i][j-1])
      else:
        dp[i][j]=min(dp[i-1][j],dp[i][j-1])

  # print(dp)
  
  return dp[h][w]

# main()
print(main())

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
from collections import deque, Counter
from heapq import heappop, heappush
from bisect import bisect_right

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

dp = [[0]*(W+1) for _ in range(H+1)]
if s[0][0] == '#':
    dp[1][1] += 1
for i in range(H):
    for j in range(W):
        if (i,j) == (0,0):
            continue
        tmp = []
        if i > 0:
            if s[i][j] == '#' and s[i-1][j] == '.':
                tmp.append(dp[i][j+1]+1)
            else:
                tmp.append(dp[i][j+1])
        if j > 0:
            if s[i][j] == '#' and s[i][j-1] == '.':
                tmp.append(dp[i+1][j]+1)
            else:
                tmp.append(dp[i+1][j])

        dp[i+1][j+1] = min(tmp)
print(dp[H][W])

Submission status: Accepted

Solution code:
H, W = map(int, input().split())
S = [list(input()) for h in range(H)]
table = [[0 for w in range(W)] for h in range(H)]

table[0][0] = int(S[0][0]=='#')
for i in range(1, H):
    table[i][0] = table[i-1][0] + int(S[i-1][0]=='.' and S[i][0]=='#')
for j in range(1, W):
    table[0][j] = table[0][j-1] + int(S[0][j-1]=='.' and S[0][j]=='#')
for i in range(1, H):
    for j in range(1, W):
        table[i][j] = min(table[i-1][j] + int(S[i-1][j]=='.' and S[i][j]=='#'),
         table[i][j-1] + int(S[i][j-1]=='.' and S[i][j]=='#'))

print(table[-1][-1])

Submission status: Accepted

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

m=[input() for i in range(h)]


cnt=[[1000000 for i in range(w)] for j in range(h)]

if m[0][0]=="#":
    cnt[0][0]=1
else:
    cnt[0][0]=0

for y in range(h):
    for x in range(w):
        if x>0:
            if m[y][x-1]=="." and m[y][x]=="#":
                cnt[y][x]=min(cnt[y][x],cnt[y][x-1]+1)
            else:
                cnt[y][x]=min(cnt[y][x],cnt[y][x-1])
        if y>0:
            if m[y-1][x]=="." and m[y][x]=="#":
                cnt[y][x]=min(cnt[y][x],cnt[y-1][x]+1)
            else:
                cnt[y][x]=min(cnt[y][x],cnt[y-1][x])


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

Submission status: Accepted

Solution code:
import copy
import heapq
H, W = map(int, input().split())
S = [['.'] * (W+1)]
for _ in range(H):
    s = list(input())
    s.insert(0,'.')
    S.append(s)

inf = float('inf')

dp = []
for _ in range(H+1):
    dp.append([inf] * (W+1))

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

for i in range(1,H+1):
    for j in range(1,W+1):
        right = dp[i][j-1]
        down = dp[i-1][j]
        if S[i][j] == '#':
            if S[i-1][j] == '.':
                down += 1
            if S[i][j-1] == '.':
                right += 1

        dp[i][j] = min(dp[i][j],right,down)

print(dp[H][W])

Submission status: Accepted

Solution code:
H, W = map(int, input().split())
Maze = [[1 if a == "#" else 0 for a in input()] for _ in range(H)]

DP = [[float('inf')] * W for _ in range(H)]

if Maze[0][0] == 1:
    DP[0][0] = 1
else:
    DP[0][0] = 0

for i in range(H):
    for j in range(W):
        if Maze[i][j] == 1:
            if i + 1 < H:
                DP[i+1][j] = DP[i][j]
            if j + 1 < W:
                DP[i][j+1] = min(DP[i][j+1], DP[i][j])
        if Maze[i][j] == 0:
            if i + 1 < H:
                if Maze[i+1][j] != 1:
                    DP[i + 1][j] = DP[i][j]
                else:
                    DP[i + 1][j] = DP[i][j] + 1
            if j + 1 < W:
                if Maze[i][j + 1] != 1:
                    DP[i][j + 1] = min(DP[i][j + 1], DP[i][j])
                else:
                    DP[i][j + 1] = min(DP[i][j + 1], DP[i][j]+1)

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

Submission status: Accepted

Solution code:
#!/usr/bin/env python
# coding: utf-8

# In[7]:


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


# In[32]:


dp = [[1000 for i in range(W+1)] for j in range(H+1)]
dp[0][1] = 0
dp[1][0] = 1

for h in range(H):
    for w in range(W):
        dp[h+1][w+1] = min(
            dp[h][w+1] + (s_mat[h][w] == "#" and (h==0 or s_mat[h-1][w] == ".")),
            dp[h+1][w] + (s_mat[h][w] == "#" and (w==0 or s_mat[h][w-1] == "."))
        )
        
print(dp[-1][-1])


# In[ ]:

Submission status: Accepted

Solution code:
#3 Range Flip Find Route
h,w = map(int,input().split())
s= [None for i in range(h)]
for i in range(h):
    s[i] = input()
    
dp = [[0]*w for i in range(h)]

dp[0][0] = int(s[0][0]=="#")
for i in range(1,w):
    dp[0][i]=dp[0][i-1] + (s[0][i-1]=="." and s[0][i]=="#")

for i in range(1,h):
    dp[i][0]=dp[i-1][0] + (s[i-1][0]=="." and s[i][0]=="#")

for i in range(1,h):
    for j in range(1,w):
        cand1 = dp[i-1][j] + (s[i-1][j]=="." and s[i][j]=="#")
        cand2 = dp[i][j-1] + (s[i][j-1]=="." and s[i][j]=="#")
        dp[i][j]=min(cand1,cand2)
        
print(dp[-1][-1])

Submission status: Accepted

Solution code:
#3 Range Flip Find Route
h,w = map(int,input().split())
s= [None for i in range(h)]
for i in range(h):
    s[i] = input()
    
dp = [[0]*w for i in range(h)]

now=0
if s[0][0]=="#":
    now+=1
    dp[0][0]=now
for i in range(1,w):
    if s[0][i-1]=="." and s[0][i]=="#":
        now+=1
    dp[0][i]=now
        
now=0
if s[0][0]=="#":
    now+=1
for i in range(1,h):
    if s[i-1][0]=="." and s[i][0]=="#":
        now+=1
    dp[i][0]=now

for i in range(1,h):
    for j in range(1,w):
        cand1 = dp[i-1][j] + (s[i-1][j]=="." and s[i][j]=="#")
        cand2 = dp[i][j-1] + (s[i][j-1]=="." and s[i][j]=="#")
        dp[i][j]=min(cand1,cand2)
        
print(dp[-1][-1])

Submission status: Accepted

Solution code:
h,w=map(int,input().split())
m=[[1 if c=="#" else 0 for c in input()] for i in range(h)]

n=[i[:] for i in m]


for i in range(1,h):
    n[i][0]=n[i-1][0]+int(m[i-1][0]-m[i][0]==-1)
for j in range(1,w):
    n[0][j]=n[0][j-1]+int(m[0][j-1]-m[0][j]==-1)

for i in range(1,h):
    for j in range(1,w):
        n[i][j]=min(n[i-1][j]+int(m[i-1][j]-m[i][j]==-1),n[i][j-1]+int(m[i][j-1]-m[i][j]==-1))

print(n[-1][-1])

Submission status: Accepted

Solution code:
h,w = map(int,input().split())
grid = []
for _ in range(h):
    grid.append(input())
dp = [[float("inf") for _ in range(w)] for _ in range(h)]
if grid[0][0] == ".":
    dp[0][0] = 0
else:
    dp[0][0] = 1
for j in range(1,w):
    if grid[0][j-1] == "." and grid[0][j] == "#":
        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(w):
        if j == 0:
            if grid[i-1][j] == "." and grid[i][j] == "#":
                dp[i][j] = dp[i-1][j]+1
            else:
                dp[i][j] = dp[i-1][j]
        else:
            if grid[i-1][j] == "." and grid[i][j-1] == "." and grid[i][j] == "#":
                dp[i][j] = min(dp[i-1][j],dp[i][j-1])+1
            elif grid[i][j-1] == "." and grid[i][j] == "#":
                dp[i][j] = min(dp[i][j-1]+1,dp[i-1][j])
            elif grid[i-1][j] == "." and grid[i][j] == "#":
                dp[i][j] = min(dp[i][j-1],dp[i-1][j]+1)
            else:
                dp[i][j] = min(dp[i-1][j],dp[i][j-1])
print(dp[h-1][w-1])