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:
# -*- coding: utf-8 -*-
import sys
import math
import os
import itertools
import string
import heapq
import _collections
from collections import Counter
from collections import defaultdict
from functools import lru_cache
import bisect
import re
import queue
from decimal import *


class Scanner():
    @staticmethod
    def int():
        return int(sys.stdin.readline().rstrip())

    @staticmethod
    def string():
        return sys.stdin.readline().rstrip()

    @staticmethod
    def map_int():
        return [int(x) for x in Scanner.string().split()]

    @staticmethod
    def string_list(n):
        return [input() for i in range(n)]

    @staticmethod
    def int_list_list(n):
        return [Scanner.map_int() for i in range(n)]

    @staticmethod
    def int_cols_list(n):
        return [int(input()) for i in range(n)]


class Math():
    @staticmethod
    def gcd(a, b):
        if b == 0:
            return a
        return Math.gcd(b, a % b)

    @staticmethod
    def lcm(a, b):
        return (a * b) // Math.gcd(a, b)

    @staticmethod
    def divisor(n):
        res = []
        i = 1
        for i in range(1, int(n ** 0.5) + 1):
            if n % i == 0:
                res.append(i)
                if i != n // i:
                    res.append(n // i)
        return res

    @staticmethod
    def round_up(a, b):
        return -(-a // b)

    @staticmethod
    def is_prime(n):
        if n < 2:
            return False
        if n == 2:
            return True
        if n % 2 == 0:
            return False
        d = int(n ** 0.5) + 1
        for i in range(3, d + 1, 2):
            if n % i == 0:
                return False
        return True


def pop_count(x):
    x = x - ((x >> 1) & 0x5555555555555555)
    x = (x & 0x3333333333333333) + ((x >> 2) & 0x3333333333333333)
    x = (x + (x >> 4)) & 0x0f0f0f0f0f0f0f0f
    x = x + (x >> 8)
    x = x + (x >> 16)
    x = x + (x >> 32)
    return x & 0x0000007f


MOD = int(1e09) + 7
INF = int(1e15)


def solve():
    H, W = Scanner.map_int()
    S = Scanner.string_list(H)
    dp = [[0 for _ in range(W)] for _ in range(H)]
    if S[0][0] == '#':
        dp[0][0] = 1
    for w in range(W - 1):
        dp[0][w + 1] = dp[0][w] + (S[0][w + 1] != S[0][w])
    for h in range(H - 1):
        dp[h + 1][0] = dp[h][0] + (S[h + 1][0] != S[h][0])
    for h in range(H - 1):
        for w in range(W - 1):
            s = dp[h][w + 1] + (S[h + 1][w + 1] != S[h][w + 1])
            t = dp[h + 1][w] + (S[h + 1][w + 1] != S[h + 1][w])
            dp[h + 1][w + 1] = min(s, t)

    print(Math.round_up(dp[H - 1][W - 1], 2))


def main():
    # sys.stdin = open("sample.txt")
    solve()


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
from collections import defaultdict

BIG = 10000

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

s = ['']*h
for i in range(h):
    s[i] = input()

cost = [[0]*w]*h

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

for r in range(h):
    for c in range(w):
        if (r, c) == (0, 0): continue
        x = BIG
        if s[r][c] == '.':
            if r > 0:
                x = min(x, cost[r-1][c])
            if c > 0:
                x = min(x, cost[r][c-1])
        else:  # black
            if r > 0:
                if s[r-1][c] == '#':
                    x = min(x, cost[r-1][c])
                else:
                    x = min(x, cost[r-1][c]+1)
            if c > 0:
                if s[r][c-1] == '#':
                    x = min(x, cost[r][c-1])
                else:
                    x = min(x, cost[r][c-1]+1)
        cost[r][c] = x

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

Submission status: Accepted

Solution code:
# coding: utf-8
# Your code here!
H,W=map(int,input().split())

meizu=[]
for _ in range(H):
    meizu.append(list(input()))

dp=[[10**9 for w in range(W)] for h in range(H)]
dp[0][0]=1 if meizu[0][0]=="#" else 0

for h in range(H):
    for w in range(W):
        if h!=H-1:
            dp[h+1][w]=min(dp[h+1][w],dp[h][w]+1 if meizu[h+1][w]=="#" and meizu[h][w]=="." else dp[h][w])
        if w!=W-1:
            dp[h][w+1]=min(dp[h][w+1],dp[h][w]+1 if meizu[h][w+1]=="#" and meizu[h][w]=="." else dp[h][w])
    
print(dp[-1][-1])

Submission status: Accepted

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

INF = H + W

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

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

for i in range(H):
    for j in range(W):
        if i - 1 >= 0:
            if S[i][j] == '#' and S[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 j - 1 >= 0:
            if S[i][j] == '#' and S[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[H-1][W-1])

Submission status: Accepted

Solution code:
# A - Range Flip Find Route
h,w=map(int,input().split())
s=[input() for i in range(h)]
inf=10**18
dp=[[inf]*(w+1) for i in range(h+1)]
if s[0][0]=="#":
  dp[0][0]=1
else:
  dp[0][0]=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 s[ni][nj]=="#" and s[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:
def check(i, j):
    if s[i][j] == '.':
        return 1
    else:
        return 0
H, W = map(int, input().split())
s = [input() for i in range(H)]
dp = [[0]*W for i in range(H)]
dp[0][0] = int(s[0][0] == '#')
for i in range(H):
    for j in range(W):
        if s[i][j] == '.':
            if i > 0 and j > 0:
                dp[i][j] = min(dp[i-1][j], dp[i][j-1])
            elif i > 0:
                dp[i][j] = dp[i-1][j]
            elif j > 0:
                dp[i][j] = dp[i][j-1]
        else:
            if i > 0 and j > 0:
                dp[i][j] = min(dp[i-1][j]+check(i-1, j), dp[i][j-1]+check(i, j-1))
            elif i > 0:
                dp[i][j] = dp[i-1][j]+check(i-1, j)
            elif j > 0:
                dp[i][j] = dp[i][j-1]+check(i, j-1)
print(dp[H-1][W-1])

Submission status: Accepted

Solution code:
H, W = map(int, input().split())
arr = [input().rstrip() for h in range(H)]
ans = [[0] * W for _ in range(H)]
for h, row in enumerate(arr):
    for w, val in enumerate(row):
        if h == 0 and w == 0:
            if arr[h][w] == "#":
                ans[h][w] = 1
            continue
        nv = 1e+9
        if h > 0:
            nv = ans[h-1][w]
            if arr[h-1][w] == "." and val == "#":
                nv += 1
        if w > 0:
            tmp = ans[h][w-1]
            if arr[h][w-1] == "." and val == "#":
                tmp += 1
            nv = min(nv, tmp)
        ans[h][w] = nv
print(ans[-1][-1])

Submission status: Accepted

Solution code:
h,w=map(int,input().split())
m=[[1 if c=="#" else 0 for c in input()] for _ in range(h)]

n=[i[:] for i in m]
for i in range(1,h):
  n[i][0]=n[i-1][0]+int(m[i-1][0]-n[i][0]==-1)
for j in range(1,w):
  n[0][j]=n[0][j-1]+int(m[0][j-1]-n[0][j]==-1)
for i in range(1,h):
  for j in range(1,w):
    n[i][j]=min(n[i-1][j]+int(m[i-1][j]-n[i][j]==-1),n[i][j-1]+int(m[i][j-1]-n[i][j]==-1))
print(n[-1][-1])

Submission status: Accepted

Solution code:
import queue

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

cost = [[99999999 for j in range(w)] for i in range(h)]

cost[0][0] = 0
xq = queue.Queue()
yq = queue.Queue()
xq.put(0)
yq.put(0)

while xq.qsize() > 0:
    x = xq.get()
    y = yq.get()

    if y + 1 < h:
        tmp = cost[y][x] + (1 if s[y][x] == '.' and s[y + 1][x] == '#' else 0)
        if tmp < cost[y + 1][x]:
            cost[y + 1][x] = tmp
            xq.put(x)
            yq.put(y + 1)
    if x + 1 < w:
        tmp = cost[y][x] + (1 if s[y][x] == '.' and s[y][x + 1] == '#' else 0)
        if tmp < cost[y][x + 1]:
            cost[y][x + 1] = tmp
            xq.put(x + 1)
            yq.put(y)

print((0 if s[0][0] == '.' else 1) + cost[h - 1][w - 1])

Submission status: Accepted

Solution code:
h, w = map(int, input().split())
S = [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:
      if S[0][0] == "#":
        dp[0][0] = 1
      continue
    if i:
      u = dp[i-1][j]
      if S[i-1][j] == "." and S[i][j] == "#":
        u += 1
    else:
      u = float("inf")
    if j:
      v = dp[i][j-1]
      if S[i][j-1] == "." and S[i][j] == "#":
        v += 1
    else:
      v = float("inf")
    dp[i][j] = min(u, v)
print(dp[-1][-1])

Submission status: Accepted

Solution code:
def solve():
    H, W = map(int, input().split())
    l = [list(input()) for _ in range(H)]
    q = [(0, 0)]
    sc = [[H*W]*W for _ in range(H)]
    sc[0][0] = 0 if l[0][0]=="." else 1

    while q:
        y, x = q.pop()
        for y1, x1 in [(y+1, x), (y, x+1)]:
            if not (0<=x1<W and 0<=y1<H):continue
            if l[y][x]=="#":
                if sc[y1][x1] > sc[y][x]:
                    sc[y1][x1] = sc[y][x]
                    q.append((y1, x1))
            else:
                v = sc[y][x]+1 if l[y1][x1]=="#" else sc[y][x]
                if sc[y1][x1] > v:
                    sc[y1][x1] = v
                    q.append((y1, x1))

    print(sc[-1][-1])


if __name__ == "__main__":
    solve()

Submission status: Accepted

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

cnts = [[0 for _ in range(W)] for _ in range(H)]
if S[0][0] == "#":
    cnts[0][0]  = 1
for h in range(H):
    for w in range(W):
        if h == 0 and w == 0:
            continue

        c1, c2 = float('inf'), float('inf')
        if 0 <= h - 1:
            c1 = cnts[h - 1][w]
            if S[h][w] == "#" and S[h - 1][w] == ".":
                c1 += 1

        if 0 <= w - 1:
            c2 = cnts[h][w - 1]
            if S[h][w] == "#" and S[h][w - 1] == ".":
                c2 += 1

        cnts[h][w] = min(c1, c2)
print(cnts[H-1][W-1])

Submission status: Accepted

Solution code:
import sys
input = lambda: sys.stdin.readline().rstrip()
input_nums = lambda: list(map(int, input().split()))

def main():
    INF = 10**9
    H, W = input_nums()
    ss = [input() for _ in range(H)]
    dp = [[0]*W for _ in range(H)]
    if ss[0][0] == '#': dp[0][0] = 1
    for h in range(H):
        for w in range(W):
            if (h, w) == (0, 0): continue
            u = l = INF
            if h-1>=0:
                u = dp[h-1][w]
                if ss[h][w] == '#' and ss[h-1][w] == '.': u += 1
            if w-1>=0:
                l = dp[h][w-1]
                if ss[h][w] == '#' and ss[h][w-1] == '.': l += 1
            dp[h][w] = min(u, l)
    print(dp[H-1][W-1])

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
h,w=map(int,input().split())
G=[["#"]*(w+2) for i in range(h+2)]
for i in range(1,h+1):
  G[i]=["#"]+list(input())+["#"]
for i in range(h+2):
  for j in range(w+2):
    if G[i][j]==".":
      G[i][j]=0
    else:
      G[i][j]=1
dp=[[1000]*(w+2) for i in range(h+2)]
dp[1][1]=0
for i in range(1,h+1):
  for j in range(1,w+1):
    if i==1 and j==1:
      continue
    dp[i][j]=min(dp[i-1][j]+(G[i-1][j]+G[i][j])%2,dp[i][j-1]+(G[i][j-1]+G[i][j])%2)
ans=dp[h][w]
if G[1][1]==1:
  ans=ans+1
print((ans+1)//2)

Submission status: Accepted

Solution code:
inputs = [s.strip() for s in open(0).readlines()]
import numpy as np
class Grid():
    def __init__(self, grid, w=0, h=0, function=lambda x: x):
        self.w = w = w if w else len(grid[0])
        self.h = h = h if h else len(grid)
        dtype = type(function(grid[0][0]))
        self.grid = np.empty((h, w), dtype=dtype)
        for i, row in zip(range(h), grid):
            for j, val in zip(range(w), row):
                self.grid[i][j] = function(val)
    
    def is_valid_x(self, x):
        return 0 <= x < self.w
    def is_valid_y(self, y):
        return 0 <= y < self.h
    def is_valid_xy(self, x, y):
        return self.is_valid_x(x) and self.is_valid_y(y) 
    
    def __iter__(self):
        return iter(self.grid)
    def __repr__(self):
        return '\n'.join([' '.join(map(str, row)) for row in self.grid])
    def __getitem__(self, x):
        return self.grid[x]
    def __setitem__(self, x, val):
        self.grid[x] = val

h, w = map(int, inputs[0].split())
grid = Grid(inputs[1:]).grid

h, w = map(int, inputs[0].split())
grid = Grid(inputs[1:])

dp = Grid(np.zeros((h, w), np.int))
dp[0, 0] = int(grid[0, 0] == '#')
for i in range(1, w):
    dp[0, i] = dp[0, i-1] + int(grid[0, i-1] + grid[0, i] == '.#')
for i in range(1, h):
    dp[i, 0] = dp[i-1, 0] + int(grid[i-1, 0] + grid[i, 0] == '.#')
x = y = 1
while not (x == w-1 and y == h-1):
    for i in range(x, w):
        dp[y, i] = min(dp[y, i-1] + int(grid[y, i-1] + grid[y, i] == '.#'),
                       dp[y-1, i] + int(grid[y-1, i] + grid[y, i] == '.#'))
    for i in range(y+1, h):
        dp[i, x] = min(dp[i-1, x] + int(grid[i-1, x] + grid[i, x] == '.#'),
                       dp[i, x-1] + int(grid[i, x-1] + grid[i, x] == '.#'))
    x, y = min(x+1, w-1), min(y+1, h-1)
print(min(dp[y-1, x] + int(grid[y-1, x] + grid[y, x] == '.#'), 
          dp[y, x-1] + int(grid[y, x-1] + grid[y, x] == '.#')))

Submission status: Accepted

Solution code:
inputs = [s.strip() for s in open(0).readlines()]
import numpy as np
class Grid():
    def __init__(self, grid, w=0, h=0, function=lambda x: x):
        self.w = w = w if w else len(grid[0])
        self.h = h = h if h else len(grid)
        dtype = type(function(grid[0][0]))
        self.grid = np.empty((h, w), dtype=dtype)
        for i, row in zip(range(h), grid):
            for j, val in zip(range(w), row):
                self.grid[i][j] = function(val)
    
    def is_valid_x(self, x):
        return 0 <= x < self.w
    def is_valid_y(self, y):
        return 0 <= y < self.h
    def is_valid_xy(self, x, y):
        return self.is_valid_x(x) and self.is_valid_y(y) 
    
    def __iter__(self):
        return iter(self.grid)
    def __repr__(self):
        return '\n'.join([' '.join(map(str, row)) for row in self.grid])
    def __getitem__(self, x):
        return self.grid[x]
    def __setitem__(self, x, val):
        self.grid[x] = val

h, w = map(int, inputs[0].split())
grid = Grid(inputs[1:]).grid

dp = np.zeros((h, w), np.int)
if grid[0][0] == '#':
    dp[0, 0] = 1
for i in range(1, w):
    dp[0, i] = dp[0, i-1] + int(grid[0, i-1] + grid[0, i] == '.#')
for i in range(1, h):
    dp[i, 0] = dp[i-1, 0] + int(grid[i-1, 0] + grid[i, 0] == '.#')
x = y = 1
while not (x == w-1 and y == h-1):
    for i in range(x, w):
        dp[y, i] = min(dp[y, i-1] + int(grid[y, i-1] + grid[y, i] == '.#'),
                       dp[y-1, i] + int(grid[y-1, i] + grid[y, i] == '.#'))
    for i in range(y+1, h):
        dp[i, x] = min(dp[i-1, x] + int(grid[i-1, x] + grid[i, x] == '.#'),
                       dp[i, x-1] + int(grid[i, x-1] + grid[i, x] == '.#'))
    x, y = min(x+1, w-1), min(y+1, h-1)
print(min(dp[y-1, x] + int(grid[y-1, x] + grid[y, x] == '.#'), 
          dp[y, x-1] + int(grid[y, x-1] + grid[y, x] == '.#')))

Submission status: Accepted

Solution code:
import sys
import numpy as np
H, W = map(int, input().split())
I = np.array([list(map(str, input())) for _ in range(H)])
grid = np.zeros([H,W], np.int16)
grid[np.where(I=='#')] = 1
inf = np.inf
dp = np.full([H,W], inf)
if grid[0,0] == 1:
    dp[0,0] = 1
else:
    dp[0,0] = 0

for i in range(H):
    for j in range(W):
        if i + 1 < H:
            if grid[i,j] == grid[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 grid[i,j] == grid[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)
if grid[-1,-1] == 1:
    dp[-1,-1,] += 1
ans = dp[-1,-1]//2
print(int(ans))

Submission status: Accepted

Solution code:
'''input
5 5
.#.#.
#.#.#
.#.#.
#.#.#
.#.#.
'''

import sys
import math
from collections import Counter

debug = 0
readln = sys.stdin.readline
#sys.setrecursionlimit(1000000)

def write(s):
    sys.stdout.write(str(s))

def writeln(s):
    sys.stdout.write(str(s))
    sys.stdout.write('\n')

def readint():
    return int(readln().strip())

def readints():
    return map(int, readln().split())

def readstr():
    return readln().strip()

def readstrs():
    return readln().split()

def dbg(*args):
    if debug: print(' '.join(map(str, args)))


h,w = readints()
mat = []
dp = [[0] * w for _ in xrange(h)]
for _ in xrange(h):
    mat.append(readstr())

def getdp(r, c, cur):
    if r < 0 and c == 0 or c < 0 and r == 0:
        old = 0
        oldc = '.'
    elif r < 0 or c < 0:
        return 2**31
    else:
        old = dp[r][c]
        oldc = mat[r][c]

    if cur == '#' and oldc == '.':
        return old + 1
    else:
        return old

def solve(h, w):
    global dp
    for r in xrange(h):
        for c in xrange(w):
            cur = mat[r][c]
            dp[r][c] = min(getdp(r-1, c, cur), getdp(r, c-1, cur))
    dbg(dp)
    return dp[h-1][w-1]

print solve(h, w)

Submission status: Accepted

Solution code:
import sys


INF = sys.maxsize
H, W = map(int, input().split())
m = []

for i in range(H):
  m.append([x for x in input()])

dp = [[INF] * W for _ in range(H)]
dp[0][0] = 0 if m[0][0] == '.' else 1

for i in range(H):
  for j in range(W):    
    for di, dj in [(0, 1), (1, 0)]:
      ni = i + di
      nj = j + dj
      if ni < H and nj < W:
        dp[ni][nj] = min(
          dp[ni][nj],
          dp[i][j] + 1 if m[i][j] == '.' and m[ni][nj] == '#' else dp[i][j],
        )

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

Submission status: Accepted

Solution code:
import itertools
import os
import sys

if os.getenv("LOCAL"):
    sys.stdin = open("_in.txt", "r")

sys.setrecursionlimit(10 ** 9)
INF = float("inf")
IINF = 10 ** 18
MOD = 10 ** 9 + 7
# MOD = 998244353


H, W = list(map(int, sys.stdin.buffer.readline().split()))
S = [sys.stdin.buffer.readline().decode().rstrip() for _ in range(H)]

# 白から黒に来るときだけ+1すればOK
dp = [[INF] * W for _ in range(H)]
dp[0][0] = 1 if S[0][0] == '#' else 0
for h, w in itertools.product(range(H), range(W)):
    for ph, pw in [(h - 1, w), (h, w - 1)]:
        if 0 <= ph < H and 0 <= pw < W:
            d = int(S[ph][pw] == '.' and S[h][w] == '#')
            dp[h][w] = min(dp[h][w], dp[ph][pw] + d)
print(dp[-1][-1])

Submission status: Accepted

Solution code:
H, W = map(int, input().split())
board = [list(input()) for _ in range(H)]
INF = float('inf')
dp = [[INF] * W for _ in range(H)]
if board[0][0] == '.':
    dp[0][0] = 0
else:
    dp[0][0] = 1
for i in range(H):
    for j in range(W):
        if i == 0 and j == 0:
            continue
        if board[i][j] == board[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)
        if board[i][j] == board[i][j-1]:
            dp[i][j] = min(dp[i][j], dp[i][j-1])
        else:
            dp[i][j] = min(dp[i][j], dp[i][j-1] + 1)
if board[H-1][W-1] == '#':
    dp[H-1][W-1] += 1
print(dp[H-1][W-1] // 2)

Submission status: Accepted

Solution code:
import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
sys.setrecursionlimit(10 ** 7)

from math import ceil

h, w = map(int, readline().split())
s = [input() for i in range(h)]
dp = [[float('inf')] * w for j in range(h)]
if s[0][0] == '#':
    dp[0][0] = 1
else:
    dp[0][0] = 0
for i in range(h):
    for j in range(w):
        if w - 1 != j:
            cnt = 0
            if s[i][j + 1] != s[i][j]:
                cnt += 1
            dp[i][j + 1] = min(dp[i][j + 1], dp[i][j] + cnt)
        if h - 1 != i:
            cnt = 0
            if s[i + 1][j] != s[i][j]:
                cnt += 1
            dp[i + 1][j] = min(dp[i + 1][j], dp[i][j] + cnt)
print(ceil(dp[-1][-1] / 2))

Submission status: Accepted

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

INF = 10 ** 18
dp = [[INF for _ in range(W)] for _ in range(H)]

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

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

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

Submission status: Accepted

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

INF = 10 ** 18
dp = [[INF for _ in range(W)] for _ in range(H)]

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

for j in range(1, W):
    if S[0][j] == "." or (S[0][j] == "#" and S[0][j - 1] == "#"):
        dp[0][j] = dp[0][j - 1]
    else:
        dp[0][j] = dp[0][j - 1] + 1

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

    
    for j in range(1, W):
        if S[i][j] == ".":
            dp[i][j] = min(dp[i - 1][j], dp[i][j - 1])
        else:
            dp[i][j] = min(dp[i - 1][j] if S[i - 1][j] == "#" else dp[i - 1][j] + 1,
                            dp[i][j - 1] if S[i][j - 1] == "#" else dp[i][j - 1] + 1)

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

Submission status: Accepted

Solution code:
def main():
    H, W = (int(i) for i in input().split())
    c = [input() for i in range(H)]
    dp = [[10**3]*W for _ in range(H)]
    if c[0][0] == "#":
        dp[0][0] = 1
    else:
        dp[0][0] = 0
    for h in range(H):
        for w in range(W):
            if c[h][w] == ".":
                if w < W-1 and c[h][w+1] == ".":
                    dp[h][w+1] = min(dp[h][w+1], dp[h][w])
                elif w < W-1 and c[h][w+1] == "#":
                    dp[h][w+1] = min(dp[h][w+1], dp[h][w] + 1)
                if h < H-1 and c[h+1][w] == ".":
                    dp[h+1][w] = min(dp[h+1][w], dp[h][w])
                elif h < H-1 and c[h+1][w] == "#":
                    dp[h+1][w] = min(dp[h+1][w], dp[h][w] + 1)
            else:
                if w < W-1:
                    dp[h][w+1] = min(dp[h][w+1], dp[h][w])
                if h < H-1:
                    dp[h+1][w] = min(dp[h+1][w], dp[h][w])
    print(dp[H-1][W-1])
    # print(*dp, sep="\n")


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(10**7)

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

dp = [[10**18 for i in range(w)] for j in range(h)]

dp[0][0] = 0

for i in range(w-1):
    if sij[0][i+1] != sij[0][i]:
        dp[0][i+1] = dp[0][i]+1
    else:
        dp[0][i+1] = dp[0][i]
        
for i in range(h-1):
    if sij[i+1][0] != sij[i][0]:
        dp[i+1][0] = dp[i][0]+1
    else:
        dp[i+1][0] = dp[i][0]

for i in range(1,h):
    for j in range(1,w):
        #print(i,j)
        if sij[i-1][j] != sij[i][j]:
            sita = dp[i-1][j]+1
        else:
            sita = dp[i-1][j]
        if sij[i][j-1] != sij[i][j]:
            yoko = dp[i][j-1]+1
        else:
            yoko = dp[i][j-1]
        #print(i,j,sita,yoko)
        dp[i][j] = min(sita,yoko)

add = 0
#print(dp)

if sij[0][0] == '#':
    add = 1
"""
if dp[h-1][w-1] == 1:
    print(1)
else:
    print(dp[h-1][w-1]//2+add)
""" 
if dp[h-1][w-1] % 2 == 1:
    print(dp[h-1][w-1]//2+1)
else:
    print(dp[h-1][w-1]//2+add)

Submission status: Accepted

Solution code:
import math
h,w = map(int,input().split())
g = [list(input()) for _ in range(h)]
dp = [[float('inf')]*w for _ in range(h)]
if g[0][0] == '.':
    dp[0][0] = 0
else:
    dp[0][0] = 1

for i in range(h):
    for j in range(w):
        for di, dj in zip((0,1), (1, 0)):
            ni, nj = i+di, j+dj
            if ni>=h or nj>=w:
                continue
            if g[ni][nj]!=g[i][j]:
                dp[ni][nj] = min(dp[ni][nj], dp[i][j]+1)
            else:
                dp[ni][nj] = min(dp[ni][nj], dp[i][j])
print(math.ceil(dp[h-1][w-1]/2))

Submission status: Accepted

Solution code:
def main():
    height, width = map(int, input().split())
    grid = [list(input()) for _ in range(height)]
    dp = [[float("inf") for _ in range(width)] for _ in range(height)]
    if grid[0][0] == "#":
        dp[0][0] = 1
    else:
        dp[0][0] = 0
    delta = [[0, 1], [1, 0]]
    for i in range(height):
        for j in range(width):
            for dx, dy in delta:
                if i + dy >= height or j + dx >= width:
                    continue
                else:
                    add = 0
                    if grid[i][j] == "." and grid[i + dy][j + dx] == "#":
                        add = 1
                    dp[i + dy][j + dx] = min(dp[i + dy][j + dx], dp[i][j] + add)
    print(dp[-1][-1])


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import numpy as np

H, W = map(int, input().split())
masu = [input() for i in range(H)]
#temp = [list(input().replace("#","0").replace(".","1")) for i in range(H)]
#masu = [[int(temp[i][j]) for j in range(W)] for i in range(H)]

#dp = np.zeros((H, W))
dp = [[0]*W for i in range(H)]
if masu[0][0] == "#":
    dp[0][0] = 1

for i in range(0,H):
    for j in range(0,W):
        if i == 0:
            a = 100000
        else:
            if masu[i][j] == "#" and masu[i-1][j] == ".":
                a = dp[i-1][j] + 1
            else:
                a = dp[i-1][j]
        if j == 0:
            b = 100000
        else:
            if masu[i][j] == "#" and masu[i][j-1] == ".":
                b = dp[i][j-1] + 1
            else:
                b = dp[i][j-1]
        if a != 100000 or b != 100000:
            dp[i][j] = min([a, b])
print(int(dp[H-1][W-1]))

Submission status: Accepted

Solution code:
#import numpy as np

H, W = map(int, input().split())
masu = [input() for i in range(H)]
#temp = [list(input().replace("#","0").replace(".","1")) for i in range(H)]
#masu = [[int(temp[i][j]) for j in range(W)] for i in range(H)]

#dp = np.zeros((H, W))
dp = [[0]*W for i in range(H)]
if masu[0][0] == "#":
    dp[0][0] = 1

for i in range(0,H):
    for j in range(0,W):
        if i == 0:
            a = 100000
        else:
            if masu[i][j] == "#" and masu[i-1][j] == ".":
                a = dp[i-1][j] + 1
            else:
                a = dp[i-1][j]
        if j == 0:
            b = 100000
        else:
            if masu[i][j] == "#" and masu[i][j-1] == ".":
                b = dp[i][j-1] + 1
            else:
                b = dp[i][j-1]
        if a != 100000 or b != 100000:
            dp[i][j] = min([a, b])
print(int(dp[H-1][W-1]))

Submission status: Accepted

Solution code:
import numpy as np

H, W = map(int, input().split())
masu = [input() for i in range(H)]
#temp = [list(input().replace("#","0").replace(".","1")) for i in range(H)]
#masu = [[int(temp[i][j]) for j in range(W)] for i in range(H)]

dp = np.zeros((H, W))
if masu[0][0] == "#":
    dp[0][0] = 1

for i in range(0,H):
    for j in range(0,W):
        if i == 0:
            a = 100000
        else:
            if masu[i][j] == "#" and masu[i-1][j] == ".":
                a = dp[i-1][j] + 1
            else:
                a = dp[i-1][j]
        if j == 0:
            b = 100000
        else:
            if masu[i][j] == "#" and masu[i][j-1] == ".":
                b = dp[i][j-1] + 1
            else:
                b = dp[i][j-1]
        if a != 100000 or b != 100000:
            dp[i][j] = min([a, b])
print(int(dp[H-1][W-1]))

Submission status: Accepted

Solution code:
import numpy as np

H, W = map(int, input().split())
temp = [list(input().replace("#","0").replace(".","1")) for i in range(H)]
masu = [[int(temp[i][j]) for j in range(W)] for i in range(H)]

dp = np.zeros((H, W))
if masu[0][0] == 0:
    dp[0][0] = 1

for i in range(0,H):
    for j in range(0,W):
        if i == 0:
            a = 100000
        else:
            if masu[i][j] == 0 and masu[i-1][j] == 1:
                a = dp[i-1][j] + 1
            else:
                a = dp[i-1][j]
        if j == 0:
            b = 100000
        else:
            if masu[i][j] == 0 and masu[i][j-1] == 1:
                b = dp[i][j-1] + 1
            else:
                b = dp[i][j-1]
        if a != 100000 or b != 100000:
            dp[i][j] = min([a, b])
print(int(dp[H-1][W-1]))

Submission status: Accepted

Solution code:
H,W = (int(x) for x in input().split())
lines = [input() for i in range(H)]
dp = [[0] * W for _ in range(H)]
if lines[0][0] == "#":
    dp[0][0] = 1
q = r = dp[0][0]
for i in range(H):
    for j in range(W):
        if i == j == 0: continue
        if j > 0:
            q = dp[i][j-1]
            if lines[i][j] == "#" and lines[i][j-1] == ".":
                q = dp[i][j-1] + 1
        if i > 0:
            r = dp[i-1][j]
            if lines[i][j] == "#" and lines[i-1][j] == ".":
                r = dp[i-1][j] + 1
        if j == 0: 
            dp[i][j] = r
        elif i == 0:
            dp[i][j] = q
        else:
            dp[i][j] = min(q,r)
print(dp[H-1][W-1])

Submission status: Accepted

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

dist = [[10**7] * W for _ in range(H)]
dist[0][0] = 0

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

if S[0][0] == '#':
    dist[H-1][W-1] += 1
print(dist[H-1][W-1])