Problem:


Score : 400 points

Problem Statement

Consider a grid with H rows and W columns of squares. Let (r, c) denote the square at the r-th row from the top and the c-th column from the left.
Each square is painted black or white.

The grid is said to be good if and only if the following condition is satisfied:

From (1, 1), we can reach (H, W) by moving one square right or down repeatedly, while always being on a white square.

Note that (1, 1) and (H, W) must be white if the grid is good.

Your task is to make the grid good by repeating the operation below. Find the minimum number of operations needed to complete the task. It can be proved that you can always complete the task in a finite number of operations.

Choose four integers r_0, c_0, r_1, c_1(1 \leq r_0 \leq r_1 \leq H, 1 \leq c_0 \leq c_1 \leq W). For each pair r, c (r_0 \leq r \leq r_1, c_0 \leq c \leq c_1), invert the color of (r, c) - that is, from white to black and vice versa.

Constraints

2 \leq H, W \leq 100

Input

Input is given from Standard Input in the following format:

H W
s_{11} s_{12} \cdots s_{1W}
s_{21} s_{22} \cdots s_{2W}
 \vdots
s_{H1} s_{H2} \cdots s_{HW}

Here s_{rc} represents the color of (r, c) - # stands for black, and . stands for white.

Output

Print the minimum number of operations needed.

Sample Input 1

3 3
.##
.#.
##.

Sample Output 1

1

Do the operation with (r_0, c_0, r_1, c_1) = (2, 2, 2, 2) to change just the color of (2, 2), and we are done.

Sample Input 2

2 2
#.
.#

Sample Output 2

2

Sample Input 3

4 4
..##
#...
###.
###.

Sample Output 3

0

No operation may be needed.

Sample Input 4

5 5
.#.#.
#.#.#
.#.#.
#.#.#
.#.#.

Sample Output 4

4



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


Sample output:
1

Submission status: Accepted

Solution code:
import sys

sys.setrecursionlimit(10 ** 5 + 10)


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


def resolve():
    H, W = map(int, input().split())
    maze = [[_ for _ in input()] for _ in range(W)]
    INF = 10 ** 5
    
    # dp[i][j]:=(i,j)に到達するまでに黒壁を壊す回数の最小値
    dp = [[INF] * W for _ in range(H)]
    
    if maze[0][0] == '#':
        dp[0][0] = 1
    else:
        dp[0][0] = 0
    
    for i in range(H):
        for j in range(W):
            for [dy, dx] in [[1, 0], [0, 1]]:
                ny, nx = i + dy, j + dx
                if ny >= H or nx >= W:
                    continue
                else:
                    if maze[i][j] == '.' and maze[ny][nx] == '#':
                        dp[ny][nx] = min(dp[ny][nx], dp[i][j] + 1)
                    else:
                        dp[ny][nx] = min(dp[ny][nx], dp[i][j])
    print(dp[H - 1][W - 1])


resolve()

Submission status: Accepted

Solution code:
import sys

sys.setrecursionlimit(10 ** 5 + 10)


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


def resolve():
    H, W = map(int, input().split())
    maze = [[_ for _ in input()] for _ in range(W)]
    INF = 10 ** 5
    # dp[i][j]:=(i,j)に到達するまでに黒壁を壊す回数の最小値
    dp = [[INF] * W for _ in range(H)]

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

    for i in range(H):
        for j in range(W):
            for [dy, dx] in [[1, 0], [0, 1]]:
                ny, nx = i + dy, j + dx
                if ny >= H or nx >= W:
                    continue
                else:
                    if maze[i][j] == '.' and maze[ny][nx] == '#':
                        dp[ny][nx] = min(dp[ny][nx], dp[i][j] + 1)
                    else:
                        dp[ny][nx] = min(dp[ny][nx], dp[i][j])
    print(dp[H - 1][W - 1])


resolve()

Submission status: Accepted

Solution code:
import sys
import fractions

sr = lambda: sys.stdin.readline().rstrip()
ir = lambda: int(sr())
lr = lambda: list(map(int, sr().split()))

H, W = lr()
dp = [[0 for _ in range(W)] for _ in range(H)]
masu = [sr() for _ in range(H)]
dp[0][0] = 1 if masu[0][0] == "#" else 0
for h, m in enumerate(masu):
    for w, s in enumerate(m):
        if w == 0 and h == 0:
            continue
        if w == 0:
            if masu[h-1][w] != s and s == "#":
                dp[h][w] += dp[h-1][w] + 1
            else:
                dp[h][w] += dp[h-1][w]
            continue
        if h == 0:
            if masu[h][w-1] != s and s == "#":
                dp[h][w] += dp[h][w-1] + 1
            else:
                dp[h][w] += dp[h][w-1]
            continue
        if masu[h-1][w] != s and s == "#":
            cand1 = dp[h][w] + dp[h-1][w] + 1
        else:
            cand1 = dp[h][w] + dp[h-1][w]
        if masu[h][w-1] != s and s == "#":
            cand2 = dp[h][w] + dp[h][w-1] + 1
        else:
            cand2 = dp[h][w] + dp[h][w-1]
        dp[h][w] = min(cand1, cand2)
print(dp[H-1][W-1])

Submission status: Accepted

Solution code:
def solve(H, W, s):
    scores = [[float('inf') for _ in range(W)] for _ in range(H)]
    scores[0][0] = 0 if s[0][0] == '.' else 1

    for i in range(H):
        for j in range(W):
            for x, y in [(i - 1, j), (i, j - 1)]:
                if x < 0 or y < 0:
                    continue
                if s[i][j] == '.' or s[x][y] == '#':
                    scores[i][j] = min(scores[i][j], scores[x][y])
                else:
                    scores[i][j] = min(scores[i][j], scores[x][y] + 1)

    return scores[H - 1][W - 1]

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

    print(solve(H, W, s))

Submission status: Accepted

Solution code:
h,w=map(int,input().split())
grid=[[1 if s=='#' else 0 for s in list(input())] for i in range(h)]
#print(grid)
maxi=10**5
from collections import deque
visited=[[maxi]*w for _ in range(h)]
def bfs(s):
    q=deque()
    q.append(s)
    visited[s[0]][s[1]]=grid[s[0]][s[1]]
    for r in range(h):
        for c in range(w):
            if r>=1:
                visited[r][c]=min(visited[r][c],visited[r-1][c]+grid[r][c])
                if grid[r-1][c]==1:
                    visited[r][c]=min(visited[r][c],visited[r-1][c])
            if c>=1:
                visited[r][c]=min(visited[r][c],visited[r][c-1]+grid[r][c])
                if grid[r][c-1]==1:
                    visited[r][c]=min(visited[r][c],visited[r][c-1])
            

bfs([0,0])
print(visited[-1][-1])

Submission status: Accepted

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

# array size HxW filled with zeroes
black = [[0 for c in range(W)] for r in range(H)]
# array size HxW filled with 10^18 (basically infinity)
dp = [[int(1e18) for c in range(W)] for r in range(H)]

for r in range(H):
    line = input()
    for c in range(W):
        black[r][c] = (line[c] == '#')

dp[0][0] = black[0][0] # this case is handled separately

for r in range(H):
    for c in range(W):
        if r >= 1:
            # r-1 can be indexed
            dp[r][c] = min(dp[r][c], dp[r-1][c] + (black[r][c] and not black[r-1][c]))
        if c >= 1:
            # c-1 can be indexed
            dp[r][c] = min(dp[r][c], dp[r][c-1] + (black[r][c] and not black[r][c-1]))

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

Submission status: Accepted

Solution code:
h,w = map(int,input().split())
a = [[(i == "#")*1 for i in list(input())] for _ in range(h)]
dp = [[float("inf")]*w for _ in range(h)]
dp[0][0] = a[0][0]
def cnt(i0,j0,i1,j1):
  if a[i0][j0] == 0 and a[i1][j1] == 1:
    return 1
  return 0

for s in range(h+w):
  for i in range(s+1):
    j = s - i
    if i >= h or j >= w:
      continue
    if i < h-1:
      dp[i+1][j] = min(dp[i+1][j],dp[i][j]+cnt(i,j,i+1,j))
    if j < w-1:
      dp[i][j+1] = min(dp[i][j+1],dp[i][j]+cnt(i,j,i,j+1))
print(dp[-1][-1])

Submission status: Accepted

Solution code:
import sys
from collections import deque

sys.setrecursionlimit(10 ** 7)
f_inf = float('inf')
mod = 10 ** 9 + 7


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

    # 白と黒が入れ替わった箇所をカウントする
    flip = [[f_inf for _ in range(W)] for _ in range(H)]

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

    que = deque([[0, 0]])
    while que:
        h, w = que.popleft()
        for dh, dw in ((0, 1), (1, 0)):
            next_h, next_w = h + dh, w + dw
            if next_h >= H or next_w >= W:
                continue

            if flip[next_h][next_w] == f_inf:
                que.append([next_h, next_w])

            # 白と黒が入れ替わったらカウントアップ
            if S[h][w] != S[next_h][next_w]:
                flip[next_h][next_w] = min(flip[next_h][next_w], flip[h][w] + 1)
            else:
                flip[next_h][next_w] = min(flip[next_h][next_w], flip[h][w])

    if S[H - 1][W - 1] == "#":
        flip[H - 1][W - 1] += 1

    # 操作の回数は白と黒が入れ替わった回数の半分（切り捨て）である
    print(flip[H - 1][W - 1] // 2)


if __name__ == '__main__':
    resolve()

Submission status: Accepted

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

s=[]

for r in range(H):
    s.append(list(input()))

c=[[200]*W for i in range(H)]
if s[0][0]==".":
    c[0][0]=0
else:
    c[0][0]=1

def rec(y,x):
    if c[y][x]!=200:
        return c[y][x]
    elif y==0 and x!=0:
        temp=rec(y,x-1)
        if s[y][x]!=s[y][x-1]:
            if s[y][x]=="#":
                temp+=1
        c[y][x]=temp
        return temp
    elif y!=0 and x==0:
        temp=rec(y-1,x)
        if s[y][x]!=s[y-1][x]:
            if s[y][x]=="#":
                temp+=1
        c[y][x]=temp
        return temp
    else:
        temp1 = rec(y, x - 1)
        if s[y][x] != s[y][x-1]:
            if s[y][x] == "#":
                temp1 += 1
        temp2 = rec(y - 1, x)
        if s[y][x] != s[y - 1][x]:
            if s[y][x] == "#":
                temp2 += 1
        temp=min(temp1,temp2)
        c[y][x]=temp
        return temp

ans=rec(H-1,W-1)

print(ans)

Submission status: Accepted

Solution code:
from queue import deque

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

inf = 10**10
dx = [1,0]
dy = [0,1]
que = deque()

#そのマスにたどり着くまでに色が変わった最小の回数を保存するリスト
flip_count = [[inf for i in range(w)]for j in range(h)]

if li[0][0] == "#":
    flip_count[0][0] = 1
else:
    flip_count[0][0] = 0

que.append([0,0])

while que:
    k = que.popleft()
    x = k[0]
    y = k[1]
    for i,j in zip(dx,dy):
        nx = x + i
        ny = y + j
        if nx >= w or ny >= h:
            continue
        if flip_count[ny][nx] == inf:
            que.append([nx,ny])
        if li[ny][nx] != li[y][x]:
            flip_count[ny][nx] = min(flip_count[ny][nx],flip_count[y][x]+1)
        else:
            flip_count[ny][nx] = min(flip_count[ny][nx],flip_count[y][x])

if li[-1][-1] == "#":
    flip_count[-1][-1] += 1

print(flip_count[-1][-1]//2)

Submission status: Accepted

Solution code:
INF = 10**9

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

# (i, j)に進むときの色の反転回数の最小値
dp = [[INF for j 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 i == H - 1 and j == W - 1:
            break
        
        if i != H - 1:
            if s[i][j] == '.' and s[i + 1][j] == '#':
                dp[i + 1][j] = min(dp[i][j] + 1, dp[i + 1][j])
            else:
                dp[i + 1][j] = min(dp[i][j], dp[i + 1][j])
        
        if j != W - 1:
            if s[i][j] == '.' and s[i][j + 1] == '#':
                dp[i][j + 1] = min(dp[i][j] + 1, dp[i][j + 1])
            else:
                dp[i][j + 1] = min(dp[i][j], dp[i][j + 1])

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

Submission status: Accepted

Solution code:
import numpy as np
import sys
read = sys.stdin.read
readline = sys.stdin.readline
readlines = sys.stdin.readlines
H, W = map(int, input().split())

I = [list(map(str, input())) for _ in range(H)]

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

for i in range(H):
	for j in range(W):
		if i == 0 and j == 0:
			continue
		if i == 0:
			dp[i][j] = dp[i][j-1] if I[i][j] == I[i][j-1] else dp[i][j-1] + 1
			continue
		if j == 0:
			dp[i][j] = dp[i-1][j] if I[i][j] == I[i-1][j] else dp[i-1][j] + 1
			continue

		dp[i][j] = dp[i][j-1] if I[i][j] == I[i][j-1] else dp[i][j-1] + 1
		if I[i][j] == I[i-1][j]:
			dp[i][j] = min(dp[i][j], dp[i-1][j])
		else:
			dp[i][j] = min(dp[i][j], dp[i-1][j] + 1)	

t = dp[-1][-1]
if I[0][0] == "#":
	t += 1
ans = -(-t//2)

print(ans)

Submission status: Accepted

Solution code:
import numpy as np

def func(x,y):
    if y-x == 2:
        return 1
    else:
        return 0


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

d = np.zeros((H,W))
dp = np.zeros((H,W))

for i in range(H):
    for j in range(W):
        if l[i][j] == "#":
            d[i][j] = 1
        else:
            d[i][j] = -1



for i in range(H-1):
    dp[i+1][0] = dp[i][0]+func(d[i][0],d[i+1][0])

for i in range(W-1):
    dp[0][i+1] = dp[0][i]+func(d[0][i],d[0][i+1])

for i in range(H-1):
    for j in range(W-1):
        dp[i+1][j+1]=min(dp[i][j+1]+func(d[i][j+1],d[i+1][j+1]),dp[i+1][j]+func(d[i+1][j],d[i+1][j+1]))

a = int(dp[-1][-1])
if d[0][0] == 1:
    a +=1
print(a)

Submission status: Accepted

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

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

if s_l[0][0] != 0:
    dp[0][0] += 1

for i in range(1,h):
    if dp[i-1][0]%2 != s_l[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 dp[0][j-1]%2 != s_l[0][j]:
        dp[0][j] = dp[0][j-1] + 1
    else:
        dp[0][j] = dp[0][j-1]

for i in range(1,h):
    for j in range(1,w):
        if dp[i-1][j]%2 != s_l[i][j]:
            plus_i = 1
        else:
            plus_i = 0
        if dp[i][j-1]%2 != s_l[i][j]:
            plus_j = 1
        else:
            plus_j = 0
        dp[i][j] = min(dp[i-1][j] + plus_i, dp[i][j-1] + plus_j)

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

Submission status: Accepted

Solution code:
H,W,*L = open(0).read().split()
H,W = map(int, (H,W))
dp = [[0]*W for i in range(H)]
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 j in range(1,W):
  if L[0][j]!=L[0][j-1]:
    dp[0][j] = dp[0][j-1]+1
  else:
    dp[0][j] = dp[0][j-1]
for i in range(1,H):
  for j in range(1,W):
    if L[i][j]!=L[i-1][j] and L[i][j]!=L[i][j-1]:
      dp[i][j] = min(dp[i-1][j],dp[i][j-1])+1
    elif L[i][j]!=L[i-1][j]:
      dp[i][j] = min(dp[i-1][j]+1,dp[i][j-1])
    elif L[i][j]!=L[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])
if L[0][0]=='.':
  ans = (dp[H-1][W-1]+1)//2
else:
  ans = (dp[H-1][W-1]+2)//2
print(ans)

Submission status: Accepted

Solution code:
h,w=map(int,input().split())
dp=[[0]*w for i in range(h)]
s=[input()for i in range(h)]
if s[0][0]=="#":
    dp[0][0]=1
for i in range(1,w):
    if s[0][i]=="#" and s[0][i-1]==".":
            dp[0][i]=dp[0][i-1]+1
    else:
        dp[0][i]=dp[0][i-1]
for i in range(1,h):
    for j in range(w):
        if j==0:
            if s[i][j]=="#" and s[i-1][j]==".":
                dp[i][j]=dp[i-1][j]+1
            else:
                dp[i][j]=dp[i-1][j]
            continue
        if s[i][j]=="#":
            p,q=0,0
            if s[i-1][j]=="#":
                p=1
            if s[i][j-1]=="#":
                q=1
            dp[i][j]=min(dp[i-1][j]-p,dp[i][j-1]-q)+1
        else:
            dp[i][j]=min(dp[i-1][j],dp[i][j-1])
print(dp[-1][-1])

Submission status: Accepted

Solution code:
from heapq import heappush, heappop

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

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

h = [(0, 0, 0)]
while h :
  cc, cy, cx = heappop(h)
  for dy, dx in ((1, 0), (0, 1)) :
    ny, nx = cy + dy, cx + dx
    if 0 <= ny < H and 0 <= nx < W :
      nc = cc + (s[ny][nx] != s[cy][cx])
      if nc < dist[ny][nx] :
        heappush(h, (nc, ny, nx))
        dist[ny][nx] = nc
        
print((dist[H-1][W-1] + 2 - s[0][0] - s[-1][-1]) // 2)

Submission status: Accepted

Solution code:
import math  # noqa
import bisect  # noqa
import queue  # noqa


if __name__ == '__main__':
    H, W = map(int, input().split())
    S = [[s for s in input()] for _ in range(H)]

    INF = 1000000005
    traj = [[INF for _ in range(W)] for _ in range(H)]
    que = queue.Queue()
    que.put((0, 0))
    traj[0][0] = 0 if S[0][0] == '.' else 1
    while not que.empty():
        h, w = que.get()
        d = ((0, 1), (1, 0))
        for dh, dw in d:
            nh = h + dh
            nw = w + dw
            if nh < 0 or H <= nh or nw < 0 or W <= nw:
                continue
            cost = traj[h][w]
            if S[h][w] == '.' and S[nh][nw] == '#':
                cost += 1
            if cost < traj[nh][nw]:
                traj[nh][nw] = cost
                que.put((nh, nw))

    print(traj[-1][-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

for c in range(W):
    for r in range(H):
        if r > 0:
            count=0
            if s[r-1][c]=='.' and s[r][c]=='#':
                count = 1
            dp[r][c] = min(dp[r][c], dp[r-1][c]+count)
        if c > 0:
            count=0
            if s[r][c-1]=='.' and s[r][c]=='#':
                count = 1
            dp[r][c] = min(dp[r][c], dp[r][c-1]+count)
print(dp[H-1][W-1])

Submission status: Accepted

Solution code:
# python3.4.2用
import math
import fractions
import bisect
import collections
import itertools
import heapq
import string
import sys
import copy
from decimal import *
from collections import deque
sys.setrecursionlimit(10**7)
MOD = 10**9+7
INF = float('inf') #無限大
def gcd(a,b):return fractions.gcd(a,b) #最大公約数
def lcm(a,b):return (a*b) // fractions.gcd(a,b) #最小公倍数
def iin(): return int(sys.stdin.readline()) #整数読み込み
def ifn(): return float(sys.stdin.readline()) #浮動小数点読み込み
def isn(): return sys.stdin.readline().split() #文字列読み込み
def imn(): return map(int, sys.stdin.readline().split()) #整数map取得
def imnn(): return map(lambda x:int(x)-1, sys.stdin.readline().split()) #整数-1map取得
def fmn(): return map(float, sys.stdin.readline().split()) #浮動小数点map取得
def iln(): return list(map(int, sys.stdin.readline().split())) #整数リスト取得
def iln_s(): return sorted(iln()) # 昇順の整数リスト取得
def iln_r(): return sorted(iln(), reverse=True) # 降順の整数リスト取得
def fln(): return list(map(float, sys.stdin.readline().split())) # 浮動小数点リスト取得
def join(l, s=''): return s.join(l) #リストを文字列に変換
def perm(l, n): return itertools.permutations(l, n) # 順列取得
def perm_count(n, r): return math.factorial(n) // math.factorial(n-r) # 順列の総数
def comb(l, n): return itertools.combinations(l, n) # 組み合わせ取得
def comb_count(n, r): return math.factorial(n) // (math.factorial(n-r) * math.factorial(r)) #組み合わせの総数
def two_distance(a, b, c, d): return ((c-a)**2 + (d-b)**2)**.5 # 2点間の距離
def m_add(a,b): return (a+b) % MOD
def lprint(l): print(*l, sep='\n')
def sieves_of_e(n):
    is_prime = [True] * (n+1)
    is_prime[0] = False
    is_prime[1] = False
    for i in range(2, int(n**0.5)+1):
        if not is_prime[i]: continue
        for j in range(i * 2, n+1, i): is_prime[j] = False
    return is_prime

H,W = imn()

s = [input() for _ in range(H)]
dp = [[INF for _ in range(W)] for _ in range(H)]
dp[0][0] = 0
if s[0][0] == '#': dp[0][0] = 1

for i in range(H):
    for j in range(W):
        if i+1 < H:
            cnt = dp[i][j]
            if s[i][j] == "." and s[i+1][j] == "#":
                cnt += 1 
            dp[i+1][j] = min(dp[i+1][j], cnt)
        if j+1 < W:
            cnt = dp[i][j]
            if s[i][j] == "." and s[i][j+1] == "#":
                cnt += 1
            dp[i][j+1] = min(dp[i][j+1], cnt)
print(dp[-1][-1])

Submission status: Accepted

Solution code:
# python3.4.2用
import math
import fractions
import bisect
import collections
import itertools
import heapq
import string
import sys
import copy
from decimal import *
from collections import deque
sys.setrecursionlimit(10**7)
MOD = 10**9+7
INF = float('inf') #無限大
def gcd(a,b):return fractions.gcd(a,b) #最大公約数
def lcm(a,b):return (a*b) // fractions.gcd(a,b) #最小公倍数
def iin(): return int(sys.stdin.readline()) #整数読み込み
def ifn(): return float(sys.stdin.readline()) #浮動小数点読み込み
def isn(): return sys.stdin.readline().split() #文字列読み込み
def imn(): return map(int, sys.stdin.readline().split()) #整数map取得
def imnn(): return map(lambda x:int(x)-1, sys.stdin.readline().split()) #整数-1map取得
def fmn(): return map(float, sys.stdin.readline().split()) #浮動小数点map取得
def iln(): return list(map(int, sys.stdin.readline().split())) #整数リスト取得
def iln_s(): return sorted(iln()) # 昇順の整数リスト取得
def iln_r(): return sorted(iln(), reverse=True) # 降順の整数リスト取得
def fln(): return list(map(float, sys.stdin.readline().split())) # 浮動小数点リスト取得
def join(l, s=''): return s.join(l) #リストを文字列に変換
def perm(l, n): return itertools.permutations(l, n) # 順列取得
def perm_count(n, r): return math.factorial(n) // math.factorial(n-r) # 順列の総数
def comb(l, n): return itertools.combinations(l, n) # 組み合わせ取得
def comb_count(n, r): return math.factorial(n) // (math.factorial(n-r) * math.factorial(r)) #組み合わせの総数
def two_distance(a, b, c, d): return ((c-a)**2 + (d-b)**2)**.5 # 2点間の距離
def m_add(a,b): return (a+b) % MOD
def lprint(l): print(*l, sep='\n')
def sieves_of_e(n):
    is_prime = [True] * (n+1)
    is_prime[0] = False
    is_prime[1] = False
    for i in range(2, int(n**0.5)+1):
        if not is_prime[i]: continue
        for j in range(i * 2, n+1, i): is_prime[j] = False
    return is_prime

H,W = imn()

s = [input() for _ in range(H)]
d = [[INF for _ in range(W)] for _ in range(H)]
d[0][0] = 0
if s[0][0] == '#': d[0][0] = 1

xd = [1, 0]
yd = [0, 1]
que = deque([(0, 0)])
cnt = 0
while len(que) > 0:
    cnt += 1
    point = que.popleft()
    x = point[0]
    y = point[1]
    if x == W-1 and y == H-1: continue
    for i in range(2):
        nx = x + xd[i]
        ny = y + yd[i]
        if nx >= W or ny >= H: continue
        if s[ny][nx] == '#' and s[y][x] == '.': 
            if d[ny][nx] > d[y][x]+1:
                d[ny][nx] = d[y][x]+1
                que.append((nx,ny))
        else:
            if d[ny][nx] > d[y][x]:
                d[ny][nx] = d[y][x]
                que.append((nx,ny))
print(d[H-1][W-1])

Submission status: Accepted

Solution code:
h,w = map(int,input().split())
s = [input()for _ in range(h)]
dp = [[10**8]*(w+1) for _ in range(h+1)]
dp[0][0] = 0
for i in range(h):
    for j in range(w): 
        if s[i][j] == '.':
            if i+1 < h 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+1 < w 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:
            dp[i+1][j]  = min(dp[i+1][j] ,dp[i][j])
            dp[i][j+1] = min(dp[i][j+1],dp[i][j])

            
        
ans = dp[h-1][w-1]
if s[0][0] == '#':ans += 1
print(ans)

Submission status: Accepted

Solution code:
H, W = map(int, input().split())
grid = [input() for _ in range(H)]
dp = [[float('inf')] * W for i in range(H)]
dp[0][0] = 1 if grid[0][0] == '#' else 0

for i in range(H):
    for j in range(W):
        for y, x in ((1,0), (0,1)):
            ni, nj = i + y, j + x
            if ni >= H or nj >= W:
                continue
            c = 0
            if grid[ni][nj] == '#' and grid[i][j] == '.':
                c = 1
            dp[ni][nj] = min(dp[ni][nj], dp[i][j] + c)

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

Submission status: Accepted

Solution code:
h,w = map(int,input().split())
s = [list(str(input())) for i in range(h)]
dp = [[10 ** 10] * w for i in range(h)]
if s[0][0] == "#":dp[0][0] = 1
else:dp[0][0] = 0
for i in range(w):
    for j in range(h):
        if s[j][i] == "#":
            s[j][i] = 1
        else:
            s[j][i] = 0
for i in range(1,h+w-1):
    for j in range(i+1):
        if 0 < j < h and 0 <= i-j < w:
            dp[j][i-j] = min(dp[j-1][i-j]+(s[j][i-j]&~s[j-1][i-j]),dp[j][i-j])
        if 0 < i-j < w and 0 <= j < h:
            dp[j][i-j] = min(dp[j][i-j-1]+(s[j][i-j]&~s[j][i-j-1]),dp[j][i-j])
print(dp[h-1][w-1])

Submission status: Accepted

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

s = []
for _ in range(h):
	s.append(list(input()))

inf = float('inf')
dp = [[inf for _ in range(w)] for _ in range(h)]
dp[0][0] = 0

for i in range(h):
	for j in range(w):
		if s[i][j] == ".":
			if j > 0 and i > 0:
				dp[i][j] = min(dp[i-1][j],dp[i][j-1])
			elif j > 0 and i == 0:
				dp[i][j] = dp[i][j-1]
			elif j == 0 and i > 0:
				dp[i][j] = dp[i-1][j]
		else:
			tmp1 = inf
			tmp2 = inf
			if i > 0:
				tmp1 = dp[i-1][j]
				if s[i-1][j] == ".":
					tmp1 += 1
			if j > 0:
				tmp2 = dp[i][j-1]
				if s[i][j-1] == ".":
					tmp2 += 1
			dp[i][j] = min(tmp1,tmp2)
			if i==0 and j==0:
				dp[i][j] = 1

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

Submission status: Accepted

Solution code:
from itertools import product
from collections import deque

class ZeroOneBFS:
    def __init__(self, N):
        self.N = N # #vertices
        self.E = [[] for _ in range(N)]
        
    def add_edge(self, init, end, weight, undirected=False):
        assert weight in [0, 1]
        self.E[init].append((end, weight))
        if undirected: self.E[end].append((init, weight))
        
    def distance(self, s):
        INF = float('inf')
        E, N = self.E, self.N
        dist = [INF] * N # the distance of each vertex from s
        prev = [-1] * N # the previous vertex of each vertex on a shortest path from s
        dist[s] = 0
        dq = deque([(0, s)]) # (dist, vertex)
        n_visited = 0 # #(visited vertices)
        while dq:
            d, v = dq.popleft() 
            if dist[v] < d: continue # (s,v)-shortest path is already calculated
            for u, c in E[v]:
                temp = d + c
                if dist[u] > temp:
                    dist[u] = temp; prev[u] = v
                    if c == 0: dq.appendleft((temp, u))
                    else: dq.append((temp, u))
            n_visited += 1
            if n_visited == N: break
        self.dist, self.prev = dist, prev
        return dist
    
    def shortest_path(self, t):
        P = []
        prev = self.prev
        while True:
            P.append(t)
            t = prev[t]
            if t == -1: break
        return P[::-1]

H, W = map(int, input().split())
zobfs = ZeroOneBFS(H * W)
 
def vtx(i, j): return i*W + j
def coord(n): return divmod(n, W)
 
grid = [input() for _ in range(H)] # |string| = W
E = [[] for _ in range(H * W)]
ans = 0 if grid[0][0] == '.' else 1
for i, j in product(range(H), range(W)):
    v = vtx(i, j)
    check = [vtx(i+dx, j+dy) for dx, dy in [(1, 0), (0, 1)] if i+dx <= H-1 and j+dy <= W-1]
    for u in check:
        x, y = coord(u)
        if grid[i][j] == '.' and grid[x][y] == '#':
            zobfs.add_edge(v, u, 1)
        else:
            zobfs.add_edge(v, u, 0)
dist = zobfs.distance(0)
ans += dist[vtx(H-1, W-1)]
print(ans)

Submission status: Accepted

Solution code:
h , w = map(int,input().split())
p = []
for i in range(h):
    kar = list(input())
    p.append(kar)
d = [[0 for i in range(w)] for j in range(h)]
for i in range(w):
    if i == 0:
        if p[0][0] == "#":
            d[0][0] = 1
    else:
        if p[0][i-1] == "." and p[0][i] == "#":
            d[0][i] += 1
        d[0][i] += d[0][i-1]
for i in range(1,h):
    if p[i-1][0] == "." and p[i][0] == "#":
        d[i][0] += 1
    d[i][0] += d[i-1][0]    

for x in range(1,w):
    for y in range(1,h):
        m = 0
        s = 0
        if p[y][x-1] == "." and p[y][x] == "#":
            m += 1
        m += d[y][x-1]
        if p[y-1][x] == "." and p[y][x] == "#":
            s += 1
        s += d[y-1][x]
        d[y][x] = min(m,s)
print(d[h-1][w-1])

Submission status: Accepted

Solution code:
import sys

sys.setrecursionlimit(10 ** 7)
rl = sys.stdin.readline


def solve():
    H, W = map(int, rl().split())
    s = [list(input()) for _ in range(H)]
    
    dp = [[0] * W for _ in range(H)]
    dp[0][0] = s[0][0] == '#'
    for i in range(1, W):
        dp[0][i] = dp[0][i - 1] + (s[0][i - 1] == '.' and s[0][i] == '#')
    for i in range(1, H):
        dp[i][0] = dp[i - 1][0] + (s[i - 1][0] == '.' and s[i][0] == '#')
    
    for i in range(1, H):
        for j in range(1, W):
            dy = s[i - 1][j] == '.' and s[i][j] == '#'
            dx = s[i][j - 1] == '.' and s[i][j] == '#'
            dp[i][j] = min(dp[i - 1][j] + dy, dp[i][j - 1] + dx)
    print(dp[-1][-1])


if __name__ == '__main__':
    solve()

Submission status: Accepted

Solution code:
MOD = 10**9 + 7
INT_MAX = (1 << 63) - 1


if __name__ == "__main__":
    # test_case_num = int(input())

    # for _ in range(test_case_num):
    m, n = map(int, input().split())
    grid = [input().strip() for _ in range(m)]

    dp = [float('inf')] * n
    for i, row in enumerate(grid):
        for j, val in enumerate(row):
            if i == 0 and j == 0:
                dp[j] = grid[0][0] == '#'
            else:
                temp = INT_MAX
                if i > 0:
                    temp = min(dp[j] + (val == '#' != grid[i-1][j]), temp)
                if j > 0:
                    temp = min(dp[j-1] + (val == '#' != grid[i][j-1]), temp)
                dp[j] = temp
        # print(dp)

    print(dp[-1])

Submission status: Accepted

Solution code:
#coding:utf-8
import sys,os
from collections import defaultdict, deque
from fractions import gcd
from math import ceil, floor
sys.setrecursionlimit(10**6)
write = sys.stdout.write
dbg = (lambda *something: print(*something)) if 'TERM_PROGRAM' in os.environ else lambda *x: 0
def main(given=sys.stdin.readline):
    input = lambda: given().rstrip()
    LMIIS = lambda: list(map(int,input().split()))
    II = lambda: int(input())
    XLMIIS = lambda x: [LMIIS() for _ in range(x)]
    YN = lambda c : print('Yes') if c else print('No')
    MOD = 10**9+7

    H,W = LMIIS()
    table = [0]*H
    for i in range(H):
        table[i] = input()
    num_route = [[0]*W for _ in range(H)]

    if table[0][0] == '#':
        num_route[0][0] = 1

    for i in range(1,W):
        if table[0][i] == '#' and table[0][i] != table[0][i-1]:
            num_route[0][i] = num_route[0][i-1] + 1
        else:
            num_route[0][i] = num_route[0][i-1]

    for i in range(1,H):
        if table[i][0] == '#' and table[i][0] != table[i-1][0]:
            num_route[i][0] = num_route[i-1][0] + 1
        else:
            num_route[i][0] = num_route[i-1][0]
    
    for i in range(1,H):
        for j in range(1,W):
            l = u = 0
            if table[i][j] == '#' and table[i][j] != table[i][j-1]:
                l = num_route[i][j-1] + 1
            else:
                l = num_route[i][j-1]
            if table[i][j] == '#' and table[i][j] != table[i-1][j]:
                u = num_route[i-1][j] + 1
            else:
                u = num_route[i-1][j]
            num_route[i][j] = min(l,u)
            
    #print(num_route)
    print(num_route[H-1][W-1])

if __name__ == '__main__':
    main()