Problem:


Score : 400 points

Problem Statement

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

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

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

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

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

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

Constraints

2 \leq H, W \leq 100

Input

Input is given from Standard Input in the following format:

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

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

Output

Print the minimum number of operations needed.

Sample Input 1

3 3
.##
.#.
##.

Sample Output 1

1

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

Sample Input 2

2 2
#.
.#

Sample Output 2

2

Sample Input 3

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

Sample Output 3

0

No operation may be needed.

Sample Input 4

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

Sample Output 4

4



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


Sample output:
1

Submission status: Accepted

Solution code:
#!/usr/bin/env python
from __future__ import division, print_function

import os
import sys
from io import BytesIO, IOBase

if sys.version_info[0] < 3:
    from __builtin__ import xrange as range
    from future_builtins import ascii, filter, hex, map, oct, zip


def main():
    h, w = [int(s) for s in input().strip().split()]
    grid = [input().strip() for _ in range(h)]
    dp = [[0] * w for _ in range(h)]
    dp[0][0] = 1 if grid[0][0] == "#" else 0
    for i in range(1, h):
        dp[i][0] = dp[i - 1][0] + (grid[i - 1][0] == "." and grid[i][0] == "#")
    for j in range(1, w):
        dp[0][j] = dp[0][j - 1] + (grid[0][j - 1] == "." and grid[0][j] == "#")
    for i in range(1, h):
        for j in range(1, w):
            dp[i][j] = min(
                dp[i - 1][j] + (grid[i - 1][j] == "." and grid[i][j] == "#"),
                dp[i][j - 1] + (grid[i][j - 1] == "." and grid[i][j] == "#")
            )
    result = dp[-1][-1]
    print(result)


# region fastio

BUFSIZE = 8192


class FastIO(IOBase):
    newlines = 0

    def __init__(self, file):
        self._fd = file.fileno()
        self.buffer = BytesIO()
        self.writable = "x" in file.mode or "r" not in file.mode
        self.write = self.buffer.write if self.writable else None

    def read(self):
        while True:
            b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
            if not b:
                break
            ptr = self.buffer.tell()
            self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr)
        self.newlines = 0
        return self.buffer.read()

    def readline(self):
        while self.newlines == 0:
            b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
            self.newlines = b.count(b"\n") + (not b)
            ptr = self.buffer.tell()
            self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr)
        self.newlines -= 1
        return self.buffer.readline()

    def flush(self):
        if self.writable:
            os.write(self._fd, self.buffer.getvalue())
            self.buffer.truncate(0), self.buffer.seek(0)


class IOWrapper(IOBase):
    def __init__(self, file):
        self.buffer = FastIO(file)
        self.flush = self.buffer.flush
        self.writable = self.buffer.writable
        self.write = lambda s: self.buffer.write(s.encode("ascii"))
        self.read = lambda: self.buffer.read().decode("ascii")
        self.readline = lambda: self.buffer.readline().decode("ascii")


def print(*args, **kwargs):
    """Prints the values to a stream, or to sys.stdout by default."""
    sep, file = kwargs.pop("sep", " "), kwargs.pop("file", sys.stdout)
    at_start = True
    for x in args:
        if not at_start:
            file.write(sep)
        file.write(str(x))
        at_start = False
    file.write(kwargs.pop("end", "\n"))
    if kwargs.pop("flush", False):
        file.flush()


if sys.version_info[0] < 3:
    sys.stdin, sys.stdout = FastIO(sys.stdin), FastIO(sys.stdout)
else:
    sys.stdin, sys.stdout = IOWrapper(sys.stdin), IOWrapper(sys.stdout)

input = lambda: sys.stdin.readline().rstrip("\r\n")

# endregion

if __name__ == "__main__":
    main()

Submission status: Accepted

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


def F(h, w, f):
    if f == -1:
        if S[h][w] == ".":
            return False
        else:
            return True
    if S[h][w] == "#":
        return False
    else:
        return True


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

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

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

Submission status: Accepted

Solution code:
import sys
def input(): return sys.stdin.readline().rstrip()
sys.setrecursionlimit(10 ** 7)

H, W = map(int, input().split())
S = [input() for _ in range(H)]
# print(S)
INF = 1001001001

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

for r in range(H):
    for c in range(W):
        if r:
            if S[r][c] == '#' and S[r-1][c] == '.':
                dp[r][c] = min(dp[r][c], dp[r-1][c]+1)
            else:
                dp[r][c] = min(dp[r][c], dp[r-1][c])
        if c:
            if S[r][c] == '#' and S[r][c-1] == '.':
                dp[r][c] = min(dp[r][c], dp[r][c-1]+1)
            else:
                dp[r][c] = min(dp[r][c], dp[r][c-1])

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

Submission status: Accepted

Solution code:
H,W = map(int,input().split())
place = []
for i in range(H):
    S = input()
    place.append(S)
ans_list = []
for i in range(H):
    Z = [0] * W
    ans_list.append(Z)
for i in range(H):
    if i == 0:
        count = 0
        for j in range(W):
            if place[0][j] == "#":
                if j == 0:
                    count += 1
                else:
                    if place[0][j-1] != "#":
                        count += 1
            ans_list[0][j] = count
    else:
        for j in range(W):
            chk = 0
            if j == 0 :
                count = ans_list[i-1][j]
            else:
                count = ans_list[i][j-1]
            if place[i][j] == "#":
                if j == 0:
                    if place[i-1][j] != "#":
                        count += 1
                else:
                    if place[i][j-1] != "#":
                        count += 1
            if place[i][j] == "#":
                if place[i][j] != place[i-1][j]:
                    chk += 1
            ans_list[i][j] = min(count,ans_list[i-1][j]+chk)
print(ans_list[H-1][W-1])

Submission status: Accepted

Solution code:
import sys

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

from collections import deque

def bfs(sy, sx, gy, gx):
    INF = 10 ** 5
    d = [[INF] * W for _ in range(H)]
    dy = [0, 1]
    dx = [1, 0]
    que = deque()
    que.append((sy, sx))
    d[sy][sx] = 0
    if grid[sy][sx] == '#':
        d[sy][sx] = 1
    while que:
        y, x = que.popleft()
        if y == gy and x == gx:
            break
        for i in range(2):
            ny = y + dy[i]
            nx = x + dx[i]
            if ny >= H or nx >= W:
                continue
            if grid[y][x] == grid[ny][nx]:
                if d[ny][nx] > d[y][x]:
                    d[ny][nx] = d[y][x]
                    que.append((ny, nx))
            elif grid[y][x] == '#' and grid[ny][nx] == '.':
                if d[ny][nx] > d[y][x]:
                    d[ny][nx] = d[y][x]
                    que.append((ny, nx))
            else:
                if d[ny][nx] > d[y][x] + 1:
                    d[ny][nx] = d[y][x] + 1
                    que.append((ny, nx))
    return d[gy][gx]

H, W = lr()
grid = [list(sr()) for _ in range(H)]
answer = bfs(0, 0, H-1, W-1)
print(answer)

Submission status: Accepted

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

INF = 10000000000

grid = [["." for _ in range(W+1)]]

for _ in range(H):
    in_list = list("." + input())
    grid.append(in_list)

# dp[i][j] = x x: これまでに何ブロックあったか
dp = [[INF for _ in range(W+1)] for _ in range(H+1)]
dp[1][0] = 0
dp[0][1] = 0


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

for j in range(1,W+1):
    for i in range(1,H+1):
        if grid[i][j] == ".": # 白の場合
            dp[i][j] = min(dp[i-1][j],dp[i][j-1])
        else: # 黒の場合
            # route_top
            if grid[i-1][j] == "#": # 上も黒ならそのまあ
                route_top = dp[i-1][j]
            else:
                route_top = dp[i-1][j] + 1

            # route_left
            if grid[i][j-1] == "#": # 上も黒ならそのまあ
                route_left = dp[i][j-1]
            else:
                route_left = dp[i][j-1] + 1
            
            dp[i][j] = min(route_top,route_left)
print(dp[-1][-1])

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(100000)

h,w=map(int,input().split())
INF=10**10
s_org=[list(input()) for _ in range(h)]
s=[[0]*w for _ in range(h)]
for i in range(h):
  for j in range(w):
    if s_org[i][j]=="#":
      s[i][j]=1
dp=[[-1]*w for _ in range(h)]
dp[0][0]=s[0][0]
def func(i,j):
  if i<0 or j<0: return INF
  if dp[i][j]!=-1:return dp[i][j]
  a=func(i,j-1)+s[i][j]
  b=func(i-1,j)+s[i][j]
  if s[i][j]==1 and s[i][j-1]==1:
    a-=1
  if s[i][j]==1 and s[i-1][j]==1:
    b-=1
  val=min(a,b)
  #print([i,j])
  #print(val)
  dp[i][j]=val
  return val
print(func(h-1,w-1))
#for a in dp:
#  print(a)
#print(s)
#print(dp)

Submission status: Accepted

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

M = [[0] * W for _ in range(H)]
colors = [[''] * W for _ in range(H)]
for i in range(H):
    colors[i] = list(input())
    for j in range(W):
        if i == 0:
            if j == 0:
                M[i][j] = 0 if colors[i][j] == '.' else 1
            else:
                M[i][j] = M[i][j-1] if colors[i][j] == '.' or colors[i][j-1] == '#' else M[i][j-1] + 1
        else:
            if j == 0:
                M[i][j] = M[i-1][j] if colors[i][j] == '.' or colors[i-1][j] == '#' else M[i-1][j] + 1
            else:
                if colors[i][j] == '.':
                    M[i][j] = min([M[i-1][j], M[i][j-1]])
                else:
                    top = M[i-1][j] if colors[i-1][j] == '#' else M[i-1][j] + 1
                    left = M[i][j-1] if colors[i][j-1] == '#' else M[i][j-1] + 1
                    M[i][j] = min(top, left)

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

Submission status: Accepted

Solution code:
from collections import deque
H, W = [int(i) for i in input().split()]
Shw = [[0 if i =="." else 1 for i in input()] for _ in range(H)]

changes = [[-1 for _ in range(W)] for _ in range(H)]

for j in range(H):
  for i in range(W):
    current = Shw[j][i]
    if i == 0 and j ==0:
      changes[j][i] = current
    elif i == 0:
      changes[j][i] = changes[j-1][i] + (1 if current == 1 and Shw[j-1][i] == 0 else 0)
    elif j == 0:
      changes[j][i] = changes[j][i-1] + (1 if current == 1 and Shw[j][i-1] == 0 else 0)
    else:
      upper = changes[j-1][i] + (1 if current == 1 and Shw[j-1][i] == 0 else 0)
      lower = changes[j][i-1] + (1 if current == 1 and Shw[j][i-1] == 0 else 0)
      changes[j][i] = min(upper, lower)
      
print(changes[-1][-1])

Submission status: Accepted

Solution code:
h, w = map(int, input().split())
stage = [list(map(lambda s: {'#': False, '.': True}[s], input())) for _ in range(h)]
change_dp = [[float("inf") for _ in range(w)] for _ in range(h)]
change_dp[0][0] = not stage[0][0]
attention = {(0, 0)}
while len(attention):
    next_attention = set()
    for x, y in attention:

        if x + 1 < h:
            if stage[x][y] == stage[x + 1][y]:
                parent = change_dp[x][y]
            else:
                parent = change_dp[x][y] + 1

            if parent < change_dp[x + 1][y]:
                change_dp[x + 1][y] = parent
                next_attention.add((x + 1, y))

        if y + 1 < w:
            if stage[x][y] == stage[x][y + 1]:
                parent = change_dp[x][y]
            else:
                parent = change_dp[x][y] + 1

            if parent < change_dp[x][y + 1]:
                change_dp[x][y + 1] = parent
                next_attention.add((x, y + 1))

    attention = next_attention

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

Submission status: Accepted

Solution code:
inm   = lambda:      map(int, input().split())
ins = lambda : input().strip()
BIG = 10**18

h,w = inm()
s = []
for i in range(h):
    s.append(ins())
d = [[0]*w for i in range(h)]
d[0][0] = 1 if s[0][0]=='#' else 0
for i in range(h):
    for j in range(w):
        if i==0 and j==0:
            continue
        vx = BIG if i==0 else \
          d[i-1][j]+(1 if s[i-1][j]=='.' and s[i][j]=='#' else 0)
        vy = BIG if j==0 else \
          d[i][j-1]+(1 if s[i][j-1]=='.' and s[i][j]=='#' else 0)
        d[i][j] = min(vx,vy)
        #ddprint(f"i {i} j {j} x {vx} y {vy} dij {d[i][j]}")
print(d[h-1][w-1])

Submission status: Accepted

Solution code:
import collections
h, w = [int(_) for _ in input().split()]
S = [list('.' * (w + 1))] + [['.'] + list(input()) for _ in range(h)]
B = [[99999] * (w + 1) for _ in range(h + 1)]
B[1][1] = 0 if S[1][1] == '.' else 1
cand = collections.deque([(1, 2), (2, 1)])
while cand:
    x, y = cand.popleft()
    if B[x][y] == 99999:
        B[x][y] = min(B[x][y - 1] + (S[x][y] == '#' != S[x][y - 1]),
                      B[x - 1][y] + (S[x][y] == '#' != S[x - 1][y]))
        if x < h:
            cand += [(x + 1, y)]
        if y < w:
            cand += [(x, y + 1)]
print(B[-1][-1])

Submission status: Accepted

Solution code:
#どっちで出すか注意, rstrip注意
#提出前に見返すこと！
def main():
    import sys
    input = sys.stdin.readline
    sys.setrecursionlimit(10000000)
    from collections import Counter, deque
    #from collections import defaultdict
    from itertools import combinations, permutations, accumulate
    #from itertools import product
    from bisect import bisect_left,bisect_right
    import heapq
    from math import floor, ceil
    #from operator import itemgetter

    #inf = 10**17
    #mod = 10**9 + 7

    H,W = map(int, input().split())
    s = [list(input().rstrip()) for _ in range(H)]
    dp = [[0]*W for _ in range(H)]
    if s[0][0] == '#':
        dp[0][0] = 1
    for i in range(H):
        for j in range(W):
            if i == j == 0:
                continue
            elif i == 0:
                if s[i][j] == '#' and s[i][j-1] == '.':
                    dp[i][j] = dp[i][j-1] + 1
                else:
                    dp[i][j] = dp[i][j-1]
            elif 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]
            else:
                p1 = dp[i-1][j]
                p2 = dp[i][j-1]
                if s[i][j] == '#' and s[i-1][j] == '.':
                    p1 += 1
                if s[i][j] == '#' and s[i][j-1] == '.':
                    p2 += 1
                dp[i][j] = min(p1, p2)
    print(dp[H-1][W-1])


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
H, W = map(int, input().split())
sL = []
for i in range(H):
    sL.append(input())
dp = [[0] * W for i in range(H)]

for h in range(H):
    for w in range(W):
        if h == 0 and w == 0:
            if sL[0][0] == ".":
                dp[0][0] = 1
            else: # (1.1) is black
                dp[0][0] = 2
        elif h == 0:
            dp[h][w] = dp[h][w-1] + int(sL[h][w] != sL[h][w-1])
        elif w == 0:
            dp[h][w] = dp[h-1][w] + int(sL[h][w] != sL[h-1][w])
        else:
            A = dp[h-1][w] + int(sL[h][w] != sL[h-1][w])
            B = dp[h][w-1] + int(sL[h][w] != sL[h][w-1])
            dp[h][w] = min(A, B)
            
print(dp[H-1][W-1] // 2)

Submission status: Accepted

Solution code:
h,w=map(int,input().split())
s=[]
cost=[]
for i in range(h):
	S=list(input())
	COST=[0 for i in range(w)]
	s.append(S)
	cost.append(COST)
#print(s) ->s[h][w]
#print(cost)
if s[0][0]=='#':
	cost[0][0]=1
for i in range(h):
	for j in range(w):
		if s[i][j]=='#':
			if i==0:
				if j!=0:
					if s[0][j-1]!='#':
						cost[0][j]=cost[0][j-1]+1
					else:
						cost[0][j]=cost[0][j-1]
			elif j==0:
				if s[i-1][j]!='#':
					cost[i][0]=cost[i-1][0]+1
				else:
					cost[i][0]=cost[i-1][0]
			else:
				cost1=cost[i-1][j]
				if s[i-1][j]!='#':
					cost1+=1
				cost2=cost[i][j-1]
				if s[i][j-1]!='#':
					cost2+=1
				cost[i][j]=min(cost1,cost2)
		else:
			if i==0:
				if j!=0:
					cost[0][j]=cost[0][j-1]
			elif j==0:
				cost[i][0]=cost[i-1][0]
			else:
				cost[i][j]=min(cost[i-1][j],cost[i][j-1])
print(cost[h-1][w-1])

Submission status: Accepted

Solution code:
h, w = map(int, input().split())
ar = []
for _ in range(h):
    row = [c == "#" for c in input().rstrip()]
    ar.append(row)

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

for i in range(h):
    for j in range(w):
        up = None
        right = None
        if i != 0:
            up = count[i - 1][j]
            if ar[i][j] and not ar[i - 1][j]:
                up += 1

        if j != 0:
            right = count[i][j - 1]
            if ar[i][j] and not ar[i][j - 1]:
                right += 1

        if up is None:
            if right is None:
                count[i][j] = int(ar[0][0])
            else:
                count[i][j] = right
        else:
            if right is None:
                count[i][j] = up
            else:
                count[i][j] = min(right, up)

print(count[-1][-1])

Submission status: Accepted

Solution code:
h, w = map(int, input().split())
lst = [['*' for i in range(w+2)]]
for i in range(h):
    string = input()
    lsti = ['*']
    for j in range(w):
        lsti.append(string[j])
        if string[j] == 's':
            start = (i+1, j+1)
        elif string[j] == 'g':
            goal = (i+1, j+1)
    lsti.append('*')
    lst.append(lsti)
lst.append(['*' for i in range(w+2)])

lst_cnt = [[300 for i in range(w+2)] for j in range(h+2)]
if lst[1][1] == '#':
    lst_cnt[1][1] = -1
else:
    lst_cnt[1][1] = 0

queue_new = [(1, 1)]
while queue_new != []:
    queue = queue_new
    queue_new = []
    while queue != []:
        zahyo = queue.pop()
        i, j = zahyo[0], zahyo[1]
        if lst[i+1][j] == '#':
            if lst_cnt[i][j] < 0:
                if abs(lst_cnt[i][j]) < abs(lst_cnt[i+1][j]):
                    lst_cnt[i+1][j] = -abs(lst_cnt[i][j])
                    queue_new.append((i+1, j))
            else:
                if abs(lst_cnt[i][j])+1 < abs(lst_cnt[i+1][j]):
                    lst_cnt[i+1][j] = -(abs(lst_cnt[i][j])+1)
                    queue_new.append((i+1, j))
        elif lst[i+1][j] == '.':
            if abs(lst_cnt[i][j]) < abs(lst_cnt[i+1][j]):
                lst_cnt[i+1][j] = abs(lst_cnt[i][j])
                queue_new.append((i+1, j))
        
        if lst[i][j+1] == '#':
            if lst_cnt[i][j] < 0:
                if abs(lst_cnt[i][j]) < abs(lst_cnt[i][j+1]):
                    lst_cnt[i][j+1] = -abs(lst_cnt[i][j])
                    queue_new.append((i, j+1))
            else:
                if abs(lst_cnt[i][j])+1 < abs(lst_cnt[i][j+1]):
                    lst_cnt[i][j+1] = -(abs(lst_cnt[i][j])+1)
                    queue_new.append((i, j+1))
        elif lst[i][j+1] == '.':
            if abs(lst_cnt[i][j]) < abs(lst_cnt[i][j+1]):
                lst_cnt[i][j+1] = abs(lst_cnt[i][j])
                queue_new.append((i, j+1))
print(abs(lst_cnt[h][w]))

Submission status: Accepted

Solution code:
import sys
input=sys.stdin.readline
from math import *
n,m=map(int,input().split())
a=[]
for i in range(n):
    p=list(input().rstrip())
    a.append(p)
p=[[0 for i in range(m+1)] for j in range(n+1)]
for i in range(n):
    for j in range(m):
        if i==0 and j==0 and a[i][j]=='#':
            p[i][j]=1
        elif i==0:
            p[i][j]=p[i][j-1]+int(a[i][j]=='#' and a[i][j-1]!='#')
        elif j==0:
            p[i][j]=p[i-1][j]+int(a[i][j]=='#' and a[i-1][j]!='#')
        else:
            p[i][j]=min(p[i][j-1]+int(a[i][j]=='#' and a[i][j-1]!='#'),p[i-1][j]+int(a[i][j]=='#' and a[i-1][j]!='#'))
print(p[n-1][m-1])

Submission status: Accepted

Solution code:
from fractions import gcd
# from datetime import date, timedelta
# from heapq import *
import heapq
import math
from collections import defaultdict, Counter, deque
from bisect import *
import itertools
import fractions
import sys
sys.setrecursionlimit(10 ** 7)
MOD = 10 ** 9 + 7
# input = sys.stdin.readline


def make_divisors(n):
    divisors = []
    for i in range(1, int(n**0.5)+1):
        if n % i == 0:
            divisors.append(i)
            if i != n // i:
                divisors.append(n//i)

    divisors.sort()
    return divisors


def main():

    # print(100, 100)
    # for i in range(100):
    #     s=""
    #     for j in range(100):
    #         if j % 2 == 0:
    #             if i % 2 == 0:
    #                 s += "#"
    #             else:
    #                 s += "."
    #         else:
    #             if i % 2 == 0:
    #                 s += "."
    #             else:
    #                 s += "#"
    #     print(s)



    h, w = map(int, input().split())
    maze = [input() for i in range(h)]
    ans = 0
    # if maze[0][0] == "#":
    #     ans+=1
    

    def Dijkstra_search(sx, sy):
        H = h
        W = w
        visited = [[False for i in range(W)] for j in range(H)]
        d = [[float("inf") for i in range(W)] for j in range(H)]  # now cost
        d[sx][sy] = 0

        queue = []
        heapq.heappush(queue, (0, (sx, sy)))
        while len(queue):
            cost, (x, y) = heapq.heappop(queue)

            if visited[x][y]:
                continue
            visited[x][y] = True

            for dx, dy in [[1, 0], [0, 1]]:
                nx = x + dx
                ny = y + dy
                if nx >= 0 and ny >= 0 and nx < H and ny < W:
                    if visited[nx][ny]:
                        continue

                    vd=cost
                    if maze[nx][ny] =="." and maze[x][y]=="#":
                        vd+=1
                    if d[nx][ny] > vd:
                        d[nx][ny] = vd
                        heapq.heappush(queue, (vd, (nx, ny)))

        if maze[h - 1][w - 1] == "#":
            d[h-1][w-1]+=1
        return d[h-1][w-1]

    ans += Dijkstra_search(0,0)
    print(ans)
 


if __name__ == '__main__':
    main()

Submission status: Accepted

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

read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

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


@lru_cache(maxsize=None)
def dfs(r, c, cnt, iswhite=True):
    # if r == H - 1 and c == W - 1:
        # return cnt

    now = '.' if iswhite == True else '#'

    ans = 200

    if MEIJI[r][c] != now:
        if iswhite == True:
            cnt += 1

        iswhite = not (iswhite)

    if r == H-1 and c == W - 1:
        return cnt
    if r < H-1:
        ans = min(dfs(r + 1, c, cnt, iswhite), ans)
    if c < W-1:
        ans = min(dfs(r, c + 1, cnt, iswhite), ans)

    return ans


ans = dfs(0, 0, 0, True)
print(ans)

Submission status: Accepted

Solution code:
H, W=map(int, input().split())
s=[input() for _ in range(H)]
math=[[-2]*W for _ in range(H)]

from collections import deque
q=deque()
qnex=deque()

def f(r, c, num):
  math[r][c]=num
  if s[r][c]=='#':
    if r<H-1 and math[r+1][c]<-1:
      q.append([r+1, c, num])
      math[r+1][c]=-1
    if c<W-1 and math[r][c+1]<-1:
      q.append([r, c+1, num])
      math[r][c+1]=-1
  else:
    if r<H-1 and math[r+1][c]<-1:
      if s[r+1][c]=='.':
        q.append([r+1, c, num])
        math[r+1][c]=-1
      else:
        qnex.append([r+1, c, num+1])
    if c<W-1 and math[r][c+1]<-1:
      if s[r][c+1]=='.':
        q.append([r, c+1, num])
        math[r][c+1]=-1
      else:
        qnex.append([r, c+1, num+1])

if s[0][0]=='.':
  f(0, 0, 0)
else:
  f(0, 0, 1)
  
while math[-1][-1]<0:
  while len(q)>0:
    data=q.popleft()
    f(data[0], data[1], data[2])
    
  while len(qnex)>0:
    data=qnex.popleft()
    if math[data[0]][data[1]]<-1:
      q.append(data)
  
print(math[-1][-1])

Submission status: Accepted

Solution code:
import sys
def main():
    input = sys.stdin.readline
    H,W=map(int, input().split())
    S=[list(input()) for _ in range(H)]

    #dp[i][j]=[i,j]にたどり着くまでの黒のかたまりの数の最小値
    INF = 10**9
    dp = [[INF] * W for _ in range(H)]
    dp[0][0] = 1 if S[0][0] == '#' else 0
    for i in range(H):
        for j in range(W):
            if i > 0: #上から来た
                if S[i-1][j] != '#' and S[i][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 > 0: #左から来た
                if S[i][j-1] != '#' and S[i][j] == '#': #白→黒
                    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])

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
import sys
# input = sys.stdin.r/eadline
def INT(): return int(input())
def MAP(): return map(int,input().split())
def LI(): return list(map(int,input().split()))

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

    if s[0][0] == "#":
        dp[0][0] = 1

    for i in range(H):
        for j in range(W):
            if i == 0:
                if j == 0:
                    continue

                if s[i][j] == "#" and s[i][j-1] == ".":
                    dp[i][j] = dp[i][j-1]+1
                else:
                    dp[i][j] = dp[i][j-1] 
            else:
                if j == 0:
                    if s[i-1][j] == "." and s[i][j] == "#":
                        up = dp[i-1][j]+1
                    else:
                        up = dp[i-1][j]
                    dp[i][j] = up
                    continue
                else:
                    if s[i-1][j] == "." and s[i][j] == "#":
                        up = dp[i-1][j]+1
                    else:
                        up = dp[i-1][j]
                    
                    if s[i][j-1] == "." and s[i][j] == "#":
                        left = dp[i][j-1]+1
                    else:
                        left = dp[i][j-1]
                    
                    dp[i][j] = min(left,up)

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

if __name__ == '__main__':
    main()

Submission status: Accepted

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

Submission status: Accepted

Solution code:

h, w = map(int, input().split())
mp = [list(input()) for i in range(h)]
dp = [[0]*105 for _ in range(105)]
if mp[0][0]=='#':
    dp[0][0]+=1
for i in range(w-1):
    plus=0
    if mp[0][i+1]!=mp[0][i] and mp[0][i+1] == '#':
        plus=1
    dp[0][i+1] = dp[0][i]+plus
for i in range(h-1):
    plus=0
    if mp[i+1][0]!=mp[i][0] and mp[i+1][0] == '#':
        plus=1
    dp[i+1][0] = dp[i][0]+plus

for i in range(1,h):
    for j in range(1,w):
        plus=0
        plus2=0
        if mp[i][j]!=mp[i-1][j] and mp[i][j]=='#':
            plus=1
        if mp[i][j]!=mp[i][j-1] and mp[i][j]=='#':
            plus2=1
        dp[i][j] = min(dp[i-1][j]+plus, dp[i][j-1]+plus2)

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

Submission status: Accepted

Solution code:
import collections
import math
import operator as op
from functools import reduce
import numpy as np
import math
import bisect
import heapq


MOD = 1000000007


def gcd(a, b):
    while b:
        a, b = b, a % b
    return a


def lcm(a, b):
    return a * b // gcd(a, b)


def get_inputs(cast_func=None):
    if cast_func is None:
        return input().split()
    else:
        return list(map(cast_func, input().split()))


def get_input(cast_func=None):
    if cast_func is None:
        return input()
    else:
        return cast_func(input())


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


def main():
    H, W = get_inputs(int)
    # white: 1 / black: 0
    s = np.zeros((H, W), dtype=np.int)
    req_n_ops = np.empty((H, W), dtype=np.int)
    for i in range(H):
        row = get_input(str)
        for j, r in enumerate(row):
            if r == ".":
                s[i, j] = 1

    if s[0, 0] == 0:
        req_n_ops[0, 0] = 1
    else:
        req_n_ops[0, 0] = 0

    for l in range(1, W+H-1):
        for i in range(H):
            j = l - i
            if not(i >= 0 and i < H and j >= 0 and j < W):
                continue
            # print(i, j)
            if i >= 1:
                if s[i, j] == 0 and s[i-1, j] == 1:
                    x1 = req_n_ops[i-1, j] + 1
                else:
                    x1 = req_n_ops[i-1, j]
            else:
                x1 = 100000

            if j >= 1:
                if s[i, j] == 0 and s[i, j-1] == 1:
                    x2 = req_n_ops[i, j-1] + 1
                else:
                    x2 = req_n_ops[i, j-1]
            else:
                x2 = 100000

            req_n_ops[i, j] = min(x1, x2)


    # print(req_n_ops)
    print(int(req_n_ops[-1, -1]))


if __name__ == '__main__':
    main()