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:
h,w = map(int,input().split())
B = [input() for _ in range(h)]
dp=[]
def ch(x1,y1,x2,y2):
    if B[x1][y1]=='.' and B[x2][y2]=='#':
        return 1
    else:
        return 0
dp = [[0 for j in range(w)] for i in range(h)]
for i in range(h):
    for j in range(w):
        if i==0 and j==0 and B[i][j]=='#':
            dp[i][j]+=1
        elif i==0:
            dp[i][j] = dp[i][j-1]+ch(i,j-1,i,j)
        elif j==0:
            dp[i][j] = dp[i-1][j]+ch(i-1,j,i,j)
        else:
            dp[i][j] = min(dp[i][j-1]+ch(i,j-1,i,j),dp[i-1][j]+ch(i-1,j,i,j))
print(dp[h-1][w-1])

Submission status: Accepted

Solution code:
import sys


def main():
    dp = [[0] * W for _ in range(H)]

    for y in range(H):
        for x in range(W):
            if x == 0 and y == 0:
                if s[0][0] == "#":
                    dp[0][0] = 1
            elif x == 0:
                if s[y][x] == "#" and s[y - 1][x] == ".":
                    dp[y][x] = dp[y - 1][x] + 1
                else:
                    dp[y][x] = dp[y - 1][x]
            elif y == 0:
                if s[y][x] == "#" and s[y][x - 1] == ".":
                    dp[y][x] = dp[y][x - 1] + 1
                else:
                    dp[y][x] = dp[y][x - 1]
            else:
                if s[y][x] == "#" and s[y][x - 1] == "." and s[y - 1][x] == ".":
                    dp[y][x] = min(dp[y][x - 1], dp[y - 1][x]) + 1
                elif s[y][x] == "#" and s[y][x - 1] == ".":
                    dp[y][x] = min(dp[y][x - 1] + 1, dp[y - 1][x])
                elif s[y][x] == "#" and s[y - 1][x] == ".":
                    dp[y][x] = min(dp[y][x - 1], dp[y - 1][x] + 1)
                else:
                    dp[y][x] = min(dp[y][x - 1], dp[y - 1][x])

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


if __name__ == "__main__":
    H, W = map(int, sys.stdin.readline().split())
    s = [list(sys.stdin.readline().rstrip()) for _ in range(H)]
    main()

Submission status: Accepted

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

dp = [[10 ** 9 for i in range(W)] for j in range(H)]
dp[0][0] = 0 if s[0][0] == '.' else 1

for i in range(H):
    for j in range(W):
        if i + 1 < H:
            cost = int(s[i][j] == '.' and s[i + 1][j] == '#')
            dp[i + 1][j] = min(dp[i + 1][j], dp[i][j] + cost)
        if j + 1 < W:
            cost = int(s[i][j] == '.' and s[i][j + 1] == '#')
            dp[i][j + 1] = min(dp[i][j + 1], dp[i][j] + cost)

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

Submission status: Accepted

Solution code:
def main():

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

    dp = [[float('inf') for _ in range(W+1)] for _ in range(H+1)]

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



if __name__ == '__main__':
    print(main())

Submission status: Accepted

Solution code:
import sys
def input(): return sys.stdin.readline().rstrip()
def main():
    h,w=map(int,input().split())
    S=[input() for _ in range(w)]
    DP=[[0]*w for _ in range(h)]
    if S[0][0]=='#':
        DP[0][0]=1
    for j in range(1,w):
        if S[0][j-1]=='.' and S[0][j]=='#':
            DP[0][j]=DP[0][j-1]+1
        else:
            DP[0][j]=DP[0][j-1]
    for i in range(1,h):
        if S[i-1][0]=='.' and S[i][0]=='#':
            DP[i][0]=DP[i-1][0]+1
        else:
            DP[i][0]=DP[i-1][0]
        for j in range(1,w):
            if S[i-1][j]=='.' and S[i][j]=='#':
                d=DP[i-1][j]+1
            else:
                d=DP[i-1][j]
            if S[i][j-1]=='.' and S[i][j]=='#':
                r=DP[i][j-1]+1
            else:
                r=DP[i][j-1]
            DP[i][j]=min(d,r)
    print(DP[-1][-1])

if __name__=='__main__':
    main()

Submission status: Accepted

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

cnt = [[float('inf')]*w for _ in range(h)]
if s[0][0] == '.':
    cnt[0][0] = 0
else:
    cnt[0][0] = 1

for i in range(h):
    for j in range(w):
        for dy, dx in [[1, 0], [0, 1]]:
            x = j+dx
            y = i+dy
            if x >= w or y >= h:
                continue
            if s[i][j] == s[y][x]:
                cnt[y][x] = min(cnt[y][x], cnt[i][j])
            else:
                cnt[y][x] = min(cnt[y][x], cnt[i][j] + 1)

if s[-1][-1] == '#':
    cnt[-1][-1] += 1
print(cnt[-1][-1]//2)

Submission status: Accepted

Solution code:
h,w = map(int, input().split())
s = [input()+"." for i in range(h)] + ["."*(w+1)]
INF = 10 ** 18
dp = [[INF]*(w+1) for i in range(h+1)]
dp[0][0] = 1 if s[0][0] == "#" else 0
for i in range(h):
  for j in range(w):
    if s[i][j] == "#":
      dp[i+1][j] = min(dp[i+1][j], dp[i][j])
      dp[i][j+1] = min(dp[i][j+1], dp[i][j])
    else:
      vi = 1 if s[i+1][j] == "#" else 0
      vj = 1 if s[i][j+1] == "#" else 0
      dp[i+1][j] = min(dp[i+1][j], dp[i][j]+vi)
      dp[i][j+1] = min(dp[i][j+1], dp[i][j]+vj)
print(dp[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 j in range(w)] for i in range(h)]
if S[0][0] == '#':
    DP[0][0] = 1
for j in range(1, w):
    if S[0][j - 1] == '.' and S[0][j] == '#':
        DP[0][j] = DP[0][j - 1] + 1
    else:
        DP[0][j] = DP[0][j - 1]
for i in range(1, h):
    if S[i - 1][0] == '.' and S[i][0] == '#':
        DP[i][0] = DP[i - 1][0] + 1
    else:
        DP[i][0] = DP[i - 1][0]
    for j in range(1, w):
        if S[i - 1][j] == '.' and S[i][j] == '#':
            up = DP[i - 1][j] + 1
        else:
            up = DP[i - 1][j]
        if S[i][j - 1] == '.' and S[i][j] == '#':
            left = DP[i][j - 1] + 1
        else:
            left = DP[i][j - 1]
        DP[i][j] = min(up, left)
print(DP[-1][-1])

Submission status: Accepted

Solution code:
import sys

readline = sys.stdin.readline
inf = float('inf')

def main():
    H, W = map(int, readline().split())
    grid = []
    grid.append(['*'] * (W+2))
    for _ in range(H):
        grid.append(['*'] + list(readline()[:-1]) + ['*'])
    grid.append(['*']*(W+2))

    DP = [[inf] * (W+2) for _ in range(H+2)]
    DP[1][1] = (grid[1][1] == '#')*1

    for i in range(1, H+1):
        for j in range(1, W+1): 
            if i == 1 and j == 1:
                continue
            k = i
            gridkj = grid[k][j]
            if gridkj == '.':
                DP[k][j] = min(DP[k][j-1], DP[k-1][j])
            if gridkj == '#':
                DP[k][j] = min(DP[k][j-1]+(grid[k][j-1] in ['.', '*']), DP[k-1][j] + (grid[k-1][j] in ['.', '*']))
    ans = DP[H][W]
    print(ans)

if __name__ == "__main__":
    main()

Submission status: Accepted

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

S = [input() for _ in range(H)]

INF = 10 ** 5
dp = [[INF] * (W + 1) for _ in range(H + 1)]
dp[0][0] = int(S[0][0] == '#')

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

        # 横移動
        if j == 0:
            v1 = INF
        else:
            v1 = int(S[i][j - 1] == '.' and S[i][j] == '#') + dp[i][j - 1]

        # 縦移動
        if i == 0:
            v2 = INF
        else:
            v2 = int(S[i - 1][j] == '.' and S[i][j] == '#') + dp[i - 1][j]

        dp[i][j] = min(v1, v2, dp[i][j])
ans = dp[H - 1][W - 1]
print(ans)

Submission status: Accepted

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

dp = [[0]*W for _ in range(H)]
if S[0][0] == "#":
    dp[0][0] = 1

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

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


for i in range(1, H):
    for j in range(1, W):
        if S[i][j] == S[i-1][j]:
            a = dp[i-1][j]
        else:
            a = dp[i-1][j]+1
        if S[i][j] == S[i][j-1]:
            b = dp[i][j-1]
        else:
            b = dp[i][j-1]+1
        dp[i][j] = min(a, b)

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

Submission status: Accepted

Solution code:
from collections import deque


H,W = map(int, input().split())

S = [input() for _ in range(H)]


"""
移動先の色が同じであれば、その部分は一回の操作でひっくり返せるので、黒から黒へ連続で移動していても操作回数は一回でOK

"""
INF = float("inf")
costs = [[INF for _ in range(W)] for _ in range(H)]

costs[0][0] = 0 if S[0][0] == "." else 1

q = deque()
q.append((costs[0][0], 0, 0))

while q:
    curr_cost, y, x = q.popleft()
    for dy, dx in [(1,0), (0,1)]:
        if y + dy >= H or x + dx >= W:
            continue
        nxt_cost = curr_cost if S[y][x] == S[y+dy][x+dx] else curr_cost + 1
        if nxt_cost < costs[y+dy][x+dx]:
            costs[y+dy][x+dx] = nxt_cost
            q.append((nxt_cost, y+dy, x+dx))


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

Submission status: Accepted

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

def pl(x1,y1,x2,y2):
    if s[x1][y1] == "." and s[x2][y2] == "#":
        return 1
    else:
        return 0

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

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

Submission status: Accepted

Solution code:
# DP
# . -> # に変わる回数が反転が必要な回数
# その最小経路をDPで解く
H, W = map(int, input().split())
S = [list(input()) for _ in range(H)]
dp = [[0]*W for _ in range(H)]

def cnt(i0, j0, i1, j1):
  if S[i0][j0] == "." and S[i1][j1] == "#":
    return 1
  else:
    return 0

for i in range(H):
  for j in range(W):
    if i == 0 and j == 0:
      dp[0][0] = 0 if S[0][0] == "." else 1
    elif i == 0:
      dp[i][j] = dp[i][j-1] + cnt(i, j-1, i, j)
    elif j == 0:
      dp[i][j] = dp[i-1][j] + cnt(i-1, j, i, j)
    else:
      dp[i][j] = min(dp[i][j-1] + cnt(i, j-1, i, j), dp[i-1][j] + cnt(i-1, j, i, j))

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

Submission status: Accepted

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

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

        if(s[i-1][j] != s[i][j]):
            top = dp[i-1][j]+1
        else:
            top = dp[i-1][j]

        dp[i][j] = min(dp[i][j],left,top)

print((dp[h-1][w-1]+1)//2)

Submission status: Accepted

Solution code:
h, w = map(int, input().split())
 
mat = [[] for _ in range(h)]
 
for i in range(h):
    mat[i] = input()
 
dp = [[float("inf")] * w for _ in range(h)]
 
if mat[0][0] == "#":
    dp[0][0] = 1
else:
    dp[0][0] = 0
 
for i in range(h):
    for j in range(w):
 
        if mat[i][j - 1] != mat[i][j]:
            left = dp[i][j - 1] + 1
        else:
            left = dp[i][j - 1]
 
        if mat[i - 1][j] != mat[i][j]:
            top = dp[i - 1][j] + 1
        else:
            top = dp[i - 1][j]
 
        dp[i][j] = min(dp[i][j], left, top)
 
print((dp[h - 1][w - 1] + 1) // 2)

Submission status: Accepted

Solution code:
from statistics import median
#import collections
#aa = collections.Counter(a) # list to list || .most_common(2)で最大の2個とりだせるお a[0][0]
from fractions import gcd
from itertools import combinations # (string,3) 3回
from collections import deque
from collections import defaultdict
import bisect
#
#    d = m - k[i] - k[j]
#    if kk[bisect.bisect_right(kk,d) - 1] == d:
#
#
#
# pythonで無理なときは、pypyでやると正解するかも！！
#
#

import sys
sys.setrecursionlimit(10000000)
mod = 10**9 + 7

def readInts():
  return list(map(int,input().split()))
def main():
    dx = [1,0]
    dy = [0,1]
    INF = float('inf')
    h,w = readInts()
    dp = [[INF]*w for _ in range(h)]
    FIELD = [input() for _ in range(h)]
    # dp[j][i] = i番目とj番目にかかる魔法の度合い
    # 初期値 魔法1, なし 0
    if FIELD[0][0] == '#':
        dp[0][0] = 1
    else:
        dp[0][0] = 0
    for i in range(w):
        for j in range(h):
            for x,y in dx,dy:
                ny = j + y
                nx = i + x
                if ny >= h or nx >= w:
                    continue
                add = 0
                if FIELD[ny][nx] == '#' and FIELD[j][i] == '.':
                    add = 1
                dp[ny][nx] = min(dp[ny][nx], dp[j][i] + add)
    print(dp[h-1][w-1])
if __name__ == '__main__':
  main()

Submission status: Accepted

Solution code:

def IsvalidStep(arr,row1,col1,row2,col2):
    if arr[row2][col2]=="#" and arr[row1][col1]==".":
        return 1
    return 0    

def solve(arr,matrix,n,m):
    maxx=0
    if n>0:
        if arr[0][0]=="#":
            matrix[0][0]=1
        for col in range(1,m):
            matrix[0][col]=matrix[0][col-1]
            if arr[0][col]=="#" and arr[0][col-1]==".":
                matrix[0][col]+=1

        for row in range(1,n):    
            matrix[row][0]=matrix[row-1][0]
            if arr[row][0]=="#" and arr[row-1][0]==".":
                matrix[row][0]+=1
          
        for row in range(1,n):
            for col in range(1,m):
                matrix[row][col]=min(matrix[row-1][col]+IsvalidStep(arr,row-1,col,row,col),matrix[row][col-1]+IsvalidStep(arr,row,col-1,row,col))
        return matrix[n-1][m-1]        



n,m=map(int,input().split())
arr=[int(0) for i in range(n)]
matrix=[int(0) for i in range(n)]
for i in range(n):
    arr[i]=list(input())
    matrix[i]=[int(0) for _ in range(m)]



print(solve(arr,matrix,n,m))       


"""
def solve(arr,n,m,row,col,count):
    if row>=n or col>=m:
        return 1e9
    elif row==n-1 and col==m-1:
        if arr[row][col]=="#":
            count+=1
        return count
    else:
        if arr[row][col]=="#":
            count+=1
        return min(solve(arr,n,m,row+1,col,count),solve(arr,n,m,row,col+1,count))        
"""

Submission status: Accepted

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

mat = [[] for _ in range(h)]

for i in range(h):
    mat[i] = input()

dp = [[float("inf")] * w for _ in range(h)]

if mat[0][0] == "#":
    dp[0][0] = 1
else:
    dp[0][0] = 0

for i in range(h):
    for j in range(w):

        if mat[i][j - 1] != mat[i][j]:
            left = dp[i][j - 1] + 1
        else:
            left = dp[i][j - 1]

        if mat[i - 1][j] != mat[i][j]:
            top = dp[i - 1][j] + 1
        else:
            top = dp[i - 1][j]

        dp[i][j] = min(dp[i][j], left, top)

print((dp[h - 1][w - 1] + 1) // 2)

Submission status: Accepted

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

def cnt(i0, j0, i1, j1):
  if S[i0][j0] == "." and S[i1][j1] == "#":
    return 1
  else:
    return 0

for i in range(H):
  for j in range(W):
    if i == 0 and j == 0:
      dp[0][0] = 0 if S[0][0] == "." else 1
    elif i == 0:
      dp[i][j] = dp[i][j-1] + cnt(i, j-1, i, j)
    elif j == 0:
      dp[i][j] = dp[i-1][j] + cnt(i-1, j, i, j)
    else:
      dp[i][j] = min(dp[i][j-1] + cnt(i, j-1, i, j), dp[i-1][j] + cnt(i-1, j, i, j))

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

Submission status: Accepted

Solution code:
import math,string,itertools,fractions,heapq,collections,re,array,bisect,sys,copy,functools
import time,random

sys.setrecursionlimit(10**7)
inf = 10**20
eps = 1.0 / 10**10
mod = 10**9+7
mod2 = 998244353
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 list(map(int, sys.stdin.readline().split()))
def LLI(): return [list(map(int, l.split())) for l in sys.stdin.readlines()]
def LI_(): return [int(x)-1 for x in sys.stdin.readline().split()]
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def I(): return int(sys.stdin.readline())
def F(): return float(sys.stdin.readline())
def S(): return input()
def pf(s): return print(s, flush=True)
def pe(s): return print(str(s), file=sys.stderr)
def JA(a, sep): return sep.join(map(str, a))
def JAA(a, s, t): return s.join(t.join(map(str, b)) for b in a)


def main():
    h,w = LI()
    aa = [[0 if c == '.' else 1 for c in S()] for _ in range(h)]

    dp = [[[inf]*2 for _ in range(w)] for __ in range(h)]
    dp[0][0][aa[0][0]] = aa[0][0]
    for i in range(h):
        for j in range(w):
            k = aa[i][j]
            if i > 0:
                dp[i][j][k] = min(dp[i][j][k], dp[i-1][j][k])
                dp[i][j][k] = min(dp[i][j][k], dp[i-1][j][1-k]+1)
            if j > 0:
                dp[i][j][k] = min(dp[i][j][k], dp[i][j-1][k])
                dp[i][j][k] = min(dp[i][j][k], dp[i][j-1][1-k]+1)

    return min(dp[-1][-1][0] + 1, dp[-1][-1][1] + 2) // 2


print(main())

Submission status: Accepted

Solution code:
h, w = map(int, input().split())
M = [list(input()) for _ in range(h)]
count = [[int(1e18) for _ in range(w)] for _ in range(h)]
count[0][0] = 1 if M[0][0] == '#' else 0

# 同じ色かどうかを見る
for i in range(h):
    for j in range(w):
        if i + 1 < h:
            v = 1 if M[i][j] != M[i + 1][j] else 0
            count[i + 1][j] = min(count[i + 1][j], count[i][j] + v)
        if j + 1 < w:
            v = 1 if M[i][j] != M[i][j + 1] else 0
            count[i][j + 1] = min(count[i][j + 1], count[i][j] + v)

print((count[h - 1][w - 1] + 1) // 2)

Submission status: Accepted

Solution code:
import numpy as np

H,W = input().split()
H,W=int(H),int(W)
P=[0]*H
for i in range(H):
    P[i] = input()

dp=np.zeros((H,W),dtype='u8')
if P[0][0]=='#':
    dp[0][0]=1
else:
    dp[0][0]=0

def DP(y,x):
    global dp
    if 0<=x<=W-1 and 0<=y<=H-1:
        return dp[y][x]
    else:
        return 9999999

for l in range(1,H+W):
    for i in range(l+1):
        if i<H and l-i<W:
            if P[i][l-i]=='#':
                a=DP(i-1,l-i)
                b=DP(i,l-i-1)
                if a < 9999999:
                    if P[i-1][l-i]=='.':
                        a+=1
                if b <  9999999:
                    if P[i][l-i-1]=='.':
                        b+=1
                dp[i][l-i]=min(a,b)
            else:
                #print(i,l-i,DP(i-1,l-i),DP(i,l-i-1))
                dp[i][l-i]=min(DP(i-1,l-i),DP(i,l-i-1))
print(dp[H-1][W-1])

Submission status: Accepted

Solution code:
h,w=map(int,input().split())
s=[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
dx=[1,0]
dy=[0,1]
for i in range(h):
    for j in range(w):
        for dir in range(2):
            ni=i+dy[dir]
            nj=j+dx[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)
print(dp[-1][-1])

Submission status: Accepted

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

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

for hi in range(h):
    for wi in range(w):
        if hi==0 and wi==0:
            continue
        dh = 10**9
        if hi-1>=0:
            if sl[hi][wi]=="#" and sl[hi-1][wi]==".":
                dh = dp[hi-1][wi] + 1
            else:
                dh = dp[hi-1][wi]
        dw = 10**9
        if wi-1>=0:
            if sl[hi][wi]=="#" and sl[hi][wi-1]==".":
                dw = dp[hi][wi-1] + 1
            else:
                dw = dp[hi][wi-1]

        dp[hi][wi] = min(dh,dw)

res = dp[h-1][w-1]
if sl[0][0]=="#":
    res += 1
print(res)

Submission status: Accepted

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

def main():
  h, w = map(int, input().split())
  grid = []
  for _ in range(h):
    grid.append(list(input().strip()))
  dp = [[0]*(w) for _ in range(h)]
  
  def cals_score(i, j):
    score = 10**9 + 7
    if i >= 1:
      score = dp[i-1][j] + (1 if grid[i-1][j]!=grid[i][j] else 0)
    if j >= 1:
      score = min(score, dp[i][j-1] + (1 if grid[i][j-1]!=grid[i][j] else 0))
    return score
      
  dp[0][0] = 1
  for i in range(1, w):
    dp[0][i] = cals_score(0, i)
  for i in range(1, h):
    dp[i][0] = cals_score(i, 0)

    
  for i in range(1, h):
    for j in range(1, w):
      dp[i][j] = cals_score(i, j)
  print(dp[-1][-1]//2 + dp[-1][-1]%2 * (grid[0][0]=='#'))

if __name__=='__main__':
  main()

Submission status: Accepted

Solution code:
H, W = [int(x) for x in input().split()]

S = []
S.append('.'*105)
for h in range(H):
    r = input()
    S.append('-' + r)

A = [[float("INF")] * 105 for _ in range(105)]
A[1][1] = (1 if S[1][1] == '#' else 0)


for h in range(1,H+1):
    for w in range(1,W+1):
        a = A[h][w]
        if S[h][w] == '#':
            if S[h][w-1] == '#':
                a = min(a, A[h][w-1])
            else:
                a = min(a, A[h][w-1] + 1)
            if S[h-1][w] == '#':
                a = min(a, A[h-1][w])
            else:
                a = min(a, A[h-1][w] + 1)
            A[h][w] = a
        else:
            A[h][w] = min(A[h][w-1], A[h-1][w], A[h][w])
            
print(A[H][W])

Submission status: Accepted

Solution code:
import sys
import collections

sys.setrecursionlimit(10 ** 8)

input = sys.stdin.readline


def main():
    H, W = [int(x) for x in input().split()]
    S = [list(input().strip()) for _ in range(H)]

    dp = [[10 ** 9] * W for _ in range(H)]
    dp[0][0] = int(S[0][0] == '#')

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


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import sys
import collections

sys.setrecursionlimit(10 ** 8)

input = sys.stdin.readline


def main():
    H, W = [int(x) for x in input().split()]
    S = [list(input().strip()) for _ in range(H)]

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

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

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

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


if __name__ == '__main__':
    main()

Submission status: Accepted

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

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

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

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

Submission status: Accepted

Solution code:
h,w=map(int,input().split())
s=['*'+'.'+'*'*w]+['*'+input()+'*' for i in range(h)]+['*'*(w+2)]
b=10**9
d=[[b]*(w+2)]+[[b]+[0]*w+[b] for _ in range(h)]+[[b]*(w+2)]
d[0][1]=0
for i in range(1,h+1):
  for j in range(1,w+1):
    d[i][j]=min(d[i-1][j]+(s[i][j]=='#')*(s[i-1][j]=='.'),d[i][j-1]+(s[i][j]=='#')*(s[i][j-1]=='.'))
print(d[h][w])

Submission status: Accepted

Solution code:
h,w=map(int,input().split())
field=[list(input()) for i in range(h)]
ans=[[0 for i in range(w)]for j in range(h)]
if field[0][0]=='#':
  ans[0][0]=1

def black(i,j,f):
  if f==1:
    if field[i][j]=='#' and field[i-1][j]=='.':
      return 1
    else:
      return 0
  else:
    if field[i][j]=='#' and field[i][j-1]=='.':
      return 1
    else:
      return 0
for i in range(h):
  for j in range(w):
    if i==0 and j==0:
      continue
    elif i==0:
      ans[i][j]=ans[i][j-1]+black(i,j,2)
    elif j==0:
      ans[i][j]=ans[i-1][j]+black(i,j,1)
    else:
      ans[i][j]=min(ans[i-1][j]+black(i,j,1),ans[i][j-1]+black(i,j,2))
print(ans[-1][-1])

Submission status: Accepted

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

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

    # for i in range(h):
    #     for j in range(w):
    #         print(dp[i][j], end=' ')
    #     print()
    print(dp[h-1][w-1])


solve()

Submission status: Accepted

Solution code:

#ライブラリインポート
from collections import defaultdict

con = 10 ** 9 + 7
#入力受け取り
def getlist():
	return list(map(int, input().split()))
INF = float("inf")

#処理内容
def main():
	H, W = getlist()
	L = []
	for i in range(H):
		l = list(input())
		L.append(l)

	DP = [[INF] * W for i in range(H)]
	#初期化
	if L[0][0] == "#":
		DP[0][0] = 1
	else:
		DP[0][0] = 0

	for i in range(1, H):
		DP[i][0] = 0
	for i in range(1, W):
		DP[0][i] = 0

	for i in range(1, H):
		if L[i][0] != L[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 L[0][i] != L[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 L[i][j] != 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] != 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])

	# print(DP)

	ans = int((DP[-1][-1] + 1) // 2)
	print(ans)


if __name__ == '__main__':
	main()

Submission status: Accepted

Solution code:
import numpy as np
h,w=map(int,input().split())
s=[input() for _ in range(h)]
dp=np.zeros((h,w),np.int64)
if s[0][0]=='#':
      dp[0,0]=1
for i in range(h):
  for j in range(w):
    if (i,j)==(0,0):
      continue
    elif i==0:
      if s[i][j-1]=='.' and s[i][j]=='#':
        dp[i,j]=dp[i,j-1]+1
      else:
        dp[i,j]=dp[i,j-1]
    elif j==0:
      if s[i-1][j]=='.' and s[i][j]=='#':
        dp[i,j]=dp[i-1,j]+1
      else:
        dp[i,j]=dp[i-1,j]
    else:
      dp[i,j]=min(dp[i,j-1]+1 if s[i][j-1]=='.' and s[i][j]=='#' else dp[i,j-1],dp[i-1,j]+1 if s[i-1][j]=='.' and s[i][j]=='#' else dp[i-1,j])
print(dp[-1,-1])
#print(dp)

Submission status: Accepted

Solution code:
# https://atcoder.jp/contests/agc043/tasks/agc043_a
h, w = map(int, input().split())
matrix = []
for _ in range(h):
    row = list(input())
    matrix.append(row)

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

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

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

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline
from collections import deque
def main():
    H, W = map(int, input().split())
    field = [input().rstrip("\r\n") for _ in range(H)]
    dv = 201
    counts = [[dv for _ in range(W)] for _ in range(H)]
    que = deque([(0, 0)])
    if field[0][0] == "#":
        counts[0][0] = 1
    else:
        counts[0][0] = 0
    while len(que) > 0:
        h, w = que.popleft()
        for dh, dw in [(1, 0), (0, 1)]:
            nh, nw = h + dh, w + dw
            if nh >= H or nw >= W:continue
            if counts[nh][nw] == dv:que.append((nh, nw))
            if field[h][w] != field[nh][nw]:
                counts[nh][nw] = min(counts[nh][nw], counts[h][w]+1)
            else:
                counts[nh][nw] = min(counts[nh][nw], counts[h][w])
    if field[-1][-1] == "#":counts[-1][-1] += 1
    print(counts[-1][-1]//2)
if __name__ == "__main__":
    main()