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:
import sys
readline = sys.stdin.buffer.readline

h,w = map(int,readline().split())

maze = []
for i in range(h):
    maze.append(readline().rstrip().decode('utf-8'))

dp = [[0]*w for _ in range(h)] #dp[i][j]:そこまでに何回変色したかの最小値

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

for i in range(h):
    for j in range(w):
        if i == 0:
            if j == 0:
                continue
            res = 1 if maze[i][j] != maze[i][j-1] else 0

            dp[i][j] = dp[i][j-1] + res

        elif j == 0:
            res = 1 if maze[i][j] != maze[i-1][j] else 0

            dp[i][j] = dp[i-1][j] + res

        else:
            res_h = 1 if maze[i][j] != maze[i-1][j] else 0
            res_w = 1 if maze[i][j] != maze[i][j-1] else 0
            
            dp[i][j] = min(dp[i][j-1] + res_w,dp[i-1][j] + res_h)

print((dp[i][j]+1)//2)

Submission status: Accepted

Solution code:
h,w = map(int,input().split())
map1 = [list(input()) for _ in range(h)]
check_board = [[9e9]*w for _ in range(h)]
for x in range(h):
	for y in range(w):
		map1[x][y] = 1 if map1[x][y] =="#" else 0
check_board[0][0] = map1[0][0]
def cal_ans(a,b,x,y):
	return ((map1[a][b]^map1[x][y])&map1[a][b])+check_board[x][y]
for x in range(h):
	for y in range(w):
		if x < h-1:
			check_board[x+1][y] = min(check_board[x+1][y],cal_ans(x+1,y,x,y))
		if y < w-1:
			check_board[x][y+1] = min(check_board[x][y+1],cal_ans(x,y+1,x,y))
print(check_board[-1][-1])

Submission status: Accepted

Solution code:
def main():
  h,t,*s=open(0)
  h,w=map(int,h.split())
  a=b=x=y=t[0]=='#'
  d=[(b,a)]
  d_add=d.append
  for i in range(1,w):
    f=t[i]=='#'
    b+=a^f
    a=f
    d_add((b,a))
  for s in s:
    f=s[0]=='#'
    y+=x^f
    b=y
    a=x=f
    p=[(b,a)]
    p_add=p.append
    for i in range(1,w):
      f=s[i]=='#'
      b+=a^f
      c,g=d[i]
      c+=f^g
      if b>c:b=c
      a=f
      p_add((b,a))
    d=p
  print(b+1>>1)
main()

Submission status: Accepted

Solution code:
# Problem A - Range Flip Find Route

# input
h, w = map(int, input().split())
s_board = [['']*w for i in range(h)]
for i in range(h):
    s = list(input())
    for j in range(w):
        s_board[i][j] = s[j]

# initialization
INF = 10**5
dp = [[INF]*w for i in range(h)]
if s_board[0][0]=='#':
    dp[0][0] = 1
else:
    dp[0][0] = 0

# count
for i in range(h):
    for j in range(w):
        # skip
        if i==0 and j==0:
            continue

        # left
        if j-1>=0:
            if s_board[i][j]=='#' and s_board[i][j-1]=='.':
                dp[i][j] = min(dp[i][j], dp[i][j-1] + 1)
            else:
                dp[i][j] = min(dp[i][j], dp[i][j-1])

        # up
        if i-1>=0:
            if s_board[i][j]=='#' and s_board[i-1][j]=='.':
                dp[i][j] = min(dp[i][j], dp[i-1][j] + 1)
            else:
                dp[i][j] = min(dp[i][j], dp[i-1][j])

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

Submission status: Accepted

Solution code:
def main():
  h,w=map(int,input().split())
  s=input()
  a=b=x=y=s[0]=='#'
  d=[(b,a)]
  d_add=d.append
  for i in range(1,w):
    f=s[i]=='#'
    b+=a^f
    a=f
    d_add((b,a))
  for _ in range(h-1):
    s=input()
    f=s[0]=='#'
    y+=x^f
    b=y
    a=x=f
    p=[(b,a)]
    p_add=p.append
    for i in range(1,w):
      f=s[i]=='#'
      b+=a^f
      c,g=d[i]
      c+=f^g
      if b>c:b=c
      a=f
      p_add((b,a))
    d=p
  print(b+1>>1)
main()

Submission status: Accepted

Solution code:
def main():
  import sys
  input=sys.stdin.buffer.readline
  h,w=map(int,input().split())
  s=input()
  a=b=x=y=s[0]==35
  d=[(b,a)]
  d_add=d.append
  for i in range(1,w):
    f=s[i]==35
    b+=a^f
    a=f
    d_add((b,a))
  for _ in range(h-1):
    s=input()
    f=s[0]==35
    y+=x^f
    b=y
    a=x=f
    p=[(b,a)]
    p_add=p.append
    for i in range(1,w):
      f=s[i]==35
      b+=a^f
      c,g=d[i]
      c+=f^g
      if b>c:b=c
      a=f
      p_add((b,a))
    d=p
  print(b+1>>1)
main()

Submission status: Accepted

Solution code:
def main():
  import sys
  input=sys.stdin.buffer.readline
  h,w=map(int,input().split())
  s=input()
  a=x=s[0]==35
  b=y=a and 1or 0
  d=[(b,a)]
  d_add=d.append
  for i in range(1,w):
    f=s[i]==35
    b+=a^f and 1or 0
    a=f
    d_add((b,a))
  for _ in range(h-1):
    s=input()
    f=s[0]==35
    y+=x^f and 1or 0
    b=y
    a=x=f
    p=[(b,a)]
    p_add=p.append
    for i in range(1,w):
      f=s[i]==35
      b+=a^f and 1or 0
      c,g=d[i]
      c+=f^g and 1or 0
      if b>c:b=c
      a=f
      p_add((b,a))
    d=p
  print(b+1>>1)
main()

Submission status: Accepted

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

dp = [[float("INF")]*w for i in range(h)]
if l[0][0] == ".":
    dp[0][0] = 0
else:
    dp[0][0] = 1

for i in range(h):
    for j in range(w):
        a = dp[i-1][j]
        b = dp[i][j-1] 
        if l[i-1][j] == "." and l[i][j] == "#":
            a += 1
        if l[i][j-1] == "." and l[i][j] == "#":
            b += 1
        dp[i][j] = min(a,b,dp[i][j])
print(dp[-1][-1])

Submission status: Accepted

Solution code:
def main():
  import sys
  input=sys.stdin.buffer.readline
  h,w=map(int,input().split())
  s=input()
  a=b=x=y=s[0]==35
  d=[(b,a)]
  d_add=d.append
  for i in range(1,w):
    f=s[i]==35
    b+=a^f and 1or 0
    a=f
    d_add((b,a))
  for _ in range(h-1):
    s=input()
    f=s[0]==35
    y+=x^f and 1or 0
    b=y
    a=x=f
    p=[(b,a)]
    p_add=p.append
    for i in range(1,w):
      f=s[i]==35
      b+=a^f and 1or 0
      c,g=d[i]
      c+=f^g and 1or 0
      if b>c:b=c
      a=f
      p_add((b,a))
    d=p
  print(b+1>>1)
main()

Submission status: Accepted

Solution code:
def main():
  import sys
  buf=sys.stdin.buffer
  h,w=map(int,buf.readline().split())
  s=buf.readline()
  a=b=x=y=s[0]==35
  d=[(b,a)]
  d_add=d.append
  for i in range(1,w):
    f=s[i]==35
    b+=a^f
    a=f
    d_add((b,a))
  for s in buf.read().split():
    f=s[0]==35
    y+=x^f
    b=y
    a=x=f
    p=[(b,a)]
    p_add=p.append
    for i in range(1,w):
      f=s[i]==35
      b+=a^f
      c,g=d[i]
      c+=f^g
      if b>c:b=c
      a=f
      p_add((b,a))
    d=p
  print(b+1>>1)
main()

Submission status: Accepted

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

dp = [[-1]*w for i in range(h)]
if l[0][0] == ".":
    dp[0][0] = 0
else:
    dp[0][0] = 1

for i in range(h):
    for j in range(w):
        if i == 0 and j == 0:
            continue

        if i == 0:
            if l[i][j-1] == "." and l[i][j] == "#":
                dp[i][j] = dp[i][j-1]+1
            else:
                dp[i][j] = dp[i][j-1]
        elif j == 0:
            if l[i-1][j] == "." and l[i][j] == "#":
                dp[i][j] = dp[i-1][j]+1
            else:
                dp[i][j] = dp[i-1][j]
        else:
            a = dp[i-1][j]
            b = dp[i][j-1] 
            if l[i-1][j] == "." and l[i][j] == "#":
                a += 1
            if l[i][j-1] == "." and l[i][j] == "#":
                b += 1
            dp[i][j] = min(a,b)
print(dp[-1][-1])

Submission status: Accepted

Solution code:
def main():
  import sys
  buf=sys.stdin.buffer
  h,w=map(int,buf.readline().split())
  s=buf.readline()
  a=b=x=y=s[0]==35
  d,e=[b],[a]
  d_add,e_add=d.append,e.append
  for i in range(1,w):
    f=s[i]==35
    b+=a^f
    a=f
    d_add(b)
    e_add(a)
  for s in buf.read().split():
    f=s[0]==35
    y+=x^f
    b=y
    a=x=f
    p,q=[b],[a]
    p_add,q_add=p.append,q.append
    for i in range(1,w):
      f=s[i]==35
      b+=a^f
      c=d[i]+(f^e[i])
      if b>c:b=c
      a=f
      p_add(b)
      q_add(a)
    d,e=p,q
  print(b+1>>1)
main()

Submission status: Accepted

Solution code:
def main():
  import sys
  buf=sys.stdin.buffer
  h,w=map(int,buf.readline().split())
  s=buf.readline()
  a=b=x=y=s[0]==35
  d=[b]
  e=[a]
  for i in range(1,w):
    f=s[i]==35
    b+=a^f
    a=f
    d+=b,
    e+=a,
  for s in buf.read().split():
    f=s[0]==35
    y+=x^f
    b=y
    a=x=f
    p=[b]
    q=[a]
    for i in range(1,w):
      f=s[i]==35
      b+=a^f
      c=d[i]+(f^e[i])
      if b>c:b=c
      a=f
      p+=b,
      q+=a,
    d=p
    e=q
  print(b+1>>1)
main()

Submission status: Accepted

Solution code:
def main():
  import sys
  buf=sys.stdin.buffer
  h,w=map(int,buf.readline().split())
  c,*s,_=buf.readline()
  a=b=x=y=c==35
  d=[(b,a)]
  for c in s:
    f=c==35
    b+=a^f
    a=f
    d+=(b,a),
  for c,*s in buf.read().split():
    f=c==35
    y+=x^f
    b=y
    a=x=f
    p=[(b,a)]
    for i,c in enumerate(s,1):
      f=c==35
      b+=a^f
      c,g=d[i]
      c+=f^g
      if b>c:b=c
      a=f
      p+=(b,a),
    d=p
  print(b+1>>1)
main()

Submission status: Accepted

Solution code:
def main():
  import sys
  buf=sys.stdin.buffer
  h,w=map(int,buf.readline().split())
  s=buf.readline()
  a=b=x=y=s[0]==35
  d=[(b,a)]
  for i in range(1,w):
    f=s[i]==35
    b+=a^f
    a=f
    d+=(b,a),
  for s in buf.read().split():
    f=s[0]==35
    y+=x^f
    b=y
    a=x=f
    p=[(b,a)]
    for i in range(1,w):
      f=s[i]==35
      b+=a^f
      c,g=d[i]
      c+=f^g
      if b>c:b=c
      a=f
      p+=(b,a),
    d=p
  print(b+1>>1)
main()

Submission status: Accepted

Solution code:
def main():
  import sys
  input=sys.stdin.buffer.readline
  h,w=map(int,input().split())
  s=input()
  a=b=x=y=s[0]==35
  d=[(b,a)]
  for i in range(1,w):
    f=s[i]==35
    b+=a^f
    a=f
    d+=(b,a),
  for _ in range(1,h):
    s=input()
    f=s[0]==35
    y+=x^f
    b=y
    a=x=f
    p=[(b,a)]
    for i in range(1,w):
      f=s[i]==35
      b+=a^f
      c,g=d[i]
      c+=f^g
      if b>c:b=c
      a=f
      p+=(b,a),
    d=p
  print(b+1>>1)
main()

Submission status: Accepted

Solution code:
def main():
  import sys
  input=sys.stdin.buffer.readline
  h,w=map(int,input().split())
  s=input()
  a=x=s[0]>>3
  b=y=5-a
  d=[(b,a)]
  for i in range(1,w):
    f=s[i]>>3
    b+=a^f
    a=f
    d+=(b,a),
  for _ in range(1,h):
    s=input()
    f=s[0]>>3
    y+=x^f
    b=y
    a=x=f
    p=[(b,a)]
    for i in range(1,w):
      f=s[i]>>3
      b+=a^f
      c,g=d[i]
      c+=f^g
      if b>c:b=c
      a=f
      p+=(b,a),
    d=p
  print(b+1>>1)
main()

Submission status: Accepted

Solution code:
import sys
h, w = list(map(int, sys.stdin.readline().split()))
graph = [list(sys.stdin.readline().rstrip()) for _ in range(h)]

dp = [[10**5 for _ in range(w)] for _ in range(h)]
dp[0][0] = 0 if graph[0][0] == '.' else 1

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

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

for j in range(1, h):
    for i in range(1, w):
        if (graph[j][i] == '.') or (graph[j][i] == graph[j-1][i] == graph[j][i-1]):
            dp[j][i] = min(dp[j-1][i], dp[j][i-1])
        elif graph[j-1][i] == '#' and graph[j][i-1] == '.':
            dp[j][i] = min(dp[j-1][i], dp[j][i-1]+1)
        elif graph[j][i-1] == '#' and graph[j-1][i] == '.':
            dp[j][i] = min(dp[j-1][i]+1, dp[j][i-1])
        else:
            dp[j][i] = min(dp[j-1][i], dp[j][i-1])+1

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

Submission status: Accepted

Solution code:
H, W = map(int, input().split())
maze = [list(input()) for i in range(H)]
dp = [[float('inf')]*W for i in range(H)]
dp[0][0] = 0

for y in range(H):
    for x in range(W):
        if y == 0 and x == 0:
            continue
        
        if x >= 1:
            if maze[y][x - 1] == "." and maze[y][x] == "#":
                dp[y][x] = min(dp[y][x - 1] + 1, dp[y][x])
            else:
                dp[y][x] = min(dp[y][x - 1], dp[y][x])
        
        if y >= 1:
            if maze[y - 1][x] == "." and maze[y][x] == "#":
                dp[y][x] = min(dp[y - 1][x] + 1, dp[y][x])
            else:
                dp[y][x] = min(dp[y - 1][x], dp[y][x])

if maze[0][0] == "#":
    print(dp[-1][-1] + 1)
else:
    print(dp[-1][-1])

Submission status: Accepted

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

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

    for w in range(1,W):
        if field[0][w-1] == '.' and field[0][w] == '#':
            dp[0][w] = dp[0][w-1] + 1
        else:
            dp[0][w] = dp[0][w-1]
    
    for w in range(1,W):
        for h in range(1,H):
            fromUpward = dp[h-1][w]
            if field[h-1][w] == '.' and field[h][w] == '#':
                fromUpward += 1

            fromLeft = dp[h][w-1]
            if field[h][w-1] == '.' and field[h][w] == '#':
                fromLeft += 1
            
            dp[h][w] = min(fromUpward, fromLeft)
    
    ans = dp[H-1][W-1]
    if field[0][0] == '#':
        ans += 1

    print(ans)

if __name__ == '__main__':
    solve()

Submission status: Accepted

Solution code:
def main():
    h, w = map(int, input().split())
    grid = [input() for _ in [0]*h]
    memo = [[0]*w for _ in [0]*h]
    for k in range(h+w):
        for i in range(max(0, k-w+1), min(h, k+1)):
            j = k-i
            if i == j == 0:
                continue
            if i == 0:
                memo[i][j] = memo[i][j-1]+(grid[i][j] != grid[i][j-1])
            elif j == 0:
                memo[i][j] = memo[i-1][j]+(grid[i][j] != grid[i-1][j])
            else:
                memo[i][j] = min(memo[i][j-1]+(grid[i][j] != grid[i][j-1]),
                                 memo[i-1][j]+(grid[i][j] != grid[i-1][j]))
    print((memo[h-1][w-1]+(grid[0][0] == "#")+(grid[h-1][w-1] == "#"))//2)


main()

Submission status: Accepted

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


def change(val):
    # 黒なら1
    if val == '#':
        return 1

    # 白なら0
    return 0


# def calc_root(board):


def main():
    h, w = map(int, input().split())
    board = [[s for s in input()] for i in range(h)]

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

    for i_row, row in enumerate(dp):
        for i_col, col in enumerate(row):
            if i_row == 0 and i_col == 0:
                dp[i_row][i_col] = change(board[i_row][i_col])
                continue

            if i_row >= 1:
                if board[i_row][i_col] == '#' and board[i_row - 1][i_col] == '.':
                    dp[i_row][i_col] = min(dp[i_row - 1][i_col] + 1, dp[i_row][i_col])
                else:
                    dp[i_row][i_col] = min(dp[i_row - 1][i_col], dp[i_row][i_col])

            if i_col >= 1:
                if board[i_row][i_col] == '#' and board[i_row][i_col - 1] == '.':
                    dp[i_row][i_col] = min(dp[i_row][i_col - 1] + 1, dp[i_row][i_col])
                else:
                    dp[i_row][i_col] = min(dp[i_row][i_col - 1], dp[i_row][i_col])

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


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
def main():
  import sys
  input=sys.stdin.buffer.readline
  h,w=map(int,input().split())
  t,*s,_=input()
  if t==46:c,f=0,False
  else:c,f=1,True
  p=[(c,f)]
  for t in s:
    g=t==35
    if g!=f:
      c+=1
      f=not f
    p+=(c,f),
  d=p
  for _ in range(h-1):
    t,*s,_=input()
    c,f=d[0]
    g=t==35
    if g!=f:
      c+=1
      f=not f
    p=[(c,f)]
    for i,t in enumerate(s,1):
      e,h=d[i]
      g=t==35
      if h!=g:
        e+=1
        h=not h
      if f!=g:
        c+=1
        f=not f
      if e<c:
        c,f=e,h
      p+=(c,f),
    d=p
  print(d[-1][0]+1>>1)
main()

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline
H,W=map(int,input().split())
S=[list(input()) for i in range(H)]
dp=[0]*W
if S[0][0]=='#':
  dp[0]=1
for j in range(1,W):
  if S[0][j]!=S[0][j-1] and S[0][j-1]=='.':
    dp[j]=dp[j-1]+1
  else:
    dp[j]=dp[j-1]
for i in range(1,H):
  if S[i][0]!=S[i-1][0] and S[i-1][0]=='.':
    dp[0]=dp[0]+1
  for j in range(1,W):
    hidari=1 if S[i][j]!=S[i][j-1] and S[i][j-1]=='.' else 0
    ue=1 if S[i][j]!=S[i-1][j] and S[i-1][j]=='.' else 0
    dp[j]=min(dp[j-1]+hidari,dp[j]+ue)
print(dp[-1])

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(10**6)
h,w=map(int,input().split())
s=[list(input())for i in range(h)]
t=[[""for i in range(w)] for j in range(h)]
t[0][0]=(1 if s[0][0]=="#" else 0)
def f(x,y):
    if t[x][y]!="":
        return t[x][y]
    else:
        t[x][y]=min((f(x-1,y)+(s[x][y]=="#" and s[x][y]!=s[x-1][y]) if x>0 else float("INF")),(f(x,y-1)+(s[x][y]=="#" and s[x][y]!=s[x][y-1]) if y>0 else float("INF")))
        return t[x][y]
print(f(h-1,w-1))

Submission status: Accepted

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

G = [['0'] * (W + 2)]
for _ in range(H):
    tmp = ['0'] + list(input()) + ['0']
    G.append(tmp)
G.append(['0'] * (W + 2))

move = [[1, 0], [0, 1]]

INF = 10 ** 6
ans = [[INF] * (W + 2) for _ in range(H + 2)]
if G[1][1] == '.':
    ans[1][1] = 0
else:
    ans[1][1] = 1


stack = [[1, 1]]
while stack:
    tmp = stack.pop()
    x, y = tmp[0], tmp[1]
    for dx, dy in move:
        nx = x + dx
        ny = y + dy
        if G[nx][ny] == '0':
            continue
        elif G[nx][ny] == '.':
            if ans[nx][ny] > ans[x][y]: #更新できるとき
                ans[nx][ny] = ans[x][y]
                stack.append([nx, ny])
        else:
            if G[x][y] == '.': #白から黒色への変わり目
                if ans[nx][ny] > ans[x][y] + 1:
                    ans[nx][ny] = ans[x][y] + 1
                    stack.append([nx, ny])
            else:
                if ans[nx][ny] > ans[x][y]: #更新できるとき
                    ans[nx][ny] = ans[x][y]
                    stack.append([nx, ny])
                    
print (ans[H][W])

# for tmp in ans:
#     print (tmp)

Submission status: Accepted

Solution code:
h,w = map(int,input().split())
map1 = []
map1.append([("n") for _ in range(w+1)])
for _ in range(h):
	map1.extend([list("n"+input())])

check_board = [[0]*(w+1) for _ in range(h+1)]

def cal_ans(a,b,x,y):
	return ((map1[a][b]^map1[x][y])&map1[x][y])+check_board[a][b]

for x in range(h+1):
	for y in range(w+1):
		if map1[x][y] == "#":
			map1[x][y] = 1
		else:
			if map1[x][y] == "n":
				check_board[x][y] = 3000
			map1[x][y] = 0
for x in range(1,h+1):
	for y in range(1,w+1):
		if x == 1 and y == 1:
			if map1[x][y] == 1:
				check_board[x][y] = 1
			continue
		check_board[x][y] = min(cal_ans(x-1,y,x,y),cal_ans(x,y-1,x,y))
print(check_board[h][w])

Submission status: Accepted

Solution code:
H, W = map(int, input().split())
#field = [list(input()) for _ in range(H)]
field =[["."] * (W+1)]
for _ in range(H):
    tmp = ["."]
    tmp.extend(list(input()))
    field.append(tmp)

dp = [[10**9] * (W+1) for _ in range(H+1)]
dp[1][0] = 0
dp[0][1] = 0
for h in range(1,H+1):
    for w in range(1,W+1):
        if field[h][w] == ".":
            dp[h][w] = min(dp[h-1][w], dp[h][w-1])
        else:
            u = dp[h-1][w] if field[h-1][w] == "#" else dp[h-1][w] + 1
            l = dp[h][w-1] if field[h][w-1] == "#" else dp[h][w-1] + 1
            dp[h][w] = min(u,l)

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

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:
import sys

sys.setrecursionlimit(10**6)

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

INF=1000
mymap=list()

for i in range(H):
    mymap.append(input().rstrip())

#print(mymap)

costmap=[[INF for i in range(W)] for j in range(H)]
#print(costmap)

def make_costmap(i,j,prev_state,c):
    #print(i,j,prev_state,c)
    state=mymap[i][j]
    if (prev_state == "." and state=="#"):
        c+=1
    if costmap[i][j] == INF or costmap[i][j]>c:
        costmap[i][j]=c
    else:
        return
        
    if (i<H-1):
        make_costmap(i+1,j,state,c)
    if (j<W-1):        
        make_costmap(i,j+1,state,c)
    return

make_costmap(0,0,".",0)

#for i in range(H):
#    print(mymap[i])
#for i in range(H):
#    print(costmap[i])

print(costmap[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:
def f(c):
    if c == "#":
        ret = 1
    else:
        ret = 0

    return ret


h, w = map(int, input().split())
s = [list(map(f, "#" * (w + 1)))]
for _ in range(h):
    s.append([1] + list(map(f, input())))
INF = 100 * 100

dp = [[[INF] * 2 for _ in range(w + 1)] for _ in range(h + 1)]
dp[1][1][s[1][1]] = s[1][1]

for i, (row_u, row) in enumerate(zip(s, s[1:]), 1):
    for j, (el, eu, e) in enumerate(zip(row, row_u[1:], row[1:]), 1):
        dp[i][j][e] = min(dp[i][j][e], dp[i-1][j][eu] + (eu + e) % 2, dp[i][j-1][el] + (el + e) % 2)

ans = dp[h][w][s[h][w]]
ans = (ans + 1) // 2
print(ans)

Submission status: Accepted

Solution code:
def main():
  import sys
  b=sys.stdin.buffer
  h,w=map(int,b.readline().split())
  x=w+1
  s=[c>>3for c in b.read()]
  dp=[10000]*h*x
  a=p=s[0]
  dp[0]=b=q=5-a
  for i in range(w):
    t=s[i]
    b+=a^t
    dp[i]=b
    a=t
  for i in range(x,h*x,x):
    t=s[i]
    q+=p^t
    dp[i]=b=q
    a=p=t
    k=i-w
    for j in range(i+1,i+w):
      sj=s[j]
      b+=a^sj
      t=dp[k]+(s[k]^sj)
      k+=1
      if b>t:b=t
      dp[j]=b
      a=sj
  print(b+1>>1)
main()

Submission status: Accepted

Solution code:
def main():
  import sys
  b=sys.stdin.buffer
  h,w=map(int,b.readline().split())
  x=w+1
  s=[c>>3for c in b.read()]
  dp=[10000]*h*x
  a=p=s[0]
  dp[0]=b=q=5-a
  for i in range(w):
    t=s[i]
    b+=a^t
    dp[i]=b
    a=t
  for i in range(x,h*x,x):
    t=s[i]
    q+=p^t
    dp[i]=b=q
    a=p=t
    k=i-x
    for j in range(i+1,i+w):
      sj=s[j]
      b+=a^sj
      k+=1
      t=dp[k]+(s[k]^sj)
      if b>t:b=t
      dp[j]=b
      a=sj
  print(b+1>>1)
main()

Submission status: Accepted

Solution code:
def main():
  import sys
  b=sys.stdin.buffer
  h,w=map(int,b.readline().split())
  x=w+1
  s=[5-c//8for c in b.read()]
  dp=[10000]*h*x
  dp[0]=a=b=p=q=s[0]
  for i in range(w):
    t=s[i]
    b+=a^t
    dp[i]=b
    a=t
  for i in range(x,h*x,x):
    t=s[i]
    q+=p^t
    dp[i]=b=q
    a=p=t
    for j in range(i+1,i+w):
      sj=s[j]
      b+=a^sj
      k=j-x
      t=dp[k]+(s[k]^sj)
      if b>t:b=t
      dp[j]=b
      a=sj
  print(b+1>>1)
main()

Submission status: Accepted

Solution code:
def main():
  import sys
  b=sys.stdin.buffer
  h,w=map(int,b.readline().split())
  x=w+1
  s=[c>>3for c in b.read()]
  dp=[10000]*h*x
  a=p=s[0]
  dp[0]=b=q=5-a
  for i in range(w):
    t=s[i]
    b+=a^t
    dp[i]=b
    a=t
  for i in range(x,h*x,x):
    t=s[i]
    q+=p^t
    dp[i]=b=q
    a=p=t
    for j in range(i+1,i+w):
      sj=s[j]
      b+=a^sj
      k=j-x
      t=dp[k]+(s[k]^sj)
      if b>t:b=t
      dp[j]=b
      a=sj
  print(b+1>>1)
main()

Submission status: Accepted

Solution code:
def main():
  import sys
  b=sys.stdin.buffer
  h,w=map(int,b.readline().split())
  x=w+1
  s=[c>>3for c in b.read()]
  dp=[10000]*h*x
  a=p=s[0]
  dp[0]=b=q=5-a
  r=range(1,w)
  for i in r:
    t=s[i]
    b+=a^t
    dp[i]=b
    a=t
  for i in range(x,h*x,x):
    t=s[i]
    q+=p^t
    dp[i]=b=q
    a=p=t
    for _ in r:
      i+=1
      si=s[i]
      b+=a^si
      j=i-x
      t=dp[j]+(s[j]^si)
      if b>t:b=t
      dp[i]=b
      a=si
  print(b+1>>1)
main()

Submission status: Accepted

Solution code:
def main():
  import sys
  b=sys.stdin.buffer
  h,w=map(int,b.readline().split())
  x=w+1
  s=[c>>3for c in b.read()]
  dp=[10000]*h*x
  a=p=s[0]
  dp[0]=b=q=5-a
  r=range(1,w)
  for i in r:
    t=s[i]
    b+=a^t
    dp[i]=b
    a=t
  for i in range(x,h*x,x):
    t=s[i]
    q+=p^t
    dp[i]=b=q
    a=p=t
    for j in r:
      k=i+j
      sk=s[k]
      b+=a^sk
      l=k-x
      t=dp[l]+(s[l]^sk)
      if b>t:b=t
      dp[k]=b
      a=sk
  print(b+1>>1)
main()

Submission status: Accepted

Solution code:
def main():
  import sys
  b=sys.stdin.buffer
  h,w=map(int,b.readline().split())
  x=w+1
  s=[c>>3for c in b.read()]
  dp=[10000]*h*x
  a=p=s[0]
  dp[0]=b=q=5-a
  for i in range(1,w):
    t=s[i]
    b+=a^t
    dp[i]=b
    a=t
  for i in range(x,h*x,x):
    t=s[i]
    q+=p^t
    dp[i]=b=q
    a=p=t
    for j in range(1,w):
      k=i+j
      sk=s[k]
      b+=a^sk
      l=k-x
      t=dp[l]+(s[l]^sk)
      if b>t:b=t
      dp[k]=b
      a=sk
  print(b+1>>1)
main()

Submission status: Accepted

Solution code:
def main():
  import sys
  b=sys.stdin.buffer
  h,w=map(int,b.readline().split())
  x=w+1
  s=[c>>3for c in b.read()]
  dp=[10000]*h*x
  a=p=s[0]
  dp[0]=b=q=5-a
  for i in range(1,w):
    t=s[i]
    dp[i]=b=b+(a^t)
    a=t
  for i in range(x,h*x,x):
    t=s[i]
    dp[i]=b=q=q+(p^t)
    a=p=t
    for j in range(1,w):
      k=i+j
      sk=s[k]
      b+=a^sk
      l=k-x
      t=dp[l]+(s[l]^sk)
      if b>t:b=t
      dp[k]=b
      a=sk
  print(b+1>>1)
main()

Submission status: Accepted

Solution code:
def main():
  import sys
  b=sys.stdin.buffer
  h,w=map(int,b.readline().split())
  x=w+1
  s=[c>>3for c in b.read()]
  dp=[10000]*h*x
  a=p=s[0]
  dp[0]=b=q=5-a
  for i in range(1,w):
    t=s[i]
    dp[i]=b=b+(a^t)
    a=t
  for i in range(x,h*x,x):
    t=s[i]
    dp[i]=b=q=q+(p^t)
    a=p=t
    for j in range(1,w):
      k=i+j
      sk=s[k]
      t=b+(a^sk)
      l=k-x
      u=dp[l]+(s[l]^sk)
      if t>u:t=u
      dp[k]=b=t
      a=sk
  print(b+1>>1)
main()

Submission status: Accepted

Solution code:
def main():
  import sys
  b=sys.stdin.buffer
  h,w=map(int,b.readline().split())
  x=w+1
  s=[c>>3for c in b.read()]
  dp=[10000]*h*x
  a=p=s[0]
  dp[0]=b=q=5-a
  for i in range(1,w):
    t=s[i]
    dp[i]=b=b+(a^t)
    a=t
  for i in range(x,h*x,x):
    t=s[i]
    dp[i]=q=q+(p^t)
    p=t
    for j in range(1,w):
      k=i+j
      sk=s[k]
      l=k-1
      t=dp[l]+(s[l]^sk)
      l=k-x
      u=dp[l]+(s[l]^sk)
      if t>u:t=u
      dp[k]=t
  print(dp[-2]+1>>1)
main()

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

Solution code:
def main():
  import sys
  b=sys.stdin.buffer
  h,w=map(int,b.readline().split())
  x=w+1
  s=[c>>3for c in b.read()]
  dp=[10000]*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):
    l=i-x
    dp[i]=dp[l]+(s[l]^s[i])
    for j in range(1,w):
      k=i+j
      l=k-1
      t=dp[l]+(s[l]^s[k])
      l=k-x
      u=dp[l]+(s[l]^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
  b=sys.stdin.buffer
  h,w=map(int,b.readline().split())
  x=w+1
  s=[c>>3for c in b.read()]
  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()