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: Time Limit Exceeded

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

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

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

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

Submission status: Time Limit Exceeded

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

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

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

Submission status: Time Limit Exceeded

Solution code:
H,W=map(int,input().split())
S=[input() for _ in range(H)]
ans=float("inf")
def search(i,j,count):
    global ans
    if i==H-1 and j==W-1:
        ans=min(ans,count)
        
    counti=count
    countj=count

    if j<W-1:
        if S[i][j]=="." and S[i][j+1]=="#":
            countj+=1
        search(i,j+1,countj)
    if i<H-1:
        if S[i][j]=="." and S[i+1][j]=="#":
            counti+=1
        search(i+1,j,counti)
search(0,0,1*(S[0][0]=="#"))
print(ans)

Submission status: Time Limit Exceeded

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

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

memo = [10000] * H * W
memo[0] = 0
def walk(x, y):
    if x == H-1 and y == W-1:
        if mymap[x][y] == '#':
            memo[x * W + y] += 1
        return
    if x != H-1: # down
        if mymap[x+1][y] == '#':
            if memo[(x+1) * W + y] > memo[x * W + y] + 1:
                memo[(x+1) * W + y] = memo[x * W + y] + 1
        else:
            if memo[(x+1) * W + y] > memo[x * W + y]:
                memo[(x+1) * W + y] = memo[x * W + y]
        walk(x+1, y)
    if y != W-1: # right
        if mymap[x][y+1] == '#':
            if memo[x * W + (y+1)] > memo[x * W + y] + 1:
                memo[x * W + (y+1)] = memo[x * W + y] + 1
        else:
            if memo[x * W + (y+1)] > memo[x * W + y]:
                memo[x * W + (y+1)] = memo[x * W + y]
        walk(x, y+1)

walk(0, 0)
print(memo[H*W-1])

Submission status: Time Limit Exceeded

Solution code:
from collections import deque
inf = 1001001001
H, W = map(int, input().split())
s = []
for _ in range(H):
    s.append(input())
queue = deque([[0,0]])
count = [[inf for i in range(W)] for j in range(H)]
if s[0][0] == "#":
    count[0][0] = 1
else:
    count[0][0] = 0
dh = [0,1]
dw = [1,0]
while len(queue) != 0:
    now = queue.popleft()
    h = now[0]
    w = now[1]
    for i in range(2):
        nh = h + dh[i]
        nw = w + dw[i]
        if nh >= H or nw >= W:
            continue
        else:
            queue.append([nh,nw])
            number = count[h][w]
            if s[h][w] == "." and s[nh][nw] == "#":
                number += 1
            count[nh][nw] = min(number, count[nh][nw])
print(count[H-1][W-1])

Submission status: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(10**6)
def main():
    h, w = map(int, input().split())
    s = [input() for _ in range(h)]
    def func(temp, now):
        x, y = now
        if y > h - 1 or x > w - 1:
            return 10**6
        if s[y][x] == "#":
            temp += 1
        if x == w-1 and y == h-1:
            return temp
        return min(func(temp, (x + 1, y)), func(temp, (x, y + 1)))
    print(func(0, (0, 0)))
main()

Submission status: Time Limit Exceeded

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


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

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

                


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

    #N = int(input())
    H,W = map(int, input().split())
    #A = tuple(map(int, input().split())) #1行ベクトル
    L = tuple(input() for i in range(H)) #改行ベクトル
    #S = tuple(tuple(map(int, input().split())) for i in range(N)) #改行行列
    
    ans=dfs(H,W,L)

    print(ans)


if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

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


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

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

                


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

    #N = int(input())
    H,W = map(int, input().split())
    #A = tuple(map(int, input().split())) #1行ベクトル
    L = tuple(input() for i in range(H)) #改行ベクトル
    #S = tuple(tuple(map(int, input().split())) for i in range(N)) #改行行列
    
    ans=dfs(H,W,L)

    print(ans)


if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
h,w = map(int,input().split())
ans = 0
grid = [['#']*(w+2)]
for i in range(h):
    grid += [ ['#'] + list(input()) + ['#']]

grid += [['#']*(w+2)]
#print(grid)
if grid[1][1] != '.':
    grid[1][1] = '.'
    ans += 1
from collections import deque

q = deque()
q.append([1,1,0])
point = 10**18
while q:
    k = q.popleft()
    x,y,p = k[0],k[1],k[2]
    if x == h and y == w:
        point = min(point,p)
    elif x == h:
        if grid[x][y+1] == '#':
            p += 1
        q.append([x,y+1,p])
    elif y == w:
        if grid[x+1][y] == '#':
            p += 1
        q.append([x+1,y,p])
    else:
        if grid[x+1][y] == '#':
            q.append([x+1,y,p+1])
        else:
            q.append([x+1,y,p])
        if grid[x][y+1] == '#':
            q.append([x,y+1,p+1])
        else:
            q.append([x,y+1,p])
ans += point
print(ans)

Submission status: Time Limit Exceeded

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

if s[0][0] == '#':
    b_0 = 1
else:
    b_0 = 0

B = H + W
for i in range(2 ** (H + W - 2)):
    n = [0, 0]
    b = b_0
    for j in range(H + W - 2):
        if ((i >> j) & 1):
            if n[0] == H - 1:
                b = H + W
                break
            n[0] += 1
            if s[n[0]][n[1]] == '#':
                b += 1
        else:
            if n[1] == W - 1:
                b = H + W
                break
            n[1] += 1
            if s[n[0]][n[1]] == '#':
                b += 1
    B = min(B, b)
print(B)

Submission status: Time Limit Exceeded

Solution code:
#A
from collections import deque
H,W = map(int,input().split())
G = [list(str(input())) for _ in range(H)]
inf = float("inf")

dist = [[inf for w in range(W)] for h in range(H)]
now = [[0,0]]

if G[0][0] == "#":
    dist[0][0] = 1
else:
    dist[0][0] = 0
    
D = deque([[0,0]])
while D:
    d = D.popleft()
    h,w = d
    if h < H-1:
        D.append([h+1,w])
        if G[h+1][w] == "#":
            dist[h+1][w] = min(dist[h+1][w],dist[h][w]+1)
        else:
            dist[h+1][w] = min(dist[h+1][w],dist[h][w])
    if w < W-1:
        D.append([h,w+1])
        if G[h][w+1] == "#":
            dist[h][w+1] = min(dist[h][w+1],dist[h][w]+1)
        else:
            dist[h][w+1] = min(dist[h][w+1],dist[h][w])

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

Submission status: Time Limit Exceeded

Solution code:
h,w = map(int,input().split())
s = [list(input()) for _ in range(h)]
def f(dh,dw):
  if s[dh][dw] == "#":
    a = 1
  else:
    a = 0
  if dh == h-1 and dw == w-1:
    return a
  elif dh == h-1:
    return a + f(dh,dw+1)
  elif dw == w-1:
    return a + f(dh+1,dw)
  else:
    return a + min(f(dh,dw+1),f(dh+1,dw))
print(f(0,0))

Submission status: Time Limit Exceeded

Solution code:
H, W = map(int, input().split())
S = [input() for _ in range(H)]
 
 
def solve(x, y, cost):
    if x == W - 1 and y == H - 1:
        return cost
 
    res = float('inf')
    if x < W - 1:
        res = min(res, solve(x + 1, y, cost + (1 if S[y][x + 1] == '#' else 0)))
    if y < H - 1:
        res = min(res, solve(x, y + 1, cost + (1 if S[y + 1][x] == '#' else 0)))
 
    return res
 
 
print(solve(0, 0, 1 if S[0][0] == '#' else 0))

Submission status: Time Limit Exceeded

Solution code:
import sys

H, W = map(int, sys.stdin.readline().split())
s = [list(sys.stdin.readline().rstrip()) for _ in range(H)]

ans = float("inf")


def dfs(x, y, tmp=0):
    if s[x][y] == "#":
        tmp = tmp + 1
    global ans
    if tmp > ans:
        return
    if x == H - 1 and y == W - 1:
        if tmp == 0:
            print(0)
            exit()
        ans = tmp
        return ans
    else:
        if x == H - 1:
            dfs(x, y + 1, tmp)
        elif y == W - 1:
            dfs(x + 1, y, tmp)
        else:
            dfs(x, y + 1, tmp)
            dfs(x + 1, y, tmp)


def main():
    dfs(0, 0)
    print(ans)


if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
import sys

H, W = map(int, sys.stdin.readline().split())
s = [list(sys.stdin.readline().rstrip()) for _ in range(H)]

ans = float("inf")


def dfs(x, y, tmp=0):
    if s[x][y] == "#":
        tmp = tmp + 1
    global ans
    if tmp > ans:
        return
    if x == H - 1 and y == W - 1:
        ans = tmp
        return ans
    else:
        if x == H - 1:
            dfs(x, y + 1, tmp)
        elif y == W - 1:
            dfs(x + 1, y, tmp)
        else:
            dfs(x, y + 1, tmp)
            dfs(x + 1, y, tmp)


def main():
    dfs(0, 0)
    print(ans)


if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
import sys

H, W = map(int, sys.stdin.readline().split())
s = [list(sys.stdin.readline().rstrip()) for _ in range(H)]

ans = []


def dfs(x, y, tmp=0):
    if s[x][y] == "#":
        tmp = tmp + 1
    if x == H - 1 and y == W - 1:
        return ans.append(tmp)
    else:
        if x == H - 1:
            dfs(x, y + 1, tmp)
        elif y == W - 1:
            dfs(x + 1, y, tmp)
        else:
            dfs(x, y + 1, tmp)
            dfs(x + 1, y, tmp)


def main():
    dfs(0, 0)
    print(min(ans))


if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
import sys
from collections import deque

#import numpy

readline = sys.stdin.readline
inf = float('inf')

def dfs(i, j, n):
    global grid, bfsque
    if grid[i][j] == '#':
        grid[i][j] = n
    if grid[i+1][j] == '#':
        dfs(i+1, j, n)
    if grid[i][j+1] == '#':
        dfs(i, j+1, n)
    if grid[i+1][j] == '.':
        bfsque.append([i+1, j])
    if grid[i][j+1] == '.':
        bfsque.append([i, j+1])


def main():
    global grid, bfsque
    H, W = map(int, readline().split())
    grid = []
    grid.append(['*'] * (W+2))
    for _ in range(H):
        grid.append(['*'] + list(readline()[:-1]) + ['*'])
    grid.append(['*']*(W+2))

    sbfs = True; sdfs = False
    bfsque = deque([[1,1]]); dfsque = deque()
    bfscnt = 0
    while True:
        while sbfs:
            fr = bfsque.popleft()
            if grid[fr[0]][fr[1]] == '.':
                grid[fr[0]][fr[1]] = bfscnt
            if grid[fr[0]][fr[1]] == '#':
                dfsque.append(fr)
                sbfs = False
                sdfs = True
                break
            tor = [fr[0], fr[1]+1]
            tod = [fr[0]+1, fr[1]]
            if grid[tor[0]][tor[1]] == '.':
                bfsque.append(tor)
            if grid[tor[0]][tor[1]] == '#':
                dfsque.append(tor)
            if grid[tod[0]][tod[1]] == '.':
                bfsque.append(tod)
            if grid[tod[0]][tod[1]] == '#':
                dfsque.append(tod)
            if len(bfsque) == 0:
                sbfs = False
                sdfs = True
        bfscnt += 1

        while sdfs:
            if len(dfsque) > 0:
                fr = dfsque.popleft()
                dfs(fr[0], fr[1], bfscnt)
            if len(dfsque) == 0:
                sbfs = True
                sdfs = False
        
        if not (grid[H][W] == '.' or grid[H][W] == '#'):
            break
    
    ans = grid[H][W]
    #print(numpy.array(grid))
    print(ans)


if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
from collections import deque
h,w=map(int,input().split())
s=[]
for i in range(h):
    s.append(list(input()))

dp=[[99999999 for i in range(w)] for i in range(h)]

q=deque()
#i,j,ans
q.append([0,0,0])

while(len(q)>0):
    i,j,ans=q.popleft()

    if(s[i][j]=='#'):
        ans+=1

    if(dp[i][j]>ans):
        dp[i][j]=ans

    if(j<w-1):
        q.append([i,j+1,ans])

    if(i<h-1):
        q.append([i+1,j,ans])

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

Submission status: Time Limit Exceeded

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

ans=99999999999

def dfs(i,j,right,down,obst):
#    print(i,j,right,down,obst)
    global ans
    obst_ij=obst
    if(s[i][j]=='#'):
        obst_ij+=1

    if(right+down>=h+w-2):
        ans=min(ans,obst_ij)

    if(right<w-1):
        #→
        dfs(i,j+1,right+1,down,obst_ij)

    if(down<h-1):
        #↓
        dfs(i+1,j,right,down+1,obst_ij)

dfs(0,0,0,0,0)
print(ans)

Submission status: Time Limit Exceeded

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


def solve(x, y, cost):
    if x == W - 1 and y == H - 1:
        return cost

    res = float('inf')
    if x < W - 1:
        res = min(res, solve(x + 1, y, cost + (1 if S[y][x + 1] == '#' else 0)))
    if y < H - 1:
        res = min(res, solve(x, y + 1, cost + (1 if S[y + 1][x] == '#' else 0)))

    return res


print(solve(0, 0, 1 if S[0][0] == '#' else 0))

Submission status: Time Limit Exceeded

Solution code:
import sys, copy, math, heapq, bisect
from itertools import accumulate
from collections import deque, defaultdict, Counter
sys.setrecursionlimit(500000)


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

global ans 
ans = 10**9+7
visited = [[0]*W for i in range(H)]
def dfs(now,color,num):
    global ans
    dire = ((1, 0), (0, 1))
    #visited[now[0]][now[1]] = 1
    que = deque([now]) # (sx, sy)からスタート
    while que:
        x, y = que.popleft()
        flag = True
        for dx, dy in dire:
            nx,ny = x+dx,y+dy
            if (nx,ny)==(H-1,W-1):
                if S[nx][ny]=='#':
                    ans = min(ans,num+1)
                else:
                    ans = min(ans,num)
                return
            if 0<=nx<H and 0<=ny<W and S[nx][ny] == color:
                que.append((nx,ny))
                #isited[nx][ny] = 1
                flag = False
        if flag:
            #print(x,y,color,num)
            if color=='.':
                dfs((x,y),'#',num+1)

            else:
                dfs((x,y),'.',num)

if S[0][0]=='.':
    dfs((0,0),'.',0)
else:
    dfs((0,0),'#',1)
print(ans)

Submission status: Time Limit Exceeded

Solution code:
maze = []
cnt = []
H,W = None,None

def dfs(x,y):
    if x< H-1:
        cnt[x+1][y] = min(cnt[x+1][y],cnt[x][y]+1) if maze[x+1][y]=="#" else min(cnt[x+1][y],cnt[x][y])
        dfs(x+1,y)
    if y< W-1:
        cnt[x][y+1] = min(cnt[x][y+1],cnt[x][y]+1) if maze[x][y+1]=="#" else min(cnt[x][y+1],cnt[x][y])
        dfs(x,y+1)


def main():
    INF = pow(10,6)
    global H,W,maze,cnt
    H,W = map(int,input().split())
    cnt = [[INF for i in range(W)] for j in range(H)]
    for i in range(H):
        tmp = list(input())
        maze.append(tmp)

    cnt[0][0] = 1 if maze[0][0]=="#" else 0
    dfs(x=0,y=0)
    print(cnt[H-1][W-1])
    return

if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
from functools import lru_cache
h,w= map(int, input().split())
maze = [[-1 for i in range(w)] for j in range(h)]

ans = 0
for i in range(h):
    maze[i] = input()

INF = 10000

@lru_cache(None)
def dfs(y,x,flg,cnt):
    if y == h-1 and x ==w-1:
        if flg ==1:
            cnt+=1
        return cnt
    ans = [INF]
    for (ny, nx) in [(y+1, x), (y, x+1)]:
        if 0 <= nx < w and 0 <= ny < h:
            if maze[ny][nx] != maze[y][x]:
                if flg == 0: ans.append(dfs(ny,nx,1,cnt))
                else: ans.append(dfs(ny,nx,0,cnt+1))
            else:
                ans.append(dfs(ny,nx,flg,cnt))
    return(min(ans))

print(dfs(0,0,(0 if maze[0][0]=='.' else 1),0))

Submission status: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(10 ** 9)
import numpy as np

h,w= map(int, input().split())
maze = [[-1 for i in range(w)] for j in range(h)]

ans = 0
for i in range(h):
    maze[i] = input()

INF = 10000

def dfs(y,x,flg,cnt):
    if y == h-1 and x ==w-1:
        return cnt
    ans = [INF]
    for (ny, nx) in [(y+1, x), (y, x+1)]:
        if 0 <= nx < w and 0 <= ny < h:
            if maze[ny][nx] != maze[y][x]:
                if flg == 0: ans.append(dfs(ny,nx,1,cnt))
                else: ans.append(dfs(ny,nx,0,cnt+1))
            else:
                ans.append(dfs(ny,nx,flg,cnt))
    return(min(ans))

print(dfs(0,0,(0 if maze[0][0]=='.' else 1),(0 if maze[0][0]=='.' else 1)))

Submission status: Time Limit Exceeded

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
    ab = input().split()
    w, h = int(ab[0]), int(ab[1])
    #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: Time Limit Exceeded

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
    w, h = map(int, input().split())
    #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: Time Limit Exceeded

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
    w, h = map(int, input().split())
  
    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: Time Limit Exceeded

Solution code:
from collections import deque

def solve(H, W, s):
    scores = [[float('inf') for _ in range(W)] for _ in range(H)]
    stack = deque()
    if s[0][0] == '.':
        scores[0][0] = 0
        stack.append([(0, 0), [(0, 0)]])
    else:
        scores[0][0] = 1
        stack.append([(0, 0), [(1, 0), (0, 1)]])

    while stack:
        (x, y), diff = stack.popleft()
        for next_x, next_y in [(x + 1, y), (x, y + 1)]:
            if not (next_x < H and next_y < W):
                continue
            if s[next_x][next_y] == '.':
                scores[next_x][next_y] = min(scores[next_x][next_y], scores[x][y])
                stack.append([(next_x, next_y), [(0, 0)]])
            elif (next_x - x, next_y - y) in diff:
                scores[next_x][next_y] = min(scores[next_x][next_y], scores[x][y])
                stack.append([(next_x, next_y), [(next_x - x, next_y - y)]])
            else:
                scores[next_x][next_y] = min(scores[next_x][next_y], scores[x][y] + 1)
                stack.append([(next_x, next_y), [(next_x - x, next_y - y)]])

    return scores[H - 1][W - 1]

if __name__ == '__main__':
    H, W = map(int, input().split())
    s = []
    for _ in range(H):
        s.append(list(input()))

    print(solve(H, W, s))

Submission status: Time Limit Exceeded

Solution code:
h,w=map(int,input().split())
grid=[[1 if s=='#' else 0 for s in list(input())] for i in range(h)]
#print(grid)
black=0
maxi=1000
from collections import deque
visited=[[1000]*w for _ in range(h)]
def bfs(s):
    q=deque()
    q.append(s)
    visited[s[0]][s[1]]=grid[s[0]][s[1]]
    D=[[1,0],[0,1]]
    while q:
        pre=q.pop()
        before=visited[pre[0]][pre[1]]
        for d in D:
            x=pre[0]+d[0]
            y=pre[1]+d[1]
            if 0<=x<h and 0<=y<w:
                q.append([x,y])
                visited[x][y]=min(visited[x][y],before+grid[x][y])

bfs([0,0])
print(visited[-1][-1])

Submission status: Time Limit Exceeded

Solution code:
from queue import deque

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

inf = 10**10
dx = [1,0]
dy = [0,1]
que = deque()

#そのマスにたどり着くまでに色が変わった最小の回数を保存するリスト
flip_count = [[inf for i in range(w)]for j in range(h)]

if li[0][0] == "#":
    flip_count[0][0] = 1
else:
    flip_count[0][0] = 0

que.append([0,0])

while que:
    k = que.popleft()
    x = k[0]
    y = k[1]
    for i,j in zip(dx,dy):
        nx = x + i
        ny = y + j
        if nx >= w or ny >= h:
            continue
        que.append([nx,ny])
        if li[ny][nx] != li[y][x]:
            flip_count[ny][nx] = min(flip_count[ny][nx],flip_count[y][x]+1)
        else:
            flip_count[ny][nx] = min(flip_count[ny][nx],flip_count[y][x])

if li[-1][-1] == "#":
    flip_count[-1][-1] += 1

print(flip_count[-1][-1]//2)