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:
def main():
  import sys
  input=sys.stdin.buffer.readline
  h,w=map(int,input().split())
  x=w+1
  s=[c>>3for _ in range(h)for c in input()]
  dp=[10001]*h*x
  dp[0]=5-s[0]
  for i in range(1,w):
    dp[i]=dp[i-1]+(s[i-1]^s[i])
  for i in range(x,h*x,x):
    dp[i]=dp[i-x]+(s[i-x]^s[i])
    for j in range(1,w):
      k=i+j
      t=dp[k-1]+(s[k-1]^s[k])
      u=dp[k-x]+(s[k-x]^s[k])
      if t>u:t=u
      dp[k]=t
  print(dp[-2]+1>>1)
main()

Submission status: Accepted

Solution code:
def main():
  import sys
  input=sys.stdin.buffer.readline
  h,w=map(int,input().split())
  s=[c>>3for _ in range(h)for c in input()[:w]]
  dp=[10001]*h*w
  dp[0]=5-s[0]
  for i in range(1,w):
    dp[i]=dp[i-1]+(s[i-1]^s[i])
  for i in range(w,h*w,w):
    dp[i]=dp[i-w]+(s[i-w]^s[i])
  for i in range(1,h):
    for j in range(1,w):
      k=i*w+j
      t=dp[k-1]+(s[k-1]^s[k])
      u=dp[k-w]+(s[k-w]^s[k])
      if t>u:t=u
      dp[k]=t
  print(dp[-1]+1>>1)
main()

Submission status: Accepted

Solution code:
def main():
  import sys
  input=sys.stdin.buffer.readline
  h,w=map(int,input().split())
  s=[c>>3for _ in range(h)for c in input()]
  dp=[10001]*h*(w+1)
  dp[0]=5-s[0]
  for i in range(h):
    for j in range(w):
      k=i*(w+1)+j
      dpk=dp[k]
      sk=s[k]
      l=k+1
      t=dpk+(sk^s[l])
      if dp[l]>t:dp[l]=t
      if i+1<h:
        l=k-~w
        t=dpk+(sk^s[l])
        if dp[l]>t:dp[l]=t
  print(dp[-2]+1>>1)
main()

Submission status: Accepted

Solution code:
def main():
  import sys
  input=sys.stdin.buffer.readline
  h,w=map(int,input().split())
  s=[c//8for _ in range(h)for c in input()]
  dp=[10001]*h*(w+1)
  dp[0]=5-s[0]
  for i in range(h):
    for j in range(w):
      k=i*(w+1)+j
      dpk=dp[k]
      sk=s[k]
      l=k+1
      t=dpk+(sk^s[l])
      if dp[l]>t:dp[l]=t
      if i+1<h:
        l=k-~w
        t=dpk+(sk^s[l])
        if dp[l]>t:dp[l]=t
  print(dp[-2]+1>>1)
main()

Submission status: Accepted

Solution code:
def main():
  import sys
  input=sys.stdin.buffer.readline
  h,w=map(int,input().split())
  s=[c//8for _ in range(h)for c in input()[:w]]
  dp=[10**9]*h*w
  dp[0]=5-s[0]
  for i in range(h):
    for j in range(w):
      k=i*w+j
      if j+1<w:
        t=dp[k]+(s[k]^s[k+1])
        if dp[k+1]>t:dp[k+1]=t
      if i+1<h:
        t=dp[k]+(s[k]^s[k+w])
        if dp[k+w]>t:dp[k+w]=t
  print(dp[-1]+1>>1)
main()

Submission status: Accepted

Solution code:
def main():
  import sys
  input=sys.stdin.buffer.readline
  h,w=map(int,input().split())
  s=[c<46and 1or 0for _ in range(h)for c in input()[:w]]
  dp=[10**9]*h*w
  dp[0]=s[0]
  for i in range(h*w):
    j,k=i//w,i%w
    for y,x in((j+1,k),(j,k+1)):
      if y<h and x<w:
        z=y*w+x
        t=dp[i]+(s[i]^s[z])
        if dp[z]>t:dp[z]=t
  print(dp[-1]+1>>1)
main()

Submission status: Accepted

Solution code:
from collections import *
from heapq import *
H,W=map(int,input().split())
S=[input() for i in range(H)]
if S[0][0]=="#":
    count=1
else:
    count=0
idlemax=10**5
visited=[[idlemax for w in range(W)] for h in range(H)]
stack=deque([[0,0,bool(S[0][0]=="#")*1,bool(S[0][0]=="#")*1]])
while stack:

    h,w,m,flag=stack.popleft()
    if m>visited[h][w]:
        continue
    for y,x in [[0,1],[1,0]]:
        Y=h+y;X=w+x
        if Y<H and X<W:
            if flag:
                if visited[Y][X]>m:
                    if S[Y][X]==".":
                        nflag=0
                    else:
                        nflag=1
                    visited[Y][X]=m
                    stack.append([Y,X,m,nflag])
            else:
                if S[Y][X]=="#":
                    nflag=1
                    M=m+1
                else:
                    nflag=0
                    M=m
                if visited[Y][X]>M:
                    visited[Y][X]=M
                    stack.append([Y,X,M,nflag])
#print(visited)
print(visited[-1][-1])

Submission status: Accepted

Solution code:
import heapq
def A():
    H, W = map(int, input().split())
    maze = []
    for i in range(H):
        maze.append(input())
    # if maze[0][0] == '.':
    #     q = [[0, (0, 0)]]
    # else:
    #     q = [[1, (0, 0)]]
    # heapq.heapify(q)
    # while q:
    #     #print(q)
    #     cost, cur = heapq.heappop(q)
    #     if cur[0] == H-1 and cur[1] == W-1:
    #         print(cost)
    #         return
    #     for direction in [(0, 1), (1, 0)]:
    #         new_r, new_c = cur[0]+direction[0], cur[1]+direction[1]
    #         if new_r >= 0 and new_c >= 0 and new_r < H and new_c < W:
    #             if maze[new_r][new_c]=='.':
    #                 heapq.heappush(q, [cost, (new_r, new_c)])
    #             else:
    #                 heapq.heappush(q, [cost+1, (new_r, new_c)])
    memo = [[float('inf') for i in range(W)] for j in range(H)]
    # if maze[H-1][W-1] == '.':
    #     memo[H-1][W-1] = 0
    # else:
    #     memo[H-1][W-1] = 1
    # def dfs(r, c, prev_flipped):
    #     if memo[r][c] < float('inf'):
    #         return memo[r][c]
    #     cur_flipped = False
    #     if maze[r][c] == '.':
    #         cur_cost = 0
    #     else:
    #         if prev_flipped:
    #             cur_cost = 0
    #         else:
    #             cur_cost = 1
    #         cur_flipped = True
    #     minimum_next = float('inf')
    #     if r+1 < H:
    #         minimum_next = dfs(r+1, c, cur_flipped)
    #     if c+1 < W:
    #         minimum_next = min(minimum_next, dfs(r, c+1, cur_flipped))
    #     res = cur_cost+minimum_next
    #     memo[r][c] = res
    #     return res
    # print(dfs(0, 0, False))
    if maze[0][0] == '.':
        memo[0][0] = 0
    else:
        memo[0][0] = 1
    for i in range(H):
        for j in range(W):
            for r, c in [(i+1, j), (i, j+1)]:
                if r<H and c<W:
                    if maze[i][j] == '.' and maze[r][c] == '#':
                        temp = 1
                    else:
                        temp = 0
                    memo[r][c] = min(memo[r][c], memo[i][j]+temp)
    print(memo[-1][-1])

A()

Submission status: Accepted

Solution code:
h,*s=open(0)
h,w=map(int,h.split())
dp=[[9e9]*w for _ in s]
dp[0][0]=s[0][0]<'.'
for i in range(h*w):
  i,j=i//w,i%w
  for y,x in((i+1,j),(i,j+1)):
    if y<h and x<w:dp[y][x]=min(dp[y][x],dp[i][j]+(s[i][j]=='.'>s[y][x]))
print(dp[-1][-1])

Submission status: Accepted

Solution code:
h, w = map(int, input().split())
mapping = [input().strip() for i in range(h)]
dp = [[123012302103120310]*w for i in range(h)]

for i in range(h):
    for j in range(w):
        if i == 0 and j == 0:
            dp[i][j] = int('#' == mapping[i][j])
 
        if j != 0:
            if mapping[i][j] == '#' and mapping[i][j-1] != '#':
                dp[i][j] = min(dp[i][j-1] + 1, dp[i][j])
            else:
                dp[i][j] = min(dp[i][j-1], dp[i][j])
        if i != 0:
            if mapping[i][j] == '#' and mapping[i-1][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])
print(dp[-1][-1])

Submission status: Accepted

Solution code:
h,w = [int(i) for i in input().split()]
s = []
for i in range(h):
  array = list(input())
  s.append(array)
d = [[float("inf")] * (w) for i in range(h)]
d[0][0]=0
if s[0][0]=='#':
  d[0][0]=1
for i in range(1,w):
  if s[0][i]!=s[0][i-1] and s[0][i]!=s[0][0]:
    d[0][i]=d[0][i-1]+1
  else:
    d[0][i]=d[0][i-1]
for i in range(1,h):
  for j in range(w):
    k=0
    u=0
    if j != 0 :
      if s[i][j]=="#" and s[i][j]!=s[i-1][j]:
        k=1
      if s[i][j]=="#" and s[i][j]!=s[i][j-1]:
        u=1
      d[i][j] = min(d[i-1][j]+k,d[i][j-1]+u)
    elif j == 0 :
      if s[i][0]=="#" and s[i][0]!=s[i-1][0]:
        k=1
      d[i][0] = d[i-1][0]+k

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

Submission status: Accepted

Solution code:
from decimal import *
from heapq import heappush, heappop, heapify
from collections import deque, defaultdict, Counter
import itertools
from itertools import permutations, combinations, accumulate
import sys
import bisect
import string
import math
import time


def I(): return int(input())


def S(): return input()


def MI(): return map(int, input().split())


def MS(): return map(str, input().split())


def LI(): return [int(i) for i in input().split()]


def LI_(): return [int(i)-1 for i in input().split()]


def StoI(): return [ord(i)-97 for i in input()]


def ItoS(nn): return chr(nn+97)


def input(): return sys.stdin.readline().rstrip()


def show(*inp, end='\n'):
    if show_flg:
        print(*inp, end=end)


YNL = {False: 'No', True: 'Yes'}
YNU = {False: 'NO', True: 'YES'}
MOD = 10**9+7
inf = float('inf')
IINF = 10**10
l_alp = string.ascii_lowercase
u_alp = string.ascii_uppercase
ts = time.time()
sys.setrecursionlimit(10**6)
nums = ['1', '2', '3', '4', '5', '6', '7', '8', '9', '10']

show_flg = False
# show_flg = True

BLOCK = '#'
ROAD = '.'


def print_matrix(mat):
    for i in range(len(mat)):
        print(*mat[i])


def main():
    H, W = MI()
    graph = [None] * H

    for i in range(H):
        graph[i] = list(S())

    dp = [[IINF] * W for i in range(H)]
    dp[0][0] = 0 if graph[0][0] == ROAD else 1

    for i in range(H):
        for j in range(W):
            for p in [(1, 0), (0, 1)]:
                ni = i + p[0]
                nj = j + p[1]
                if ni >= 0 and ni < H and nj >= 0 and nj < W:
                    cost = 0
                    if graph[i][j] == ROAD and graph[ni][nj] == BLOCK:
                        cost = dp[i][j] + 1
                    else:
                        cost = dp[i][j]
                    dp[ni][nj] = min(cost, dp[ni][nj])

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


if __name__ == '__main__':
    main()

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,boundary=1,search=[],replacement_of_found='.',mp_def={'#':1,'.':0}):
#h,w,g,sg=GGI(h,w,boundary=1,search=['S','G'],replacement_of_found='.',mp_def={'#':1,'.':0}) # sample usage
    mp=[boundary]*(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+=[boundary]+[mp_def[j] for j in s]+[boundary]
    mp+=[boundary]*(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)
def show2d(g,h,w):
    for i in range(h):show(g[i*w:i*w+w])

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,_=GGI(h,w,boundary=-1)
dp=[1e6]*(h*w)
dp[w+1]=g[w+1]

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

print(dp[-w-2])

Submission status: Accepted

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

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

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

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

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

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

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

Submission status: Accepted

Solution code:
import copy
n,m=map(int,input().split())
l=[]
for i in range(n):
    s=list(input())
    l.append(s)
flag=0
s=copy.deepcopy(l)
#print(l)
if(l[0][0]=="#"):
    l[0][0]=1 
else:
    l[0][0]=0;
for i in range(1,n):
    if(l[i][0]=="#"):
        if s[i-1][0]=="#":
            l[i][0]=l[i-1][0]
        else:
            l[i][0]=l[i-1][0]+1
            
    else:
        l[i][0]=l[i-1][0]
for i in range(1,m):
    if( l[0][i]=="#"):
        if s[0][i-1]=="#":
            l[0][i]=l[0][i-1]
        else:
            l[0][i]=l[0][i-1]+1
    else:
        l[0][i]=l[0][i-1]

for i in range(1,n):
    for j in range(1,m):
        if(l[i][j]=="#"):
            a1=l[i][j-1]
            a2=l[i-1][j]
            if s[i][j-1]==".":
                a1+=1
            if s[i-1][j]==".":
                a2+=1
            l[i][j]=min(a1,a2)
        else:
            l[i][j]=min(l[i-1][j],l[i][j-1])
#print(l)
print(l[n-1][m-1])

Submission status: Accepted

Solution code:
h, w = map(int, input().split())
a = lambda x: 1 if x=="#" else 0
S = [list(map(a, list(input()))) for _ in range(h)]
inf = 10*3
dp = [[inf]*w for _ in range(h)]
dp[0][0] = S[0][0]
for i in range(1, w):
    dp[0][i] = dp[0][i-1] + S[0][i]*(S[0][i]!=S[0][i-1])
for i in range(1, h):
    dp[i][0] = dp[i-1][0] + S[i][0]*(S[i][0]!=S[i-1][0])
for i in range(1, h):
    for j in range(1, w):
        dp[i][j] = min(dp[i-1][j]+S[i][j]*(S[i-1][j]!=S[i][j]), dp[i][j-1]+S[i][j]*(S[i][j]!=S[i][j-1]))
print(dp[-1][-1])

Submission status: Accepted

Solution code:
from decimal import *
from heapq import heappush, heappop, heapify
from collections import deque, defaultdict, Counter
import itertools
from itertools import permutations, combinations, accumulate
import sys
import bisect
import string
import math
import time


def I(): return int(input())


def S(): return input()


def MI(): return map(int, input().split())


def MS(): return map(str, input().split())


def LI(): return [int(i) for i in input().split()]


def LI_(): return [int(i)-1 for i in input().split()]


def StoI(): return [ord(i)-97 for i in input()]


def ItoS(nn): return chr(nn+97)


def input(): return sys.stdin.readline().rstrip()


def show(*inp, end='\n'):
    if show_flg:
        print(*inp, end=end)


YNL = {False: 'No', True: 'Yes'}
YNU = {False: 'NO', True: 'YES'}
MOD = 10**9+7
inf = float('inf')
IINF = 10**10
l_alp = string.ascii_lowercase
u_alp = string.ascii_uppercase
ts = time.time()
sys.setrecursionlimit(10**6)
nums = ['1', '2', '3', '4', '5', '6', '7', '8', '9', '10']

show_flg = False
# show_flg = True

BLOCK = '#'
ROAD = '.'


def print_matrix(mat):
    for i in range(len(mat)):
        print(*mat[i])


def bfs(graph, initial, goal, H, W):
    options = [(1, 0), (0, 1)]
    q = deque([initial])
    dist = [[10**9 for i in range(W)] for i in range(H)]
    dist[initial[0]][initial[1]] = 0 if graph[initial[0]][initial[1]] == ROAD else 1

    while len(q) != 0:
        p = q.popleft()

        for d in options:
            i = p[0] + d[0]
            j = p[1] + d[1]

            if i >= 0 and i < H and j >= 0 and j < W:
                if dist[i][j] == 10**9 or dist[p[0]][p[1]] < dist[i][j]:
                    q.append((i, j))
                    if graph[p[0]][p[1]] != BLOCK and graph[i][j] == BLOCK:
                        dist[i][j] = dist[p[0]][p[1]] + 1
                    else:
                        dist[i][j] = dist[p[0]][p[1]]

    # print_matrix(dist)
    return dist[goal[0]][goal[1]]


def main():
    H, W = MI()
    graph = [None] * H

    for i in range(H):
        graph[i] = list(S())

    ret = bfs(graph, (0, 0), (H-1, W-1), H, W)
    print(ret)


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
ii = lambda : int(input())
mi = lambda : map(int,input().split())
li = lambda : list(map(int,input().split()))

h,w = mi()

a = []
for i in range(h):
    k = input()
    a.append([1 if k[j]=='#' else 0 for j in range(w)])

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

# 白から黒で+1
if a[0][0] == 0:
    dp[0][0] = 0
else:
    dp[0][0] = 1

for i in range(1,w):
    if a[0][i-1] == 0 and a[0][i] == 1:
        dp[0][i] = dp[0][i-1] + 1
    else:
        dp[0][i] = dp[0][i-1]

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

for i in range(1,h):#y
    for j in range(1,w):#x
        # u = 200
        if(a[i][j] == 0):
            dp[i][j] = min(dp[i-1][j],dp[i][j-1])
        else:
            if a[i-1][j] == 1:
                u = dp[i-1][j]
            else:
                u = dp[i-1][j] +1

            if a[i][j-1] == 1:
                l = dp[i][j-1]
            else:
                l = dp[i][j-1] +1

            dp[i][j] = min(u,l)


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

Submission status: Accepted

Solution code:
h, w = map(int,input().split())
g = [input() for i in range(h)]
 
d = [[200] * w for i in range(h)]

d[0][0] = ( g[0][0] == "#")
for i in range(h):
    for j in range(w):
        if i + 1 < h:
            d[i+1][j] = min(d[i+1][j], d[i][j]+(g[i+1][j] == '#' and g[i][j] == '.'))
        if j + 1 < w:
            d[i][j+1] = min(d[i][j+1], d[i][j]+(g[i][j+1] == '#' and g[i][j] == '.'))

print(d[-1][-1])

Submission status: Accepted

Solution code:
import sys
from collections import deque as dq
input = sys.stdin.readline
H, W = map(int, input().split())
S = [list(input())[: -1] for _ in range(H)]
Q = dq([0])
d = [1, 0]
dp = [float("inf")] * (H * W)
dp[0] = int(S[0][0] == "#")
while len(Q):
  p = Q.popleft()
  for k in range(2):
    y = p // W + d[k]
    x = p % W + d[-1 - k]
    if y in range(H) and (x in range(W)):
      f = (S[p // W][p % W] == ".") and (S[y][x] == "#")
      if dp[y * W + x] > dp[p] + f:
        dp[y * W + x] = dp[p] + f
        if f: Q.append(y * W + x)
        else: Q.appendleft(y * W + x)
print(dp[-1])

Submission status: Accepted

Solution code:
import numpy as np

H, W = map(int, input().split(' '))
S = []
for i in range(H):
  S.append([x=='#' for x in input()])
# print(S)
S = np.array(S)
C = np.zeros_like(S, dtype=np.int)
for h in range(H):
  for w in range(W):
    if h == 0 and w == 0:
      C[0, 0] = S[0, 0]
      continue
    candidates = []
    if h > 0:
      if S[h, w] and not S[h-1, w]:
        candidates.append(C[h-1, w] + 1)
      else:
        candidates.append(C[h-1, w])
    if w > 0:
      if S[h, w] and not S[h, w-1]:
        candidates.append(C[h, w-1] + 1)
      else:
        candidates.append(C[h, w-1])
    C[h, w] = min(candidates)
#print(C)
print(C[H-1, W-1])

Submission status: Accepted

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

inf = 10**5

cost = [[inf]*w for _ in range(h)]
if s[-1][-1]==".":
    cost[-1][-1]=0
else:
    cost[-1][-1]=1

for i in range(h-1,-1,-1):
    for j in range(w-1,-1,-1):
        if i==h-1 and j==w-1:
            continue
        if s[i][j]=="#":
            if j==w-1:
                pass
            else:
                if s[i][j+1]=="#":
                    cost[i][j]=cost[i][j+1]
                else:
                    cost[i][j]=cost[i][j+1]+1
            if i==h-1:
                pass
            else:
                if s[i+1][j]=="#":
                    cost[i][j]=min(cost[i][j],cost[i+1][j])
                else:
                    cost[i][j]=min(cost[i][j],cost[i+1][j]+1)
        else:
            if j<w-1:
                cost[i][j]=cost[i][j+1]
            if i<h-1:
                cost[i][j]=min(cost[i][j],cost[i+1][j])
print(cost[0][0])

Submission status: Accepted

Solution code:
h,w=map(int,input().split())
S=[]
for i in range(h):
    S.append(input())
    
cnt=0
D=[[10**9]*w for _ in range(h)]
D[0][0]=0
for i in range(h):
    for j in range(w):
        for x,y in [(0,1),(1,0)]:
            if i+x>=h or j+y>=w:
                continue
            if S[i][j]!=S[i+x][j+y]:
                D[i+x][j+y]=min(D[i][j]+1,D[i+x][j+y])
            else:
                D[i+x][j+y]=min(D[i][j],D[i+x][j+y])
                
                
if S[0][0]=='#':
    print(1+D[h-1][w-1]//2)
else:
    print(D[h-1][w-1]//2+(S[0][0]!=S[h-1][w-1]))

Submission status: Accepted

Solution code:
h,w=map(int,input().split())
S=[]
for i in range(h):
    S.append(input())

cnt=0
D=[[10**9]*w for _ in range(h)]
D[0][0]=0
for i in range(h):
    for j in range(w):
        if j>0:
            D[i][j]=D[i][j-1]+(S[i][j]!=S[i][j-1])
        if i>0:
            D[i][j]=min(D[i][j],D[i-1][j]+(S[i][j]!=S[i-1][j]))   
                
                
if S[0][0]=='#':
    print(1+D[h-1][w-1]//2)
else:
    print(D[h-1][w-1]//2+(S[0][0]!=S[h-1][w-1]))

Submission status: Accepted

Solution code:
#-------------------------------------------------------------------
import sys
def p(*_a):
  _s=" ".join(map(str,_a))
  #print(_s)
  sys.stderr.write(_s+"\n")
#-------------------------------------------------------------------

H,W = map(int, input().split())			# "5 7" -> ["5", "7"] -> 5, 7 => N=5,K=7

M = list( list(input()) for _ in range(H) )
#=> [['.', '.', '.', '.'], ['.', 'S', 'S', '.'], ['.', '.', 'S', '.'], ['.', '.', '.', '.']]

INF  = float("inf") # 正の無限大
L = [[[INF,-1] for _c in range(W)] for _r in range(H)]


if M[0][0]=='.':
	L[0][0]=[0,0]
else:
	L[0][0]=[1,1]

h=0
w=0

for h in range(1,H):
	l = [ L[h-1][0][0], 0]
	if M[h][0]=='#':
		l[0] += (0 if L[h-1][0][1] else 1)
		l[1] = 1
	L[h][0] = l

for w in range(1,W):
	l = [ L[0][w-1][0], 0]
	if M[0][w]=='#':
		l[0] += (0 if L[0][w-1][1] else 1)
		l[1] = 1
	L[0][w] = l

#p(M)
#p(L)


for h in range(1,H):
	for w in range(1,W):
		l = [ L[h][w-1][0], 0]
		t = [ L[h-1][w][0], 0]
		if M[h][w]=='#':
			l[0] += (0 if L[h][w-1][1] else 1)
			t[0] += (0 if L[h-1][w][1] else 1)
			l[1] = t[1] = 1
		
		L[h][w] = (l if l[0]<t[0] else t)



#p(M)
#p(L)
print(L[H-1][W-1][0])

Submission status: Accepted

Solution code:
#!python3

import numpy as np


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


def main():
    dp = np.zeros((H, W), dtype=int)
    if S[0][0] == "#":
        dp[0][0] = 1
    
    INF = 10 ** 5
    for i in range(H):
        for j in range(W):
            if i == 0 and j == 0:
                continue
            if i == 0:
                a = INF
            else:
                a = dp[i-1][j]
                if S[i-1][j] == "." and S[i][j] == "#":
                    a += 1
            if j == 0:
                b = INF
            else:
                b = dp[i][j-1]
                if S[i][j-1] == "." and S[i][j] == "#":
                    b += 1
            dp[i][j] = min(a, b)
        
    print(dp[-1][-1])


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:

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

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

        if i != 0:
            cnt = 0
            if s[i][j] == '#' and s[i - 1][j] == '.':
                cnt += 1
            dp[i][j] = min(dp[i][j], dp[i - 1][j] + cnt)

print(dp[-1][-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.pop()
        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:
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]+(g[j]*2+g[j+d]==1),dp[j+d])

print(dp[-w-2])