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:
from math import ceil,floor,comb,factorial,gcd,pow,sqrt,log2,cos,sin,tan,acos,asin,atan,degrees,radians,pi,inf
from itertools import accumulate,permutations,combinations,product,combinations_with_replacement
from collections import deque,defaultdict,Counter
from bisect import bisect_left,bisect_right
from operator import itemgetter
from heapq import heapify,heappop,heappush
from copy import deepcopy
from time import time
import string
import sys
sys.setrecursionlimit(10 ** 7)
def input() : return sys.stdin.readline().strip()
def INT()   : return int(input())
def MAP()   : return map(int,input().split())
def LIST()  : return list(MAP())

def bfs():
    que = deque()
    que.append([0, 0])
    if s[0][0] == '#':
        d[0][0] = 1
    else:
        d[0][0] = 0

    while que:
        p = que.popleft()
        if p[0] == h-1 and p[1] == w-1:
            break

        for i in range(2):
            ny = p[0] + dy[i]
            nx = p[1] + dx[i]
            if 0 <= ny < h and 0 <= nx < w:
                que.append([ny, nx])
                if s[p[0]][p[1]] == '.' and  s[ny][nx] == '#':
                    if d[ny][nx] > d[p[0]][p[1]]+1:
                        d[ny][nx] = d[p[0]][p[1]]+1
                        que.append([ny, nx])
                else:
                    if d[ny][nx] > d[p[0]][p[1]]:
                        d[ny][nx] = d[p[0]][p[1]]
                        que.append([ny, nx])

    return d[h-1][w-1]

h, w = MAP()
s = [input() for i in range(h)]
d = [[inf]*w for i in range(h)]

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

print(bfs())

Submission status: Time Limit Exceeded

Solution code:
from math import ceil,floor,comb,factorial,gcd,pow,sqrt,log2,cos,sin,tan,acos,asin,atan,degrees,radians,pi,inf
from itertools import accumulate,permutations,combinations,product,combinations_with_replacement
from collections import deque,defaultdict,Counter
from bisect import bisect_left,bisect_right
from operator import itemgetter
from heapq import heapify,heappop,heappush
from copy import deepcopy
from time import time
import string
import sys
sys.setrecursionlimit(10 ** 7)
def input() : return sys.stdin.readline().strip()
def INT()   : return int(input())
def MAP()   : return map(int,input().split())
def LIST()  : return list(MAP())

def bfs():
    que = deque()
    que.append([0, 0])
    if s[0][0] == '#':
        d[0][0] = 1
    else:
        d[0][0] = 0

    while que:
        p = que.popleft()
        if p[0] == h-1 and p[1] == w-1:
            break

        for i in range(2):
            ny = p[0] + dy[i]
            nx = p[1] + dx[i]
            if 0 <= ny < h and 0 <= nx < w:
                que.append([ny, nx])
                if s[p[0]][p[1]] == '.' and  s[ny][nx] == '#':
                    d[ny][nx] = min(d[ny][nx], d[p[0]][p[1]]+1)
                else:
                    d[ny][nx] = min(d[ny][nx], d[p[0]][p[1]])

    return d[h-1][w-1]

h, w = MAP()
s = [input() for i in range(h)]
d = [[inf]*w for i in range(h)]

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

print(bfs())

Submission status: Time Limit Exceeded

Solution code:
from math import ceil,floor,comb,factorial,gcd,pow,sqrt,log2,cos,sin,tan,acos,asin,atan,degrees,radians,pi,inf
from itertools import accumulate,permutations,combinations,product,combinations_with_replacement
from collections import deque,defaultdict,Counter
from bisect import bisect_left,bisect_right
from operator import itemgetter
from heapq import heapify,heappop,heappush
from copy import deepcopy
from time import time
import string
import sys
sys.setrecursionlimit(10 ** 7)
def input() : return sys.stdin.readline().strip()
def INT()   : return int(input())
def MAP()   : return map(int,input().split())
def LIST()  : return list(MAP())

def bfs():
    cnt = 0
    que = deque()
    que.append([0, 0])
    if s[0][0] == '#':
        d[0][0] = 1
    else:
        d[0][0] = 0

    while que:
        p = que.popleft()
        if p[0] == h-1 and p[1] == w-1:
            if cnt == 0:
                cnt += 1
            else:
                break

        for i in range(2):
            ny = p[0] + dy[i]
            nx = p[1] + dx[i]
            if 0 <= ny < h and 0 <= nx < w:
                que.append([ny, nx])
                if s[p[0]][p[1]] == '.' and  s[ny][nx] == '#':
                    d[ny][nx] = min(d[ny][nx], d[p[0]][p[1]]+1)
                else:
                    d[ny][nx] = min(d[ny][nx], d[p[0]][p[1]])

    return d[h-1][w-1]

h, w = MAP()
s = [input() for i in range(h)]
d = [[inf]*w for i in range(h)]

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

print(bfs())

Submission status: Time Limit Exceeded

Solution code:
h, w = map(int, input().split())
s = [list(input()) for _ in range(h)]
def dfs(x0, y0, cnt):
    ans = h * w
    for i, j in [(1, 0), (0, 1)]:
        x = x0 + i
        y = y0 + j
        ret = 0
        if 0 <= x < w and 0 <= y < h:
            if s[y][x] == "#" and s[y0][x0] == ".":
                ret += 1
            if x == w - 1 and y == h - 1:
                return cnt + ret
            ans = min(ans, dfs(x, y, cnt + ret))
    return ans

print(dfs(0, 0, 0 if s[0][0] == "." else 1))

Submission status: Time Limit Exceeded

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

dp = [[10**9 for _ in range(W)] for __ in range(H)]

cnt = 0
#solve
def dfs(i, j, score, lc):
    if lc == '.' and g[i][j] == '#':
        score += 1
    dp[i][j] = min(dp[i][j], score)

    if i+1 < H:
        dfs(i+1, j, score, g[i][j])
    if j+1 < W:
        dfs(i, j+1, score, g[i][j])        

dfs(0, 0, 0, '.')
print(dp[H-1][W-1])

Submission status: Time Limit Exceeded

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

dp = [[10**9 for _ in range(W)] for __ in range(H)]

cnt = 0
#solve
def dfs(i, j, score, lc):
    
    if i < H and i >= 0 and j < W and j >= 0:
        if lc == '.' and g[i][j] == '#':
            score += 1
        dp[i][j] = min(dp[i][j], score)

        if i+1 < H:
            dfs(i+1, j, score, g[i][j])
        if j+1 < W:
            dfs(i, j+1, score, g[i][j])        

dfs(0, 0, 0, '.')
print(dp[H-1][W-1])

Submission status: Time Limit Exceeded

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

dp = [[10**9 for _ in range(W)] for __ in range(H)]

#solve
def dfs(i, j, score, lc):
    if i < H and i >= 0 and j < W and j >= 0:
        if lc == '.' and g[i][j] == '#':
            score += 1
        dp[i][j] = min(dp[i][j], score)

        dfs(i+1, j, score, g[i][j])
        dfs(i, j+1, score, g[i][j])        
    
dfs(0, 0, 0, '.')
print(dp[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 p(x,y,res):
  if S[y][x]=="#":
    res+=1
  m,n=10001,10001
  if x==W-1 and y==H-1:
    return res
  else:
    if x!=W-1:
      m=p(x+1,y,res)
    if y!=H-1:
      n=p(x,y+1,res)
  return min(m,n)   
  
print(p(0,0,0))

Submission status: Time Limit Exceeded

Solution code:
import sys
from collections import deque

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

def main():
    H,W = map(int,input().split())
    S = [list(input()) for _ in range(H)]
    dp = [[float('inf') for _ in range(W)] for _ in range(H)]

    def bfs(x,y):
        que = deque()
        que.append((x,y))
        if S[y][x] == '.':
            dp[y][x] = 0
        else:
            dp[y][x] = 1
        while que.__len__():
            x,y = que.popleft()
            for dx,dy in ((1,0),(0,1)):
                sx = x + dx
                sy = y + dy
                if sx >= W or sy >= H:
                    continue
                if S[y][x] == '.' and S[sy][sx] == '#':
                    tmp = 1
                else:
                    tmp = 0
                dp[sy][sx] = min(dp[y][x]+tmp,dp[sy][sx])
                que.append((sx,sy))
    bfs(0,0)
    print(dp[H-1][W-1])
if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
from collections import deque

H,W = map(int,input().split())
S = [list(input()) for _ in range(H)]
dp = [[float('inf') for _ in range(W)] for _ in range(H)]

def bfs(x,y):
    que = deque()
    que.append((x,y))
    if S[y][x] == '.':
        dp[y][x] = 0
    else:
        dp[y][x] = 1
    while que.__len__():
        x,y = que.popleft()
        for dx,dy in ((1,0),(0,1)):
            sx = x + dx
            sy = y + dy
            if sx >= W or sy >= H:
                continue
            if S[y][x] == '.' and S[sy][sx] == '#':
                tmp = 1
            else:
                tmp = 0
            dp[sy][sx] = min(dp[y][x]+tmp,dp[sy][sx])
            que.append((sx,sy))
bfs(0,0)
print(dp[H-1][W-1])

Submission status: Time Limit Exceeded

Solution code:
#!/usr/bin python3
# -*- coding: utf-8 -*-

H, W = map(int,input().split())
sth, stw = 0, 0
glh, glw = H-1, W-1

INF = 10000
Gmap = [list(input()) for _ in range(H)]
Dist = [[INF]*W for _ in range(H)]
direc = {(1,0), (0,1)}

from collections import deque

def bfs(init):

    next_q = deque([])
    if Gmap[init[0]][init[1]]=="#":
        Dist[init[0]][init[1]] = 1
        next_q.append([0,0,"#"])
    else:
        Dist[init[0]][init[1]] = 0
        next_q.append([0,0,"."])

    while len(next_q)!=0:
        #キュー取り出し(先頭)
        h, w, fg = next_q.popleft()
        for d in direc:
            hs, ws = h + d[0], w + d[1]
            if not (0<=hs<H and 0<=ws<W):
                continue
            fgs = Gmap[hs][ws]
            if fgs=='#' and fg == '.':
                Dist[hs][ws] = min(Dist[h][w]+1, Dist[hs][ws])
            else:
                Dist[hs][ws] = min(Dist[h][w], Dist[hs][ws])
            next_q.append([hs,ws,fgs])
    return Dist

def main():
    ret = bfs([sth,stw])
    print(ret[glh][glw])

if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
#!/usr/bin python3
# -*- coding: utf-8 -*-

H, W = map(int,input().split())
sth, stw = 0, 0
glh, glw = H-1, W-1

INF = 10000
Gmap = [list(input()) for _ in range(H)]
Dist = [[INF]*W for _ in range(H)]
direc = {(1,0), (0,1)}

from collections import deque

def bfs(init):

    next_q = deque([])
    if Gmap[init[0]][init[1]]=="#":
        Dist[init[0]][init[1]] = 1
        next_q.append([0,0,"#"])
    else:
        Dist[init[0]][init[1]] = 0
        next_q.append([0,0,"."])

    while len(next_q)!=0:
        #キュー取り出し(先頭)
        h, w, fg = next_q.popleft()
        for d in direc:
            hs, ws = h + d[0], w + d[1]
            if not (0<=hs<H and 0<=ws<W):
                continue
            fgs = Gmap[hs][ws]
            if fgs=='#' and fg == '.':
                Dist[hs][ws] = min(Dist[h][w]+1, Dist[hs][ws])
            else:
                Dist[hs][ws] = min(Dist[h][w], Dist[hs][ws])
            next_q.append([hs,ws,fgs])
    return Dist

def main():
    ret = bfs([sth,stw])
    print(ret[glh][glw])

if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
H,W=map(int,input().split())
s=[]
dp=[[10**9]*(W)for _ in range(H)]
dp[0][0]=0
for i in range(H):
    S=input()
    s.append(S)
q=[(0,0)]
while q:
    a,b=q.pop(0)
    if a+1<H:
        if s[a][b]=="." and s[a+1][b]=="#":
            dp[a+1][b]=min(dp[a][b]+1,dp[a+1][b])
        else:
            dp[a+1][b]=min(dp[a][b],dp[a+1][b])
        q.append((a+1,b))
    if b+1<W:
        if s[a][b]=="." and s[a][b+1]=="#":
            dp[a][b+1]=min(dp[a][b]+1,dp[a][b+1])
        else:
            dp[a][b+1]=min(dp[a][b],dp[a][b+1])
        q.append((a,b+1))
ans=dp[H-1][W-1]
if s[0][0]=="#":
    ans+=1
print(ans)

Submission status: Time Limit Exceeded

Solution code:
#!/usr/bin/env python3
from collections import deque, Counter
from heapq import heappop, heappush
from bisect import bisect_right

H,W = map(int, input().split())
s = [None for _ in range(H)]
ans = H + W - 1

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

def saiki(i,j,count):
    global ans
    tmp = count
    if s[i][j] == '#':
        tmp += 1
    
    if (i,j) == (H-1,W-1):# ゴール
        ans = min(ans,tmp)
    else:
        if i < H-1:# 下へ分岐する
            saiki(i+1,j,tmp)
        if j < W-1:
            saiki(i,j+1,tmp)

saiki(0,0,0)
print(ans)

Submission status: Time Limit Exceeded

Solution code:
from collections import deque

H, W = map(int, input().split())
Maze = [[1 if a == "#" else 0 for a in input()] for _ in range(H)]

Q = deque()
f = 0
if Maze[0][0]:
    f += 1
Q.append((0, 0, f))
ans = 0
while Q:
    x, y, f = Q.popleft()
    if x == W - 1 and y == H - 1:
        ans = f
        break
    for d in range(2):
        nx = x + (0, 1)[d]
        ny = y + (1, 0)[d]
        if nx >= W or ny >= H:
            continue
        if Maze[y][x] == 0 and Maze[ny][nx] == 1:
            Q.append((nx, ny, f + 1))
        else:
            Q.appendleft((nx, ny, f))


print(ans)

Submission status: Time Limit Exceeded

Solution code:
from collections import deque

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

Q = deque()
f = 0
if Maze[0][0] == '#':
    f += 1
Q.append((0, 0, f))
ans = 0
while Q:
    x, y, f = Q.popleft()
    if x == W - 1 and y == H - 1:
        ans = f
        break
    for d in range(2):
        nx = x + (0, 1)[d]
        ny = y + (1, 0)[d]
        if nx >= W or ny >= H:
            continue
        if Maze[y][x] == '.' and Maze[ny][nx] == '#':
            Q.append((nx, ny, f + 1))
        else:
            Q.appendleft((nx, ny, f))


print(ans)

Submission status: Time Limit Exceeded

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

count = [[100000] * W for _ in range(W)]

def dfs(h,w,p):
    if h >= H or w >= W:
        return
    else:
        if S[h][w] == ".":
            count[h][w] = min(count[h][w], p)
            dfs(h+1, w, p)
            dfs(h, w+1, p)
        else:
            count[h][w] = min(count[h][w], p+1)
            dfs(h+1, w, p+1)
            dfs(h, w+1, p+1)

dfs(0,0,0)

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

Submission status: Time Limit Exceeded

Solution code:
from collections import deque

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

cost = [[10001] * w for _ in range(h)]

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

q = deque([[0, 0]])
moves = [[1, 0], [0, 1]]

while q:
    curr = q.popleft()
    curr_cost = cost[curr[0]][curr[1]]

    for m in moves:
        y, x = curr[0] + m[0], curr[1] + m[1]
        if y < h and x < w:
            if s[y][x] == "#":
                cost[y][x] = min(curr_cost + 1, cost[y][x])
            else:
                cost[y][x] = min(curr_cost, cost[y][x])
            q.append([y, x])
        else:
            continue

print(cost[-1][-1])

Submission status: Time Limit Exceeded

Solution code:
from collections import deque

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

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

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

q = deque([[0, 0]])
moves = [[1, 0], [0, 1]]

while q:
    curr = q.popleft()
    curr_cost = cost[curr[0]][curr[1]]

    for m in moves:
        if curr[0] + m[0] < h and curr[1] + m[1] < w:
            if s[curr[0] + m[0]][curr[1] + m[1]] == "#":
                cost[curr[0] + m[0]][curr[1] + m[1]] = min(curr_cost + 1, cost[curr[0] + m[0]][curr[1] + m[1]])
            else:
                cost[curr[0] + m[0]][curr[1] + m[1]] = min(curr_cost, cost[curr[0] + m[0]][curr[1] + m[1]])
            q.append([curr[0] + m[0], curr[1] + m[1]])
        else:
            continue

print(cost[-1][-1])

Submission status: Time Limit Exceeded

Solution code:
h,w = map(int,input().split())
s = [input() for _ in range(h)]
dp = [[-1]*w for i in range(h)]
dp[0][0] = 1 if s[0][0]=='#' else 0
q = [[0,0]]
while q:
    x,y = q.pop()
    a = 1 if s[x][y]=='#' else 0
    if x+1<h:
        if dp[x+1][y]<0:dp[x+1][y] = dp[x][y]+a
        else:dp[x+1][y] = min(dp[x][y]+a,dp[x+1][y])
        q.append([x+1,y])
    if y+1<w:
        if dp[x][y+1]<0:dp[x][y+1] = dp[x][y]+a
        else:dp[x][y+1] = min(dp[x][y]+a,dp[x][y+1])
        q.append([x,y+1])

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

Submission status: Time Limit Exceeded

Solution code:
h,w = map(int,input().split())
s = [input() for _ in range(h)]
dp = [[float('inf')]*w for i in range(h)]
dp[0][0] = 1 if s[0][0]=='#' else 0
q = [[0,0]]
while q:
    x,y = q.pop()
    a = 1 if s[x][y]=='#' else 0
    if x+1<h:
        dp[x+1][y] = min(dp[x][y]+a,dp[x+1][y])
        q.append([x+1,y])
    if y+1<w:
        dp[x][y+1] = min(dp[x][y]+a,dp[x][y+1])
        q.append([x,y+1])
print(dp[h-1][w-1])

Submission status: Time Limit Exceeded

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

q = deque()
inf = 10**6
used = [[inf]*W for _ in range(H)]
if S[0][0] == ".":
    used[0][0] = 0
else:
    used[0][0] = 1
q.append((0, 0))

while q:
    temp = q.popleft()
    r = temp[0]
    c = temp[1]
    if r < H-1:
        if S[r+1][c] == "#" and S[r][c] == ".":
            used[r+1][c] = min(used[r+1][c], used[r][c] + 1)
            q.append((r+1, c))
        else:
            used[r+1][c] = min(used[r+1][c], used[r][c])
            q.append((r+1, c))
    if c < W-1:
        if S[r][c+1] == "#" and S[r][c] == ".":
            used[r][c+1] = min(used[r][c+1], used[r][c] + 1)
            q.append((r, c+1))
        else:
            used[r][c+1] = min(used[r][c+1], used[r][c])
            q.append((r, c+1))
    
print(used[-1][-1])

Submission status: Time Limit Exceeded

Solution code:
def solve(S,x,y):
    if x == 0 and y ==0:
        return 0 if S[0][0]=="." else 1
    
    temp = 200
    if x != 0:
        temp =min(temp,solve(S,x-1,y))
    if y!= 0:
        temp = min(temp,solve(S,x,y-1))

    return temp +( 0 if S[y][x]=="." else 1)





def resolve():
    H,W = map(int,input().split())
    S = [input() for i in range(H)]
    
    print(solve(S,W-1,H-1))     


resolve()

Submission status: Time Limit Exceeded

Solution code:
def solve(S,x,y):
    if x == 0 and y ==0:
        return 0 if S[0][0]=="." else 1
    
    temp = 200
    if x != 0:
        temp =min(temp,solve(S,x-1,y))
    if y!= 0:
        temp = min(temp,solve(S,x,y-1))

    return temp +( 0 if S[y][x]=="." else 1)





def resolve():
    H,W = map(int,input().split())
    S = [input() for i in range(H)]
    
    print(solve(S,W-1,H-1))     


resolve()

Submission status: Time Limit Exceeded

Solution code:
from collections import defaultdict, deque, Counter
from heapq import heappush, heappop, heapify
from itertools import permutations, accumulate, combinations, combinations_with_replacement
from math import sqrt, ceil, floor, factorial
from bisect import bisect_left, bisect_right, insort_left, insort_right
from copy import deepcopy
from operator import itemgetter
from functools import reduce
from fractions import gcd
import sys
def input(): return sys.stdin.readline().rstrip()
def I(): return int(input())
def Is(): return map(int, input().split())
def LI(): return list(map(int, input().split()))
def TI(): return tuple(map(int, input().split()))
def IR(n): return [I() for _ in range(n)]
def LIR(n): return [LI() for _ in range(n)]
def TIR(n): return [TI() for _ in range(n)]
def S(): return input()
def Ss(): return input().split()
def LS(): return list(input())
def SR(n): return [S() for _ in range(n)]
def SsR(n): return [Ss() for _ in range(n)]
def LSR(n): return [LS() for _ in range(n)]
sys.setrecursionlimit(10**6)
MOD = 10**9+7
INF = 10**18
# ----------------------------------------------------------- #

h, w = Is()
s = LSR(h)
y = [1, 0]
x = [0, 1]

def dfs(sy, sx, gy, gx, ans, flag):
    if sy == gy and sx == gx:
        return 0
    for i in range(2):
        ny = sy + y[i]
        nx = sx + x[i]
        if 0 <= ny < h and 0 <= nx < w:
            if s[ny][nx] == '#':
                if flag:
                    ans = min(ans, dfs(ny, nx, gy, gx, ans, True))
                else:
                    ans = min(ans, dfs(ny, nx, gy, gx, ans, True)+1)
            else:  # s[ny][nx] == '.'
                ans = min(ans, dfs(ny, nx, gy, gx, ans, False))
    return ans

if s[0][0] == '.':
    print(dfs(0, 0, h-1, w-1, INF, False))
else:
    print(dfs(0, 0, h-1, w-1, INF, True)+1)

Submission status: Time Limit Exceeded

Solution code:
# A - Range Flip Find Route

import sys
sys.setrecursionlimit(10**7)

H, W = map(int, input().split())
S = [[''] * W for _ in range(H)]
for i in range(H):
    S[i] = list(str(input()))

def dfs(x, y, n):
    #print(x, y, n)
    global flg
    global ans
    if x == H-1 and y == W-1:
        ans = min(ans , n)
        #print('ans', ans)
        return ans 
    if y+1 < W:
        if flg == 0:
            if S[x][y+1] == '#':
                if n+1 >= ans:
                    return
                flg = 1
                dfs(x, y+1, n+1)
            else:
                dfs(x, y+1, n)
        elif flg == 1:
            if S[x][y+1] == '.':
                flg = 0
            dfs(x, y+1, n)
    if x+1 < H:
        if flg == 0:
            if S[x+1][y] == '#':
                if n+1 >= ans:
                    return
                flg = 1
                dfs(x+1, y, n+1)
            else:
                dfs(x+1, y, n)
        elif flg == 1:
            if S[x+1][y] == '.':
                flg = 0
            dfs(x+1, y, n)

ans = 10**10
if S[0][0] == '.':
    flg = 0
    dfs(0, 0, 0)
else:
    flg = 1
    dfs(0, 0, 1)

print(ans)

Submission status: Time Limit Exceeded

Solution code:
# A - Range Flip Find Route

import sys
sys.setrecursionlimit(10**7)

H, W = map(int, input().split())
S = [[''] * W for _ in range(H)]
for i in range(H):
    S[i] = list(str(input()))

def dfs(x, y, n):
    #print(x, y, n)
    global flg
    global ans
    if x == H-1 and y == W-1:
        ans = min(ans , n)
        #print('ans', ans)
        return ans 
    if y+1 < W:
        if flg == 0:
            if S[x][y+1] == '#':
                flg = 1
                dfs(x, y+1, n+1)
            else:
                dfs(x, y+1, n)
        elif flg == 1:
            if S[x][y+1] == '.':
                flg = 0
            dfs(x, y+1, n)
    if x+1 < H:
        if flg == 0:
            if S[x+1][y] == '#':
                flg = 1
                dfs(x+1, y, n+1)
            else:
                dfs(x+1, y, n)
        elif flg == 1:
            if S[x+1][y] == '.':
                flg = 0
            dfs(x+1, y, n)

ans = 10**10
if S[0][0] == '.':
    flg = 0
    dfs(0, 0, 0)
else:
    flg = 1
    dfs(0, 0, 1)

print(ans)

Submission status: Time Limit Exceeded

Solution code:
def main():
    from heapq import heappush, heappop

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

    h = [(int(s[0][0] == '#'), 0, 0)]

    while h:
        bk, r, c = heappop(h)
        if r == H - 1 and c == W - 1:
            print(bk)
            return

        curr = s[r][c]
        if r < H - 1:
            if curr == s[r + 1][c]:
                heappush(h, (bk, r + 1, c))
            elif curr == '.':
                heappush(h, (bk + 1, r + 1, c))
            else:
                heappush(h, (bk, r + 1, c))

        if c < W - 1:
            if curr == s[r][c + 1]:
                heappush(h, (bk, r, c + 1))
            elif curr == '.':
                heappush(h, (bk + 1, r, c + 1))
            else:
                heappush(h, (bk, r, c + 1))


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
def main():
    from collections import deque

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

    dq = deque()
    dq.append((0, 0, int(s[0][0] == '#')))

    ans = 1 << 60
    while dq:
        r, c, bk = dq.popleft()
        if r == H - 1 and c == W - 1:
            if ans > bk:
                ans = bk
            continue

        curr = s[r][c]
        if r < H - 1:
            if curr == s[r + 1][c]:
                dq.append((r + 1, c, bk))
            elif curr == '.':
                dq.append((r + 1, c, bk + 1))
            else:
                dq.append((r + 1, c, bk))
        if c < W - 1:
            if curr == s[r][c + 1]:
                dq.append((r, c + 1, bk))
            elif curr == '.':
                dq.append((r, c + 1, bk + 1))
            else:
                dq.append((r, c + 1, bk))

    print(ans)


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
import itertools

H, W = [int(i) for i in input().split()]
sw = []
for i in range(H):
    sw.append([j for j in input()[::1]])
l = ["h"] * (H-1) + ["w"] * (W-1)

min_score = H + W - 1
l = set(itertools.permutations(l))
for i in l:
    sw_ij = (0,0)
    score = 0 if sw[0][0] == "." else 1
    for j in i:
        sw_ij = (sw_ij[0]+1, sw_ij[1]) if j == "h" else (sw_ij[0], sw_ij[1]+1)
        score += 1 if sw[sw_ij[0]][sw_ij[1]] == "#" else 0
        if score == min_score:
            break
    if score < min_score:
        min_score = score
print(min_score)

Submission status: Time Limit Exceeded

Solution code:
import itertools

H, W = [int(i) for i in input().split()]
sw = []
for i in range(H):
    sw.append([j for j in input()[::1]])
l = ["h"] * (H-1) + ["w"] * (W-1)

min_score = H + W - 1
l = set(itertools.permutations(l))
for i in l:
    sw_i = 0
    sw_j = 0
    score = 0 if sw[0][0] == "." else 1
    for j in i:
        if j == "h":
            sw_i += 1
        else:
            sw_j += 1
        score += 1 if sw[sw_i][sw_j] == "#" else 0
        if score >= min_score:
            break
    if score < min_score:
        min_score = score
print(min_score)

Submission status: Time Limit Exceeded

Solution code:
import itertools

H, W = [int(i) for i in input().split()]
sw = []
for i in range(H):
    sw.append([j for j in input()[::1]])
l = ["h"] * (H-1) + ["w"] * (W-1)

min_score = H + W - 1
l = set(itertools.permutations(l))
for i in l:
    sw_ij = [0,0]
    score = 0 if sw[0][0] == "." else 1
    for j in i:
        sw_ij = [sw_ij[0]+1, sw_ij[1]] if j == "h" else [sw_ij[0], sw_ij[1]+1]
        score += 1 if sw[sw_ij[0]][sw_ij[1]] == "#" else 0
        if score == min_score:
            break
    if score < min_score:
        min_score = score
print(min_score)

Submission status: Time Limit Exceeded

Solution code:
from collections import deque
h, w = map(int, input().split())
s_list = []
for _ in range(h):
    s = input()
    s_list.append(s)
d = deque()
count = 0
if s_list[0][0] == '#':
    count += 1
d.append([0, 0, count])

ans = 101
while d:
    x, y, count = d.pop()
    for xx, yy in [[1, 0], [0, 1]]:
        if (0 <= x + xx < h) & (0 <= y + yy < w):
            if (s_list[x + xx][y + yy] == '#') & (s_list[x][y] == '.'):
                d.append([x + xx, y + yy, count + 1])
            else:
                d.append([x + xx, y + yy, count])
        if (x + xx == h - 1) & (y + yy == w - 1):
            if s_list[x + xx][y + yy] == '#':
	            ans = min(ans, count + 1)
            else:
                ans = min(ans, count)
print(ans)

Submission status: Time Limit Exceeded

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

def g(j):
    if j==".":
        return 1 #白
    else:
        return 0 #黒
    
S=[]
for j in range(H):
    S.append(list(map(g,input())))

def bools(b):
    if b==True:
        return 1
    else:
        return 0

def m(x,y):
    if (x,y)==(W-1,H-1):
        return 0
    elif x==W-1:
        return m(x,y+1)+bools(S[y][x]!=S[y+1][x])
    
    elif y==H-1:
        return m(x+1,y)+bools(S[y][x]!=S[y][x+1])

    else:
        return min(m(x+1,y)+bools(S[y][x]!=S[y][x+1]),m(x,y+1)+bools(S[y][x]!=S[y+1][x]))

print((m(0,0)+bools(S[0][0]==0)+1)//2)

Submission status: Time Limit Exceeded

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

def g(j):
    if j==".":
        return 1 #白
    else:
        return 0 #黒
    
S=[]
for j in range(H):
    S.append(list(map(g,input())))

def m(x,y):
    if (x,y)==(W-1,H-1):
        return 0
    elif x==W-1:
        if S[y][x]==1 and S[y+1][x]==0:
            return m(x,y+1)+1
        else:
            return m(x,y+1)
    
    elif y==H-1:
        if S[y][x]==1 and S[y][x+1]==0:
            return m(x+1,y)+1
        else:
            return m(x+1,y)

    else:
        v=m(x+1,y)
        u=m(x,y+1)
        
        s=S[y][x]
        if s==1 and S[y][x+1]==0:
            v+=1
        if s==1 and S[y+1][x]==0:
            u+=1

        return min(u,v)

print(m(0,0)+1-S[0][0])

Submission status: Time Limit Exceeded

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

ansList = []

def dfs(h, w, root):
    root.append(S[h][w])
    if (h == H - 1 and w == W - 1):
        ansList.append(root.copy())
        return
    else:
        if (h+1 < H):
            dfs(h+1, w, root.copy())
        if (w+1 < W):
            dfs(h, w+1, root.copy())
dfs(0, 0, [])

ans = H * W
for a in ansList:
    ans = min(ans, a.count("#"))

print(ans)

Submission status: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(1000000)

h, w = map(int, input().split())
maze = [list(input()) for i in range(h)]
flag = 0
    
def dfs(x, y, cnt):
    global flag
    if x == w - 1 and y == h - 1:
        flag = 1
        return 
    
    dx = [1, 0]
    dy = [0, 1]

    for i in range(2):
        nx = x + dx[i]
        ny = y + dy[i]
        
        
        if 0 <= nx <= w - 1 and 0 <= ny <= h - 1:
            if maze[ny][nx] == ".":
                dfs(nx, ny, cnt)
            elif maze[ny][nx] == "#" and cnt > 0:
                dfs(nx, ny, cnt - 1)

ans = 0

while ans < h * w:
    dfs(0, 0, ans)
    if flag == 1:
        break
    ans += 1
    
if maze[0][0] == "#":
    ans += 1
    
print(ans)