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:
H, W = map(int, input().split())
field = [list(input()) for _ in range(H)]

count = []
def dfs(x,y,cnt):
    if x==H-1 and y==W-1:
        count.append(cnt)
        return
    if y < W-1:
        if field[x][y]=='#':
            dfs(x,y+1,cnt+1)
        else:
            dfs(x,y+1,cnt)
    if x < H-1:
        if field[x][y]=='#':
            dfs(x+1,y,cnt+1)
        else:
            dfs(x+1,y,cnt)


if field[0][0]=='#':
    dfs(0,0,1)
else:
    dfs(0,0,0)

print(min(count))

Submission status: Time Limit Exceeded

Solution code:
import math

def bfs(N,M,Map):
	# 始点，終点探索
	
    sx, sy = 0, 0
    gx, gy = H, W

    INF = float('inf')

    d = [[INF] * N for _ in range(M)]
    # スタート地点をキューに入れる
    que = [(sy, sx)]
    if Map[sy][sx] == '#':
        d[sy][sx] = 1
    else:
        # 始点を0にしてindexをつける
        d[sy][sx] = 0

    while que and que[0] != (gy,gx):

        py, px = que.pop(0)

        # 右か下方向に移動
        for ny, nx in (py+1, px), (py, px+1):

            if 0 <= nx and nx < N and 0 <= ny and ny < M:
                    que.append([ny,nx])
                    if Map[py][px] == '#':
                        if d[ny][nx] > d[py][px]:
                            d[ny][nx] = d[py][px] + 1
                    else: 
                        d[ny][nx] = d[py][px]

    return d[gy-1][gx-1]

H, W = map(int, input().split())
mp = []
for _ in range(H):
    mp.append(input())
res = bfs(H,W,mp)

print(res)

Submission status: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(10 ** 7)

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

d = [[1, 0], [0, 1]]

ans = float("inf")


def dfs(hh, ww, c, cnt):
    if hh == h - 1 and ww == w - 1:
        global ans
        ans = min(ans, cnt)

    for dh, dw in d:
        nh = hh + dh
        nw = ww + dw
        if nh < h and nw < w:
            if c == "#":
                dfs(nh, nw, s[nh][nw], cnt)
            else:
                if s[nh][nw] == "#":
                    dfs(nh, nw, s[nh][nw], cnt + 1)
                else:
                    dfs(nh, nw, s[nh][nw], cnt)


dfs(0, 0, s[0][0], 0)
if s[0][0] == "#":
    ans += 1
print(ans)

Submission status: Time Limit Exceeded

Solution code:
from collections import deque
h, w = map(int, input().split())
mass = [input() for _ in range(h)]


# 座標r, c, 変更数x
inf = 10**9
q = deque([[0, 0]])
depth = [[inf]*w for _ in range(h)]
if mass[0][0] == "#":
    depth[0][0] = 1
else:
    depth[0][0] = 0

while True:
    x, y = q.popleft()

    if x == h-1 and y == w-1:
        break
    if x < h-1:
        if mass[x+1][y] == "#":
            q.append([x+1, y])
            depth[x+1][y] = min(depth[x][y] + 1, depth[x+1][y])
        else:
            q.appendleft([x+1, y])
            depth[x+1][y] = min(depth[x][y], depth[x+1][y])

    if y < w-1:
        if mass[x][y+1] == "#":
            q.append([x, y+1])
            depth[x][y+1] = min(depth[x][y] + 1, depth[x][y+1])
        else:
            q.appendleft([x, y+1])
            depth[x][y+1] = min(depth[x][y], depth[x][y+1])

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

Submission status: Time Limit Exceeded

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



def bfs(x, y):
    d = [[INF] * w for i in range(h)]
    dx = [1,0]
    dy = [0,1]
    if s[0][0] == '#':
        d[0][0] = 1
    else:
        d[0][0] = 0
    que = deque([(0, 0)])

    while len(que) != 0:
        val = que.popleft()

        for i in range(2):
            nx = val[0] + dx[i]
            ny = (val[1] + dy[i])
            if nx < h and ny < w:

                que.append((nx, ny))
                if (s[nx][ny] == '#') and (d[nx][ny] > d[val[0]][val[1]]):
                    d[nx][ny] = min(d[val[0]][val[1]] + 1, d[nx][ny])
                elif s[nx][ny] != '#' and d[nx][ny] < d[val[0]][val[1]]:
                    d[nx][ny] = d[nx][ny]

                else:
                    d[nx][ny] = d[val[0]][val[1]]
    return d[h-1][w-1]
print(bfs(h, w))

Submission status: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(10 ** 7)

read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

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


def dfs(r, c, cnt, iswhite=True):
    # if r == H - 1 and c == W - 1:
        # return cnt

    now = '.' if iswhite == True else '#'

    ans = 200

    if MEIJI[r][c] != now:
        if iswhite == True:
            cnt += 1

        iswhite = not (iswhite)

    if r == H-1 and c == W - 1:
        return cnt
    if r < H-1:
        ans = min(dfs(r + 1, c, cnt, iswhite), ans)
    if c < W-1:
        ans = min(dfs(r, c + 1, cnt, iswhite), ans)

    return ans


ans = dfs(0, 0, 0, True)
print(ans)

Submission status: Time Limit Exceeded

Solution code:
from sys import stdin, stdout
from itertools import permutations
h, w = stdin.readline().split()
h = int(h)
w = int(w)
l = [list(input()) for x in range(h)]
ans = 999999999
l2 = list(0 for i in range(h-1)) + list(1 for i in range(w-1))
for perm in permutations(l2):
	cnt, i, j = 0, 0, 0
	if l[i][j] == '#':
		cnt += 1
	for k in perm:
		if k:
			j+=1
		else:
			i+=1
		if l[i][j] == '#':
			cnt += 1
	ans = min(ans, cnt)
print(ans)

Submission status: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(10 ** 7)

read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

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


def dfs(r, c, cnt, iswhite=True):
    #if r == H - 1 and c == W - 1:
        #return cnt

    now = '.' if iswhite == True else '#'

    ans = 200

    if MEIJI[r][c] != now:
        if iswhite == True:
            cnt += 1

        iswhite = not (iswhite)
        
    if r == H-1 and c == W - 1:
        return cnt
    if r < H-1:
        ans = min(dfs(r + 1, c, cnt, iswhite), ans)
    if c < W-1:
        ans = min(dfs(r, c + 1, cnt, iswhite), ans)

    return ans


ans = dfs(0, 0, 0, True)
print(ans)

Submission status: Time Limit Exceeded

Solution code:
def dfs(row, col, count):
    global n, m
    global grid

    if row == n-1 and col == m-1:
        if grid[row][col] == '.':
            count += 1
        counts.append(count)
        return
    else:
        if grid[row][col] == '.':
            count += 1
        if row+1 <= n-1:
            dfs(row+1,col,count)
        if col+1 <= m-1:
            dfs(row,col+1,count)


n, m = map(int, input().split())
counts = []
grid = [[0 for i in range(m)]for j in range(n)]
for row in range(n):
    temp = input()
    for col in range(m):
        grid[row][col] = temp[col]

dfs(0,0,0)
print(m+n-1 - max(counts))

Submission status: Time Limit Exceeded

Solution code:
from collections import deque

h,w = [int(x) for x in input().split()]
m = []
for _ in range(h):
    m.append(list(input()))
ans = 0
if m[0][0]=="#":
    m[0][0]="."
    ans+=1
if m[h-1][w-1]=="#":
    m[h-1][w-1]="."
    ans += 1

q = deque()
v = deque()
q.append([0,0,0])
while q or v:
    if q:
        p = q.popleft()
        if p[0]==h-1 and p[1]==w-1:
            ans += p[2]
            break
        for dy,dx in [[1,0],[0,1]]:
            ny = p[0]+dy
            nx = p[1]+dx
            if 0<=ny<h and 0<=nx<w:
                if m[ny][nx]==".":
                    q.append([ny,nx,p[2]])
                else:
                    v.append([ny,nx,p[2]+1])
    else:
        z = v.popleft()
        for dy,dx in [[1,0],[0,1]]:
            ny = z[0]+dy
            nx = z[1]+dx
            if 0<=ny<h and 0<=nx<w:
                if m[ny][nx]==".":
                    q.append([ny,nx,z[2]])
                else:
                    v.append([ny,nx,z[2]+1])

print(ans)

Submission status: Time Limit Exceeded

Solution code:
#template
def inputlist(): return [int(i) for i in input().split()]
#template
#issueから始める
from sys import setrecursionlimit
setrecursionlimit(10**6)
H,W = inputlist()
maze = ['0']*H
for i in range(H):
    maze[i] = list(input())
import heapq
from collections import deque
li = deque()
def dfs(x,y,count):
    if maze[x][y] == '#':
        count+=1
    if x == H-1 and y == W-1:
        li.append(count)
        return True
    if x < H-1:
        dfs(x+1,y,count)
    if y < W-1:
        dfs(x,y+1,count)
dfs(0,0,0)
li = list(li)
heapq.heapify(li)
print(heapq.heappop(li))

Submission status: Time Limit Exceeded

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

min_count = 10 ** 4 + 1

def dfs(h, w, before_black, count):
    if maze[h][w] == "#":
        is_black = True
        if not before_black:
            count += 1
    else:
        is_black = False
    if h == H-1 and w == W-1:
        global min_count
        if count < min_count:
            min_count = count
    elif h == H-1:
        dfs(h, w+1, is_black, count)
    elif w == W-1:
        dfs(h+1, w, is_black, count)
    else:
        dfs(h+1, w, is_black, count)
        dfs(h, w+1, is_black, count)

dfs(0,0,False,0)

print(min_count)

Submission status: Time Limit Exceeded

Solution code:
import queue
def main():
    h, w = map(int, input().split())
    s = [list(input().rstrip()) for _ in range(h)]
#    q = queue.Queue()
    a = []
    t = [[10**9]*w for _ in range(h)]
    if s[h-1][w-1] == "#":
        t[h-1][w-1] = 1
#        q.put([h-1, w-1])
    else:
        t[h-1][w-1] = 0
    a.append([h-1, w-1])
    while 0 < len(a):
        y, x = a[len(a)-1][0], a[len(a)-1][1]
        if y < h-1 and x < w-1:
            py = t[y+1][x]
            if s[y][x] == "#" and s[y+1][x] == ".":
                py += 1
            px = t[y][x+1]
            if s[y][x] == "#" and s[y][x+1] == ".":
                px += 1
            t[y][x] = min(py, px)
        elif y == h-1 and x < w-1:
            px = t[y][x+1]
            if s[y][x] == "#" and s[y][x+1] == ".":
                px += 1
            t[y][x] = px
        elif x == w-1 and y < h-1:
            py = t[y+1][x]
            if s[y][x] == "#" and s[y+1][x] == ".":
                py += 1
            t[y][x] = py
        a.pop(-1)
        if 0 < y:
            a.append([y-1, x])
        if 0 < x:
            a.append([y, x-1])

#        q.put([h-1, w-1])
#    while not q.empty():
#        y, x = q.get()
#        print(y, x)
#        if 0 < y and 0 < x:
#            if s[y][x] == "#":
#                q.put([y-1, x])
#                q.put([y, x-1])
#            else:
#                if s[y-1][x] == "#":
#                    t[y-1][x] = t[y][x] + 1
#                else:
#                    t[y-1][x] = t[y][x]
#                if s[y][x-1] == "#":
#                    t[y][x-1] = t[y][x] + 1
#                else:
#                    t[y][x-1] = t[y][x]
#            q.put([y-1, x])
#            q.put([y, x-1])
#        elif y == 0 and 0 < x:
#            if s[y][x] == "#":
#                q.put([y, x-1])
#            else:
#                if s[y][x-1] == "#":
#                    t[y][x-1] = t[y][x] + 1
#                else:
#                    t[y][x-1] = t[y][x]
#            q.put([y, x-1])
#        elif x == 0 and 0 < y:
#            if s[y][x] == "#":
#                q.put([y-1, x])
#            else:
#                if s[y-1][x] == "#":
#                    t[y-1][x] = t[y][x] + 1
#                else:
#                    t[y-1][x] = t[y][x]
#            q.put([y-1, x])
    print(t[0][0])

if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:

#####

import numpy as np
# from numpy import int32, int8
# from collections import defaultdict

#####

def getIntList(inp):
	return [int(_) for _ in inp]


from sys import stdin
import sys
sys.setrecursionlimit(10**8)

def getInputs():
	inputs=[]
	for line in stdin:
		line=line.split()
		inputs.append(line)
	return inputs


def travel(colors, h, w, row0, col0, targetColor, flipSize):
	
# 	print()
# 	print("row0",row0,"col0",col0,"flipSize",flipSize)
	
	visited=np.zeros((h, w), np.bool)
	visited[row0,col0]=True
	next=set()
	for hi in range(row0, h):
		for wi in range(col0, w):
			c=colors[hi,wi]==targetColor
			if hi>0 and visited[hi-1,wi]:
				if c:
					visited[hi,wi]=True
				else:
					next.add((hi,wi))
			if wi>0 and visited[hi,wi-1]:
				if c:
					visited[hi,wi]=True
				else:
					next.add((hi,wi))
	
	if visited[h-1,w-1]:
# 		print("found")
		return flipSize
					
# 	print(next)
	if len(next)==0: return None
	minFlipSize=None
	if targetColor: nextFlipSize=flipSize+1
	else: nextFlipSize=flipSize
	for nr,nc in next:
		fs=travel(colors, h, w, nr, nc, not targetColor, nextFlipSize)
		if fs is None: continue
		if minFlipSize is None or fs<minFlipSize: minFlipSize=fs
	return minFlipSize
				

def main(inputs):
	h,w=getIntList(inputs[0])
	colors=np.empty((h,w),np.bool)
	for hi in range(h):
		for wi in range(w):
			colors[hi,wi]=inputs[1+hi][0][wi]=="."
# 	print(colors)
	
	if colors[0,0]: nextFlipSize=0
	else: nextFlipSize=1
	flipSize=travel(colors, h, w, 0, 0, colors[0,0], nextFlipSize)
# 	print("flipSize",flipSize)
	print(flipSize)
	

if __name__=="__main__":
	inputs=getInputs()
# 	inputs=simInputs()
	main(inputs)

Submission status: Time Limit Exceeded

Solution code:
def inputs(): return [int(x) for x in input().split()]
h,w = inputs()
meiro=[list(input()) for _ in range(h)]
visit = [[-1]*w for _ in range(h)]
#if meiro[0][0]=="#":
#  a = 1
#else:
#  a=0
stk = [[(0,0),(-1,-1),0]]
while stk:
    v,p,cnt = stk.pop()
    vx,vy = v
    px,py = p
    if w<=vx or h<=vy or (visit[vy][vx]!=-1 and visit[vy][vx]<cnt):
        continue
    if py==-1 and px==-1:
      if meiro[vy][vx]=="#":
        visit[vy][vx]=1
        cnt+=1
      else:
        visit[vy][vx]=0
    elif meiro[vy][vx]=="#"  and meiro[py][px]=="#":
        visit[vy][vx] = cnt
    elif meiro[vy][vx]=="#" and meiro[py][px]!="#":
        visit[vy][vx] = cnt+1
        cnt+=1
    elif meiro[vy][vx]==".":
        visit[vy][vx]=cnt
    dx = [0,1]
    dy = [1,0]
    for i in range(2):
        vx1 = vx+dx[i]
        vy1 = vy+dy[i]
        stk.append([(vx1,vy1),(vx,vy),cnt])
print(visit[h-1][w-1])

Submission status: Time Limit Exceeded

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

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

goal_cnt = [10**20]
def dfs(x, y, cnt):
    if cnt >= goal_cnt[0]:
        return
    if field[y][x] == "#":
        cnt += 1
    if x == W-1 and y == H-1:
        goal_cnt[0] = min(goal_cnt[0], cnt)
        return
    for nx, ny in ((1,0),(0,1)):
        nx += x
        ny += y
        if nx >= W or ny >= H:
            continue
        dfs(nx, ny, cnt)

dfs(0,0,0)
print(goal_cnt[0])

Submission status: Time Limit Exceeded

Solution code:
H, W = map(int,input().split())
l = [list(input()) for _ in range(H)]
def DFS(r, c, cnt):
  if l[r][c] == '#':
    cnt += 1
  if r == H - 1 and c == W - 1:
    return cnt
  
  if c + 1 >= W:
    cnt = DFS(r + 1, c, cnt)
  elif r + 1 >= H:
    cnt = DFS(r, c + 1, cnt)
  else:
    cnt = min(DFS(r, c + 1, cnt), DFS(r + 1, c, cnt))
  return cnt

print(DFS(0, 0, 0))

Submission status: Time Limit Exceeded

Solution code:
import bisect
import math
from collections import deque

def sRaw():
    return input().rstrip("\r")


def iRaw():
    return int(input())


def ssRaw():
    return input().split()


def isRaw():
    return list(map(int, ssRaw()))


INF = 1 << 29

DIV = (10**9) + 7


def mod_inv_prime(a, mod=DIV):
    return pow(a, mod-2, mod)


def ncr(n, r, mod=DIV):
	r = min(r, n-r)
	ret = 1
	for i in range(1, r+1):
		ret = ret * (n-i+1) % mod
		ret = ret * mod_inv(i, mod) % mod
	return ret


def mod_inv(a, b):
    r = a
    w = b
    u = 1
    v = 0
    while w != 0:
        t = r//w
        r -= t*w
        r, w = w, r
        u -= t*v
        u, v = v, u
    return (u % b+b) % b


def CONV_TBL(max, mod=DIV):
    fac, finv, inv = [0]*max, [0]*max, [0]*max
    fac[0] = fac[1] = 1
    finv[0] = finv[1] = 1
    inv[1] = 1
    for i in range(2, max):
        fac[i] = fac[i-1]*i % mod
        inv[i] = mod - inv[mod % i] * (mod//i) % mod
        finv[i] = finv[i-1]*inv[i] % mod

    class CONV:
        def __init__(self):
            pass

        def ncr(self, n, k):
            if(n < k):
                return 0
            if(n < 0 or k < 0):
                return 0
            return fac[n]*(finv[k]*finv[n-k] % mod) % mod
    return CONV()


def matchAB(a,b):
    #print ("matching",a,b)
    tmp = -1
    tmp_res =""
    for ai_start in range(len(a)):
        ai = ai_start
        notMached= False
        for bi,bc in enumerate(b):
            ac = a[ai]
            if ac!="?" and bc!="?" and ac!=bc:
                notMached = True
                break
            ai+=1
            if ai == len(a):
                if bi!=len(b):
                    tmp_res = b[bi+1:]
                break
        
        if notMached == False:
            tmp = ai_start
            if ai != len(a):
                tmp_res = a[ai+1:]  
            break
    if tmp == -1:
        #print(a+b, tmp, tmp_res)
        return a+b
    else:
        ans = a[:ai_start]
        for aidx in range(ai_start, ai_start+ min(len(a)-ai_start,len(b))):
            if a[aidx]=="?":
                ans += b[aidx-ai_start]
            else:
                ans+=a[aidx]
        #print (ans,tmp,tmp_res)
        return ans+tmp_res

def matchABC(a,b,c):
    s = matchAB(matchAB(a, b), c)
    #print(s)
    return len(s)

def isReach(ss):
    W = len(ss[0])
    H = len(ss)
    qu = deque()
    isF = 1 if ss[0][0] == "#" else 0
    qu.append([0,0,isF,isF])
    ans = INF
    while len(qu)!=0:
        x,y,z,isF = qu.popleft()
        if x == W-1 and y == H-1:
            ans = min(ans, z)
            continue
        if x!=W-1:
            nx = x+1
            nisF = 1 if ss[nx][y] == "#" else 0
            z2 = z
            if nisF==1 and isF==0:
                z2+=1
            qu.append([nx,y,z2,nisF])
        if y!=H-1:
            ny = y+1
            nisF = 1 if ss[x][ny] == "#" else 0
            z2 = z
            if nisF == 1 and isF == 0:
                z2 += 1
            qu.append([x, ny, z2, nisF])
        
    return ans

def main():
    H,W  =isRaw()
    ss = [sRaw() for _ in range(H)]
    return isReach(ss)
    
if __name__ == "__main__":
    print(main())

Submission status: Time Limit Exceeded

Solution code:
from collections import deque
from math import ceil
H, W = [int(i) for i in input().split()]
s = [input() for _ in range(H)]

dq = deque()
D = [[999999999999]*W for _ in range(H)]
if s[0][0] == '.':
    D[0][0] = 0
else:
    D[0][0] = 1
dq.append((1, 0, s[0][0], D[0][0]))
dq.append((0, 1, s[0][0], D[0][0]))

while len(dq):
    h, w, m, d = dq.popleft()
    if s[h][w] != m:
        d += 1
    D[h][w] = min(D[h][w], d)

    for nh, nw in ((h+1, w), (h, w+1)):
        if nh < H and nw < W:
            dq.append((nh, nw, s[h][w], d))
print(ceil(D[-1][-1]/2))

Submission status: Time Limit Exceeded

Solution code:
from collections import deque
H, W = [int(i) for i in input().split()]
Shw = [[0 if i =="." else 1 for i in input()] for _ in range(H)]

changes = [[-1 for _ in range(W)] for _ in range(H)]
que = deque()
i0 = 0
j0 = 0
que.append((i0, j0,  0, 0))

while len(que) > 0:
  i, j,  o, c = que.popleft()
  current = Shw[j][i]
  diff = 1 if current > 0 and o == 0 else 0
  change = c + diff
  if changes[j][i] == -1:
    changes[j][i] = change
  else:
    changes[j][i] = min(change, changes[j][i])
  if i < W-1:
    que.append((i+1, j, current, change))
  if j < H-1:
    que.append((i, j+1, current, change))
print(changes[-1][-1])

Submission status: Time Limit Exceeded

Solution code:
import sys
def input(): return sys.stdin.readline().rstrip()
sys.setrecursionlimit(10 ** 7)

H, W = map(int, input().split())
S = [input() for _ in range(H)]
# print(S)
dr = [ 1, 0]
dc = [ 0, 1]
ans = 1001001001

def dfs(r,c,cnt,flg):
    """
    r, c
    cnt: 連続黒の回数
    flg: 1: 現在白（黒に来たらcnt+1）, 0: 現在黒
    """
    global ans
    if S[r][c] == '#':
        if flg:
            cnt += 1
            black_flg = 0
    else:
        flg = 1

    if r==H-1 and c ==W-1:
        ans = min(ans, cnt)
        return

    for dir in range(2):
        nr = r + dr[dir]
        nc = c + dc[dir]
        if nr >= H or nc >= W: continue
        dfs(nr, nc, cnt, flg)
    return

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

Submission status: Time Limit Exceeded

Solution code:
allPaths = []
cnt=[]
def findPaths(maze, m, n):
    path = [0 for d in range(m + n - 1)]
    findPathsUtil(maze, m, n, 0, 0, path, 0)
def findPathsUtil(maze, m, n, i, j, path, indx):
    global allPaths
    if i == m - 1:
        for k in range(j, n):
            path[indx + k - j] = maze[i][k]
        cnt.append(path.count('#'))
        allPaths.append(path)
        return cnt
    if j == n - 1:
        for k in range(i, m):
            path[indx + k - i] = maze[k][j]
        cnt.append(path.count('#'))
        allPaths.append(path)
        return cnt
    path[indx] = maze[i][j]
    findPathsUtil(maze, m, n, i + 1, j, path, indx + 1)
    findPathsUtil(maze, m, n, i, j + 1, path, indx + 1)

n,m=map(int,input().split())
maze=[]
for i in range(n):
    s=input()
    l=[]
    for i in s:
        l.append(i)
    maze.append(l)

findPaths(maze, n, m)
print(min(cnt))

Submission status: Time Limit Exceeded

Solution code:
h,w=map(int,input().split())
s=[list(input()) for _ in range(h)]
q=[(0,0)]
g=[[1000]*w for  _ in range(h)]
g[0][0]=0
if s[0][0]=="#":
    g[0][0]=1
from collections import deque
while q:
    qq=deque([])
    for x,y in q:
        for dx,dy in ((1,0),(0,1)):
            if not(0 <= x+dx < w) or not(0 <= y+dy < h):
                continue
            elif s[y+dy][x+dx] == '#':
                g[y+dy][x+dx]=min(g[y][x]+1,g[y+dy][x+dx])
            else:
                g[y+dy][x+dx]=min(g[y][x],g[y+dy][x+dx])
            qq.append((x+dx,y+dy))
    q=qq

print(g[-1][-1])

Submission status: Time Limit Exceeded

Solution code:
def main():


    from collections import deque


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

    q = deque()

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

    while(q):
        f = q.popleft()
        x, y, c = f[0], f[1], f[2]
        if (x,y) == (w-1,h-1):
            print(c)
            break

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

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


if __name__=='__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
import sys
from collections import deque
input = sys.stdin.readline

STEPS = [
    (0, 1),
    (1, 0)
]
BLACK = '#'
WHITE = '.'
CHECKED = 't'

def main():
    H, W = map(int, input().split())
    board = [list(input().strip()) for _ in range(H)]

    ans = float('INF')

    if board[0][0] == WHITE:
        que = deque([[0, 0, WHITE, 0]])
    else:
        que = deque([[0, 0, BLACK, 1]])


    while que:
        y, x, color, rev = que.popleft()

        for (i,j) in STEPS:
            ny, nx = y + i, x + j
            if ny >= H or nx >= W:
                continue

            n_rev = rev
            target = board[ny][nx]

            if color == WHITE and target == BLACK:
                n_rev += 1

            if ny == H -1 and nx == W - 1:
                ans = min(ans, n_rev)

            que.append([ny, nx, target, n_rev])

    print(ans)


if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
import heapq
h, w = map(int, input().split())
c = [input() for _ in range(h)]
 
d=[[100000]*w for _ in range(h)]
 
def bfs():
    if c[0][0] == '.':
        que = [(0, (0, 0))]
        heapq.heapify(que)
        d[0][0] = 0
    else:
        que = [(1, (0, 0))]
        heapq.heapify(que)
        d[0][0] = 1
    while len(que):
        _, (qx, qy) = heapq.heappop(que)
        if qx == h-1 and qy == w-1:
            return d[h-1][w-1]
        for dx,dy in [[1,0], [0,1]]:
            px, py = qx+dx, qy+dy
            if 0<=px<h and 0<=py<w:
                d[px][py]=min(d[px][py], d[qx][qy] + (c[px][py]=='#'))
                heapq.heappush(que, (d[px][py], (px , py)))

print(bfs())

Submission status: Time Limit Exceeded

Solution code:
def right(r,c,count):
  if s[r][c] == '#':
    count += 1
  if r == h - 1 and c == w - 1:
    return count
  if r == h - 1:
    return down(r,c+1,count)
  elif c == w - 1:
    return right(r+1,c,count)
  else:
    return min(right(r+1,c,count),down(r,c+1,count))

def down(r,c,count):
  if s[r][c] == '#':
    count += 1
  if r == h - 1 and c == w - 1:
    return count
  if r == h - 1:
    return down(r,c+1,count)
  elif c == w - 1:
    return right(r+1,c,count)
  else:
    return min(right(r+1,c,count),down(r,c+1,count))

h,w = map(int,input().split())
s = ['.' * h] * w
for i in range(h):
  s[i] = input()
  
print(right(0,0,0))

Submission status: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(4100000)
from collections import deque

def main():
    H, W = map(int, input().split())
    S = list(input() for _ in range(H))
    visited = [[float('inf')] * W for _ in range(H)]
    dh = [0,1]
    dw = [1,0]
    if S[0][0] == '#':
        visited[0][0] = 1
        pre = False
    else:
        visited[0][0] = 0
        pre = True
    
    Q = deque([])
    Q.append((0,0,pre))
    while Q:
        h, w, pre = Q.popleft()
        
        if h == H - 1 and w == W - 1:
            break

        for i in range(2):
            nh = h + dh[i]
            nw = w + dw[i]

            if 0 <= nh < H and 0 <= nw < W:
                if S[nh][nw] == '.':
                    visited[nh][nw] = min(visited[nh][nw], visited[h][w])
                    Q.append((nh,nw,True))
                else:
                    if pre:
                        visited[nh][nw] = min(visited[nh][nw], visited[h][w] + 1)
                        Q.append((nh,nw,False))
                    else:
                        visited[nh][nw] = min(visited[nh][nw], visited[h][w])
                        Q.append((nh,nw,False))

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



if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:

def main():


    from collections import deque


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

    q = deque()

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

    while(q):
        f = q.popleft()
        x, y, c = f[0], f[1], f[2]
        if (x,y) == (w-1,h-1):
            print(c)
            break

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

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


if __name__=='__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
import sys
from itertools import permutations


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


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

    S = [list(input()) for _ in range(H)]
    C = [2 * i for i in range(H - 1)] + [2 * j + 1 for j in range(W - 1)]
    check = list(permutations(C))
    answer = float("inf")
    for chk in check:
        if S[0][0] == "#":
            cnt = 1
        else:
            cnt = 0
        now = [0, 0]
        for i in range(H + W - 2):
            if chk[i] % 2 == 0:
                now[0] += 1
            else:
                now[1] += 1
            if now[0] <= H - 1 and now[1] <= W - 1:
                if S[now[0]][now[1]] == "#":
                    cnt += 1
            # print(now)
            # print(cnt)
        if cnt < answer:
            answer = cnt
    print(answer)


main()

Submission status: Time Limit Exceeded

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

from collections import deque
cnts = [[1000] * W for i in range(H)]
q = deque()
q.append((0,0))
cnts[0][0] = 0
str_s = "."
mv = [(1,0),(0,1)]
while len(q) > 0:
    h,w = q.popleft()
    # mark = fields[h][w]
    for dh, dw in mv:
        if h + dh < H and w + dw < W:
            # print("upd",h,w,h+dh,w+dw,H,W)
            if fields[h][w] == fields[h+dh][w+dw]:
                upd = cnts[h][w] 
            else:
                if fields[h][w] == ".":
                    upd = cnts[h][w] + 1
                else:
                    upd = cnts[h][w]
            cnts[h+dh][w+dw] = min(cnts[h+dh][w+dw],upd)
            q.append((h+dh,w+dw))

# print(cnts)

ans = cnts[H-1][W-1]
if fields[0][0] == "#":ans += 1
print(ans)