Problem:


Score : 400 points

Problem Statement

Consider a grid with H rows and W columns of squares. Let (r, c) denote the square at the r-th row from the top and the c-th column from the left.
Each square is painted black or white.

The grid is said to be good if and only if the following condition is satisfied:

From (1, 1), we can reach (H, W) by moving one square right or down repeatedly, while always being on a white square.

Note that (1, 1) and (H, W) must be white if the grid is good.

Your task is to make the grid good by repeating the operation below. Find the minimum number of operations needed to complete the task. It can be proved that you can always complete the task in a finite number of operations.

Choose four integers r_0, c_0, r_1, c_1(1 \leq r_0 \leq r_1 \leq H, 1 \leq c_0 \leq c_1 \leq W). For each pair r, c (r_0 \leq r \leq r_1, c_0 \leq c \leq c_1), invert the color of (r, c) - that is, from white to black and vice versa.

Constraints

2 \leq H, W \leq 100

Input

Input is given from Standard Input in the following format:

H W
s_{11} s_{12} \cdots s_{1W}
s_{21} s_{22} \cdots s_{2W}
 \vdots
s_{H1} s_{H2} \cdots s_{HW}

Here s_{rc} represents the color of (r, c) - # stands for black, and . stands for white.

Output

Print the minimum number of operations needed.

Sample Input 1

3 3
.##
.#.
##.

Sample Output 1

1

Do the operation with (r_0, c_0, r_1, c_1) = (2, 2, 2, 2) to change just the color of (2, 2), and we are done.

Sample Input 2

2 2
#.
.#

Sample Output 2

2

Sample Input 3

4 4
..##
#...
###.
###.

Sample Output 3

0

No operation may be needed.

Sample Input 4

5 5
.#.#.
#.#.#
.#.#.
#.#.#
.#.#.

Sample Output 4

4



Sample input:
3 3
.##
.#.
##.


Sample output:
1

Submission status: Time Limit Exceeded

Solution code:
import sys, re, os
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, radians, acos, atan, asin, log, log10
from itertools import permutations, combinations, product, accumulate
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
from fractions import gcd
def debug(*args):
    if debugmode:
        print(*args)
def input(): return sys.stdin.readline().strip()
def STR(): return input()
def INT(): return int(input())
def FLOAT(): return float(input())
def MAP(): return map(int, input().split())
def S_MAP(): return map(str, input().split())
def LIST(): return list(map(int, input().split()))
def S_LIST(): return list(map(str, input().split()))
def lcm(a, b): return a * b // gcd(a, b)
sys.setrecursionlimit(10 ** 9)
inf = sys.maxsize
mod = 10 ** 9 + 7
dx = [0, 1, 0, -1, 1, -1, -1, 1]
dy = [1, 0, -1, 0, 1, -1, 1, -1]
debugmode = True

def func(y, x, pres):
    if y == h - 1 and x == w - 1:
        return pres
    res = inf
    for i in range(2):
        if x + dx[i] < w and y + dy[i] < h:
            res = min(res, func(y + dy[i], x + dx[i], pres if s[y + dy[i]][x + dx[i]] == '.' else pres + 1))
    return res

h, w = MAP()
s = [list(STR()) for _ in range(h)]
tmp = 1 if s[0][0] == '#' else 0
ans = func(0, 0, tmp)
print(ans)

Submission status: Time Limit Exceeded

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

def dfs(h, w, count=0):
    if s[h][w]=='#':
        count+=1
    if h==H-1 and w==W-1:
        return count
    else:
        ans = float('inf')
        if w+1<W:
            ans = min(ans, dfs(h, w+1, count=count))
            if ans == 0:
                return 0
        if h+1<H:
            ans = min(ans, dfs(h+1, w, count=count))
            if ans == 0:
                return 0
        return ans
print(dfs(0,0,0))

Submission status: Time Limit Exceeded

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

def dfs(h, w, count=0):
    if s[h][w]=='#':
        count+=1
    if h==H-1 and w==W-1:
        return count
    else:
        ans = float('inf')
        if w+1<W:
            ans = min(ans, dfs(h, w+1, count=count))
        if h+1<H:
            ans = min(ans, dfs(h+1, w, count=count))
        return ans
print(dfs(0,0,0))

Submission status: Time Limit Exceeded

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

H,W = imn()

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

xd = [1, 0]
yd = [0, 1]
que = deque([(0, 0)])
while len(que) > 0:
    point = que.popleft()
    x = point[0]
    y = point[1]
    if x == W-1 and y == H-1: continue
    for i in range(2):
        nx = x + xd[i]
        ny = y + yd[i]
        if nx >= W or ny >= H: continue
        if s[ny][nx] == '#': 
            d[ny][nx] = min(d[ny][nx], d[y][x]+1)
        else:
            d[ny][nx] = min(d[ny][nx], d[y][x])
        que.append((nx, ny))
print(d[H-1][W-1])

Submission status: Time Limit Exceeded

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

H,W = imn()

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

xd = [1, 0]
yd = [0, 1]
que = deque([(0, 0)])
while len(que) > 0:
    point = que.popleft()
    x = point[0]
    y = point[1]
    if x == W-1 and y == H-1: continue
    for i in range(2):
        nx = x + xd[i]
        ny = y + yd[i]
        if nx >= W or ny >= H: continue
        if s[ny][nx] == '#': 
            d[ny][nx] = min(d[ny][nx], d[y][x]+1)
        else:
            d[ny][nx] = min(d[ny][nx], d[y][x])
        que.append((nx, ny))
print(d[H-1][W-1])

Submission status: Time Limit Exceeded

Solution code:
def solve():
    H, W = map(int, input().split())
    l = [list(input()) for _ in range(H)]
    q = [(0, 0)]
    sc = [[H*W]*W for _ in range(H)]
    sc[0][0] = 0 if l[0][0]=="." else 1

    while q:
        y, x = q.pop()
        for y1, x1 in [(y+1, x), (y, x+1)]:
            if not (0<=x1<W and 0<=y1<H):continue
            if l[y][x]=="#":
                sc[y1][x1] = min(sc[y1][x1], sc[y][x])
                q.append((y1, x1))
            else:
                sc[y1][x1] = min(sc[y1][x1], sc[y][x]+1 if l[y1][x1]=="#" else sc[y][x])
                q.append((y1, x1))

    print(sc[-1][-1])


if __name__ == "__main__":
    solve()

Submission status: Time Limit Exceeded

Solution code:
from itertools import permutations
H, W = map(int, input().split())
l = [input() for _ in range(H)]

q = [(0, 0, l[0][0], 0 if l[0][0]=="." else 1)]
ans = H * W
while q:
    y, x, c, score = q.pop()
    if y==H-1 and x==W-1:
        ans = min(ans, score)
    for y1, x1 in [(y+1, x), (y, x+1)]:
        if not (0<=x1<W and 0<=y1<H):continue
        if c=="#":
            q.append((y1, x1, l[y1][x1], score))
        else:
            q.append((y1, x1, l[y1][x1], score+1 if l[y1][x1]=="#" else score))

print(ans)

Submission status: Time Limit Exceeded

Solution code:
from collections import deque

h,w = map(int,input().split())
c = []
c.append(['×' for _ in range(w+2)])
for _ in range(h):
	c.append(list('×'+input()+'×'))
c.append(['×' for _ in range(w+2)])
ans = [[101 for _ in range(w+2)]for _ in range(h+2)]
if c[1][1] == '.':
	ans[1][1] = 0
else:
	ans[1][1] = 1

q = deque()

def bfs(x,y):
	global q
	global c
	q.append([x,y])

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

		if [x,y] == [w,h]:
			return ans[h][w]
		if c[y][x+1] == '.':
			q.append([x+1,y])
			ans[y][x+1] = min(ans[y][x+1],ans[y][x])
		elif c[y][x+1] == '#':
			q.append([x+1,y])
			ans[y][x+1] = min(ans[y][x+1],ans[y][x]+1)
		if c[y+1][x] == '.':
			q.append([x,y+1])
			ans[y+1][x] = min(ans[y+1][x],ans[y][x])
		elif c[y+1][x] == '#':
			q.append([x,y+1])
			ans[y+1][x] = min(ans[y+1][x],ans[y][x]+1)


print(bfs(1,1))

Submission status: Time Limit Exceeded

Solution code:
from collections import deque

h,w = map(int,input().split())
c = []
c.append(['×' for _ in range(w+2)])
for _ in range(h):
	c.append(list('×'+input()+'×'))
c.append(['×' for _ in range(w+2)])
ans = [[101 for _ in range(w+2)]for _ in range(h+2)]
if c[1][1] == '.':
	ans[1][1] = 0
else:
	ans[1][1] = 1

q = deque()

def bfs(x,y):
	global q
	global c
	q.append([x,y])

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

		if [x,y] == [w,h]:
			return ans[h][w]
		if c[y][x+1] == '.':
			q.append([x+1,y])
			#c[y][x+1] = '×'
			if ans[y][x+1] == 101:
				ans[y][x+1] = ans[y][x]
			else:
				ans[y][x+1] = min(ans[y][x+1],ans[y][x])
		elif c[y][x+1] == '#':
			q.append([x+1,y])
			#c[y][x+1] = '×'
			if ans[y][x+1] == 101:
				ans[y][x+1] = ans[y][x] + 1
			else:
				ans[y][x+1] = min(ans[y][x+1],ans[y][x]+1)
		if c[y+1][x] == '.':
			q.append([x,y+1])
			#c[y+1][x] = '×'
			if ans[y+1][x] == 101:
				ans[y+1][x] = ans[y][x]
			else:
				ans[y+1][x] = min(ans[y+1][x],ans[y][x])
		elif c[y+1][x] == '#':
			q.append([x,y+1])
			#c[y+1][x] = '×'
			if ans[y+1][x] == 101:
				ans[y+1][x] = ans[y][x] + 1
			else:
				ans[y+1][x] = min(ans[y+1][x],ans[y][x]+1)


print(bfs(1,1))

Submission status: Time Limit Exceeded

Solution code:
import collections

h,w=map(int,input().split())
board=[list(input()) for _ in range(h)]
q=collections.deque()
if board[0][0]=='#':
  q.append((0,0,1,1))
else:
  q.append((0,0,0,0))
ans=10**18
while len(q)!=0:
  x,y,cnt,flag=q.popleft()
  if x==w-1 and y==h-1:
    ans=min(ans,cnt)
  else:
    if x!=w-1:
      if flag==0:
        if board[y][x+1]=='#':
          q.append((x+1,y,cnt+1,1))
        else:
          q.append((x+1,y,cnt,0))
      else:
        if board[y][x+1]=='#':
          q.append((x+1,y,cnt,1))
        else:
          q.append((x+1,y,cnt,0))
    if y!=h-1:
      if flag==0:
        if board[y+1][x]=='#':
          q.append((x,y+1,cnt+1,1))
        else:
          q.append((x,y+1,cnt,0))
      else:
        if board[y+1][x]=='#':
          q.append((x,y+1,cnt,1))
        else:
          q.append((x,y+1,cnt,0))
print(ans)

Submission status: Time Limit Exceeded

Solution code:
# coding: utf-8
import itertools
H, W = list(map(int, input().split()))
S = []
for _ in range(H):
    S.append(list(input()))

_w = list(range(H+W-2))

min_change = H * W
paths = list(itertools.combinations(_w,W-1))
for path in paths:
    state = [0, 0]
    pathway = [0] * (H+W-2)
    change = 0
    for i in path:
        pathway[i] = 1
    # init Flag
    black_flag = True if S[0][0] == '#' else False
    
    for go in pathway:
        state[go] += 1
        if S[state[0]][state[1]] == '#':
            if state == [H-1, W-1]:
                change += 1
                break
            if black_flag:
                continue
            else:
                black_flag = True
        else:
            if black_flag:
                change += 1
                black_flag = False
            else:
                continue
    if min_change > change:
        min_change = change

print(min_change)

Submission status: Time Limit Exceeded

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

_w = list(range(H+W-2))

min_change = H * W

for path in itertools.combinations(_w,W-1):
    state = [0, 0]
    pathway = [0] * (H+W-2)
    path = list(path)
    change = 0
    for i in path:
        pathway[i] = 1
    # init Flag
    black_flag = True if S[0][0] == '#' else False
    
    for go in pathway:
        state[go] += 1
        if S[state[0]][state[1]] == '#':
            if state == [H-1, W-1]:
                change += 1
                break
            if black_flag:
                continue
            else:
                black_flag = True
        else:
            if black_flag:
                change += 1
            else:
                continue
    if min_change > change:
        min_change = change
print(min_change)

Submission status: Time Limit Exceeded

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

_w = list(range(H+W-2))

changes = []
for path in itertools.combinations(_w,W-1):
    state = [0, 0]
    pathway = [0] * (H+W-2)
    path = list(path)
    change = 0
    for i in path:
        pathway[i] = 1
    # init Flag
    black_flag = True if S[0][0] == '#' else False
    
    for go in pathway:
        state[go] += 1
        if S[state[0]][state[1]] == '#':
            if state == [H-1, W-1]:
                change += 1
                break
            if black_flag:
                continue
            else:
                black_flag = True
        else:
            if black_flag:
                change += 1
            else:
                continue
    changes.append(change)
print(min(changes))
#print(changes)

Submission status: Time Limit Exceeded

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

import sys
from collections import deque

def main():
    input = sys.stdin.readline
    H,W = map(int,input().split())
    Gd = [list(input()) for _ in range(H)]
    INF = H*W
    direc = [[1,0],[0,1]]
    def dfs(start):
        Dis = [[INF]*W for _ in range(H)]
        Dis[start[0]][start[1]]= (Gd[start[0]][start[1]] == '#')
        q = deque([])   # スタック
        q.append(start)
        while len(q)!=0:
            h,w = q.popleft()   # スタック取りだし（先頭）
            for d in direc:
                hs, ws = h + d[0], w + d[1]
                if not (0<=hs<H and 0<=ws<W):
                    continue
                else:
                    q.append([hs,ws])
                    Dis[hs][ws] = min(Dis[hs][ws], Dis[h][w] + (Gd[hs][ws]=='#'))
        print(Dis[H-1][W-1])
    dfs([0, 0])

if __name__=='__main__':
    main()

Submission status: Time Limit Exceeded

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

inf = float('inf')

from collections import deque
dx = [0, 1]
dy = [1, 0]

q = deque()
d = [[inf for _ in range(W)] for _ in range(H)]
if S[0][0] == '#':
    d[0][0] = 1
    q.append([0, 0, 1])
else:
    d[0][0] = 0
    q.append([0, 0, 0])
while q:
    p = q.popleft()
    if p == [H - 1, W - 1]:
        break
    for i in range(2):
        nx = p[1] + dx[i]
        ny = p[0] + dy[i]
        if nx >= 0 and nx < W and ny >= 0 and ny < H:
            if S[ny][nx] == '#':
                d[ny][nx] = min(d[ny][nx], p[2] + 1)
                q.append([ny, nx, p[2] + 1])
            else:
                d[ny][nx] = min(d[ny][nx], p[2])
                q.append([ny, nx, p[2]])

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

Submission status: Time Limit Exceeded

Solution code:
from collections import deque

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

    def bfs(x,y,G):
        prepare = 1 if A[y][x] == '#' else 0
        q = deque([(x, y, prepare)])
        MOVE = [(1,0), (0,1)]
        while q:
            z = q.popleft()
            
            for (a, b) in MOVE:
                w, h, c = z
                w_n, h_n = w+a, h+b

                if w_n >= W or h_n >= H:
                    continue
                if A[h_n][w_n] == '#':
                    c += 1
                
                d[h_n][w_n] = min(d[h_n][w_n], c)
                q.append((w_n, h_n, c))

    bfs(0, 0, A)
    return d[H-1][W-1]

print(solve())

Submission status: Time Limit Exceeded

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

inf = float('inf')

from collections import deque
dx = [0, 1]
dy = [1, 0]

def bfs():
    q = deque()
    d = [[inf for _ in range(W)] for _ in range(H)]
    q.append([0, 0])
    if S[0][0] == '#':
        d[0][0] = 1
    else:
        d[0][0] = 0
    while q:
        p = q.popleft()
        if p == [H - 1, W - 1]:
            break
        for i in range(2):
            nx = p[1] + dx[i]
            ny = p[0] + dy[i]
            if nx >= 0 and nx < W and ny >= 0 and ny < H:
                q.append([ny, nx])
                if 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]])
    # print(d)
    return d[H - 1][W - 1]
print(bfs())

Submission status: Time Limit Exceeded

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

inf = float('inf')

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

def bfs():
    q = queue.Queue()
    d = [[inf for _ in range(W)] for _ in range(H)]
    q.put([0, 0])
    if S[0][0] == '#':
        d[0][0] = 1
    else:
        d[0][0] = 0
    while not q.empty():
        p = q.get()
        if p == [H - 1, W - 1]:
            break
        for i in range(2):
            nx = p[1] + dx[i]
            ny = p[0] + dy[i]
            if nx >= 0 and nx < W and ny >= 0 and ny < H:
                q.put([ny, nx])
                if 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]])
    # print(d)
    return d[H - 1][W - 1]
print(bfs())

Submission status: Time Limit Exceeded

Solution code:
H, W = list(map(int, input().split(" ")))
s_list = []
ans_list = []
for i in range(H):
    s = input()
    temp_list = []
    for temp in s:
        if temp == "#":
            temp_list.append(1)
        else:
            temp_list.append(0)
    s_list.append(temp_list)


def a(now_x, now_y, black, black_count, sum_count):
    global s_list, ans_list
    if now_x == W-1 and now_y == H-1:
        if black_count > 0:
            sum_count += black_count
        elif s_list[now_y][now_x] == 1:
            sum_count += 1
        ans_list.append(sum_count)
        return
    if s_list[now_y][now_x] == 1:
        black = True
        if now_x < W-1:
            a(now_x+1, now_y, black, black_count+1, sum_count)
        if now_y < H-1:
            a(now_x, now_y+1, black, black_count+1, sum_count)
    else:
        if black:
            sum_count += black_count
        black = False
        black_count = 0
        if now_x < W-1:
            a(now_x+1, now_y, black, black_count, sum_count)
        if now_y < H-1:
            a(now_x, now_y+1, black, black_count, sum_count)


a(0, 0, False, 0, 0)
print(min(ans_list))

Submission status: Time Limit Exceeded

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

que = deque()
alr = [[float('inf') for i in range(W)] for j in range(H)]
if s[0][0] == '.':
    alr[0][0] = 0
else:
    alr[0][0] = 1
que.append((0,0))
while que:
    h,w = que.popleft()
    if h < H-1:
        que.append((h+1,w))
        if s[h+1][w] == '.':
            alr[h+1][w] = min(alr[h][w],alr[h+1][w])
        else:
            alr[h+1][w] = min(alr[h][w] + 1,alr[h+1][w])
    if w < W-1:
        que.append((h,w+1))
        if s[h][w+1] == '.':
            alr[h][w+1] = min(alr[h][w],alr[h][w+1])
        else:
            alr[h][w+1] = min(alr[h][w] + 1,alr[h][w+1])
print(alr[-1][-1])

Submission status: Time Limit Exceeded

Solution code:
import sys
import re
from decimal import *

l = sys.stdin.readline()
l = l.split(' ')
l = [int(str) for str in l]

hv = l[0]
wv = l[1]
ex = wv-1
ey = hv-1
minlen = hv*wv

def dp(s,x,y,count):
  global minlen
  if( s[x+y*wv] == '#'):
    count += 1
  if( x == ex and y == ey ):
    minlen = min(minlen, count)
    if(minlen==0):
      print("0")
      exit(0)
  if( x+1 < wv):
    dp(s,x+1,y,count)
  if( y+1 < hv):
    dp(s,x,y+1,count)

s = ""
for h in range(0,hv):
   s = s + sys.stdin.readline().replace('\n','')

sx = 0
sy = 0
count = 0
dp(s, sx, sy, count)


print(minlen)

sys.stdout.flush()

Submission status: Time Limit Exceeded

Solution code:
import sys
import re
from decimal import *

l = sys.stdin.readline()
l = l.split(' ')
l = [int(str) for str in l]

hv = l[0]
wv = l[1]
ex = wv-1
ey = hv-1
minlen = hv*wv

def dp(s,x,y,count):
  global minlen
  if( s[x+y*wv] == '#'):
    count += 1
  if( x == ex and y == ey ):
    minlen = min(minlen, count)
  if( x+1 < wv):
    dp(s,x+1,y,count)
  if( y+1 < hv):
    dp(s,x,y+1,count)

s = ""
for h in range(0,hv):
   s = s + sys.stdin.readline().replace('\n','')

sx = 0
sy = 0
count = 0
dp(s, sx, sy, count)


print(minlen)

sys.stdout.flush()

Submission status: Time Limit Exceeded

Solution code:
import queue
INF = 10**10


H, W = map(int, input().split())

def next_field (a):
    ret = []
    if a[0] < H-1 :
        ret.append((a[0] + 1, a[1]))
    
    if a[1] < W-1:
        ret.append((a[0], a[1] + 1))
    
    return ret

field = {}
dist = {}
for h in range(H):
    f = input()
    for w, c in enumerate(f):
        field[(h,w)] = c
        dist[(h,w)] = INF

que = queue.PriorityQueue()

if field[(0,0)] == ".":
    dist[(0,0)] = 0
else:
    dist[(0,0)] = 1

que.put((0,0))


while not que.empty():
    cur = que.get()

    for nxt in next_field(cur):

        if field[cur] == field[nxt] or field[nxt] == ".":
            dist[nxt] = min(dist[nxt], dist[cur])
        else:
            dist[nxt] = min(dist[nxt], 1 + dist[cur])

        que.put(nxt)
    
print(dist[(H-1,W-1)])

Submission status: Time Limit Exceeded

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

def com(r, c):
	if r == 1 and c == 1:
		if masu[0][0] == '.':
			a = 0
		else:
			a = 1
	elif r == 1 and c >= 2:
		a = masu[0][:c].count('#')
	elif r >= 2 and c == 1:
		if masu[r-1][0] == '.':    
			a = com(r-1, 1) + 0
		else:
			a = com(r-1, 1) + 1
	else:
		if masu[r-1][c-1] == '.':
			a = min(com(r-1, c), com(r, c-1))
		else:
			a = min(com(r-1, c), com(r, c-1)) + 1
      
	return a
  
print(com(H, W))

Submission status: Time Limit Exceeded

Solution code:
from collections import deque
import pprint

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

dp=[[float("inf")]*w for _ in range(h)]
if sw[0][0] == "#":
    dp[0][0] = 1
else:
    dp[0][0] = 0
    
def bfs():
    que = deque([])
    que.append((0,0))
    while que:
        p = que.popleft()
        for i in range(2):
            if i == 0:
                nx = p[0] + 1
                ny = p[1]
            if i == 1:
                nx = p[0]
                ny = p[1] + 1
            if nx < w and ny < h: 
                bw_check=0
                if sw[p[1]][p[0]] == "#" and sw[ny][nx] == ".":
                    bw_check = 1       
                que.append((nx,ny))
                dp[ny][nx] = min(dp[ny][nx],dp[p[1]][p[0]]+bw_check)

    return dp

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

Submission status: Time Limit Exceeded

Solution code:
# Problem A - Range Flip Find Route

# input
h, w = map(int, input().split())
s_board = [['.']*w for i in range(h)]
c_board = [[100000]*w for i in range(h)]
for i in range(h):
    w_line = list(input())
    for j in range(w):
        s_board[i][j] = w_line[j]

# initialization
visit_queue = []

# count step
visit_queue.append([0, 0])
c_board[0][0] = 0
while len(visit_queue)>0:
    q = visit_queue.pop(0)
    r = q[0]
    c = q[1]
    # right
    if c+1<w:
        if s_board[r][c]=='.' and s_board[r][c+1]=='#':
            c_board[r][c+1] = min(c_board[r][c+1], c_board[r][c]+1)
        else:
            c_board[r][c+1] = min(c_board[r][c+1], c_board[r][c])
        visit_queue.append([r, c+1])
    # down
    if r+1<h:
        if s_board[r][c]=='.' and s_board[r+1][c]=='#':
            c_board[r+1][c] = min(c_board[r+1][c], c_board[r][c]+1)
        else:
            c_board[r+1][c] = min(c_board[r+1][c], c_board[r][c])
        visit_queue.append([r+1, c])

# start adjust
if s_board[0][0]=='#':
    c_board[h-1][w-1] += 1

# output
print(c_board[h-1][w-1])

Submission status: Time Limit Exceeded

Solution code:
from collections import deque
H, W = map(int, input().split())
maze = [list(input()) for i in range(H)]
dp = [[float('inf')]*W for i in range(H)]
dp[0][0] = 0

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

while len(q):
    pos = q.popleft()
    posX, posY = pos
    if posX + 1 < W:
        rightX, rightY = posX + 1, posY
        if maze[posY][posX] == "." and maze[rightY][rightX] == "#":
            dp[rightY][rightX] = min(dp[posY][posX] + 1, dp[rightY][rightX])
        else:
            dp[rightY][rightX] = min(dp[posY][posX], dp[rightY][rightX])
        q.append([rightX, rightY])
        
    if posY + 1 < H:
        downX, downY = posX, posY + 1
        if maze[posY][posX] == "." and maze[downY][downX] == "#":
            dp[downY][downX] = min(dp[posY][posX] + 1, dp[downY][downX])
        else:
            dp[downY][downX] = min(dp[posY][posX], dp[downY][downX])
        q.append([downX, downY])

if maze[0][0] == "#":
    print(dp[-1][-1] + 1)
else:
    print(dp[-1][-1])

Submission status: Time Limit Exceeded

Solution code:
import sys
from collections import deque

stdin = sys.stdin

ns = lambda: stdin.readline().rstrip()
ni = lambda: int(stdin.readline().rstrip())
nm = lambda: map(int, stdin.readline().split())
nl = lambda: list(map(int, stdin.readline().split()))

h,w = nm()
g = [list(map(lambda s:s=='#', list(input()))) for _ in range(h)]
dp = [[h*w]*w for _ in range(h)]
q = deque()
q.append((0,g[0][0]))
while q:
    v,d = q.popleft()
    if v == h*w-1: print(int(d)); break
    y,x = divmod(v,w)
    if dp[y][x] < d: continue
    dp[y][x] = d
    if y < h-1:
        if g[y+1][x] < g[y][x]:
            q.append((v+w, d+1))
        else:
            q.appendleft((v+w, d))
    if x < w-1:
        if g[y][x+1] < g[y][x]:
            q.append((v+1, d+1))
        else:
            q.appendleft((v+1, d))

Submission status: Time Limit Exceeded

Solution code:
# coding: utf-8
# Your code here!

# coding: utf-8 
# Your code here! 
H,W=map(int,input().split()) 
S=[] 

for _ in range(H):
    S.append(list(input()))


def dfs(h,w,num):
    if h==H-1 and w==W-1:
        ans.append(num)
    
    if h!=H-1: 
        if S[h+1][w]=="#": 
            dfs(h+1,w,num+1)
        else:
            dfs(h+1,w,num)

    if w!=W-1: 
        if S[h][w+1]=="#": 
            dfs(h,w+1,num+1)
        else:
            dfs(h,w+1,num)

ans=[]
dfs(0,0,1) if S[0][0]=="#" else dfs(0,0,0)

print(min(ans))

Submission status: Time Limit Exceeded

Solution code:
import queue

class VInfo(object):
    def __init__(self,x,y,d,color):
        self.color=color
        self.d=d
        self.x=x
        self.y=y
    def turnColor(self):
        if self.color==".":return "#"
        else:return "."

h,w=map(int,input().split())
a=[[str(i) for i in input()] for j in range(h)]
sx,sy=0,0
gx,gy=w-1,h-1
cw=0
mapA=[]
m=100000000000000
for my in range(h):
    l=[]
    for mx in range(w):
        l.append(m)
    mapA.append(l)

q=queue.Queue()
if a[0][0]==".":q.put(VInfo(0,0,0,"."))
else:q.put(VInfo(0,0,1,"#"))
l=[]
while not q.empty():
    now=q.get()
    if now.x==gx and now.y==gy:
        if now.color=="#":l.append((mapA[gy][gx]+2)//2)
        else:l.append((mapA[gy][gx]+1)//2)

    if now.y+1<h and a[now.y+1][now.x]==now.color and mapA[now.y+1][now.x]>now.d:
            mapA[now.y+1][now.x]=now.d
            q.put(VInfo(now.x,now.y+1,now.d,now.color))
    if now.y+1<h and a[now.y+1][now.x]!=now.color and mapA[now.y+1][now.x]>now.d:
            mapA[now.y+1][now.x]=now.d
            q.put(VInfo(now.x,now.y+1,now.d+1,now.turnColor()))
    if now.x+1<w and a[now.y][now.x+1]==now.color and mapA[now.y][now.x+1]>now.d:
            mapA[now.y][now.x+1]=now.d
            q.put(VInfo(now.x+1,now.y,now.d,now.color))
    if now.x+1<w and a[now.y][now.x+1]!=now.color and mapA[now.y][now.x+1]>now.d:
            mapA[now.y][now.x+1]=now.d
            q.put(VInfo(now.x+1,now.y,now.d+1,now.turnColor()))
print(min(l))