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: Runtime Error

Solution code:
import sys
sys.setrecursionlimit(10**6)
from math import floor,ceil,sqrt,factorial,log

mod = 10 ** 9 + 7
inf = float('inf')
ninf = -float('inf')
 
#整数input
def ii(): return int(sys.stdin.readline().rstrip()) #int(input())
def mii(): return map(int,sys.stdin.readline().rstrip().split())
def limii(): return list(mii()) #list(map(int,input().split()))
def lin(n:int): return [ii() for _ in range(n)]
def llint(n: int): return [limii() for _ in range(n)]
#文字列input
def ss(): return sys.stdin.readline().rstrip() #input()
def mss(): return sys.stdin.readline().rstrip().split()
def limss(): return list(mss()) #list(input().split())
def lst(n:int): return [ss() for _ in range(n)]
def llstr(n: int): return [limss() for _ in range(n)]

#本当に貪欲法か？ DP法では？？
#本当に貪欲法か？ DP法では？？
#本当に貪欲法か？ DP法では？？

w,h=mii()

mat=[list(ss()) for _ in range(h)]

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

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

Submission status: Runtime Error

Solution code:
def calc(i, j):
    print(f'{i}, {j}')
    global m, scores, H, W
    if scores[i][j] is not None:
        return scores[i][j]
    if i == H - 1 and j == W - 1 and i != 0 and j != 0:
        score = 0
        scores[i][j] = score
        print(f'i: {i}, j: {j}, score: {score}')
        return score
    diff = []
    if j < W - 1:
        diff.append((0, 1))
    if i < H - 1:
        diff.append((1, 0))
#     print(f'diff: {diff}')
    score_cand = []
    for di, dj in diff:
        additional = 0
        if (m[i][j] == '.' and m[i+di][j+dj] == '#') or (i == 0 and j == 0 and m[0][0] == '#'):
            additional += 1 
        score = calc(i+di, j+dj) + additional
        score_cand.append(score)
    score = min(score_cand)
    scores[i][j] = score
    print(f'i: {i}, j: {j}, score: {score}')
    return score

Submission status: Runtime Error

Solution code:
H, W = list(map(int, input().split()))
m = [list(input()) for _ in range(H)]
def calc(i, j):
#     print(f'{i}, {j}')
    global m, scores, H, W
    if i == H - 1 and j == W - 1:
        score = 1 if m[i][j] == '#' else 0
        scores[i][j] = score
        return score
    if scores[i][j] is not None:
        return scores[i][j]
    diff = []
    if j < W - 1:
        diff.append((0, 1))
    if i < H - 1:
        diff.append((1, 0))
#     print(f'diff: {diff}')
    score_cand = []
    for di, dj in diff:
        additional = 1 if m[i][j] == '.' and m[i+di][j+dj] == '#' else 0
        score = calc(i+di, j+dj) + additional
        score_cand.append(score)
    score = min(score_cand)
    scores[i][j] = score
    return score
print(calc(0, 0))

Submission status: Runtime Error

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

# ある経路をきめる.
# そのとき(白マスから黒マスに移動する回数)＝(その経路がいい経路にするための操作回数）
dp = [[float("inf")]*w for _ in range(h)]
if s[0][0] == "#":
    dp[0][0] = 1
else:
    dp[0][0] = 0
# dp[i][j]は00からijに行くときに白マスから黒マスに移動する回数の最小値
for j in range(h):
    for i in range(w):
        if i+1 < w:
            count1 = dp[i][j]
            if s[i][j] == "." and s[i+1][j] == "#":
                count1 += 1
            dp[i+1][j] = min(dp[i+1][j], count1)
        if j+1 < h:
            count2 = dp[i][j]
            if s[i][j] == "." and s[i][j+1] == "#":
                count2 += 1
            dp[i][j+1] = min(dp[i][j+1], count2)
print(dp[h-1][w-1])

Submission status: Runtime Error

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

dp = [[float("inf")]*w for _ in range(h)]
if s[0][0] == "#":
    dp[0][0] = 1
else:
    dp[0][0] = 0

for j in range(h):
    for i in range(w):
        if i+1 < w:
            count1 = dp[i][j]
            if s[i][j] == "." and s[i+1][j] == "#":
                count1 += 1
            dp[i+1][j] = min(dp[i+1][j], count1)
        if j+1 < h:
            count2 = dp[i][j]
            if s[i][j] == "." and s[i][j+1] == "#":
                count2 += 1
            dp[i][j+1] = min(dp[i][j+1], count2)
print(dp[w-1][h-1])

Submission status: Runtime Error

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

# ある経路をきめる.
# そのとき(白マスから黒マスに移動する回数)＝(その経路がいい経路にするための操作回数）
dp = [[float("inf")]*w for _ in range(h)]
if s[0][0] == "#":
    dp[0][0] = 1
else:
    dp[0][0] = 0
# dp[i][j]は00からijに行くときに白マスから黒マスに移動する回数の最小値
for j in range(h):
    for i in range(w):
        if i+1 < w:
            count1 = dp[i][j]
            if s[i][j] == "." and s[i+1][j] == "#":
                count1 += 1
            dp[i+1][j] = min(dp[i+1][j], count1)
        if j+1 < h:
            count2 = dp[i][j]
            if s[i][j] == "." and s[i][j+1] == "#":
                count2 += 1
            dp[i][j+1] = min(dp[i][j+1], count2)
print(dp[w-1][h-1])

Submission status: Runtime Error

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

# ある経路をきめる.
# そのとき(白マスから黒マスに移動する回数)＝(その経路がいい経路にするための操作回数）
count = 0
if s[0][0] == "#":
    count = 1

dp = [[100000]*w for _ in range(h)]
dp[0][0] = count
# dp[i][j]は00からijに行くときに白マスから黒マスに移動する回数の最小値
for j in range(h):
    for i in range(w):
        if i+1 < w:
            count1 = dp[i][j]
            if s[i][j] == "." and s[i+1][j] == "#":
                count1 += 1
            dp[i+1][j] = min(dp[i+1][j], count1)
        if j+1 < h:
            count2 = dp[i][j]
            if s[i][j] == "." and s[i][j+1] == "#":
                count2 += 1
            dp[i][j+1] = min(dp[i][j+1], count2)
print(dp[w-1][h-1])

Submission status: Runtime Error

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

# ある経路をきめる.
# そのとき(白マスから黒マスに移動する回数)＝(その経路がいい経路にするための操作回数）
count = 0
if s[0][0] == "#":
    count = 1

dp = [[100000]*w for _ in range(h)]
dp[0][0] = count
# dp[i][j]は00からijに行くときに白マスから黒マスに移動する回数の最小値
for j in range(h):
    for i in range(w):
        if i+1 < w:
            count1 = dp[i][j]
            if s[i][j] == "." and s[i+1][j] == "#":
                count1 += 1
            dp[i+1][j] = min(dp[i+1][j], count1)
        if j+1 < h:
            count2 = dp[i][j]
            if s[i][j] == "." and s[i][j+1] == "#":
                count2 += 1
            dp[i][j+1] = min(dp[i][j+1], count2)
print(dp[w-1][h-1])

Submission status: Runtime Error

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

# ある経路をきめる.
# そのとき(白マスから黒マスに移動する回数)＝(その経路がいい経路にするための操作回数）
count = 0
if s[0][0] == "#":
    count = 1

dp = [[100000 for _ in range(w)] for _ in range(h)]
dp[0][0] = count
# dp[i][j]は00からijに行くときに白マスから黒マスに移動する回数の最小値
for j in range(h):
    for i in range(w):
        if i+1 < w:
            if s[i][j] == "." and s[i+1][j] == "#":
                dp[i+1][j] = min(dp[i+1][j], dp[i][j] + 1)
            else:
                dp[i+1][j] = min(dp[i+1][j], dp[i][j])
        if j+1 < h:
            if s[i][j] == "." and s[i][j+1] == "#":
                dp[i][j+1] = min(dp[i][j+1], dp[i][j] + 1)
            else:
                dp[i][j+1] = min(dp[i][j+1], dp[i][j])
print(dp[w-1][h-1])

Submission status: Runtime Error

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

# ある経路をきめる.
# そのとき(白マスから黒マスに移動する回数)＝(その経路がいい経路にするための操作回数）
count = 0
if s[0][0] == "#":
    count += 1

dp = [[100000]*w for _ in range(h)]
dp[0][0] = count
# dp[i][j]は00からijに行くときに白マスから黒マスに移動する回数の最小値
for j in range(h):
    for i in range(w):
        if i+1 < w:
            if s[i][j] == "." and s[i+1][j] == "#":
                dp[i+1][j] = min(dp[i+1][j], dp[i][j] + 1)
            else:
                dp[i+1][j] = min(dp[i+1][j], dp[i][j])
        if j+1 < h:
            if s[i][j] == "." and s[i][j+1] == "#":
                dp[i][j+1] = min(dp[i][j+1], dp[i][j] + 1)
            else:
                dp[i][j+1] = min(dp[i][j+1], dp[i][j])
print(dp[w-1][h-1])

Submission status: Runtime Error

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

# ある経路をきめる.
# そのとき(白マスから黒マスに移動する回数)＝(その経路がいい経路にするための操作回数）
count = 0
if s[0][0] == "#":
    count += 1

dp = [[100000]*w for _ in range(h)]
dp[0][0] = count
# dp[i][j]は00からijに行くときに白マスから黒マスに移動する回数の最小値
for i in range(w):
    for j in range(h):
        if i+1 <= w-1:
            if s[i][j] == "." and s[i+1][j] == "#":
                dp[i+1][j] = min(dp[i+1][j], dp[i][j] + 1)
            else:
                dp[i+1][j] = min(dp[i+1][j], dp[i][j])
        if j+1 <= h-1:
            if s[i][j] == "." and s[i][j+1] == "#":
                dp[i][j+1] = min(dp[i][j+1], dp[i][j] + 1)
            else:
                dp[i][j+1] = min(dp[i][j+1], dp[i][j])
print(dp[w-1][h-1])

Submission status: Runtime Error

Solution code:
from collections import deque
import math


def bfs(maze, mazeColor, h, w, sy, sx, gy, gx):
    for y in range(h):
        for x in range(w):
            maze[y][x] = math.inf

    if mazeColor[sy][sx] == '.':
        maze[sy][sx] = 0
    else:
        maze[sy][sx] = 1
    que = deque([[sy, sx]])
    while que:
        y, x = que.popleft()
        for i, j in [(1, 0), (0, 1)]:
            nexty, nextx = y + i, x + j
            distColor = mazeColor[nexty][nextx]
            dist = maze[nexty][nextx]
            if distColor != '#':
                if dist > maze[y][x]:
                    maze[nexty][nextx] = maze[y][x] + 0
                    que.append([nexty, nextx])
            else:
                if dist > maze[y][x]:
                    maze[nexty][nextx] = maze[y][x] + 1
                    que.append([nexty, nextx])

    # for i in range(len(maze[0])):
    #    print(maze[i])
    print(maze[gy][gx])


h, w = map(int, input().split())
mazeColor = ['#'+'#'*w+'#']
for i in range(h):
    mazeColor.append('#'+input()+'#')
mazeColor.append('#'+'#'*w+'#')

maze = [[0 for j in range(w+2)] for i in range(h+2)]

bfs(maze, mazeColor, h+1, w+1, 1, 1, h, w)

Submission status: Runtime Error

Solution code:
from collections import deque
import math


def bfs(maze, mazeColor, h, w, sy, sx, gy, gx):
    for y in range(h):
        for x in range(w):
            maze[y][x] = math.inf

    if mazeColor[sy][sx] == '.':
        maze[sy][sx] = 0
    else:
        maze[sy][sx] = 1
    que = deque([[sy, sx]])
    while que:
        y, x = que.popleft()
        for i, j in [(1, 0), (0, 1)]:
            nexty, nextx = y + i, x + j
            distColor = mazeColor[nexty][nextx]
            dist = maze[nexty][nextx]
            if distColor != '#':
                if dist > maze[y][x]:
                    maze[nexty][nextx] = maze[y][x] + 0
                    que.append([nexty, nextx])
            else:
                if dist > maze[y][x]:
                    maze[nexty][nextx] = maze[y][x] + 1
                    que.append([nexty, nextx])
    print(maze[gy][gx])


h, w = map(int, input().split())
mazeColor = ['#'+'#'*w+'#']
for i in range(h):
    mazeColor.append('#'+input()+'#')
mazeColor.append('#'+'#'*w+'#')

maze = [[0 for j in range(w+2)] for i in range(h+2)]

bfs(maze, mazeColor, h+1, w+1, 1, 1, h, w)

Submission status: Runtime Error

Solution code:
# A - Range Flip Find Route

import sys
sys.setrecursionlimit(10**7)

H, W = map(int, input().split())
S = [[''] * W for _ in range(H)]
for i in range(H):
    S[i] = list(str(input()))

def dfs(x, y, n):
    #print(x, y, n)
    global flg
    global ans
    if x == H-1 and y == W-1:
        ans = min(ans , n)
        #print('ans', ans)
        return ans 
    if y+1 < W:
        if flg == 0:
            if S[x][y+1] == '#':
                if n+1 >= ans:
                    break
                flg = 1
                dfs(x, y+1, n+1)
            else:
                dfs(x, y+1, n)
        elif flg == 1:
            if S[x][y+1] == '.':
                flg = 0
            dfs(x, y+1, n)
    if x+1 < H:
        if flg == 0:
            if S[x+1][y] == '#':
                if n+1 >= ans:
                    break
                flg = 1
                dfs(x+1, y, n+1)
            else:
                dfs(x+1, y, n)
        elif flg == 1:
            if S[x+1][y] == '.':
                flg = 0
            dfs(x+1, y, n)

ans = 10**10
if S[0][0] == '.':
    flg = 0
    dfs(0, 0, 0)
else:
    flg = 1
    dfs(0, 0, 1)

print(ans)

Submission status: Runtime Error

Solution code:
# A - Range Flip Find Route

import numpy as np
H, W = map(int, input().split())
S = np.zeros((W, H), dtype=np.int8)
for i in range(H):
    arr = np.array(list(str(input()))) == '#'
    S[i] = arr.astype(np.int8)

def dfs(x, y, n):
    #print(x, y, n)
    global flg
    global ans
    if x == H-1 and y == W-1:
        ans = min(ans , n)
        #print('ans', ans)
        return ans 
    if y+1 < W:
        if flg == 0:
            if S[x][y+1] == 1:
                flg = 1
                dfs(x, y+1, n+1)
            else:
                dfs(x, y+1, n)
        elif flg == 1:
            if S[x][y+1] == 0:
                flg = 0
            dfs(x, y+1, n)
    if x+1 < H:
        if flg == 0:
            if S[x+1][y] == 1:
                flg = 1
                dfs(x+1, y, n+1)
            else:
                dfs(x+1, y, n)
        elif flg == 1:
            if S[x+1][y] == 0:
                flg = 0
            dfs(x+1, y, n)

ans = 10**10
if S[0][0] == 0:
    flg = 0
    dfs(0, 0, 0)
else:
    flg = 1
    dfs(0, 0, 1)

print(ans)

Submission status: Runtime Error

Solution code:
W,H=list(map(int,input().split()))
l=[list(input()) for i in range(H)]
DP=[[201]*W for i in range(H)]
DP[0][0]=0
for y in range(H):
   for x in range(W):
      if x ==0 and y==0:
         DP[y][x] += 1 if l[y][x] == "#" else 0
         continue
      elif x == 0:
         DP[y][x] = DP[y-1][x]
      elif y == 0:
         DP[y][x] = DP[y][x-1]
      else:
         DP[y][x] = min(DP[y][x-1],DP[y-1][x])
      DP[y][x] += 1 if l[y][x] == "#" else 0
print(DP[H-1][W-1])

Submission status: Runtime Error

Solution code:
W,H=list(map(int,input().split()))
l=[list(input()) for i in range(H)]
DP=[[201]*W for i in range(H)]
DP[0][0]=0
for y in range(H):
   for x in range(W):
      if x ==0 and y==0:
         DP[x][y] += 1 if l[x][y] == "#" else 0
         continue
      elif x == 0:
         DP[x][y] = DP[x][y-1]
      elif y == 0:
         DP[x][y] = DP[x-1][y]
      else:
         DP[x][y] = min(DP[x-1][y],DP[x][y-1])
      DP[x][y] += 1 if l[x][y] == "#" else 0
print(DP[W-1][H-1])

Submission status: Runtime Error

Solution code:
H,W = map(int,input().split())
s = [input() for _ in range(H)]
import math
DP = [[math.inf]+[0]*W for _ in range(H+1)]
re = [[0]*(W+1) for _ in range(H+1)]
DP[0] = [math.inf]*(W+1)
DP[0][1] = DP[1][0] = 0

for i in range(1,H+1):
    for j in range(1,W+1):
        if s[i-1][j-1] == ".":
            DP[i][j] = min(DP[i-1][j],DP[i][j-1])
        else:
            u = DP[i-1][j]+1-re[i-1][j]
            l = DP[i][j-1]+1-re[i][j-1]
            DP[i][j] = min(u, l)
            re[i][j] = 1
            if u < l and re[i-1][j] == 0:
                DP[i][j] += 1
            elif u > l and re[i][j-1] == 0:
                count += 1
            elif u == l:
                count += 1 - re[i-1][j]*re[i][j-1]
                
print(DP[H][W])

Submission status: Runtime Error

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

L=[int(x) for x in range(h+w-2)]
mn=(h+w)//2
import itertools
for route in itertools.permutations(L,h-1):
    route=sorted(route)
    if s[0]=='.':
        t=0
        count=0
    else:
        t=1
        count=2
    k=0
    for i in L:
        if i in route:
            if s[k]!=s[k+1]:
                if t==0:
                    count += 1
                    t=1
                else:
                    t=0
            k += 1
        else:
            if s[k]!=s[k+w]:
                if t==0:
                    count += 1
                    t=1
                else:
                    t=0
            k += w
    mn=min(mn,count)

print(mn)

Submission status: Runtime Error

Solution code:
from collections import deque

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

table = [[None] * W for _ in range(H)]
table[0][0] = (0 if S[0][0] == '.' else 1)

D = deque([(0, 0)])
new_D = deque()
while D:
    h, w = D.popleft()
    for dh, dw in ((1, 0), (0, 1)):
        if 0 <= h + dh < H and 0 <= w + dw < W and table[h + dh][w + dw] is None:
            if S[h + dh][w + dw] == S[h][w]:
                D.append((h + dh, w + dw))
                table[h + dh][w + dw] = table[h][w]
            else:
                new_D.append((h + dh, w + dw))
                table[h + dh][w + dw] = table[h][w] + 1
    if not D:
        D = new_D.copy()
        new_D.clear()

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

Submission status: Runtime Error

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

H, W = map(int, input().split())
s = ['0' * (W+2)]
for _ in range(H):
    s.append('0' + input().rstrip() + '0')
s.append('0' * (W+2))

ans = []
if s[1][1] == '#': a = 1
else: a = 0
temp = [[1, 1, a]]

while temp:
    p = temp.pop()
    for y, x in [[p[0]+1, p[1]], [p[0], p[1]+1]]:
        if s[y][x] == '0':continue
        if s[y][x] == '#' and s[p[0]][p[1]] == '.':
            d = p[2] + 1
        if y == H and x == W:
            ans.append(d)
        else:
            temp.append([y, x, d])
            
print(min(ans))

Submission status: Runtime Error

Solution code:
import queue

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

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

ini = 0
if s[0][0] == '#':
    ini = 1

dist = [[ini for _ in range(W)] for _ in range(H)]
start = (0,0)

qq = queue.Queue()

for i in range(H):
    for j in range(W):
        tgt = []
        if j == 0:
            pass
        else:
            if s[i][j-1] == '.' and s[i][j] == '#':
                tgt.append(dist[i][j-1] + 1)

            else:
                tgt.append(dist[i][j-1])

        if i == 0:
            pass
        else:
            if s[i-1][j] == '.' and s[i][j] == "#":
                tgt.append(dist[i-1][j] + 1)
            else:
                tgt.append(dist[i-1][j])
        if i + j == 0:
            continue
        dist[i][j] = min(tgt)

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

Submission status: Runtime Error

Solution code:

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

def isvalid(r,c):
    return 0 <= r < h and 0 <= c < w

g = [input() for _ in range(h)]
d = [1,0,-1,0]
queue = [(0,0)]
dist = [[1000000]* h for _ in range(w)]
dist[0][0] = 0
if g[0][0] == '#':
    dist[0][0] = 1
while len(queue) > 0:
    next_queue = []
    for r,c in queue:
        for i in range(4):
            cos = dist[r][c]
            nr = r + d[i]
            nc = c + d[1^i]
            if not isvalid(nr,nc):
                continue
            if  g[r][c] != g[nr][nc]:
                cos += 1
            if cos < dist[nr][nc]:
                dist[nr][nc] = cos
                next_queue.append((nr,nc))
    queue = next_queue
print((dist[h-1][w-1] + 1)//2)

Submission status: Runtime Error

Solution code:
#!/usr/bin/env python3


def main() -> None:
    H, W = rmi()
    s = []
    for h in range(H):
        line = list(map(lambda c: c == '.', list(r())))
        s.append(line)
    dp = []
    for _ in range(H):
        dp.append([-1] * W)
    dp[0][0] = 0 if s[0][0] else 1
    for h in range(1, H):
        dp[h][0] = dp[h - 1][0] if s[h][0] else dp[h - 1][0] + 1
    for w in range(1, W):
        dp[0][w] = dp[0][w - 1] if s[0][w] else dp[0][w - 1] + 1
    for h in range(1, H):
        for w in range(1, W):
            minimum = min(dp[h - 1][w], dp[h][w - 1])
            dp[h][w] = minimum if s[h][w] else minimum + 1
    print(dp[H][W])


def r() -> str:
    return input().strip()


def ri() -> int:
    return int(r())


def rmi(delim: str = ' ') -> tuple:
    return tuple(map(int, input().split(delim)))


def w(data) -> None:
    print(data)


def wm(*data, delim: str = ' ') -> None:
    print(delim.join(map(str, data)))


if __name__ == '__main__':
    import sys
    sys.setrecursionlimit(10 ** 9)
    main()

Submission status: Runtime Error

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

for _ in range(W):
    maze.append(list(input()))

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


direction = [[1, 0], [0, 1]]

start = [[0, 0]]

while not [H-1, W-1] in start:

    for s in start:
        r = []
        x, y = s
        for x1, y1 in direction:
            if x+x1 == W or y+y1 == H:
                continue
            if dp[x+x1][y+y1] < dp[x][y]:
                continue
            if maze[x][y] != maze[x+x1][y+y1] and maze[x+x1][y+y1] == '#':
                dp[x+x1][y+y1] = dp[x][y] + 1
            else:
                dp[x+x1][y+y1] = dp[x][y]
            start.append([x+x1, y+y1])


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

Submission status: Runtime Error

Solution code:
import pprint
from itertools import permutations,accumulate

print = pprint.pprint
class solver(object):

    def __init__(self):
        self.H, self.W = tuple(int(i) for i in str.split(input()))
        self.board = tuple(input() for i in range(self.H))
        l = ['r']*(self.W-1)
        for i in range(self.H-1):
            l.append('d')
        self.moves = tuple(permutations(l))

    def solve(self):
        #幅優先で探索するのでなく
        #start -> goalの経路を全パターン生成して各径路の#の数をカウントしたほうが早そう
        def f(m,pt):
            if m == 'r':
                return (pt[0]+1,pt[1])
            else:
                return (pt[0],pt[1]+1)

        def acc(iter, func, initial):
            result = [initial]
            for i in iter:
                result.append(func(i, result[-1]))
            return  result
        # print([path for path in map(lambda m:acc(m,f,(0,0)),self.moves)])
        print(
            min(
                len(
                    ( (self.board[pt[0]][pt[1]] for pt in path if self.board[pt[0]][pt[1]]=='#') for path in map(lambda m:acc(m,f,(0,0)), self.moves))
                )
            )
        )

def main():
    s = solver()
    s.solve()

if __name__ == "__main__":
    main()

Submission status: Runtime Error

Solution code:
import sys
sys.setrecursionlimit(10**6) #再帰関数の上限
import math
from copy import copy, deepcopy
from operator import itemgetter
from bisect import bisect_left, bisect, bisect_right#2分探索
#bisect_left(l,x), bisect(l,x)#aはソート済みである必要あり。aの中からx未満の要素数を返す。rightだと以下
from collections import deque 
#deque(l), pop(), append(x), popleft(), appendleft(x)
##listでqueの代用をするとO(N)の計算量がかかってしまうので注意
from collections import Counter#文字列を個数カウント辞書に、
#S=Counter(l),S.most_common(x),S.keys(),S.values(),S.items()
from itertools import accumulate#累積和
#list(accumulate(l))
from heapq import heapify,heappop,heappush
#heapify(q),heappush(q,a),heappop(q) #q=heapify(q)としないこと、返り値はNone
#import fractions#古いatcoderコンテストの場合GCDなどはここからimportする


def input(): return sys.stdin.readline()[:-1]
def printl(li): print(*li, sep="\n")
def argsort(s, return_sorted=False): 
    inds=sorted(range(len(s)), key=lambda k: s[k])
    if return_sorted: return inds, [s[i] for i in inds]
    return inds
def alp2num(c,cap=False): return ord(c)-97 if not cap else ord(c)-65
def num2alp(i,cap=False): return chr(i+97) if not cap else chr(i+65)

def dfs(H,W,L):
    d=0
    c=True
    if L[0][0]==False:
        d=1
        c=False
    q=deque([(d*10000,c)])
    dxs=((0,1),(1,0))
    while len(q):
        #print(q)
        dxy,c=q.popleft()#ここをpopleftにすると幅優先探索BFSになる
        d,xy=divmod(dxy,10000)
        x,y=divmod(xy,100)
        if x==H-1 and y==W-1:
            return d
        for dx in dxs:
            nx=x+dx[0]
            ny=y+dx[1]
            if nx>=H or ny>=W:
                continue
            if L[nx][ny]:
                q.appendleft((d*10000+nx*100+ny,True))
            else:
                if not c:
                    q.appendleft((d*10000+nx*100+ny,False))
                else:
                    q.append(((d+1)*10000+nx*100+ny,False))

                


def main():
    mod = 10**9+7
    #w.sort(key=itemgetter(1),reversed=True)  #二個目の要素で降順並び替え

    #N = int(input())
    H,W = map(int, input().split())
    #A = tuple(map(int, input().split())) #1行ベクトル
    L = tuple(input() for i in range(H)) #改行ベクトル
    #S = tuple(tuple(map(int, input().split())) for i in range(N)) #改行行列
    Lt=[[True]*H for _ in range(W)]
    for i in range (H):
        for j in range(W):
            if L[i][j]=='#':
                Lt[i][j]=False
            
    ans=dfs(H,W,Lt)

    print(ans)


if __name__ == "__main__":
    main()

Submission status: Runtime Error

Solution code:
from collections import deque
h,w = map(int, input().split())
s = [list(input()) for _ in range(w)]
f = [[-1]*w for _ in range(h)]
flag = 0
stop = [(0,0)]
stopnum = 0
count = 0
stn = 0
while True:
    stack = deque([])
    for i,j in stop:
        stack.append((i,j,s[i][j])) #縦、横、状態、カウント

    while stack:
        #print(stack)
        a,b,c = stack.pop()
        flag = 0
        if (a==h-1 and b==w-1):
            stn = h+w-2
            break
        if (c=="."):
            if (a<h-1):
                if (s[a+1][b]=="."):
                    stack.appendleft((a+1,b,"."))
                    flag = 1
            if (b<w-1):
                if (s[a][b+1]=="."):
                    stack.appendleft((a,b+1,"."))
                    flag = 1
            #print(flag)
            if (flag == 0):
                if (a+b+1>stopnum):
                    if (a<h-1 and b<w-1):
                        stop = [(a+1,b),(a,b+1)]
                    elif (a<h-1):
                        stop = [(a+1,b)]
                    elif (b<w-1):
                            stop = [(a,b+1)]
                    stopnum = a+b+1
                    #print(stop)
        elif (c=="#"):
            if (a<h-1):
                if (s[a+1][b]=="#"):
                    stack.appendleft((a+1,b,"#"))
                    flag = 1
            if (b<w-1):
                if (s[a][b+1]=="#"):
                    stack.appendleft((a,b+1,"#"))
                    flag = 1
            if (flag == 0):
                if (a+b+1>stopnum):
                    if (a<h-1 and b<w-1):
                        stop = [(a+1,b),(a,b+1)]
                    elif (a<h-1):
                        stop = [(a+1,b)]
                    elif (b<w-1):
                            stop = [(a,b+1)]
                    stopnum = a+b+1
                    #print(stop)
    #count += 1
    
    #print(count)
    if (stn>=h+w-2):
        break
    stn = stopnum
    count += 1

if (s[0][0]=="."):    
    print((count+1)//2)
else:
    print((count+2)//2)

Submission status: Runtime Error

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

dp = [[1000 for _ in range(W+1)] for _ in range(H+1)]
dp[0][1] = 0
dp[1][0] = 0

for y in range(W):
    for x in range(H):
        dp[y+1][x+1] = min(
            dp[y][x+1] + (s[y][x] == '#' and (y == 0 or s[y-1][x] == '.')),
            dp[y+1][x] + (s[y][x] == '#' and (x == 0 or s[y][x-1] == '.'))
        )

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

Submission status: Runtime Error

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

dp = [1000 for _ in range(W+1) for _ in range(H+1)]
dp[0][1] = 0
dp[1][0] = 0

for y in range(W):
    for x in range(H):
        dp[y+1][x+1] = min(
            dp[y][x+1] + (s[y][x] == '#' and (y == 0 or s[y-1][x] == '.')),
            dp[y+1][x] + (s[y][x] == '#' and (x == 0 or s[y][x-1] == '.'))
        )

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

Submission status: Runtime Error

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

dp = [[float("inf")] * (W+1) for _ in range(H+1)]
dp[0][1] = 0
dp[1][0] = 0

for y in range(W):
    for x in range(H):
        dp[y+1][x+1] = min(
            dp[y][x+1] + (s[y][x] == '#' and (y == 0 or s[y-1][x] == '.')),
            dp[y+1][x] + (s[y][x] == '#' and (x == 0 or s[y][x-1] == '.'))
        )

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

Submission status: Runtime Error

Solution code:
h,w=map(int,input().split())
m=[]
grid=[]
nextdfsstart=set()
nextdfsstart.add(0)
def dfs(x,y,colour):
  global grid
  global nextdfsstartcopy
  global visited
  grid[y][x]=depth
  visited.add(x+w*y)
  if x<w-1 and not x+1+y*w in visited:
    if m[y][x+1]==colour :
      dfs(x+1,y,colour)
    else:
      nextdfsstartcopy.add(x+1+y*w)
  if x>0 and not x-1+y*w in visited:
    if m[y][x-1]==colour :
      dfs(x-1,y,colour)
    else:
      nextdfsstartcopy.add(x-1+y*w)
  if y<h-1 and not x+(y+1)*w in visited:
    if m[y+1][x]==colour :
      dfs(x,y+1,colour)
    else:
      nextdfsstartcopy.add(x+(y+1)*w)
  if y>0 and not x+w*(y-1) in visited:
    if m[y-1][x]==colour :
      dfs(x,y-1,colour)
    else:
      nextdfsstartcopy.add(x+w*(y-1))
for i in range(h):
  m.append(input())
  grid.append([])
  for j in range(w):
      grid[i].append(-1)
visited=set()
depth=0
while grid[h-1][w-1]==-1:
  nextdfsstartcopy=set()
  for i in nextdfsstart:
    if i in visited:
      continue
    k=i//w
    if (k+1)*w<=i:
      k+=1
    dfs(i%w,k,m[k][i%w])
  depth+=1
  if depth==1:
    visited.add(0)
  nextdfsstart=nextdfsstartcopy.copy()
ans=grid[h-1][w-1]//2
if m[0][0]=='#' or m[h-1][w-1]=='#':
  ans+=1
print(ans)