Problem:


Score : 400 points

Problem Statement

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

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

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

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

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

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

Constraints

2 \leq H, W \leq 100

Input

Input is given from Standard Input in the following format:

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

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

Output

Print the minimum number of operations needed.

Sample Input 1

3 3
.##
.#.
##.

Sample Output 1

1

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

Sample Input 2

2 2
#.
.#

Sample Output 2

2

Sample Input 3

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

Sample Output 3

0

No operation may be needed.

Sample Input 4

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

Sample Output 4

4



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


Sample output:
1

Submission status: Accepted

Solution code:
from pprint import pprint
H, W = map(int, input().split())
s = ["-1"]
dp = [[1000] * (W + 1) for _ in range(H + 1)]
for _ in range(H):
    s.append(input())
s = list(map(lambda x: " " + x, s))
for y in range(1, H + 1):
    for x in range(1, W + 1):
        if y == 1 and x == 1:
            if s[y][x] == "#":
                dp[y][x] = 1
            else:
                dp[y][x] = 0
            continue
        if x == 1:
            if s[y][x] == "#":
                if s[y - 1][x] == "#":
                    dp[y][x] = dp[y - 1][x]
                else:
                    dp[y][x] = dp[y - 1][x] + 1
            else:
                dp[y][x] = dp[y - 1][x]
        elif y == 1:
            if s[y][x] == "#":
                if s[y][x - 1] == "#":
                    dp[y][x] = dp[y][x - 1]
                else:
                    dp[y][x] = dp[y][x - 1] + 1
            else:
                dp[y][x] = dp[y][x - 1]
        else:
            if s[y][x] == "#":
                if s[y][x - 1] == "#":
                    dp[y][x] = dp[y][x - 1]
                if s[y - 1][x] == "#":
                    dp[y][x] = min(dp[y][x], dp[y - 1][x])
                if s[y][x - 1] != "#" 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])
#pprint(dp)
print(dp[H][W])

Submission status: Accepted

Solution code:
h, w  = map(int, input().split())
s = [input() for _ in range(h)]
m = [[-1]*w for _ in range(h)]
def dp(x, y):
    if m[x][y] == -1:
        if x == 0 and y == 0:
            m[x][y] = 1 if s[x][y] == "#" else 0
        elif x == 0:
            a = dp(x, y-1)
            m[x][y] = a+1 if s[x][y] == "#" and s[x][y-1] == "." else a
        elif y == 0:
            b = dp(x-1, y)
            m[x][y] = b+1 if s[x][y] == "#" and s[x-1][y] == "." else b
        else:
            a = dp(x, y-1)
            b = dp(x-1, y)
            c = a+1 if s[x][y] == "#" and s[x][y-1] == "." else a
            d = b+1 if s[x][y] == "#" and s[x-1][y] == "." else b
            m[x][y] = min(c, d)
    return m[x][y]
print(dp(h-1, w-1))

Submission status: Accepted

Solution code:
def resolve():
  H, W = map(int, input().split(" "))
  s = []
  dp = [[0] * W for i in range(H)]
  for _ in range(H):
    s.append([x == "." for x in list(input())])

  for h in range(H):
    for w in range(W):
      if h == 0 and w == 0:
        if not s[0][0]:
          dp[0][0] = 1

      elif h == 0:
        dp[0][w] = dp[0][w-1]
        if s[0][w-1] and not s[0][w]:
          dp[0][w] += 1

      elif w == 0:
        dp[h][0] = dp[h-1][0]
        if s[h-1][0] and not s[h][0]:
          dp[h][0] += 1

      else:
        # 左側と上側を見て、操作回数が最小になるようにする。
        # 上だけをみる
        temp_up = dp[h-1][w]
        if s[h-1][w] and not s[h][w]:
          temp_up += 1

        # 左だけを見る
        temp_left = dp[h][w-1]
        if s[h][w-1] and not s[h][w]:
          temp_left += 1

        dp[h][w] = min(temp_up, temp_left)

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

if __name__ == "__main__":
  resolve()

Submission status: Accepted

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

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

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

adjacent = [[1, 0], [0, 1]]

for i in range(H):
    for j in range(W):
        for dy, dx in adjacent:
            ny = i+dy
            nx = j+dx
            if ny == H or nx == W:
                continue
            # 壁の中に移動する時
            if gridgraph[i][j] == "." and gridgraph[ny][nx] == "#":
                dp[ny][nx] = min(dp[i][j]+1, dp[ny][nx])
            else:
                dp[ny][nx] = min(dp[i][j], dp[ny][nx])
print(dp[H-1][W-1])

Submission status: Accepted

Solution code:
import sys
H, W = map(int, input().split())
S = [list(s.rstrip()) for s in sys.stdin.readlines()]
dp = [[10**9] * W for _ in range(H)]
if S[0][0] == '#':
  dp[0][0] = 1
else:
  dp[0][0] = 0
for h in range(H):
  for w in range(W):
    for a, b in ((h+1, w), (h, w+1)):
      if a >= H or b >= W:
        continue
      else:
        if S[h][w] == '.' and S[a][b] == '#':
          dp[a][b] = min(dp[a][b], dp[h][w]+1)
        else:
          dp[a][b] = min(dp[a][b], dp[h][w])
print(dp[H-1][W-1])

Submission status: Accepted

Solution code:
import sys

h, w = map(int, input().split())
s = [list(x.rstrip()) for x in sys.stdin.readlines()]
dp = [[10**6]*w for _ 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):
        for k in range(2):
            nx, ny = i + (k + 1)%2, j + k%2
            if nx >= w or ny >= h:
                continue
            else:
                add = 0
                if s[ny][nx] == "#" and s[j][i] == ".":
                    add = 1
                dp[ny][nx] = min(dp[ny][nx], dp[j][i] + add)
print(dp[h-1][w-1])

Submission status: Accepted

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

N = [[10**9]*W]*H
l = 0
u = 0
if S[0][0] == '#' :
    N[0][0] = 1
else :
    N[0][0] = 0
for i in range(H) :
    for j in range(W) :
        if i == 0 and j == 0 :
            continue
        #横移動
        l = N[i][j-1]
        #縦移動
        u = N[i-1][j]

        if S[i][j-1] == '.' and  S[i][j] == '#' :
            l += 1
        if S[i-1][j] == '.' and  S[i][j] == '#' :
            u += 1
        N[i][j] = min(l,u)

print(N[-1][-1])

Submission status: Accepted

Solution code:
import sys
import math
import copy
import heapq
from functools import cmp_to_key
from bisect import bisect_left, bisect_right
from collections import defaultdict, deque, Counter
sys.setrecursionlimit(1000000)

# input aliases
input = sys.stdin.readline
getS = lambda: input().strip()
getN = lambda: int(input())
getList = lambda: list(map(int, input().split()))
getZList = lambda: [int(x) - 1 for x in input().split()]

INF = float("inf")
MOD = 10**9 + 7
divide = lambda x: pow(x, MOD-2, MOD)

def nck(n, k, kaijyo):
    return (npk(n, k, kaijyo) * divide(kaijyo[k])) % MOD

def npk(n, k, kaijyo):
    if k == 0 or k == n:
        return n % MOD
    return (kaijyo[n] * divide(kaijyo[n-k])) % MOD

def fact_and_inv(SIZE):
    inv = [0] * SIZE  # inv[j] = j^{-1} mod MOD
    fac = [0] * SIZE  # fac[j] = j! mod MOD
    finv = [0] * SIZE  # finv[j] = (j!)^{-1} mod MOD
    inv[1] = 1
    fac[0] = fac[1] = 1
    finv[0] = finv[1] = 1
    for i in range(2, SIZE):
        inv[i] = MOD - (MOD // i) * inv[MOD % i] % MOD
        fac[i] = fac[i - 1] * i % MOD
        finv[i] = finv[i - 1] * inv[i] % MOD

    return fac, finv

def renritsu(A, Y):
    # example 2x + y = 3, x + 3y = 4
    # A = [[2,1], [1,3]])
    # Y = [[3],[4]] または [3,4]
    A = np.matrix(A)
    Y = np.matrix(Y)
    Y = np.reshape(Y, (-1, 1))
    X = np.linalg.solve(A, Y)

    # [1.0, 1.0]
    return X.flatten().tolist()[0]

class TwoDimGrid:
    # 2次元座標 -> 1次元
    def __init__(self, h, w, wall="o"):
        self.h = h
        self.w = w
        self.size = (h+2) * (w+2)
        self.wall = wall
        self.get_grid()
        self.init_cost()

    def get_grid(self):
        grid = [self.wall * (self.w + 2)]
        for i in range(self.h):
            grid.append(self.wall + getS() + self.wall)

        grid.append(self.wall * (self.w + 2))
        self.grid = grid
    def init_cost(self):
        self.cost = [INF] * self.size

    def pos(self, x, y):
        # 壁も含めて0-indexed 元々の座標だけ考えると1-indexed
        return y * (self.w + 2) + x
    def getgrid(self, x, y):
        return self.grid[y][x]
    def get(self, x, y):
        return self.cost[self.pos(x, y)]
    def set(self, x, y, v):
        self.cost[self.pos(x, y)] = v
        return
    def show(self):
        for i in range(self.h+2):
            print(self.cost[(self.w + 2) * i:(self.w + 2) * (i+1)])
    def showsome(self, tgt):
        for t in tgt:
            print(t)
        return
    def showsomejoin(self, tgt):
        for t in tgt:
            print("".join(t))
        return

    def search(self):
        grid = self.grid
        move = [(0, 1), (0, -1), (1, 0), (-1, 0)]
        move_eight = [(0, 1), (0, -1), (1, 0), (-1, 0), (1, 1), (1, -1), (-1, 1), (-1, -1)]
        d = deque()
        d.append((1,1))
        self.set(1,1,0)
        while(d):
            cx, cy = d.popleft()
            cc = self.get(cx, cy)
            if self.getgrid(cx, cy) == self.wall:
                continue
            for dx, dy in [(1, 0), (0, 1)]:
                nx, ny = cx + dx, cy + dy
                if self.getgrid(cx, cy) == self.getgrid(nx, ny):
                    if self.get(nx, ny) > cc:
                        d.append((nx, ny))
                        self.set(nx, ny, cc)
                else:
                    if self.get(nx, ny) > cc + 1:
                        d.append((nx, ny))
                        self.set(nx, ny, cc + 1)

        # self.show()
        ans = (self.get(self.w, self.h))
        if self.getgrid(1,1) == "#":
            ans += 1
        print((ans + 1) // 2)

def soinsu(n):
    ret = defaultdict(int)
    for i in range(2, int(math.sqrt(n) + 2)):
        if n % i == 0:
            while True:
                if n % i == 0:
                    ret[i] += 1
                    n //= i
                else:
                    break

    if not ret:
        return {n: 1}
    return ret


def solve():
    h, w = getList()
    G = TwoDimGrid(h, w)
    G.search()




def main():
    n = getN()
    for _ in range(n):
        solve()

    return
if __name__ == "__main__":
    # main()
    solve()

Submission status: Accepted

Solution code:
h,w=map(int,input().split())
s=[0]*h
t=[0]*h
for i in range(h):
  st=str(input())
  st=list(st)
  s[i]=st
  tt=[0]*w
  t[i]=tt
if s[0][0]=="#":
  t[0][0]=1
for i in range(1,h):
  t[i][0]=t[i-1][0]
  if s[i-1][0]=="." and s[i][0]=="#":
    t[i][0]=t[i-1][0]+1
for i in range(1,w):
  t[0][i]=t[0][i-1]
  if s[0][i-1]=="." and s[0][i]=="#":
    t[0][i]=t[0][i-1]+1
for i in range(1,w):
  for j in range(1,h):
    if s[j-1][i]=="." and s[j][i]=="#":
      t1=t[j-1][i]+1
    else:
      t1=t[j-1][i]
    if s[j][i-1]=="." and s[j][i]=="#":
      t2=t[j][i-1]+1
    else:
      t2=t[j][i-1]
    t[j][i]=min(t1,t2)
print(t[h-1][w-1])

Submission status: Accepted

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


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

for h_i in range(h):
    for w_i in range(w):
        if h_i+1 < h:
            if sl[h_i][w_i] == '.' and sl[h_i+1][w_i] == '#':
                dp[h_i+1][w_i] = min( dp[h_i+1][w_i], dp[h_i][w_i]+1 )
            else:
                dp[h_i+1][w_i] = min( dp[h_i+1][w_i], dp[h_i][w_i] )

        if w_i+1 < w:
            if sl[h_i][w_i] == '.' and sl[h_i][w_i+1] == '#':
                dp[h_i][w_i+1] = min( dp[h_i][w_i+1], dp[h_i][w_i]+1 )
            else:
                dp[h_i][w_i+1] = min( dp[h_i][w_i+1], dp[h_i][w_i] )


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

Submission status: Accepted

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

dp = [[0]*(W+1) for _ in range(H+1)]
for h in range(H+1):
    dp[h][0] = H*2
for w in range(W+1):
    dp[0][w] = W*2
dp[0][1] = 0

for h in range(1, H+1):
    for w in range(1, W+1):
        dp[h][w] = min(dp[h-1][w]+(S[h][w]!=S[h-1][w]), dp[h][w-1]+(S[h][w]!=S[h][w-1]))

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

Submission status: Accepted

Solution code:
# AGC 043 A
H,W = map(int, input().split())
table = [input() for _ in range(H)]

inf = 10**9
dp = [[inf] * (W+1) for _ in range(H+1)]
dp[0][0] = 0 if table[0][0] == "." else 1

for h in range(H):
    for w in range(W):
        flg = table[h][w] == "." and (table[h][w+1] == "#" if w < W-1 else True) 
        dp[h][w+1] = min(dp[h][w+1], dp[h][w] + 1 if flg else dp[h][w])

        flg = table[h][w] == "." and (table[h+1][w] == "#" if h < H-1 else True)
        dp[h+1][w] = dp[h][w] + 1 if flg else dp[h][w]

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

Submission status: Accepted

Solution code:
def input_li():
    return list(map(int, input().split()))

def input_int():
    return int(input())

H, W = input_li()
board = [input() for _ in range(H)]
# dp[x][y] ... マス(x, y)時点で実行した操作の最小回数
dp = [[10 ** 9] * W for _ in range(H)]
dp[0][0] = 1 if board[0][0] == '#' else 0
for h in range(H):
    for w in range(W):
        is_now_black = board[h][w] == '#'
        if h == 0 and w != 0:
            dp[h][w] = dp[h][w - 1] + (1 if is_now_black and board[h][w - 1] == '.' else 0)
        elif h != 0 and w == 0:
            dp[h][w] = dp[h - 1][w] + (1 if is_now_black and board[h - 1][w] == '.' else 0)
        elif h != 0 and w != 0:
            from_w = dp[h][w - 1] + (1 if is_now_black and board[h][w - 1] == '.' else 0)
            from_h = dp[h - 1][w] + (1 if is_now_black and board[h - 1][w] == '.' else 0)
            dp[h][w] = min(from_h, from_w)
print(dp[-1][-1])

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
from collections import deque

h, w = map(int, input().split())
maze = [[i == "#" for i in input()] for _ in range(h)]

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

que = deque([])
que.append((0, 0, maze[0][0], 1 if maze[0][0] else 0))
count = [[h + w] * w for _ in range(h)]

while que:
    x, y, b, c = que.pop()
    if c >= count[x][y]:
        continue
    count[x][y] = c
    if x == h - 1 and y == w - 1:
        continue
    for i in range(2):
        nx = x + dx[i]
        ny = y + dy[i]

        if not (0 <= nx < h and 0 <= ny < w):
            continue
        que.append((nx, ny, maze[nx][ny], c + (not b and maze[nx][ny])))
print(count[h - 1][w - 1])

Submission status: Accepted

Solution code:
def resolve():
    '''
    code here
    '''
    import collections
    import numpy as np
    H, W = [int(item) for item in input().split()]

    grid = [[item for item in input()] for _ in range(H)]
    dp = [[300 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 grid[0][0] == '#':
                    dp[i+1][j+1] = 1
                else:
                    dp[i+1][j+1] = 0
            else:
                add_v = 0
                add_h = 0
                if grid[i][j] != grid[i][j-1]:
                    add_h = 1
        
                if grid[i][j] != grid[i-1][j]:
                    add_v = 1

                dp[i+1][j+1] = min(dp[i+1][j]+add_h, dp[i][j+1]+add_v)
    # print(dp)
    if grid[H-1][W-1] == '#':
        print(dp[H][W]//2+1)
    else:
        print(dp[H][W]//2)

if __name__ == "__main__":
    resolve()

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

Solution code:
h,w= map(int,input().split())
tb = [input() for _ in range(h)]
st = [[0 for _ in range(w)] for _ in range(h)]
for i in range(h):
    for j in range(w):
        if i==0 and j==0:st[i][j]= (1 if tb[i][j]=='#' else 0)
        else:
            tr=td=999999999
            if i!=0:
                td=st[i-1][j]+(1 if (tb[i-1][j]=='.' and tb[i][j]=='#') else 0)
            if j!=0:
                tr=st[i][j-1]+(1 if (tb[i][j-1]=='.' and tb[i][j]=='#') else 0)
            st[i][j]=min(td,tr)
print(st[h-1][w-1])

Submission status: Accepted

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

for i in range(H):
    for j in range(W):
        for k in range(2):
            ni = i + dx[k]
            nj = j + dy[k]
            if ni >= H or nj >= W:
                continue
            add = 0
            # print(i, j, ni, nj)
            if s[i][j] == '.' and s[ni][nj] == '#': add += 1
            dp[ni][nj] = min(dp[ni][nj], dp[i][j] + add)

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

Submission status: Accepted

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

H,W = list(map(int,input().split()))
S = [ input().rstrip() for _ in range(H)] #マップの読み込み
dp = [[float('inf')]*W for _ in range(H)] #コスト
if S[0][0] == '#':#はじめが'#'なら1,else 0
    dp[0][0] = 1
else:
    dp[0][0] = 0

for i in range(H):
    for j in range(W):
        if i == 0 and j == 0:#スタート地点は無視
            continue
        a = float('inf')
        b = float('inf')
        # S[i][j]にくるには i-1 かj-1からくるしかない
        if i >= 1:
            a = dp[i-1][j] + ( S[i-1][j] =='.' and S[i][j] =='#') #i-1からくる
        
        if j >= j:
            b=  dp[i][j-1] + ( S[i][j-1] =='.' and S[i][j] =='#') #j-1からくる

        dp[i][j] = min(a,b)#a,bの小さいほうが最小コスト
print(dp[i][j])

Submission status: Accepted

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

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

for i in range(H):
    for j in range(W):
        if i == j == 0: 
            continue
        if i == 0:
            cost[i][j] = cost[i][j-1] + 1*(S[i][j] != S[i][j-1])
        elif j == 0:
            cost[i][j] = cost[i-1][j] + 1*(S[i][j] != S[i-1][j])
        else:
            cost[i][j] = min(cost[i][j-1] + 1*(S[i][j] != S[i][j-1]), cost[i-1][j] + 1*(S[i][j] != S[i-1][j]))

if S[0][0] == S[-1][-1] == '.':
    ans = cost[-1][-1]//2
elif S[0][0] != S[-1][-1]:
    ans = cost[-1][-1]//2 + 1
else:
    ans = cost[-1][-1]//2 + 1

print(ans)

Submission status: Accepted

Solution code:
h, w = map(int, input().split())
g = [[0] * w for _ in range(h)]#白が1、黒が０
for i in range(h):
    s = list(input())
    for j in range(w):
        if s[j] == '.':
            g[i][j] = 1
INF = 10**9
dp = [[INF] * w for _ in range(h)]
if g[0][0] == 0:
    dp[0][0] = 1
else:
    dp[0][0] = 0

for i in range(h):
    for j in range(w):
        for dx, dy in ((1, 0), (0, 1)):
            nx = j + dx
            ny = i + dy
            if ny >= h or nx >= w:
                continue
            add = 0
            if g[ny][nx] == 0 and g[i][j]  == 1:
                add = 1
            dp[ny][nx] = min(dp[ny][nx], dp[i][j] + add)
            
print(dp[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 collections import *
H,W=map(int,input().split())
S=[input() for i in range(H)]
INF=10**9
D=[[INF]*W for i in range(H)]
if S[0][0]=='.':
  D[0][0]=0
else:
  D[0][0]=1
Q=deque([(0,0)])
v=0
while len(Q):
  v=Q.popleft()
  if v[0]!=H-1:
    if S[v[0]][v[1]]=='.' and S[v[0]+1][v[1]]=='#':
      if D[v[0]][v[1]]+1<D[v[0]+1][v[1]]:
        D[v[0]+1][v[1]]=D[v[0]][v[1]]+1
        Q.append((v[0]+1,v[1]))
    else:
      if D[v[0]][v[1]]<D[v[0]+1][v[1]]:
        D[v[0]+1][v[1]]=D[v[0]][v[1]]
        Q.append((v[0]+1,v[1]))
  if v[1]!=W-1:
    if S[v[0]][v[1]]=='.' and S[v[0]][v[1]+1]=='#':
      if D[v[0]][v[1]]+1<D[v[0]][v[1]+1]:
        D[v[0]][v[1]+1]=D[v[0]][v[1]]+1
        Q.append((v[0],v[1]+1))
    else:
      if D[v[0]][v[1]]<D[v[0]][v[1]+1]:
        D[v[0]][v[1]+1]=D[v[0]][v[1]]
        Q.append((v[0],v[1]+1))
print(D[-1][-1])

Submission status: Accepted

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

dp = [[0 for x in range(w)] for y in range(h)]
if grid[0][0] == '#':
    dp[0][0] = 1
else:
    dp[0][0] = 0

for i in range(1, w):
    if grid[0][i] == '.':
        dp[0][i] = dp[0][i-1]
    else:
        if grid[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):
    if grid[i][0] == '.':
        dp[i][0] = dp[i-1][0]
    else:
        if grid[i-1][0] == '.':
            dp[i][0] = dp[i-1][0]+1
        else:
            dp[i][0] = dp[i-1][0]

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

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

Submission status: Accepted

Solution code:
#! /usr/bin/env python3

import sys
import numpy as np
int1 = lambda x: int(x) - 1
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
sys.setrecursionlimit(500000)


# adjacent_2
def adjacent_2(h, w, H, W):
    ret = []
    for (dh, dw) in [(0, 1), (1, 0)]:
        h_ = h + dh
        w_ = w + dw
        if (0 <= h_) & (h_ < H) & (0 <= w_) & (w_ < W):
            ret.append((h_, w_))
    return ret


H, W = map(int, readline().split())
A = [list(readline().decode().rstrip()) for _ in range(H)]
cnt = [[1000 for _ in range(W)] for _ in range(H)]

if A[0][0] == '.':
    cnt[0][0] = 0
else:
    cnt[0][0] = 1

for h in range(H):
    for w in range(W):
        acc = adjacent_2(h, w, H, W)
        for h_, w_ in acc:
            if (A[h][w] == ".") & (A[h_][w_] == "#"):
                cnt[h_][w_] = min(cnt[h][w] + 1, cnt[h_][w_])
            else:
                cnt[h_][w_] = min(cnt[h][w], cnt[h_][w_])

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

Submission status: Accepted

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

dp = [[h * w] * w for _ in range(h)]
dp[0][0] = int(s[0][0] == '#')
for i in range(h):
    for j in range(w):
        if i + 1 < h:
            dp[i + 1][j] = min(dp[i + 1][j],
                               dp[i][j] + int(s[i + 1][j] != s[i][j]))
        if j + 1 < w:
            dp[i][j + 1] = min(dp[i][j + 1],
                               dp[i][j] + int(s[i][j + 1] != s[i][j]))
print((dp[-1][-1] + 1) // 2)

Submission status: Accepted

Solution code:
import sys

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


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

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

    for h in range(H):
        for w in range(W + 1):
            if w == 0:
                if h != 0:
                    continue
                next_h, next_w = h, w + 1
                if grid[h][w] == "." and grid[next_h][next_w] == "#":
                    dp[next_h][next_w] = min(dp[next_h][next_w], dp[h][w] + 1)
                elif grid[h][w] == "." and grid[next_h][next_w] == "#":
                    dp[next_h][next_w] = min(dp[next_h][next_w], dp[h][w] + 1)
                else:
                    dp[next_h][next_w] = min(dp[next_h][next_w], dp[h][w])
            else:
                for dh, dw in [(1, 0), (0, 1)]:
                    next_h, next_w = h + dh, w + dw
                    if next_h < 0 or next_h >= H or next_w < 0 or next_w >= W + 1:
                        continue
                    if grid[h][w] == "." and grid[next_h][next_w] == "#":
                        dp[next_h][next_w] = min(dp[next_h][next_w], dp[h][w] + 1)
                    elif grid[h][w] == "." and grid[next_h][next_w] == "#":
                        dp[next_h][next_w] = min(dp[next_h][next_w], dp[h][w] + 1)
                    else:
                        dp[next_h][next_w] = min(dp[next_h][next_w], dp[h][w])
    print(dp[-1][-1])


if __name__ == '__main__':
    resolve()

Submission status: Accepted

Solution code:
from collections import deque
h, w = map(int, input().split())
S = [list(input()) for _ in range(h)]
DP = [[10000]*w for _ in range(h)]
DP[0][0] = 0 if S[0][0]=='.' else 1

directs = [[0,1], [1,0]]
for hi in range(h):
    for wi in range(w):
        for dh,dw in directs:
            if not (0<=hi+dh<h and 0<=wi+dw<w): continue
            if S[hi][wi]=='.' and S[hi+dh][wi+dw]=='#':
                DP[hi+dh][wi+dw] = min(DP[hi+dh][wi+dw], DP[hi][wi]+1)
            else:
                DP[hi+dh][wi+dw] = min(DP[hi+dh][wi+dw], DP[hi][wi])
print(DP[-1][-1])

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline
INF = 99999#1001001001
from collections import deque

def linput(ty=int, cvt=list):
	return cvt(map(ty,input().split()))

def pad(mxy, wall="#"):
	w = len(mxy[0])
	gp = wall*(w+2)
	re = [gp,]
	re_app = re.append
	for vx in mxy:
		re_app(wall+vx+wall)
	re_app(gp)
	return re

vD = [(0,1),(1,0)]
vQ = deque([])
vQ_app, vQ_popl = vQ.append, vQ.popleft

def main():
	H,W = linput()
	mM = [input().rstrip() for _ in [0,]*H]
	mM = pad(mM, "$")
	
	res = 0
	cnt = 0
	
	for sr in range(1,1+1):
		for sc in range(1,1+1):
			if mM[sr][sc]=="#":
				res += 1
			mV = [[INF,]*(W+2) for _ in [INF,]*(H+2)]
			mV[sr][sc] = res
			vQ_app((sr,sc))
			while vQ:
				r,c = vQ_popl()
				now_cost = mV[r][c]
				now_s = mM[r][c]
				for dr,dc in vD:
					nr,nc = r+dr, c+dc
					if mM[nr][nc]=="$":
						continue
					next = now_s=="."!=mM[nr][nc]
					new_cost = now_cost + next
					if new_cost < mV[nr][nc]:
						vQ_app((nr,nc))
						mV[nr][nc] = new_cost
		
				cnt += 1
				#print(res,cnt,X,Y,H)
				if cnt>999999: break
	
	#print(*mV,sep="\n")###
	res = mV[H][W]
	print(res)

if __name__ == "__main__":
	main()

Submission status: Accepted

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

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

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

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


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

for y in range(1, H):
	for x in range(W):
		if x == 0:
			dp[y][x] = dp[y-1][x] + (s[y-1][x] != s[y][x])
		else:
			dp[y][x] = min(dp[y-1][x]+(s[y-1][x] != s[y][x]), dp[y][x-1]+(s[y][x-1] != s[y][x]))

if s[H-1][W-1] == "#":
	dp[H-1][W-1] += 1


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

Submission status: Accepted

Solution code:
h,w = map(int, input().split())
grid = [list(input()) for _ in range(h)]
dpgrid = [[0]*w for _ in range(h)]
for i in range(h):
    for j in range(w):
        d = 1 if grid[i][j] == "#" else 0
        if (i == 0) & (j == 0):
            dpgrid[i][j] = d
        elif (i == 0):
            a = 1 if (grid[i][j-1] == ".") & (d == 1) else 0
            dpgrid[i][j] = a + dpgrid[i][j-1]
        elif (j == 0):
            b = 1 if (grid[i-1][j] == ".") & (d == 1) else 0
            dpgrid[i][j] = b + dpgrid[i-1][j]
        else:
            a = 1 if (grid[i][j-1] == ".") & (d == 1) else 0
            b = 1 if (grid[i-1][j] == ".") & (d == 1) else 0
            dpgrid[i][j] = min(a + dpgrid[i][j-1], b + dpgrid[i-1][j])
print(dpgrid[h-1][w-1])

Submission status: Accepted

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

h, w = MAP()
s = [input() for i in range(h)]
dp = [[inf]*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+1 < h:
            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+1 < w:
            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])