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

Submission status: Runtime Error

Solution code:
N,A,B = map(int, input().split(" "))
distance = abs(B - A)
res=0
if distance % 2 == 0:
  res = distance/2
else:
  a,b = min(A,B), max(A,B)
  ans = distance//2 + min(a-1, N-b)+1

Submission status: Runtime Error

Solution code:
H, W = [int(a) for a in input().split()]
grid = []
for _ in range(H):
    grid.append(list(input()))
wt = [[-1 for _ in range(H)] for _ in range(W)]
if grid[0][0] == '#':
    wt[0][0] = 1
else:
    wt[0][0] = 0
for i in range(1, H):
    wt[i][0] = wt[i-1][0] +1 if grid[i][0] == "#" and grid[i-1][0] == "." else wt[i-1][0]
for j in range(1, W):
    wt[0][j] = wt[0][j-1] +1 if grid[0][j] == "#" and grid[0][j-1] == "." else wt[0][j-1]
for i in range(1, H):
    for j in range(1, W):
        if grid[i][j] == ".":
            wt[i][j] = min([wt[i-1][j], wt[i][j-1]])
        else:
            p1 = wt[i-1][j]+1 if grid[i-1][j] == "." else wt[i-1][j]
            p2 = wt[i][j-1]+1 if grid[i][j-1] == "." else wt[i][j-1]
            wt[i][j] = min([p1, p2])
print(wt[H-1][W-1])

Submission status: Runtime Error

Solution code:
H, W = [int(a) for a in input().split()]
grid = []
for _ in range(H):
    grid.append(list(input()))
wt = [[-1 for _ in range(H)] for _ in range(W)]
if grid[0][0] == '#':
    wt[0][0] = 1
else:
    wt[0][0] = 0
for i in range(1, H):
    wt[i][0] = wt[i-1][0] + \
        1 if grid[i][0] == "#" and grid[i-1][0] == "." else wt[i-1][0]
for j in range(1, W):
    wt[0][j] = wt[0][j-1] + \
        1 if grid[0][j] == "#" and grid[0][j-1] == "." else wt[0][j-1]
for i in range(1, H):
    for j in range(1, W):
        if grid[i][j] == ".":
            wt[i][j] = min([wt[i-1][j], wt[i][j-1]])
        else:
            p1 = wt[i-1][j]+1 if grid[i-1][j] == "." else wt[i-1][j]
            p2 = wt[i][j-1]+1 if grid[i][j-1] == "." else wt[i][j-1]
            wt[i][j] = min([p1, p2])
print(wt[H-1][W-1])

Submission status: Runtime Error

Solution code:
    H, W = [int(a) for a in input().split()]
    grid = []
    for _ in range(H):
        grid.append(list(input()))
    paths = [[[0, 0]]]
    test = False
    while True:
        newpaths = []
        for path in paths:
            lastNode = path[-1]
            if lastNode == [H-1, W-1]:
                test = True
                break
            if lastNode[0] < H-1:
                path2 = path+[[lastNode[0]+1, lastNode[1]]]
                newpaths.append(path2)
            if lastNode[1] < W-1:
                path1 = path+[[lastNode[0], lastNode[1]+1]]
                newpaths.append(path1)
        if test:
            break
        else:
            paths = newpaths
    test2 = False
    attempts = []
    for path in paths:
        att = 0
        for [x, y] in path:
            if grid[x][y] == '#' and test2 == False:
                test2 = True
                att = att+1
            if grid[x][y] == '.':
                test2 = False
        attempts.append(att)
    print(min(attempts))

Submission status: Runtime Error

Solution code:
    H, W = [int(a) for a in input().split()]
    grid = []
    for _ in range(H):
        grid.append(list(input()))
    paths = [[[0, 0]]]
    test = False
    while True:
        newpaths = []
        for path in paths:
            lastNode = path[-1]
            if lastNode == [H-1, W-1]:
                test = True
                break
            if lastNode[0] < H-1:
                path2 = path+[[lastNode[0]+1, lastNode[1]]]
                newpaths.append(path2)
            if lastNode[1] < W-1:
                path1 = path+[[lastNode[0], lastNode[1]+1]]
                newpaths.append(path1)
        if test:
            break
        else:
            paths = newpaths
    test = False
    attempts = []
    for path in paths:
        att = 0
        for [x, y] in path:
            if grid[x][y] == '#' and test == False:
                test = True
                att = att+1
            if grid[x][y] == '.':
                test = False
        attempts.append(att)
    print(min(attempts))

Submission status: Runtime Error

Solution code:
def main()
  N = raw_input()
  seq = str(raw_input)
  tri = [int(i) for i in seq]

  for idx in range(len(seq)-1):
    curr = []
    for i in range(len(seq)-idx-1):
      curr.append(abs(tri[i] - tri[i+1]))
    tri = curr

  return tri[-1]

main()

Submission status: Runtime Error

Solution code:

def solve(arr,matrix,n,m):
    maxx=0
    if n>0:
        if arr[0][0]=="#":
            matrix[0][0]=1
        maxx=max(maxx,matrix[0][0])
        for col in range(1,m):
            matrix[0][col]=matrix[0][col-1]
            if arr[0][col]=="#":
                matrix[0][col]+=1
            maxx=max(maxx,matrix[0][col])

        for row in range(1,n):    
            matrix[row][0]=matrix[row-1][0]
            if arr[row][0]=="#":
                matrix[row][0]+=1
            maxx=max(maxx,matrix[row][0])

        for row in range(1,n):
            for col in range(1,m):
                matrix[row][col]=min(matrix[row-1][col],matrix[row][col-1])
                if arr[row][col]=="#":
                    matrix[row][col]+=1
                maxx=max(maxx,matrix[row][col])
        return matrix[n-1][m-1]        



n,m=map(int,input().split())
arr=[int(0) for i in range(n)]
matrix=[int(0) for i in range(n)]
for i in range(m):
    arr[i]=list(input())
    matrix[i]=[int(0) for _ in range(m)]



print(solve(arr,matrix,n,m))

Submission status: Runtime Error

Solution code:


def solve(arr,n,m,row,col,count):
    if row>=n or col>=m:
        return 1e9
    elif row==n-1 and col==m-1:
        if arr[row][col]=="#":
            count+=1
        return count
    else:
        if arr[row][col]=="#":
            count+=1
        return min(solve(arr,n,m,row+1,col,count),solve(arr,n,m,row,col+1,count))        

n,m=map(int,input().split())
arr=[int(0) for i in range(n)]
for i in range(m):
    arr[i]=list(input())



#print(arr)
print(solve(arr,n,m,0,0,0))

Submission status: Runtime Error

Solution code:
H,W = input().split()
H,W=int(H),int(W)
P=[0]*H
for i in range(H):
    P[i] = input()

count=0

now=[[0,0]]
next=[]
loop=0
flag = True

while(1):
    for num in range(len(now)):
        for j in range(loop+1):
            #print('now',now[num][0]+loop-j,now[num][1]+j,W-1,H-1)
            if now[num][0]+loop-j==W-1 and now[num][1]+j==H-1:
                if P[now[num][0]+loop-j][now[num][1]+j]=='#':
                    count+=1
                print(count)
                exit()
            if now[num][0]+loop-j+1>W-1 and now[num][1]+j+1>H-1:
                continue
            if now[num][0]+loop-j+1<=W-1 and now[num][1]+j<=H-1:
                #print('searching',now[num][0]+loop-j+1,now[num][1]+j)
                if P[now[num][0]+loop-j+1][now[num][1]+j]=='.' and \
                    not [now[num][0]+loop-j+1,now[num][1]+j] in next:
                    next.append([now[num][0]+loop-j+1,now[num][1]+j])
            if now[num][0]+loop-j<=W-1 and now[num][1]+j+1<=H-1:
                #print('searching',now[num][0]+loop-j,now[num][1]+j+1)
                if P[now[num][0]+loop-j][now[num][1]+j+1]=='.' and \
                    not [now[num][0]+loop-j,now[num][1]+j+1] in next:
                    next.append([now[num][0]+loop-j,now[num][1]+j+1])
            
        #print(next)
    if next==[]:
        loop+=1
        if flag:
            count+=1
            flag=False
    else:
        now=[]
        now=next
        next=[]
        flag=True

Submission status: Runtime Error

Solution code:
H,W = input().split()
H,W=int(H),int(W)
sw=[[0]*W]*H

for i in range(W):
    sw[i] = input()

count=0
if sw[0][0]=='#':
    sw[0]='.'+sw[0][1:]
    count+=1
if sw[H-1][W-1]=='#':
    sw[H-1]=sw[H-1][:W-1]+'.'
    count+=1

def search(h,v):
    global H,W
    global sw
    if h==H-1 and v==W-1:
        return -2,-2
    elif v>=H-1 or h>=W-1:
        return -1,-1
    else:
        if sw[h+1][v]=='.':
            return h+1,v
        elif sw[h][v+1]=='.':
            return h,v+1
        else:
            return -1,-1

P=[[0,0]]
next=[]
i=0
plus=True
while(1):
    flag=False
    for p in P:
        for j in range(i+1):
            if p[0]+i-j>=W or p[1]+j>=H:
                continue
            result=search(p[0]+i-j,p[1]+j)
            #print('search',p[0]+i-j,p[1]+j,count)
            if result==(-2,-2):
                print(count)
                exit()
            elif result!=(-1,-1):
                next.append(result)
                flag=True
                i=0
                
    if not flag:
        #print('yaa')
        i+=1
        if plus:
            count+=1
        plus=False
    else:
        plus=True
        #print('next',next,count)
        P=[]
        P=next
        next=[]

Submission status: Runtime Error

Solution code:
H,W = input().split()
H,W=int(H),int(W)
sw=[[0]*W]*H

for i in range(W):
    sw[i] = input()

count=0
if sw[0][0]=='#':
    sw[0]='.'+sw[0][1:]
    count+=1
if sw[H-1][W-1]=='#':
    sw[H-1]=sw[H-1][:W-1]+'.'
    count+=1

def search(h,v):
    global H,W
    global sw
    if h>=H-1 and v>=W-1:
        return -2,-2
    elif v>=H-1:
        if sw[h+1][W-1]=='.':
            return h+1,v
        else:
            return -1,-1
    elif h>=W-1:
        if sw[H-1][v+1]=='.':
            return h,v+1
        else:
            return -1,-1
    else:
        if sw[h+1][v]=='.':
            return h+1,v
        elif sw[h][v+1]=='.':
            return h,v+1
        else:
            return -1,-1

h=0
v=0
i=0
while(1):
    flag=True
    for j in range(i+1):
        result = search(h+i-j,v+j)
        if result == (-2,-2):
            print(count)
            exit()
        if result!=(-1,-1):
            i=0
            flag = False
            h,v=result
            break
    if flag:
        count+=1
        i+=1

Submission status: Runtime Error

Solution code:
H,W = input().split()
H,W=int(H),int(W)
sw=[[0]*W]*H

for i in range(W):
    sw[i] = input()

count=0
if sw[0][0]=='#':
    sw[0]='.'+sw[0][1:]
    count+=1
if sw[H-1][W-1]=='#':
    sw[H-1]=sw[H-1][:W-1]+'.'
    count+=1

def search(h,v):
    global H,W
    global sw
    if h>=H-1 and v>=W-1:
        return -2,-2
    elif v>=H-1:
        if sw[h+1][W-1]=='.':
            return h+1,v
        else:
            return -1,-1
    elif h>=W-1:
        if sw[H-1][v+1]=='.':
            return h,v+1
        else:
            return -1,-1
    else:
        if sw[h+1][v]=='.':
            return h+1,v
        elif sw[h][v+1]=='.':
            return h,v+1
        else:
            return -1,-1

h=0
v=0
i=0
while(1):
    flag=True
    for j in range(i+1):
        result = search(h+i-j,v+j)
        if result == (-2,-2):
            exit()
        if result!=(-1,-1):
            i=0
            flag = False
            h,v=result
            break
    if flag:
        count+=1
        i+=1

Submission status: Runtime Error

Solution code:
H,W = input().split()
H,W=int(H),int(W)
sw=[[0]*W]*H

for i in range(W):
    sw[i] = input()

count=0
if sw[0][0]=='#':
    sw[0]='.'+sw[0][1:]
    count+=1
if sw[H-1][W-1]=='#':
    sw[H-1]=sw[H-1][:W-1]+'.'
    count+=1

def search(h,v):
    global H,W
    global sw
    if h>=H-1 and v>=W-1:
        return -2,-2
    elif v>=H-1:
        if sw[h+1][W-1]=='.':
            return h+1,v
        else:
            return -1,-1
    elif h>=W-1:
        if sw[H-1][v+1]=='.':
            return h,v+1
        else:
            return -1,-1
    else:
        if sw[h+1][v]=='.':
            return h+1,v
        elif sw[h][v+1]=='.':
            return h,v+1
        else:
            return -1,-1

h=0
v=0
i=0
while(1):
    flag=True
    for j in range(i+1):
        result = search(h+i-j,v+j)
        if result == (-2,-2):
            print(count)
            exit()
        if result!=(-1,-1):
            flag = False
            h,v=result
            break
    if flag:
        count+=1
        i+=1
    else:
        i=1

Submission status: Runtime Error

Solution code:
def main():
    h,w = map(int,input().split(" "))
    s = [list(input()) for i in range(h)]
    
    dp = [[0]*h for i in range(w)]
    dp[0][0] = 1 if s[0][0]=="#" else 0

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

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

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

Submission status: Runtime Error

Solution code:
def main():
    h,w = map(int,input().split(" "))
    s = [list(input()) for i in range(h)]
    
    dp = [[0]*h for i in range(w)]
    dp[0][0] = 1 if s[0][0]==1 else 0

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

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

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

Submission status: Runtime Error

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

# count min of color change cnt in the path
dp = [[0]*w for i in range(h)]
dp[0][0] = 1 if s[0][0] == '#' else 0
for i in range(w):
    for j in range(h):
        if i==j==0: continue
        a,b = h*w, h*w
        if i>0:
            a = dp[i-1][j] + (1 if s[i-1][j]!=s[i][j] else 0)
        if j>0:
            b = dp[i][j-1] + (1 if s[i][j-1]!=s[i][j] else 0)
        dp[i][j] = min(a,b)
if s[h-1][w-1] == '#':
    dp[h-1][w-1]+=1
print(int(dp[h-1][w-1]/2))

Submission status: Runtime Error

Solution code:
H, W = map(int, input().split())
maze = [[_ for _ in input()] for _ in range(W)]
INF = 10 ** 5

# dp[i][j]:=(i,j)に到達するまでに黒壁を壊す回数の最小値
dp = [[INF] * W for _ in range(H)]

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

for i in range(H):
    for j in range(W):
        for [dy, dx] in [[1, 0], [0, 1]]:
            ny, nx = i + dy, j + dx
            if ny >= H or nx >= W:
                continue
            else:
                if maze[i][j] == '.' and maze[ny][nx] == '#':
                    dp[ny][nx] = min(dp[ny][nx], dp[i][j] + 1)
                else:
                    dp[ny][nx] = min(dp[ny][nx], dp[i][j])
print(dp[H - 1][W - 1])

Submission status: Runtime Error

Solution code:
import sys

sys.setrecursionlimit(10 ** 5 + 10)


def input(): return sys.stdin.readline().strip()


def resolve():
    H, W = map(int, input().split())
    maze = [[_ for _ in input()] for _ in range(W)]
    INF = 10 ** 10
    # dp[i][j]:=(i,j)に到達するまでに黒壁を壊す回数の最小値
    dp = [[INF] * W for _ in range(H)]

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

    for i in range(H):
        for j in range(W):
            for [dy, dx] in [[1, 0], [0, 1]]:
                ny, nx = i + dy, j + dx
                if ny >= H or nx >= W:
                    continue
                else:
                    if maze[i][j] == '.' and maze[ny][nx] == '#':
                        dp[ny][nx] = min(dp[ny][nx], dp[i][j] + 1)
                    else:
                        dp[ny][nx] = min(dp[ny][nx], dp[i][j])
    print(dp[W-1][H-1])


resolve()

Submission status: Runtime Error

Solution code:
def rootjene(a,b):
    root=list()
    #print(a)
    #print(b)
    max=2+2*(a-2)
    #print("max="+str(max))
    #max=2**(a)#3なら4
    maxli=2**max#3なら32
    
    preroot=0
    #print("maxli="+str(maxli-1))
    #for f in range(maxli):#0~3
    for g in range(maxli):#0~15
        preroot=preroot+1
        preroot1=str(format(preroot,'b').zfill(max))
        if preroot1.count('0')==(max)/2:
            #print(preroot1)
            root.append(preroot1)

    return root


if __name__ == '__main__':
    maxres=99
    a=input()
    w=int(a[0])
    h=int(a[2])
    tile=list()
    for i in range(w):
        tile.append(str(input()))
    
    #print("\n")
    #print("//////////////////////")
    #print(w)
    #print(h)
    #for i in range(w):
        #print(tile[i])
    #print("//////////////////////")
    reverse=0
    #print(tile[0][0])
    sttile=0
    if(tile[0][0]=="#"):
        sttile=1
    
    roots=rootjene(w,h)
    #print(roots)
    #0は右1はした
    noww=0
    nowh=0
    #print("sttile="+str(sttile))
    for i in range(len(roots)):
        noww=0
        nowh=0
        strroot=str(roots[i])
        reverse=sttile
        for f in range(2+2*(w-2)):
            #print("h="+str(nowh))
            #print("w="+str(noww))
            #print("strroot="+str(strroot[f]))
            if(strroot[f]==str(0)):#右
                #print("right")
                if(tile[nowh][noww+1]=="#"):
                    reverse=reverse+1
                noww=noww+1
            else:
                #print("down")
                #print(reverse)
                #print(tile[2][1])

                if(tile[(nowh)+1][noww]=="#"):
                    reverse=reverse+1
                nowh=nowh+1
            #print("revers:::"+str(reverse))
        #print("revers="+str(reverse))
        if(reverse+sttile<maxres):
            
            maxres=reverse
        

    print(maxres)

Submission status: Runtime Error

Solution code:

import sys

def rootjene(a,b):
    root=list()
    #print(a)
    #print(b)
    max=2+2*(a-2)
    print("max="+str(max))
    #max=2**(a)#3なら4
    maxli=2**max#3なら32
    
    preroot=0
    print("maxli="+str(maxli-1))
    #for f in range(maxli):#0~3
    for g in range(maxli):#0~15
        preroot=preroot+1
        preroot1=str(format(preroot,'b').zfill(max))
        if preroot1.count('0')==(max)/2:
            print(preroot1)
            root.append(preroot1)

    return root


if __name__ == '__main__':
    maxres=99
    a=input()
    w=int(a[0])
    h=int(a[2])
    tile=list()
    for i in range(w):
        tile.append(str(sys.stdin.readline()))
    
    print("\n")
    print("//////////////////////")
    print(w)
    print(h)
    for i in range(w):
        print(tile[i])
    print("//////////////////////")
    reverse=0
    #print(tile[0][0])
    sttile=0
    if(tile[0][0]=="#"):
        sttile=1
    
    roots=rootjene(w,h)
    print(roots)
    #0は右1はした
    noww=0
    nowh=0
    print("sttile="+str(sttile))
    for i in range(len(roots)):
        noww=0
        nowh=0
        strroot=str(roots[i])
        reverse=sttile
        for f in range(2+2*(w-2)):
            print("h="+str(nowh))
            print("w="+str(noww))
            #print("strroot="+str(strroot[f]))
            if(strroot[f]==str(0)):#右
                print("right")
                if(tile[nowh][noww+1]=="#"):
                    reverse=reverse+1
                noww=noww+1
            else:
                print("down")
                #print(reverse)
                #print(tile[2][1])

                if(tile[(nowh)+1][noww]=="#"):
                    reverse=reverse+1
                nowh=nowh+1
            print("revers:::"+str(reverse))
        print("revers="+str(reverse))
        if(reverse+sttile<maxres):
            
            maxres=reverse
        

    print(maxres)

Submission status: Runtime Error

Solution code:



def rootjene(a,b):
    root=list()
    #print(a)
    #print(b)
    max=2+2*(a-2)
    print("max="+str(max))
    #max=2**(a)#3なら4
    maxli=2**max#3なら32
    
    preroot=0
    print("maxli="+str(maxli-1))
    #for f in range(maxli):#0~3
    for g in range(maxli):#0~15
        preroot=preroot+1
        preroot1=str(format(preroot,'b').zfill(max))
        if preroot1.count('0')==(max)/2:
            print(preroot1)
            root.append(preroot1)

    return root


if __name__ == '__main__':
    maxres=99
    a=input()
    w=int(a[0])
    h=int(a[2])

    tile=list()
    for i in range(w):
        tile.append(str(input()))
    print("//////////////////////")
    print(w)
    print(h)
    for i in range(w):
        print(tile[i])
    print("//////////////////////")
    reverse=0
    #print(tile[0][0])
    sttile=0
    if(tile[0][0]=="#"):
        sttile=1
    
    roots=rootjene(w,h)
    print(roots)
    #0は右1はした
    noww=0
    nowh=0
    print("sttile="+str(sttile))
    for i in range(len(roots)):
        noww=0
        nowh=0
        strroot=str(roots[i])
        reverse=sttile
        for f in range(2+2*(w-2)):
            print("h="+str(nowh))
            print("w="+str(noww))
            #print("strroot="+str(strroot[f]))
            if(strroot[f]==str(0)):#右
                print("right")
                if(tile[nowh][noww+1]=="#"):
                    reverse=reverse+1
                noww=noww+1
            else:
                print("down")
                #print(reverse)
                #print(tile[2][1])

                if(tile[(nowh)+1][noww]=="#"):
                    reverse=reverse+1
                nowh=nowh+1
            print("revers:::"+str(reverse))
        print("revers="+str(reverse))
        if(reverse+sttile<maxres):
            
            maxres=reverse
        

    print(maxres)

Submission status: Runtime Error

Solution code:
H,W,*L = open('0').read().split()
H,W = map(int, (H,W))
dp = [[0]*W for i in range(H)]
if L[0][0]=='#':
  dp[0][0] = 1
for i in range(1,H):
  if L[i][0]=='#':
    dp[i][0] = dp[i-1][0]+1
  else:
    dp[i][0] = dp[i-1][0]
for j in range(1,W):
  if L[0][j]=='#':
    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):
    if L[i][j]=='#':
      dp[i][j] = min(dp[i-1][j],dp[i][j-1])+1
    else:
      dp[i][j] = min(dp[i-1][j],dp[i][j-1])
print(dp[H-1][W-1])

Submission status: Runtime Error

Solution code:
# python3.4.2用
import math
import fractions
import bisect
import collections
import itertools
import heapq
import string
import sys
import copy
from decimal import *
from collections import deque
sys.setrecursionlimit(10**7)
MOD = 10**9+7
INF = float('inf') #無限大
def gcd(a,b):return fractions.gcd(a,b) #最大公約数
def lcm(a,b):return (a*b) // fractions.gcd(a,b) #最小公倍数
def iin(): return int(sys.stdin.readline()) #整数読み込み
def ifn(): return float(sys.stdin.readline()) #浮動小数点読み込み
def isn(): return sys.stdin.readline().split() #文字列読み込み
def imn(): return map(int, sys.stdin.readline().split()) #整数map取得
def imnn(): return map(lambda x:int(x)-1, sys.stdin.readline().split()) #整数-1map取得
def fmn(): return map(float, sys.stdin.readline().split()) #浮動小数点map取得
def iln(): return list(map(int, sys.stdin.readline().split())) #整数リスト取得
def iln_s(): return sorted(iln()) # 昇順の整数リスト取得
def iln_r(): return sorted(iln(), reverse=True) # 降順の整数リスト取得
def fln(): return list(map(float, sys.stdin.readline().split())) # 浮動小数点リスト取得
def join(l, s=''): return s.join(l) #リストを文字列に変換
def perm(l, n): return itertools.permutations(l, n) # 順列取得
def perm_count(n, r): return math.factorial(n) // math.factorial(n-r) # 順列の総数
def comb(l, n): return itertools.combinations(l, n) # 組み合わせ取得
def comb_count(n, r): return math.factorial(n) // (math.factorial(n-r) * math.factorial(r)) #組み合わせの総数
def two_distance(a, b, c, d): return ((c-a)**2 + (d-b)**2)**.5 # 2点間の距離
def m_add(a,b): return (a+b) % MOD
def lprint(l): print(*l, sep='\n')
def sieves_of_e(n):
    is_prime = [True] * (n+1)
    is_prime[0] = False
    is_prime[1] = False
    for i in range(2, int(n**0.5)+1):
        if not is_prime[i]: continue
        for j in range(i * 2, n+1, i): is_prime[j] = False
    return is_prime

H,W = imn()

s = [input() for _ in range(H)]
dp = [[INF for _ in range(W)] for _ in range(H)]
dp[0][0] = 0
if s[0][0] == '#': d[0][0] = 1

for i in range(H):
    for j in range(W):
        cnt = dp[i][j]
        if i+1 < H:
            if s[i][j] == "." and s[i+1][j] == "#":
                cnt += 1 
            dp[i+1][j] = min(dp[i+1][j], cnt)
        if j+1 < W:
            if s[i][j] == "." and s[i][j+1] == "#":
                cnt += 1
            dp[i][j+1] = min(dp[i][j+1], cnt)
print(dp[-1][-1])

Submission status: Runtime Error

Solution code:
import sys

sys.setrecursionlimit(10 ** 7)
rl = sys.stdin.readline


def solve():
    H, W = map(int, rl().split())
    s = [list(input()) for _ in range(H)]
    
    dp = [[0] * W for _ in range(H)]
    dp[0][0] = s[0][0] == '#'
    for i in range(1, W):
        dp[0][i] = dp[0][i - 1] + (s[0][i] == '#')
        dp[i][0] = dp[i - 1][0] + (s[i][0] == '#')
    
    for i in range(1, H):
        for j in range(1, W):
            dp[i][j] = min(dp[i - 1][j], dp[i][j - 1]) + (s[i][j] == '#')
    print(dp[-1][-1])


if __name__ == '__main__':
    solve()

Submission status: Runtime Error

Solution code:
from itertools import (
    accumulate,  # 累積和のイテレータ
    groupby,  # 値をkey,同じ値の集まりをgroup
    permutations,  # 順列
    combinations,  # 組み合わせ
    product,  # 重複あり順列（直積, 深いネストにも使える）
    combinations_with_replacement,  # 重複あり組み合わせ
)

def check(s):
    cnt = 0
    flag = False
    for i in range(len(s)):
        if flag == False:
            if s[i]=='#':
                flag = True
                cnt += 1
        else:
            if s[i]=='.':
                flag = False
    return cnt

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

ans = float('inf')
root = ['W']*(W-1) + ['H']*(H-1)
for v in permutations(root):
    x, y = 0, 0
    r = S[x][y]
    for c in v:
        if c=='H':
            y += 1
            r += S[x][y]
        else:
            x += 1
            r += S[x][y]
    ans = min(ans, check(r))

print(ans)

Submission status: Runtime Error

Solution code:
from collections import deque

def solve():
    H, W = map(int, input().split())
    A = [list(input()) for _ in range(H)]
    INF = 10 ** 9
    d = [[INF] * W for i in range(H)]
    d[0][0] = 1 if A[0][0] == '#' else 0

    def bfs():
        prepare = 1 if A[0][0] == '#' else 0
        q = deque([(0, 0, prepare)])
        while q:
            w, h, c = q.popleft()
            for a, b in [(1,0), (0,1)]:
                w_n, h_n = w+a, h+b
                if w_n >= W or h_n >= H: continue
                k = 1 if A[w_n][h_n] == '#' else 0
                if c+k >= d[h_n][w_n]: continue
                d[h_n][w_n] = c+k
                q.append((w_n, h_n, c+k))
    bfs()
    return d[H-1][W-1]

print(solve())

Submission status: Runtime Error

Solution code:
from collections import deque

def solve():
    H, W = map(int, input().split())
    A = [list(input()) for _ in range(H)]
    INF = 10 ** 9
    d = [[INF] * W for i in range(H)]
    d[0][0] = 1 if A[0][0] == '#' else 0

    def bfs():
        prepare = 1 if A[0][0] == '#' else 0
        q = deque([(0, 0, prepare)])
        while q:
            w, h, c = q.popleft()
            for a, b in [(1,0), (0,1)]:
                w_n, h_n = w+a, h+b
                if w_n >= W or h_n >= H: continue
                k = 1 if A[w_n][h_n] == '#' else 0
                if c+k >= d[h_n][w_n]: continue
                d[h_n][w_n] = c+k
                q.append((w_n, h_n, c+k))
    bfs()
    return d[W-1][H-1]

print(solve())

Submission status: Runtime Error

Solution code:
from collections import deque

def solve():
    H, W = map(int, input().split())
    A = [list(input()) for _ in range(H)]
    INF = 10 ** 9
    d = [[INF] * W for i in range(H)]
    d[0][0] = 1 if A[0][0] == '#' else 0

    def bfs():
        prepare = 1 if A[0][0] == '#' else 0
        q = deque([(0, 0, prepare)])
        while q:
            w, h, c = q.popleft()
            for a, b in [(1,0), (0,1)]:
                w_n, h_n = w+a, h+b
                if w_n >= W or h_n >= H: continue
                k = 1 if A[w_n][h_n] == '#' else 0
                if c+k >= d[h_n][w_n]: continue
                d[h_n][w_n] = c+k
                q.append((w_n, h_n, c+k))
    bfs()
    return d[-1][-1]

print(solve())