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:
#!/usr/bin/env python3

h, w = list(map(int, input().split()))

ss = [list(str(input())) for _ in range(h)]

dp = [[100*100 for _ in range(w)] for i in range(h)]  # dp[h][w]

if ss[0][0] == "#":
    dp[0][0] = 1
else:
    dp[0][0] = 0
# print(dp)

for h_tmp in range(0, h):
    for w_tmp in range(0, w):
        if w_tmp > 0:
            # print(dp[h_tmp][w_tmp-1])
            if ss[h_tmp][w_tmp-1] == "." and ss[h_tmp][w_tmp] == "#":
                dp[h_tmp][w_tmp] = min(dp[h_tmp][w_tmp], dp[h_tmp][w_tmp-1]+1)
            else:
                dp[h_tmp][w_tmp] = min(dp[h_tmp][w_tmp], dp[h_tmp][w_tmp-1])
        if h_tmp > 0:
            # print(dp[h_tmp][w_tmp-1])
            if ss[h_tmp-1][w_tmp] == "." and ss[h_tmp][w_tmp] == "#":
                dp[h_tmp][w_tmp] = min(dp[h_tmp][w_tmp], dp[h_tmp-1][w_tmp]+1)
            else:
                dp[h_tmp][w_tmp] = min(dp[h_tmp][w_tmp], dp[h_tmp-1][w_tmp])

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

Submission status: Accepted

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

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(10**6)
def main():
    h, w = map(int, input().split())
    s = [input() for _ in range(h)]
    dp = [[10**5] * w for _ in range(h)]
    def func(temp, now, flag):
        x, y = now
        if y > h - 1 or x > w - 1:
            return 10**6
        if s[y][x] == "#":
            if not flag:
                temp += 1
            flag = True
        else:
            flag = False
        if x == w-1 and y == h-1:
            return temp
        if dp[y][x] <= temp:
            return 10**6
        dp[y][x] = temp
        piyo = []
        return min(func(temp, (x + 1, y), flag), func(temp, (x, y + 1), flag))
    print(func(0, (0, 0), False))
main()

Submission status: Accepted

Solution code:
from collections import deque
h,w = map(int,input().split())
map_input = [list(input()) for i in range(h)]

score = [[10**10]*(w+1) for i in range(h+1)]
score[0][1] = 0
score[1][0] = 0

for i in range(h):
    for j in range(w):
        tmp1 = score[i][j+1] + (map_input[i][j]=='#' and (i==0 or map_input[i-1][j]=='.'))
        tmp2 = score[i+1][j] + (map_input[i][j]=='#' and (j==0 or map_input[i][j-1]=='.'))
        score[i+1][j+1]=min(tmp1,tmp2)
print(score[-1][-1])

Submission status: Accepted

Solution code:
import numpy as np
H,W=map(int,input().split(' '))
S = (np.array([list(input()) for i in range(H)])=='#')*1
flg=[[float("inf")]*W for i in range(H)]
flg[0][0]=S[0][0]

for i in range(H):
    for j in range(W):
        if i<H-1:
            if S[i][j]==0 and S[i+1][j]==1:
                flg[i+1][j] = min(flg[i][j]+1,flg[i+1][j])
            else:
                flg[i+1][j] = min(flg[i][j],flg[i+1][j])
        if j<W-1:
            if S[i][j]==0 and S[i][j+1]==1:
                flg[i][j+1] = min(flg[i][j]+1,flg[i][j+1])
            else:
                flg[i][j+1] = min(flg[i][j],flg[i][j+1])
print(flg[-1][-1])

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(10**6) #再帰関数の上限
import math
from copy import copy, deepcopy
from operator import itemgetter
from bisect import bisect_left, bisect, bisect_right#2分探索
#bisect_left(l,x), bisect(l,x)#aはソート済みである必要あり。aの中からx未満の要素数を返す。rightだと以下
from collections import deque 
#deque(l), pop(), append(x), popleft(), appendleft(x)
##listでqueの代用をするとO(N)の計算量がかかってしまうので注意
from collections import Counter#文字列を個数カウント辞書に、
#S=Counter(l),S.most_common(x),S.keys(),S.values(),S.items()
from itertools import accumulate#累積和
#list(accumulate(l))
from heapq import heapify,heappop,heappush
#heapify(q),heappush(q,a),heappop(q) #q=heapify(q)としないこと、返り値はNone
#import fractions#古いatcoderコンテストの場合GCDなどはここからimportする


def input(): return sys.stdin.readline()[:-1]
def printl(li): print(*li, sep="\n")
def argsort(s, return_sorted=False): 
    inds=sorted(range(len(s)), key=lambda k: s[k])
    if return_sorted: return inds, [s[i] for i in inds]
    return inds
def alp2num(c,cap=False): return ord(c)-97 if not cap else ord(c)-65
def num2alp(i,cap=False): return chr(i+97) if not cap else chr(i+65)

def dfs(H,W,L):
    d=0
    c=True
    if L[0][0]==False:
        d=1
        c=False
    q=deque([(d*10000,c)])
    dxs=((0,1),(1,0))
    visited=[False]*10000
    while len(q):
        
        #print(q)
        dxy,c=q.popleft()#ここをpopleftにすると幅優先探索BFSになる
        d,xy=divmod(dxy,10000)
        x,y=divmod(xy,100)
        if visited[xy]: continue
        visited[xy]=True
        if x==H-1 and y==W-1:
            return d
        for dx in dxs:
            nx=x+dx[0]
            ny=y+dx[1]
            if nx>=H or ny>=W:
                continue
            if visited[nx*100+ny]:continue

            if L[nx][ny] or c==False:
                q.appendleft((d*10000+nx*100+ny,L[nx][ny]))
            else:
                q.append(((d+1)*10000+nx*100+ny,False))

                


def main():
    mod = 10**9+7
    #w.sort(key=itemgetter(1),reversed=True)  #二個目の要素で降順並び替え

    #N = int(input())
    H,W = map(int, input().split())
    #A = tuple(map(int, input().split())) #1行ベクトル
    L = list(list(input()) for i in range(H)) #改行ベクトル
    #S = tuple(tuple(map(int, input().split())) for i in range(N)) #改行行列
    #Lt=[[True]*H for _ in range(W)]
    for i in range (H):
        for j in range(W):
            if L[i][j]=='#':
                L[i][j]=False
            else:
                L[i][j]=True
            
    ans=dfs(H,W,L)

    print(ans)


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
h,w = map(int,input().split())
grid = []
for _ in range(h):
    grid.append(list(input()))
 
dp = [[0]*(w+1) for i in range(h+1)]
#dp[i][j] = i,jでの最小の操作回数
 
if grid[0][0] == '#':
    dp[0][0] += 1
 
for i in range(1,h):
    p = 0
    if grid[i][0] == '#' and grid[i-1][0] == '.':
        p += 1
    dp[i][0] = dp[i-1][0] + p
 
for i in range(1,w):
    p = 0
    if grid[0][i] == '#' and grid[0][i-1] == '.':
        p += 1
    dp[0][i] = dp[0][i-1] + p
 
for x in range(1,h):
    for y in range(1,w):
        a,b = 0,0
        if grid[x][y] == '#' and grid[x-1][y] == '.':
            a += 1
        if grid[x][y] == '#' and grid[x][y-1] == '.':
            b += 1
        dp[x][y] = min(dp[x-1][y] + a,dp[x][y-1] + b)
print(dp[h-1][w-1])
#print(dp)

Submission status: Accepted

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

s = []

for i in range(H):

    S = list(input())
    s.append(S)

dis = [[float("inf")] * W for i in range(H)]

if s[0][0] == "#":
    dis[0][0] = 1
else:
    dis[0][0] = 0

for i in range(H):

    for j in range(W):

        if i != H-1:

            if s[i][j] == "." and s[i+1][j] == "#":

                dis[i+1][j] = min(dis[i][j] + 1,dis[i+1][j])

            else:
                dis[i+1][j] = min(dis[i][j],dis[i+1][j])

        if j != W-1:
            if s[i][j] == "." and s[i][j+1] == "#":

                dis[i][j+1] = min(dis[i][j] + 1,dis[i][j+1])

            else:
                dis[i][j+1] = min(dis[i][j],dis[i][j+1])

print (dis[-1][-1])

Submission status: Accepted

Solution code:
import sys
from collections import *
import heapq
import math
import bisect
from itertools import permutations,accumulate,combinations,product
from fractions import gcd
def input():
    return sys.stdin.readline()[:-1]
def ruiseki(lst):
    return [0]+list(accumulate(lst))
mod=pow(10,9)+7
al=[chr(ord('a') + i) for i in range(26)]

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

d=deque([[0,0]])
itta=[[float('inf')]*w for i in range(h)]
if s[0][0]=="#":
    itta[0][0]=1
else:
    itta[0][0]=0

# print(itta)
ans=0
for i in range(h+w-2):
    # print(itta)
    for j in range(len(d)):
        now=d.popleft()
        nh,nw=now
        cnt=itta[nh][nw]
        if nh+1<h:
            tmp=cnt
            if s[nh][nw]=="." and s[nh+1][nw]=="#":
                tmp+=1
            if itta[nh+1][nw]==float('inf'):
                d.append([nh+1,nw])
            itta[nh+1][nw]=min(itta[nh+1][nw],tmp)
        if nw+1<w:
            tmp=cnt
            if s[nh][nw]=="." and s[nh][nw+1]=="#":
                tmp+=1
            if itta[nh][nw+1]==float('inf'):
                d.append([nh,nw+1])
            itta[nh][nw+1]=min(itta[nh][nw+1],tmp)

# print(itta)
# for i in range(len(d)):
print(itta[-1][-1])

Submission status: Accepted

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

grid_to_num = {"#":1, ".":0}

blacks[0][0] = grid_to_num[grid[0][0]]
for j in range(1, W):
    blacks[0][j] = blacks[0][j-1] + grid_to_num[grid[0][j]] * (1-grid_to_num[grid[0][j-1]])
for i in range(1, H):
    blacks[i][0] = blacks[i-1][0] + grid_to_num[grid[i][0]] * (1-grid_to_num[grid[i-1][0]])
    for j in range(1, W):
        blacks[i][j] = blacks[i][j-1] + grid_to_num[grid[i][j]] * (1-grid_to_num[grid[i][j-1]])
        blacks[i][j] = min(blacks[i-1][j] + grid_to_num[grid[i][j]] * (1-grid_to_num[grid[i-1][j]]), blacks[i][j])

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

Submission status: Accepted

Solution code:
#A
H,W = map(int,input().split())
G = [list(str(input())) for _ in range(H)]
inf = float("inf")

dist = [[inf for w in range(W)] for h in range(H)]

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

for i in range(H):
    for j in range(W):
        if i == 0 and j == 0:
            pass
        elif j == 0:
            dist[i][j] = dist[i-1][j]
            if G[i][j] == "#" and G[i-1][j] != "#":
                dist[i][j]+=1
        elif i == 0:
            dist[i][j] = dist[i][j-1]
            if G[i][j] == "#" and G[i][j-1] != "#":
                dist[i][j]+=1
        else:
            d1 = dist[i-1][j]
            d2 = dist[i][j-1]
            if G[i][j] == "#" and G[i-1][j] != "#":
                d1+=1
            if G[i][j] == "#" and G[i][j-1] != "#":
                d2+=1
            dist[i][j] = min(d1,d2)
        

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

Submission status: Accepted

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


#def sur(x):
#    res=[]
#    if x+1<=w-1:
#        res.append((x+1,y))
#    if y+1<=h-1:
#        res.append((x,y+1))
#    return res


dp=[[-1]*w for index1 in range(h)]
if s[0][0]=='.':
    dp[0][0]=0
else:
    dp[0][0]=1

temp=s[0][0]
for index2 in range(1,w):
    if temp=='.' and s[0][index2]=='#':
        dp[0][index2]=dp[0][index2-1]+1
    else:
        dp[0][index2]=dp[0][index2-1]
    temp=s[0][index2]

temp=s[0][0]
for index3 in range(1,h):
    if temp=='.' and s[index3][0]=='#':
        dp[index3][0]=dp[index3-1][0]+1
    else:
        dp[index3][0]=dp[index3-1][0]
    temp=s[index3][0]


for i in range(1,h):
    for j in range(1,w):
        if s[i][j]=='#':
            if s[i-1][j]=='.':
                if s[i][j-1]=='.':
                    dp[i][j]=min(dp[i-1][j]+1,dp[i][j-1]+1)
                else:
                    dp[i][j]=min(dp[i-1][j]+1,dp[i][j-1])
            else:
                if s[i][j-1]=='.':
                    dp[i][j]=min(dp[i-1][j],dp[i][j-1]+1)
                else:
                    dp[i][j]=min(dp[i-1][j],dp[i][j-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:
H, W = map(int, input().split())
s = [list(input()) for _ in range(H)]

dp = [[float("inf")] * W for _ in range(H)]
if s[0][0] == "#":
    dp[0][0] = 1
else:
    dp[0][0] = 0

dxdy = [(1, 0), (0, 1)]
for y in range(H):
    for x in range(W):
        for dx, dy in dxdy:
            nx = x + dx
            ny = y + dy
            if nx >= W or ny >= H: continue
            if s[ny][nx] == '#' and s[y][x] == '.':
                dp[ny][nx] = min(dp[ny][nx], dp[y][x] + 1)
            else:
                dp[ny][nx] = min(dp[ny][nx], dp[y][x])

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

Submission status: Accepted

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

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

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

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

Submission status: Accepted

Solution code:
from sys import stdin, stdout

int_in = lambda: int(stdin.readline())
arr_in = lambda: [int(x) for x in stdin.readline().split()]
mat_in = lambda rows: [arr_in() for y in range(rows)]
str_in = lambda: stdin.readline().strip()
out = lambda o: stdout.write("{}\n".format(o))
arr_out = lambda o: out(" ".join(map(str, o)))
bool_out = lambda o: out("YES" if o else "NO")
tests = lambda: range(1, int_in() + 1)


def solve(h, w, matrix):
    dp = [[[0, False] for x in range(w)] for y in range(h)]
    for row in range(h):
        for col in range(w):
            dp[row][col][1] = matrix[row][col] == "#"
            prev = False
            if row > 0 and col > 0:
                if dp[row-1][col][0] < dp[row][col-1][0]:
                    prev = dp[row-1][col][1]
                    dp[row][col][0] = dp[row-1][col][0]
                elif dp[row-1][col][0] > dp[row][col-1][0]:
                    prev = dp[row][col-1][1]
                    dp[row][col][0] = dp[row][col-1][0]
                else:
                    prev = dp[row-1][col][1] or dp[row][col-1][1]
                    dp[row][col][0] = dp[row][col-1][0]
            elif row > 0:
                prev = dp[row-1][col][1]
                dp[row][col][0] = dp[row-1][col][0]
            elif col > 0:
                prev = dp[row][col-1][1]
                dp[row][col][0] = dp[row][col-1][0]
            if dp[row][col][1] and not prev:
                dp[row][col][0] += 1
    return dp[h-1][w-1][0]


if __name__ == "__main__":
    h, w = arr_in()
    matrix = [str_in() for x in range(h)]
    out(solve(h, w, matrix))

Submission status: Accepted

Solution code:
h,w=map(int,input().split())
m=[]
grid=[]
nextdfsstart=set()
nextdfsstart.add(0)
def dfs(x,y,colour):
  global grid
  global nextdfsstartcopy
  global visited
  grid[y][x]=depth
  visited.add(x+w*y)
  if x<w-1 and not x+1+y*w in visited:
    if m[y][x+1]==colour :
      dfs(x+1,y,colour)
    else:
      nextdfsstartcopy.add(x+1+y*w)
  if y<h-1 and not x+(y+1)*w in visited:
    if m[y+1][x]==colour :
      dfs(x,y+1,colour)
    else:
      nextdfsstartcopy.add(x+(y+1)*w)
for i in range(h):
  m.append(input())
  grid.append([])
  for j in range(w):
      grid[i].append(-1)
visited=set()
depth=0
while grid[h-1][w-1]==-1:
  nextdfsstartcopy=set()
  for i in nextdfsstart:
    if i in visited:
      continue
    k=i//w
    if (k+1)*w<=i:
      k+=1
    dfs(i%w,k,m[k][i%w])
  depth+=1
  nextdfsstart=nextdfsstartcopy.copy()
ans=grid[h-1][w-1]//2
if m[0][0]=='#' or m[h-1][w-1]=='#':
  ans+=1
print(ans)

Submission status: Accepted

Solution code:
h, w = map(int, input().split())
s = [input() for _i in range(h)]
visit = [[float("inf") for _ in range(w)] for _j in range(h)]
visit[0][0] = 0
for i in range(h):
    for j in range(w):
        if i-1 >= 0:
            visit[i][j] = visit[i-1][j]+(s[i][j]!=s[i-1][j])
        if j-1 >= 0:
            visit[i][j] = min(visit[i][j], visit[i][j-1]+(s[i][j]!=s[i][j-1]))

if s[0][0]==s[h-1][w-1]==".":
    print(visit[h-1][w-1]//2)
elif s[0][0]==s[h-1][w-1]=="#":
    print(visit[h-1][w-1]//2 +1) 
else:
    print(visit[h-1][w-1]//2 +1)

Submission status: Accepted

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

ans = [[0 for i in range(w)] for j in range(h)]
for i, row in enumerate(s):
    for j, index in enumerate(row):
        if i == j == 0:
            if s[i][j] == "#":
                ans[i][j] = 1
        elif i == 0:
            if s[i][j] == s[i][j - 1]:
                ans[i][j] = ans[i][j - 1]
            else:
                ans[i][j] = ans[i][j - 1] + 1
        elif j == 0:
            if s[i][j] == s[i - 1][j]:
                ans[i][j] = ans[i - 1][j]
            else:
                ans[i][j] = ans[i - 1][j] + 1
        else:
            if s[i][j] == s[i - 1][j]:
                a1 = ans[i - 1][j]
            else:
                a1 = ans[i - 1][j] + 1
            if s[i][j] == s[i][j - 1]:
                a2 = ans[i][j - 1]
            else:
                a2 = ans[i][j - 1] + 1
            ans[i][j] = min(a1, a2)

print((ans[-1][-1] + 1) // 2)

Submission status: Accepted

Solution code:
h,w=map(int,input().split())
s=list()
for i in range(h):
    line=str(input())
    s.append(line)


result=list()
for i in range(h):
    line=list()
    for j in range(w):
        line.append(0)
    result.append(line)
def se(x,y):
    if x==0 and y==0:
        if s[0][0]=="#":
            result[x][y]=1
        else:
            result[x][y]=0
    elif x==0:
        if s[x][y-1]!=s[x][y]:
            result[x][y]=result[x][y-1]+1
        else:
            result[x][y]=result[x][y-1]
    elif y==0:
        if s[x-1][y]!=s[x][y]:
            result[x][y]=result[x-1][y]+1
        else:
            result[x][y]=result[x-1][y]
    else:
        if s[x][y-1]!=s[x][y]:
            a=result[x][y-1]+1
        else:
            a=result[x][y-1]
        if s[x-1][y]!=s[x][y]:
            b=result[x-1][y]+1
        else:
            b=result[x-1][y]
        result[x][y]=min(a,b)
        
for i in range(h):
    for j in range(w):
        se(i,j)
        
if s[h-1][w-1]=="#":
    result[h-1][w-1]+=1
else:
    pass


print(int(result[h-1][w-1]/2))

Submission status: Accepted

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


def g(m):
    if data[0][0] == '.':
        a = 0
    else:
        a = 1

    for i in range(1, m, 1):
        if data[0][i] == '.':
            continue
        elif data[0][i] == '#' and data[0][i - 1] == '.':
            a += 1
        else:
            continue
    return a


def h(n):
    if data[0][0] == '.':
        a = 0
    else:
        a = 1

    for i in range(1, n, 1):
        if data[i][0] == '.':
            continue
        elif data[i][0] == '#' and data[i - 1][0] == '.':
            a += 1
        else:
            continue
    return a

A = [0] + [g(i) for i in range(1,W+1)]
B = [0] + [h(i) for i in range(1,H+1)]
C = [[0]*(W+1) for i in range(H+1)]

for n in range(1,H+1):
    for m in range(1,W+1):
        if n == 1:
            C[n][m] = A[m]
        elif m == 1:
            C[n][m] = B[n]
        else:
            if data[n - 1][m - 1] == '.':
                C[n][m] = min(C[n - 1][m], C[n][m - 1])
            elif data[n - 2][m - 1] == '.':
                if data[n - 1][m - 2] == '.':
                    C[n][m] = min(C[n - 1][m] + 1, C[n][m - 1] + 1)
                else:
                    C[n][m] =  min(C[n - 1][m] + 1, C[n][m - 1])
            else:
                if data[n - 1][m - 2] == '.':
                    C[n][m] = min(C[n - 1][m], C[n][m - 1] + 1)
                else:
                    C[n][m] = min(C[n - 1][m], C[n][m - 1])


print(C[H][W])

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

Submission status: Accepted

Solution code:
import sys
import re
import math
import collections
import decimal
import bisect
import itertools
import fractions
import functools
import copy
import heapq
import decimal
import statistics
import queue

sys.setrecursionlimit(10000001)
INF = 10 ** 10
MOD = 10 ** 9 + 7

ni = lambda: int(sys.stdin.readline())
ns = lambda: map(int, sys.stdin.readline().split())
na = lambda: list(map(int, sys.stdin.readline().split()))


# ===CODE===
def main():
    h, w = ns()
    mat = [list(input()) for _ in range(h)]

    ans_mat = [[INF for _ in range(w)] for _ in range(h)]
    if mat[0][0] == "#":
        ans_mat[0][0] = 1
    else:
        ans_mat[0][0] = 0

    for y in range(h):
        for x in range(w):
            if x + 1 < w:
                if mat[y][x] != mat[y][x + 1]:
                    ans_mat[y][x + 1] = min(ans_mat[y][x + 1], ans_mat[y][x] + 1)
                else:
                    ans_mat[y][x + 1] = min(ans_mat[y][x + 1], ans_mat[y][x])

            if y + 1 < h:
                if mat[y][x] != mat[y + 1][x]:
                    ans_mat[y + 1][x] = min(ans_mat[y + 1][x], ans_mat[y][x] + 1)
                else:
                    ans_mat[y + 1][x] = min(ans_mat[y + 1][x], ans_mat[y][x])

    tmp = ans_mat[h - 1][w - 1]
    print(tmp - tmp // 2)


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import sys
readline = sys.stdin.buffer.readline
sys.setrecursionlimit(10 ** 8)
INF = float('inf')
MOD = 10 ** 9 + 7

def main():
    H, W = map(int, readline().split())
    S = list(readline().decode('utf-8').strip() for _ in range(H))
    dp = [[INF] * (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):
            if i != H-1:
                if S[i][j]=='.' and S[i+1][j]=='#':
                    dp[i+1][j] = min(dp[i+1][j],dp[i][j]+1)
                else:
                    dp[i+1][j] = min(dp[i+1][j],dp[i][j])
            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+1],dp[i][j])


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

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import sys
readline = sys.stdin.buffer.readline
sys.setrecursionlimit(10 ** 8)
INF = float('inf')
MOD = 10 ** 9 + 7

def main():
    H, W = map(int, readline().split())
    S = list(readline().decode('utf-8').strip() for _ in range(H))
    dp = [[INF] * (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):
            if i==H-1 and j == W-1:
                break
            if j==W-1:
                if S[i][j]=='.' and S[i+1][j]=='#':
                    dp[i+1][j] = min(dp[i+1][j],dp[i][j]+1)
                else:
                    dp[i+1][j] = min(dp[i+1][j],dp[i][j])
            elif i == H-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+1],dp[i][j])
            else:
                if S[i][j]=='.' and S[i+1][j]=='#':
                    dp[i+1][j] = min(dp[i+1][j],dp[i][j]+1)
                else:
                    dp[i+1][j] = min(dp[i+1][j],dp[i][j])
                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+1],dp[i][j])


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

if __name__ == '__main__':
    main()

Submission status: Accepted

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

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

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

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

Submission status: Accepted

Solution code:
INF=10**18
H,W=map(int,input().split())
G=[list(input()) for i in range(H)]

dp=[[INF]*W for i in range(H)]
dp[0][0]=0
dx=[0,1]
dy=[1,0]

for i in range(H):
    for j in range(W):
        for x,y in zip(dx,dy):
            if i+x>=H or j+y>=W:
                continue
            if G[i][j]=='.' and G[i+x][j+y]=='#':
                dp[i+x][j+y]=min(dp[i][j]+1,dp[i+x][j+y])
            else:
                dp[i+x][j+y]=min(dp[i][j],dp[i+x][j+y])
ans=dp[H-1][W-1]
print(ans if G[0][0]!='#' else ans+1)

Submission status: Accepted

Solution code:
import itertools,sys
def S(): return sys.stdin.readline().rstrip()
def LI(): return list(map(int,sys.stdin.readline().rstrip().split()))
H,W = LI()
S = [S() for _ in range(H)]
dp = [[float('INF')]*W for _ in range(H)]
for i,j in itertools.product(range(H),range(W)):
    if i==0:
        if j==0:
            dp[i][j] = 1 if S[i][j]=='#' else 0
        else:
            dp[i][j] = dp[i][j-1]+(1 if S[i][j]=='#' and S[i][j-1]=='.' else 0)
    else:
        if i==0:
            dp[i][j] = dp[i-1][j]+(1 if S[i][j]=='#' and S[i-1][j]=='.' else 0)
        else:
            dp[i][j] = min(dp[i][j],dp[i][j-1]+(1 if S[i][j]=='#' and S[i][j-1]=='.' else 0))
            dp[i][j] = min(dp[i][j],dp[i-1][j]+(1 if S[i][j]=='#' and S[i-1][j]=='.' else 0))
print(dp[-1][-1])

Submission status: Accepted

Solution code:
import sys
sys.stdin.readline

H, W = map(int, input().split())
board = [[[0,1][a == "#"] for a in input()] for i in range(H)]
Y = [[0]*W for _ in range(H)]

for i in range(H):
    for j in range(W):
        a = []
        if j == 0:
            pass
        else:
            if board[i][j-1] == False and board[i][j] == True:
                a.append(Y[i][j-1] + 1)
            else:
                a.append(Y[i][j-1])
        if i == 0:
            pass
        else:
            if board[i-1][j] == False and board[i][j] == True:
                a.append(Y[i-1][j] + 1)
            else:
                a.append(Y[i-1][j])
        if i + j == 0:
            if board[i][j]:
                a.append(1)
            else:
                continue
        Y[i][j] = min(a)


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

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
    dp[i][j]=min(a,b,dp[i][j])
print(dp[-1][-1])

Submission status: Accepted

Solution code:
from sys import stdin, stdout
from collections import deque, defaultdict
import math as m

rl = lambda: stdin.readline()
rll = lambda: stdin.readline().split()
rli = lambda: map(int, stdin.readline().split())

INF, NINF = float('inf'), float('-inf')

def main():
	H, W = rli()
	M = []
	#0 white, 1 black
	for _ in range(H):
		row = list(rll()[0])
		row = list(map(lambda x: 0 if x == "." else 1, row))
		M.append(row)

	dp = [[INF if i != 0 and j != 0 else 0 for j in range(W)] for i in range(H)]
	dp[0][0] = 1 if M[0][0] == 1 else 0
	
	for c in range(1, W):
		if M[0][c-1] == 0 and M[0][c] == 1:
			dp[0][c] = dp[0][c-1] + 1
		else:
			dp[0][c] = dp[0][c-1]
	for r in range(1, H):
		if M[r-1][0] == 0 and M[r][0] == 1:
			dp[r][0] = dp[r-1][0] + 1
		else:
			dp[r][0] = dp[r-1][0]

	for r in range(1, H):
		for c in range(1, W):
			c1, c2 = INF, INF
			if M[r-1][c] == 0 and M[r][c] == 1:
				c1 = dp[r-1][c] + 1
			if M[r][c-1] == 0 and M[r][c] == 1:
				c2 = dp[r][c-1] + 1
			c1 = dp[r-1][c] if c1 == INF else c1 
			c2 = dp[r][c-1] if c2 == INF else c2
			dp[r][c] = min(c1, c2)
	print(dp[-1][-1])
	stdout.close()

if __name__ == "__main__":
	main()

Submission status: Accepted

Solution code:
import sys

H, W = map(int, input().split())
G = [list(sys.stdin.readline().strip()) for _ in range(H)]

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

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

for i in range(1, H):
    for j in range(1, W):
        t = int(G[i][j] == "#")
        DP[i][j] = min(DP[i - 1][j] + int(t and G[i - 1][j] == "."), DP[i][j - 1] + int(t and G[i][j - 1] == "."))

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

Submission status: Accepted

Solution code:
H, W = map(int, input().split())
s = []
for _ in range(H):
  s.append(input())
  
def main(H, W, s):
  # 動的計画法
  
  INF = float('inf')
  dp = [[INF]*W for _ in range(H)]
  if s[0][0] == '#':
    dp[0][0] = 1
  else:
    dp[0][0] = 0

  dx = (1, 0)
  dy = (0, 1)
  for i in range(H):
    for j in range(W):
      for dir_ in range(2):  # 右に行くか下に行くかの2通り
        ni = i + dx[dir_]
        nj = j + dy[dir_]
        if ni >= H or nj >= W:
          continue
        add = 0
        if s[ni][nj] == '#' and s[i][j] == '.':
          add = 1
        dp[ni][nj] = min(dp[ni][nj], dp[i][j] + add)

  return dp[H-1][W-1]

print(main(H, W, s))