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
# Your code here!
# coding: utf-8
import sys
sys.setrecursionlimit(10000000)

#const
dxdy=((1,0),(0,1))
# my functions here!
def pin(type=int):
    return map(type,input().rstrip().split())
    

#絶対TLEする！A問題のpython回答はこちら！！！！

def sx(h,w,ans=0):#depth-first? search functionを障害物を消しながら行う
    from collections import deque as DQ
    q=DQ()
    q.append((h,w,ans,0))
    
    flag=0
    while (len(q) >0):
        temp=q.popleft()
        s,t,z,flag=temp
        
        if s>=H or t>=W:continue
        #print(maze[s][t])
        if maze[s][t]=="#":
            z+=1-flag
            flag=1
        elif maze[s][t]==".":
            flag=0
        #print((s,t,z))            
        if z<dp[s][t]:
            dp[s][t]=z
            for d in dxdy:
                q.append((s+d[0],t+d[1],z,flag))

def resolve():
    
    global anss ,dp,H,W,maze
    global res
    res=0
    H,W=pin()
    dp=[[(H+W)]*W for _ in range(H)]
    
    maze=tuple(tuple(input())for i in range(H))
    sx(0,0)
    #print(min(anss),len(anss),res)
    print(dp[H-1][W-1])
    

"""         
#printデバッグ消した？
#前の問題の結果見てないのに次の問題に行くの？
"""
"""
お前カッコ閉じるの忘れてるだろ
"""

import sys
from io import StringIO
import unittest


class TestClass(unittest.TestCase):
    def assertIO(self, input, output):
        stdout, stdin = sys.stdout, sys.stdin
        sys.stdout, sys.stdin = StringIO(), StringIO(input)
        resolve()
        sys.stdout.seek(0)
        out = sys.stdout.read()[:-1]
        sys.stdout, sys.stdin = stdout, stdin
        self.assertEqual(out, output)

    def test_入力例_1(self):
        input = """3 3
.##
.#.
##."""
        output = """1"""
        self.assertIO(input, output)

    def test_入力例_2(self):
        input = """2 2
#.
.#"""
        output = """2"""
        self.assertIO(input, output)

    def test_入力例_3(self):
        input = """4 4
..##
#...
###.
###."""
        output = """0"""
        self.assertIO(input, output)

    def test_入力例_4(self):
        input = """5 5
.#.#.
#.#.#
.#.#.
#.#.#
.#.#."""
        output = """4"""
        self.assertIO(input, output)
if __name__=="__main__":resolve()

Submission status: Accepted

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

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

for i in range(H):
    for j in range(W):
        if i>0:
            dp[i][j] = min(dp[i][j], dp[i-1][j] + (field[i-1][j]=='.' and field[i][j]=='#'))
        if j>0:
            dp[i][j] = min(dp[i][j], dp[i][j-1] + (field[i][j-1]=='.' and field[i][j]=='#'))
print(dp[H-1][W-1])

Submission status: Accepted

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

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

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

for h in range(H):
    for w in range(W):
        if h == 0:
            if w == 0:
                continue
            else:
                res[h][w] = res[h][w-1] + (1 if S[h][w] == '#' and S[h][w-1] == '.' else 0)
        else:
            if w == 0:
                res[h][w] = res[h-1][w] + (1 if S[h][w] == '#' and S[h-1][w] == '.' else 0)
            else:
                f_t = res[h-1][w] + (1 if S[h][w] == '#' and S[h-1][w] == '.' else 0)
                f_l = res[h][w-1] + (1if S[h][w] == '#' and S[h][w-1] == '.' else 0)
                res[h][w] = min(f_t, f_l)

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

Submission status: Accepted

Solution code:
from sys import stdin, setrecursionlimit
from collections import deque

setrecursionlimit(10 ** 9)

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

inf = 10 ** 9

flip_cnt = [[inf] * W for _ in range(H)]
direction = [[0, 1], [1, 0]]

q = deque([])


def bfs(h, w):
    q.append([h, w])

    while q:

        h, w = q.popleft()

        for dh, dw in direction:
            nh = h + dh
            nw = w + dw

            if nh >= H or nw >= W:
                continue

            if field[nh][nw] == field[h][w]:
                if flip_cnt[nh][nw] <= flip_cnt[h][w]:
                    continue
                else:
                    flip_cnt[nh][nw] = flip_cnt[h][w]
                    q.append([nh, nw])
            else:
                if flip_cnt[nh][nw] <= flip_cnt[h][w] + 1:
                    continue
                else:
                    flip_cnt[nh][nw] = flip_cnt[h][w] + 1
                    q.append([nh, nw])


flip_cnt[0][0] = 0
bfs(0, 0)

if field[0][0] == field[H - 1][W - 1] == "#":
    flip_cnt[H - 1][W - 1] += 1

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

# for f in flip_cnt:
#     print(f)

Submission status: Accepted

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

A = [[None for c in range(W)] for r in range(H)]
for i in range(H):
    line = input()
    for j in range(W):
        A[i][j] = 0 if line[j] == '.' else 1

D = [[0 for c in range(W)] for r in range(H)]
for i in range(H):
    for j in range(W):
        up_left = []
        if i >= 1:
            up_left.append([A[i-1][j], D[i-1][j]])
        if j >= 1:
            up_left.append([A[i][j-1], D[i][j-1]])
        if A[i][j] == 0:
            if not up_left:
                D[i][j] = 0
                continue
            D[i][j] = min(map(lambda x: x[1], up_left))
        else:
            if not up_left:
                D[i][j] = 1
                continue
            D[i][j] = min(map(lambda x: (1-x[0])+x[1], up_left))

print(D[-1][-1])

Submission status: Accepted

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

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

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

for h in range(H):
    for w in range(W):
        if h == 0:
            if w == 0:
                continue
            else:
                res[h][w] = res[h][w-1] + (1 if S[h][w] == '#' and S[h][w-1] == '.' else 0)
        else:
            if w == 0:
                res[h][w] = res[h-1][w] + (1 if S[h][w] == '#' and S[h-1][w] == '.' else 0)
            else:
                f_t = res[h-1][w] + 1 if S[h][w] == '#' and S[h-1][w] == '.' else res[h-1][w]
                f_l = res[h][w-1] + 1 if S[h][w] == '#' and S[h][w-1] == '.' else res[h][w-1]
                res[h][w] = min(f_t, f_l)

print(res[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)]

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

for y in range(1, h):
    dp[y][0] = dp[y-1][0]+1 if S[y][0]=='#' and S[y-1][0]=='.' else dp[y-1][0]

for x in range(1, w):
    dp[0][x] = dp[0][x-1]+1 if S[0][x]=='#' and S[0][x-1]=='.' else dp[0][x-1]

for y in range(1, h):
    for x in range(1, w):
        a = dp[y-1][x]+1 if S[y][x]=='#' and S[y-1][x]=='.' else dp[y-1][x]
        b = dp[y][x-1]+1 if S[y][x]=='#' and S[y][x-1]=='.' else dp[y][x-1]
        dp[y][x] = min(a,b)

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

Submission status: Accepted

Solution code:
from collections import deque
h, w =  map(int, input().split())
s = [[i for i in list(str(input()))] for i in range(h)]
INF = 10**9
dp = [[INF for _ in range(w)] for _ in range(h)]


if s[0][0] == "#":
    dp[0][0] = 1
else:
    dp[0][0] = 0
que = deque()
que.append((0, 0))
is_checked = [[False for _ in range(w)] for _ in range(h)]
while len(que) > 0:
    y, x = que.popleft()
    if y + 1 < h:
        if s[y][x] != s[y+1][x]:
            dp[y+1][x] = min(dp[y+1][x], dp[y][x]+1)
        else:
            dp[y+1][x] = min(dp[y+1][x], dp[y][x])
        if not is_checked[y+1][x]:
            que.append((y+1, x))
            is_checked[y+1][x] = True
    if x + 1 < w:
        if s[y][x] != s[y][x+1]:
            dp[y][x+1] = min(dp[y][x+1], dp[y][x]+1)
        else:
            dp[y][x+1] = min(dp[y][x+1], dp[y][x])
        if not is_checked[y][x+1]:
            que.append((y, x+1))
            is_checked[y][x+1] = True
if s[h-1][w-1] == "#":
    dp[h-1][w-1]+=1
print(dp[h-1][w-1]//2)

Submission status: Accepted

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

for i in range(1,h):
    if s[i][0]=="#" and s[i-1][0]==".":
        d[i][0]=d[i-1][0]+1
    else:
        d[i][0]=d[i-1][0]

for i in range(1,h):
    for j in range(1,w):
        if s[i][j]=="#" and s[i][j-1]==".":
            p=d[i][j-1]+1
        else:
            p=d[i][j-1]
        if s[i][j]=="#" and s[i-1][j]==".":
            q=d[i-1][j]+1
        else:
            q=d[i-1][j]
        d[i][j]=min(p,q)
# for i in d:
#     print(i)
print(d[-1][-1])

Submission status: Accepted

Solution code:
h,w=map(int,input().split())
l=[]
for i in range(h):
    l.append(list(input()))
dp=[[10**10 for j in range(w)] for i in range(h)]
if l[0][0]=='.':
    dp[0][0]=0
else:
    dp[0][0]=1
for i in range(h-1):
    if l[i][0]=='.' and l[i+1][0]=='#':
        dp[i+1][0]=dp[i][0]+1
    else:
        dp[i+1][0]=dp[i][0]
for i in range(w-1):
    if l[0][i]=='.' and l[0][i+1]=='#':
        dp[0][i+1]=dp[0][i]+1
    else:
        dp[0][i+1]=dp[0][i]       
for i in range(1,h):
    for j in range(1,w):
        a=dp[i-1][j]
        if l[i-1][j]+l[i][j]=='.#':
            a+=1
        b=dp[i][j-1]
        if l[i][j-1]+l[i][j]=='.#':
            b+=1
        dp[i][j]=min(a,b)
print(dp[h-1][w-1])

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
import sys
from collections import deque
sys.setrecursionlimit(10**9)
INF=10**18
MOD=10**9+7
def input(): return sys.stdin.readline().rstrip()

def main():
    H,W=map(int,input().split())
    s=[[] for _ in range(H+2)]
    s[0]=s[H+1]=[-1]*(W+2)
    for i in range(1,H+1):
        s[i]=[-1]+list(map(lambda s:int(s.replace('.','0').replace('#','1')),list(input())))+[-1]
        s[i]
    
    dp=[[INF]*(W+2) for _ in range(H+2)]
    dp[1][1]=s[1][1]
    for column in range(1,H+1):
        for row in range(1,W+1):
            if s[column-1][row]!=-1:
                if s[column][row]==s[column-1][row]+1:
                    dp[column][row]=min(dp[column][row],dp[column-1][row]+1)
                else:
                    dp[column][row]=min(dp[column][row],dp[column-1][row])
            if s[column][row-1]!=-1:
                if s[column][row]==s[column][row-1]+1:
                    dp[column][row]=min(dp[column][row],dp[column][row-1]+1)
                else:
                    dp[column][row]=min(dp[column][row],dp[column][row-1])
    print(dp[H][W])
            
    

if __name__ == '__main__':
    main()

Submission status: Accepted

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

p.append(["."] * (W + 1))
dp = [[10 ** 9] * (W + 1) for i in range(H + 1)]

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

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

        if p[i][j + 1] == ".":
            dp[i][j + 1] = min(dp[i][j], dp[i][j + 1])
        elif p[i][j] == "#":
            dp[i][j + 1] = min(dp[i][j], dp[i][j + 1])
        else:
            dp[i][j + 1] = min(dp[i][j] + 1, dp[i][j + 1])

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

Submission status: Accepted

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

for i in range(h):
    field.append(list(input()))

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

for i in range(1, w):
    if field[0][i - 1] == field[0][i]:
        dp[0][i] = dp[0][i - 1] 

    else:
        if field[0][i - 1] == "." and field[0][i] == "#":
            dp[0][i] = dp[0][i - 1] + 1
        else:
            dp[0][i] = dp[0][i - 1]

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

for y in range(1, h):
    for x in range(1, w):
        dp[y][x] = min(dp[y - 1][x] + (1 if field[y][x] != field[y - 1][x] and field[y - 1][x] == "." else 0), dp[y][x - 1] + (1 if field[y][x] != field[y][x - 1] and field[y][x - 1] == "."  else 0))

print(dp[h - 1][w - 1] + (1 if field[0][0] == "#" else 0))

Submission status: Accepted

Solution code:
from heapq import*
def main():
  h,w=map(int,input().split())
  s=[input()for _ in range(h)]
  g=h*w+1
  e=[[]for _ in range(g)]
  for i in range(h):
    for j in range(w):
      for y,x in((i+1,j),(i,j+1)):
        if y<h and x<w:
          if s[i][j]=='.'and s[y][x]!='.':
            e[i*w+j]+=(1,y*w+x),
          else:
            e[i*w+j]+=(0,y*w+x),
  e[g-1]+=(s[0][0]!='.',0),
  q=[g-1]
  d=[10**12]*g
  while q:
    c=heappop(q)
    c,v=c//g,c%g
    if c>d[v]:continue
    d[v]=c
    for x,w in e[v]:
      x+=c
      if d[w]>x:
        d[w]=x
        heappush(q,x*g+w)
  print(d[g-2])
main()

Submission status: Accepted

Solution code:
# import numpy as np
# import math
# import copy
from collections import deque
import sys
input = sys.stdin.readline
# sys.setrecursionlimit(10000)


def main():
    H,W = map(int,input().split())
    s = [ input().rstrip() for _ in range(H) ]

    INF = 10 ** 9 + 7

    dp = [ [ INF for i in range(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 i != 0:
                if (s[i][j] == '#') & (s[i-1][j] == '.'):
                    cost = 1
                else:
                    cost = 0
                dp[i][j] = min(dp[i][j],dp[i-1][j] + cost)
            if j != 0:
                if (s[i][j] == '#') & (s[i][j-1] == '.'):
                    cost = 1
                else:
                    cost = 0
                dp[i][j] = min(dp[i][j],dp[i][j-1] + cost)

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



main()

Submission status: Accepted

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

dp = [[float('inf')]*(W+1)] + [[float('inf')] + [0]*W for h in range(H)]
dp[0][1] = dp[1][0] = 0
for h in range(1, H+1):
  for w in range(1, W+1):
    if S[h][w] == '.':
      dp[h][w] = min(dp[h][w-1], dp[h-1][w])
    else:
      if S[h][w-1] == S[h-1][w] == '.':
        dp[h][w] = min(dp[h-1][w], dp[h][w-1]) + 1
      elif S[h][w-1] == '#' and S[h-1][w] == '.':
        dp[h][w] = min(dp[h][w-1], dp[h-1][w]+1)
      elif S[h][w-1] == '.' and S[h-1][w] == '#':
        dp[h][w] = min(dp[h][w-1]+1, dp[h-1][w])
      else:
        dp[h][w] = min(dp[h][w-1], dp[h-1][w])

print(dp[H][W])

Submission status: Accepted

Solution code:
# 新しいvalueのほうが小さい場合のみ設定
def set_val(map, x, y, value):
    key = str(x) + " " + str(y)
    if key in map:
        if value < map[key]:
            map[key] = value
    else:
        map[key] = value
    return map


size_x, size_y = map(int, input().split())
count = size_x + size_y
temp_values = []

for i in range(size_x):
    temp_values.append(input())

values = []
for value in temp_values:
    values.append(list(value))

initial = 0
yet = True
all_same = True
if values[0][0] == "#":
    initial = 1

check_value = {"0 0": initial}
# 探索処理
for i in range(count):
    check_temp_value = {}
    for key in check_value.keys():
        x, y = map(int, key.split())
        value = check_value.get(key)
        # 下に移動
        if x + 1 <= size_x - 1:
            if values[x + 1][y] == "#" and values[x][y] == ".":
                # 異なる経路で同一座標に到達した場合、小さいほうの値を設定
                check_temp_value = set_val(check_temp_value, x + 1, y, value + 1)
                yet = False
                all_same = False
            else:
                check_temp_value = set_val(check_temp_value, x + 1, y, value)
        # 右に移動
        if y + 1 <= size_y - 1:
            if values[x][y + 1] == "#" and values[x][y] == ".":
                # 異なる経路で同一座標に到達した場合、小さいほうの値を設定
                check_temp_value = set_val(check_temp_value, x, y + 1, value + 1)
                yet = False
                all_same = False
            else:
                check_temp_value = set_val(check_temp_value, x, y + 1, value)
    check_value = check_temp_value
    if len(check_value) == 1:
        # ゴールについたら終了
        break
    yet = True

# すべて同じなら無条件に初期値
if all_same:
    print(initial)
else:
    # 最後が#なら加算
    result_val_add = 0
    if values[size_x - 1][size_y - 1] == "#" and yet :
        result_val_add = 1
    print(list(check_value.values())[0] + result_val_add)

Submission status: Accepted

Solution code:
# Author: cr4zjh0bp
# Created: Fri Mar 20 22:48:43 UTC 2020
import sys
 
stdin = sys.stdin
inf = 1 << 60
mod = 1000000007
 
ni      = lambda: int(ns())
nin     = lambda y: [ni() for _ in range(y)]
na      = lambda: list(map(int, stdin.readline().split()))
nan     = lambda y: [na() for _ in range(y)]
nf      = lambda: float(ns())
nfn     = lambda y: [nf() for _ in range(y)]
nfa     = lambda: list(map(float, stdin.readline().split()))
nfan    = lambda y: [nfa() for _ in range(y)]
ns      = lambda: stdin.readline().rstrip()
nsn     = lambda y: [ns() for _ in range(y)]
ncl     = lambda y: [list(ns()) for _ in range(y)]
nas     = lambda: stdin.readline().split()

from collections import deque

h, w = na()
m = nsn(h)

def bfs():
    q = deque()
    al = 0
    f = False
    if m[0][0] == '#':
        al += 1
        f = True
    q.append((0, 0, al, f))
    d = [[inf] * w for _ in range(h)]
    res = inf
    dx, dy = [0, 1], [1, 0]
    while len(q):
        p = q.popleft()
        x, y, l, flag = p
        for i in range(2):
            nx, ny = x + dx[i], y + dy[i]
            nl = l
            if nx >= 0 and nx < w and ny >= 0 and ny < h and d[ny][nx] > nl:
                if m[ny][nx] == '#':
                    if not flag:
                        nl += 1
                    q.append((nx, ny, nl, True))
                else:
                    q.append((nx, ny, nl, False))
                d[ny][nx] = min(d[ny][nx], nl)
    return d[h - 1][w - 1]

print(bfs())

Submission status: Accepted

Solution code:
# 新しいvalueのほうが小さい場合のみ設定
def set_val(map, x, y, value):
    key = str(x) + " " + str(y)
    if key in map:
        if value < map[key]:
            map[key] = value
    else:
        map[key] = value
    return map


size_x, size_y = map(int, input().split())
count = size_x + size_y
temp_values = []

for i in range(size_x):
    temp_values.append(input())

values = []
for value in temp_values:
    values.append(list(value))

initial = 0
yet = True
all_black = True
if values[0][0] == "#":
    initial = 1

check_value = {"0 0": initial}
# 探索処理
for i in range(count):
    check_temp_value = {}
    for key in check_value.keys():
        x, y = map(int, key.split())
        value = check_value.get(key)
        # 下に移動
        if x + 1 <= size_x - 1:
            if values[x + 1][y] == "#" and values[x][y] == ".":
                # 異なる経路で同一座標に到達した場合、小さいほうの値を設定
                check_temp_value = set_val(check_temp_value, x + 1, y, value + 1)
                yet = False
                all_black = False
            else:
                check_temp_value = set_val(check_temp_value, x + 1, y, value)
        # 右に移動
        if y + 1 <= size_y - 1:
            if values[x][y + 1] == "#" and values[x][y] == ".":
                # 異なる経路で同一座標に到達した場合、小さいほうの値を設定
                check_temp_value = set_val(check_temp_value, x, y + 1, value + 1)
                yet = False
                all_black = False
            else:
                check_temp_value = set_val(check_temp_value, x, y + 1, value)
    check_value = check_temp_value
    if len(check_value) == 1:
        # ゴールについたら終了
        break
    yet = True

# すべて黒なら無条件に1
if all_black:
    print(1)
else:
    # 最後が#なら加算
    result_val_add = 0
    if values[size_x - 1][size_y - 1] == "#" and yet :
        result_val_add = 1
    print(list(check_value.values())[0] + result_val_add)

Submission status: Accepted

Solution code:
import heapq
import sys

# スペース区切りの入力を読み込んで数値リストにして返します。
def get_nums_l():
    return [ int(s) for s in input().split(" ")]

def log(*args):
    print("DEBUG:", *args, file=sys.stderr)

h,w = get_nums_l()
grid = [ input() for _ in range(h) ]
dp = [ [99999999999999999999] * w for _ in range(h)]

def bfs(cost, x, y):
    # log(cost, y, x)
    if dp[y][x] <= cost:
        return

    dp[y][x] = cost

    if x < w-1:
        if grid[y][x] == "." and grid[y][x+1] == "#":
            heapq.heappush(heap, (cost+1, x+1, y))
        else:
            heapq.heappush(heap, (cost, x+1, y))

    if y < h-1:
        if grid[y][x] =="." and grid[y+1][x] == "#":
            heapq.heappush(heap, (cost+1, x, y+1))
        else:
            heapq.heappush(heap, (cost, x, y+1))

heap = []

if grid[0][0] == ".":
    heapq.heappush(heap, (0,0,0))
else:
    heapq.heappush(heap, (1,0,0))

while heap:
    cost, x, y = heapq.heappop(heap)
    bfs(cost, x, y)

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

Submission status: Accepted

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

grid_state = []

# 1 = black, 0 = white

for _ in range(h):
    temp = [int(s) for s in input().replace(".", "0").replace("#", "1")]
    grid_state.append(temp)

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

grid_cost[0][0] = grid_state[0][0]

for i in range(1, h + w - 1):
    j = i
    if j > w - 1:
        j = w - 1
    while((j >= 0) and (i - j < h)):
        if i - j == 0:
            if grid_state[i - j][j - 1] == 1:
                grid_cost[i - j][j] = grid_cost[i - j][j - 1]
            else:
                grid_cost[i - j][j] = grid_cost[i - j][j - 1] + grid_state[i - j][j]
        elif j == 0:
            if grid_state[i - j - 1][j] == 1:
                grid_cost[i - j][j] = grid_cost[i - j - 1][j]
            else:
                grid_cost[i - j][j] = grid_cost[i - j - 1][j] + grid_state[i - j][j]
        else:
            min_cost = min([grid_cost[i - j - 1][j], grid_cost[i - j][j - 1]])

            if grid_state[i - j][j] == 0:
                grid_cost[i - j][j] = min([grid_cost[i - j - 1][j], grid_cost[i - j][j - 1]])
            elif (grid_state[i - j - 1][j] == 1) and (grid_cost[i - j - 1][j] <= grid_cost[i - j][j - 1]):
                grid_cost[i - j][j] = min_cost
            elif (grid_state[i - j - 1][j] == 0) and (grid_cost[i - j - 1][j] < grid_cost[i - j][j - 1]):
                grid_cost[i - j][j] = min_cost + 1
            elif (grid_state[i - j][j - 1] == 1) and (grid_cost[i - j - 1][j] >= grid_cost[i - j][j - 1]):
                grid_cost[i - j][j] = min_cost
            else:
                grid_cost[i - j][j] = min_cost + 1

        j -= 1

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

Submission status: Accepted

Solution code:
import math
from functools import reduce
from collections import deque
import heapq
import sys
sys.setrecursionlimit(10**7)

# スペース区切りの入力を読み込んで数値リストにして返します。
def get_nums_l():
    return [ int(s) for s in input().split(" ")]

# 改行区切りの入力をn行読み込んで数値リストにして返します。
def get_nums_n(n):
    return [ int(input()) for _ in range(n)]

# 改行またはスペース区切りの入力をすべて読み込んでイテレータを返します。
def get_all_int():
    return map(int, open(0).read().split())

def log(*args):
    print("DEBUG:", *args, file=sys.stderr)

h,w = get_nums_l()
grid = [ input() for _ in range(h) ]
dp = [ [99999999999999999999] * w for _ in range(h)]

def bfs(cost, x, y):
    log(cost, y, x)
    if dp[y][x] <= cost:
        return

    dp[y][x] = cost

    if x < w-1:
        if grid[y][x] == "." and grid[y][x+1] == "#":
            heapq.heappush(heap, (cost+1, x+1, y))
        else:
            heapq.heappush(heap, (cost, x+1, y))

    if y < h-1:
        if grid[y][x] =="." and grid[y+1][x] == "#":
            heapq.heappush(heap, (cost+1, x, y+1))
        else:
            heapq.heappush(heap, (cost, x, y+1))

heap = []

if grid[0][0] == ".":
    heapq.heappush(heap, (0,0,0))
else:
    heapq.heappush(heap, (1,0,0))

while heap:
    cost, x, y = heapq.heappop(heap)
    bfs(cost, x, y)

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

Submission status: Accepted

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

dp = [[float('inf')]*(W+1)] + [[float('inf')] + [0]*W for h in range(H)]
for h in range(1, H+1):
  for w in range(1, W+1):
    if h*w == 1:
      if S[h][w] == '#':
        dp[h][w] = 1
      continue
    if S[h][w] == '.':
      dp[h][w] = min(dp[h][w-1], dp[h-1][w])
    else:
      if S[h][w-1] == S[h-1][w] == '.':
        dp[h][w] = min(dp[h-1][w], dp[h][w-1]) + 1
      elif S[h][w-1] == '#' and S[h-1][w] == '.':
        dp[h][w] = min(dp[h][w-1], dp[h-1][w]+1)
      elif S[h][w-1] == '.' and S[h-1][w] == '#':
        dp[h][w] = min(dp[h][w-1]+1, dp[h-1][w])
      else:
        dp[h][w] = min(dp[h][w-1], dp[h-1][w])

print(dp[H][W])

Submission status: Accepted

Solution code:
import numpy as np

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

M = np.array([[ (0 if s[i][j] == '.' else 1) for j in range(W) ] for i in range(H)])
INF = 10 ** 9
dp = np.array([[INF for j in range(W)] for i in range(H)])

for i in range(H - 1, -1, -1):
    for j in range(W - 1, -1, -1):
        ans_r = INF
        ans_d = INF
        if i == H - 1 and j == W - 1:
            dp[i][j] = M[i][j]
            continue
        if j < W - 1:  # 右に動ける
            if M[i][j] == 1 and M[i][j + 1] == 0:
                ans_r = dp[i][j + 1] + 1
            else:
                ans_r = dp[i][j + 1]
        if i < H - 1:  # 下に動ける
            if M[i][j] == 1 and M[i + 1][j] == 0:
                ans_d = dp[i + 1][j] + 1
            else:
                ans_d = dp[i + 1][j]
        dp[i][j] = min(ans_r, ans_d)

print(dp[0][0])

Submission status: Accepted

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

dp=[]
blacks=[]
whites=[]
black=0
white=0
#DP=[]
#print(s)

for h in range(H):
    dp.append([0]*W)
    #DP.append([0]*W)
    for w in range(W):
        #print(s[h][w],dp[h][w])
        if s[h][w]==".":
            if h!=0 and w==0:
                dp[h][w]=dp[h-1][w]
                #DP[h][w]=DP[h-1][w]+1
            elif h==0 and w!=0:
                dp[h][w]=dp[h][w-1]
                #DP[h][w]=DP[h][w-1]+1
            elif h==0 and w==0:
                dp[h][w]=0
                #DP[h][w]=1
            else:
                dp[h][w]=min(dp[h-1][w],dp[h][w-1])
                #DP[h][w]=min(DP[h-1][w],DP[h][w-1])+1
        else:
            if h!=0 and w==0:
                if s[h-1][w]=="#":
                    dp[h][w]=dp[h-1][w]
                else:
                    dp[h][w]=dp[h-1][w]+1
                #DP[h][w]=DP[h-1][w]
            elif h==0 and w!=0:
                if s[h][w-1]=="#":
                    dp[h][w]=dp[h][w-1]
                else:
                    dp[h][w]=dp[h][w-1]+1
                #DP[h][w]=DP[h][w-1]
            elif h==0 and w==0:
                dp[0][0]=1
                #DP[0][0]=0
            else:
                if s[h-1][w]=="." and s[h][w-1]=="#":
                    dp[h][w]=min(dp[h-1][w]+1,dp[h][w-1])
                elif s[h-1][w]=="#" and s[h][w-1]==".":
                    dp[h][w]=min(dp[h-1][w],dp[h][w-1]+1)
                elif s[h-1][w]=="#" and s[h][w-1]=="#":
                    dp[h][w]=min(dp[h-1][w],dp[h][w-1])
                elif s[h-1][w]=="." and s[h][w-1]==".":
                    dp[h][w]=min(dp[h-1][w]+1,dp[h][w-1]+1)
        #print(dp)
                
print(dp[H-1][W-1])

Submission status: Accepted

Solution code:
from collections import deque

INF = float("inf")

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

dp = [[INF] * W for _ in range(H)]
dp[0][0] = int(S[0][0] == "#")

Q = deque([(dp[0][0], 0, 0)])
while Q:
    cur, i, j = Q.popleft()
    for ni, nj in [(i + 1, j), (i, j + 1)]:
        if H <= ni or W <= nj:
            continue

        c = int(S[i][j] != S[ni][nj])
        if dp[ni][nj] > cur + c:
            dp[ni][nj] = cur + c
            Q.append((cur + c, ni, nj))

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

Submission status: Accepted

Solution code:
import itertools
h, w = map(int, input().split())
map_lst = []
for i in range(h):
    map_lst.append(list(input()))
dp = [[200] * (w) for i in range(h)]
if map_lst[0][0] == '.': dp[0][0] = 0
else: dp[0][0] = 1
# for i in dp:
#     print(i)
for c in range(w):
    for r in range(h):
        over = 0
        left = 0
        if r > 0:
            if map_lst[r-1][c] == '.' and map_lst[r][c] == '#':
                over = 1
        if c > 0:
            if map_lst[r][c-1] == '.' and map_lst[r][c] == '#':
                left = 1
        if r == 0 and c == 0:
            continue
        elif r == 0:
            dp[r][c] = dp[r][c-1] + left
        elif c == 0:
            dp[r][c] = dp[r-1][c] + over
        else:
            dp[r][c] = min(dp[r-1][c] + over, dp[r][c-1] + left)
# for i in dp:
#     print(i)
print(dp[-1][-1])