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:
INFTY = 10**3
def paint0(i,j):
    global cnt
    if j+1<W and C[i][j+1]<0 and A[i][j+1]==0:
        C[i][j+1]=cnt
        paint0(i,j+1)
    if i-1>=0 and C[i-1][j]<0 and A[i-1][j]==0:
        C[i-1][j]=cnt
        paint0(i-1,j)
    if j-1>=0 and C[i][j-1]<0 and A[i][j-1]==0:
        C[i][j-1]==cnt
        paint0(i,j-1)
    if i+1<H and C[i+1][j]<0 and A[i+1][j]==0:
        C[i+1][j]=cnt
        paint0(i+1,j)
def paint1(i,j):
    if j+1<W and A[i][j+1]==1:
        A[i][j+1]=0
        paint1(i,j+1)
    if i-1>=0 and A[i-1][j]==1:
        A[i-1][j]=0
        paint1(i-1,j)
    if j-1>=0 and A[i][j-1]==1:
        A[i][j-1]=0
        paint1(i,j-1)
    if i+1<H and A[i+1][j]==1:
        A[i+1][j]=0
        paint1(i+1,j)
def paint2(i,j):
    global ind
    if j+1<W and A[i][j+1]==1 and C[i][j+1]<0:
        C[i][j+1]=ind
        paint2(i,j+1)
    elif j+1<W and A[i][j+1]==0 and dist[C[i][j+1]]>=INFTY:
        dist[C[i][j+1]] = dist[ind]+1
    if i-1>=0 and A[i-1][j]==1 and C[i-1][j]<0:
        C[i-1][j]=ind
        paint2(i-1,j)
    elif i-1>=0 and A[i-1][j]==0 and dist[C[i-1][j]]>=INFTY:
        dist[C[i-1][j]]=dist[ind]+1
    if j-1>=0 and A[i][j-1]==1 and C[i][j-1]<0:
        C[i][j-1]=ind
        paint2(i,j-1)
    elif j-1>=0 and A[i][j-1]==0 and dist[C[i][j-1]]>=INFTY:
        dist[C[i][j-1]]=dist[ind]+1
    if i+1<H and A[i+1][j]==1 and C[i+1][j]<0:
        C[i+1][j]=ind
        paint2(i+1,j)
    elif i+1<H and A[i+1][j]==0 and dist[C[i+1][j]]>=INFTY:
        dist[C[i+1][j]]=dist[ind]+1
    
H,W = map(int,input().split())
S = [input() for _ in range(H)]
A = [[0 for _ in range(W)] for _ in range(H)]
for i in range(H):
    for j in range(W):
        if S[i][j]=="#":
            A[i][j] = 1
C = [[-1 for _ in range(W)] for _ in range(H)]
ans = 0
if A[0][0]==1:
    A[0][0]=0
    paint1(0,0)
    ans += 1
if A[H-1][W-1]==1:
    A[H-1][W-1]=0
    paint1(H-1,W-1)
    ans += 1
cnt = 0
for i in range(H):
    for j in range(W):
        if C[i][j]<0 and A[i][j]==0:
            C[i][j] = cnt
            paint0(i,j)
            cnt += 1
dist = [INFTY for _ in range(cnt)]
dist[0] = 0
for i in range(H):
    for j in range(W):
        if A[i][j]==0:
            ind = C[i][j]
            paint2(i,j)
x = C[H-1][W-1]
ans += dist[x]
print(ans)

Submission status: Runtime Error

Solution code:
from collections import deque
h,w = map(int,input().split())
m = []
k = [[-1 for _ in range(w)] for _ in range(h)]
count = 0
cl =[]
for i in range(h):
  m.append(list(input()))

def bfs_w(cx,cy,count,cl,gx,gy,flg,k):
  dx = [0,1]
  dy = [1,0]
  d = deque()
  d.appendleft([cx,cy])
  if flg == 1:
    count += 1
    key = '.'
    flg =0
  else :
    key = '#'
    flg = 1
    
  while d:
    n = d.pop()
    x = n[0]
    y = n[1]

    
    nowhere = 0
    lo = []
    for i in range(2):
      nx = x + dx[i]
      ny = y + dy[i] 

      if(nx == gx and ny == gy and m[ny][nx] != key):
        cl.append(count) 
        break
        
      elif nx < w and ny < h and m[ny][nx] != key:
        if k[nx][ny] >=0 and k[nx][ny] <= count:
          break
        else:
          d.appendleft([nx,ny])
          k[nx][ny] = count
      
      else:
        nowhere += 1
    if nowhere == 2:
      bfs_w(x,y,count,cl,gx,gy,flg,k)  

if m[0][0] == '.':
  bfs_w(0,0,count,cl,w-1,h-1,0,k)
else:
  bfs_w(0,0,count,cl,w-1,h-1,1,k)
  
print(min(cl))

Submission status: Runtime Error

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

save=[[100000]*(W) for i in range(H)]

if L[0][0]=="#":
    save[0][0]=1
else:
    save[0][0]=0

H_LAST=H-1
W_LAST=W-1
    
for b in range(H-1):
    for r in range(W-1):
        nr=r+1
        nb=b+1

        if L[b][nr]=="#":
            save[b][nr]=min(save[b][r]+1,save[b][nr])
        else:
            save[b][nr]=min(save[b][r],save[b][nr])
            
        if L[nb][r]=="#":
            save[nb][r]=min(save[b][r]+1,save[nb][r])
        else:
            save[nb][r]=min(save[b][r],save[nb][r])
    
    for i in range(b,H_LAST):
        nb=i+1
        if L[nb][H_LAST]=="#":
            save[nb][H_LAST]=min(save[i][H_LAST]+1,save[nb][H_LAST])
        else:
            save[nb][H_LAST]=min(save[i][H_LAST],save[nb][H_LAST])
    
for i in range(r,W_LAST):
    nr=i+1
    if L[W_LAST][nr]=="#":
        save[W_LAST][nr]=min(save[W_LAST][i]+1,save[W_LAST][nr])
    else:
        save[nr][W_LAST]=min(save[W_LAST][i],save[W_LAST][nr])
        
print(save[W_LAST][H_LAST])

Submission status: Runtime Error

Solution code:
def update(black):
    return '.' if black == '#' else '#'


def dp(i, j, w_end, h_end, black='#', memo={}):
    if (i, j, w_end, h_end, black) in memo:
        return memo[i, j, w_end, h_end, black]
    elif i < 0 or j < 0 or w_end >= W or h_end >= H:
        return float('inf')
    elif i == w_end and j == h_end:
        return 1 if grid[i][j] == black else 0
    elif grid[i][j] == black and grid[w_end][h_end] == black:
        not_flip = 1 + min(dp(i - 1, j, w_end, h_end, black, memo),
                           dp(i, j - 1, w_end, h_end, black, memo),
                           dp(i, j, w_end + 1, h_end, black, memo),
                           dp(i, j, w_end, h_end + 1, black, memo))
        new = update(black)
        flip = 1 + min(dp(i - 1, j, w_end + 1, h_end, new, memo),
                       dp(i - 1, j, w_end, h_end + 1, new, memo),
                       dp(i, j - 1, w_end + 1, h_end, new,  memo),
                       dp(i, j - 1, w_end, h_end + 1, new,  memo))
        res = min(not_flip, flip)
        memo[i, j, w_end, h_end, black] = res
        return res
    elif grid[i][j] == black:
        not_flip = 1 + min(dp(i - 1, j, w_end + 1, h_end, black, memo),
                           dp(i - 1, j, w_end, h_end + 1, black, memo),
                           dp(i, j - 1, w_end + 1, h_end, black, memo),
                           dp(i, j - 1, w_end, h_end + 1, black, memo))
        new = update(black)
        flip = 1 + min(dp(i - 1, j, w_end + 1, h_end + 1, new, memo),
                       dp(i, j - 1, w_end + 1, h_end + 1, new, memo))
        flip += min(dp(w_end + 1, h_end, w_end + 1, h_end, black, memo),
                    dp(w_end, h_end + 1, w_end, h_end + 1, black, memo))
        res = min(not_flip, flip)
        memo[i, j, w_end, h_end, black] = res
        return res
    elif grid[w_end][h_end] == black:
        not_flip = 1 + min(dp(i - 1, j, w_end + 1, h_end, black, memo),
                           dp(i - 1, j, w_end, h_end + 1, black, memo),
                           dp(i, j - 1, w_end + 1, h_end, black, memo),
                           dp(i, j - 1, w_end, h_end + 1, black, memo))
        new = update(black)
        flip = 1 + min(dp(i - 1, j - 1, w_end + 1, h_end, new, memo),
                       dp(i - 1, j - 1, w_end, h_end + 1, new, memo))
        flip += min(dp(i - 1, j, i - 1, j, black, memo),
                    dp(i, j - 1, i, j - 1, black, memo))
        res = min(not_flip, flip)
        memo[i, j, w_end, h_end, black] = res
        return res
    else:
        res = min(dp(i - 1, j, w_end + 1, h_end, black, memo),
                  dp(i - 1, j, w_end, h_end + 1, black, memo),
                  dp(i, j - 1, w_end + 1, h_end, black, memo),
                  dp(i, j - 1, w_end, h_end + 1, black, memo))
        memo[i, j, w_end, h_end, black] = res
        return res


H, W = map(int, input().split())
grid = [[None] * W for _ in range(H)]
for i in range(H):
    for j, x in enumerate(input()):
        grid[i][j] = x

memo = {}
print(min(dp(H - 1, W - 1, 0, 0, '#', memo),
          1 + dp(H - 1, W - 1, 0, 0, '.', memo)))

Submission status: Runtime Error

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

dpw = [[float("inf")] * h for _ in range(w)]
dpb = [[float("inf")] * h for _ in range(w)]

for i in range(h):
    for j in range(w):
        if i == 0 and j == 0:
            if maze[-1-i][-1-j] == '.':
                dpw[i][j] = 0
                dpb[i][j] = 1
            else:
                dpw[i][j] = 1
                dpb[i][j] = 0
        elif i == 0:
            if maze[-1-i][-1-j] == '.':
                dpw[i][j] = dpw[i][j-1]
                dpb[i][j] = min(dpw[i][j-1]+1, dpb[i][j-1]+1)
            else:
                dpw[i][j] = min(dpw[i][j-1]+1, dpb[i][j-1]+1)
                dpb[i][j] = dpb[i][j-1]
        elif j == 0:
            if maze[-1-i][-1-j] == '.':
                dpw[i][j] = dpw[i-1][j]
                dpb[i][j] = min(dpw[i-1][j]+1, dpb[i-1][j]+1)
            else:
                dpw[i][j] = min(dpw[i-1][j]+1, dpb[i-1][j]+1)
                dpb[i][j] = dpb[i-1][j]
        else:
            if maze[-1-i][-1-j] == '.':
                dpw[i][j] = min(dpw[i-1][j], dpw[i][j-1])
                dpb[i][j] = min(dpw[i-1][j]+1, dpw[i][j-1]+1, dpb[i-1][j]+1, dpb[i][j-1]+1)
            else:
                dpw[i][j] = min(dpw[i-1][j]+1, dpw[i][j-1]+1, dpb[i-1][j]+1, dpb[i][j-1]+1)
                dpb[i][j] = min(dpb[i-1][j], dpb[i][j-1])

print(min(dpw[-1][-1], dpb[-1][-1]+1))

Submission status: Runtime Error

Solution code:
import math
from collections import deque
def main():
    h,w = tuple([int(t)for t in input().split()])

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

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

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

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

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

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

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

Submission status: Runtime Error

Solution code:
H, W = map(int, input().rstrip().split())
D = []
for h in range(H):
    D.append(list(input().rstrip()))
# print(*D, sep='\n')
d = {}
for i in range(1, H + W):  # i: total
    for h in range(i):
        if h > H - 1:
            h = H - 1
        w = i - h - 1
        if w > W - 1 or h > H - 1 or w < 0 or h < 0:
            continue
        # print(h, w)
        if (h - 1, w) in d.keys() and (h, w - 1) in d.keys():
            d[(h, w)] = min(d[(h - 1, w)], d[(h, w - 1)])
        elif (h - 1, w) in d.keys():
            d[(h, w)] = d[(h - 1, w)]
        elif (h, w - 1) in d.keys():
            d[(h, w)] = d[(h, w - 1)]
        else:
            d[(h, w)] = 0
        if D[h][w] == '#':
            d[(h, w)] += 1
print(d[(H - 1, W - 1)])
assert d[(H - 1, W - 1)] == int(input().rstrip())
print(input().rstrip())

Submission status: Runtime Error

Solution code:
n = int(input())
 
numlist = list(input())

l_numlist = len(numlist)

while l_numlist > 1:
 
    for a in range(0, l_numlist-1):
        d = int(numlist[a]) - int(numlist[a+1])
        if not d == 0:
            numlist.append(abs(d))
 
    numlist = numlist[l_numlist:]
    l_numlist = len(numlist)
    
print(numlist[0])

Submission status: Runtime Error

Solution code:
import sys
import copy
h,w = map(int,input().split())
C = [list(input()) for i in range(h)]
ans = 0
check = 0
for i in range(h):
    if len(C[i]) == C[i].count('#'):
        check += 1        
if check == h:
    print(1)
    sys.exit()
s = "#"   
dy_dx = [[1,0],[0,1]]
visited1 = [[0 for i in range(w)] for i in range(h)]
def bfs():
    global ans
    global s
    
    queue = []
    visited = copy.deepcopy(visited)

    queue.append([0,0])
    visited[0][0] = 1
  
    while len(queue) > 0:
        now = queue.pop(0)
        for k in range(2):
            y = now[0]+dy_dx[k][0]
            x = now[1]+dy_dx[k][1]
            if 0 <= y < h and 0 <= x < w:
                if C[y][x] != s and visited[y][x] == 0:
                    visited[y][x] = visited[now[0]][now[1]]+1
                    C[y][x] = s
                    C[now[0]][now[1]] = s
                    queue.append([y,x])
                    
        if visited[h-1][w-1] != 0:
            if s == ".":
              ans += 1
            print(ans)
            sys.exit()
    if s == "#":
      ans += 1
    if s == '#':
      s = "."
    else:
      s = "#"
    bfs()
        
bfs()

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)]

    p = deque()
    q = deque()

    n = a[0][0]=='.'
    if n:
        p.append((0,0,0))
    else:
        q.append((0,0,1))

    while(True):
        if p:
            f = p.pop()
            x, y, c = f[0], f[1], f[2]
        else:
            f = q.pop()
            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:
                    p.append((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:
import math

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



flag=True
que=[]

now=[0,0,0]
result=[]
first=True
num=0
if maps[0][0]=="#":
    now=[0,0,1]

while flag:


    if now[0]==H-1 and now[1]==W-1:


        result.append(now)
        if first:
            num=now[2]
            first=False

        if now[2]<num:
            num=now[2]




        if not que:
            flag=False
            continue
        else:
            now=que.pop()


    if now[0]+1<W:
        if maps[now[0]+1][now[1]]==".":
            que.append([now[0]+1,now[1],now[2]])

        else:
            que.append([now[0]+1,now[1],now[2]+1])

    if now[1]+1<H:
        if maps[now[0]][now[1]+1]==".":

            que.append([now[0],now[1]+1,now[2]])

        else:
            que.append([now[0],now[1]+1,now[2]+1])

    if not que:
        flag=False
        continue
    que.sort(key=lambda x:x[2],reverse=True)



    now=que.pop(0)

print(num)

Submission status: Runtime Error

Solution code:
h,w = map(int,input().split())
lstMap = [list(input())for i in range(h)]
#判定ロジック共通化の為、余分に1列分確保
lstJudgeP = [[0 for _ in range(h+1)] for _ in range(w+1)]

r = h - 1
c = w - 1
while True:
    #加算ポイントを初期化
    plusP = 0
    #縦軸横軸全て確認し終えたら終了
    if r < 0 and c <= 0:
        break
    #縦軸を最後まで見たら横軸をずらして再判定
    if r < 0:
        r = h - 1
        c -= 1

    #自分の位置が黒の場合、加算ポイントを与える
    if lstMap[r][c] == "#":
        plusP = 1
    #現在地からゴールまでの最短値を算出
    if c == w-1:
        lstJudgeP[r][c] = lstJudgeP[r+1][c] + plusP
    elif r == h-1:
        lstJudgeP[r][c] = lstJudgeP[r][c+1] + plusP
    elif lstJudgeP[r+1][c] < lstJudgeP[r][c+1]:
        lstJudgeP[r][c] = lstJudgeP[r+1][c] + plusP
    elif lstJudgeP[r+1][c] >= lstJudgeP[r][c+1]:
        lstJudgeP[r][c] = lstJudgeP[r][c+1] + plusP

    #縦軸をずらして検索
    r -= 1

print(lstJudgeP[0][0])

Submission status: Runtime Error

Solution code:
import sys
import copy
h,w = map(int,input().split())
C = [list(input()) for i in range(h)]
ans = 0
check = 0
for i in range(h):
    if len(c[i]) == c[i].count('#'):
        check += 1        
if check == h:
    print(1)
    sys.exit()
s = "#"   
dy_dx = [[1,0],[0,1]]
visited1 = [[0 for i in range(w)] for i in range(h)]
def bfs():
    global ans
    global s
    
    queue = []
    visited = copy.deepcopy(visited)

    queue.append([0,0])
    visited[0][0] = 1
  
    while len(queue) > 0:
        now = queue.pop(0)
        for k in range(2):
            y = now[0]+dy_dx[k][0]
            x = now[1]+dy_dx[k][1]
            if 0 <= y < h and 0 <= x < w:
                if C[y][x] != s and visited[y][x] == 0:
                    visited[y][x] = visited[now[0]][now[1]]+1
                    C[y][x] = s
                    C[now[0]][now[1]] = s
                    queue.append([y,x])
                    
        if visited[h-1][w-1] != 0:
            if s == ".":
              ans += 1
            print(ans)
            sys.exit()
    if s == "#":
      ans += 1
    if s == '#':
      s = "."
    else:
      s = "#"
    bfs()
        
bfs()

Submission status: Runtime Error

Solution code:
# -*- coding: utf-8 -*-
# 整数の入力

a = input()
# スペース区切りの整数の入力
H,W=a.split(" ")
H=int(H)
W=int(W)
bord=[["#" for i in range(W+2)] for j in range(H+2)]
for i in range(H):
    tempbord=input()
    for j in range(W):
        bord[i+1][j+1]=tempbord[j]
DPbord=[[H*W for i in range(W+2)] for j in range(H+2)]


if bord[1][1]==".":
    DPbord[1][1]=0
if bord[1][1]=="#":
    DPbord[1][1]=1
"""
H=100
W=100
bord=[["#" for i in range(W+2)] for j in range(H+2)]
DPbord=[[H*W for i in range(W+2)] for j in range(H+2)]
if bord[1][1]==".":
    DPbord[1][1]=0
if bord[1][1]=="#":
    DPbord[1][1]=1

for i in range(H):
    for j in range(W):
        bord[i][j]="#"
"""


for i in range(3,H+W+3):
   for j in range(i-1):
       if j+1>H or i-j-1>W:
           continue

       #print(j+1,i-j-1)
       if bord[j+1][i-j-1]=="#":
           DPbord[j+1][i-j-1]=min([DPbord[j][i-j-1],DPbord[j+1][i-j-2]])+1
       if bord[j+1][i-j-1]==".":
           DPbord[j+1][i-j-1]=min([DPbord[j][i-j-1],DPbord[j+1][i-j-2]])
print(DPbord[W][H])

"""
for i in range(H):
   for j in range(W):
       print(bord[i][j],end=" ")
   print("")
"""

Submission status: Runtime Error

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

WALL = '#'
stack = [(0, 0, 0)]
min_cnt = H * W
tmp_min_cnt

# BFS
while stack:
    """
    stack取り出す
    調べる
    stack
    """
    y, x, cnt = stack.pop()

    if S[y][x] == WALL:
        cnt += 1

    if (y, x) == (H - 1, W - 1):
        # 0回を見つけたら強制終了
        if cnt == 0:
            min_cnt = 0
            break
        # それ以外は継続
        else:
            min_cnt = cnt

    next_y = y + 1
    next_x = x + 1

    # 打ち切りを入れる
    if min_cnt and min_cnt <= cnt:
        pass
    else:
        if next_y < H and next_x < W:
            # WALLじゃない方を優先して、listの後ろへ入れる
            if S[y][next_x] != WALL and S[next_y][x] == WALL:
                stack.append([next_y, x, cnt])
                stack.append([y, next_x, cnt])
            elif S[y][next_x] == WALL and S[next_y][x] != WALL:
                stack.append([y, next_x, cnt])
                stack.append([next_y, x, cnt])
            else:
                stack.append([next_y, x, cnt])
                stack.append([y, next_x, cnt])
        elif next_y == H and next_x < W:
            stack.append([y, next_x, cnt])
        elif next_y < H and next_x == W:
            stack.append([next_y, x, cnt])

print(min_cnt)

Submission status: Runtime Error

Solution code:
"""
ID: takesh.1
LANG: PYTHON2
TASK: task1
"""


gr = []

maxw = 100
bw = maxw+1
MAXX = maxw*maxw+1
weight = []


w, h = map(int, raw_input().split(" "))
wei = []
wwei = [MAXX] * (w+2)
wei.append(wwei)
weight.append([MAXX] * (w+2))
for i in range(h):
    wwei = [MAXX]*(w+2)
    weight.append([MAXX] * (w+2))
    gr.append(raw_input().rstrip("\r\n"))
    for j, c in enumerate(gr[i]):
        if c == ".":
            wwei[j+1] = 1
        else:
            wwei[j+1] = bw
    wei.append(wwei)

wwei = [MAXX] * (w+2)
wei.append(wwei)
weight.append([MAXX] * (w+1))

def calcWB(ww, hh):
    for i in range(1, hh+1):
        for j in range(1, ww+1):
            zz = weight[i][j] + wei[i][j+1]
            yy = weight[i][j] + wei[i+1][j]
            if weight[i][j+1] > zz:
                weight[i][j + 1] = zz
            if weight[i+1][j] > yy:
                weight[i+1][j] = yy

def calcW(ww, hh):
    if (ww == 0) and (hh == 0):
        return wei[ww][hh]

    if (ww < 0) or (hh < 0):
        return MAXX

    wLeft = calcW(ww-1, hh)
    wUp = calcW(ww, hh-1)
    return wei[ww][hh] + min(wLeft, wUp)

#weiz = calcW(w-1, h-1)

weight[1][1] = wei[1][1]
calcWB(w, h)
weiz = weight[w][h]
out = int(weiz/100)

print(str(out)+"\n")

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)]

    p = deque()
    q = deque()

    n = a[0][0]=='.'
    if n:
        p.append((0,0,0))
    else:
        q.append((0,0,1))

    while(True):
        if p:
            f = p.pop()
            x, y, c = f[0], f[1], f[2]
        if q:
            f = q.pop()
            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:
                    p.append((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:
import math

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



flag=True
que=[]

now=[0,0,0]
result=[]
first=True
num=0
if maps[0][0]=="#":
    now=[0,0,1]

while flag:


    if now[0]==H-1 and now[1]==W-1:


        result.append(now)
        if first:
            num=now[2]
            first=False
        else:
            if now[2]<num:
                num=now[2]




        if not que:
            flag=False
            continue
        else:
            now=que.pop()


    if now[0]+1<W:
        if maps[now[0]+1][now[1]]==".":
            que.append([now[0]+1,now[1],now[2]])

        else:
            que.append([now[0]+1,now[1],now[2]+1])

    if now[1]+1<H:
        if maps[now[0]][now[1]+1]==".":

            que.append([now[0],now[1]+1,now[2]])

        else:
            que.append([now[0],now[1]+1,now[2]+1])

    if not que:
        flag=False
        continue
    que.sort(key=lambda x:x[2],reverse=True)



    now=que.pop(0)
    
print(num)

Submission status: Runtime Error

Solution code:
h,w=map(int,input().split())
s=[]
for i in range(
  S=[int(i) for i in input().split()]
  s.append(S)
print(s)
  
for i in range(1,h):
  if 
  for j in range(w):

Submission status: Runtime Error

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

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

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

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

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

Submission status: Runtime Error

Solution code:
N=int(input())

s=list(input())

b=[]

while True:
    for i in range(len(s)-1):

        a=abs(int(s[i])-int(s[i+1]))
        b.append(a)
 
    s=b
    b=[]
    if len(s)>1:
        continue
    elif len(s)==1:
        print(s)
        break

Submission status: Runtime Error

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

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

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

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

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

Submission status: Runtime Error

Solution code:
import math

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

flag=True
que=[]



now=[0,0,0]
count=0
nummin=0
first=True




result=[]
if maps[0][0]=="#":
    count+=1
    now=[0,0,1]

while flag:

    if now[0]==H-1 and now[1]==W-1:

        result.append(now)
        if first:
            nummin=now[2]
            first=False
        else:
            if now[2]<nummin:
                nummin=now[2]



        if not que:
            flag=False
            continue
        else:
            now=que.pop()
            continue


    if now[0]+1<W:
        if maps[now[0]+1][now[1]]==".":
            que.append([now[0]+1,now[1],now[2]])

        else:
            que.append([now[0]+1,now[1],now[2]+1])

    if now[1]+1<H:
        if maps[now[0]][now[1]+1]==".":
            que.append([now[0],now[1]+1,now[2]])

        else:
            que.append([now[0],now[1]+1,now[2]+1])
    if not que:
        flag=False
        continue
    now=que.pop()



print(nummin)

Submission status: Runtime Error

Solution code:
h,w = map(int,input().split())
lstMap = [list(input())for i in range(h)]
#判定ロジック共通化の為、余分に1列分確保
lstJudgeP = [[0 for _ in range(h+1)] for _ in range(w+1)]

r = h - 1
c = w - 1
while True:
    #加算ポイントを初期化
    plusP = 0
    #縦軸横軸全て確認し終えたら終了
    if r < 0 and c <= 0:
        break
    #縦軸を最後まで見たら横軸をずらして再判定
    if r < 0:
        r = h - 1
        c -= 1

    #自分の位置が黒の場合、加算ポイントを与える
    if lstMap[r][c] == "#":
        plusP = 1
    #現在地からゴールまでの最短値を算出
    if lstJudgeP[r+1][c] < lstJudgeP[r][c+1] or r == h-1:
        lstJudgeP[r][c] = lstJudgeP[r][c+1] + plusP
    elif lstJudgeP[r+1][c] >= lstJudgeP[r][c+1] or c == w-1:
        lstJudgeP[r][c] = lstJudgeP[r+1][c] + plusP

    #縦軸をずらして検索
    r -= 1

print(lstJudgeP[0][0])

Submission status: Runtime Error

Solution code:
H, W = map(int, input().rstrip().split())
D = []
for h in range(H):
    D.append(list(input().rstrip()))
# print(*D, sep='\n')
d = {}
for i in range(1, H+W):  # i: total
    for h in range(i):
        w = i-h-1
        if h > H:
            h = H-1
            w = i-h
        if w >= W or h >= H or w < 0 or h < 0:
            continue
        print(h, w)
        if (h-1, w) in d.keys() and (h, w-1) in d.keys():
            d[(h, w)] = min(d[(h-1, w)], d[(h, w-1)])
        elif (h-1, w) in d.keys():
            d[(h, w)] = d[(h-1, w)]
        elif (h, w-1) in d.keys():
            d[(h, w)] = d[(h, w-1)]
        else:
            d[(h, w)] = 0
        if D[h][w] == '#':
            d[(h, w)] += 1
print(d[(H-1, W-1)])
assert d[(H-1, W-1)] == int(input().rstrip())
print(input().rstrip())

Submission status: Runtime Error

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

dpw = [[float("inf")] * h for _ in range(w)]
dpb = [[float("inf")] * h for _ in range(w)]

for i in range(h):
    for j in range(w):
        if i == 0 and j == 0:
            if maze[-1-i][-1-j] == '.':
                dpw[i][j] = 0
                dpb[i][j] = 1
            else:
                dpw[i][j] = 1
                dpb[i][j] = 0
        else:
            if maze[-1-i][-1-j] == '.':
                dpw[i][j] = min(dpw[i-1][j], dpw[i][j-1])
                dpb[i][j] = min(dpw[i-1][j]+1, dpw[i][j-1]+1, dpb[i-1][j]+1, dpb[i][j-1]+1)
            else:
                dpw[i][j] = min(dpw[i-1][j]+1, dpw[i][j-1]+1, dpb[i-1][j]+1, dpb[i][j-1]+1)
                dpb[i][j] = min(dpb[i-1][j], dpb[i][j-1])

print(min(dpw[-1][-1], dpb[-1][-1]+1))

Submission status: Runtime Error

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

min_r = 200

def solve(H: int, W: int, s: "List[str]"):
    l = H+W
    global min_r
    def cal_c(cmp, y, x, pre):
        global min_r
        if cmp < min_r :
            if ((y==H-1)&(x==W-1)):
                min_r = cmp+((pre ==".")&(s[y][x]=="#"))*1
            else:
                k = ((pre==".")&(s[y][x]=="#"))*1
                if y < H-1:
                    cal_c(cmp+k, y+1, x, s[y][x])
                if x < W-1:
                    cal_c(cmp+k, y, x+1, s[y][x])

    cal_c(0, 0, 0, ".")
    print(min_r)

    return


# Generated by 1.1.6 https://github.com/kyuridenamida/atcoder-tools  (tips: You use the default template now. You can remove this line by using your custom template)
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 numpy as np
H, W = map(int, input().split())

array = np.zeros((H, W))
for i in range(H):
  l = list(map(int, input().split()))
  array[i, :] = l

result_all = 0
if array[0,0] == '#':
  result_all += 1

from itertools import combinations
wl = ["w"]*len(W-1)
hl = ["h"]*len(H-1)
l = wl+hl
base = combinations(l)
base = list(base)

rl =[]
for i in base:
  w = 0
  l = 0
  result = result_all
  for j in list(i):
    if j == "w":
      w += 1
    else:
      h += 1
    if array[h, w] == "#":
      result += 1
  rl.append(result)
  
print(rl.min())