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:
#!/usr/bin/env python3
import sys
import heapq

def solve(H: int, W: int, s: "List[str]"):
    minScore = 10**16
    def isBlock(x,y):
        return s[y][x] == "#"
    first = isBlock(0,0)
    current = [(0,0,1 if first else 0,first)]
    def addNextIfCan(x,y,prevScore,prevBlock):
        if x >= W or y >= H:
            return
        c = isBlock(x,y)
        if c and not prevBlock:
            current.append((x,y,prevScore+1,c))
        else:
            current.append((x,y,prevScore,c))
    
    while len(current) > 0:
        n = current.pop()
        if n[0] == W - 1 and n[1] == H - 1:
            minScore = min(minScore,n[2])
        addNextIfCan(n[0]+1,n[1],n[2],n[3])
        addNextIfCan(n[0],n[1]+1,n[2],n[3])
    print(minScore)
    return


# Generated by 1.1.6 https://github.com/kyuridenamida/atcoder-tools  (tips: You use the default template now. You can remove this line by using your custom template)
def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    H = int(next(tokens))  # type: int
    W = int(next(tokens))  # type: int
    s = [next(tokens) for _ in range(H)]  # type: "List[str]"
    solve(H, W, s)

if __name__ == '__main__':
    main()

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

    qu.append([0,0,[1 if ss[0][0]=="#" else 0]])
    ans = INF
    while len(qu)!=0:
        x,y,z = qu.popleft()
        if x!=W-1:
            z2 = z+[1 if ss[x+1][y]=="#" else 0]
            qu.append([x+1,y,z2])
        if y!=H-1:
            z2 = z+[1 if ss[x][y+1] == "#" else 0]
            qu.append([x, y+1, z2])
        if x==W-1 and y==H-1:
            buf = 0
            for zidx,az in enumerate(z):
                if az==1 and (zidx==0 or z[zidx-1]==0):
                    buf+=1
            ans = min(ans,buf)
    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:
import sys, re, os
def input(): return sys.stdin.readline().strip()
##幅優先探索
from collections import deque
 
def dfs(H,W,M):
    que = deque()
    if M[0][0] == "#":
        que.append([0,0,1,1])
    else:
        que.append([0,0,0,0])

    d = [[1,0],[0,1]]
    m = 1000000
    
    while que:
        x,y,num_sharp,in_sharp = que.popleft()

        for i,j in d:
            dx = x + i
            dy = y + j
            if 0 <= dx <= W-1 and 0 <= dy <= H-1:
                if M[dx][dy] == "#" and in_sharp:
                    que.append([dx,dy,num_sharp,1])
                elif M[dx][dy] == "#" and not in_sharp:
                    que.append([dx,dy,num_sharp+1,0])
                else:##M[dx][dy] == "."
                    que.append([dx,dy,num_sharp,0])
        if x == W-1 and y == H-1:
            m = min(m,num_sharp)
    return m 
 
 
def main():
    H,W = map(int,input().split())
    M = []
    for i in range(H):
        M.append(input())
    print(dfs(H,W,M))
 
if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
from collections import deque


def bfs(si, sj):
    q = deque()
    used = set()
    if grids[sj][si] == '#':
        q.append([si, sj, 1])
    else:
        q.append([si, sj, 0])

    ans = float('inf')
    while len(q) > 0:
        prv_si, prv_sj, num_b = q.popleft()
        if [prv_si, prv_sj] == [W - 1, H - 1]:
            ans = min(ans, num_b)

        else:
            if prv_si < W - 1:
                if grids[prv_sj][prv_si] == '.' and grids[prv_sj][prv_si + 1] == '#':
                    q.append([prv_si + 1, prv_sj, num_b + 1])
                else:
                    q.append([prv_si + 1, prv_sj, num_b])

            if prv_sj < H - 1:
                if grids[prv_sj][prv_si] == '.' and grids[prv_sj + 1][prv_si] == '#':
                    q.append([prv_si, prv_sj + 1, num_b + 1])
                else:
                    q.append([prv_si, prv_sj + 1, num_b])

    return ans


H, W = map(int, input().split())
grids = [input() for _ in range(H)]
print(bfs(0, 0))

Submission status: Time Limit Exceeded

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

h, w = map(int, input().split())
s = []
for _ in range(h):
    s.append(input().rstrip('\n'))

ans = h + w

def bfs(cur, pre, cnt):
    global ans
    stack = deque([[cur, pre, cnt]])
    while stack:
        cur, pre, cnt = stack.popleft()
        r, c = cur
        col = s[r][c]
        if col != pre:
            cnt += 1
        if r == h-1 and c == w-1:
            ans = min(ans, cnt)
        next = [[r+1, c], [r, c+1]]
        for r2, c2 in next:
            if r2 < h and c2 < w:
                stack.append([[r2, c2], col, cnt])

bfs([0, 0], '.', 0)

print((ans+1)//2)

Submission status: Time Limit Exceeded

Solution code:
import heapq
def A():
    H, W = map(int, input().split())
    maze = []
    for i in range(H):
        maze.append(input())
    if maze[0][0] == '.':
        q = [[0, (0, 0)]]
    else:
        q = [[1, (0, 0)]]
    heapq.heapify(q)
    while q:
        #print(q)
        cost, cur = heapq.heappop(q)
        if cur[0] == H-1 and cur[1] == W-1:
            print(cost)
            return
        for direction in [(0, 1), (1, 0)]:
            new_r, new_c = cur[0]+direction[0], cur[1]+direction[1]
            if new_r >= 0 and new_c >= 0 and new_r < H and new_c < W:
                if maze[new_r][new_c]=='.':
                    heapq.heappush(q, [cost, (new_r, new_c)])
                else:
                    heapq.heappush(q, [cost+1, (new_r, new_c)])

A()

Submission status: Time Limit Exceeded

Solution code:
#template
from collections import Counter
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
li = []
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)
heapq.heapify(li)
print(heapq.heappop(li))

Submission status: Time Limit Exceeded

Solution code:
from collections import deque

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

ans = h + w

def bfs(cur, pre, cnt):
    global ans
    stack = deque([[cur, pre, cnt]])
    while stack:
        cur, pre, cnt = stack.popleft()
        r, c = cur
        col = s[r][c]
        if col != pre:
            cnt += 1
        if r == h-1 and c == w-1:
            ans = min(ans, cnt)
        next = [[r+1, c], [r, c+1]]
        for r2, c2 in next:
            if r2 < h and c2 < w:
                stack.append([[r2, c2], col, cnt])

bfs([0, 0], '.', 0)

print((ans+1)//2)

Submission status: Time Limit Exceeded

Solution code:
h,w = (int(x) for x in input().split())
ab = []
for _ in range(h):
    a = input()
    a = a+'#'
    ab.append(list(a))
ab.append(list('#'*w))
dp = [[100000000000000000 for a in range(w+1)] for b in range(h+1)]
if ab[0][0] == '#':
    dp[0][0] = 1
else:
    dp[0][0] = 0
step = [[0, 0]]
 
while len(step) > 0:
    y, x = step.pop(0)
    
    if h-1<y or w-1 < x:continue
    
    if ab[y+1][x] == '#':
        step.append([y+1, x])
        dp[y+1][x] = min(dp[y][x] + 1, dp[y+1][x])
    else:
        step.append([y+1, x])
        dp[y+1][x] = min(dp[y][x], dp[y+1][x])
    if ab[y][x+1] == '#':
        step.append([y, x+1])
        dp[y][x+1] = min(dp[y][x] + 1, dp[y][x+1])
    else:
        step.append([y, x+1])
        dp[y][x+1] = min(dp[y][x],dp[y][x+1])
 
print(dp[h-1][w-1])

Submission status: Time Limit Exceeded

Solution code:
# -*- coding: utf-8 -*-
import bisect
import heapq
import math
import random
import sys
from collections import Counter, defaultdict, deque
from decimal import ROUND_CEILING, ROUND_HALF_UP, Decimal
from functools import lru_cache, reduce
from itertools import combinations, combinations_with_replacement, product, permutations
from operator import add, mul, sub

sys.setrecursionlimit(100000)
input = sys.stdin.readline
INF = 2**62-1

def read_int():
    return int(input())


def read_int_n():
    return list(map(int, input().split()))


def read_float():
    return float(input())


def read_float_n():
    return list(map(float, input().split()))


def read_str():
    return input().strip()


def read_str_n():
    return list(map(str, input().split()))


def error_print(*args):
    print(*args, file=sys.stderr)


def mt(f):
    import time

    def wrap(*args, **kwargs):
        s = time.time()
        ret = f(*args, **kwargs)
        e = time.time()

        error_print(e - s, 'sec')
        return ret

    return wrap


def warshall_floyd(g):
    d = defaultdict(dict)
    V = list(g.keys())
    for v in g.values():
        V.extend(list(v))
    V = set(V)
    for i in V:
        for j in V:
            if i in g and j in g[i]:
                d[i][j] = g[i][j]
            else:
                d[i][j] = sys.maxsize
    for k in g:
        for i in g:
            for j in g:
                if d[i][j] > d[i][k] + d[k][j]:
                    d[i][j] = d[i][k] + d[k][j]

    return d


@mt
def slv(H, W, S):
    g = defaultdict(dict)
    for i in range(H):
        for j in range(W):
            for x, y in ((0, 1), (1, 0), (0, -1), (-1, 0)):
                if 0 <= i + x < H and 0 <= j+y < W:
                    if S[i][j] == '.' and S[i+x][j+y] == '#':
                        c = 1
                    else:
                        c = 0
                    g[(i, j)][(i+x, j+y)] = c

    d = warshall_floyd(g)
    return d[(0, 0)][(H-1, W-1)] + (1 if S[0][0] == '#' else 0)


def main():
    H, W = read_int_n()
    S = [read_str() for _ in range(H)]
    print(slv(H, W, S))


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
from collections import deque
q = deque()
h,w=map(int,input().split())
global finished 
finished = set()
c=[]
for i in range(h):
    c.append(list(map(str,input())))
q.append([0,0,0])
if c[h-1][w-1]=='#':
    asd=1
else:
    asd=0
c[h-1][w-1]='s'

def check(x,y):
    if 0<=x and x<h:
        if 0<=y and y<w:
            return True
    return False
global ans
ans=1000

def search():
    while (q):
        x,y,count=q.popleft()
        #print(q)
        global ans
        
        if check(x,y)==False  :
            continue

        else:
            if c[x][y]=='#':
                q.append([x,y+1,count+1])
                q.append([x+1,y,count+1])
            else:
                q.append([x,y+1,count])
                q.append([x+1,y,count])
            finished.add((x,y))
            if c[x][y]=="s":
                ans=min(ans,count)
                #print(ans)
search()
print(ans+asd)

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

while q:
    qq=[]
    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:
from collections import deque
import sys
sys.setrecursionlimit(10 ** 9)
# import numpy as np
# 答えの提出の時にi+1とj+1は忘れないように
h, w = map(int, input().split())
maze = [[-1 for i in range(w)] for j in range(h)]

INF = h*w
countBlack = [[INF for i in range(w)] for j in range(h)]

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

sx=0
sy=0
queue = deque()
queue.append((sy,sx))
countBlack[sy][sx] = int(maze[0][0]== '#')

while queue:
    y, x = queue.popleft()
    for i,j in [(1,0),(0,1)]:
        ny, nx = y+i, x+j
        if 0 <= nx < w and 0 <= ny < h:
            queue.append((ny, nx))
            if maze[ny][nx] == '#':
                tmp = countBlack[y][x] + 1
                countBlack[ny][nx] = min(countBlack[ny][nx], tmp)
            else:
                countBlack[ny][nx] = min(countBlack[ny][nx], countBlack[y][x])


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

Submission status: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(4100000)

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
    
    def dfs(h,w,visited,pre):
        if h == H - 1 and w == W - 1:
            return

        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])
                    dfs(nh,nw,visited,True)
                else:
                    if pre:
                        visited[nh][nw] = min(visited[nh][nw], visited[h][w] + 1)
                        dfs(nh,nw,visited,False)
                    else:
                        visited[nh][nw] = min(visited[nh][nw], visited[h][w])
                        dfs(nh,nw,visited,False)

    dfs(0,0,visited,pre)
    print(visited[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())

g = []
for _ in range(h):
    tmp = list(input())
    g.append(tmp)

dp = [[1000000 for _ in range(w)] for __ in range(h)]

dp[0][0] = 0
q = deque([(0, 0)])

while q:
    x, y = q.popleft()
    if x+1 < h:
        if g[x+1][y] != g[x][y]:
            dp[x+1][y] = min(dp[x+1][y], dp[x][y]+1)
        else:
            dp[x+1][y] = min(dp[x+1][y], dp[x][y])
        q.append((x+1, y))
    if y+1 < w:
        if g[x][y+1] != g[x][y]:
            dp[x][y+1] = min(dp[x][y+1], dp[x][y]+1)
        else:
            dp[x][y+1] = min(dp[x][y+1], dp[x][y])
        q.append((x, y+1))

if g[0][0] == '.' and g[h-1][w-1] == '.':
    print(dp[h-1][w-1]//2)
elif g[0][0] != g[h-1][w-1]:
    print((dp[h-1][w-1]+1)//2)
else:
    print(1 + (dp[h-1][w-1]//2))

Submission status: Time Limit Exceeded

Solution code:
H, W = map(int, input().split())
m = [list(input()) for _ in range(H)]
ans = float('inf')

def dfs(h, w, c):
  global ans
  cnt = c
  
  if h >= H or h < 0 or w >= W or w < 0:
    return
  
  if m[h][w] == "#":
    cnt += 1
  
  if h == H - 1 and w == W - 1:
    ans = min(ans, cnt)
    return
  
  dfs(h + 1, w, cnt)
  dfs(h, w + 1, cnt)

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

Submission status: Time Limit Exceeded

Solution code:
from collections import deque

H, W = map(int,input().split())
S = [input() for i in range(H)]
ans = 10**9

if S[0][0] == "#":
    q = deque([(0,0,1, "#")])
else:
    q = deque([(0,0,0, None)])
while q:
    i, j, cnt, prev = q.popleft()
    if i == H - 1 and j == W - 1:
        ans = min(ans, cnt)
    for ni, nj in [(i+1, j), (i, j+1)]:
        if 0 <= ni < H and 0 <= nj < W:
            if S[ni][nj] == "#":
                if prev == "#":
                    q.append((ni,nj, cnt, "#"))
                else:
                    q.append((ni,nj, cnt+1, "#"))
            else:
                q.append((ni,nj, cnt, "."))
print(ans)

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()
    step = []
    if a[0][0]=='.':
        q.appendleft((0,0,0))
    else:
        q.appendleft((0,0,1))

    while(q):
        f = q.pop()
        x, y, c = f[0], f[1], f[2]
        if (x,y) == (w-1,h-1):
            step.append(c)

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

        if y + 1 <= h - 1:
            n = a[x][y+1] == '#'
            q.appendleft((x , y+1, c + n))
    ans = min(step)
    print(ans)


if __name__=='__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
r, c = map(int, input().split())
board = []
for _ in range(r):
    line = input()
    row = []
    for i in range(c):
        row.append(line[i])
    board.append(row)


def search(board, i, j, r, c, count):
    if i == (r - 1) and j == (c - 1):
        if board[i][j] == '.':
            return count
        else:
            return count + 1

    new_count = []
    if i < r - 1:
        if board[i + 1][j] == '.':
            new_count.append(search(board, i + 1, j, r, c, count))
        else:
            new_count.append(search(board, i + 1, j, r, c, count + 1))

    if j < c - 1:
        if board[i][j + 1] == '.':
            new_count.append(search(board, i, j + 1, r, c, count))
        else:
            new_count.append(search(board, i, j + 1, r, c, count + 1))

    return min(new_count)


print(search(board, 0, 0, r, c, 0))

Submission status: Time Limit Exceeded

Solution code:
from collections import deque


def bfs(si, sj):
    q = deque()
    used = set()
    if grids[sj][si] == '#':
        q.append([si, sj, 1])
    else:
        q.append([si, sj, 0])
    used.add(tuple([si, sj]))

    ans = float('inf')
    while len(q) > 0:
        prv_si, prv_sj, num_b = q.popleft()
        if [prv_si, prv_sj] == [W - 1, H - 1]:
            ans = min(ans, num_b)

        else:
            if prv_si < W - 1:
                if grids[prv_sj][prv_si] == '.' and grids[prv_sj][prv_si + 1] == '#':
                    q.append([prv_si + 1, prv_sj, num_b + 1])
                else:
                    q.append([prv_si + 1, prv_sj, num_b])
                used.add(tuple([prv_si + 1, prv_sj]))

            if prv_sj < H - 1:
                if grids[prv_sj][prv_si] == '.' and grids[prv_sj + 1][prv_si] == '#':
                    q.append([prv_si, prv_sj + 1, num_b + 1])
                else:
                    q.append([prv_si, prv_sj + 1, num_b])
                used.add(tuple([prv_si, prv_sj + 1]))
    return ans


H, W = map(int, input().split())
grids = [input() for _ in range(H)]
print(bfs(0, 0))

Submission status: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(10 ** 9 + 7)
ans = 10 ** 9 + 7
def solve(x, y, cnt):
    global ans
    if x == w - 1 and y == h - 1:
        if field[y][x] == "#":
            cnt += 1
        ans = min(ans, cnt)
        return

    if 0 <= x < w and 0 <= y < h:
        if field[y][x] == "#":
            solve(x + 1, y, cnt + 1)
            solve(x, y + 1, cnt + 1)
        else:
            solve(x + 1, y, cnt)
            solve(x, y + 1, cnt)
    else:
        return

h, w = map(int, input().split())
field = []

for i in range(h):
    field.append(list(input()))

solve(0, 0, 0)
print(ans)

Submission status: Time Limit Exceeded

Solution code:
import sys, re
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, radians
from itertools import accumulate, permutations, combinations, product
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
from bisect import bisect, bisect_left
from fractions import gcd
from heapq import heappush, heappop
from functools import reduce
def input(): return sys.stdin.readline().strip()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
def ZIP(n): return zip(*(MAP() for _ in range(n)))
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
mod = 10 ** 9 + 7

def main():
    H, W = MAP()
    dx = [1, 0]
    dy = [0, 1]
    s = [input() for _ in range(H)]

    start = (0, 0)

    q = deque()
    q.append(start)

    cost = [[INF]*W for _ in range(H)]
    if s[0][0] == "#":
        cost[0][0] = 1
    else:
        cost[0][0] = 0
    while q:
        i, j = q.popleft()
        for k in range(2):
            y = i + dy[k]
            x = j + dx[k]
            if y < 0 or y > H-1 or x < 0 or x > W-1:
                continue
            if s[i][j] == "." and s[y][x] == "#":
                cost[y][x] = min(cost[y][x], cost[i][j] + 1)
                q.append((y, x))
            elif s[i][j] == "#" and s[y][x] == "#":
                cost[y][x] = min(cost[y][x], cost[i][j])
                q.append((y, x))
            elif s[i][j] == "." and s[y][x] == ".":
                cost[y][x] = min(cost[y][x], cost[i][j])
                q.append((y, x))
            else:  # # -> .
                cost[y][x] = min(cost[y][x], cost[i][j])
                q.append((y, x))
    # print(cost)
    print(cost[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)]

def next_positions(current_position):
    output = []
    for udrl in [[0,1],[1,0]]:
        y = current_position[0]+udrl[0]
        x = current_position[1]+udrl[1]
        if 0 <= y <= H-1 and 0 <= x <= W-1:
            output.append([y,x])
    return output

d = deque([[0,0]])
distance = [[float("inf")]*W for _ in range(H)]
if s[0][0] == ".":
    distance[0][0] = 0
else:
    distance[0][0] = 1

while d:
    current_position = d.popleft()
    for q in next_positions(current_position):
        if s[q[0]][q[1]] == ".":
            distance[q[0]][q[1]] = min(distance[q[0]][q[1]], distance[current_position[0]][current_position[1]])
        else:
            distance[q[0]][q[1]] = min(distance[q[0]][q[1]], distance[current_position[0]][current_position[1]] + 1)
        d.append(q)

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

Submission status: Time Limit Exceeded

Solution code:
##幅優先探索
from collections import deque
 
def dfs(H,W,M):
    que = deque()
    if M[0][0] == "#":
        que.append([0,0,1,1])
    else:
        que.append([0,0,0,0])

    d = [[1,0],[0,1]]
    ans = []
    
    while que:
        x,y,num_sharp,in_sharp = que.popleft()

        for i,j in d:
            dx = x + i
            dy = y + j
            if 0 <= dx <= W-1 and 0 <= dy <= H-1:
                if M[dx][dy] == "#" and in_sharp:
                    que.append([dx,dy,num_sharp,1])
                elif M[dx][dy] == "#" and not in_sharp:
                    que.append([dx,dy,num_sharp+1,0])
                else:##M[dx][dy] == "."
                    que.append([dx,dy,num_sharp,0])
        if x == W-1 and y == H-1:
            ans.append(num_sharp)
    return min(ans)
 
 
 
def main():
    H,W = map(int,input().split())
    M = []
    for i in range(H):
        M.append(input())
    print(dfs(H,W,M))
 
if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
h,w= map(int,input().split(' '))
min= h*w

grid= [[0 for i in range(w)] for j in range(h)]

for i in range(h):
    row=input()
    for j in range(len(row)):
        if row[j]=='#':
            grid[i][j]=1

def go(i,j,count):
    global h,w,min,grid
    if i>=h or j>=w:
        return
    if count>min:
        return
    if i==h-1 and j==w-1:
        if grid[i][j]==1:
            count+=1
        min=count
        return
    if grid[i][j]==1:
        count+=1
        go(i+1,j,count)
        go(i,j+1,count)
    else:
        go(i + 1, j, count)
        go(i, j + 1, count)

go(0,0,0)
print(min)

Submission status: Time Limit Exceeded

Solution code:
import collections
h, w = [int(_) for _ in input().split()]
S = [list(input()) for _ in range(h)]
B = [[-1] * w for _ in range(h)]
B[0][0] = 0 if S[0][0] == '.' else 1
cand = collections.deque([(0, 1), (1, 0)])
while cand:
    x, y = cand.popleft()
    s = 999
    if y:
        s = B[x][y - 1] + (S[x][y] == '#' != S[x][y - 1])
    if x:
        s = min(s, B[x - 1][y] + (S[x][y] == '#' != S[x - 1][y]))
    B[x][y] = s
    if x + 1 < h:
        cand += [(x + 1, y)]
    if y + 1 < w:
        cand += [(x, y + 1)]
print(B[-1][-1])

Submission status: Time Limit Exceeded

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

cost = [[10000]*W for _ in range(H)]

def dfs(i, j, c):
  if i >= H or j >= W:
    return
  else:
    cost[i][j] = min(cost[i][j], c+1 if S[i][j]=='#' else c)
    dfs(i+1, j, cost[i][j])
    dfs(i, j+1, cost[i][j])

dfs(0, 0, 0)
print(cost[-1][-1])

Submission status: Time Limit Exceeded

Solution code:
h,w=map(int,input().split())
D=[list(input()) for i in range(h)]
# D[i][j]はD[h-1][w-1]まで
#dfs
stack=[]
stack.append((0,0,0))
da=[0,1]
db=[1,0]
infi=10**10
ans=infi
while stack:
    a,b, cnt=stack.pop()
    if D[a][b]=='#':
        cnt+=1
    if a+b==(h+w-2):
        ans=min(ans,cnt)
    for i in range(2):
        p=a+da[i]
        q=b+db[i]
        if 0<=p and p<=h-1 and 0<=q and q<=w-1:
            stack.append((p,q,cnt))
print(ans)

Submission status: Time Limit Exceeded

Solution code:
#template
from collections import Counter
def inputlist(): return [int(i) for i in input().split()]
#template
#issueから始める
H,W = inputlist()
maze = ['0']*H
for i in range(H):
    maze[i] = list(input())
li = []
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.sort()
print(li[0])

Submission status: Time Limit Exceeded

Solution code:
#!python3

from heapq import heappush, heappop
iim = lambda: map(int, input().rstrip().split())

def resolve():
    H, W = iim()
    S = [input() for i in range(H)]
    H1, W1 = H-1, W-1

    dq = []
    heappush(dq, (0, 0, 0))

    while dq:
        cost, x, y = heappop(dq)

        if S[y][x] == "#":
            cost += 1

        if x == W1 and y == H1:
            print(cost)
            return

        if x < W1:
            heappush(dq, (cost, x+1, y))
        if y < H1:
            heappush(dq, (cost, x, y+1))

if __name__ == "__main__":
    resolve()

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

    q = deque()
    if s[0][0] == '#':
        q.append((0, 0, 1))
    else:
        q.append((0, 0, 0))

    while q:
        r, c, cnt = q.popleft()
        if r == H - 1 and c == W - 1:
            print(cnt)
            return
        if r < H - 1:
            if s[r + 1][c] == '#':
                q.append((r + 1, c, cnt + 1))
            else:
                q.appendleft((r + 1, c, cnt))
        if c < W - 1:
            if s[r][c + 1] == '#':
                q.append((r, c + 1, cnt + 1))
            else:
                q.appendleft((r, c + 1, cnt))


if __name__ == '__main__':
    main()

# import sys
#
# input = sys.stdin.readline
# sys.setrecursionlimit(10 ** 7)
# rstrip()
# int(input())
# map(int, input().split())