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())
s = [input() for _ in range(H)]

A = [[H+W-1 for _ in range(W)] for _ in range(H)]
if s[0][0] == ".": 
  A[0][0] = A[0][1] = A[1][0] = 0
else: A[0][0] = A[0][1] = A[1][0] = 1

x = [1,0]
y = [0,1]

while len(x) > 0:
  if s[x[0]][y[0]] == "#":
    A[x[0]][y[0]] += 1
  if x[0] + 1 < W:
    x.append(x[0] + 1)
    y.append(y[0])
    A[x[-1]][y[-1]] = min(A[x[0]][y[0]], A[x[-1]][y[-1]])
  if y[0] + 1 < H:
    x.append(x[0])
    y.append(y[0]+1)
    A[x[-1]][y[-1]] = min(A[x[0]][y[0]], A[x[-1]][y[-1]])
  x.pop(0)
  y.pop(0)
print(A[-1][-1] if s[-1][-1] == "." else A[-1][-1]-1)

Submission status: Time Limit Exceeded

Solution code:
from math import ceil

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

n = h * w

dp = [[[float("inf")] * 2 for _ in range(n + 1)] for _ in range(n + 1)]
if s[0][0] == "#":
    dp[1][1][1] = 1
else:
    dp[1][1][0] = 0

for i in range(1, h + 1):
    for j in range(1, w + 1):
        if s[i-1][j-1] == "#":
            dp[i][j][1] = min(dp[i][j][1], dp[i-1][j][0] + 1, dp[i-1][j][1], dp[i][j-1][0] + 1, dp[i][j-1][1])
        else:
            dp[i][j][0] = min(dp[i][j][0], dp[i-1][j][0], dp[i-1][j][1] + 1, dp[i][j-1][0], dp[i][j-1][1] + 1)

idx = 1 if s[h-1][w-1] == "#" else 0
ans = dp[h][w][idx]
ans = ceil(ans / 2)
print(ans)

Submission status: Time Limit Exceeded

Solution code:
h,w=map(int,input().split())
s=[tuple(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
q=deque([(0,0)])

while q:
    x,y=q.popleft()
    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])
        q.append((x+dx,y+dy))
print(g[-1][-1])

Submission status: Time Limit Exceeded

Solution code:
h, w = list(map(int, input().split(" ")))
mp = [list(input()) for _ in range(h)]

ans = 0


def next(cx, cy):
    c = 0
    g, b = 0, 0
    if mp[cy - 1][cx - 1] == "#":
        c = 1
    # end
    if cx != w:
        g = next(cx + 1, cy) + c
    else:
        return c
    if cy != h:
        b = next(cx, cy + 1) + c
    else:
        return c
    return c + min(g, b)


print(next(1, 1))

Submission status: Time Limit Exceeded

Solution code:
H,W = map(int, input().split())
maze = []
for i in range(H):
    maze.append(list(input()))
distan = [[float('inf')]*W for i in range(H)]
distan[0][0] = 0
from collections import deque
quex = deque([0])
quey = deque([0])
dist = deque([1])
par = deque([0])

if maze[0][0] == '.':
    par.pop()
    par.append(1) #1が白
    dist.pop()
    dist.append(0)


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


while quex:
    x =quex.popleft()
    y = quey.popleft()
    p = par.popleft()
    d = dist.popleft()
    for i in range(2):
        if  (x+dx[i])<0 or (x+dx[i])>=H or (y+dy[i])<0 or (y+dy[i])>=W:
            continue
        if p == 1:
            if maze[x + dx[i]][y + dy[i]] == '.':
                distan[x + dx[i]][y + dy[i]] = min(d, distan[x + dx[i]][y + dy[i]])
                quex.append(x + dx[i])
                quey.append(y + dy[i])
                par.append(1)
                dist.append(d)
            elif maze[x + dx[i]][y + dy[i]] == '#':
                distan[x + dx[i]][y + dy[i]] = min(d+1, distan[x + dx[i]][y + dy[i]])
                quex.append(x + dx[i])
                quey.append(y + dy[i])
                par.append(0)
                dist.append(d+1)
        elif p == 0:
            if maze[x + dx[i]][y + dy[i]] == '.':
                distan[x + dx[i]][y + dy[i]] = min(d, distan[x + dx[i]][y + dy[i]])
                quex.append(x + dx[i])
                quey.append(y + dy[i])
                par.append(1)
                dist.append(d)
            elif maze[x + dx[i]][y + dy[i]] == '#':
                distan[x + dx[i]][y + dy[i]] = min(d, distan[x + dx[i]][y + dy[i]])
                quex.append(x + dx[i])
                quey.append(y + dy[i])
                par.append(0)
                dist.append(d)
print(distan[H-1][W-1])

Submission status: Time Limit Exceeded

Solution code:
import itertools
k = input()

heigh, wight = k.split(' ')

list_ = []
for i in range(0, int(heigh)):
  f = input()
  list_.append(list(f))
list_.reverse()
sg = '0' * (int(heigh) - 1) + '1' * (int(wight) -1)
l_ = [int(i) for i in sg]
result_counts = [500]
max_ = 0
if int(heigh) > int(wight):
  max_ = int(heigh)
else:
  max_ = int(wight)

for l__ in set(list(itertools.permutations(l_))):
    count = 0
    x, y = 0, 0
    now = list_[int(heigh) - y - 1][x]
    for s in l__:
        if s == 1:
            x = x + 1
        else:
            y = y + 1
        next_ = list_[int(heigh) - y - 1][x]
        if now == '#' and next_== '.':
            count += 1
        if count > max_:
            break
        if count > min(result_counts):
            break
        now = next_
    if now == '#':
        count += 1
    result_counts.append(count)
    if count == 0:
        break
print(min(result_counts))

Submission status: Time Limit Exceeded

Solution code:
import queue

class VInfo(object):
    def __init__(self,color,x,y,d,isChange):
        if not isChange:
            self.color=color
            self.d=d
        else:
            if color==".":self.color="#"
            else:self.color="."
            self.d=d+1
        self.x=x
        self.y=y

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


q=queue.Queue()
q.put(VInfo(".",sx,sy,0,False))
isGoal=False
m=100000000000000
while not q.empty():
    now=q.get()
    cnt=now.d
    if now.x==gx and now.y==gy:
        m=min(m,now.d)
    if now.y+1<w and a[now.y+1][now.x]==now.color:q.put(VInfo(now.color,now.x,now.y+1,now.d,False))
    if now.y+1<w and a[now.y+1][now.x]!=now.color:q.put(VInfo(now.color,now.x,now.y+1,now.d,True))

    if now.x+1<h and a[now.y][now.x+1]==now.color:q.put(VInfo(now.color,now.x+1,now.y,now.d,False))
    if now.x+1<h and a[now.y][now.x+1]!=now.color:q.put(VInfo(now.color,now.x+1,now.y,now.d,True))
if a[h-1][w-1]=="#":m+=1
m=m//2
if a[0][0]=="#":m+=1
print(m)

Submission status: Time Limit Exceeded

Solution code:
# input
H, W = [int(_) for _ in input().split(' ')]
#cheese = [[float(1) if a=='.' else float('inf') for a in input()] for _ in range(H)]
cheese = [[a for a in input()] for _ in range(H)]
#print(H,W)
#print(cheese)
START = [0,0]
if cheese[0][0]=='#':
    START.append(1)
else:
    START.append(0)

GOAL = [H-1, W-1]

#process
point = []
point.insert(0, START)
minimum = float('inf')

while True:
    #print(point)
    # break condition
    if not minimum==float('inf'):
        length = len(point)
        c = 0
        for i in range(length):
            if point[i-c][2]>=minimum:
                #print('nyan')
                point.pop(i-c)
                c += 1
    # que has element or not
    if len(point)==0:
        break
    h, w, count = point.pop()
    if h==GOAL[0] and w==GOAL[1]:
        if minimum>count:
            minimum = count
        if count==0:
            break

    # explore
    for i in range(0,2):
        h_, w_, count_ = h + [1,0][i], w + [0,1][i], count
        if h_>=0 and h_<H and w_>=0 and w_<W:
            if cheese[h_][w_]=='#':
                count_+=1
            point.insert(0, [h_,w_,count_])

print(minimum)

Submission status: Time Limit Exceeded

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

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

#方向ベクトル 今回は右と下への移動のみを考える　
#つまり行と列番号を増やす向きのみ考える
dx = [1,0]
dy = [0,1]

#####白マスの中を泳ぐdfsの定義
def wdfs(h,w,grid,seen,l_b):
  #白マスの時にかぎり以下を行う
  if grid[h][w] == ".":
    seen[h][w] = True
    for i in range(2):
      new_h = h + dy[i]
      new_w = w + dx[i]

      #場外アウトしたり、移動先が壁の場合はスルー
      if (new_h<0 or new_w <0 or new_h>=H or new_w >= W ):
        continue
      #移動先が黒マスの時はスルー
      elif grid[new_h][new_w] == "#":
        l_b.append([new_h,new_w])
        continue
      #移動先が探索済みの場合スルー
      elif seen[new_h][new_w] == True:
        continue
      wdfs(new_h,new_w,grid,seen,l_b)  
  #最初のマスが黒かった時    
  else:
    l_b.append([h,w])           
#####dfsの定義

#####黒マスの中を泳ぐdfsの定義
def bdfs(h,w,grid,seen,l_w):
  seen[h][w] = True

  for i in range(2):
    new_h = h + dy[i]
    new_w = w + dx[i]

    #場外アウトの場合はスルー
    if (new_h<0 or new_w <0 or new_h>=H or new_w >= W ):
      continue
    #移動先が白マスの時はスルー
    elif grid[new_h][new_w] == ".":
      l_w.append([new_h,new_w])
      continue
    #移動先が探索済みの場合スルー
    elif seen[new_h][new_w] == True:
      continue
    bdfs(new_h,new_w,grid,seen,l_w)  
#####dfsの定義

#探索
seen = [ [False for i in range(W)] for i in range(H) ]
cnt = 0
l_w =deque( [[0,0]] )
l_b =deque([])


while seen[H-1][W-1] == False:
  while len(l_w) > 0: 
    w = l_w.popleft()
    wdfs(w[0],w[1],grid,seen,l_b)
  if seen[H-1][W-1] == True:
    break

  cnt = cnt+1

  while len(l_b) > 0: 
    b = l_b.popleft()
    bdfs(b[0],b[1],grid,seen,l_w)
  if seen[H-1][W-1] == True:
    break

###
print(cnt)

Submission status: Time Limit Exceeded

Solution code:
import sys
from collections import deque
input = sys.stdin.readline
sys.setrecursionlimit(10**9)
H, W = map(int, input().split())
S = [list(input()) for i in range(H)]
G = [[] for _ in range(H*W)]
for i in range(H*W) :
    h = i//W
    w = i%W
    if S[h][w] == "#" :
        if h >= 1 and S[h-1][w] == "." :
            j = (h-1)*W + w
            G[i].append(j)
        if h < H-1 and S[h+1][w] == "." :
            j = (h+1)*W + w
            G[i].append(j)
        if w >= 1 and S[h][w-1] == "." :
            j = h*W + w-1
            G[i].append(j)
        if w < W-1 and S[h][w+1] == "." :
            j = h*W + w+1
            G[i].append(j)
    if S[h][w] == "." :
        if h >= 1 and S[h-1][w] == "#" :
            j = (h-1)*W + w
            G[i].append(j)
        if h < H-1 and S[h+1][w] == "#" :
            j = (h+1)*W + w
            G[i].append(j)
        if w >= 1 and S[h][w-1] == "#" :
            j = h*W + w-1
            G[i].append(j)
        if w < W-1 and S[h][w+1] == "#" :
            j = h*W + w+1
            G[i].append(j)

def root(pat) :
    now = 0
    tmp = 0
    for i in pat :
        if i == "R" :
            now += 1
            if now in G[now-1] :
                tmp += 1
        elif i == "D" :
            now += W
            if now in G[now-W] :
                tmp += 1
    return tmp

ans = 10**10
import itertools
r = "R"*(W-1)+"D"*(H-1)
for pat in itertools.permutations(r, W+H-2) :
    ans = min(ans,root(pat))

ans2 = 0
if S[0][0] == "#" :
    ans2 += 1
    ans -= 1
if S[H-1][W-1] == "#" :
    ans2 += 1
    ans -= 1

print(ans//2 + ans2)

Submission status: Time Limit Exceeded

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

mat=[]
for i in range(H):
  array=[x=='.' for x in input()]
  mat.append(array)
#print(mat)

#convert mat to graph
#(i0,j0)->(i1,j1,dist)
graph={}
if mat[0][0]:
  graph[(0,0)]=[(1,1,0)]
else:
  graph[(0,0)]=[(1,1,1)]
  
for i in range(H):
  for j in range(W):
    graph[(i+1,j+1)]=[]
    if mat[i][j]:
      if i<H-1:
        if mat[i+1][j]:
          graph[(i+1,j+1)].append((i+2,j+1,0))
        else:
          graph[(i+1,j+1)].append((i+2,j+1,1))
      if j<W-1:
        if mat[i][j+1]:
          graph[(i+1,j+1)].append((i+1,j+2,0))
        else:
          graph[(i+1,j+1)].append((i+1,j+2,1))
    else:
      if i<H-1:
        graph[(i+1,j+1)].append((i+2,j+1,0))
      if j<W-1:
        graph[(i+1,j+1)].append((i+1,j+2,0))
#print(graph)

# init used,queue,dist
used={}
dist={}
queue=set()
used[(0,0)]=False
dist[(0,0)]=0
queue.add((0,0))
for i in range(1,H+1):
  for j in range(1,W+1):
    used[(i,j)]=False
    dist[(i,j)]=10**9
    queue.add((i,j))
#print(queue)

#dkjstra
while(True):
  d=10**9
  min_q=None
  for q in queue:
    if not used[q] and dist[q]<d:
      min_q=q
      d=dist[q]
      
  #print(min_q,d)
  if min_q==None:
    break
    
  used[min_q]=True
  candlist=graph[min_q]
  for cand in candlist:
    xx,yy,dd=cand
    dist[(xx,yy)]=min(dist[(xx,yy)],dist[min_q]+dd)
  
print(dist[(H,W)])

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

    p = deque()
    q = deque()

    n = a[0][0]=='.'
    if n:
        p.append((0,0,0))
    else:
        q.append((0,0,1))

    while(True):
        if p:
            f = p.pop()
            x, y, c = f[0], f[1], f[2]
        else:
            f = q.pop()
            x, y, c = f[0], f[1], f[2]

        for u, v in [(1,0), (0,1)]:
            if x + u <= w - 1 and y + v <= h - 1:
                if x+u == w-1 and y+v == h-1:
                    n = a[w-1][h-1]=='#'
                    print(c+n)
                    exit()

                n = a[x+u][y+v]=='.'
                if n:
                    p.append((x + u, y + v, c + 0))
                else:
                    q.appendleft((x + u, y + v, c + 1))



if __name__=='__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(2147483)

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

ds = [(1, 0), (0, 1), (-1, 0), (0, -1)]
ans = []

def dfs(x, y, m):
    if board[y][x] == "#":
        m += 1
    if x == w - 1 and y == h - 1:
        ans.append(m)
        return
    temp = board[y][x]
    board[y][x] = "x"
    for (dx, dy) in ds:
        if -1 < x + dx < w and -1 < y + dy < h and board[y + dy][x + dx] != "x":
            dfs(x + dx, y + dy, m)
    board[y][x] = temp
        
dfs(0, 0, 0)
print(min(ans))

Submission status: Time Limit Exceeded

Solution code:
import itertools
k = input()

heigh, wight = k.split(' ')

list_ = []
for i in range(0, int(heigh)):
  f = input()
  list_.append(list(f))
list_.reverse()
sg = '0' * (int(heigh) - 1) + '1' * (int(wight) -1)
l_ = [int(i) for i in sg]
result_counts = [500]

for l__ in set(list(itertools.permutations(l_))):
    count = 0
    x, y = 0, 0
    now = list_[int(heigh) - y - 1][x]
    for s in l__:
        if s == 1:
            x = x + 1
        else:
            y = y + 1
        next_ = list_[int(heigh) - y - 1][x]
        if now == '#' and next_== '.':
            count += 1
        if count > min(result_counts):
            break
        now = next_
    if now == '#':
        count += 1
    result_counts.append(count)
    if count == 0:
        break
print(min(result_counts))

Submission status: Time Limit Exceeded

Solution code:
import itertools
h, w = map(int, input().split())
map_lst = []
for i in range(h):
    map_lst.append(list(input()))
#0:下 1:右
lst = [i for i in range(h + w - 2)]
lst = list(itertools.combinations(lst,h-1))
ans = 200
for i in lst:
    rc_lst = [1] * (h + w - 2)
    for j in i:
        rc_lst[j] = 0
    bw_lst = []
    if map_lst[0][0] == '.': bw_lst.append(0)
    elif map_lst[0][0] == '#': bw_lst.append(1)
    r = 0
    c = 0
    cnt_b = 0
    # print(rc_lst)
    for j in range(h + w - 2):
        if rc_lst[j] == 0: r += 1
        elif rc_lst[j] == 1: c += 1
        if map_lst[r][c] == ".":
            if bw_lst[-1] == 1:
                cnt_b += 1
            bw_lst.append(0)
        elif map_lst[r][c] == "#":
            bw_lst.append(1)
    if map_lst[h-1][w-1] == '#': cnt_b += 1
    ans = min(ans, cnt_b)
    # print(rc_lst, bw_lst, cnt_b)
print(ans)

Submission status: Time Limit Exceeded

Solution code:

#####

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

#####

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, nextParams: deque, usedRC0: set):
	
# 	print()
# 	print("row0",row0,"col0",col0,"flipSize",flipSize)
	
	visited=np.zeros((h-row0, w-col0), np.bool)
	visited[0,0]=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-row0,wi-col0]:
				if c:
					visited[hi-row0,wi-col0]=True
					usedRC0.add((hi,wi))
				else:
					next.add((hi,wi))
			if wi>0 and visited[hi-row0,wi-1-col0]:
				if c:
					visited[hi-row0,wi-col0]=True
					usedRC0.add((hi,wi))
				else:
					next.add((hi,wi))
		if not visited[hi-row0].any(): break
	
	if visited[h-1-row0,w-1-col0]:
# 		print("found")
		print(flipSize)
		sys.exit(0)
					
# 	print("next",next)
	
	if len(next)==0: return None
	
	if targetColor: nextFlipSize=flipSize+1
	else: nextFlipSize=flipSize
	
	next=sorted(next, key=lambda x: -(x[0]+x[1]))
	
	for nrc in next:
		if nrc in usedRC0: continue
		usedRC0.add(nrc)
		p=(colors, h, w, nrc[0], nrc[1], not targetColor, nextFlipSize)
		nextParams.append(p)


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.astype(np.int32))
	
	if colors[0,0]: nextFlipSize=0
	else: nextFlipSize=1
	
	nextParams=deque()
	p=(colors, h, w, 0, 0, colors[0,0], nextFlipSize)
	nextParams.append(p)
	
	usedRC0=set()
	while len(nextParams)>0:
		param=nextParams.popleft()
		travel(*param, nextParams=nextParams, usedRC0=usedRC0)


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

Submission status: Time Limit Exceeded

Solution code:
#coding:utf-8

from collections import deque

def main():
    h, w = map(int, input().split())
    mtrx = []
    for _ in range(h):
        mtrx.append(list(input()))
    
    dire = [[0, 1], [1, 0]]
    cnt = 0
    q = deque([])
    # cnt, flg, i, j
    if mtrx[0][0] == '#':
        cnt += 1
    q.append([cnt, mtrx[0][0], 0, 0])

    minv = 100000000000

    dummy = [[minv for _ in range(w)] for _ in range(h)]
    while len(q) > 0:
        now = q.popleft()
        i = now[2]
        j = now[3]

        for d in dire:
            i_n = i + d[0]
            j_n = j + d[1]
            cnt = now[0]
            if i_n >= w or j_n >= h:
                continue
            if mtrx[i_n][j_n] == '#':
                cnt += 1
            if dummy[i_n][j_n] <= cnt:
                continue
            # print(now)
            # print(mtrx[i_n][j_n])
            next_obj = [cnt, mtrx[i_n][j_n], i_n, j_n]
            q.append(next_obj)
            
        if i == h - 1 and j == w - 1:
            minv = min(minv, now[0])
    print(minv)

if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

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

def f(a,b,s,pre):
  x=0
  if s[a-1][b-1]=="#":
    if pre==".":
      x=1
  if a==1:
    if b==1:
      return(x)
    else:
      y=x+f(a,b-1,s,s[a-1][b-1])
      return(y)
  elif b==1:
    y=x+f(a-1,b,s,s[a-1][b-1])
    return(y)
  else:
    y=x+min(
      f(a-1,b,s,s[a-1][b-1]),
      f(a,b-1,s,s[a-1][b-1]))
    return(y)

y=f(h,w,s,".")
print(y)

Submission status: Time Limit Exceeded

Solution code:
# def solve():
#
#
# def test():
#
#
# def main():
#     H,
#     solve()
#     test()
#
# if __name__ == "main":
#     main()


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

WALL = '#'
ROAD = '.'
cnt_global = []

stack = [(0, 0, 0)]

while stack:
    """
    stack取り出す
    調べる
    stack
    """
    y, x, cnt = stack.pop()
    if S[y][x] == WALL:
        cnt += 1

    if (y, x) == (H - 1, W - 1):
        cnt_global.append(cnt)

    next_y = y + 1
    next_x = x + 1

    if cnt_global and max(cnt_global) <= cnt:
        pass
    else:
        if next_y < H and next_x < W:
            stack.append([next_y, x, cnt])
            stack.append([y, next_x, cnt])
        elif next_y == H and next_x < W:
            stack.append([y, next_x, cnt])
        elif next_y < H and next_x == W:
            stack.append([next_y, x, cnt])

print(min(cnt_global))

Submission status: Time Limit Exceeded

Solution code:
import itertools
import sys
input = sys.stdin.readline
[hukasa,haba]=[int(i)for i in input().split()]

map=[]

for i in range(hukasa):
    numedInp = [True if chr=='#' else False for chr in input()]
    map.append(numedInp)

patternTuple=tuple(itertools.combinations(range(hukasa+haba-2),hukasa-1))

#print(patternTuple)
min=hukasa+haba-2

for item in patternTuple:
    #print(item)
    flipCnt=0
    renzokuCnt=0
    h=0
    w=0
    #itemに数字があるステップは下に行く
    for i in range(hukasa+haba-2):
        #print("{},{}".format(h,w))
        if map[h][w]:
            #黒なら連続カウント+1
            renzokuCnt+=1
        else:
            #連続カウントが溜まっていればフリップ回数+1,白なら連続カウント=0
            if renzokuCnt>0:
                flipCnt+=1
                if(flipCnt==min):break
            renzokuCnt+=0
        if i in item:
            #下に行く
            h+=1
        else:
            #右に行く
            w+=1
    if renzokuCnt>0:flipCnt+=1
    renzokuCnt+=0
    #最後に連続カウントが溜まっていればフリップ
    if min>flipCnt:
        min=flipCnt

print(min)

Submission status: Time Limit Exceeded

Solution code:
H, W = input().split(' ')
H = int(H)
W = int(W)
S = 100000

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

def dfs(r, c, cnt):
    global S
    if cnt > S:
        return
    if map[r - 1][c - 1] == '#':
        cnt += 1
    if r == H and c == W:
        if cnt < S:
            S = cnt
        return
    if r < H:
        dfs(r + 1, c, cnt)
    if c < W:
        dfs(r, c + 1, cnt)

dfs(1, 1, 0)
print(S)

Submission status: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(2147483647)

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

ds = [(1, 0), (0, 1), (-1, 0), (0, -1)]
ans = []

def dfs(x, y, m):
    if board[y][x] == "#":
        m += 1
    if x == w - 1 and y == h - 1:
        ans.append(m)
        return
    temp = board[y][x]
    for (dx, dy) in ds:
        board[y][x] = "x"
        if -1 < x + dx < w and -1 < y + dy < h and board[y + dy][x + dx] != "x":
            dfs(x + dx, y + dy, m)
        board[y][x] = temp
        
dfs(0, 0, 0)
print(min(ans))

Submission status: Time Limit Exceeded

Solution code:
H, W = input().split(' ')
H = int(H)
W = int(W)
S = 100000

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

def dfs(r, c, cnt):
    if map[r - 1][c - 1] == '#':
        cnt += 1
    if r == H and c == W:
        global S
        if cnt < S:
            S = cnt
        return
    if r < H:
        dfs(r + 1, c, cnt)
    if c < W:
        dfs(r, c + 1, cnt)

dfs(1, 1, 0)
print(S)

Submission status: Time Limit Exceeded

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

def bfs(r, c, count):
    # マス目をいい状態にする
    if arr[r][c] == '#':
        count += 1

    # ゴールした場合終了
    if r == H - 1 and c == W - 1 :
        ans.append(count)
        return False

    # 下に進める場合は進む
    if r + 1 < H:
        bfs(r + 1, c, count)
    
    # 右に進める場合は進む
    if c + 1 < W:
        bfs(r, c + 1, count)


bfs(0, 0, 0)
print(min(ans))

Submission status: Time Limit Exceeded

Solution code:
import sys
import heapq

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

def removeWalls(wallPointH,wallPointW):
  if maze[wallPointH][wallPointW]=="#":
    maze[wallPointH][wallPointW]="."
    if wallPointH+1 <= H-1:
      removeWalls(wallPointH+1,wallPointW)
    if wallPointW+1 <= W-1:
      removeWalls(wallPointH,wallPointW+1)

que = [[0,0,0]]
heapq.heapify(que)
count = 0
      
while que:
  qu = heapq.heappop(que)
  #print(que)
  if qu[0]==1:
    heapq.heappush(que, qu)
    count += 1
    for q in que:#いったん"#"の撤去作業を行う
      q[0]=0
      removeWalls(q[1],q[2])
  else:#queの中身にまだTrueがあるなら
    now = qu
    nowH = now[1]
    nowW = now[2]
    if maze[nowH][nowW]=="#":#行き止まりの場合
      heapq.heappush(que, [1,nowH,nowW])
      continue
    elif nowH==H-1 and nowW==W-1:#ゴールの場合
      print(count)
      sys.exit()
    else:#それ以外の場合
      #右近傍と下近傍、それぞれマップの中ならqueに格納。
      if nowH+1 <= H-1:
        heapq.heappush(que, [0,nowH+1,nowW])
      if nowW+1 <= W-1:
        heapq.heappush(que, [0,nowH,nowW+1])

Submission status: Time Limit Exceeded

Solution code:
import copy 
import sys
import resource
from collections import deque
sys.setrecursionlimit(1000*1000)

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

#方向ベクトル 今回は右と下への移動のみを考える　
#つまり行と列番号を増やす向きのみ考える
dx = [1,0]
dy = [0,1]

#####白マスの中を泳ぐdfsの定義
def wdfs(h,w,grid,seen,l_b):
  #白マスの時にかぎり以下を行う
  if grid[h][w] == ".":
    seen[h][w] = True
    for i in range(2):
      new_h = h + dy[i]
      new_w = w + dx[i]

      #場外アウトしたり、移動先が壁の場合はスルー
      if (new_h<0 or new_w <0 or new_h>=H or new_w >= W ):
        continue
      #移動先が黒マスの時はスルー
      elif grid[new_h][new_w] == "#":
        l_b.append([new_h,new_w])
        continue
      #移動先が探索済みの場合スルー
      elif seen[new_h][new_w] == True:
        continue
      wdfs(new_h,new_w,grid,seen,l_b)  
  #最初のマスが黒かった時    
  else:
    l_b.append([h,w])           
#####dfsの定義

#####黒マスの中を泳ぐdfsの定義
def bdfs(h,w,grid,seen,l_w):
  seen[h][w] = True

  for i in range(2):
    new_h = h + dy[i]
    new_w = w + dx[i]

    #場外アウトの場合はスルー
    if (new_h<0 or new_w <0 or new_h>=H or new_w >= W ):
      continue
    #移動先が白マスの時はスルー
    elif grid[new_h][new_w] == ".":
      l_w.append([new_h,new_w])
      continue
    #移動先が探索済みの場合スルー
    elif seen[new_h][new_w] == True:
      continue
    bdfs(new_h,new_w,grid,seen,l_w)  
#####dfsの定義

#探索
seen = [ [False for i in range(W)] for i in range(H) ]
cnt = 0
l_w =deque( [[0,0]] )



while seen[H-1][W-1] == False:
  l_b =deque([])
  while len(l_w) > 0: 
    w = l_w.popleft()
    s1,s2 = w[0],w[1]
    wdfs(s1,s2,grid,seen,l_b)
  if seen[H-1][W-1] == True:
    break

  cnt = cnt+1

  l_w =deque([])
  while len(l_b) > 0: 
    b = l_b.popleft()
    s1,s2 = b[0],b[1]
    bdfs(s1,s2,grid,seen,l_w)
  if seen[H-1][W-1] == True:
    break

###
print(cnt)

Submission status: Time Limit Exceeded

Solution code:
import numpy as np

direction = [(0, 1), (1, 0)]
h = w = 0
min_cnt = np.inf

def dfs(x, y, cnt):
    global min_cnt
    for mx, my in direction:
        nx = x + mx
        ny = y + my
        # print(nx+1, ny+1)
        if w < nx+1 or h < ny+1:
            # print('over')
            continue

        if S[ny][nx] == "#":
            ncnt = cnt + 1
            # print(ncnt, min_cnt)
            if ncnt > min_cnt:
                continue
        else:
            ncnt = cnt

        if nx+1 == w and ny+1 == h:
            # print('goal', ncnt)
            if ncnt < min_cnt:
                min_cnt = ncnt
            return
        else:
            dfs(nx, ny, ncnt)


def solver():
    global h
    global w
    h, w = map(int, input().split())
    global S
    S = [list(input()) for _ in range(h)]
    dfs(0, 0, 1 if S[0][0] == "#" else 0)
    # print(change_cnt_list)
    print(min_cnt)


if __name__ == '__main__':
    solver()

Submission status: Time Limit Exceeded

Solution code:
from collections import deque

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

ans = 10**9

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

if C[0][0] == "#": 
    stack = deque([[0, 0, 1]])
    visited_list[0][0] = 1
else:
    stack = deque([[0, 0, 0]])
    visited_list[0][0] = 0

def dfs(town, visited_list, stack):
    global ans
    while len(stack) > 0:
        h, w, cnt = stack.pop()
        if h == H-1 and w == W-1 and ans > cnt:
            ans = cnt
            continue
        for j, k in ([1, 0], [0, 1]):
            new_h, new_w = h+j, w+k
            if new_h < 0 or new_h >= H or new_w < 0 or new_w >= W:
                continue
            if  visited_list[new_h][new_w] >= cnt and town[new_h][new_w] != "#":
                visited_list[new_h][new_w] = cnt
                stack.append([new_h, new_w, cnt])
            elif visited_list[new_h][new_w] >= cnt + 1 and town[new_h][new_w] == "#":
                visited_list[new_h][new_w] = cnt + 1
                # print("a " + str(cnt+1))
                stack.append([new_h, new_w, cnt+1])
    return ans

print(dfs(C, visited_list, stack))

Submission status: Time Limit Exceeded

Solution code:
import sys
input = lambda: sys.stdin.readline().rstrip() 

def resolve():
    H, W = map(int, input().split())
    s = [input() for _ in range(H)]
    # 全ルートの中で、連続する#の数が一番少ないものを探す

    ans = [H+W]
    dir = ((1, 0), (0, 1))
    # 前の色、前の進行方向、今までの連続ブロックの数
    
    def dfs(x, y, pw, pd, cnt):
        if x==W-1 and y==H-1:
            if pw=='.' and s[y][x]=='#':
                cnt += 1
            ans[0] = min(cnt, ans[0])
            if ans[0]==0:
                print(ans[0])
                sys.exit()
        else:
            for d in dir:
                nx = x+d[0]
                ny = y+d[1]
                if nx<W and ny<H:
                    ncnt = cnt
                    # 前が白で今が黒
                    if pw=='.' and s[y][x]=='#':
                        ncnt += 1
                    dfs(nx, ny, s[y][x], d, ncnt)

    dfs(0, 0, '.', dir[0], 0)
    print(ans[0])

if __name__ == '__main__':
    resolve()

Submission status: Time Limit Exceeded

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

WALL = '#'
ROAD = '.'
cnt_global = []

stack = [(0, 0, 0)]

while stack:
    """
    stack取り出す
    調べる
    stack
    """
    y, x, cnt = stack.pop()
    if S[y][x] == WALL:
        cnt += 1

    if (y, x) == (H - 1, W - 1):
        cnt_global.append(cnt)

    next_y = y + 1
    next_x = x + 1

    if next_y < H and next_x < W:
        stack.append([next_y, x, cnt])
        stack.append([y, next_x, cnt])
    elif next_y == H and next_x < W:
        stack.append([y, next_x, cnt])
    elif next_y < H and next_x == W:
        stack.append([next_y, x, cnt])


print(min(cnt_global))