Problem:


Score : 400 points

Problem Statement

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

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

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

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

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

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

Constraints

2 \leq H, W \leq 100

Input

Input is given from Standard Input in the following format:

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

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

Output

Print the minimum number of operations needed.

Sample Input 1

3 3
.##
.#.
##.

Sample Output 1

1

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

Sample Input 2

2 2
#.
.#

Sample Output 2

2

Sample Input 3

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

Sample Output 3

0

No operation may be needed.

Sample Input 4

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

Sample Output 4

4



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


Sample output:
1

Submission status: Accepted

Solution code:
from heapq import heappush,heappop,heapify
from collections import deque,defaultdict,Counter
from itertools import permutations,combinations,groupby
import sys,bisect,string,math,time,functools,random
def Golf():*a,=map(int,open(0))
def I():return int(input())
def S_():return input()
def IS():return input().split()
def LS():return [i for i in input().split()]
def LI():return [int(i) for i in input().split()]
def LI_():return [int(i)-1 for i in input().split()]
def NI(n):return [int(input()) for i in range(n)]
def NI_(n):return [int(input())-1 for i in range(n)]
def StoLI():return [ord(i)-97 for i in input()]
def ItoS(n):return chr(n+97)
def LtoS(ls):return ''.join([chr(i+97) for i in ls])
def GI(V,E,Directed=False,index=0):
    org_inp=[];g=[[] for i in range(n)]
    for i in range(E):
        inp=LI();org_inp.append(inp)
        if index==0:inp[0]-=1;inp[1]-=1
        if len(inp)==2:
            a,b=inp;g[a].append(b)
            if not Directed:g[b].append(a)
        elif len(inp)==3:
            a,b,c=inp;aa=(inp[0],inp[2]);bb=(inp[1],inp[2]);g[a].append(bb)
            if not Directed:g[b].append(aa)
    return g,org_inp
def GGI(h,w,search=[],replacement_of_found='.',mp_def={'#':1,'.':0}):
#h,w,g,sg=GGI(h,w,search=['S','G'],replacement_of_found='.',mp_def={'#':1,'.':0}) # sample usage
    mp=[1]*(w+2);found={}
    for i in range(h):
        s=input()
        for char in search:
            if char in s:
                found[char]=((i+1)*(w+2)+s.index(char)+1)
                mp_def[char]=mp_def[replacement_of_found]
        mp+=[1]+[mp_def[j] for j in s]+[1]
    mp+=[1]*(w+2)
    return h+2,w+2,mp,found
def TI(n):return GI(n,n-1)
def bit_combination(k,n=2):return [[tb//(n**bt)%n for bt in range(k)] for tb in range(n**k)]
def show(*inp,end='\n'):
    if show_flg:print(*inp,end=end)

YN=['YES','NO'];Yn=['Yes','No']
mo=10**9+7
inf=float('inf')
l_alp=string.ascii_lowercase
#sys.setrecursionlimit(10**7)
input=lambda: sys.stdin.readline().rstrip()

def ran_input():
    n=random.randint(4,16)
    rmin,rmax=1,10
    a=[random.randint(rmin,rmax) for _ in range(n)]
    return n,a

show_flg=False
show_flg=True

h,w=LI()
h,w,g,sg=GGI(h,w)
dp=[1e6]*(h*w)
dp[w+1]=g[w+1]

for j in range(h*w-w):
  for d in (1,w):
    dp[j+d]=min(dp[j]+1 if (g[j],g[j+d])==(0,1) else dp[j],dp[j+d])

print(dp[(h-2)*w+w-2])

Submission status: Accepted

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

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

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

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

for h in range(1, H):
    for w in range(1, W):
        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-1][W-1])

Submission status: Accepted

Solution code:
from heapq import heappush,heappop,heapify
from collections import deque,defaultdict,Counter
from itertools import permutations,combinations,groupby
import sys,bisect,string,math,time,functools,random
def Golf():*a,=map(int,open(0))
def I():return int(input())
def S_():return input()
def IS():return input().split()
def LS():return [i for i in input().split()]
def LI():return [int(i) for i in input().split()]
def LI_():return [int(i)-1 for i in input().split()]
def NI(n):return [int(input()) for i in range(n)]
def NI_(n):return [int(input())-1 for i in range(n)]
def StoLI():return [ord(i)-97 for i in input()]
def ItoS(n):return chr(n+97)
def LtoS(ls):return ''.join([chr(i+97) for i in ls])
def GI(V,E,Directed=False,index=0):
    org_inp=[];g=[[] for i in range(n)]
    for i in range(E):
        inp=LI();org_inp.append(inp)
        if index==0:inp[0]-=1;inp[1]-=1
        if len(inp)==2:
            a,b=inp;g[a].append(b)
            if not Directed:g[b].append(a)
        elif len(inp)==3:
            a,b,c=inp;aa=(inp[0],inp[2]);bb=(inp[1],inp[2]);g[a].append(bb)
            if not Directed:g[b].append(aa)
    return g,org_inp
def GGI(h,w,search=None,replacement_of_found='.',mp_def={'#':1,'.':0}):
#h,w,g,sg=GGI(h,w,search=['S','G'],replacement_of_found='.',mp_def={'#':1,'.':0}) # sample usage
    mp=[1]*(w+2);found={}
    for i in range(h):
        s=input()
        for char in search:
            if char in s:
                found[char]=((i+1)*(w+2)+s.index(char)+1)
                mp_def[char]=mp_def[replacement_of_found]
        mp+=[1]+[mp_def[j] for j in s]+[1]
    mp+=[1]*(w+2)
    return h+2,w+2,mp,found
def TI(n):return GI(n,n-1)
def bit_combination(k,n=2):return [[tb//(n**bt)%n for bt in range(k)] for tb in range(n**k)]
def show(*inp,end='\n'):
    if show_flg:print(*inp,end=end)

YN=['YES','NO'];Yn=['Yes','No']
mo=10**9+7
inf=float('inf')
l_alp=string.ascii_lowercase
#sys.setrecursionlimit(10**7)
input=lambda: sys.stdin.readline().rstrip()

def ran_input():
    n=random.randint(4,16)
    rmin,rmax=1,10
    a=[random.randint(rmin,rmax) for _ in range(n)]
    return n,a

show_flg=False
show_flg=True

h,w=LI()
h,w,g,sg=GGI(h,w,search=['S','G'])
dp=[1e6]*(h*w)
dp[w+1]=g[w+1]

for j in range(h*w-w):
  for d in (1,w):
    dp[j+d]=min(dp[j]+1 if (g[j],g[j+d])==(0,1) else dp[j],dp[j+d])

print(dp[(h-2)*w+w-2])

Submission status: Accepted

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

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

Submission status: Accepted

Solution code:
from heapq import heappush,heappop,heapify
from collections import deque,defaultdict,Counter
from itertools import permutations,combinations,groupby
import sys,bisect,string,math,time,functools,random
def Golf():*a,=map(int,open(0))
def I():return int(input())
def S_():return input()
def IS():return input().split()
def LS():return [i for i in input().split()]
def LI():return [int(i) for i in input().split()]
def LI_():return [int(i)-1 for i in input().split()]
def NI(n):return [int(input()) for i in range(n)]
def NI_(n):return [int(input())-1 for i in range(n)]
def StoLI():return [ord(i)-97 for i in input()]
def ItoS(n):return chr(n+97)
def LtoS(ls):return ''.join([chr(i+97) for i in ls])
def GI(V,E,Directed=False,index=0):
    org_inp=[];g=[[] for i in range(n)]
    for i in range(E):
        inp=LI();org_inp.append(inp)
        if index==0:inp[0]-=1;inp[1]-=1
        if len(inp)==2:
            a,b=inp;g[a].append(b)
            if not Directed:g[b].append(a)
        elif len(inp)==3:
            a,b,c=inp;aa=(inp[0],inp[2]);bb=(inp[1],inp[2]);g[a].append(bb)
            if not Directed:g[b].append(aa)
    return g,org_inp
def GGI(h,w,search=None,replacement_of_found='.',mp_def={'#':1,'.':0}):
#h,w,g,sg=GGI(h,w,search=['S','G'],replacement_of_found='.',mp_def={'#':1,'.':0}) # sample usage
    mp=[1]*(w+2);found={}
    for i in range(h):
        s=input()
        for char in search:
            if char in s:
                found[char]=((i+1)*(w+2)+s.index(char)+1)
                mp_def[char]=mp_def[replacement_of_found]
        mp+=[1]+[mp_def[j] for j in s]+[1]
    mp+=[1]*(w+2)
    return h+2,w+2,mp,found
def TI(n):return GI(n,n-1)
def bit_combination(k,n=2):return [[tb//(n**bt)%n for bt in range(k)] for tb in range(n**k)]
def show(*inp,end='\n'):
    if show_flg:print(*inp,end=end)

YN=['YES','NO'];Yn=['Yes','No']
mo=10**9+7
inf=float('inf')
l_alp=string.ascii_lowercase
#sys.setrecursionlimit(10**7)
input=lambda: sys.stdin.readline().rstrip()

def ran_input():
    n=random.randint(4,16)
    rmin,rmax=1,10
    a=[random.randint(rmin,rmax) for _ in range(n)]
    return n,a

show_flg=False
show_flg=True

h,w=LI()
h,w,g,sg=GGI(h,w,search=['S','G'],replacement_of_found='.',mp_def={'#':1,'.':0})
dp=[1e6]*(h*w)
dp[w+1]=g[w+1]

for j in range(h*w-w):
  for d in (1,w):
    dp[j+d]=min(dp[j]+1 if (g[j],g[j+d])==(0,1) else dp[j],dp[j+d])

print(dp[(h-2)*w+w-2])

Submission status: Accepted

Solution code:
from heapq import heappush,heappop,heapify
from collections import deque,defaultdict,Counter
from itertools import permutations,combinations,groupby
import sys,bisect,string,math,time,functools,random
def Golf():*a,=map(int,open(0))
def I():return int(input())
def S_():return input()
def IS():return input().split()
def LS():return [i for i in input().split()]
def LI():return [int(i) for i in input().split()]
def LI_():return [int(i)-1 for i in input().split()]
def NI(n):return [int(input()) for i in range(n)]
def NI_(n):return [int(input())-1 for i in range(n)]
def StoLI():return [ord(i)-97 for i in input()]
def ItoS(n):return chr(n+97)
def LtoS(ls):return ''.join([chr(i+97) for i in ls])
def GI(V,E,Directed=False,index=0):
    org_inp=[];g=[[] for i in range(n)]
    for i in range(E):
        inp=LI();org_inp.append(inp)
        if index==0:inp[0]-=1;inp[1]-=1
        if len(inp)==2:
            a,b=inp;g[a].append(b)
            if not Directed:g[b].append(a)
        elif len(inp)==3:
            a,b,c=inp;aa=(inp[0],inp[2]);bb=(inp[1],inp[2]);g[a].append(bb)
            if not Directed:g[b].append(aa)
    return g,org_inp
def GGI(h,w,search=None,replacement_of_found='.',mp_def={'#':1,'.':0}):
#h,w,g,sg=GGI(h,w,search=['S','G'],replacement_of_found='.',mp_def={'#':1,'.':0}) # sample usage
    mp=[1]*(w+2);found={}
    for i in range(h):
        s=input()
        for char in search:
            if char in s:
                found[char]=((i+1)*(w+2)+s.index(char)+1)
                mp_def[char]=mp_def[replacement_of_found]
        mp+=[1]+[mp_def[j] for j in s]+[1]
    mp+=[1]*(w+2)
    return h+2,w+2,mp,found
def TI(n):return GI(n,n-1)
def bit_combination(k,n=2):return [[tb//(n**bt)%n for bt in range(k)] for tb in range(n**k)]
def show(*inp,end='\n'):
    if show_flg:print(*inp,end=end)

YN=['YES','NO'];Yn=['Yes','No']
mo=10**9+7
inf=float('inf')
l_alp=string.ascii_lowercase
#sys.setrecursionlimit(10**7)
input=lambda: sys.stdin.readline().rstrip()

def ran_input():
    n=random.randint(4,16)
    rmin,rmax=1,10
    a=[random.randint(rmin,rmax) for _ in range(n)]
    return n,a

show_flg=False
show_flg=True

h,w=LI()
h,w,g,sg=GGI(h,w,search=['S','G'],replacement_of_found='.',mp_def={'#':1,'.':0})
dp=[1e6]*(h*w)
dp[w+1]=g[w+1]

for j in range(h*w-w):
        dp[j+1]=min(dp[j]+1 if (g[j],g[j+1])==(0,1) else dp[j],dp[j+1])
        dp[j+w]=min(dp[j]+1 if (g[j],g[j+w])==(0,1) else dp[j],dp[j+w])

print(dp[(h-2)*w+w-2])

Submission status: Accepted

Solution code:
from heapq import heappush,heappop,heapify
from collections import deque,defaultdict,Counter
from itertools import permutations,combinations,groupby
import sys,bisect,string,math,time,functools,random
def Golf():*a,=map(int,open(0))
def I():return int(input())
def S_():return input()
def IS():return input().split()
def LS():return [i for i in input().split()]
def LI():return [int(i) for i in input().split()]
def LI_():return [int(i)-1 for i in input().split()]
def NI(n):return [int(input()) for i in range(n)]
def NI_(n):return [int(input())-1 for i in range(n)]
def StoLI():return [ord(i)-97 for i in input()]
def ItoS(n):return chr(n+97)
def LtoS(ls):return ''.join([chr(i+97) for i in ls])
def GI(V,E,Directed=False,index=0):
    org_inp=[];g=[[] for i in range(n)]
    for i in range(E):
        inp=LI();org_inp.append(inp)
        if index==0:inp[0]-=1;inp[1]-=1
        if len(inp)==2:
            a,b=inp;g[a].append(b)
            if not Directed:g[b].append(a)
        elif len(inp)==3:
            a,b,c=inp;aa=(inp[0],inp[2]);bb=(inp[1],inp[2]);g[a].append(bb)
            if not Directed:g[b].append(aa)
    return g,org_inp
def GGI(h,w,search=None,replacement_of_found='.',mp_def={'#':1,'.':0}):
#h,w,g,sg=GGI(h,w,search=['S','G'],replacement_of_found='.',mp_def={'#':1,'.':0}) # sample usage
    mp=[1]*(w+2);found={}
    for i in range(h):
        s=input()
        for char in search:
            if char in s:
                found[char]=((i+1)*(w+2)+s.index(char)+1)
                mp_def[char]=mp_def[replacement_of_found]
        mp+=[1]+[mp_def[j] for j in s]+[1]
    mp+=[1]*(w+2)
    return h+2,w+2,mp,found
def TI(n):return GI(n,n-1)
def bit_combination(k,n=2):return [[tb//(n**bt)%n for bt in range(k)] for tb in range(n**k)]
def show(*inp,end='\n'):
    if show_flg:print(*inp,end=end)

YN=['YES','NO'];Yn=['Yes','No']
mo=10**9+7
inf=float('inf')
l_alp=string.ascii_lowercase
#sys.setrecursionlimit(10**7)
input=lambda: sys.stdin.readline().rstrip()

def ran_input():
    n=random.randint(4,16)
    rmin,rmax=1,10
    a=[random.randint(rmin,rmax) for _ in range(n)]
    return n,a

show_flg=False
show_flg=True

h,w=LI()
h,w,g,sg=GGI(h,w,search=['S','G'],replacement_of_found='.',mp_def={'#':1,'.':0})
dp=[1e6]*(h*w)
dp[w+1]=g[w+1]

for r in range(1,h-1):
    for c in range(1,w-1):
        j=r*w+c
        dp[j+1]=min(dp[j]+1 if (g[j],g[j+1])==(0,1) else dp[j],dp[j+1])
        dp[j+w]=min(dp[j]+1 if (g[j],g[j+w])==(0,1) else dp[j],dp[j+w])

print(dp[(h-2)*w+w-2])

Submission status: Accepted

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

H,W=map(int,readline().split())
grid=[None]*H
for i in range(H):
  grid[i]=readline().rstrip()

INF=10**10
dp=[[INF for i in range(W)] for j in range(H)]
curwhite=True

# 下もしくは右に進み、白から黒に行ったら反転数を+1する
# 自分より大きい値だったら上書きする

from collections import deque
q=deque()
# h,w,今までに反転した数,今まで白だったか
q.append([0,0,0,curwhite])
while q:
  y,x,num,curwhite=q.popleft()
  if grid[y][x]=="#":
    # 黒だった場合
    if curwhite:
      curwhite=False
      # 今まで白だった場合
      num+=1
      if dp[y][x]>num:
        dp[y][x]=num
      else:
        continue
    else:
      # 今まで黒だった場合
      if dp[y][x]>num:
        dp[y][x]=num
      else:
        continue
  else:
    # 白だった場合
    if curwhite:
      # 今まで白だった場合
      if dp[y][x]>num:
        dp[y][x]=num
      else:
        continue
    else:
      # 今まで黒だった場合
      curwhite=True
      if dp[y][x]>num:
        dp[y][x]=num
      else:
        continue
  if y+1<H:
    q.append([y+1,x,num,curwhite])
  if x+1<W:
    q.append([y,x+1,num,curwhite])

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

Submission status: Accepted

Solution code:
from collections import defaultdict
import queue

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

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

n = dp[0][0]
for i in range(H-1):
    if c[i][0] == "." and c[i+1][0] == "#":
        n += 1
    dp[i+1][0] = n

m = dp[0][0]
for i in range(W-1):
    if c[0][i] == "." and c[0][i+1] == "#":
        m += 1
    dp[0][i+1] = m

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

        if c[i][g-1] == "." and c[i][g] == "#":
            dp[i][g] = min(dp[i][g-1]+1, dp[i][g])
        else:
            dp[i][g] = min(dp[i][g-1], dp[i][g])

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

Submission status: Accepted

Solution code:
#!usr/bin/env python3
from collections import defaultdict, deque
from heapq import heappush, heappop
from itertools import permutations, accumulate
import sys
import math
import bisect
def LI(): return [int(x) for x in sys.stdin.readline().split()]
def I(): return int(sys.stdin.readline())
def LS():return [list(x) for x in sys.stdin.readline().split()]
def S():
    res = list(sys.stdin.readline())
    if res[-1] == "\n":
        return res[:-1]
    return res
def IR(n):
    return [I() for i in range(n)]
def LIR(n):
    return [LI() for i in range(n)]
def SR(n):
    return [S() for i in range(n)]
def LSR(n):
    return [LS() for i in range(n)]

sys.setrecursionlimit(1000000)
mod = 1000000007

d = [(1,0),(0,1)]
def solve():
    h,w = LI()
    s = [input() for i in range(h)]
    bfs = [[float("inf")]*w for i in range(h)]
    bfs[0][0] = 1&(s[0][0] == "#")
    q = [(bfs[0][0],0,0)]
    while q:
        b,y,x = heappop(q)
        if (y,x) == (h-1,w-1):
            print(b)
            return
        for dy,dx in d:
            ny,nx = y+dy,x+dx
            if 0 <= ny < h and 0 <= nx < w:
                if s[ny][nx] == "#" and s[y][x] != "#":
                    nb = b+1
                else:
                    nb = b
                if nb < bfs[ny][nx]:
                    bfs[ny][nx] = nb
                    heappush(q,(nb,ny,nx))
    return

#Solve
if __name__ == "__main__":
    solve()

Submission status: Accepted

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

def main():
    h,w=map(int,input().split())
    S=[['#']*(w+1)]
    for _ in range(h):
        S.append(['#']+list(input().strip()))
    A=[[0]*(w+1) for _ in range(h+1)]
    for i in range(w+1):
        A[0][i]=float('inf')
    for i in range(h+1):
        A[i][0]=float('inf')
    A[1][1]=int(S[1][1]=='#')
    for i in range(1,h+1):
        for j in range(1,w+1):
            if i==1 and j==1:
                continue
            if S[i][j]=='.':
                A[i][j]=min(A[i-1][j],A[i][j-1])
            else: #S[i][j]=='#'
                A[i][j]=min(A[i-1][j]+int(S[i-1][j]=='.'),A[i][j-1]+int(S[i][j-1]=='.'))
    print(A[-1][-1])
    
if __name__=='__main__':
    main()

Submission status: Accepted

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

import sys

def input(): return sys.stdin.readline().strip()
def list2d(a, b, c): return [[c] * b for i in range(a)]
def list3d(a, b, c, d): return [[[d] * c for j in range(b)] for i in range(a)]
def list4d(a, b, c, d, e): return [[[[e] * d for j in range(c)] for j in range(b)] for i in range(a)]
def ceil(x, y=1): return int(-(-x // y))
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(N=None): return list(MAP()) if N is None else [INT() for i in range(N)]
def Yes(): print('Yes')
def No(): print('No')
def YES(): print('YES')
def NO(): print('NO')
sys.setrecursionlimit(10 ** 9)
INF = 10 ** 18
MOD = 10 ** 9 + 7

def build_grid(H, W, intv, _type, space=True, padding=False):
    # 入力がスペース区切りかどうか
    if space:
        _input = lambda: input().split()
    else:
        _input = lambda: input()
    _list = lambda: list(map(_type, _input()))
    # 余白の有無
    if padding:
        offset = 1
    else:
        offset = 0
    grid = list2d(H+offset*2, W+offset*2, intv)
    for i in range(offset, H+offset):
        row = _list()
        for j in range(offset, W+offset):
            grid[i][j] = row[j-offset]
    return grid

H, W = MAP()
grid = build_grid(H, W, '*', str, space=0, padding=1)

# dp[i][j] := マス(i, j)に到達するための最小コスト
dp = list2d(H+2, W+2, INF)
if grid[1][1] == '.':
    dp[1][1] = 0
else:
    dp[1][1] = 1
for i in range(H+1):
    for j in range(W+1):
        # 白から黒への移動のみコストがかかる
        if grid[i][j] == '.' and grid[i][j+1] == '#':
            dp[i][j+1] = min(dp[i][j+1], dp[i][j] + 1)
        else:
            dp[i][j+1] = min(dp[i][j+1], dp[i][j])  
        if grid[i][j] == '.' and grid[i+1][j] == '#':  
            dp[i+1][j] = min(dp[i+1][j], dp[i][j] + 1)
        else:
            dp[i+1][j] = min(dp[i+1][j], dp[i][j])
ans = dp[H][W]
print(ans)

Submission status: Accepted

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

s = []
for i in range(h):
    s.append(list(input()))

dp = [[1000000]*w for i in range(h)]

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

Submission status: Accepted

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

def main():
    H, W = MAP()
    dx = [1, 0]
    dy = [0, 1]
    s = [input() for _ in range(H)]

    start = (0, 0)

    q = deque()
    q.append(start)

    cost = [[INF]*W for _ in range(H)]
    if s[0][0] == "#":
        cost[0][0] = 1
    else:
        cost[0][0] = 0
    while q:
        i, j = q.popleft()
        for k in range(2):
            y = i + dy[k]
            x = j + dx[k]
            if y < 0 or y > H-1 or x < 0 or x > W-1:
                continue
            if s[i][j] == "." and s[y][x] == "#":  # コストが増える
                if cost[y][x] > cost[i][j] + 1:
                    cost[y][x] = cost[i][j] + 1
                    q.append((y, x))
            else:
                if cost[y][x] > cost[i][j]: 
                    cost[y][x] = cost[i][j]
                    q.append((y, x))
    print(cost[H-1][W-1])

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import sys
#input = sys.stdin.buffer.readline
 
def main():
    H,W = map(int,input().split())
    s = [list(input()) for _ in range(H)]
    
    memo = [[-1 for _ in range(W)] for _ in range(H)]
    def ch(x,y):
        if x == H-1 and y == W-1:
            memo[x][y] = 0
        else:
            if s[x][y] == ".":
                if y == W-1:
                    if s[x+1][y] == ".":
                        memo[x][y] = memo[x+1][y] if memo[x+1][y] != -1 else ch(x+1,y)
                    else:
                        memo[x][y] = memo[x+1][y]+1 if memo[x+1][y] != -1 else ch(x+1,y)+1
                elif x == H-1:
                    if s[x][y+1] == ".":
                        memo[x][y] = memo[x][y+1] if memo[x][y+1] != -1 else ch(x,y+1)
                    else:
                        memo[x][y] = memo[x][y+1]+1 if memo[x][y+1] != -1 else ch(x,y+1)+1
                else:
                    if s[x][y] == s[x+1][y]:
                        a = memo[x+1][y] if memo[x+1][y] != -1 else ch(x+1,y)
                    else:
                        a = memo[x+1][y]+1 if memo[x+1][y] != -1 else ch(x+1,y)+1
                    if s[x][y] == s[x][y+1]:
                        b = memo[x][y+1] if memo[x][y+1] != -1 else ch(x,y+1)
                    else:
                        b = memo[x][y+1]+1 if memo[x][y+1] != -1 else ch(x,y+1)+1
                    memo[x][y] = min(a,b)
            else:
                if y == W-1:
                    memo[x][y] = memo[x+1][y] if memo[x+1][y] != -1 else ch(x+1,y)
                elif x == H-1:
                    memo[x][y] = memo[x][y+1] if memo[x][y+1] != -1 else ch(x,y+1)
                else:
                    memo[x][y] = min(memo[x][y+1],memo[x+1][y]) if (memo[x][y+1] != -1 and memo[x+1][y] != -1) else min(ch(x+1,y),ch(x,y+1))
        return memo[x][y]

    if s[0][0] == "#":
        a = 1
    else:
        a = 0
    print(a+ch(0,0))
    
if __name__ == "__main__":
    main()

Submission status: Accepted

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

import sys

def input(): return sys.stdin.readline().strip()
def list2d(a, b, c): return [[c] * b for i in range(a)]
def list3d(a, b, c, d): return [[[d] * c for j in range(b)] for i in range(a)]
def list4d(a, b, c, d, e): return [[[[e] * d for j in range(c)] for j in range(b)] for i in range(a)]
def ceil(x, y=1): return int(-(-x // y))
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(N=None): return list(MAP()) if N is None else [INT() for i in range(N)]
def Yes(): print('Yes')
def No(): print('No')
def YES(): print('YES')
def NO(): print('NO')
sys.setrecursionlimit(10 ** 9)
INF = 10 ** 18
MOD = 10 ** 9 + 7

def build_grid(H, W, intv, _type, space=True, padding=False):
    # 入力がスペース区切りかどうか
    if space:
        _input = lambda: input().split()
    else:
        _input = lambda: input()
    _list = lambda: list(map(_type, _input()))
    # 余白の有無
    if padding:
        offset = 1
    else:
        offset = 0
    grid = list2d(H+offset*2, W+offset*2, intv)
    for i in range(offset, H+offset):
        row = _list()
        for j in range(offset, W+offset):
            grid[i][j] = row[j-offset]
    return grid

H, W = MAP()
grid = build_grid(H, W, '*', str, space=0, padding=1)

dp = list2d(H+2, W+2, INF)
if grid[1][1] == '.':
    dp[1][1] = 0
else:
    dp[1][1] = 1
for i in range(H+1):
    for j in range(W+1):
        if grid[i][j] == '.' and grid[i][j+1] == '#':
            dp[i][j+1] = min(dp[i][j+1], dp[i][j] + 1)
        else:
            dp[i][j+1] = min(dp[i][j+1], dp[i][j])  
        if grid[i][j] == '.' and grid[i+1][j] == '#':  
            dp[i+1][j] = min(dp[i+1][j], dp[i][j] + 1)
        else:
            dp[i+1][j] = min(dp[i+1][j], dp[i][j])
ans = dp[H][W]
print(ans)

Submission status: Accepted

Solution code:
def main():
    h, w = map(int, input().split())
    s = [[i == "." for i in input()] for _ in range(h)]
    dp = [[10000] * w for _ in range(h)]
    dp[0][0] = 1 - s[0][0]
    for r in range(1, h):
        dp[r][0] = dp[r - 1][0] + (s[r - 1][0] and not s[r][0])
    for c in range(1, w):
        dp[0][c] = dp[0][c - 1] + (s[0][c - 1] and not s[0][c])
    for r in range(1, h):
        for c in range(1, w):
            dp[r][c] = min(dp[r - 1][c] + (s[r - 1][c] and not s[r][c]), dp[r][c - 1] + (s[r][c - 1] and not s[r][c]))
    print(dp[-1][-1])


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
from collections import defaultdict,deque
from heapq import heappush, heappop
from bisect import bisect_left, bisect_right
import sys, random, itertools, math
sys.setrecursionlimit(10**5)
input = sys.stdin.readline
sqrt = math.sqrt
def LI(): return list(map(int, input().split()))
def LF(): return list(map(float, input().split()))
def LI_(): return list(map(lambda x: int(x)-1, input().split()))
def II(): return int(input())
def IF(): return float(input())
def LS(): return list(map(list, input().split()))
def S(): return list(input().rstrip())
def IR(n): return [II() for _ in range(n)]
def LIR(n): return [LI() for _ in range(n)]
def FR(n): return [IF() for _ in range(n)]
def LFR(n): return [LI() for _ in range(n)]
def LIR_(n): return [LI_() for _ in range(n)]
def SR(n): return [S() for _ in range(n)]
def LSR(n): return [LS() for _ in range(n)]
mod = 1000000007
inf = float("INF")

#solve
def solve():
    h,w = LI()
    s = SR(h)
    b = [[inf] * w for i in range(h)]
    q = [(s[0][0] == "#", (0, 0))]
    b[0][0] = s[0][0] == "#"
    while q:
        p, xy = heappop(q)
        y, x = xy
        z = s[y][x]
        for mx, my in [(0, 1), (1, 0)]:
            mx += x
            my += y
            if 0 <= mx < w and 0 <= my < h:
                if b[my][mx] > p + (z != s[my][mx] and s[my][mx] != "."):
                    b[my][mx] = p + (z != s[my][mx] and s[my][mx] != ".")
                    heappush(q, (p + (z != s[my][mx] and s[my][mx] != "."), (my, mx)))

    print(b[-1][-1] if b[-1][-1] else 0)

    return


#main
if __name__ == '__main__':
    solve()

Submission status: Accepted

Solution code:
h, w = map(int, input().split())
s = []
for _ in range(h):
    s.append(input())
mem = [[None]*w for _ in range(h)]
def next(r, c):
    if r==h-1 and c==w-1:
        return 0 if s[0][0]=='.' else 1
    if mem[r][c] is not None:
        return mem[r][c]
    tmp = 10000
    if c<w-1:
        if s[r][c]=='.' and s[r][c+1]=='#':
            tmp = next(r, c+1) + 1
        else:
            tmp = next(r, c+1)
    if r<h-1:
        if s[r][c]=='.' and s[r+1][c]=='#':
            tmp = min(next(r+1, c) + 1, tmp)
        else:
            tmp = min(next(r+1, c), tmp)
    mem[r][c] = tmp
    return tmp
print(next(0, 0))