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:
from collections import deque
import copy

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


# h x w のマップのリストを整形
t = []
for i in range(h):
    tmp = []
    for j in range(w):
        tmp.append(s[i][j])
    t.append(tmp)


# 現在地とその距離
if s[0][0] == '#':
    q = list([(0,0,1)])
else:
    q = list([(0,0,0)])

# スタートを設定してsをコピー
#t = copy.deepcopy(t_tmp)
#print(t)
tmp_list = []

tmp_min = 1000000
while q:
    #print(q)
    x,y,c = q[0]
    q.pop(0)

    if (x+1, y+2) == (w, h) or (x+2, y+1) == (w, h):
        #print('continue')
        continue
    pass_ = 0
    #if (x+1,y+1) == (h,w):
    #    continue

    for dx, dy in [(1,0),(0,1)]:
        # 壁を超えるか否か
        nx, ny = x+dx, y+dy
        if 0<=nx<h and 0<=ny<w and t[nx][ny] == '.':
            #print(nx, ny)
            #t[nx][ny] = '#'
            q.append((nx,ny,c))
            pass_ = 1
            if (nx+1,ny+2) == (h, w):
                if t[nx][ny+1] == '.':
                    tmp_list.append(c)
                elif t[nx][ny+1] == '#':
                    tmp_list.append(c+1)
            elif (nx+2,ny+1) == (h, w):
                if t[nx+1][ny] == '.':
                    tmp_list.append(c)
                elif t[nx+1][ny] == '#':
                    tmp_list.append(c+1)

    
        elif 0<=nx<h and 0<=ny<w and t[nx][ny] == '#' and pass_ == 0:
            #t[nx][ny] = '#'
            q.append((nx,ny,c+1))
            
            if (nx+1,ny+2) == (h, w):
                if t[nx][ny+1] == '.':
                    tmp_list.append(c+1)
                elif t[nx][ny+1] == '#':
                    tmp_list.append(c+2)

            elif (nx+2,ny+1) == (h, w):
                if t[nx+1][ny] == '.':
                    tmp_list.append(c+1)
                elif t[nx+1][ny] == '#':
                    tmp_list.append(c+2)
    
    q = list(set(q))

#print(tmp_list)

if tmp_list == []:
    print('0')
else:
    print(min(tmp_list))

Submission status: Time Limit Exceeded

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

WALL = '#'
stack = [(0, 0, 0)]
min_cnt = H * W

# BFS
while stack:
    """
    stack取り出す
    調べる
    stack
    """
    y, x, cnt = stack.pop()

    if S[y][x] == WALL:
        cnt += 1

    if (y, x) == (H - 1, W - 1):
        # 0回を見つけたら強制終了
        if cnt == 0:
            min_cnt = 0
            break
        # それ以外は継続
        else:
            min_cnt = cnt

    next_y = y + 1
    next_x = x + 1

    # 打ち切りを入れる
    if min_cnt and min_cnt <= cnt:
        pass
    else:
        if next_y < H and next_x < W:
            # WALLじゃない方を優先して、listの後ろへ入れる
            if S[y][next_x] != WALL and S[next_y][x] == WALL:
                stack.append([next_y, x, cnt])
                stack.append([y, next_x, cnt])
            elif S[y][next_x] == WALL and S[next_y][x] != WALL:
                stack.append([y, next_x, cnt])
                stack.append([next_y, x, cnt])
            else:
                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)

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]

max_ = 0
if int(heigh) > int(wight):
  max_ = int(wight)
else:
  max_ = int(heigh)

result_counts = [max_]
 
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 itertools
import sys
input = sys.stdin.readline
[hukasa,haba]=[int(i)for i in input().split()]

map=[]

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

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
        if min == 0:
            print(min)
            exit()

print(min)

Submission status: Time Limit Exceeded

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

while q:
    qq=[]
    for x,y in q:
        for dx,dy in ((1,0),(0,1)):
            if not(0 <= x+dx < w) or not(0 <= y+dy < h):
                continue
            elif s[y+dy][x+dx] == '#':
                g[y+dy][x+dx]=min(g[y][x]+1,g[y+dy][x+dx])
            else:
                g[y+dy][x+dx]=min(g[y][x],g[y+dy][x+dx])
            qq.append((x+dx,y+dy))
    q=qq

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

Submission status: Time Limit Exceeded

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

def next(cx, cy):
    c = 0
    wx, wy = 0, 0
    if mp[cy - 1][cx - 1] == "#":
        c = 1
    if cx != w:
        wx = next(cx + 1, cy) + c
    if cy != h:
        wy = next(cx, cy + 1) + c

    return c + min(wx, wy)


print(next(1, 1))

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)]
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
#import copy

input = raw_input
h, w = map(int, input().split(" "))
gh = h - 1
gw = w - 1

#dot_coords = []
#for hi in range(h):
#    wi = 0
#    for c in input():
#        if c == ".":
#            dot_coords.append((wi, hi))
#        wi += 1
        
maps = [list(input()) for _ in range(h)]
#num_maps = [[None for _ in range(w)] for _ in range(h)]

full_count = h+w-2
org_downs = [False for _ in range(h+w-2)]

def main(pattern):
    #down_flags = copy.deepcopy(org_downs)
    #for hi in pattern[:h-1]:
    #    down_flags[hi] = True

    cur_count = 0

    x = 0
    y = 0
    ret = 0
    if maps[y][x] == ".":
        batu_count = 0
    else:
        batu_count = 1

    cur_count += 1
    max_done_down = h-1
    down_count = 0
    down_indexs = pattern
    next_down = down_indexs[down_count] 
    for cur_count in range(full_count):
        isdown = False
        if cur_count == next_down:
            isdown = True
            down_count += 1
            if down_count < max_done_down:
                next_down = down_indexs[down_count] 
            else:
                next_down = None

                

        if isdown:
            y += 1
        else:
            x += 1
        #print(y, x)
        if maps[y][x] == ".":
            if batu_count >= 1:
                ret += 1
                batu_count = 0
        else:
            batu_count += 1
        cur_count += 1

    if batu_count >= 1:
        ret += 1
        batu_count = 0
    return ret



patterns = itertools.combinations(range(h+w-2), h-1)
pi = 0
for pattern in patterns:
    ret = main(pattern)
    if pi == 0:
        out = ret
    else:
        out = min(out, ret)
    pi += 1

print(out)

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]=="#":
    changeTo = "."
  elif maze[wallPointH][wallPointW]=="1":
    changeTo = "0"
  if maze[wallPointH][wallPointW]=="#" or maze[wallPointH][wallPointW]=="1":
    maze[wallPointH][wallPointW]=changeTo
    if wallPointH+1 <= H-1:
      removeWalls(wallPointH+1,wallPointW)
    if wallPointW+1 <= W-1:
      removeWalls(wallPointH,wallPointW+1)

if maze[0][0]=="#":
  flag=1
else:
  flag=0
      
que = [[flag,0,0]]
heapq.heapify(que)
count = 0
      
while que:
  qu = heapq.heappop(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の中身にまだ進める場所があるなら
    nowH = qu[1]
    nowW = qu[2]
    if nowH==H-1 and nowW==W-1:#ゴールの場合
      print(count)
      sys.exit()
    else:#それ以外の場合
      #右近傍と下近傍、それぞれマップの中ならqueに格納。
      if nowH+1 <= H-1:
        if maze[nowH+1][nowW]=="#":
          maze[nowH+1][nowW]=="1"
          heapq.heappush(que, [1,nowH+1,nowW])
        elif maze[nowH+1][nowW]==".":
          maze[nowH+1][nowW]=="0"
          heapq.heappush(que, [0,nowH+1,nowW])
      if nowW+1 <= W-1:
        if maze[nowH][nowW+1]=="#":
          maze[nowH][nowW+1]=="1"
          heapq.heappush(que, [1,nowH,nowW+1])
        elif maze[nowH][nowW+1]==".":
          maze[nowH][nowW+1]=="0"
          heapq.heappush(que, [0,nowH,nowW+1])

Submission status: Time Limit Exceeded

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

WALL = '#'
stack = [(0, 0, 0)]
min_cnt = H * W

# BFS
while stack:
    """
    stack取り出す
    調べる
    stack
    """
    sorted(stack, key= lambda x:x[2], reverse=True)
    y, x, cnt = stack.pop()

    if S[y][x] == WALL:
        cnt += 1

    if (y, x) == (H - 1, W - 1):
        # 0回を見つけたら強制終了
        if cnt == 0:
            min_cnt = 0
            break
        # それ以外は継続
        else:
            min_cnt = cnt

    next_y = y + 1
    next_x = x + 1

    # 打ち切りを入れる
    if min_cnt and min_cnt <= cnt:
        pass
    else:
        if next_y < H and next_x < W:
            # WALLじゃない方を優先して、listの後ろへ入れる
            if S[y][next_x] != WALL and S[next_y][x] == WALL:
                stack.append([next_y, x, cnt])
                stack.append([y, next_x, cnt])
            elif S[y][next_x] == WALL and S[next_y][x] != WALL:
                stack.append([y, next_x, cnt])
                stack.append([next_y, x, cnt])
            else:
                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)


#
# def solve(S, y, x, cnt, checked):
#     if ((y, x) == (0, 0)) and (S[0][0] == WALL):
#         cnt = 1
#     checked.append((y, x))
#     # goal
#     if (y, x) == (H - 1, W - 1):
#         print('goal', cnt, checked,sep=' ')
#         cnt_global.append(cnt)
#
#     # 探索
#     for (next_y, next_x) in [(y, x+1), (y+1, x)]:
#         # 範囲内
#         if next_y < H and next_x < W:
#             if S[next_y][next_x] == WALL:
#                 cnt += 1
#
#             route = solve(S, next_y, next_x, cnt, checked)
#             # if route:
#             #     return [cnt] + route
#         # 範囲外
#         else:
#             continue
#
# solve(S, 0, 0, 0, [])
#
# print(cnt_global)
# print(min(cnt_global))
#
# # if S[0][0] == WALL:
# #     hoge += 1

Submission status: Time Limit Exceeded

Solution code:
import math

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



flag=True
que=[]

now=[0,0,0]
result=[]
if maps[0][0]=="#":
    now=[0,0,1]

while flag:


    if now[0]==H-1 and now[1]==W-1:


        result.append(now)
        flag=False
        continue


    if now[0]+1<W:
        if maps[now[0]+1][now[1]]==".":
            que.append([now[0]+1,now[1],now[2]])

        else:
            que.append([now[0]+1,now[1],now[2]+1])

    if now[1]+1<H:
        if maps[now[0]][now[1]+1]==".":

            que.append([now[0],now[1]+1,now[2]])

        else:
            que.append([now[0],now[1]+1,now[2]+1])

    if not que:
        flag=False
        continue
    que.sort(key=lambda x:x[2],reverse=True)

    now=que.pop()
print(result[0][2])

Submission status: Time Limit Exceeded

Solution code:
#from collections import deque

H, W = map(int, input().split())
leng = 0
mapList=[] #appendのために宣言が必要
while True:
    try:
        mapList.append(input())
        leng+=1
    except:
        break;
        #または、quit(),os.exit()をして止める。
row = len(mapList[0])

mapNum = []
temp = []
for i in range(leng):
  for j in range(row):
    if(mapList[i][j] == '.'):
      temp.append(0)
    elif(mapList[i][j] == '#'):
      temp.append(1)
    #print(mapNum[i][j])
  mapNum.append(temp)
  #print(mapNum[i])
  temp=[]
#print(mapNum)

score = [9999]
maze = []
h = H - 1
w = W - 1

def bfs(map, p, q, count):
  count += map[p][q]
  if(count>=max(score)):
    return
  if(p == h and q == w):
    maze.append([p, q])
    score.append(count)
    return
  
  elif(p == h or p == leng):
    bfs(map, p, q+1, count)
  elif(q == w or q == row):
    bfs(map, p+1, q, count)
  else:
    bfs(map, p, q+1, count)
    bfs(map, p+1, q, count)
  return
#visited[sy][sx] = 0
  

     

#maze = [input() for i in range(R)]
point = [[0]*row for j in range(leng)]
bfs(mapNum, 0, 0, 0)

print(min(score))
#print(ind)
#print(maze[ind])

Submission status: Time Limit Exceeded

Solution code:
import math

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



flag=True
que=[]

now=[0,0,0]
result=[]
first=True
num=0
if maps[0][0]=="#":
    now=[0,0,1]

while flag:


    if now[0]==H-1 and now[1]==W-1:


        result.append(now)
        if first:
            num=now[2]
            first=False

        if now[2]<num:
            num=now[2]




        if not que:
            flag=False
            continue
        else:
            now=que.pop(0)


    if now[0]+1<W:
        if maps[now[0]+1][now[1]]==".":
            que.append([now[0]+1,now[1],now[2]])

        else:
            que.append([now[0]+1,now[1],now[2]+1])

    if now[1]+1<H:
        if maps[now[0]][now[1]+1]==".":

            que.append([now[0],now[1]+1,now[2]])

        else:
            que.append([now[0],now[1]+1,now[2]+1])

    if not que:
        flag=False
        continue
    que.sort(key=lambda x:x[2])
    now=que.pop(0)

print(num)

Submission status: Time Limit Exceeded

Solution code:
from collections import deque

#スタート位置、ゴール位置の指定がある場合
def bfs(n):
    #移動距離　最小値に更新していく
    d = [[float("inf")] * C for _ in range(R)]

    dx = [1,0]
    dy = [0,1]
    que = deque([])
    que.append((sy, sx))
    if maze[sy][sx] == ".":
        d[sy][sx] = 0
    else:
        d[sy][sx] = 1
 

    while que:
        p = que.popleft()
        if p[0] == gy and p[1] == gx:
            continue

        for i in range(2):
            nx = p[1] + dx[i]
            ny = p[0] + dy[i]

            if 0<=nx<C and 0<=ny<R:
                #全周を超えない
                if maze[p[0]][p[1]] != maze[ny][nx] and maze[p[0]][p[1]] == ".":
                    d[ny][nx] = min(d[ny][nx], d[p[0]][p[1]] + 1)
                    if d[ny][nx] <= n:
                        que.append((ny, nx))
                else:
                    d[ny][nx] = min(d[ny][nx], d[p[0]][p[1]])
                    if d[ny][nx] <= n:
                        que.append((ny, nx))
    
    if d[gy][gx] == float("inf"):
        return False
    else:
        return d[gy][gx]
   

R,C = map(int,input().split())
sy, sx = 0,0
gy, gx = R-1,C-1

maze = [list(input()) for _ in range(R)]

ans = 10**3
judge = bfs(10**2 + 1)
if judge != False:
    ans = judge
if ans != 10**3:
    print(judge)
else:
    print(0)

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]

max_ = 0
if int(heigh) > int(wight):
  max_ = int(heigh)
else:
  max_ = int(wight)

result_counts = [max_]
 
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:
#A
from collections import deque
h, w = map(int, input().split())
s=[]
for i in range(h):
    s.append(list(input()))
#下　右
dx = [0, 1]
dy = [1, 0]
ans=0
def seath(i, j):
    a = []
    for d in range(2):  # 2方向
        ans=0
        nx = i + dx[d]
        ny = j + dy[d]
        if nx>= w or ny >= h:#マスの外
            continue
        if s[ny][nx] == '#':#壁の中
            ans += 1
        if ny == h - 1 and nx == w - 1:
            return ans
        a.append(seath(nx, ny) + ans)

    return min(a)

if s[0][0] == '#':
    an = 1
else:
    an = 0
an += seath(0, 0)
print(an)

Submission status: Time Limit Exceeded

Solution code:
#from collections import deque

H, W = map(int, input().split())
leng = 0
mapList=[] #appendのために宣言が必要
while True:
    try:
        mapList.append(input())
        leng+=1
    except:
        break;
        #または、quit(),os.exit()をして止める。
row = len(mapList[0])

mapNum = []
temp = []
for i in range(leng):
  for j in range(row):
    if(mapList[i][j] == '.'):
      temp.append(0)
    elif(mapList[i][j] == '#'):
      temp.append(1)
    #print(mapNum[i][j])
  mapNum.append(temp)
  #print(mapNum[i])
  temp=[]
#print(mapNum)

score = []
maze = []
h = H - 1
w = W - 1

def bfs(map, p, q, count):
  count += map[p][q]
  
  if(p == h and q == w):
    maze.append([p, q])
    score.append(count)
    return
  
  elif(p == h or p == leng):
    bfs(map, p, q+1, count)
  elif(q == w or q == row):
    bfs(map, p+1, q, count)
  else:
    bfs(map, p, q+1, count)
    bfs(map, p+1, q, count)
  return
#visited[sy][sx] = 0
  

     

#maze = [input() for i in range(R)]
point = [[0]*row for j in range(leng)]
bfs(mapNum, 0, 0, 0)

print(min(score))
#print(ind)
#print(maze[ind])

Submission status: Time Limit Exceeded

Solution code:
H,W = map(int, input().split())
maze = []
for i in range(H):
    maze.append(tuple(input()))
#distan = [[200]*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])
distG = 200
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
        elif x+dx[i] == H-1 and y+dy[i] == W-1:
            if p == 1 and maze[x + dx[i]][y + dy[i]] == '#':
                distG = min(d+1, distG)
            else:
                distG = min(d, distG)

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

Submission status: Time Limit Exceeded

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


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 + (g if g < b else b)


print(next(1, 1))

Submission status: Time Limit Exceeded

Solution code:
import numpy as np
direction = [(0, 1), (1, 0)]


def solver():
    h, w = map(int, input().split())
    S = [list(input()) for _ in range(h)]
    S_cnt = [[np.inf for _ in range(w)] for _ in range(h)]
    if S[0][0] == "#":
        S_cnt[0][0] = 1
    else:
        S_cnt[0][0] = 0

    # q = deque([(0, 0)])
    q = [(0, 0)]
    for ch, cw in q:
        # print(ch, cw)
        for mh, mw in direction:
            nh = ch + mh
            nw = cw + mw
            if nh == h or nw == w:
                continue
            q.append((nh, nw))

            cnt = S_cnt[ch][cw]
            if S[nh][nw] == "#":
                cnt = cnt + 1

            if S_cnt[nh][nw] > cnt:
                S_cnt[nh][nw] = cnt

            # print(S_cnt)
    print(S_cnt[h-1][w-1])


if __name__ == '__main__':
    solver()

Submission status: Time Limit Exceeded

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

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:
import sys; sys.setrecursionlimit(2147483647); input = sys.stdin.readline
from math import floor, ceil, sqrt, factorial, log
from collections import Counter, defaultdict, deque
from operator import itemgetter
INF = float('inf'); MOD = 10**9+7
def I(): return int(input())
def MI(): return map(int, input().split())
def LI(): return list(MI())
def LIR(n): return [LI() for i in range(n)]
def IS(): return input().rstrip()

def judge(i, j):
    if i+1 == H and j+1 == W:
        if s[i][j] == '.': return 0
        else: return 1
    elif i+1 == H:
        c = 0
        for j in range(j, W):
            if s[i][j] == '#': c += 1
        return c
    elif j+1 == W:
        c = 0
        for i in range(i, H):
            if s[i][j] == '#': c += 1
        return c
    else:
        if s[i][j] == '.':
            return min(judge(i+1, j), judge(i, j+1))
        else:
            return min(judge(i+1, j)+1, judge(i, j+1)+1)
        '''
        if s[i][j] == '.':
            if s[i+1][j] == '.': return judge(i+1, j)
            elif s[i][j+1] == '.': return judge(i, j+1)
            else: return min(judge(i+1, j)+1, judge(i, j+1)+1)
        else:
            if s[i+1][j] == '.': return judge(i+1, j)
            elif s[i][j+1] == '.': return judge(i, j+1)
            else: return min(judge(i+1, j)+1, judge(i, j+1)+1)
        '''

H, W = MI()
s = [IS() for i in range(H)]
print(judge(0, 0))

Submission status: Time Limit Exceeded

Solution code:
import itertools
import copy

input = raw_input
h, w = map(int, input().split(" "))
gh = h - 1
gw = w - 1

#dot_coords = []
#for hi in range(h):
#    wi = 0
#    for c in input():
#        if c == ".":
#            dot_coords.append((wi, hi))
#        wi += 1
        
maps = [list(input()) for _ in range(h)]
#num_maps = [[None for _ in range(w)] for _ in range(h)]

org_downs = [False for _ in range(h+w-2)]

def main(pattern):
    down_flags = copy.deepcopy(org_downs)
    for hi in pattern[:h-1]:
        down_flags[hi] = True
    #print("down_flags", down_flags)

    cur_count = 0

    x = 0
    y = 0
    ret = 0
    if maps[y][x] == ".":
        batu_count = 0
    else:
        batu_count = 1
    for isdown in down_flags:
        if isdown:
            y += 1
        else:
            x += 1
        #print(y, x)
        if maps[y][x] == ".":
            if batu_count >= 1:
                ret += 1
                batu_count = 0
        else:
            batu_count += 1

    if batu_count >= 1:
        ret += 1
        batu_count = 0
    return ret



patterns = itertools.permutations(range(h+w-2))
pi = 0
for pattern in patterns:
    ret = main(pattern)
    if pi == 0:
        out = ret
    else:
        out = min(out, ret)
    pi += 1

print(out)

Submission status: Time Limit Exceeded

Solution code:
from collections import deque

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


def bfs0(white_cells, black_cells):

    while white_cells:
        h, w = white_cells.popleft()
        if h==0 and w==0 and grid[h][w] == "#":
            black_cells.append((h, w))
            return black_cells

        for dy, dx in ((1, 0), (0, 1)):
            new_h = h + dy
            new_w = w + dx
            if new_h < 0 or H <= new_h or new_w < 0 or W <= new_w:
                continue
            if grid[new_h][new_w] == ".":
                if (new_h, new_w) not in white_cells:
                    white_cells.append((new_h, new_w))
            else:
                if (new_h, new_w) not in black_cells:
                    black_cells.append((new_h, new_w))
            if new_h == H-1 and new_w == W-1:
                if grid[new_h][new_w] == ".":
                    return 1
                else:
                    return 0

    return black_cells


def bfs1(black_cells, white_cells):

    while black_cells:
        h, w = black_cells.popleft()
        for dy, dx in ((1, 0), (0, 1)):
            new_h = h + dy
            new_w = w + dx
            if new_h < 0 or H <= new_h or new_w < 0 or W <= new_w:
                continue
            if grid[new_h][new_w] == "#":
                if (new_h, new_w) not in black_cells:
                    black_cells.append((new_h, new_w))
            else:
                if (new_h, new_w) not in white_cells:
                    white_cells.append((new_h, new_w))
            if new_h == H-1 and new_w == W-1:
                if grid[new_h][new_w] == "#":
                    return 1
                else:
                    return 0

    return white_cells

count = 0
ans = 0

if count == 0:
    white_cells = deque()
    white_cells.append((0, 0))
    black_cells = deque()

while black_cells != 1 and white_cells != 1 and black_cells != 0 and white_cells != 0:
    if count % 2 == 0:
        a = 1
        temp_black_cells = bfs0(white_cells, black_cells)
        black_cells = temp_black_cells
        ans += 1
    else:
        a = 0
        temp_white_cells = bfs1(black_cells, white_cells)
        white_cells = temp_white_cells
    count += 1

if black_cells == 1:
    ans -=1

print(ans)

Submission status: Time Limit Exceeded

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

H, W = map(int, input().split())
field = [list(input()) for _ in range(H)]
next_list = []
now_list = [(-1,0)]
ok = "."
cnt = 0
goal = 0
direction = ((1,0),(0,1))
while goal == 0:
    
    next_list = set()
    for x, y in now_list:
        if x == W-1 and y == H-1:
            goal = 1
            break
        for nx, ny in direction:
            nx += x
            ny += y
            if nx >= W or ny >= H or nx < 0 or ny < 0:
                continue
            if field[ny][nx] == ok:
                next_list.add((nx,ny))
    if goal == 1:
        pass
    elif len(next_list) > 0:
        now_list = list(next_list)
    else:
        if ok == ".":
            cnt += 1
            direction = ((1,0),(0,1),(-1,0),(0,-1))
            ok = "#"
        else:
            direction = ((1,0),(0,1))
            ok = "."

print(cnt)