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 math
from collections import deque
def main():
    h,w = tuple([int(t)for t in input().split()])

    s = [['.']*(w+1)]

    s.extend(([list('.'+input()) for _ in range(h)]))

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

    for i in range(h):
        if s[i+1][1] == '.':
            dp[i+1][1] = dp[i][1]
        else:
            if s[i][1]=='.':
                dp[i+1][1] = dp[i][1]+1
            else:
                dp[i+1][1] = dp[i][1]

    for j in range(w):
        if s[1][j+1] == '.':
            dp[1][j+1] = dp[1][j]
        else:
            if s[1][j]=='.':
                dp[1][j+1] = dp[1][j]+1
            else:
                dp[1][j+1] = dp[1][j]

    for i in range(1,h):
        for j in range(1,w):
            if s[i+1][j+1] == '.':
                dp[i+1][j+1] = min(dp[i][j+1],dp[i+1][j])
            else:
                if s[i][j+1] == '.':
                    if s[i+1][j] == '.':
                        dp[i+1][j+1] = min(dp[i][j+1],dp[i+1][j])+1
                    else:
                        dp[i+1][j+1] = min(dp[i][j+1]+1,dp[i+1][j])
                else:
                    if s[i+1][j] == '.':
                        dp[i+1][j+1] = min(dp[i][j+1],dp[i+1][j]+1)
                    else:
                        dp[i+1][j+1] = min(dp[i][j+1],dp[i+1][j])

    print(dp[-1][-1])
if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
def update(i,j):

    tmp_A = 200
    tmp_B = 200
    
    if 0 < i < H and j < W:
        if table[i-1][j] == table[i][j]:
            tmp_A = colormap[i-1][j]
        else:
            if table[i-1][j]:
                tmp_A = colormap[i-1][j] + 1
            else:
                tmp_A = colormap[i-1][j]
    if i < H and 0 < j < W:
        if table[i][j-1] == table[i][j]:
            tmp_B = colormap[i][j-1]
        else:
            if table[i][j-1]:
                tmp_B = colormap[i][j-1] + 1
            else:
                tmp_B = colormap[i][j-1]
    
    colormap[i][j] = min(tmp_A, tmp_B)

H, W = map(int, input().split())
table = []
for i in range(H):
    table.append([(True if x == "." else False) for x in list(input())])

colormap = [[0 for _ in range(W)] for _ in range(H)]
colormap[0][0] = 0 if table[0][0] else 1

for i in range(H):
    for j in range(W):
        if not(i == 0 and j ==0):
            update(i, j)
    # print(colormap)

# 必要反転回数
print(colormap[H-1][W-1])

Submission status: Accepted

Solution code:
import sys
from collections import deque
sys.setrecursionlimit(1000*1000)

H,W = map(int,list(input().split()))
grid = []
for i in range(H):
  S = input()
  grid.append( [S[i] for i in range(W) ])

#方向ベクトル 今回は右と下への移動のみを考える　
#つまり行と列番号を増やす向きのみ考える
dx = [1,0]
dy = [0,1]

#####白マスの中を泳ぐdfsの定義
def wdfs(h,w,grid,seen,l_b):
  #白マスの時にかぎり以下を行う
  if seen[h][w] == False and grid[h][w] == ".":
    seen[h][w] = True
    for i in range(2):
      new_h = h + dy[i]
      new_w = w + dx[i]

      #場外アウトしたり、移動先が壁の場合はスルー
      if (new_h<0 or new_w <0 or new_h>=H or new_w >= W ):
        continue
      #移動先が黒マスの時はスルー
      elif grid[new_h][new_w] == "#":
        l_b.append([new_h,new_w])
        continue
      #移動先が探索済みの場合スルー
      elif seen[new_h][new_w] == True:
        continue
      wdfs(new_h,new_w,grid,seen,l_b)  
  #最初のマスが黒かった時    
  else:
    l_b.append([h,w])           
#####dfsの定義

#####黒マスの中を泳ぐdfsの定義
def bdfs(h,w,grid,seen,l_w):
  if seen[h][w] == False:
    seen[h][w] = True
    
    for i in range(2):
      new_h = h + dy[i]
      new_w = w + dx[i]

      #場外アウトの場合はスルー
      if (new_h<0 or new_w <0 or new_h>=H or new_w >= W ):
        continue
      #移動先が白マスの時はスルー
      elif grid[new_h][new_w] == ".":
        l_w.append([new_h,new_w])
        continue
      #移動先が探索済みの場合スルー
      elif seen[new_h][new_w] == True:
        continue
      bdfs(new_h,new_w,grid,seen,l_w)  
#####dfsの定義

#探索
seen = [ [False for i in range(W)] for i in range(H) ]
cnt = 0
l_w =deque( [[0,0]] )
l_b =deque([])


while seen[H-1][W-1] == False:
  while len(l_w) > 0: 
    w = l_w.popleft()
    wdfs(w[0],w[1],grid,seen,l_b)
  if seen[H-1][W-1] == True:
    break

  cnt = cnt+1

  while len(l_b) > 0: 
    b = l_b.popleft()
    bdfs(b[0],b[1],grid,seen,l_w)
  if seen[H-1][W-1] == True:
    break

###
print(cnt)

Submission status: Accepted

Solution code:
import numpy as np

h, w = map(int, input().split())
grid = np.array(['*'*(w+2)] + ['*'+input()+'*' for _ in range(h)] + ['*'*(w+2)])

cnt = np.full((h+3, w+3), h+w, dtype=np.int)
MAX = h + w
for i in range(1, h+2):
    for k in range(1, w+2):
        if i == k == 1:
            cnt[i+1][k+1] = 1 if grid[i][k] == '#' else 0
        else:
            if grid[i][k] == '#':
                if grid[i-1][k] == '#':
                    a = cnt[i][k+1]
                elif grid[i-1][k] == '.':
                    a = cnt[i][k+1] + 1
                else:
                    a = MAX
                if grid[i][k-1] == '#':
                    b = cnt[i+1][k]
                elif grid[i][k-1] == '.':
                    b = cnt[i+1][k] + 1
                else:
                    b = MAX
                cnt[i+1][k+1] = min(a, b)
            else:
                cnt[i+1][k+1] = min(cnt[i][k+1], cnt[i+1][k])

print(cnt[h+1][w+1])

Submission status: Accepted

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

INF = float('inf')
dp = [[[INF, s[h][w]] for w in range(W)] for h in range(H)]

def update_dp_1(c, dp):
  if dp[1] == ".":
    if c == ".":
      res = [dp[0], "."]
    else:  # c == "#"
      res = [dp[0]+1, "#"]
  else:  # dp[1] == "#"
    if c == ".":
      res = [dp[0], "."]
    else:  # c == "#"
      res = [dp[0], "#"]
  return res

def update_dp_2(c, dp_a, dp_b):
  a = update_dp_1(c, dp_a)
  b = update_dp_1(c, dp_b)
  if a[0] < b[0]:
    return a
  else:
    return b

if s[0][0] == ".":
  dp[0][0] = [0, "."]
else:  #  == "#"
  dp[0][0] = [1, "#"]

for h in range(H):
  if h != 0:
    dp[h][0] = update_dp_1(dp[h][0][1], dp[h-1][0])
  for w in range(1, W):
    if h == 0:
      dp[h][w] = update_dp_1(dp[h][w][1], dp[h][w-1])
    else:
      dp[h][w] = update_dp_2(dp[h][w][1], dp[h-1][w], dp[h][w-1])

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

Submission status: Accepted

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

dp = np.zeros(h * w).reshape(h, w)

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

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

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

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
H, W = map(int, input().split())
HW_list = []

for i in range(H):
    HW_list.append(str(input()))

dp = [[H * W] * W] * H

dp[0][0] = 0
for i in range(H):
    for j in range(W):
        if i == 0 and j == 0:
            continue
        if i == 0:
            min_num_h = H * W
        else:
            min_num_h = dp[i - 1][j] + (0 if HW_list[i][j] == HW_list[i - 1][j] else 1)
        if j == 0:
            min_num_w = H * W
        else:
            min_num_w = dp[i][j - 1] + (0 if HW_list[i][j] == HW_list[i][j - 1] else 1)
        dp[i][j] = min(min_num_h, min_num_w)

print(dp[H - 1][W - 1] // 2 + (1 if HW_list[0][0] == "#" or HW_list[H - 1][W - 1] == "#" else 0))

Submission status: Accepted

Solution code:
from collections import deque

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


def bfs0(white_cells, black_cells):

    while white_cells:
        h, w = white_cells.popleft()
        if h==0 and w==0 and grid[h][w] == "#":
            black_cells.append((h, w))
            return black_cells

        for dy, dx in ((1, 0), (0, 1)):
            new_h = h + dy
            new_w = w + dx
            if new_h < 0 or H <= new_h or new_w < 0 or W <= new_w:
                continue
            if grid[new_h][new_w] == ".":
                if (new_h, new_w) not in white_cells:
                    white_cells.append((new_h, new_w))
            else:
                if (new_h, new_w) not in black_cells:
                    black_cells.append((new_h, new_w))
            if new_h == H-1 and new_w == W-1:
                if grid[new_h][new_w] == ".":
                    return 1
                else:
                    return 0

    return black_cells


def bfs1(black_cells, white_cells):

    while black_cells:
        h, w = black_cells.popleft()
        for dy, dx in ((1, 0), (0, 1)):
            new_h = h + dy
            new_w = w + dx
            if new_h < 0 or H <= new_h or new_w < 0 or W <= new_w:
                continue
            if grid[new_h][new_w] == "#":
                if (new_h, new_w) not in black_cells:
                    black_cells.append((new_h, new_w))
            else:
                if (new_h, new_w) not in white_cells:
                    white_cells.append((new_h, new_w))
            if new_h == H-1 and new_w == W-1:
                if grid[new_h][new_w] == "#":
                    return 1
                else:
                    return 0

    return white_cells

count = 0
ans = 0

if count == 0:
    white_cells = deque()
    white_cells.append((0, 0))
    black_cells = deque()

while black_cells != 1 and white_cells != 1 and black_cells != 0 and white_cells != 0:
    if count % 2 == 0:
        a = 1
        temp_black_cells = bfs0(white_cells, black_cells)
        black_cells = temp_black_cells
        ans += 1
    else:
        a = 0
        temp_white_cells = bfs1(black_cells, white_cells)
        white_cells = temp_white_cells
    count += 1

if black_cells == 1:
    ans -=1

print(ans)

Submission status: Accepted

Solution code:
from collections import deque

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

ans = 10**9

visited_list = [[10**9]*W for _ in range(H)]

if C[0][0] == "#": 
    stack = deque([[0, 0, 1]])
    visited_list[0][0] = 1
else:
    stack = deque([[0, 0, 0]])
    visited_list[0][0] = 0

def dfs(town, visited_list, stack):
    global ans
    while len(stack) > 0:
        h, w, cnt = stack.pop()
        if h == H-1 and w == W-1 and ans > cnt:
            ans = cnt
            continue
        for j, k in ([1, 0], [0, 1]):
            new_h, new_w = h+j, w+k
            if new_h < 0 or new_h >= H or new_w < 0 or new_w >= W:
                continue
            if  town[new_h][new_w] != "#" and visited_list[new_h][new_w] > cnt:
                visited_list[new_h][new_w] = cnt
                stack.append([new_h, new_w, cnt])
            elif town[h][w] == "#" and town[new_h][new_w] == "#" and visited_list[new_h][new_w] > cnt:
                visited_list[new_h][new_w] = cnt
                stack.append([new_h, new_w, cnt])
            elif town[new_h][new_w] == "#" and visited_list[new_h][new_w] > cnt + 1:
                visited_list[new_h][new_w] = cnt + 1
                # print("a " + str(cnt+1))
                stack.append([new_h, new_w, cnt+1])
    return ans

print(dfs(C, visited_list, stack))

Submission status: Accepted

Solution code:
import copy

H, W = map(int,input().split())
root_list = []
for _ in range(H):
    root_list.append(list(str(input())))


change_list = copy.deepcopy(root_list)
DP_list = []

for i, line in enumerate(root_list):
    DP_line = []
    str_pt = root_list[i][0]
    if i == 0:
        DP_line.append(0) # 初期値
    else:
        if root_list[i-1][0] == line[0]: # 1文字目が上下一致
            DP_line.append(DP_list[i-1][0])
        else:
            DP_line.append(DP_list[i-1][0] + 1)

    for j, pt in enumerate(line[1:], 1): # 先頭は抜かす
        if i == 0: # 1行目
            if str_pt == pt: # 前の文字と一致
                DP_line.append(DP_line[j-1]) # 前の値を入れる
            else:
                DP_line.append(DP_line[j-1] + 1) # 違ったら1足す
                str_pt = pt
        else: # 2行目以降（上下左右比較）
            # 横比較
            if str_pt == pt:
                yoko_pt = DP_line[j-1]
            else:
                yoko_pt = DP_line[j-1] + 1
            
            # 縦比較
            if pt == root_list[i-1][j]:
                tate_pt = DP_list[i-1][j]
            else:
                tate_pt = DP_list[i-1][j] + 1
            
            DP_line.append(min(yoko_pt, tate_pt))
            str_pt = pt

    DP_list.append(DP_line)

result = DP_list[H-1][W-1] // 2

if root_list[0][0] == "#":
    result += 1
if root_list[H-1][W-1] == "#":
    result += 1
if  root_list[0][0] == "#" and root_list[H-1][W-1] == "#":
    if result == 2 or (H == 1 and W == 1):
        result = 1
    else:
        result -= 1

print(result)

Submission status: Accepted

Solution code:
H,W = map(int,input().split())
A = []
for i in range(H):
	s = list(input())
	A.append([0 if c == "." else 1 for c in s])
dist = [[0 if r == 0 and c == 0 else 1000 for c in range(W)] for r in range(H)]
for r in range(H):
	for c in range(W):
		if c == 0 and r == 0:
			continue
		if r == 0:
			dist[r][c] = dist[r][c-1] + int(abs(A[r][c] - A[r][c-1]))
		elif c == 0:
			dist[r][c] = dist[r-1][c] + int(abs(A[r][c] - A[r-1][c]))
		else:
			dist[r][c] = min(dist[r][c-1] + int(abs(A[r][c] - A[r][c-1])), dist[r-1][c] + int(abs(A[r][c] - A[r-1][c])))
ans = (dist[H-1][W-1] + 1) // 2
if A[0][0] == 1 and A[H-1][W-1] == 1:
	print(ans + 1)
else:
	print(ans)

Submission status: Accepted

Solution code:
# import sys
# input = sys.stdin.readline
h,w=map(int,input().split())
infi=10**10
D=[list(input()) for i in range(h)]
kotae=[[infi]*(w) for _ in range(h)]
# D[i][j]はD[h-1][w-1]まで

cnt=0
if D[0][0]=='.':
    kotae[0][0]=0
else:
    kotae[0][0]=1
    cnt+=1
for i in range(1,h):
    if D[i][0]=='#' and D[i-1][0]=='.':
        cnt+=1
    kotae[i][0]=cnt

cnt=0
if D[0][0]=='.':
    kotae[0][0]=0
else:
    kotae[0][0]=1
    cnt+=1
for j in range(1,w):
    if D[0][j]=='#' and D[0][j-1]=='.':
        cnt+=1
    kotae[0][j]=cnt
for i in range(h-1):
    for j in range(w-1):
        kouho1 = kotae[i][j+1]
        if D[i][j+1]=='.' and D[i+1][j+1]=='#':
            kouho1+=1
        kouho2=kotae[i+1][j]
        if D[i+1][j]=='.' and D[i+1][j+1]=='#':
            kouho2+=1
        kotae[i+1][j+1]=min(kouho1,kouho2)
print(kotae[h-1][w-1])

Submission status: Accepted

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

for h in range(H):
    for w in range(W):
        if h==0:
            if w==0: #原点
                if s[h][w]=="#":
                    M[h][w]=1
            elif w>0: #最上行
                if s[h][w]==".":
                    M[h][w]=M[h][w-1]
                else:
                    if s[h][w-1]=="#":
                        M[h][w]=M[h][w-1]
                    else:
                        M[h][w]=M[h][w-1]+1
        elif w==0: #最左列
            if s[h][w]==".":
                M[h][w]=M[h-1][w]
            else:
                if s[h-1][w]=="#":
                    M[h][w]=M[h-1][w]
                else:
                    M[h][w]=M[h-1][w]+1
        else: #一般的な位置
            if s[h][w]==".":
                M[h][w]=min(M[h-1][w],M[h][w-1])
            else:
                if s[h-1][w]=="." and s[h][w-1]==".":
                    M[h][w]=min(M[h-1][w],M[h][w-1])+1
                elif s[h-1][w]=="#" and s[h][w-1]==".":
                    M[h][w]=min(M[h-1][w],M[h][w-1]+1)
                elif s[h-1][w]=="." and s[h][w-1]=="#":
                    M[h][w]=min(M[h-1][w]+1,M[h][w-1])
                else:
                    M[h][w]=min(M[h-1][w],M[h][w-1])

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

Submission status: Accepted

Solution code:
from collections import deque
import math
import sys

h,w = map(int,input().split())
s = [0] * h
for i in range(h):
     s[i] = [i for i in str(input())]
memo = [[300] * w for _ in range(h)]
memo[0][0] = 0
box=[deque([]) for _ in range(w+h-1)]
box[0].append([0,0])
ans = 0
for i in range(w+h-1):
     while box[i]:

          y,x = box[i].popleft()
          if y == h-1 and x == w-1:
               if s[y][x] == '.' and s[0][0] == '.':
                    print(ans//2)
               elif s[y][x] == '.' and s[0][0] == '#' :
                    print((ans+1)//2)
               elif s[y][x] == '#' and s[0][0] == '.':
                    print((ans + 1) // 2)
               else:
                    print(ans//2 + 1)
               sys.exit()
          for k, j in [(1, 0), (0, 1)]:
               nexty, nextx = y + k, x + j
               if nexty < h and nextx < w:
                    if memo[nexty][nextx] > 250:
                         memo[nexty][nextx] = ans
                         if s[nexty][nextx] == s[y][x]:
                              box[i].append([nexty, nextx])

                         elif s[nexty][nextx] != s[y][x]:
                              box[i + 1].append([nexty, nextx])


     ans += 1

Submission status: Accepted

Solution code:
from collections import deque

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

todo = deque([(0,0)])
seen = [[200 for j in range(w)] for i in range(h)]
sx = 0
sy = 0
if hw[0][0] == '.':
    seen[0][0] = 0
else:
    seen[0][0] = 1




while todo:
    sx,sy = todo.popleft()
    if sx + 1 < h and seen[sx+1][sy] == 200:
        todo.append((sx+1,sy))
    if sx + 1 < h and hw[sx+1][sy] == '.' and seen[sx+1][sy] > seen[sx][sy]:
        seen[sx+1][sy] = seen[sx][sy]
    if sx + 1 < h and hw[sx+1][sy] == '#' and seen[sx+1][sy] > seen[sx][sy]+1 and hw[sx][sy] == '.':
        seen[sx+1][sy] = seen[sx][sy]+1
    if sx + 1 < h and hw[sx+1][sy] == '#' and seen[sx+1][sy] > seen[sx][sy] and hw[sx][sy] == '#':
        seen[sx+1][sy] = seen[sx][sy]
    if sy+1 < w and seen[sx][sy+1] == 200:
        todo.append((sx,sy+1))
    if sy + 1 < w and hw[sx][sy+1] == '.' and seen[sx][sy+1] > seen[sx][sy]:
        seen[sx][sy+1] = seen[sx][sy]
    if sy + 1 < w and hw[sx][sy+1] == '#' and seen[sx][sy+1] > seen[sx][sy]+1 and hw[sx][sy] == '.':
        seen[sx][sy+1] = seen[sx][sy]+1
    if sy + 1 < w and hw[sx][sy+1] == '#' and seen[sx][sy+1] > seen[sx][sy] and hw[sx][sy] == '#':
        seen[sx][sy+1] = seen[sx][sy]



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

Submission status: Accepted

Solution code:
import sys
from heapq import heappop, heappush
sys.setrecursionlimit(10000000)

h, w = map(int, input().split())
c = [input() for _ in range(h)]
d = [[10000]*w for _ in range(h)]

que = []
if c[0][0] == '.':
    heappush(que, (0, 0, 0))
    d[0][0] = 0
else:
    heappush(que, (1, 0, 0))
    d[0][0] = 1

while len(que):
    dist, px, py = heappop(que)
    if d[h-1][w-1] < dist:
        break
    for dx, dy in [(0, 1), (1, 0)]:
        qx, qy = px + dx, py + dy
        if not (0 <= qx < h and 0 <= qy < w):
            continue
        if d[qx][qy] > dist:
            if c[px][py]=='.' and c[qx][qy]=='#':
                d[qx][qy] = dist + 1
                heappush(que, (d[qx][qy], qx, qy))
            else:
                d[qx][qy] = dist
                heappush(que, (d[qx][qy], qx, qy))
print(d[h-1][w-1])

Submission status: Accepted

Solution code:
import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

H,W = map(int,readline().split())
S = ''.join(read().decode().split())

INF = 10 ** 9
N = H*W
U = 250
dp = [[INF] * U for _ in range(N)]
# そのマスをいじる回数 → 総回数の最小値
dp[0] = list(range(U))
for n in range(H*W):
    for i in range(U-1,0,-1):
        if dp[n][i-1]> dp[n][i]:
            dp[n][i-1] = dp[n][i]
    for i in range(1,U):
        if dp[n][i-1] + 1 < dp[n][i]:
            dp[n][i] = dp[n][i-1] + 1
    s = S[n]
    if s == '#':
        for i in range(0,U,2):
            dp[n][i] = INF
    else:
        for i in range(1,U,2):
            dp[n][i] = INF
    x,y = divmod(n,W)
    to = []
    if y < W - 1:
        to.append(n+1)
    if x < H - 1:
        to.append(n+W)
    for m in to:
        for i in range(U):
            if dp[m][i] > dp[n][i]:
                dp[m][i] = dp[n][i]

print(min(dp[-1]))

Submission status: Accepted

Solution code:
from collections import deque

h,w = map(int,input().split())
base = []

for i in range(h):
  base.append(input())
  
seen = [-1]*(h*w)
q = deque([])
q.append([0,0])
now_ini = base[0][0]

if now_ini == ".":
  seen[0] = 0
elif now_ini == "#":
  seen[0] = 1

while q:
  r,c = q.popleft()
  now = base[r][c]
  
      

      
  if (r+1<h) and (seen[(r+1)*w+c] == -1):
    if now == base[r+1][c]:
      sign = 0
    elif (now != base[r+1][c]) and (now == "."):
      sign = 1
    elif (now != base[r+1][c]) and (now == "#"):
      sign = 2
      
    if sign == 0:
      q.appendleft([r+1,c])
      seen[(r+1)*w+c] = seen[r*w+c]
    elif sign == 1:
      q.append([r+1,c])
      seen[(r+1)*w+c] = seen[r*w+c] + 1
    elif (sign == 2):
      q.append([r+1,c])
      seen[(r+1)*w+c] = seen[r*w+c]
      
  if (c+1<w) and (seen[r*w+c+1] == -1):
    if now == base[r][c+1]:
      sign = 0
    elif now != base[r][c+1] and (now == "."):
      sign = 1
    elif (now != base[r][c+1]) and (now == "#"):
      sign = 2
      
    if sign == 0:
      q.appendleft([r,c+1])
      seen[r*w+c+1] = seen[r*w+c]
    elif sign == 1:
      q.append([r,c+1])
      seen[r*w+c+1] = seen[r*w+c] + 1
    elif (sign == 2):
      q.append([r,c+1])
      seen[r*w+c+1] = seen[r*w+c]
      
      
print(seen[w*h-1])

Submission status: Accepted

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

dp[0][0] = 1 if lines[0][0] == '#' else 0

for i in range(1, W):
  if lines[0][i-1] != '#' and lines[0][i] == '#':
    dp[0][i] = dp[0][i-1] + 1
  else:
    dp[0][i] = dp[0][i-1]

for i in range(1, H):
  if lines[i-1][0] != '#' and lines[i][0] == '#':
    dp[i][0] = dp[i-1][0] + 1
  else:
    dp[i][0] = dp[i-1][0]

for i in range(1, H):
  for j in range(1, W):
    if lines[i-1][j] != '#' and lines[i][j] == '#':
      a = dp[i-1][j] + 1
    else:
      a = dp[i-1][j]

    if lines[i][j-1] != '#' and lines[i][j] == '#':
      b = dp[i][j-1] + 1
    else:
      b = dp[i][j-1]

    dp[i][j] = min(a, b)

# for l in dp:
#   print(l)
print(dp[H-1][W-1])

Submission status: Accepted

Solution code:
def main():
    from collections import deque

    WHITE = 0
    BLACK = 1

    CHAR = '.', '#'

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

    h = deque()
    x = CHAR.index(s[0][0])
    h.append((x, 0, 0, x))

    cost = [[H * W] * W for _ in range(H)]
    cost[0][0] = x

    while h:
        cnt, r, c, mode = h.popleft()
        if cnt > cost[r][c]:
            continue
        if r == H - 1 and c == W - 1:
            print(cnt)
            return

        delta = int(mode == WHITE)
        ncnt = cnt + delta

        if r < H - 1:
            if s[r + 1][c] == CHAR[mode]:
                if cnt < cost[r + 1][c]:
                    cost[r + 1][c] = cnt
                    h.appendleft((cnt, r + 1, c, mode))
            else:
                if delta:
                    if ncnt < cost[r + 1][c]:
                        cost[r + 1][c] = ncnt
                        h.append((ncnt, r + 1, c, 1 - mode))
                else:
                    if ncnt < cost[r + 1][c]:
                        cost[r + 1][c] = ncnt
                        h.appendleft((ncnt, r + 1, c, 1 - mode))

        if c < W - 1:
            if s[r][c + 1] == CHAR[mode]:
                if cnt < cost[r][c + 1]:
                    cost[r][c + 1] = cnt
                    h.appendleft((cnt, r, c + 1, mode))
            else:
                if delta:
                    if ncnt < cost[r][c + 1]:
                        cost[r][c + 1] = ncnt
                        h.append((ncnt, r, c + 1, 1 - mode))
                else:
                    if ncnt < cost[r][c + 1]:
                        cost[r][c + 1] = ncnt
                        h.appendleft((ncnt, r, c + 1, 1 - mode))


if __name__ == '__main__':
    main()

# import sys
#
# input = sys.stdin.readline
# sys.setrecursionlimit(10 ** 7)
# rstrip()
# int(input())
# map(int, input().split())

Submission status: Accepted

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

dp = {}

# 最短で通ってるやつのうちの連続してる箇所


# Y, X, ひとつ前が#かどうか
def rec(y, x, f):
    if (y, x, f) in dp:
        return dp[(y, x, f)]
    if y == h - 1 and x == w - 1:
        return 0
    if y < 0 or h <= y or x < 0 or w <= x:
        print(10.0 / 0)
    ret = 10**8
    steps = [0, 1, 0]
    for i in range(2):
        next_x, next_y = x + steps[i], y + steps[i + 1]
        if 0 <= next_y < h and 0 <= next_x < w:
            if table[next_y][next_x] == "#":
                if f == True:
                    ret = min(rec(next_y, next_x, True), ret)
                else:
                    ret = min(rec(next_y, next_x, True) + 1, ret)
            else:
                ret = min(rec(next_y, next_x, False), ret)
        else:
            continue
    dp[(y, x, f)] = ret
    return ret


ans = rec(0, 0, True) + 1 if table[0][0] == "#" else rec(0, 0, False)
print(ans)
"""
問題文読み違えてた？
3 3
.##
#.#
#..
だと
2
じゃなくて
1
が正解？

ADD: やっぱり読み違えてたみたいだ 1時間以上ロスしたんだけど 日本語のおべんきょうをやりなおそうね
"""

Submission status: Accepted

Solution code:
import bisect, collections
 
 
 
def solution():
    h, w = [int(x) for x in input().strip().split(" ")]
    b, dp = [], []
    for _ in range(h):
        b.append(input().strip())
        dp.append([0]*w)

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

def main():    
    # T = int(input().strip())
    for _ in range(1):
        solution()

if __name__ == "__main__":
    main()

Submission status: Accepted

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

dp = {}

# 最短で通ってるやつのうちの連続してる箇所


# Y, X, ひとつ前が#かどうか
def rec(y, x, f):
    if (y, x, f) in dp:
        return dp[(y, x, f)]
    if y == h - 1 and x == w - 1:
        # dp[(y, x)] = c
        return 0
    if y < 0 or h <= y or x < 0 or w <= x:
        print(10.0 / 0)
    ret = 10**8
    steps = [0, 1, 0]
    for i in range(2):
        next_x, next_y = x + steps[i], y + steps[i + 1]
        if 0 <= next_y < h and 0 <= next_x < w:
            if table[next_y][next_x] == "#":
                # ret = min(rec(next_y, next_x, c) + 1, ret)
                if f == True:
                    ret = min(rec(next_y, next_x, True), ret)
                else:
                    ret = min(rec(next_y, next_x, True) + 1, ret)
            else:
                # ret = min(rec(next_y, neaxt_x, c), ret)
                ret = min(rec(next_y, next_x, False), ret)
        else:
            continue
    # dp[(y, x, c)] = ret
    dp[(y, x, f)] = ret
    return ret


ans = rec(0, 0, True) + 1 if table[0][0] == "#" else rec(0, 0, False)
print(ans)
"""
問題文読み違えてた？
3 3
.##
#.#
#..
だと
2
じゃなくて
1
が正解？
"""

Submission status: Accepted

Solution code:
H,W=map(int,input().split())
s=[input() for i in range(H)]
m=[[None]*W for i in range(H)]
if s[0][0]==".":
    m[0][0]=0
    t=0
else:
    m[0][0]=1
    t=1
for i in range(1,W):
    if s[0][i-1]!=s[0][i]:
        t+=1
    m[0][i]=t
t=m[0][0]
for i in range(1,H):
    if s[i-1][0]!=s[i][0]:
        t+=1
    m[i][0]=t
for i in range(1,H):
    for j in range(1,W):
        if s[i][j]==s[i-1][j] and s[i][j]==s[i][j-1]:
            m[i][j]=min(m[i-1][j],m[i][j-1])
        elif s[i][j]==s[i-1][j]:
            m[i][j]=min(m[i-1][j],m[i][j-1]+1)
        elif s[i][j]==s[i][j-1]:
            m[i][j]=min(m[i][j-1],m[i-1][j]+1)
        else:
            m[i][j]=min(m[i-1][j],m[i][j-1])+1
print((m[-1][-1]+1)//2)