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 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 = []

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
        now = next_
    if now == '#':
        count += 1
    result_counts.append(count)
print(min(result_counts))

Submission status: Time Limit Exceeded

Solution code:
dp = list(list(-1 for i in range(100)) for j in range(100))
def solve(l, i, j):
	if i==0 and j==0:
		if l[0][0]=='#':
			return 1
		else:
			return 0
	else:
		if j!=0:
			if dp[i][j-1]==-1:
				dp[i][j-1] = solve(l, i, j-1)
			else:
				dp[i][j-1] = min(dp[i][j-1], solve(l, i, j-1))
		if i!=0:
			if dp[i-1][j]==-1:
				dp[i-1][j] = solve(l, i-1, j)
			else:
				dp[i-1][j] = min(dp[i-1][j], solve(l, i-1, j))
		if l[i][j]=='#':
			if(i==0):	
				return(dp[i][j-1]+1)
			if(j==0):	
				return(dp[i-1][j]+1)
			else:
				return(min(dp[i][j-1], dp[i-1][j])+1)
		else:
			if(i==0):	
				return(dp[i][j-1])
			if(j==0):	
				return(dp[i-1][j])
			else:
				return(min(dp[i][j-1], dp[i-1][j]))
from sys import stdin, stdout
h, w = stdin.readline().split()
h = int(h)
w = int(w)
l = [list(input()) for x in range(h)]
print(solve(l, 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([int(g) for g in f.replace('#', '0').replace('.', '1')])
list_.reverse()
sg = '0' * (int(heigh) - 1) + '1' * (int(wight) -1)
l_ = [int(i) for i in sg]
result_counts = []

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 == 0 and next_== 1:
            count += 1
        now = next_
    if now == 0:
        count += 1
    result_counts.append(count)
print(min(result_counts))

Submission status: Time Limit Exceeded

Solution code:
import itertools
 
h, w = map(int, input().split())
 
HW = []
for i in range(h):
    HW.append(input())
    
roots = []
for i in range(h):
    for j in range(w):
        roots.append([i, j])
roots.pop(0)
 
search_root = []
for vv in itertools.combinations(roots, (h - 1) + (w - 1)):
    # 一番目が初期値以外はスキップ
    if not(vv[0] == [0, 1] or vv[0] == [1, 0]): continue
    # 最後が最終値以外はスキップ
    if not(vv[-1] == [h -1, w - 1]): continue
    tmp = []
    for v in vv:
        if tmp == []:
            tmp.append(v)
        else:
            # 右か下に移動するルート以外はスキップ
            if not(tmp[-1][0] == v[0] and tmp[-1][1] + 1 == v[1] \
                or tmp[-1][0] + 1 == v[0] and tmp[-1][1] == v[1]
                ): break
            tmp.append(v)
    if len(tmp) == ((h - 1) + (w - 1)):
        tmp.insert(0, [0, 0])
        search_root.append(tmp)
        
search_count = []
for root in search_root:
    count = 0
    is_break = False
    for point in root:
        r, c = point[0], point[1]
        if HW[r][c] == "#":
            count += 1
            if search_count:
                if min(search_count) < count:
                    is_break = True
                    break
    if not is_break: search_count.append(count)
      
print(min(search_count))

Submission status: Time Limit Exceeded

Solution code:
H,W = map(int, input().split())
S = []
for h in range(H):
    tmp_Si = input()
    Si = []
    for w in range(W):
        if tmp_Si[w] == '.':  #白
            Si.append(0)
        else:   #黒
            Si.append(1)
    S.append(Si)

#print(S)
move_vec = [[0,1], [1,0]]
record = [H+W]

def move_and_record(h, w, black):
    for dh, dw in move_vec:
        nh = h + dh
        nw = w + dw
        #print('nh=',nh)
        #print('nw=',nw)
        if nh == H-1 and nw == W-1: #ゴール
            if S[nh][nw] == 1:
                black += 1
            else:   #S[nh][nw] == 0:
                pass
            record.append(black)
        elif nh > H-1: #もう下にはいけない
            pass
        elif nw > W-1: #もう右にはいけない
            pass
        else:   #さらに進む
            if S[nh][nw] == 1:
                if black+1 >= min(record):
                    pass
                else:
                    move_and_record(nh, nw, black+1)
            else:   #S[nh][nw] == 0:
                move_and_record(nh, nw, black)
            """
            if S[nh][nw] == 1:
                black += 1
            else:   #S[nh][nw] == 0:
                pass
            
            if black >= min(record):
                pass
            else:
                move_and_record(nh, nw, black)
            """
            """
            if S[nh][nw] == 1:
                black += 1
            else:   #S[nh][nw] == 0:
                pass
            move_and_record(nh, nw, black)
            """

if S[0][0] == 1:
    move_and_record(0,0,1)
else:   #S[0][0] == 0:
    move_and_record(0,0,0)

#print(record)
print(min(record))

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([g for g in f.replace('#', '黒').replace('.', '白')])
list_.reverse()
sg = '下' * (int(heigh) - 1) + '右' * (int(wight) -1)
l_ = list(sg)
result_counts = []

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 == '右':
            x = x + 1
        else:
            y = y + 1
        next_ = list_[int(heigh) - y - 1][x]
        if now == '黒' and next_== '白':
            count += 1
        now = next_
    if now == '黒':
        count += 1
    result_counts.append(count)
print(min(result_counts))

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
    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
                # 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:
import numpy as np

def LI():
	return [ int(s) for s in input().split() ]

H,W = LI()
field = np.array([ list(input()) for _ in range(H) ])

min_cnt = 300

def dfs(i,j,cnt):
  global min_cnt
  if field[i][j] == '#':
    cnt+=1
  if cnt >= min_cnt:
    return 300
  if i==H-1 and j==W-1:
    if cnt <= min_cnt:
      min_cnt = cnt
    return cnt
  if i < H-1 and j < W-1:
    return min(dfs(i+1,j,cnt),dfs(i,j+1,cnt))
  if i < H-1:
    return dfs(i+1,j,cnt)
  if j < W-1:
    return dfs(i,j+1,cnt)

print(dfs(0,0,0))

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])
        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:
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:
            # print(h,w,cnt)
            if ans > cnt:
                ans = cnt
                continue
        for j, k in ([1, 0], [-1, 0], [0, 1], [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:
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("s")
        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.appendleft([x,y+1,count])
                q.appendleft([x+1,y,count])
            finished.add((x,y))
            if c[x][y]=="s":
                return count
print(search()+asd)

Submission status: Time Limit Exceeded

Solution code:
import itertools
 
h, w = map(int, input().split())
 
HW = []
for i in range(h):
    HW.append(input())
    
roots = []
for i in range(h):
    for j in range(w):
        roots.append([i, j])
roots.pop(0)
 
search_root = []
for vv in itertools.combinations(roots, (h - 1) + (w - 1)):
    # 一番目が初期値以外はスキップ
    if not(vv[0] == [0, 1] or vv[0] == [1, 0]): continue
    # 最後が最終値以外はスキップ
    if not(vv[-1] == [h -1, w - 1]): continue
    tmp = []
    for v in vv:
        if tmp == []:
            tmp.append(v)
        else:
            # 右か下に移動するルート以外はスキップ
            if not(tmp[-1][0] == v[0] and tmp[-1][1] + 1 == v[1] \
                or tmp[-1][0] + 1 == v[0] and tmp[-1][1] == v[1]
                ): continue
            tmp.append(v)
    if len(tmp) == ((h - 1) + (w - 1)):
        tmp.insert(0, [0, 0])
        search_root.append(tmp)
        
search_count = []
for root in search_root:
    count = 0
    is_break = False
    for point in root:
        r, c = point[0], point[1]
        if HW[r][c] == "#":
            count += 1
            if search_count:
                if min(search_count) < count:
                    is_break = True
                    break
    if not is_break: search_count.append(count)
      
print(min(search_count))

Submission status: Time Limit Exceeded

Solution code:
import numpy as np
import math
import itertools

H, W = map(int, input().split())
mat = np.zeros((H, W))

for i in range(H):
  lines = list(input())
  for j in range(W):
    if lines[j]=='#':
      mat[i,j] = 1
      
min_score = 1000

H_count = ''.join(str(0) for i in range(H-1))
W_count = ''.join(str(1) for i in range(W-1))
roots = H_count + W_count
for root in itertools.permutations(roots):
  state = np.zeros((H, W))
  h = 0
  w = 0
  state[h,w] = 1
  for a in root:
    if a == '0':
      h +=1
    else:
      w +=1
    state[h,w] = 1
    score = int(np.sum(mat * state))
  if score < min_score:
  	min_score = score

print(min_score)

Submission status: Time Limit Exceeded

Solution code:
direction = [(0, 1), (1, 0)]
h = w = 0
change_cnt_list = []


def dfs(x, y, 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
        else:
            ncnt = cnt

        if nx+1 == w and ny+1 == h:
            # print('goal', ncnt)
            change_cnt_list.append(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)]
    # print(S)
    # print(S[1-1][2-1])

    # last = (h, w)
    # q = deque([(1, 1)])
    dfs(0, 0, 1 if S[0][0] == "#" else 0)
    # print(change_cnt_list)
    print(min(change_cnt_list))


if __name__ == '__main__':
    solver()

Submission status: Time Limit Exceeded

Solution code:
import numpy as np

def LI():
	return [ int(s) for s in input().split() ]

H,W = LI()
field = np.array([ list(input()) for _ in range(H) ])

min_cnt = 300

def dfs(i,j,cnt):
  if field[i][j] == '#':
    cnt+=1
  if cnt >= min_cnt:
    return 300
  if i==H-1 and j==W-1:
    return cnt
  if i < H-1 and j < W-1:
    return min(dfs(i+1,j,cnt),dfs(i,j+1,cnt))
  if i < H-1:
    return dfs(i+1,j,cnt)
  if j < W-1:
    return dfs(i,j+1,cnt)

print(dfs(0,0,0))

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
				else:
					next.add((hi,wi))
			if wi>0 and visited[hi-row0,wi-1-col0]:
				if c:
					visited[hi-row0,wi-col0]=True
				else:
					next.add((hi,wi))
		if not visited[hi-row0].any(): break
	
	if visited[h-1-row0,w-1-col0]:
# 		print("found")
# 		return flipSize
		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)
# 	print("flipSize",flipSize)
# 	print(flipSize)


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

Submission status: Time Limit Exceeded

Solution code:
h,w=map(int,input().split())
s=[list(input()) for _ in range(h)]
q=[(0,0)]
g=[[1000]*w for  _ in range(h)]
g[0][0]=0
if s[0][0]=="#":
    g[0][0]=1
from collections import deque
q=deque([(0,0)])

while q:
    x,y=q.popleft()
    x*=-1
    y*=-1
    if x==w-1 and y==h-1:
        break
    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:
import sys
from collections import deque
sys.setrecursionlimit(10 ** 6)
input = sys.stdin.readline
H, W = [int(x) for x in input().strip().split()]
G = [0 for _ in range(H)]
C = [[float('inf') for _ in range(W)] for _ in range(H)]

pre = ''
NH = H
for h in range(H):
    s = list(input().strip())
    if s != pre:
        G[h] = s
        pre = s
    else:
        NH -= 1

H = NH
def dfs(r, c, cost):
    # print(' -- dfs --')
    C[r][c] = cost
    ret = deque([])
    q = deque([(r, c)])
    while q:
        cr, cc = q.popleft()
        # print('    cr = {}, cc = {}'.format(cr, cc))
        for i, j in [(0, 1), (1, 0)]:
            if not(0 <= cr + i < H and 0 <= cc + j < W):
                continue
            if C[cr+i][cc+j] != float('inf'):
                continue
            if G[r][c] == G[cr+i][cc+j]:
                C[cr+i][cc+j] = cost
                q.append((cr+i, cc+j))
            else:
                ret.append((cr+i, cc+j))
    # print(ret)
    return ret

q = deque([(0, 0)])
cost = 0
while True:
    # print('q = {}'.format(q))
    nq = deque([])
    if G[q[0][0]][q[0][1]] == '#':
        cost += 1
    for r, c in q:
        # print('  r = {}, c = {}'.format(r, c))
        nq.extend(dfs(r, c, cost))
    q = nq
    # print(C)
    # print('nq = {}'.format(nq))
    if C[H-1][W-1] != float('inf'):
        print(C[H-1][W-1])
        exit()

Submission status: Time Limit Exceeded

Solution code:
import itertools

h, w = map(int, input().split())

HW = []
for i in range(h):
    HW.append(input())
    
roots = []
for i in range(h):
    for j in range(w):
        roots.append([i, j])
roots.pop(0)

search_root = []
for vv in itertools.combinations(roots, (h - 1) + (w - 1)):
    # 一番目が初期値以外はスキップ
    if not(vv[0] == [0, 1] or vv[0] == [1, 0]): continue
    # 最後が最終値以外はスキップ
    if not(vv[-1] == [h -1, w - 1]): continue
    tmp = []
    for v in vv:
        if tmp == []:
            tmp.append(v)
        else:
            # 右か下に移動するルート以外はスキップ
            if not(tmp[-1][0] == v[0] and tmp[-1][1] + 1 == v[1] \
                or tmp[-1][0] + 1 == v[0] and tmp[-1][1] == v[1]
                ): continue
            tmp.append(v)
    if len(tmp) == ((h - 1) + (w - 1)):
        tmp.insert(0, [0, 0])
        search_root.append(tmp)
        
search_count = []
for root in search_root:
    count = 0
    is_break = False
    for point in root:
        r, c = point[0], point[1]
        if HW[r][c] == "#":
            count += 1
            if search_count:
                if min(search_count) < count:
                    is_break = True
                    break
    if not is_break: search_count.append(count)
      
print(min(search_count))

Submission status: Time Limit Exceeded

Solution code:
def dijkstra(s, n, cost):
    # 始点sから各頂点への最短距離
    # n:頂点数, cost[u][v] : 辺uvのコスト(存在しないときはinf)
    d = [float("inf")] * n
    used = [False] * n
    d[s] = 0
    R = {}

    while True:
        v = -1
        # まだ使われてない頂点の中から最小の距離のものを探す
        for i in range(n):
            if (not used[i]) and (v == -1):
                v = i
            elif (not used[i]) and d[i] < d[v]:
                v = i
        if v == -1:
            break
        used[v] = True

        for j in range(n):
            if d[j] > d[v]+cost[v][j]:
                R[j] = (v, j)
            d[j] = min(d[j], d[v]+cost[v][j])

    result = []
    result.append(n-1)
    cur = n-1
    while True:
        cur_next = R[cur][0]
        result.append(cur_next)
        cur = cur_next
        if cur == 0:
            break
    return result[::-1]
    # return d[n-1]


def _dijkstra():
    # n, w = map(int, input().split())  # n:頂点数　w:辺の数
    H, W = list(map(int, input().split()))
    A = []
    for _ in range(H):
        s = input()
        A.append(s)

    n = H * W

    cost = [[float("inf") for i in range(n)] for i in range(n)]
    # cost[u][v] : 辺uvのコスト(存在しないときはinf この場合は10**10)
    for i in range(H):
        for j in range(W):
            id = i * W + j
            # right
            if j != W-1:
                if A[i][j+1] == '.':
                    cost[id][id+1] = 1
                elif A[i][j+1] == '#':
                    cost[id][id+1] = 100000
                else:
                    raise Exception
            # down
            if i != H-1:
                if A[i+1][j] == '.':
                    cost[id][id+W] = 1
                elif A[i+1][j] == '#':
                    cost[id][id+W] = 100000
                else:
                    raise Exception
    route = dijkstra(0, n, cost)

    result = 0
    now_mark = A[0][0]
    if(now_mark) == '#':
        result += 1

    for id in route[1:]:

        i = id // W
        j = id % W
        next_mark = A[i][j]
        if now_mark == '.' and next_mark == '#':
            result += 1
        now_mark = next_mark
    print(result)


if __name__ == "__main__":
    _dijkstra()

Submission status: Time Limit Exceeded

Solution code:
h, w = list(map(int, input().split(" ")))
matrix = []
result = []

for i in range(h):
    matrix.append(input())
    
def check(x, y, count):
  if x > (h - 1):
    return
  if y > (w - 1):
    return

  if matrix[x][y] == "#":
    if result and min(result) < count:
      return
    count += 1
  if x == (w - 1) and y == (h - 1):
    result.append(count)
    return
  check(x+1, y, count)
  check(x, y+1, count)

check(0, 0, 0)
min_result = min(result) if result else 0
print(min_result)

Submission status: Time Limit Exceeded

Solution code:
import sys

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

Submission status: Time Limit Exceeded

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

INF = 10**20
def main():
    H,W = map(int,input().split())
    s = [[""] * W for _ in range(H)]
    for i in range(H):
        S = input()
        for j in range(W):
            s[i][j] = S[j]

    s_e = (s[0][0] == "#") + 0
    s_e += (s[H-1][W-1] == "#") + 0
    s[H-1][W-1] = "."


    def pos(r,c):
        return r*H+c

    max_edge = max(H+1,W+1) ** 2
    m = [0] * max_edge
    cost = [[INF] * max_edge for _ in range(max_edge)]
    for r in range(H):
        for c in range(W):
            cost_ = (s[r][c] == "#") + 0
            if r == c:
                cost[pos(r,c)][pos(r,c)] = 0

            if r > 0:
                cost[pos(r-1,c)][pos(r,c)] = cost_
                cost[pos(r,c)][pos(r-1,c)] = cost_
            if c > 0:
                cost[pos(r,c-1)][pos(r,c)] = cost_
                cost[pos(r,c)][pos(r,c-1)] = cost_
            # if c < W:
            #     cost[pos(r,c+1)][pos(r,c)] = cost_
            #     cost[pos(r,c)][pos(r,c+1)] = cost_
            # if r < H:
            #     cost[pos(r+1,c)][pos(r,c)] = cost_
            #     cost[pos(r,c)][pos(r+1,c)] = cost_




    d = [INF] * max_edge
    used = [False] * max_edge
    d[0] = 0

    while True:
        v = -1
        for i in range(max_edge):
            if (not used[i]) and (v == -1):
               v = i
            elif (not used[i]) and d[i] < d[v]:
                v = i
        if v == -1:
               break
        used[v] = True

        for j in range(1,max_edge):
               d[j] = min(d[j],d[v]+cost[v][j])

    d[pos(H-1,W-1)] = 0 if d[pos(H-1,W-1)] == INF else d[pos(H-1,W-1)]
    # print(cost)
    # print(d)
    print(d[pos(H-1,W-1)]+s_e)

if __name__ == "__main__":
  main()

Submission status: Time Limit Exceeded

Solution code:
# -*- coding: utf-8 -*-
H, W = map(int, input().split())
HW_list = []

for i in range(H):
    HW_list.append(str(input()))

def get_min_compress_num(h, w, min_num):
    if h == 0:
        min_num_h = min_num
    else:
        add_min_num_h = 0 if HW_list[h][w] == HW_list[h - 1][w] else 1
        min_num_h = get_min_compress_num(h - 1, w, min_num + add_min_num_h)
    if w == 0:
        min_num_w = min_num
    else:
        add_min_num_w = 0 if HW_list[h][w] == HW_list[h][w - 1] else 1
        min_num_w = get_min_compress_num(h, w - 1, min_num + add_min_num_w)
    return(min(min_num_h, min_num_w))

add_adjust = 1 if HW_list[0][0] == "#" else 0
print(get_min_compress_num(H - 1, W - 1, 0) + add_adjust)

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] 

if C[0][0] == "#": stack = deque([[0,0,1]])
else: stack = deque([[0, 0, 0]])
ans = 10**9

visited_list = [[10**9]*W for _ in range(H)]
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:
            # print(h,w,cnt)
            if ans > cnt:
                ans = cnt
                continue
        for j, k in ([1, 0], [-1, 0], [0, 1], [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 town[new_h][new_w] != "#" and visited_list[new_h][new_w] > cnt:
                visited_list[new_h][new_w] = cnt
                stack.append([new_h, new_w, cnt])
            elif town[new_h][new_w] == "#" and visited_list[new_h][new_w] > cnt + 1:
                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

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

"""
①BFSでゴールまで行けるかを試す
↓行けない
＃の位置を覚えておく（次に探索すべきqueに格納＆1つ目の数字として、1を入れておく。
↓
queの中身が全部行き止まりリストになったら（ソートして判断）、いったんループをやめて、count += 1
行き止まりリストの座標含む近傍の＃を全部.に変える。
↓
queの中身の各リストの1つ目の数字をすべて0に帰る。
↓
①に戻る
"""

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

Submission status: Time Limit Exceeded

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

map=[]

for i in range(hukasa):
    map.append(input())

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

#print(patternTuple)
min=11451419191810

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