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
def MI(): return map(int, sys.stdin.readline().split())

H,W = MI()
s = [list(input()) for _ in range(H)]
dp = [[0 for _ in range(W)] for _ in range(H)]

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

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

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

if H==1 or W==1:
	print(dp[W-1][H-1])
	sys.exit()
# print(dp)

def next(start, goal, start_value):
	if start=='.' and goal=='#':
		start_value += 1
	return start_value

for i in range(1,W):
	for j in range(1,W):
		# print(next(s[i][j-1],s[i][j],dp[i][j-1]),next(s[i-1][j],s[i][j],dp[i-1][j]))
		dp[i][j] = min(next(s[i][j-1],s[i][j],dp[i][j-1]),next(s[i-1][j],s[i][j],dp[i-1][j]))
print(dp[W-1][H-1])

Submission status: Runtime Error

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

T = [-1] * H * W
if S[0] == '#':
    T[0] = 1
else:
    T[0] = 0
S[0] = '-'

k = 0
v = T[k]
R = {k:v}

def get_search_address(add):
    p = []
    x = add % W
    y = add // W
    next_x = x+1
    next_y = y+1
    if next_x <= (H-1):
        p.append(W*y+next_x)
    if next_y <= (W-1):
        p.append(W*next_y+x)
    return p

while R:
    k = min(R, key=R.get)
    # print('k:{}'.format(k))
    p = get_search_address(k)
    # print('p:{}'.format(p))
    for n in p:
        # print('n:{}'.format(n))
        if T[n] == -1:
            if S[n] == '-':
                if T[k]+1 < T[n]:
                    T[n] = T[k]+1
            elif S[n] == '#':
                T[n] = T[k]+1
                S[n] == '-'
                R[n] = T[n]
            else:
                T[n] = T[k]
                S[n] == '-'
                R[n] = T[n]
    del R[k]
    # print('R:{}'.format(R))
    # print('T:{}'.format(T))

print(T[H*W-1])

Submission status: Runtime Error

Solution code:
def ans_dp(H,W,M):
    dp = [[0 for i in range(H)] for j in range(W)]
    flag = [[0 for i in range(H)] for j in range(W)]
    if M[0][0] == "#":
        dp[0][0] = 1
        flag[0][0] = 1
    else:
        dp[0][0] == 0
    for i in range(1,W):
        if M[0][i] == "#":
            flag[0][i] = 1
            if flag[0][i-1] == 1:
                dp[0][i] = dp[0][i-1]
            else:
                dp[0][i] = dp[0][i-1] + 1 
        else:##M[0][i] = "."
            dp[0][i] = dp[0][i-1]
    for j in range(1,H):
        if M[j][0] == "#":
            flag[j][0] = 1
            if flag[j-1][0] == 1:
                dp[j][0] = dp[j-1][0]
            else:
                dp[j][0] = dp[j-1][0] + 1 
        else:##M[0][i] = "."
            dp[j][0] = dp[j-1][0]
    
    for i in range(1,H):
        for j in range(1,W):
            if M[i][j] == "#":
                flag[i][j] = 1
                dp[i][j] = min(dp[i-1][j]+int(not flag[i-1][j]),dp[i][j-1]+int(not flag[i][j-1]))
            else:#M[i][j] == "."
                dp[i][j] = min(dp[i-1][j],dp[i][j-1])
    """
    for i in range(H):
        print(dp[i])
    for i in range(H):
        print(flag[i])
    """
    return dp[W-1][H-1]

def main():
    H,W = map(int,input().split())
    M = []
    for i in range(H):
        M.append(list(input()))
    print(ans_dp(H,W,M))
 
if __name__ == "__main__":
    main()

Submission status: Runtime Error

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

#入力
H, W = map(int,input().split())
s = [list(map(str,list(input()))) for i in range(H)] 

#初期値
count1 = 0
count2 = 0
j = 0
k = 0

if s[j][k]=='#':
    count1 += 1
    count2 += 1


while  j+1<W or k+1<H:
    if j+1!=W and s[j+1][k] == '.':
            j += 1
    elif k+1!=H and s[j][k+1] == '.':
        k += 1
    elif j+1!=W and s[j+1][k] == '#' :
        count1 += 1
        j+=1
    elif k+1!=H and s[j][k+1] == '#':
        count1 += 1
        k+=1

    
j = 0
k = 0
    
while  j+1<W or k+1<H:
    if k+1!=H and s[j][k+1] == '.':
        k += 1
    elif j+1!=W and s[j+1][k] == '.':
        j += 1
    elif k+1!=H and s[j][k+1] == '#':
        count2 += 1
        k+=1
    elif j+1!=W and s[j+1][k] == '#' :
        count2 += 1
        j+=1
    

if count1<count2:
    count=count1
else:
    count=count2

print(count)

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
    dt=[[999]*W for _ in range(H)]
    dt[y][x]=1 if s[y][x]=="#" else 0
    for y in range(H):
        for x in range(W):
            if y>0:
                dt[y][x]=min(dt[y][x], dt[y-1][x]+(1 if s[y][x]!=s[y-1][x] else 0))
            if x>0:
                dt[y][x]=min(dt[y][x], dt[y][x-1]+(1 if s[y][x]!=s[y][x-1] else 0))
    print((dt[H-1][W-1]+1)//2)
    #print("#",s,dt)
    """
    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:
            print(x,y,k+1)
            k+=1
            if x<W-1:
                x+=1
            else:
                y+=1
    print(k,(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 sys
def MI(): return map(int, sys.stdin.readline().split())

H,W = MI()
s = [list(input()) for _ in range(H)]
dp = [[0 for _ in range(W)] for _ in range(H)]

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

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

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

# print(dp)

def next(start, goal, start_value):
	if start=='.' and goal=='#':
		start_value += 1
	return start_value

for i in range(1,W):
	for j in range(1,W):
		# print(next(s[i][j-1],s[i][j],dp[i][j-1]),next(s[i-1][j],s[i][j],dp[i-1][j]))
		dp[i][j] = min(next(s[i][j-1],s[i][j],dp[i][j-1]),next(s[i-1][j],s[i][j],dp[i-1][j]))
print(dp[W-1][H-1])

Submission status: Runtime Error

Solution code:
def maze(r, c, MAP, count, shaf, H, W):
    if r == H-1 and c == W-1:
            print(count)
            exit()       

    if MAP[0][0]=='#':
        shaf=1
        count+=1

    if r==H or c==W:
        return
    
    if shaf==0:
        if r != H-1 and MAP[r+1][c] == '.':
            maze(r+1, c, MAP, count, shaf, H, W)
        elif c != W-1 and MAP[r][c+1] == '.':
            maze(r, c+1, MAP, count, shaf, H, W)
        else:
            maze(r+1, c, MAP, count+1, 1, H, W)
            maze(r, c+1, MAP, count+1, 1, H, W)

    if shaf==1:
        if r != H-1 and MAP[r+1][c] == '#':
            maze(r+1, c, MAP, count, shaf, H, W)
        elif c != W-1 and MAP[r][c+1] == '#':
            maze(r, c+1, MAP, count, shaf, H, W)
        else:
            maze(r+1, c, MAP, count, 0, H, W)
            maze(r, c+1, MAP, count, 0, H, W)


def main():
    H, W = list(map(int, input().split()))

    MAP = [[int() for x in range(H)] for xx in range(W)]
    for i in range(W):
        MAP[i] = input()


    count = 0
    shaf = 0
    print(maze(0, 0, MAP, count, shaf, H, W))


main()

Submission status: Runtime Error

Solution code:
import math
h,w=map(int,input().split())
s=[]
dp=[]
for i in range(h):
    s.append(input())
    dp.append([1000]*w)
dp[0][0]=0 if s[0][0]=='.' else 1
for i in range(h+w-1):
    for j in range(min(i+1,h+w-i-1)):
        a=min(i+1,h+w-i-1)
        b=max(0,math.ceil((i-(h+w-i-1))/2))
        print(j+b,a+b-j-1)
        if j+b+1<h:
            dp[j+b+1][a+b-j-1]=min(dp[j+b+1][a+b-j-1],dp[j+b][a+b-j-1]+(s[j+b+1][a+b-j-1]=='#'))
        if a-j+b<w:
            dp[j+b][a+b-j]=min(dp[j+b][a+b-j],dp[j+b][a+b-j-1]+(s[j+b][a+b-j]=='#'))
        
print(dp)

Submission status: Runtime Error

Solution code:
N = int(input())
s = input()
num = [int(c) for c in s]

temp = num

def sumlist(x1,x2):
  return abs(x1-x2)

I = N-1
for i in range(I):
  list1 = temp[1:]
  list2 = temp[:-1]
  result = map(sumlist, list1, list2)
  temp = list(result)

print(temp[0])

Submission status: Runtime Error

Solution code:
h, w = map(int, input().split())
INF = 10**5
MAP = ["."*(w+2)]
for _ in range(h):
    MAP.append("."+input()+".")
MAP.append("."*(w+2))
ROUTE = [[0]*(w+2) for _ in range(h+2)]
for i in range(2, w+1):
    ROUTE[0][i] = INF
    ROUTE[i][0] = INF

for i in range(1, h+1):
    for j in range(1, w+1):
        if MAP[i][j] == ".":
            x1 = ROUTE[i][j-1]
            x2 = ROUTE[i-1][j]
        else:
            if MAP[i][j-1] == "#":
                x1 = ROUTE[i][j-1]
            else:
                x1 = ROUTE[i][j-1]+1

            if MAP[i-1][j] == "#":
                x2 = ROUTE[i-1][j]
            else:
                x2 = ROUTE[i-1][j]+1
        ROUTE[i][j] = min(x1, x2)


print(ROUTE[h][w])

Submission status: Runtime Error

Solution code:
saasa

Submission status: Runtime Error

Solution code:
import math
h,w=map(int,input().split())
s=[list(map(str,input().split())) for i in range(h)]
count=0

if s[0][0]==r'#'.:
  count+=1
elif s[h][w]==r'#':
  count+=1
  
def stu(i):
   if s[i][i+1]==r'#' and s[i+1][i]==r'#':
    count+=1
    a=random.randint(1,2)
     if a==1:
      return s[i][i+1]
    else:
      return s[i+1][i]
  elif s[i][i+1]==r'.' and s[i+1][i]==r'#':
    return s[i][i+1]
  elif s[i][i+1]==r'#' and s[i+1][i]==r'.':
    return s[i+1][i]
  elif s[i][i+1]==r'.' and s[i+1][i]==r'.':
    a=random.randint(1,2)
    if a==1:
      return s[i][i+1]
    else:
      return s[i+1][i]
      
    
  
for i in range(100):
  ans=stu(i)
  if ans==a[h][w]:
    break
    
print(count)

Submission status: Runtime Error

Solution code:
H,W = map(int, input().split())
S = []
for h Ain range(H):
    tmp_Si = input()
    Si = []
    for w in range(W):
        if tmp_Si[w] == '.':  #白
            Si.append(0)
        else:   #黒
            Si.append(1)
    S.append(Si)

#print(S)
move_vec = [[0,1], [1,0]]
record = []

def move_and_record(h, w, black):
    for dh, dw in move_vec:
        nh = h + dh
        nw = w + dw
        #print('nh=',nh)
        #print('nw=',nw)
        if nh == H-1 and nw == W-1: #ゴール
            if S[nh][nw] == 1:
                black += 1
            else:   #S[nh][nw] == 0:
                pass
            record.append(black)
        elif nh > H-1: #もう下にはいけない
            pass
        elif nw > W-1: #もう右にはいけない
            pass
        else:   #さらに進む
            if S[nh][nw] == 1:
                move_and_record(nh, nw, black+1)
            else:   #S[nh][nw] == 0:
                move_and_record(nh, nw, black)

if S[0][0] == 1:
    move_and_record(0,0,1)
else:   #S[0][0] == 0:
    move_and_record(0,0,0)

#print(record)
print(min(record))

Submission status: Runtime Error

Solution code:
N,W=[int(x) for x in input().split()]

s=[input() for _ in range(W)]


table = [[300 for i in range(110)]for j in range(110)]

table[0][0] = 1 if s[0][0]=='#' else 0

for j in range(N):
    for i in range(W):
        if i==0 and j==0:
            continue
        q = 1 if s[i][j]=='#' else 0
        table[i][j] = min(table[i-1][j] ,table[i][j-1])+q

print(table[W-1][N-1])
#print(table)

Submission status: Runtime Error

Solution code:
N,W=[int(x) for x in input().split()]

s=[input() for _ in range(W)]


table = [[300 for i in range(10)]for j in range(10)]

table[0][0] = 1 if s[0][0]=='#' else 0

for j in range(N):
    for i in range(W):
        if i==0 and j==0:
            continue
        q = 1 if s[i][j]=='#' else 0
        table[i][j] = min(table[i-1][j] ,table[i][j-1])+q

print(table[W-1][N-1])
#print(table)

Submission status: Runtime Error

Solution code:
import math
h,w=map(int,input().split())
s=[]
dp=[]
for i in range(h):
    s.append(input())
    dp.append([5]*w)
dp[0][0]=0 if s[0][0]=='.' else 1
for i in range(h+w-2):
    for j in range(min(i+1,h+w-i-1)):
        a=min(i+1,h+w-i-1)
        b=max(0,math.ceil((i-(h+w-i-1))/2))
        if j+b+1<h:
            dp[j+b+1][a+b-j-1]=min(dp[j+b+1][a+b-j-1],dp[j+b][a+b-j-1]+(s[j+b+1][a+b-j-1]=='#'))
        if a-j+b<w:
            dp[j+b][a+b-j]=min(dp[j+b][a+b-j],dp[j+b][a+b-j-1]+(s[j+b][a+b-j]=='#'))
print(dp[-1][-1])

Submission status: Runtime Error

Solution code:
import itertools

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

HW = []
for i in range(h):
    HW.append(input())
    
root = []
for i in range(h):
    for j in range(w):
        root.append([i, j])
root.pop(0)

search_root = []
for vv in itertools.combinations(root, (h - 1) + (w - 1)):
    # 一番目が初期値以外はスキップ
    if not(vv[0] == [0, 1] or vv[0] == [1, 0]): continue
    # 最後が最終値以外はスキップ
    if not(vv[-1] == [h -1, w - 1]): continue
    tmp = []
    for v in vv:
        if tmp == []:
            tmp.append(v)
        else:
            # 右か下に移動するルート以外はスキップ
            if not(tmp[-1][0] == v[0] and tmp[-1][1] + 1 == v[1] \
                or tmp[-1][0] + 1 == v[0] and tmp[-1][1] == v[1]
                ): continue
            tmp.append(v)
    if len(tmp) == 4:
        tmp.insert(0, [0, 0])
        search_root.append(tmp)
        
search_count = []
for root in search_root:
    count = 0
    is_break = False
    for point in root:
        r, c = point[0], point[1]
        if HW[r][c] == "#":
            count += 1
            if search_count:
                if min(search_count) < count:
                    is_break = True
                    break
    if not is_break: search_count.append(count)

print(min(search_count))

Submission status: Runtime Error

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

lastest = max(h, w)

s = [[0]]*lastest
dp = [[0 for i in range(lastest)] for j in range(lastest)]
ans = 0

for i in range(lastest):
    s[i] = input()

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


for i in range(lastest):
    for j in range(lastest):
        if i == 0:
            if j == 0: continue
            if s[0][j] == '#':
                dp[0][j] = dp[0][j-1] + 1
            else:
                dp[0][j] = dp[0][j-1]
        else:
            if s[i][j] == '#':
                if j == 0:
                    dp[i][j] = dp[i-1][j] + 1
                else:
                    dp[i][j] = (min(dp[i][j-1], dp[i-1][j]) + 1)
            else:
                if j == 0:
                    dp[i][j] = dp[i-1][j]
                else:
                    dp[i][j] = min(dp[i][j - 1], dp[i - 1][j])


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

Submission status: Runtime Error

Solution code:
h,w= [int(x) for x in input().split()]
maze = [[] for _ in range(h)]
for i in range(h):
  c = input()
  for j in range(w):
    maze[i].append(c[j])
#print(maze)

maps = [[100 for _ in range(w)] for _ in range(h)]

if maze[0][0] == ".":
  maps[0][0] = 0
else:
  maps[0][0] = 1

count = 0
for i in range(1,h):
  if maze[i][0] ==".":
    maps[i][0] = maps[i-1][0]
  else:
    if maze[i-1][0] == "#":
      maps[i][0] = maps[i-1][0]
    else:
      maps[i][0] = maps[i-1][0]+1
    
for i in range(1,w):
  if maze[0][i] ==".":
    maps[0][i] = maps[0][i-1]
  else:
    if maze[0][i-1] == "#":
      maps[0][i] = maps[0][i-1]
    else:
      maps[0][i] = maps[0][i-1]+1

#for i in maps:
#  print(i)
for i in range(1,h):
  for j in range(1,w):
    if maze[i][j] == ".":
      maps[i][j] = min(maps[i-1][j],maps[i][j-1])
    else:
      a = maps[i-1][j]
      b = maps[i][j-1]
      if a <= b:
        if maze[i-1][j] == "#" or maze[i][j-1] == "#":
          t = min(a,b)
      maps[i][j] = t
print(maps[-1][-1])

Submission status: Runtime Error

Solution code:
def ans_dp(H,W,M):
    dp = [[0 for i in range(W+1)] for j in range(H+1)]
    flag = [[0 for i in range(W+1)] for j in range(H+1)]
    if M[0][0] == "#":
        dp[0][0] = 1
        flag[0][0] = 1
    else:
        dp[0][0] == 0
    for i in range(1,W):
        if M[i][0] == "#":
            flag[i][0] = 1
            if flag[i-1][0] == 1:
                dp[i][0] = dp[i-1][0]
            else:
                dp[i][0] = dp[i-1][0] + 1 
        else:##M[0][i] = "."
            dp[i][0] = dp[i-1][0]
    for j in range(1,H):
        if M[0][j] == "#":
            flag[0][j] = 1
            if flag[0][j-1] == 1:
                dp[0][j] = dp[0][j-1]
            else:
                dp[0][j] = dp[0][j-1] + 1 
        else:##M[0][i] = "."
            dp[0][j] = dp[0][j-1]
    
    for i in range(1,W):
        for j in range(1,H):
            if M[i][j] == "#":
                flag[i][j] = 1
                dp[i][j] = min(dp[i-1][j]+int(not flag[i-1][j]),dp[i][j-1]+int(not flag[i][j-1]))
            else:#M[i][j] == "."
                dp[i][j] = min(dp[i-1][j],dp[i][j-1])
    """
    for i in range(H):
        print(dp[i])
    for i in range(H):
        print(flag[i])
    """
    return dp[W-1][H-1]

def main():
    H,W = map(int,input().split())
    M = []
    for i in range(H):
        M.append(list(input()))
    print(ans_dp(H,W,M))
 
if __name__ == "__main__":
    main()

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(0,W-1):
        if M[i][j+1]==0:
            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 = map(int,input().split())

field = [list(input()) for i in range(H)]


import sys
sys.setrecursionlimit(4100000)

dx = [0,1]
dy = [1,0]

if field[0][0] == "#":
    flag = False
else:
    flag = True

L = []
def dfs(x,y,cnt,flag):
    
    if field[x][y] == "#":
        flag = False
        
    if field[x][y] == ".":
        if flag ==False:
            cnt += 1
            flag = True
        else:
            flag = True
            
    if H == y + 1 and W == x + 1 :
        return L.append(cnt)
    
    
    
    for i in range(2):
        nx = x + dx[i]
        ny = y + dy[i]
        
        if 0 <= nx and nx < W and 0<= ny and ny < H:
            
            dfs(nx,ny,cnt,flag)

dfs(0,0,0,flag)

if flag:
    ans = min(L)
else:
    ans = min(L) + 1
print(ans)

Submission status: Runtime Error

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

ls = [[0]*W for _ in range(H)]
ls[0][0] = int(bool(s[0][0]=="#"))

for i in range(1,H):
    ls[0][i] = ls[0][i-1]+ int(bool(s[0][i]=="." and s[0][i-1]=="#"))
    
for j in range(1,W):
    ls[j][0] = ls[j-1][0]+ int(bool(s[j][0]=="." and s[j-1][0]=="#"))

for i in range(1,H):
    for j in range(1,W):
        ls[j][i] = min(ls[j][i-1]+ int(bool(s[j][i]=="." and s[j][i-1]=="#")),
                       ls[j-1][i]+ int(bool(s[j][i]=="." and s[j-1][i]=="#")))
        
print(ls[-1][-1])

Submission status: Runtime Error

Solution code:
import itertools
N, M = map(int, input().split())
p = [list(input()) for i in range(M)]
res=N+1
for n in set(list(itertools.permutations(["→","↓"]*(N-1)))):
  x=0
  y=0
  bb=[]
  bb.append(p[0][0])
  for sa in n:
   if sa=="→":
    x=x+1
   if sa=="↓":
    y=y+1
   bb.append(p[y][x])
  res=min(bb.count("#"),res)
print(res)

Submission status: Runtime Error

Solution code:

def main():


    from collections import deque


    h ,w = map(int, input().split())
    a = [ list(input())  for _ in range(h)]

    q = deque()

    if a[0][0]=='.':
        q.appendleft((0,0,0))
    else:
        q.appendleft((0,0,1))

    while(True):
        f = q.popleft()
        x, y, c = f[0], f[1], f[2]
        for u, v in [(1,0), (0,1)]:
            if x + u <= w - 1 and y + v<= h - 1:
                if x+u == w-1 and y+v == h-1:
                    n = a[w-1][h-1]=='#'
                    print(c+n)
                    exit()

                n = a[x+u][y+v]=='.'
                if n:a
                    q.appendleft((x + u, y + v, c + 0))
                else:
                    q.append((x + u, y + v, c + 1))



if __name__=='__main__':
    main()

Submission status: Runtime Error

Solution code:
aaaaaa

Submission status: Runtime Error

Solution code:
N,W=[int(x) for x in input().split()]

s=[input() for _ in range(W)]


dpTable = [[-1 for i in range(101)]for j in range(101)]

dpTable[0][0] = 1 if s[0][0]=='#' else 0

def dp(r,c):
    if dpTable[r][c] >=0:
        return dpTable[r][c]
    
    q= 1 if s[r][c]=='#' else 0
    if r==0:
        return dp(r,c-1)+q
    if c==0:
        return dp(r-1,c)+q
    return min(dp(r-1,c),dp(r,c-1))+q

print(dp(N-1,W-1))

Submission status: Runtime Error

Solution code:
white = 0
black = 1
temp = []
def resolve(board, H, W):
    now = [0, 0]
    while now != [H-1, W-1]:
        now = check(board, now)
    return len(temp)
def check(board, now):
    if now[0] > len(board) -1 or board[now[0]+1][now[1]]==black:
        if now[1] > len(board[0]) -1 or board[now[0]][now[1]+1]==black:
            temp.append([now[0], now[1]+1])
            return [now[0], now[1]+1]
        else:
            return [now[0], now[1]+1]
    else:
        return [now[0]+1, now[1]]
def change(board, r0, c0, r1, c1):
    for r in range(r0, r1 + 1):
        for c in range(c0, c1 + 1):
            board[r][c] = 1 - board[r][c]
def main():
    H, W = map(int, input().split())
    board = [[white for i in range(W)] for j in range(H)]
    for i in range(H):
        s = input()
        for j in range(W):
            if s[j] == ".":
                board[i][j] = white
            else:
                board[i][j] = black
    n = resolve(board, H, W)
    print(n)
if __name__ == "__main__":
    main()

Submission status: Runtime Error

Solution code:

def ans_dp(H,W,M):
    dp = [[0 for i in range(W)] for j in range(H)]
    flag = [[0 for i in range(W)] for j in range(H)]
    if M[0][0] == "#":
        dp[0][0] = 1
        flag[0][0] = 1
    else:
        dp[0][0] == 0
    for i in range(1,W):
        if M[i][0] == "#":
            flag[i][0] = 1
            if flag[i-1][0] == 1:
                dp[i][0] = dp[i-1][0]
            else:
                dp[i][0] = dp[i-1][0] + 1 
        else:##M[0][i] = "."
            dp[i][0] = dp[i-1][0]
    for j in range(1,H):
        if M[0][j] == "#":
            flag[0][j] = 1
            if flag[0][j-1] == 1:
                dp[0][j] = dp[0][j-1]
            else:
                dp[0][j] = dp[0][j-1] + 1 
        else:##M[0][i] = "."
            dp[0][j] = dp[0][j-1]
    
    for i in range(1,W):
        for j in range(1,H):
            if M[i][j] == "#":
                flag[i][j] = 1
                if flag[i-1][j] == 1 or flag[i][j-1] == 1:
                    dp[i][j] = min(dp[i-1][j],dp[i][j-1])
                else:
                    dp[i][j] = min(dp[i-1][j],dp[i][j-1]) + 1
            else:#M[i][j] == "."
                dp[i][j] = min(dp[i-1][j],dp[i][j-1])
    """
    for i in range(H):
        print(dp[i])
    for i in range(H):
        print(flag[i])
    """
    return dp[-1][-1]

def main():
    H,W = map(int,input().split())
    M = []
    for i in range(H):
        M.append(list(input()))
    print(ans_dp(H,W,M))
 
if __name__ == "__main__":
    main()

Submission status: Runtime Error

Solution code:

def main():

    from collections import deque


    h ,w = map(int, input().split())
    a = [ list(input())  for _ in range(h)]

    q = deque()

    if a[0][0]=='.':
        q.appendleft((0,0,0))
    else:
        q.appendleft((0,0,1))

    while(True):
        f = q.popleft()
        x, y, c = f[0], f[1], f[2]
        for u, v in [(1,0), (0,1)]:
            if x + u <= w - 1 and y + v<= h - 1:
                if x+u == w-1 and y+u == h-1:
                    n = a[w-1][h-1]=='#'
                    print(c+n)
                    break
                
                n = a[x+u][y+v]=='.'
                if n:
                    q.appendleft((x + u, y + v, c + 0))
                else:
                    q.append((x + u, y + v, c + 1))



if __name__=='__main__':
    main()

Submission status: Runtime Error

Solution code:
from heapq import heappush,heappop,heapify
from collections import deque,defaultdict,Counter
from itertools import permutations,combinations,groupby
import sys,bisect,string,math,time,functools,random
def Golf():*a,=map(int,open(0))
def I():return int(input())
def S_():return input()
def IS():return input().split()
def LS():return [i for i in input().split()]
def LI():return [int(i) for i in input().split()]
def LI_():return [int(i)-1 for i in input().split()]
def NI(n):return [int(input()) for i in range(n)]
def NI_(n):return [int(input())-1 for i in range(n)]
def StoLI():return [ord(i)-97 for i in input()]
def ItoS(n):return chr(n+97)
def LtoS(ls):return ''.join([chr(i+97) for i in ls])
def GI(V,E,Directed=False,index=0):
    org_inp=[];g=[[] for i in range(n)]
    for i in range(E):
        inp=LI();org_inp.append(inp)
        if index==0:inp[0]-=1;inp[1]-=1
        if len(inp)==2:
            a,b=inp;g[a].append(b)
            if not Directed:g[b].append(a)
        elif len(inp)==3:
            a,b,c=inp;aa=(inp[0],inp[2]);bb=(inp[1],inp[2]);g[a].append(bb)
            if not Directed:g[b].append(aa)
    return g,org_inp
def GGI(h,w,search=None,replacement_of_found='.',mp_def={'#':1,'.':0}):
#h,w,g,sg=GGI(h,w,search=['S','G'],replacement_of_found='.',mp_def={'#':1,'.':0}) # sample usage
    mp=[1]*(w+2);found={}
    for i in range(h):
        s=input()
        for char in search:
            if char in s:
                found[char]=((i+1)*(w+2)+s.index(char)+1)
                mp_def[char]=mp_def[replacement_of_found]
        mp+=[1]+[mp_def[j] for j in s]+[1]
    mp+=[1]*(w+2)
    return h+2,w+2,mp,found
def TI(n):return GI(n,n-1)
def bit_combination(k,n=2):return [[tb//(n**bt)%n for bt in range(k)] for tb in range(n**k)]
def show(*inp,end='\n'):
    if show_flg:print(*inp,end=end)

YN=['YES','NO'];Yn=['Yes','No']
mo=10**9+7
inf=float('inf')
l_alp=string.ascii_lowercase
#sys.setrecursionlimit(10**7)
input=lambda: sys.stdin.readline().rstrip()

def ran_input():
    n=random.randint(4,16)
    rmin,rmax=1,10
    a=[random.randint(rmin,rmax) for _ in range(n)]
    return n,a

show_flg=False
show_flg=True

ans=0

h,w=LI()

h,w,g,sg=GGI(h,w,search=['S','G'],replacement_of_found='.',mp_def={'#':1,'.':0})
dp=[10**6]*(h*w)
dp[1]=0
g[1]=0

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

print(dp[(h-2)*w+w-2])

Submission status: Runtime Error

Solution code:
import itertools
N, M = map(int, input().split())
p = [list(input()) for i in range(M)]
s=["→","↓"]*(N-1)
k=list(itertools.permutations(s))
a=[]
for pp in k:
 if not pp in a:
   a.append(pp)
b=[]
bb=[]
for n in a:
  x=0
  y=0
  bb=[]
  bb.append(p[0][0])
  #print(n)
  #print(p)
  for sa in n:
   if sa=="→":
    x=x+1
   if sa=="↓":
    y=y+1
   #print("x,y",x,y)
   bb.append(p[y][x])
  b.append(bb)
#print(b)
res=100000
for rr in b:
 res=min(rr.count("#"),res)
print(res)

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

if W > 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]
if H > 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]

if H > 1 and W > 1:
    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])