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:
d = input().split(" ")
h = int(d[0])
w = int(d[1])
l = []
for i in range(h):
	s = input()
	l.append(list(s))
f = 0
p = l[0][0]
a = [[201] * w for i in range(h)]
a[0][0] = 0
for i in range(1, h):
	if p == l[i][0]:
		a[i][0] = a[i-1][0]
	else:
		a[i][0] = a[i-1][0] + 1
	p = l[i][0]
p = l[0][0]
for i in range(1, w):
	if p == l[0][i]:
		a[0][i] = a[0][i-1]
	else:
		a[0][i] = a[0][i-1] + 1
	p = l[0][i]
for i in range(1, h):
	for j in range(1, w):
		x = a[i-1][j]
		y = a[i][j-1]
		if l[i-1][j] != l[i][j]:
			x += 1
		if l[i][j-1] != l[i][j]:
			y += 1
		a[i][j] = min(x, y)
if l[0][0] == "." and l[h-1][w-1] == ".":
	print(int(a[h-1][w-1]/2))
elif l[0][0] == "." and l[h-1][w-1] == "#":
	print(int((a[h-1][w-1]+1)/2))
elif l[0][0] == "#" and l[h-1][w-1] == ".":
	print(int((a[h-1][w-1]+1)/2))
elif l[0][0] == "#" and l[h-1][w-1] == "#":
	print(int((a[h-1][w-1]/2) + 1))

Submission status: Accepted

Solution code:
def main():
    import sys
    from collections import deque
    input = sys.stdin.readline

    H, W = map(int, input().split())
    grid = []
    for _ in range(H):
        grid.append(input().rstrip('\n'))

    d = [(1, 0), (0, 1)]
    que = deque()
    que.append((0, 0))
    seen = [[-1] * W for _ in range(H)]
    if grid[0][0] == '#':
        seen[0][0] = 1
    else:
        seen[0][0] = 0
    while que:
        h, w = que.popleft()
        for dh, dw in d:
            h_new, w_new = h+dh, w+dw
            if 0 <= h_new < H and 0 <= w_new < W:
                if seen[h_new][w_new] == -1:
                    if grid[h_new][w_new] == grid[h][w]:
                        seen[h_new][w_new] = seen[h][w]
                        que.appendleft((h_new, w_new))
                    else:
                        if grid[h_new][w_new] == '#':
                            seen[h_new][w_new] = seen[h][w] + 1
                        else:
                            seen[h_new][w_new] = seen[h][w]
                        que.append((h_new, w_new))
    print(seen[-1][-1])
    #[print(seen[h]) for h in range(H)]


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
from collections import deque
from heapq import heappush, heappop
h, w = map(int, input().split())
grid = [input() for _ in range(h)]

def solve(grid, h, w):
    if h == 0 or w == 0:
        return 0
    color = grid[0][0]
    cnt = 0
    if color == '#':
        cnt += 1
    dist = [[-1] * w for _ in range(h)]
    dist[0][0] = cnt
    q = []
    q.append((0, 0))
    current_color_cluster = [(0, 0)]
    while q and dist[h - 1][w - 1] == -1:
        new_q = []
        for i, j in q:
            for ii, jj in ((i + 1, j), (i, j + 1)):
                if 0 <= ii < h and 0 <= jj < w and dist[ii][jj] == -1 and grid[ii][jj] == color:
                    dist[ii][jj] = cnt
                    new_q.append((ii, jj))
        if new_q:
            current_color_cluster.extend(new_q)
            q = new_q
        elif dist[h - 1][w - 1] == -1:
            if color == '.':
                cnt += 1
            color = '#' if color == '.' else '.'
            q = current_color_cluster
            current_color_cluster = []
    return dist[h - 1][w - 1]

print(solve(grid, h, w))

Submission status: Accepted

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

ls = [[0]*W for _ in range(H)]
ls[0][0] = int(bool(s[0][0]=="#"))

for i in range(1,W):
    ls[0][i] = ls[0][i-1]+ int(bool(s[0][i]=="#" and s[0][i-1]=="."))
    
for j in range(1,H):
    ls[j][0] = ls[j-1][0]+ int(bool(s[j][0]=="#" and s[j-1][0]=="."))

for i in range(1,W):
    for j in range(1,H):
        ls[j][i] = min(ls[j][i-1]+ int(bool(s[j][i]=="#" and s[j][i-1]==".")),
                       ls[j-1][i]+ int(bool(s[j][i]=="#" and s[j-1][i]==".")))
        
print(ls[-1][-1])

Submission status: Accepted

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

class tree:
    def __init__(self):
        self.num = 0
        self.borw = 0
li2 = [[tree() for i in range(W)]for j in range(H)]
for i in range(H):
    for j in range(W):
        if li[i][j] == "#":
            li2[i][j].borw = 1
        else:
            li2[i][j].borw = 0
for i in range(H):
    for j in range(W):
        numA = 0
        numB = 0
        if i == 0 and j == 0:
            li2[i][j].num = 0
            if li2[i][j].borw == 1:
                li2[i][j].num = 1
        else:
            if i == 0:
                li2[i][j].num = li2[i][j-1].num
                if li2[i][j-1].borw == 0 and li2[i][j].borw == 1:
                    li2[i][j].num += 1
            if j == 0:
                li2[i][j].num = li2[i-1][j].num
                if li2[i-1][j].borw == 0 and li2[i][j].borw == 1:
                    li2[i][j].num += 1
            if i != 0 and j != 0:
                numA = li2[i][j-1].num
                if li2[i][j-1].borw == 0 and li2[i][j].borw == 1:
                    numA += 1
                numB = li2[i-1][j].num
                if li2[i-1][j].borw == 0 and li2[i][j].borw == 1:
                    numB += 1
                li2[i][j].num = min(numA, numB)

print(li2[H-1][W-1].num)

Submission status: Accepted

Solution code:
from collections import deque
import sys
input = sys.stdin.readline
import numpy as np

H, W = map(int, input().split())
c = [input() for _ in range(H)]
si = sj =0

dist = [[-1] * W for _ in range(H)]
dist[0][0] = 0
queue = deque()
queue.append((0,0))
move = [(1, 0), (0, 1)]#,(-1,0),(0,-1)]
while queue:
    i, j = queue.popleft()
    for di, dj in move:
        ni, nj = i+di, j+dj
        if 0 <= ni < H and 0 <= nj < W and dist[ni][nj] == -1:
            if c[ni][nj] == c[i][j]:
                dist[ni][nj] =dist[i][j]
                queue.appendleft((ni,nj))
            else:
                dist[ni][nj] =dist[i][j] +1
                queue.append((ni,nj))

if dist[-1][-1]%2==1:
  ans=dist[-1][-1]//2+1
else:
  if c[0][0]==".":
    ans=dist[-1][-1]//2
  else:
    ans=dist[-1][-1]//2+1

print(ans)

Submission status: Accepted

Solution code:
import sys,collections as cl,bisect as bs
sys.setrecursionlimit(100000)
input = sys.stdin.readline
mod = 10**9+7
Max = sys.maxsize
def l(): #intのlist
    return list(map(int,input().split()))
def m(): #複数文字
    return map(int,input().split())
def onem(): #Nとかの取得
    return int(input())
def s(x): #圧縮
    a = []
    if len(x) == 0:
        return []
    aa = x[0]
    su = 1
    for i in range(len(x)-1):
        if aa != x[i+1]:
            a.append([aa,su])
            aa = x[i+1]
            su = 1
        else:
            su += 1
    a.append([aa,su])
    return a
def jo(x): #listをスペースごとに分ける
    return " ".join(map(str,x))
def max2(x): #他のときもどうように作成可能
    return max(map(max,x))
def In(x,a): #aがリスト(sorted)
    k = bs.bisect_left(a,x)
    if k != len(a) and a[k] ==  x:
        return True
    else:
        return False
"""
def nibu(x,n,r):
    ll = 0
    rr = r
    while True:
        mid = (ll+rr)//2

    if rr == mid:
        return ll
    if (ここに評価入れる):
        rr = mid
    else:
        ll = mid+1
"""


H,W = m()

po = [list(input()) for i in range(H)]

aaa = [[[mod,0] for i in range(W)] for j in range(H)]
aa = [[[mod,0] for i in range(W)] for j in range(H)]

if po[0][0] == "#":
    aaa[0][0] = [1,3]
else:
    aaa[0][0] = [0,0]

for i in range(H):
    if i == 0:
        for j in range(1,W):
            if po[i][j] == "#":
                if aaa[i][j-1][1] == 0:
                    aaa[i][j][0] = min(aaa[i][j][0],aaa[i][j-1][0]+1)
                    aaa[i][j][1] = 3
                elif aaa[i][j-1][1] == 1 or aaa[i][j-1][1] == 3:
                    aaa[i][j][0] = min(aaa[i][j][0],aaa[i][j-1][0])
                    aaa[i][j][1] = 3
            else:
                aaa[i][j][0] = min(aaa[i][j][0],aaa[i][j-1][0])

    else:
        for j in range(W):
            if j == 0:
                if po[i][j] == "#":
                    if aaa[i-1][j][1] == 0:
                        aaa[i][j][0] = min(aaa[i][j][0],aaa[i-1][j][0]+1)
                        aaa[i][j][1] = 3
                    elif aaa[i-1][j][1] == 3 or aaa[i-1][j][1] == 2:
                        aaa[i][j][0] = min(aaa[i][j][0],aaa[i-1][j][0])
                        aaa[i][j][1] = 3
                else:
                    aaa[i][j][0] = min(aaa[i][j][0],aaa[i-1][j][0])
            else:
                if po[i][j] == "#":
                    if aaa[i-1][j][1] == 0 or aaa[i-1][j][1] == 1:
                        if aaa[i][j-1][1] == 0 or aaa[i][j-1][1] == 2:
                            aaa[i][j][0] = min(aaa[i][j][0],aaa[i][j-1][0]+1,aaa[i-1][j][0]+1)
                            aaa[i][j][1] = 3
                        elif aaa[i][j-1][1] == 1:
                            aaa[i][j][0] = min(aaa[i][j][0],aaa[i][j-1][0],aaa[i-1][j][0]+1)
                            aaa[i][j][1] = 3
                        elif aaa[i][j-1][1] == 3:
                            aaa[i][j][0] = min(aaa[i][j][0],aaa[i][j-1][0],aaa[i-1][j][0]+1)
                            aaa[i][j][1] = 3
                    elif aaa[i-1][j][1] == 2:
                        if aaa[i][j-1][1] == 0 or aaa[i][j-1][1] == 2:
                            aaa[i][j][0] = min(aaa[i][j][0],aaa[i][j-1][0]+1,aaa[i-1][j][0])
                            aaa[i][j][1] = 3
                        elif aaa[i][j-1][1] == 1:
                            aaa[i][j][0] = min(aaa[i][j][0],aaa[i][j-1][0],aaa[i-1][j][0])
                            aaa[i][j][1] = 3
                        elif aaa[i][j-1][1] == 3:
                            aaa[i][j][0] = min(aaa[i][j][0],aaa[i][j-1][0],aaa[i-1][j][0])
                            aaa[i][j][1] = 3
                    elif aaa[i-1][j][1] == 3:
                        if aaa[i][j-1][1] == 0 or aaa[i][j-1][1] == 2:
                            aaa[i][j][0] = min(aaa[i][j][0],aaa[i][j-1][0]+1,aaa[i-1][j][0])
                            aaa[i][j][1] = 3
                        elif aaa[i][j-1][1] == 1:
                            aaa[i][j][0] = min(aaa[i][j][0],aaa[i][j-1][0],aaa[i-1][j][0])
                            aaa[i][j][1] = 3
                        elif aaa[i][j-1][1] == 3:
                            aaa[i][j][0] = min(aaa[i][j][0],aaa[i][j-1][0],aaa[i-1][j][0])
                            aaa[i][j][1] = 3
                else:
                    aaa[i][j][0] = min(aaa[i][j][0],aaa[i][j-1][0],aaa[i-1][j][0])

if po[0][0] == ".":
    aa[0][0] = [2,3]
else:
    aa[0][0] = [1,0]

for i in range(H):
    if i == 0:
        for j in range(1,W):
            if po[i][j] == ".":
                if aa[i][j-1][1] == 0:
                    aa[i][j][0] = min(aa[i][j][0],aa[i][j-1][0]+1)
                    aa[i][j][1] = 3
                elif aa[i][j-1][1] == 1 or aa[i][j-1][1] == 3:
                    aa[i][j][0] = min(aa[i][j][0],aa[i][j-1][0])
                    aa[i][j][1] = 1
            else:
                aa[i][j][0] = min(aa[i][j][0],aa[i][j-1][0])

    else:
        for j in range(W):
            if j == 0:
                if po[i][j] == ".":
                    if aa[i-1][j][1] == 0:
                        aa[i][j][0] = min(aa[i][j][0],aa[i-1][j][0]+1)
                        aa[i][j][1] = 3
                    elif aa[i-1][j][1] == 3 or aa[i-1][j][1] == 2:
                        aa[i][j][0] = min(aa[i][j][0],aa[i-1][j][0])
                        aa[i][j][1] = 2
                else:
                    aa[i][j][0] = min(aa[i][j][0],aa[i-1][j][0])
            else:
                if po[i][j] == ".":
                    if aa[i-1][j][1] == 0 or aa[i-1][j][1] == 1:
                        if aa[i][j-1][1] == 0 or aa[i][j-1][1] == 2:
                            aa[i][j][0] = min(aa[i][j][0],aa[i][j-1][0]+1,aa[i-1][j][0]+1)
                            aa[i][j][1] = 3
                        elif aa[i][j-1][1] == 1:
                            aa[i][j][0] = min(aa[i][j][0],aa[i][j-1][0],aa[i-1][j][0]+1)
                            aa[i][j][1] = 3
                        elif aa[i][j-1][1] == 3:
                            aa[i][j][0] = min(aa[i][j][0],aa[i][j-1][0],aa[i-1][j][0]+1)
                            aa[i][j][1] = 3
                    elif aa[i-1][j][1] == 2:
                        if aa[i][j-1][1] == 0 or aa[i][j-1][1] == 2:
                            aa[i][j][0] = min(aa[i][j][0],aa[i][j-1][0]+1,aa[i-1][j][0])
                            aa[i][j][1] = 3
                        elif aa[i][j-1][1] == 1:
                            aa[i][j][0] = min(aa[i][j][0],aa[i][j-1][0],aa[i-1][j][0])
                            aa[i][j][1] = 3
                        elif aa[i][j-1][1] == 3:
                            aa[i][j][0] = min(aa[i][j][0],aa[i][j-1][0],aa[i-1][j][0])
                            aa[i][j][1] = 3
                    elif aa[i-1][j][1] == 3 or aa[i][j-1][1] == 2:
                        if aa[i][j-1][1] == 0:
                            aa[i][j][0] = min(aa[i][j][0],aa[i][j-1][0]+1,aa[i-1][j][0])
                            aa[i][j][1] = 3
                        elif aa[i][j-1][1] == 1:
                            aa[i][j][0] = min(aa[i][j][0],aa[i][j-1][0],aa[i-1][j][0])
                            aa[i][j][1] = 3
                        elif aa[i][j-1][1] == 3:
                            aa[i][j][0] = min(aa[i][j][0],aa[i][j-1][0],aa[i-1][j][0])
                            aa[i][j][1] = 3
                else:
                    aa[i][j][0] = min(aa[i][j][0],aa[i][j-1][0],aa[i-1][j][0])

print(min(aaa[-1][-1][0],aa[-1][-1][0]))

Submission status: Accepted

Solution code:
import numpy as np

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

s=[]

for i in range(H):
    s.append(str(input()))
    
# s[i][0] to s[i][W-1] 

pat_mat=[]

for i in range(H):
    if i ==0:
        if s[0][0] == ".":
            pat_mat.append([0])
        else:
            pat_mat.append([1])
        if W>1:
            for j in range(1,W):
                if s[0][j] == ".":
                    pat_mat[0].append(pat_mat[0][j-1])
                else:
                    if s[0][j-1]==s[0][j]:
                        pat_mat[0].append(int(pat_mat[0][j-1]))
                    else:
                        pat_mat[0].append(int(pat_mat[0][j-1]+1))
    else:
        if s[i][0] == ".":
            pat_mat.append([pat_mat[i-1][0]])
        else:
            if s[i-1][0]==s[i][0]:
                pat_mat.append([pat_mat[i-1][0]])
            else:
                
                pat_mat.append([pat_mat[i-1][0]+1])
        if W>1:
            for j in range(1,W):
                if s[i][j] == ".":
                    pat_mat[i].append(min(pat_mat[i][j-1],pat_mat[i-1][j]))
                else:
                    if s[i][j-1]==s[i][j]:
                        cand_l = pat_mat[i][j-1]
                    else:
                        cand_l = pat_mat[i][j-1]+1
                    if s[i][j]==s[i-1][j]:
                        cand_t= pat_mat[i-1][j]
                    else:
                        cand_t= pat_mat[i-1][j]+1

                    pat_mat[i].append(min(cand_l,cand_t))
                        
                    
print(int(pat_mat[H-1][W-1]))

Submission status: Accepted

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

for i in range(H):
    for j in range(W):
        # (0,0)
        if i == 0 and j == 0:
            if s[i][j] == "#":
                dp[i][j] = 1
        # 1行目
        elif i == 0:
            if s[i][j-1] == "#":
                dp[i][j] = dp[i][j-1]
            else:
                if s[i][j] == "#":
                    dp[i][j] = dp[i][j-1] + 1
                else:
                    dp[i][j] = dp[i][j-1]
        # 1列目
        elif j == 0:
            if s[i-1][j] == "#":
                dp[i][j] = dp[i-1][j]
            else:
                if s[i][j] == "#":
                    dp[i][j] = dp[i-1][j] + 1
                else:
                    dp[i][j] = dp[i-1][j]
        else:
            # 上か左どちらの値が小さいか
            # 左側の方が小さい
            if dp[i-1][j] > dp[i][j-1]:
                if s[i][j-1] == "#":
                    dp[i][j] = dp[i][j-1]
                else:
                    if s[i][j] == "#":
                        dp[i][j] = dp[i][j-1] + 1
                    else:
                        dp[i][j] = dp[i][j-1]
            # 上側の方が小さい
            elif dp[i-1][j] < dp[i][j-1]:
                if s[i-1][j] == "#":
                    dp[i][j] = dp[i-1][j]
                else:
                    if s[i][j] == "#":
                        dp[i][j] = dp[i-1][j] + 1
                    else:
                        dp[i][j] = dp[i-1][j]
            # 等しい
            else:
                if s[i-1][j] == "#" or s[i][j-1] == "#":
                    dp[i][j] = dp[i-1][j]
                else:
                    if s[i][j] == "#":
                        dp[i][j] = dp[i-1][j] + 1
                    else:
                        dp[i][j] = dp[i-1][j]

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

Submission status: Accepted

Solution code:
### ----------------
### ここから
### ----------------

import sys
from io import StringIO
import unittest

def yn(b):
    print("Yes" if b==1 else "No")
    return

def resolve():
    readline=sys.stdin.readline

    #n,m,k=map(int, readline().rstrip().split())
    #arr=list(map(int, readline().rstrip().split()))
    #n=int(readline())
    #ss=readline().rstrip()
    #yn(1)
    h,w=map(int, readline().rstrip().split())
    masu=[]
    count=[[-1 for i in range(w)] for j in range(h)]
    for i in range(h):
        masu.append(readline().rstrip())

    if masu[0][0]=="#":
        count[0][0]=1
    else:
        count[0][0]=0

    for y in range(h):
        for x in range(w):
            if y==0 and x==0:
                continue

            left=999999
            up=999999
            if x > 0: # get left
                if masu[y][x]==".":
                    left=count[y][x-1]
                else: #
                    if masu[y][x-1]==".":
                        left=count[y][x-1]+1
                    else:
                        left=count[y][x-1]
            if y > 0: # get up
                if masu[y][x]==".":
                    up=count[y-1][x]
                else: #
                    if masu[y-1][x]==".":
                        up=count[y-1][x]+1
                    else:
                        up=count[y-1][x]
            count[y][x]=min(left,up)
    print(count[h-1][w-1])
    return

if 'doTest' not in globals():
    resolve()
    sys.exit()

### ----------------
### ここまで 
### ----------------

Submission status: Accepted

Solution code:
h, w = map(int, input().split())
s = [list(input()) for _ in range(h)]
dp = [[float('inf') for i in range(w)] for j in range(h)]
if s[0][0] == '.':
    dp[0][0] = 0
    total = 0
else:
    dp[0][0] = 1
    total = 1
for i in range(1,w):
    if s[0][i] == '#':
        if s[0][i-1] == '#':
            dp[0][i] = total
        else:
            total += 1
            dp[0][i] = total
    else:
        dp[0][i] = total
if s[0][0] == '.':
    total = 0
else:
    total = 1
for i in range(1,h):
    if s[i][0] == '#':
        if s[i-1][0] == '#':
            dp[i][0] = total
        else:
            total += 1
            dp[i][0] = total
    else:
        dp[i][0] = total
for i in range(1,h):
    for j in range(1,w):
        if s[i][j] == '#':
            if s[i-1][j] == '#' and s[i][j-1] == '#':
                dp[i][j] = min(dp[i-1][j], dp[i][j-1])
            elif s[i-1][j] == '#':
                dp[i][j] = min(dp[i-1][j], dp[i][j-1] + 1)
            elif s[i][j-1] == '#':
                dp[i][j] = min(dp[i][j-1], dp[i-1][j] + 1)
            else:
                dp[i][j] = min(dp[i-1][j] + 1, dp[i][j-1] + 1)
        else:
            dp[i][j] = min(dp[i-1][j], dp[i][j-1])
print(dp[h-1][w-1])

Submission status: Accepted

Solution code:
import sys


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


def main():
    H, W = map(int, input().split())

    S = [list(input()) for _ in range(H)]
    # print(S)
    check = [[10 ** 9 for i in range(W)] for j in range(H)]
    if S[0][0] == "#":
        check[0][0] = 1
    else:
        check[0][0] = 0
    for i in range(1, W):
        left = check[0][i - 1]
        if S[0][i] == "#":
            if S[0][i - 1] == "#":
                check[0][i] = left
            else:
                check[0][i] = left + 1
        else:
            check[0][i] = left
    for i in range(1, H):
        up = check[i - 1][0]
        if S[i][0] == "#":
            if S[i - 1][0] == "#":
                check[i][0] = up
            else:
                check[i][0] = up + 1
        else:
            check[i][0] = up
    for i in range(1, H):
        for j in range(1, W):
            # print(S[i][j])
            left = check[i][j - 1]
            up = check[i - 1][j]
            if S[i][j] == "#":
                if S[i][j - 1] == "#" and S[i - 1][j] == "#":
                    check[i][j] = min(left, up)
                elif S[i][j - 1] != "#" and S[i - 1][j] == "#":
                    check[i][j] = min(left + 1, up)
                elif S[i][j - 1] == "#" and S[i - 1][j] != "#":
                    check[i][j] = min(left, up + 1)
                else:
                    check[i][j] = min(left, up) + 1
            else:
                check[i][j] = min(left, up)
    # print(check)
    print(check[-1][-1])


main()

Submission status: Accepted

Solution code:
from math import *

n, m = map(int, input().split())
a = []
for i in range(n):
    a.append([1 if j == '.' else 0 for j in input()])
dp = []
for i in range(n):
    dp.append([n*m] * m)

dp[0][0] = 1 - a[0][0]

for i in range(n):
    for j in range(m):
        #print(i, j)
        if i == j == 0:
            continue
        if a[i][j]:
            if i > 0:
                dp[i][j] = min(dp[i][j], dp[i-1][j])
            if j > 0:
                dp[i][j] = min(dp[i][j], dp[i][j-1])
        else:
            if i > 0 and not a[i-1][j]:
                dp[i][j] = min(dp[i][j], dp[i-1][j])
            elif i > 0:
                dp[i][j] = min(dp[i][j], dp[i-1][j] + 1)
                
            if j > 0 and not a[i][j-1]:
                dp[i][j] = min(dp[i][j], dp[i][j-1])
            elif j > 0:
                dp[i][j] = min(dp[i][j], dp[i][j-1] + 1)

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

Submission status: Accepted

Solution code:
h, w= map(int, input().split())
maze = [input() for i in range(h)]
maze_num =[[0] for i in range(h)]



maze_num =[[0]*w for i in range(h)]
for i in range(h):
    for k in range(w):
        maze_num[i][k] = [float("inf"), maze[i][k]]

maze_num[0][0][0] = 0

for i in range(h):
    for k in range(w):
        if i == h-1 and k ==w-1:
            break
        if k != w-1:
            if maze_num[i][k][1] =="#" and maze_num[i][k+1][1] ==".":
                maze_num[i][k+1][0] = min(maze_num[i][k+1][0], maze_num[i][k][0]+ 1)
            else:
                maze_num[i][k+1][0] = min(maze_num[i][k+1][0], maze_num[i][k][0])
        if i != h-1:
            if maze_num[i][k][1] =="#" and maze_num[i+1][k][1] ==".":
                maze_num[i+1][k][0] = min(maze_num[i+1][k][0], maze_num[i][k][0]+ 1)
            else:
                maze_num[i+1][k][0] = min(maze_num[i+1][k][0], maze_num[i][k][0])

if maze_num[h-1][w-1][1] =="#":
    print(maze_num[h-1][w-1][0] + 1)
else:
    print(maze_num[h-1][w-1][0])

Submission status: Accepted

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

dp=[[-1 for i in range(W)] for j in range(H)]
if s[0][0]=='#':
    dp[0][0]=1
else:
    dp[0][0]=0
for i in range(1,W):
    if s[0][i-1]=='.' and s[0][i]=='#':
        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(0,W):
        fromup=10**5
        fromleft=10**5
        if s[i-1][j]=='.' and s[i][j]=='#':
            fromup=dp[i-1][j]+1
        else:
            fromup=dp[i-1][j]
        if j!=0:
            if s[i][j-1]=='.' and s[i][j]=='#':
                fromleft=dp[i][j-1]+1
            else:
                fromleft=dp[i][j-1]
        dp[i][j]=min(fromup,fromleft)

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

Submission status: Accepted

Solution code:
import sys
def MI(): return map(int, sys.stdin.readline().split())

H,W = MI()
s = [list(input()) for _ in range(H)]
dp = [[0 for _ in range(W)] for _ in range(H)]

if s[0][0]=='#':
	dp[0][0] = 1

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

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

def next(start, goal, start_value):
	if start=='.' and goal=='#':
		start_value += 1
	return start_value

for i in range(1,H):
	for j in range(1,W):
		# print(next(s[i][j-1],s[i][j],dp[i][j-1]),next(s[i-1][j],s[i][j],dp[i-1][j]))
		dp[i][j] = min(next(s[i][j-1],s[i][j],dp[i][j-1]), next(s[i-1][j],s[i][j],dp[i-1][j]))

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

Submission status: Accepted

Solution code:
h, w = map(int, input().split())
s = []
s.append(["."] * (w + 1))
for i in range(h):
    s.append(["."] + list(input()))
s2 = []
for i in range(h + 1):
    s2.append([0] * (w + 1))

for i in range(w - 1):
    if s[1][i + 1] == "#":
        if s[1][i] != "#":
            s2[0][i + 2] = s2[0][i + 1] + 1
        else:
            s2[0][i + 2] = s2[0][i + 1]
    else:
        s2[0][i + 2] = s2[0][i + 1]
for i in range(h - 1):
    if s[i + 1][1] == "#":
        if s[i][1] != "#":
            s2[i + 2][0] = s2[i + 1][0] + 1
        else:
            s2[i + 2][0] = s2[i + 1][0]
    else:
        s2[i + 2][0] = s2[i + 1][0]

for i in range(h):
    for j in range(w):
        if s[i + 1][j + 1] == ".":
            s2[i + 1][j + 1] = min(s2[i][j + 1], s2[i + 1][j])
        else:
            if s[i][j + 1] == "#":
                if s[i + 1][j] == "#":
                    s2[i + 1][j + 1] = min(s2[i][j + 1], s2[i + 1][j])
                else:
                    s2[i + 1][j + 1] = min(s2[i][j + 1], s2[i + 1][j] + 1)
            else:
                if s[i + 1][j] == "#":
                    s2[i + 1][j + 1] = min(s2[i][j + 1] + 1, s2[i + 1][j])
                else:
                    s2[i + 1][j + 1] = min(s2[i][j + 1], s2[i + 1][j]) + 1
print(s2[h][w])

Submission status: Accepted

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

def BFS(i0=0):
    Q = deque([i0])
    D = [-1] * (H * W)
    D[i0] = X[0][0]
    while Q:
        x = Q.popleft()
        i, j = x // W, x % W
        for di, dj in ((0, 1), (1, 0)):
            ni, nj = i + di, j + dj
            if 0 <= ni < H and 0 <= nj < W:
                y = ni * W + nj
                if X[ni][nj] == X[i][j]:
                    if D[y] == -1:
                        D[y] = D[x]
                        Q.appendleft(y)
                else:
                    if D[y] == -1:
                        D[y] = D[x] + 1
                        Q.append(y)
                        
    return D

print(BFS(0)[-1] + 1 >> 1)

Submission status: Accepted

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

paint=((1,0),(0,1))
dp=[[0]*(w) for _ in range(h)] # そのマスにたどり着くまでに何回色の変更を経験するか

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

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

if s[0][0]=='.' and s[h-1][w-1]=='.':
    print(dp[h-1][w-1]//2)
    exit()
    
if (s[0][0]=='#' and s[h-1][w-1]=='.') or (s[0][0]=='.' and s[h-1][w-1]=='#'):
    print((dp[h-1][w-1]+1)//2)
    exit()

if s[0][0]=='#' and s[h-1][w-1]=='#':
    print(dp[h-1][w-1]//2+1)
    exit()

Submission status: Accepted

Solution code:
from itertools import product


def read():
    H, W = list(map(int, input().strip().split()))
    S = list()
    S.append(list('#' * (W+2)))
    for i in range(H):
        s = list(input().strip())
        S.append(['#'] + s + ['#'])
    S.append(list('#' * (W+2)))
    return H, W, S


def solve(H, W, S, INF=10000):
    field = [[INF for j in range(W+2)] for i in range(H+2)]
    field[1][1] = 1 if S[1][1] == '#' else 0
    for j in range(2, W+1):
        u = 1 if S[1][j-1] == '.' and S[1][j] == '#' else 0
        field[1][j] = field[1][j-1] + u
    for i, j in product(range(2, H+1), range(1, W+1)):
        # 上から
        if S[i-1][j] == '.' and S[i][j] == '#':
            u = field[i-1][j] + 1  
        else:
            u = field[i-1][j]
        # 左から
        if S[i][j-1] == '.' and S[i][j] == '#':
            v = field[i][j-1] + 1  
        else:
            v = field[i][j-1]
        field[i][j] = min(u, v)
    return field[H][W]


if __name__ == '__main__':
    inputs = read()
    print("%s" % solve(*inputs))

Submission status: Accepted

Solution code:
h,w=map(int,input().split())
li=[[]]*h
for i in range(h):
  li[i]=[str(k) for k in input()]
  
lil=[[0 for i in range(w)] for j in range(h)]
#[h][w]=着くまでの最小操作回数
for i in range(h):
  for j in range(w):
    if i==0 and j==0:
      if li[0][0]==".":
        lil[0][0]=0
      else:
        lil[0][0]=1
    elif i==0:
      if li[i][j]==li[i][j-1] or li[i][j]==".":
        lil[i][j]=lil[i][j-1]
      elif li[i][j]=="#":
        lil[i][j]=lil[i][j-1]+1
    elif j==0:
      if li[i][j]==li[i-1][j] or li[i][j]==".":
        lil[i][j]=lil[i-1][j]
      elif li[i][j]=="#":
        lil[i][j]=lil[i-1][j]+1
    else:
      if li[i][j]==li[i-1][j] or li[i][j]==".":
        ko=lil[i-1][j]
      elif li[i][j]=="#":
        ko=lil[i-1][j]+1
      if li[i][j]==li[i][j-1] or li[i][j]==".":
        ks=lil[i][j-1]
      elif li[i][j]=="#":
        ks=lil[i][j-1]+1
      lil[i][j]=min(ko,ks)
print(lil[h-1][w-1])