Problem:


Score : 400 points

Problem Statement

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

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

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

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

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

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

Constraints

2 \leq H, W \leq 100

Input

Input is given from Standard Input in the following format:

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

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

Output

Print the minimum number of operations needed.

Sample Input 1

3 3
.##
.#.
##.

Sample Output 1

1

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

Sample Input 2

2 2
#.
.#

Sample Output 2

2

Sample Input 3

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

Sample Output 3

0

No operation may be needed.

Sample Input 4

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

Sample Output 4

4



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


Sample output:
1

Submission status: Accepted

Solution code:
H, W = map(int,input().split())
MAP = []
INF = 10 ** 8
for _ in range(H):
    MAP.append(input())

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

for i in range(H):
    for j in range(W):
        if i == 0 and j == 0:
            if MAP[i][j] == "#":
                dp[i][j] = 1
        elif i == 0:
            flag = 0
            if MAP[i][j] == "#" and MAP[i][j-1] == ".":
                flag = 1
            dp[i][j] = flag + dp[i][j-1]
        elif j == 0:
            flag = 0
            if MAP[i][j] == "#" and MAP[i-1][j] == ".":
                flag = 1
            dp[i][j] = flag + dp[i-1][j]
        else:
            flag1 = 0
            flag2 = 0
            if MAP[i][j] == "#" and MAP[i][j-1] == ".":
                flag1 = 1
            if MAP[i][j] == "#" and MAP[i-1][j] == ".":
                flag2 = 1
            dp[i][j] = min(dp[i][j-1]+flag1,dp[i-1][j]+flag2)
        

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

Submission status: Accepted

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

def solve():
    dxys = [(1,0), (0,1)]

    H, W = map(int, input().split())
    Sss = ['$'*(W+2)] + ['$'+input().rstrip()+'$' for _ in range(H)] + ['$'*(W+2)]

    vWhites, vBlacks = set(), set()
    if Sss[1][1] == '.':
        vWhites.add((1, 1))
    else:
        vBlacks.add((1, 1))

    ans = 0
    while True:
        while vWhites:
            v2s = set()
            for r, c in vWhites:
                if (r, c) == (H, W):
                    return ans
                for dr, dc in dxys:
                    r2, c2 = r+dr, c+dc
                    if Sss[r2][c2] == '$': continue
                    if Sss[r2][c2] == '.':
                        v2s.add((r2, c2))
                    else:
                        vBlacks.add((r2, c2))
            vWhites = v2s
        ans += 1

        while vBlacks:
            v2s = set()
            for r, c in vBlacks:
                if (r, c) == (H, W):
                    return ans
                for dr, dc in dxys:
                    r2, c2 = r+dr, c+dc
                    if Sss[r2][c2] == '$': continue
                    if Sss[r2][c2] == '#':
                        v2s.add((r2, c2))
                    else:
                        vWhites.add((r2, c2))
            vBlacks = v2s
#        ans += 1


ans = solve()
print(ans)

Submission status: Accepted

Solution code:
h,w =map(int,input().split())
ls = []
for i in range(h):
    ls.append(list(input()))
ma = [[(10**9)]*w for i in range(h)]
if ls[0][0] == "." :
    ma[0][0] = 0
else:
    ma[0][0] =1
delta = [(-1,0),(0,-1)]
for y in range(h):
    for x in range(w):
        for dy,dx in delta:
            if 0<=y+dy<=h-1 and 0<=x+dx<=w-1 :
                if ls[y][x] == ls[y+dy][x+dx]:
                    ma[y][x] = min(ma[y+dy][x+dx],ma[y][x])
                else:
                    if ls[y][x] =="#":
                        cnt = 1
                    else:
                        cnt =0
                    ma[y][x] = min(ma[y][x],ma[y+dy][x+dx]+cnt)
print(ma[h-1][w-1])

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-

#############
# Libraries #
#############

import sys
input = sys.stdin.readline

import math
from collections import deque
from fractions import gcd
from functools import lru_cache


#############
# Constants #
#############

MOD = 10**9 +7
INF = float('inf')

#############
# Functions #
#############

######INPUT######
def inputI(): return int(input().strip())
def inputS(): return input().strip()
def inputIL(): return list(map(int,input().split()))
def inputSL(): return list(map(str,input().split()))
def inputILs(n): return list(int(input()) for _ in range(n))
def inputSLs(n): return list(input().strip() for _ in range(n))
def inputILL(n): return [list(map(int, input().split())) for _ in range(n)]
def inputSLL(n): return [list(map(str, input().split())) for _ in range(n)]

#####Inverse#####
def inv(n): return pow(n, MOD-2, MOD)

######Combination######
kaijo_memo = []
def kaijo(n):
  if(len(kaijo_memo) > n):
    return kaijo_memo[n]
  if(len(kaijo_memo) == 0):
    kaijo_memo.append(1)
  while(len(kaijo_memo) <= n):
    kaijo_memo.append(kaijo_memo[-1] * len(kaijo_memo) % MOD)
  return kaijo_memo[n]

gyaku_kaijo_memo = []
def gyaku_kaijo(n):
  if(len(gyaku_kaijo_memo) > n):
    return gyaku_kaijo_memo[n]
  if(len(gyaku_kaijo_memo) == 0):
    gyaku_kaijo_memo.append(1)
  while(len(gyaku_kaijo_memo) <= n):
    gyaku_kaijo_memo.append(gyaku_kaijo_memo[-1] * pow(len(gyaku_kaijo_memo),MOD-2,MOD) % MOD)
  return gyaku_kaijo_memo[n]

def nCr(n,r):
  if(n == r):
    return 1
  if(n < r or r < 0):
    return 0
  ret = 1
  ret = ret * kaijo(n) % MOD
  ret = ret * gyaku_kaijo(r) % MOD
  ret = ret * gyaku_kaijo(n-r) % MOD
  return ret

######Factorization######
def factorization(n):
    arr = []
    temp = n
    for i in range(2, int(-(-n**0.5//1))+1):
        if temp%i==0:
            cnt=0
            while temp%i==0:
                cnt+=1
                temp //= i
            arr.append([i, cnt])
    if temp!=1:
        arr.append([temp, 1])

    if arr==[]:
        arr.append([n, 1])
    return arr

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

#############
# Main Code #
#############

H,W = inputIL()
s = []
for i in range(H):
  s.append(list(inputS()))

dp = [[INF for __ in range(W)] for ___ in range(H)]

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


if s[0][0] == ".":
  print((dp[-1][-1]+1)//2)
else:
  print((dp[-1][-1])//2+1)

Submission status: Accepted

Solution code:
def flip_count_mem(r, c):
  if memory[r][c] < 0:
    memory[r][c] = flip_count(r, c)
  return memory[r][c]

def flip_count (r, c):
  if r == H - 1 and c == W - 1:
    if s[r][c] == "#":
      return 1
    else:
      return 0
  #右に行ったとき
  if c == W - 1:
    count_right = 10000
  else:
    count_right = flip_count_mem (r, c + 1)
    if s[r][c] == "#" and s[r][c + 1] == ".":
      count_right += 1
  #下に行ったとき
  if r == H - 1:
    count_down = 10000
  else:
    count_down = flip_count_mem (r + 1, c)
    if s[r][c] == "#" and s[r + 1][c] == ".":
      count_down += 1
  return min(count_right, count_down)

H, W = input().split()
W = int (W)
H = int (H)
s = []
for i in range(H):
  s.append(input())
memory = [[-1 for i in range(W)] for j in range(H)]
print (flip_count(0, 0))

Submission status: Accepted

Solution code:
def main():
    H, W = map(int, input().split())
    S = [input() for _ in range(H)]
    if S[0][0] == '.':
        c, f = 0, False
    else:
        c, f = 1, True
    v = [(c, f)]
    for s in S[0][1:]:
        sf = s == '#'
        if sf != f:
            c, f = c + 1, not f
        v.append((c, f))
    u = v
    for ss in S[1:]:
        c, f = u[0]
        sf = ss[0] == '#'
        if sf != f:
            c, f = c + 1, not f
        v = [(c, f)]
        for i, s in enumerate(ss[1:], 1):
            uc, uf = u[i]
            sf = s == '#'
            if uf != sf:
                uc, uf = uc + 1, not uf
            if f != sf:
                c, f = c + 1, not f
            if uc < c:
                c, f = uc, uf
            v.append((c, f))
        u = v
    return (u[-1][0] + 1) // 2

print(main())

Submission status: Accepted

Solution code:
from math import ceil
from collections import defaultdict

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

n = h * w
INF = 100 * 100

dp = defaultdict(lambda: INF)
if s[0][0] == "#":
    dp[(1, 1, 1)] = 1
else:
    dp[(1, 1, 0)] = 0

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

idx = 1 if s[h-1][w-1] == "#" else 0
ans = dp[(h, w, idx)]
ans = ceil(ans / 2)
print(ans)

Submission status: Accepted

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

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

# 初期条件
if S[0][0] == "#":
    dp[0][0][0] = 1
    dp[0][0][1] = True
for j in range(1,W):
    dp[0][j] = dp[0][j-1].copy()
    if not dp[0][j-1][1]:
        if S[0][j] == "#":
            dp[0][j][0] += 1
            dp[0][j][1] = True
    else:
        if S[0][j] == ".":
            dp[0][j][1] = False
for i in range(1,H):
    dp[i][0] = dp[i-1][0].copy()
    if not dp[i-1][0][1]:
        if S[i][0] == "#":
            dp[i][0][0] += 1
            dp[i][0][1] = True
    else:
        if S[i][0] == ".":
            dp[i][0][1] = False

def which(i,j):
    """
    True -> 上
    False -> 左
    """
    if dp[i-1][j][0] > dp[i][j-1][0]:
        return False
    elif dp[i-1][j][0] < dp[i][j-1][0]:
        return True
    else:
        if S[i][j] == "#":
            if dp[i-1][j][1]:
                return True
            else:
                return False
        else:
            if not dp[i-1][j][1]:
                return True
            else:
                return False

# DPループ
for i in range(1,H):
    for j in range(1,W):
        if which(i,j): # 上
            dp[i][j] = dp[i-1][j].copy()
            if not dp[i-1][j][1]:
                if S[i][j] == "#":
                    dp[i][j][0] += 1
                    dp[i][j][1] = True
            else:
                if S[i][j] == ".":
                    dp[i][j][1] = False
        else: # 左
            dp[i][j] = dp[i][j-1].copy()
            if not dp[i][j-1][1]:
                if S[i][j] == "#":
                    dp[i][j][0] += 1
                    dp[i][j][1] = True
            else:
                if S[i][j] == ".":
                    dp[i][j][1] = False

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

Submission status: Accepted

Solution code:
from collections import deque
h,w = map(int,input().split())
data = [input() for _ in range(h)]
pena = [[10**10]*w for _ in range(h)]
queue = deque()
if data[0][0] == ".":
    pena[0][0] = 0
else:
    pena[0][0] = 1
queue.append([0,0])
while queue:
    x,y = queue.popleft()
    if x+1<h:
        c = False
        if pena[x+1][y] == 10**10:
            c = True
        if data[x+1][y] == '#' and data[x][y] == '.':
            pena[x+1][y] = min(pena[x+1][y],pena[x][y] + 1)
        else:
            pena[x+1][y] = min(pena[x+1][y],pena[x][y])
        if c:
            queue.append([x+1,y])

    if y+1<w:
        c = False
        if pena[x][y+1] == 10 ** 10:
            c = True
        if data[x][y+1] == '#' and data[x][y] == '.':
            pena[x][y+1] = min(pena[x][y+1],pena[x][y] + 1)
        else:
            pena[x][y + 1] = min(pena[x][y+1], pena[x][y])
        if c:
            queue.append([x,y+1])

print(pena[-1][-1])

Submission status: Accepted

Solution code:

import sys
sys.setrecursionlimit(1 << 25)
read = sys.stdin.readline


def read_ints():
    return list(map(int, read().split()))


def read_a_int():
    return int(read())


def read_tuple(H):
    '''
    H is number of rows
    '''
    ret = []
    for _ in range(H):
        ret.append(tuple(map(int, read().split())))
    return ret


def read_col(H, n_cols):
    '''
    H is number of rows
    n_cols is number of cols
    A列、B列が与えられるようなとき
    '''
    ret = [[] for _ in range(n_cols)]
    for _ in range(H):
        tmp = list(map(int, read().split()))
        for col in range(n_cols):
            ret[col].append(tmp[col])
    return ret


def read_matrix(H):
    '''
    H is number of rows
    '''
    ret = []
    for _ in range(H):
        ret.append(list(map(int, read().split())))
    return ret
    # return [list(map(int, read().split())) for _ in range(H)] # 内包表記はpypyでは遅いため


def read_map(H):
    '''
    H is number of rows
    文字列で与えられた盤面を読み取る用
    '''
    return [read()[:-1] for _ in range(H)]


def read_map_as_int(H):
    '''
    #→1,.→0として読み込む
    '''
    ret = []
    for _ in range(H):
        ret.append([1 if s == '#' else 0 for s in read()[:-1]])
        # 内包表記はpypyでは若干遅いことに注意
        # #numpy使うだろうからこれを残しておくけど
    return ret


MOD = 10**9 + 7
# default import
from itertools import product, permutations, combinations
H, W = read_ints()
S = read_map_as_int(H)  # が1 .が0

dp = [[100000] * (W) for _ in range(H)]  # -1アクセス用に余分に取っておく
# 初期化
dp[0][0] = S[0][0]

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

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

Submission status: Accepted

Solution code:
H, W = map(int, input().split())
S = ['' for _ in range(H)]
for i in range(H):
    S[i] = input()
DP = [[0 for _ in range(W)] for _ in range(H)]
if S[0][0] == '#':
    DP[0][0] = 1
for i in range(1,W):
    if S[0][i] == '#' and S[0][i-1] == '.':
        DP[0][i] = DP[0][i-1] + 1
    else:
        DP[0][i] = DP[0][i-1]
for h in range(1,H):
    for w in range(W):
        if w == 0:
            if S[h][w] == '#' and S[h-1][w] == '.':
                DP[h][w] = DP[h-1][w] + 1
            else:
                DP[h][w] = DP[h-1][w]
        else:
            if S[h][w] == '#' and S[h-1][w] == '.':
                r = DP[h-1][w] + 1
            else:
                r = DP[h-1][w]
            if S[h][w] == '#' and S[h][w-1] == '.':
                c = DP[h][w-1] + 1
            else:
                c = DP[h][w-1]
            DP[h][w] = min(r, c)
print(DP[H-1][W-1])

Submission status: Accepted

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

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

for i in range(h):
    for j in range(w-1):
        if i > 0:
            dp[i][0] = dp[i-1][0] if s[i][0] == s[i-1][0] else dp[i-1][0]+1
            above = dp[i-1][j+1]
            left  = dp[i][j]
            if s[i-1][j+1] != s[i][j+1]:
                above += 1
            if s[i][j] != s[i][j+1]:
                left += 1
            dp[i][j+1] = min(above,left)
        else:
            left  = dp[i][j]
            if s[i][j] != s[i][j+1]:
                left += 1
            dp[i][j+1] = left

n = dp[-1][-1]
if s[0][0] == '.' and s[-1][-1] == '.':
    print(n//2)
elif s[0][0] == '#' and s[-1][-1] == '#':
    print(n//2+1)
else:
    print((n+1)//2)

Submission status: Accepted

Solution code:
input = raw_input
h, w = map(int, input().split(" "))
gh = h - 1
gw = w - 1

#dot_coords = []
#for hi in range(h):
#    wi = 0
#    for c in input():
#        if c == ".":
#            dot_coords.append((wi, hi))
#        wi += 1
        
maps = [list(input()) for _ in range(h)]
num_maps = [[None for _ in range(w)] for _ in range(h)]

count = 0
def find(sx, sy, cur_cost, color):
    next_cost_coord = []
    global count
    num_r = 1
    found = False
    routes = [(sx, sy)]
    num_maps[sy][sx] = cur_cost
    count += 1

    pre = False
    if sx == 1 and sy == 1:
        pre = True

    while num_r >= 1 and not found:
        x, y = routes[0]
        routes = routes[1:]
        num_r -= 1

        for nx, ny in [(x+1, y), (x, y+1)]:
            if pre:
                pass
                #print("lennummap", len(num_maps))
                #print(num_maps, ny, nx)
                #print(x, y, nx, ny, num_maps[ny][nx], gw, gh, "routes", routes)

            if nx <= gw and ny <= gh:
                if num_maps[ny][nx] is None:
                    if maps[ny][nx] == color:
                        num_maps[ny][nx] = cur_cost
                        if nx == gw and ny == gh:
                            found = True
                            return next_cost_coord, found
                        else:
                            routes.append((nx, ny))
                            num_r += 1
                    else:
                        next_cost_coord.append((nx, ny))
    return next_cost_coord, found

cur_coords = [(0, 0)]
if maps[0][0] == ".":
    cur_cost = 0
else:
    cur_cost = 1

while True:   
    color = "." if cur_cost % 2 == 0 else "#"
    #print("cur_cost", cur_cost, "cur_coords", cur_coords)
    next_coords = []

    in_cost = cur_cost // 2 if cur_cost % 2 == 0 else cur_cost // 2 + 1
    for sx, sy in cur_coords:
        cur_nc_coord, found = find(sx, sy, in_cost, color)
        next_coords += cur_nc_coord
        #print(cur_nc_coord, num_maps)
        found = num_maps[gh][gw] is not None
        if found:
            break
    #print("cur_cost", cur_cost,"num_maps", num_maps)
    if found:
        break
    else:
        #print("test")
        cur_coords = set(next_coords)
        assert len(cur_coords) >= 1
        cur_cost += 1
        #print("cur_cost", cur_cost)

out = num_maps[gh][gw]
print(out)
#print(count)

Submission status: Accepted

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

mat=[]
for i in range(H):
  array=[x=='.' for x in input()]
  mat.append(array)
#print(mat)

dist=[]
for i in range(H):
  dist.append([-1]*W)

if mat[0][0]:
  dist[0][0]=0
else:
  dist[0][0]=1
  
for i in range(1,H):
  if mat[i-1][0] and not mat[i][0]:
    dist[i][0]=dist[i-1][0]+1
  else:
    dist[i][0]=dist[i-1][0]
    
for j in range(1,W):
  if mat[0][j-1] and not mat[0][j]:
    dist[0][j]=dist[0][j-1]+1
  else:
    dist[0][j]=dist[0][j-1]
    
for i in range(1,H):
  for j in range(1,W):
    if mat[i-1][j] and not mat[i][j]:
      dist1=dist[i-1][j]+1
    else:
      dist1=dist[i-1][j]
    
    if mat[i][j-1] and not mat[i][j]:
      dist2=dist[i][j-1]+1
    else:
      dist2=dist[i][j-1]
      
    dist[i][j]=min(dist1,dist2)
    
#print(dist)
print(dist[H-1][W-1])

Submission status: Accepted

Solution code:
def main():
    H, W = map( int, input().split())
    S = [ list( input()) for _ in range(H)]
    # if S[0][0] == "#":
    #     for i in range(H):
    #         for j in range(W):
    #             if S[i][j] == ".":
    #                 S[i][j] = "#"
    #             else:
    #                 S[i][j] = "."
    dp = [[10**5]*W for _ in range(H)]
    # if S[0][0] == "#":
    #     dp[0][0] = 1
    # else:
    #     dp[0][0] = 0
    dp[0][0] = 0
    for i in range(H):
        for j in range(W):
            if i > 0:
                if S[i-1][j] == S[i][j]:
                    if dp[i-1][j] < dp[i][j]:
                        dp[i][j] = dp[i-1][j]
                else:
                    if dp[i-1][j]+1 < dp[i][j]:
                        dp[i][j] = dp[i-1][j]+1
            if j > 0:
                if S[i][j-1] == S[i][j]:
                    if dp[i][j-1] < dp[i][j]:
                        dp[i][j] = dp[i][j-1]
                else:
                    if dp[i][j-1]+1 < dp[i][j]:
                        dp[i][j] = dp[i][j-1]+1
    #print(dp)
    ans = dp[H-1][W-1]
    ans //= 2
    if S[0][0] == "#" or S[H-1][W-1] == "#":
        ans += 1
    print(ans)
                
if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
from collections import deque
t,*g=open(0)
h,w=map(int,t.split())
vis=[[1e9]*w for _ in range(h)]
vis[0][0]=int(g[0][0]=="#")
q=deque([(0,0)])
while q:
	cy,cx=q.popleft()
	for ny,nx in ((cy+1,cx),(cy,cx+1)):
		if not not (0<=ny<h and 0<=nx<w) and vis[cy][cx]+(g[cy][cx]!=g[ny][nx]=="#")<vis[ny][nx]:
			vis[ny][nx]=vis[cy][cx]+(g[cy][cx]!=g[ny][nx]=="#")
			q.append((ny,nx))
print(vis[-1][-1])

Submission status: Accepted

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

road_count = 0
lis = [list('#'*(w+2))]
for _ in range(h):
    li = input()
    for i in li:
        if i == '.':
            road_count += 1
    li = '#' + li + '#'
    lis.append(list(li))
lis.append(list('#'*(w+2)))

#print(lis)
dp = [[999]*(w+2) for _ in range(h+2)]

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

#print(dp)
#(開始x,開始y)
step = [[1,1]]
while len(step)>0:
    x,y = step.pop(0)
    if x > h:
        continue
    if y > w:
        continue
    #print(x,y)
    if dp[x+1][y] == 999:
        step.append([x+1,y])
        if lis[x+1][y] != '#':
            dp[x+1][y] = min(dp[x][y],dp[x+1][y-1])
        else:
            if lis[x][y] == '#' and lis[x+1][y-1] == '#':
                dp[x+1][y] = min(dp[x][y],dp[x+1][y-1])
            elif lis[x][y] == '#':
                dp[x+1][y] = min(dp[x][y],dp[x+1][y-1]+1)
            elif lis[x+1][y-1] == '#':
                dp[x+1][y] = min(dp[x][y]+1,dp[x+1][y-1])
            else:
                dp[x+1][y] = min(dp[x][y],dp[x+1][y-1])+1
    if dp[x][y+1] == 999:
        step.append([x,y+1])
        if lis[x][y+1] != '#':
            dp[x][y+1] = min(dp[x][y],dp[x-1][y+1])
        else:
            if lis[x][y] == '#' and lis[x-1][y+1] == '#':
                dp[x][y+1] = min(dp[x][y],dp[x-1][y+1])
            elif lis[x][y] == '#':
                dp[x][y+1] = min(dp[x][y],dp[x-1][y+1]+1)
            elif lis[x-1][y+1] == '#':
                dp[x][y+1] = min(dp[x][y]+1,dp[x-1][y+1])
            else:
                dp[x][y+1] = min(dp[x][y],dp[x-1][y+1])+1
#print(lis)
#print(dp)
print(dp[h][w])

Submission status: Accepted

Solution code:
import heapq

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

mat=[]
for i in range(H):
  array=[x=='.' for x in input()]
  mat.append(array)
#print(mat)

dist=[]
for i in range(H):
  dist.append([-1]*W)

if mat[0][0]:
  dist[0][0]=0
else:
  dist[0][0]=1
  
for i in range(1,H):
  if mat[i-1][0] and not mat[i][0]:
    dist[i][0]=dist[i-1][0]+1
  else:
    dist[i][0]=dist[i-1][0]
    
for j in range(1,W):
  if mat[0][j-1] and not mat[0][j]:
    dist[0][j]=dist[0][j-1]+1
  else:
    dist[0][j]=dist[0][j-1]
    
for i in range(1,H):
  for j in range(1,W):
    if mat[i-1][j] and not mat[i][j]:
      dist1=dist[i-1][j]+1
    else:
      dist1=dist[i-1][j]
    
    if mat[i][j-1] and not mat[i][j]:
      dist2=dist[i][j-1]+1
    else:
      dist2=dist[i][j-1]
      
    dist[i][j]=min(dist1,dist2)
    
#print(dist)
print(dist[H-1][W-1])

Submission status: Accepted

Solution code:
#!python3

iim = lambda: map(int, input().rstrip().split())

def resolve():
    H, W = iim()
    S = [input() for i in range(H)]
    c1 = "#"
    H1, W1 = H-1, W-1

    inf = H*W+1
    dq = [0]*W
    dq0 = [(inf, True)]*W
    dq0[0] = (0, True)

    for y in range(H):
        (co, good0) = dq0[0]

        good = not S[y][0] == c1
        if not good:
            if good0:
                co += 1
        dq1 = dq[0] = (co, good)
        for x in range(1, W):
            (co0, good0) = dq0[x]
            (co1, good1) = dq1
            good = not S[y][x] == c1
            if not good:
                if good0:
                    co0 += 1
                if good1:
                    co1 += 1
            dq1 = dq[x] = (min(co0, co1), good)
        dq, dq0 = dq0, dq
        #print(dq0)
    print(dq0[-1][0])

if __name__ == "__main__":
    resolve()

Submission status: Accepted

Solution code:
def bw(a):
    c=0
    if a=="#":
        c=1
    return c

def bw2(a,b): #b = now
    c=0
    if a=="." and b=="#":
        c=1
    return c

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

s=[ "" for i in range(H) ]
for i in range(H):
    s[i] = input()

M=[[1000 for j in range(W)] for i in range(H) ]

M[0][0] = bw(s[0][0])


for i in range(H-1):
    M[i+1][0] = M[i][0] + bw2(s[i][0],s[i+1][0]) 

    
for j in range(W-1):
    M[0][j+1] = M[0][j]+ bw2(s[0][j],s[0][j+1])

    

for i in range(H-1):
    for j in range(W-1):
        
        M[i+1][j+1] = min(M[i][j+1] + bw2(s[i][j+1],s[i+1][j+1]) , M[i+1][j]+ bw2(s[i+1][j],s[i+1][j+1]) )
print(M[H-1][W-1])

Submission status: Accepted

Solution code:
H, W = map(int, input().split())
S = [0]*(H+2)
S[0] = '*'*(W+2)
S[H+1] = '*'*(W+2)
for i in range(1,H+1):
  S[i] = '*'+input()+'*'


unsearched_nodes = list(range(1,H*W+1)) # 未探索ノード
distance= [10000]*(W*H+1)
#print(unsearched_nodes,distance)
previous_move = [[-1]*(W+2) for _ in range(H+2)] # 最短経路でそのノードのひとつ前に到達するノードのリスト
previous_color = [''] * (H*W+1)
distance[1] = 0 # 初期のノードの距離は0とする
if S[1][1]=='#':
  distance[1] = 1
while len(unsearched_nodes) != 0: #未探索ノードがなくなるまで繰り返す
    # まず未探索ノードのうちdistanceが最小のものを選択する
  posible_min_distance = 10001 # 最小のdistanceを見つけるための一時的なdistance。初期値は inf に設定。
  for node_index in unsearched_nodes: # 未探索のノードのループ
    #print(node_index)
    if posible_min_distance > distance[node_index]: 
      posible_min_distance = distance[node_index] # より小さい値が見つかれば更新
      target_min_index = node_index
  #print(unsearched_nodes,target_min_index,distance)
  unsearched_nodes.remove(target_min_index) # ここで探索するので未探索リストから除去
	
  dh = [0,1]
  dw = [1,0]
  target_h = (target_min_index-1) // W + 1
  target_w = target_min_index % W
  if target_w == 0:
    target_w = W
  for i in range(2):
    h = target_h + dh[i]
    w = target_w + dw[i]
    ind = (h-1)*W+w
    route_dis = 0
    if S[h][w]=='*':
      continue
    if S[h][w]=='#':
      if S[target_h][target_w]=='.':
        route_dis = 1
    if distance[ind] > distance[target_min_index] + route_dis:
      distance[ind] = distance[target_min_index] + route_dis # 過去に設定されたdistanceよりも小さい場合はdistanceを更新
      previous_color[ind] =  S[target_h][target_w]
      
  #print(distance)
print(distance[-1])
#print(*ans, sep='\n')

Submission status: Accepted

Solution code:
import bisect
import collections
import sys

sys.setrecursionlimit(100000)
input = sys.stdin.readline
ACMOD = 1000000007
INF = 1 << 32


def lmi():
    return list(map(int, input().split()))


def llmi(n):
    return [lmi() for _ in range(n)]


H, W = lmi()
S = [input().strip() for _ in range(W)]

import functools


@functools.lru_cache(maxsize=None)
def solve(h, w, last_b=False):
    if h < 0 or w < 0:
        return INF
    if h == 0 and w == 0:
        return int(S[0][0] == '#') and (not last_b)
    b = bool(S[h][w] == '#')
    if b:
        return min(solve(h - 1, w, last_b=True) + (not last_b),
                   solve(h, w - 1, last_b=True) + (not last_b),
                   )
    return min(
        solve(h - 1, w, last_b=False),
        solve(h, w - 1, last_b=False),
        solve(h - 1, w, last_b=True) + 1,
        solve(h, w - 1, last_b=True) + 1,
        # solve(h - 1, w, last_b=False) + b,
        # solve(h, w - 1, last_b=False) + b,
    )


print(solve(H - 1, W - 1))

Submission status: Accepted

Solution code:
import copy
H, W = map(int, input().split())
fields = []


def black_white(x):
    if x == '.':  # 白ならば0
        return 0
    elif x == '#':
        return 1  # 黒ならば1


for i in range(H):
    fields.append(list(map(black_white, list(input()))))

DP_map = [[0 for i in range(W)] for j in range(H)]

if fields[0][0] == 1:
    DP_map[0][0] = 1
for h in range(H):
    for w in range(W):
        if h == 0 and w == 0:
            continue
        elif h == 0:
            if fields[h][w] - fields[h][w-1] == 1:
                DP_map[h][w] = DP_map[h][w-1] + 1
            else:
                DP_map[h][w] = DP_map[h][w-1]
            # 白から黒に変わった時だけプラス1点
        elif w == 0:
            if fields[h][w] - fields[h-1][w] == 1:
                DP_map[h][w] = DP_map[h-1][w] + 1
            else:
                DP_map[h][w] = DP_map[h-1][w]
        else:
            if fields[h][w] - fields[h][w-1] == 1:
                horizontal_cnt = DP_map[h][w-1] + 1
            else:
                horizontal_cnt = DP_map[h][w-1]
            if fields[h][w] - fields[h-1][w] == 1:
                vertical_cnt = DP_map[h-1][w] + 1
            else:
                vertical_cnt = DP_map[h-1][w]
            DP_map[h][w] = min(horizontal_cnt, vertical_cnt)
print(DP_map[H-1][W-1])

Submission status: Accepted

Solution code:
import sys
import heapq

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

def removeWalls(wallPointH,wallPointW):
  if maze[wallPointH][wallPointW]=="#":
    changeTo = "."
  elif maze[wallPointH][wallPointW]=="1":
    changeTo = "0"
  if maze[wallPointH][wallPointW]=="#" or maze[wallPointH][wallPointW]=="1":
    maze[wallPointH][wallPointW]=changeTo
    if wallPointH+1 <= H-1:
      removeWalls(wallPointH+1,wallPointW)
    if wallPointW+1 <= W-1:
      removeWalls(wallPointH,wallPointW+1)

if maze[0][0]=="#":
  flag=1
else:
  flag=0
      
que = [[flag,0,0]]
heapq.heapify(que)
count = 0
      
while que:
  qu = heapq.heappop(que)
  if qu[0]==1:
    heapq.heappush(que, qu)
    count += 1
    for q in que:#いったん"#"の撤去作業を行う
      q[0]=0
      removeWalls(q[1],q[2])
  else:#queの中身にまだ進める場所があるなら
    nowH = qu[1]
    nowW = qu[2]
    if nowH==H-1 and nowW==W-1:#ゴールの場合
      print(count)
      sys.exit()
    else:#それ以外の場合
      #右近傍と下近傍、それぞれマップの中ならqueに格納。
      if nowH+1 <= H-1:
        if maze[nowH+1][nowW]=="#":
          maze[nowH+1][nowW]="1"
          heapq.heappush(que, [1,nowH+1,nowW])
        elif maze[nowH+1][nowW]==".":
          maze[nowH+1][nowW]="0"
          heapq.heappush(que, [0,nowH+1,nowW])
      if nowW+1 <= W-1:
        if maze[nowH][nowW+1]=="#":
          maze[nowH][nowW+1]="1"
          heapq.heappush(que, [1,nowH,nowW+1])
        elif maze[nowH][nowW+1]==".":
          maze[nowH][nowW+1]="0"
          heapq.heappush(que, [0,nowH,nowW+1])