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:
"""
    Template written to be used by Python Programmers.
    Use at your own risk!!!!
    Owned by enraged(rating - 5 star at CodeChef and Specialist at Codeforces).
"""
import sys
import heapq
from math import ceil, floor, gcd, fabs, factorial, fmod, sqrt
from collections import defaultdict as dd, deque, Counter as c
from itertools import combinations as comb, permutations as perm
from bisect import bisect_left as bl, bisect_right as br, bisect
# sys.setrecursionlimit(2*pow(10, 6)+1)
# sys.stdin = open("input.txt", "r")
# sys.stdout = open("output.txt", "w")
mod = pow(10, 9) + 7
mod2 = 998244353
def data(): return sys.stdin.readline().strip()
def out(var): sys.stdout.write(str(var))
def l(): return list(sp())
def sl(): return list(ssp())
def sp(): return map(int, data().split())
def ssp(): return map(str, data().split())
def l1d(n, val=0): return [val for i in range(n)]
def l2d(n, m, val=0): return [[val for i in range(n)] for j in range(m)]


def valid(x, y):
    if 0 <= x < h and 0 <= y < w:
        return True
    return False


def revert_column(arr, t):
    for i in range(h):
        arr[i][t] = ('.', '#')[arr[i][t] == '.']
    return arr


def revert_row(arr, t):
    for i in range(w):
        arr[t][i] = ('.', '#')[arr[t][i] == '.']
    return arr


h, w = sp()
mat = []
for i in range(h):
    mat.append(list(data()))
i, j = 0, 0
answer = 0
if mat[i][j] == '#':
    answer = 1
    mat = revert_row(mat, 0)
while i < h and j < w:
    if valid(i+1, j):
        if mat[i+1][j] == '.':
            i += 1
            continue
    if valid(i, j+1):
        if mat[i][j+1] == '.':
            j += 1
            continue
    if i == h-1 and j == w-1:
        break
    answer += 1
    if valid(i, j+1):
        mat = revert_column(mat, j+1)
    elif valid(i+1, j):
        mat = revert_row(mat, i+1)
out(answer)

Submission status: Runtime Error

Solution code:
H, W = map(int,input().split())
S = [input() for i in range(H)]
dp = [[0 for _ in range(H)] for _ in range(W)]
dp[0][0] = 1 if S[0][0] == "#" else 0
for i in range(1, H):
    if S[i][0] == "#":
        if S[i-1][0] == "#":
            dp[i][0] =  dp[i-1][0]
        else:
             dp[i][0] = dp[i-1][0] + 1
    else:
        dp[i][0] =  dp[i-1][0]

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

for i in range(1,H):
    for j in range(1,W):
        up = dp[i-1][j] + (1 if S[i-1][j] != "#" and S[i][j] == "#" else 0) 
        left = dp[i][j-1] + (1 if S[i][j-1] != "#" and S[i][j] == "#" else 0)
        dp[i][j] = min(up, left)
print(dp[-1][-1])

Submission status: Runtime Error

Solution code:
H,W=map(int,input().split())
M=[[0 for i in range(W)] for i in range(H)]
for _ in range(H):
    s=input()
    for i in range(W):
        if s[i]=='#':
            M[_][i]=1
dp=[[10**6 for i in range(W)] for i in range(H)]
if M[0][0]==1:
    dp[0][0]=1
else:
    dp[0][0]=0
for j in range(W-1):
    if M[j+1][0]==0:
        dp[j+1][0]=dp[j][0]
    else:
        if M[j][0]==1:
            dp[j+1][0]=dp[j][0]
        else:
            dp[j+1][0]=dp[j][0]+1
for i in range(H-1):
    if M[0][i+1]==0:
        dp[0][i+1]=dp[0][i]
    else:
        if M[0][i]==1:
            dp[0][i+1]=dp[0][i]
        else:
            dp[0][i+1]=dp[0][i]+1
for i in range(1,H):
    for j in range(W-1):
        if M[i][j+1]==0:
            if M[i-1][j+1]==0:
                dp[i][j+1]=min(dp[i-1][j+1],dp[i][j])
            else:
                dp[i][j+1]=min(dp[i-1][j+1],dp[i][j])
        elif M[i][j+1]==1:
            if M[i-1][j+1]==1:
                if M[i][j]==1:
                    dp[i][j+1]=min(dp[i-1][j+1],dp[i][j])
                else:
                    dp[i][j+1]=min(dp[i-1][j+1],dp[i][j]+1)
            else:
                if M[i][j]==1:
                    dp[i][j+1]=min(dp[i-1][j+1]+1, dp[i][j])
                else:
                    dp[i][j+1]=min(dp[i-1][j+1]+1,dp[i][j]+1)
print(dp[H-1][W-1])

Submission status: Runtime Error

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

grid_state = []

# 1 = black, 0 = white

for _ in range(w):
    temp = [int(s) for s in input().replace(".", "0").replace("#", "1")]
    grid_state.append(temp)

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

grid_cost[0][0] = grid_state[0][0]

for i in range(1, h + w - 1):
    j = i
    if j > w - 1:
        j = w - 1
    while((j >= 0) and (i - j < h)):
        if i - j == 0: 
            grid_cost[i - j][j] = grid_cost[i - j][j - 1] + grid_state[i - j][j]
        elif j == 0:
            grid_cost[i - j][j] = grid_cost[i - j - 1][j] + grid_state[i - j][j]
        else:
            grid_cost[i - j][j] = min([grid_cost[i - j - 1][j], grid_cost[i - j][j - 1]]) + grid_state[i - j][j]
        j -= 1

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

Submission status: Runtime Error

Solution code:
H,W=map(int,input().split())
S=[input() for i in range(H)]
i=0
count=0
while True:

Submission status: Runtime Error

Solution code:
h, w = list(map(int, input().split(" ")))
matrix = []
result = []

for i in range(h):
  row = input()
  for j in range(w):
    if row[j] == "#":
      k = True
    else:
      k = False
    if len(matrix) == i:
      matrix.append([k])
    else:
      matrix[i].append(k)

def check(x, y, count):
  if x > (w - 1) or y > (h - 1):
    return
  
  if matrix[x][y]:
    count += 1
  if x == (w - 1) and y == (h - 1):
    result.append(count)
  check(x+1, y, count)
  check(x, y+1, count)

check(0, 0, 0)
min_result = min(result) if min(result) else 0
print(min_result)

Submission status: Runtime Error

Solution code:
def main():
    h,w = map(int, input().split())
    s = []
    for i in range(h):
        ss = list(input())
        s.append(ss)

    now = [0,0]
    cnt = 0
    if s[0][0] == '#':
        cnt += 1
        # s[0][0] = '.'
    if s[h-1][w-1] == '#':
        # cnt += 1
        # s[h-1][w-1] = '.'

    dp = [[-1] * w for i in range(h)]
    dp[0][0] = cnt

    for i in range(h):
        for j in range(w):
            tmp_up = 100000
            tmp_left = 100000
            change  = 0
            if s[i][j] == '#':
                change = 1
            if i == 0 and j == 0:
                continue
            if i != 0:
                if s[i-1][j] == '#' and s[i][j] == '#':
                    tmp_up = dp[i-1][j]
                else:
                    tmp_up = dp[i-1][j] + change
            if j != 0:
                if s[i][j-1] == '#' and s[i][j] == '#':
                    tmp_left = dp[i][j-1]
                else:

                    tmp_left = dp[i][j-1] + change

            dp[i][j] = min(tmp_up,tmp_left)


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

if __name__ == '__main__':
    main()

Submission status: Runtime Error

Solution code:
import sys
sys.setrecursionlimit(500*500)
h,w = map(int,input().split())
hw = []
for i in range(h):
    hw.append(input())

todo = [(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 len(todo)>0:
    sx,sy = todo.pop(0)
    if sx + 1 < w and seen[sx+1][sy] == 200:
        todo.append((sx+1,sy))
    if sx + 1 < w and hw[sx+1][sy] == '.' and seen[sx+1][sy] > seen[sx][sy]:
        seen[sx+1][sy] = seen[sx][sy]
    if sx + 1 < w and hw[sx+1][sy] == '#' and seen[sx+1][sy] > seen[sx][sy]+1:
        seen[sx+1][sy] = seen[sx][sy]+1
    if sy+1 < h and seen[sx][sy+1] == 200:
        todo.append((sx,sy+1))
    if sy + 1 < h and hw[sx][sy+1] == '.' and seen[sx][sy+1] > seen[sx][sy]:
        seen[sx][sy+1] = seen[sx][sy]
    if sy + 1 < h and hw[sx][sy+1] == '#' and seen[sx][sy+1] > seen[sx][sy]+1:
        seen[sx][sy+1] = seen[sx][sy]+1



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

Submission status: Runtime Error

Solution code:
import java.util.*;
public class Main {

	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int H = sc.nextInt();
		int W = sc.nextInt();
		char[] s = new char[(H+1)*(W+1)];
		for(int i = 0; i < H; i++) {
			String S = sc.next();
			for(int j = 0; j < S.length(); j++)
				s[i*H+j] = S.charAt(j);
		}
		int[] n = new int[(H+1)*(W+1)];
		Arrays.fill(n, 10000);
		n[0] = 0;
		ArrayDeque<Integer> q = new ArrayDeque<>();
		q.offer(0);
		while(q.size() > 0) {
			int x = q.poll();
			if(x + 1 >= H * W)
				continue;
			if(s[x+1] == s[x]) {
				if(n[x+1] > n[x]) {
					n[x+1] = n[x];
					q.offer(x+1);
				}
			}
			else {
				if(n[x+1] > n[x] + 1) {
					n[x+1] = n[x] + 1;
					q.offer(x+1);
				}
			}
			if(x + W >= H * W)
				continue;
			if(s[x+W] == s[x]) {
				if(n[x+W] > n[x]) {
					n[x+W] = n[x];
					q.offer(x+W);
				}
			}
			else {
				if(n[x+W] > n[x] + 1) {
					n[x+W] = n[x] + 1;
					q.offer(x+W);
				}
			}
		}
		if(s[0] == '#')
			System.out.println((n[H*W-1])/2 + 1);
		else
			System.out.println((n[H*W-1]+1)/2);

	}

}

Submission status: Runtime Error

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

S = []
for i in range(H):
  S.append(input().split())

a = 0
if S[0] = '#':
  a = 1
  
import sys
  
for i in range(0, 100, W):
  while S[i] != S[i+1] and S[i] != S[i+W]:

Submission status: Runtime Error

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

board = [[0] * W for i in range(H)]

if S[0][0] == '#':
    board[0][0] = 1

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

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

for i in range(1, W):
    for j in range(1, H):
        if S[i][j] == '.':
            board[i][j] = min(board[i - 1][j], board[i][j - 1])
        else:
            if S[i - 1][j] == '.':
                left = 1
            else:
                left = 0
            if S[i][j - 1] == '.':
                up = 1
            else:
                up = 0
            board[i][j] = min(board[i - 1][j] + left, board[i][j - 1] + up)

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

Submission status: Runtime Error

Solution code:
#!/usr/bin/env python3
import sys
#sys.setrecursionlimit(150000)


def solve(H: int, W: int, s: "List[str]"):
    x=y=0
    k=1 if s[y][x]=="#" else 0
    for i in range(H+W-2):
        if y<H-1 and s[y][x]==s[y+1][x]:
            y+=1
        elif x<W-1 and s[y][x]==s[y][x+1]:
            x+=1
        else:
            k+=1
            if x<W-1:
                x+=1
            else:
                y+=1
    print((k+1)//2)
    return
        
# Generated by 1.1.6 https://github.com/kyuridenamida/atcoder-tools
def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    H = int(next(tokens))  # type: int
    W = int(next(tokens))  # type: int
    s = [next(tokens) for _ in range(W)]  # type: "List[str]"
    solve(H, W, s)

if __name__ == '__main__':
    main()

Submission status: Runtime Error

Solution code:
import math

def bfs(N,M,Map):
	# 始点，終点探索
	
    sx, sy = 0, 0
    gx, gy = H, W

    INF = math.inf

    d = [[INF] * N for _ in range(M)]
    # スタート地点をキューに入れる
    que = [(sy, sx)]
    if Map[sy][sx] == '#':
        d[sy][sx] = 1
    else:
        # 始点を0にしてindexをつける
        d[sy][sx] = 0

    while que and que[0] != (gy,gx):

        py, px = que.pop(0)

        # 右か下方向に移動
        for ny, nx in (py+1, px), (py, px+1):

            if 0 <= nx and nx < N and 0 <= ny and ny < M:
                    que.append([ny,nx])
                    if Map[py][px] == '#':
                        if d[ny][nx] > d[py][px]:
                            d[ny][nx] = d[py][px] + 1
                    else: 
                        d[ny][nx] = d[py][px]

    return d[gy-1][gx-1]

H, W = map(int, input().split())
mp = []
for _ in range(H):
    mp.append(input())
res = bfs(H,W,mp)

print(res)

Submission status: Runtime Error

Solution code:
r, c = map(int, input().split())
board = []
for _ in range(r):
    line = input()
    row = []
    for i in range(c):
        row.append(line[i])
    board.append(row)


def search(board, i, j, r, c, count, max_count):
    if max_count <= count:
        return max_count

    if i == (r - 1) and j == (c - 1):
        if board[i][j] == '.':
            return count
        else:
            return count + 1

    new_count = []
    if i < r - 1:
        if board[i + 1][j] == '.':
            new_count.append(search(board, i + 1, j, r, c, count, max_count))
        else:
            new_count.append(search(board, i + 1, j, r, c, count + 1, max_count))

    if j < c - 1:
        if board[i][j + 1] == '.':
            new_count.append(search(board, i, j + 1, r, c, count, max_count))
        else:
            new_count.append(search(board, i, j + 1, r, c, count + 1, max_count))

    return min(new_count)


def naive_search(board, r, c):
    counter = [0, 0]
    for i in range(r):
        counter[0] += 1 if board[0][i] == '.' else 0
        counter[1] += 1 if board[r - 1][i] == '.' else 0
    for i in range(c):
        counter[0] += 1 if board[i][c - 1] == '.' else 0
        counter[1] += 1 if board[i][0] == '.' else 0

    if board[0][0] == '#':
        counter[0] -= 1
        counter[1] -= 1

    if board[r - 1][c - 1] == '#':
        counter[0] -= 1
        counter[1] -= 1

    return min(counter)


nc = naive_search(board, r, c)
print(search(board, 0, 0, r, c, 0, nc))

Submission status: Runtime Error

Solution code:
import sys
from collections import deque
input = sys.stdin.readline

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

s = []

for _ in range(H):
    s.append(input().strip())

r = 0
c = 0
now = deque()
now.append([r,c])
if s[0][0] == '#':
    cost = 1
else:
    cost = 0

while True:
    cur = now.popleft()
    r = cur[0]
    c = cur[1]
    if c < W-1 and s[r][c + 1] == '.':
        now.append([r,c+1])
    if r < H-1 and s[r + 1][c] == '.':
        now.append([r+1,c])
    if now == deque():
        flag = False
        if c < W-1 and s[r][c + 1] == '#':
            cost += 1
            flag = True
            now.append([r,c+1])
        if r < H-1 and s[r + 1][c] == '#':
            if not flag:
                cost += 1
            now.append([r,c+1])
    if r == H-1 and c == W-1:
        break

print(cost)

Submission status: Runtime Error

Solution code:
h,w=map(int,input().split())
s=[input() for _ in range(h)]
infi=10**18
dp=[[infi]*h for _ in range(w)]
if s[0][0]=='#':
  dp[0][0]=1
else:
  dp[0][0]=0
for i in range(h):
  for j in range(w):
    if s[i][j]=='.':
      if i<h-1:
        if s[i+1][j]=='.':
          dp[i+1][j]=min(dp[i+1][j],dp[i][j])
        else:
          dp[i+1][j]=min(dp[i+1][j],dp[i][j]+1)
      if j<w-1:
        if s[i][j+1]=='.':
          dp[i][j+1]=min(dp[i][j+1],dp[i][j])
        else:
          dp[i][j+1]=min(dp[i][j+1],dp[i][j]+1)
    else:
      if i<h-1:
        if s[i+1][j]=='.':
          dp[i+1][j]=min(dp[i+1][j],dp[i][j])
        else:
          dp[i+1][j]=min(dp[i+1][j],dp[i][j])
      if j<w-1:
        if s[i][j+1]=='.':
          dp[i][j+1]=min(dp[i][j+1],dp[i][j])
        else:
          dp[i][j+1]=min(dp[i][j+1],dp[i][j])
print(dp[h-1][w-1])

Submission status: Runtime Error

Solution code:
h, w = list(map(int, input().split(" ")))
matrix = []
result = []

for i in range(h):
    matrix.append(input())

def check(x, y, count):
  if x > (w - 1) or y > (h - 1):
    return
  
  if matrix[x][y] == "#":
    count += 1
  if x == (w - 1) and y == (h - 1):
    result.append(count)
  check(x+1, y, count)
  check(x, y+1, count)

check(0, 0, 0)
min_result = min(result) if min(result) else 0
print(min_result)

Submission status: Runtime Error

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

dp=[[0]*H]*W
#print(s)
answer=[]



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

Submission status: Runtime Error

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

def solve(H: int, W: int, s: "List[str]"):
    dp = [[0]*W for _ in range(H)]

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

    for i in range(H):
        for j in range(W):
            if i == 0:
                if j == 0:
                    continue

                if s[i][j] == "#" and s[i][j-1] == ".":
                    dp[i][j] = dp[i][j-1]+1
                else:
                    dp[i][j] = dp[i][j-1] 
            else:
                if j == 0:
                    if s[i-1][j] == "." and s[i][j] == "#":
                        up = dp[i-1][j]+1
                    else:
                        up = dp[i-1][j]
                    dp[i][j] = up
                    continue
                else:
                    if s[i-1][j] == "." and s[i][j] == "#":
                        up = dp[i-1][j]+1
                    else:
                        up = dp[i-1][j]
                    
                    if s[i][j-1] == "." and s[i][j] == "#":
                        left = dp[i][j-1]+1
                    else:
                        left = dp[i][j-1]
                    
                    dp[i][j] = min(left,up)

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


def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    H = int(next(tokens))  # type: int
    W = int(next(tokens))  # type: int
    s = [next(tokens) for _ in range(W)]  # type: "List[str]"
    solve(H, W, s)

if __name__ == '__main__':
    main()

Submission status: Runtime Error

Solution code:
import sys
from collections import deque
input = sys.stdin.readline

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

s = []

for _ in range(H):
    s.append(input().strip())

r = 0
c = 0
now = deque()
now.append([r,c])
cost = 0

while True:
    cur = now.popleft()
    r = cur[0]
    c = cur[1]
    if c < W-1 and s[r][c + 1] == '.':
        now.append([r,c+1])
    if r < H-1 and s[r + 1][c] == '.':
        now.append([r+1,c])
    if now == deque():
        flag = False
        if c < W-1 and s[r][c + 1] == '#':
            cost += 1
            flag = True
            now.append([r,c+1])
        if r < H-1 and s[r + 1][c] == '#':
            if not flag:
                cost += 1
            now.append([r,c+1])
    if r == H-1 and c == W-1:
        break

print(cost)

Submission status: Runtime Error

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

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

position = [0, 0]
count = 0

if colors[0][0] == '#':
    count += 1
if colors[h][w] == '#':
    count += 1

pos_h = 0
pos_w = 0
flag_h = False
flag_w = False

while True:
    if not pos_h:
        if colors[pos_h + 1][pos_w] == ".":
            pos_h += 1
            continue
    if not pos_w:
        if colors[pos_h][pos_w + 1] == ".":
            pos_w += 1
            continue

    if pos_h == h - 1:
        pos_h = True
    if pos_w == w - 1:
        pos_w = True

    if pos_h and pos_w:
        break

    if pos_h:
        pos_w += 1
        count += 1
        continue
    if pos_w:
        pos_h += 1
        count += 1
        continue

print(count)

Submission status: Runtime Error

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

def f(i,j,h,w,c,r):
    global a
    if a[i][j]=="#":
        c+=1
    if i==h and j==w:
        if r == None or r > c:
            r = c
            return r
    if i < h:
        r=f(i+1,j,h,w,c,r)
    if j < w:
        r=f(i,j+1,h,w,c,r)
    return r

print(f(0,0,h-1,w-1,0,None))

Submission status: Runtime Error

Solution code:
import itertools
h, w = map(int, input().split())
# 縦 h y, 横 w x
s = [['' for _ in range(h)] for _ in range(w)]
for y in range(h):
    t = str(input())
    for x in range(w):
        s[y][x] = t[x]

ans = (h - 1)*(w - 1)

# 連続して通る黒ブロックの数の最小値
mov = []

for _ in range(h - 1):
    mov.append('y')
for _ in range(w - 1):
    mov.append('x')


for v in itertools.permutations(mov, len(mov)):
    isB = False
    cnt = 0
    r = 0
    c = 0
    for m in range(len(v)):
        if s[r][c] == '#':
            if isB:
                pass
            else:
                cnt += 1
            isB = True
        else:
            isB = False
        if v[m] == 'x':
            c += 1
        else:
            r += 1
    ans = min(ans, cnt)
print(ans)

Submission status: Runtime Error

Solution code:
"""
    Template written to be used by Python Programmers.
    Use at your own risk!!!!
    Owned by enraged(rating - 5 star at CodeChef and Specialist at Codeforces).
"""
import sys
import heapq
from math import ceil, floor, gcd, fabs, factorial, fmod, sqrt
from collections import defaultdict as dd, deque, Counter as c
from itertools import combinations as comb, permutations as perm
from bisect import bisect_left as bl, bisect_right as br, bisect
# sys.setrecursionlimit(2*pow(10, 6)+1)
# sys.stdin = open("input.txt", "r")
# sys.stdout = open("output.txt", "w")
mod = pow(10, 9) + 7
mod2 = 998244353
def data(): return sys.stdin.readline().strip()
def out(var): sys.stdout.write(str(var))
def l(): return list(sp())
def sl(): return list(ssp())
def sp(): return map(int, data().split())
def ssp(): return map(str, data().split())
def l1d(n, val=0): return [val for i in range(n)]
def l2d(n, m, val=0): return [[val for i in range(n)] for j in range(m)]


def valid(x, y):
    if 0 <= x < h and 0 <= y < h:
        return True
    return False


def revert_column(arr, t):
    for i in range(h):
        arr[i][t] = ('.', '#')[arr[i][t] == '.']
    return arr


def revert_row(arr, t):
    for i in range(w):
        arr[t][i] = ('.', '#')[arr[t][i] == '.']
    return arr


h, w = sp()
mat = []
for i in range(h):
    s = list(data())
    mat.append(s)
i, j = 0, 0
answer = 0
if mat[i][j] == '#':
    answer = 1
    mat = revert_row(mat, 0)
while i < h and j < w:
    if valid(i+1, j):
        if mat[i+1][j] == '.':
            i += 1
            continue
    if valid(i, j+1):
        if mat[i][j+1] == '.':
            j += 1
            continue
    if i == h-1 and j == w-1:
        break
    answer += 1
    if valid(i, j+1):
        mat = revert_column(mat, j+1)
    elif valid(i+1, j):
        mat = revert_row(mat, i+1)
out(answer)

Submission status: Runtime Error

Solution code:
print(これもうわかんねぇな)

Submission status: Runtime Error

Solution code:
H, W = map(int, input().split())
MAX_VAL = 10**9
cost = [[MAX_VAL]*(W+1) for _ in range(H+1)]
field = ["#" * (H+1)]
for i in range(H):
    line = input()
    field.append("#" + line)

if field[1][1] == "#":
    cost[1][1] = 1
else:
    cost[1][1] = 0

for i in range(1, H+1):
    for j in range(1, W+1):
        if i * j == 1:
            continue

        if field[i][j] == ".":
            cost[i][j] = min(cost[i-1][j], cost[i][j-1])
        else:
            top_cost = cost[i-1][j]
            left_cost = cost[i][j-1]
            
            if field[i-1][j] == ".":
                top_cost += 1
            if field[i][j-1] == ".":
                left_cost += 1
            
            cost[i][j] = min(top_cost, left_cost)

print(cost[H][W])

Submission status: Runtime Error

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

S = [input() for _ in range(H)]
p = [[0, 0, 0, 0]]
if S[0][0] == '#':
  p[3] = 1
for m in range(H+W-2):
  n = len(p)
  for i in range(n):
    x = p[i]
    if x[0] < H - 1:
      if x[3] == 1 and S[x[0]+1][x[1]] == '.':
        p.append([x[0]+1, x[1], x[2], 0])
      elif x[3] == 0 and S[x[0]+1][x[1]] == '#':
        p.append([x[0]+1, x[1], x[2]+1, 1])
      else:
        p.append([x[0]+1, x[1], x[2], x[3]])
    if x[1] < W - 1:
      if x[3] == 1 and S[x[0]][x[1]+1] == '.':
        p.append([x[0], x[1]+1, x[2], 0])
      elif x[3] == 0 and S[x[0]][x[1]+1] == '#':
        p.append([x[0], x[1]+1, x[2]+1, 1])
      else:
        p.append([x[0], x[1]+1, x[2], x[3]])
  p = p[n:]
print(min(p[i][2] for i in range(len(p))))

Submission status: Runtime Error

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

todo = [(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 len(todo)>0:
    sx,sy = todo.pop(0)
    if sx + 1 < w and hw[sx+1][sy] == '.' and seen[sx+1][sy] > seen[sx][sy]:
        seen[sx+1][sy] = seen[sx][sy]
        todo.append((sx+1,sy))
    if sx + 1 < w and hw[sx+1][sy] == '#' and seen[sx+1][sy] > seen[sx][sy]+1:
        seen[sx+1][sy] = seen[sx][sy]+1
        todo.append((sx+1,sy))
    if sy + 1 < h and hw[sx][sy+1] == '.' and seen[sx][sy+1] > seen[sx][sy]:
        seen[sx][sy+1] = seen[sx][sy]
        todo.append((sx,sy+1))
    if sy + 1 < h and hw[sx][sy+1] == '#' and seen[sx][sy+1] > seen[sx][sy]+1:
        seen[sx][sy+1] = seen[sx][sy]+1
        todo.append((sx,sy+1))



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

Submission status: Runtime Error

Solution code:
h, w = list(map(int, input().split(" ")))
matrix = []
result = []

for i in range(h):
  row = input()
  for j in range(w):
    if len(matrix) == i:
      matrix.append([row[j]])
    else:
      matrix[i].append(row[j])

def check(x, y, count):
  if x > (w - 1) or y > (h - 1):
    return
  
  if matrix[x][y] == "#":
    count += 1
  if x == (w - 1) and y == (h - 1):
    result.append(count)
  check(x+1, y, count)
  check(x, y+1, count)

check(0, 0, 0)
min_result = min(result) if min(result) else 0
print(min_result)

Submission status: Runtime Error

Solution code:
t = int(input())
s = input()
l1 =[list(map(int,s))]
for i in range(0,t-1):
    x = []
    print(l1)
    for j in range(0,len(l1[i]) - 1):
        n = abs(l1[i][j]-l1[i][j+1])
        x.append(n)
    l1.append(x)
print(l1[-1][0])

Submission status: Runtime Error

Solution code:
def f(i,j,h,w,c,a,r):
    if a[i][j]=="#":
        c+=1
    if i==h and j==w:
        if r == None or r > c:
            r = c
            return r
    if i < h:
        r=f(i+1,j,h,w,c,a,r)
    if j < w:
        r=f(i,j+1,h,w,c,a,r)
    return r

h,w=[int(i) for i in input().split()]
a=[]
for i in range(w):
    a.append(list(input().strip()))

r=f(0,0,h-1,w-1,0,a,None)
print(r)

Submission status: Runtime Error

Solution code:
#S = input()
#N = int(input())
#A, B, C = input().split()
#l, m, n = map(int, input().split())

#N = int(input())
#A = [int(x) for x in input().split()]

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

point = [[0 for i in range(H)] for j in range(W)]
if(S[0][0]!='.'): point[0][0] = 1
for i in range(1,H):
    if(S[i][0]!='.'): point[i][0] = point[i-1][0] + 1
    else: point[i][0] = point[i-1][0]
for i in range(1,W):
    if(S[0][i]!='.'): point[0][i] = point[0][i-1] + 1
    else: point[0][i] = point[0][i-1]
for i in range(1,H):
    for j in range(1,W):
        minscore = min(point[i-1][j], point[i][j-1])
        if(S[i][j]=='.'): point[i][j] = minscore
        else: point[i][j] = minscore + 1
print(point[H-1][W-1])

Submission status: Runtime Error

Solution code:
from sys import stdin,setrecursionlimit
from collections import deque
h,w = [int(x) for x in stdin.readline().rstrip().split()]
li = [["" for i in range(w)]for j in range(h)]
point = 0
for i in range(h):
    s = stdin.readline().rstrip()
    point += s.count(".")
    for j in range(w):
        li[i][j] = s[j]
dx = [1,0,-1,0]
dy = [0,1,0,-1]
que = deque()
lin = [[inf for i in range(w)]for j in range(h)]
lin[0][0] = 0#ここをスタートの座標に変えること
que.append([0,0])