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())
board=[[0]*W for h in range(H)]
counter=[]
def bw(ch):
    if ch=='.':
        return 0
    elif ch=='#':
        return 1
    else:
        return -1
for h in range(H):
    s=input()
    for w in range(W):
        board[h][w]=bw(s[w])
        
direct=[[1,0],[0,1]]

def onboard(h,w):
    return (h<=H-1) and (w<=W-1)

def goal(h,w):
    return h==H-1 and w==W-1     
      
def search(h,w,c,trace):
    global counter
    if goal(h,w):
        if board[h][w]==1:
            c+=1
        counter+=[c]
    if onboard(h,w):
        if board[h][w]==1:
            c+=1
        for d in direct:
            hh,ww=h+d[0],w+d[1]
            if  onboard(hh,ww):
                trace+=[(hh,ww)]
                search(hh,ww,c,trace)
                try:
                   trace.remove((hh,ww))
                except:
                   pass

search(0,0,0,[(0,0)])
print(min(counter))

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:
#black is 0 and white is 1
def traverse(arr , i , j, ops):
	#print(i,j)
	if i == h and j == w:
		#print("end ", ops)
		return ops
	down = None
	right = None
	if i+1 <= h:
		down = 0
		if arr[i+1][j]:
			down += traverse(arr,i+1,j,ops)
		else: 
			down += traverse(arr,i+1,j,ops+1)
	if j+1 <= w:
		right = 0
		if arr[i][j+1]:
			right += traverse(arr,i,j+1,ops)
		else:
			right += traverse(arr,i,j+1,ops+1)
	if right != None and down != None:
		return(min(right, down))
	else:
		return right if right !=  None else down

h, w  = map(int ,input().split())
h -=1
w-=1
arr = []
#v = [True]*(h+1)
#visited = [v for i in range(w+1)]
for i in range(h+1):
	l = input()
	temp = []
	#print(l)
	for j in l:
		#print(j)
		if j == "#" : 
			temp.append(0)
		elif j == ".": 
			temp.append(1)
	arr.append(temp)
#print(arr)
c = 0
if arr[0][0] == 0:
	c+=1
	arr[0][0] = 1
if arr[h][w] == 0:
	c+=1
	arr[h][w] = 1
_k1=0
_k2=0
_k = traverse(arr , 0 , 0, 0) 
print(c + _k)

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
        #print('nuan')
        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(0)
    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:
from collections import deque
h,w = map(int,input().split())
m = []
count = 0
cl =[]
for i in range(h):
  m.append(list(input()))

def bfs_w(cx,cy,count,cl,gx,gy,flg):
  dx = [0,1]
  dy = [1,0]
  d = deque()
  d.appendleft([cx,cy])
  if flg == 1:
    count += 1
    key = '.'
    flg =0
  else :
    key = '#'
    flg = 1
    
  while d:
    n = d.pop()
    x = n[0]
    y = n[1]

    
    nowhere = 0
    lo = []
    for i in range(2):
      nx = x + dx[i]
      ny = y + dy[i] 

      if(nx == gx and ny == gy and m[ny][nx] != key):
        cl.append(count) 
        break
        
      elif nx < w and ny < h and m[ny][nx] != key:
        d.appendleft([nx,ny])
      
      else:
        nowhere += 1
    if nowhere == 2:
      bfs_w(x,y,count,cl,gx,gy,flg)  

if m[0][0] == '.':
  bfs_w(0,0,count,cl,w-1,h-1,0)
else:
  bfs_w(0,0,count,cl,w-1,h-1,1)
  
print(min(cl))

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):
        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:
            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:
from functools import lru_cache

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:
from collections import deque
INF = int(1e9) + 7
h, w = map(int, input().split())
s = [list(input()) for i in range(h)]
d = [[INF] * w for i in range(h)]
dx = [1,0]
dy = [0,1]
if s[0][0] == '#':
    d[0][0] = 1
else:
    d[0][0] = 0
que = deque([(0, 0)])

while len(que) != 0:
    val = que.popleft()

    for i in range(2):
        nx = val[0] + dx[i]
        ny = (val[1] + dy[i])
        if nx < h and ny < w:

            que.append((nx, ny))
            if (s[nx][ny] == '#') and (d[nx][ny] > d[val[0]][val[1]]):
                d[nx][ny] = d[val[0]][val[1]] + 1
            elif s[nx][ny] != '#' and d[nx][ny] < d[val[0]][val[1]]:
                d[nx][ny] = d[nx][ny]

            else:
                d[nx][ny] = d[val[0]][val[1]]
print(d[h-1][w-1])

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

    n = a[0][0]=='#'
    p.append((0,0,n))


    while(True):
        f = p.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:
                    p.appendleft((x + u, y + v, c + 1))



if __name__=='__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
from collections import deque
import math
import sys

h,w = map(int,input().split())
s = [0] * h
for i in range(h):
     s[i] = [i for i in str(input())]

box=[deque([]) for _ in range(w+h-1)]
box[0].append([0,0])
ans = 0
for i in range(w+h-1):
     while box[i]:
          y,x = box[i].popleft()
          if y == h-1 and x == w-1:
               if s[y][x] == '.' and s[0][0] == '.':
                    print(ans//2)
               elif s[y][x] == '.' and s[0][0] == '#' :
                    print((ans+1)//2)
               elif s[y][x] == '#' and s[0][0] == '.':
                    print((ans + 1) // 2)
               else:
                    print(ans//2 + 1)
               sys.exit()
          for k, j in [(1, 0), (0, 1)]:

               nexty, nextx = y + k, x + j
               if nexty < h and nextx < w:
                    if s[nexty][nextx] == s[y][x]:
                         box[i].append([nexty, nextx])

                    elif s[nexty][nextx] != s[y][x]:
                         box[i+1].append([nexty, nextx])


     ans += 1

Submission status: Time Limit Exceeded

Solution code:
# -*- coding: utf-8 -*-
import itertools


def change(val):
    # 黒なら1
    if val == '#':
        return 1

    # 白なら0
    return 0


# def calc_root(board):


def main():
    h, w = map(int, input().split())
    board = [[change(s) for s in input()] for i in range(h)]

    cnt = 200
    for move in itertools.product(range(0, 2), repeat=h + w - 2):

        if sum(move) != h - 1:
            continue

        x, y = (0, 0)
        temp_root = [(x, y, board[y][x])]
        change_cnt = 0
        if board[y][x] == 1:
            change_cnt += 1

        for hko in move:
            # 0なら横移動
            if hko == 0:
                x += 1
            else:
                y += 1

            # temp_root.append((x, y, board[y][x]))

            if board[y][x] == 1:
                change_cnt += 1

        cnt = min(cnt, change_cnt)

    print(cnt)


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
import itertools
k = input()

heigh, wight = k.split(' ')
heigh, wight = int(heigh), int(wight)

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

for l__ in set(itertools.permutations(l_, len(l_))):
    count = 0
    x, y = 0, 0
    now = list_[heigh - y - 1][x]
    for s in l__:
        if s == 1:
            x = x + 1
        else:
            y = y + 1
        next_ = list_[heigh - y - 1][x]
        if now == '#' and next_== '.':
            count += 1
        if count > max_:
            continue
        if count > min(result_counts):
            continue
        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:
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 == H-1 and new_w == W-1:
                if grid[new_h][new_w] == ".":
                    return 1
                else:
                    return 0
            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))

    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 == H-1 and new_w == W-1:
                if grid[new_h][new_w] == "#":
                    return 1
                else:
                    return 0
            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))

    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
        if black_cells != 1 and white_cells != 1:
            ans += 1
    else:
        a = 0
        temp_white_cells = bfs1(black_cells, white_cells)
        white_cells = temp_white_cells
    count += 1





print(ans)

Submission status: Time Limit Exceeded

Solution code:
def main():
    from collections import deque

    WHITE = 0
    BLACK = 1

    CHAR = '.', '#'

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

    h = deque()
    x = CHAR.index(s[0][0])
    h.append((x, 0, 0, x))

    while h:
        cnt, r, c, mode = h.popleft()
        if r == H - 1 and c == W - 1:
            print(cnt)
            return

        delta = int(mode == WHITE)
        ncnt = cnt + delta

        if r < H - 1:
            if s[r + 1][c] == CHAR[mode]:
                h.appendleft((cnt, r + 1, c, mode))
            else:
                if delta:
                    h.append((ncnt, r + 1, c, 1 - mode))
                else:
                    h.appendleft((ncnt, r + 1, c, 1 - mode))

        if c < W - 1:
            if s[r][c + 1] == CHAR[mode]:
                h.appendleft((cnt, r, c + 1, mode))
            else:
                if delta:
                    h.append((ncnt, r, c + 1, 1 - mode))
                else:
                    h.appendleft((ncnt, r, c + 1, 1 - mode))


if __name__ == '__main__':
    main()

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

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
for i in range(10**2 + 1):
    judge = bfs(i)
    if judge != False:
        ans = judge
        break
if ans != 10**3:
    print(judge)
else:
    print(0)

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):
        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:
            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:
h, w = list(map(int, input().split(" ")))
matrix = []
result = []
r_0 = ""
c_0 = ""
r_1 = ""
c_1 = ""

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

  if matrix[x][y] == "#":
    if result and min(result) < count:
      return
    count += 1
    if r_0 == "" and c_0 == "" and r_1 == 0 and c_1 == 0:
      r_0 = x
      c_0 = y
      r_1 = x
      c_1 = y
    elif r_0 != "" and c_0 != "":
      r_1 = x
      c_1 = y
      if (r_1 - r_0) != (c_1 - c_0):
        return
      if (c_0 - r_0) != (c_1 - r_1):
        return 
  if x == (w - 1) and y == (h - 1):
    result.append(count)
  check(x+1, y, count, r_0, c_0, r_1, c_1)
  check(x, y+1, count, r_0, c_0, r_1, c_1)

check(0, 0, 0, r_0, c_0, r_1, c_1)
min_result = min(result) if result else 0
print(min_result)

Submission status: Time Limit Exceeded

Solution code:
# import numpy as np

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

def to_num(input_str):
    if input_str == '.':
        return 0
    else:
        return 1

matrix = []
for i in range(h):
    matrix.append(list(map(to_num, list(input()))))

# matrix = np.array(matrix)

def check_right_down(check_list):
    #print(check_list)
    #if check_list.shape[0] == 1 or check_list.shape[1] == 1:
    if len(check_list[0]) == 1 or len(check_list) == 1:
        #return np.sum(check_list)
        #print(sum(check_list[0]))
        return sum(map(sum, check_list))
    else:
        #print(check_list[1:])
        #print([l[1:] for l in check_list])
        #print(check_list)
        #print(check_list[0][0])
        return min(check_right_down(check_list[1:]), check_right_down([l[1:] for l in check_list])) + check_list[0][0]

print(check_right_down(matrix))

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

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 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):
	
	if (row0,col0) in usedRC0: return None
	usedRC0.add((row0,col0))
# 	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
		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]=="."


# 	h=20
# 	w=20
# 	np.random.seed(0)
# 	colors=np.random.randint(0,2,(h,w))
# 	from matplotlib import pyplot as plt
# 	plt.imshow(colors)
# 	plt.show()
			
# 	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:
h, w = list(map(int, input().split(" ")))
matrix = []
result = []
r_0 = ""
c_0 = ""
r_1 = ""
c_1 = ""

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

  if matrix[x][y] == "#":
    if result and min(result) < count:
      return
    count += 1
    if r_0 == "" and c_0 == "" and r_1 == 0 and c_1 == 0:
      r_0 = x
      c_0 = y
      r_1 = x
      c_1 = y
    elif r_0 != "" and c_0 != "":
      r_1 = x
      c_1 = y
      if (r_1 - r_0) == (c_1 - c_0):
        return
      if (c_0 - r_0) == (c_1 - r_1):
        return 
  if x == (w - 1) and y == (h - 1):
    result.append(count)
  check(x+1, y, count, r_0, c_0, r_1, c_1)
  check(x, y+1, count, r_0, c_0, r_1, c_1)

check(0, 0, 0, r_0, c_0, r_1, c_1)
min_result = min(result) if result else 0
print(min_result)

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 == H-1 and new_w == W-1:
                if grid[new_h][new_w] == ".":
                    return 1
                else:
                    return 0
            if new_h < 0 or H <= new_h or new_w < 0 or W <= new_w:
                continue
            if grid[new_h][new_w] == ".":
                white_cells.append((new_h, new_w))
            else:
                if (new_h, new_w) not in black_cells:
                    black_cells.append((new_h, new_w))

    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 == H-1 and new_w == W-1:
                if grid[new_h][new_w] == "#":
                    return 1
                else:
                    return 0
            if new_h < 0 or H <= new_h or new_w < 0 or W <= new_w:
                continue
            if grid[new_h][new_w] == "#":
                black_cells.append((new_h, new_w))
            else:
                if (new_h, new_w) not in white_cells:
                    white_cells.append((new_h, new_w))

    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
        if black_cells != 1 and white_cells != 1:
            ans += 1
    else:
        a = 0
        temp_white_cells = bfs1(black_cells, white_cells)
        white_cells = temp_white_cells
    count += 1

print(ans)

Submission status: Time Limit Exceeded

Solution code:
def main():
    from heapq import heappush, heappop

    WHITE = 0
    BLACK = 1

    CHAR = '.', '#'

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

    h = []
    x = CHAR.index(s[0][0])
    heappush(h, (x, 0, 0, x))

    while h:
        cnt, r, c, mode = heappop(h)
        if r == H - 1 and c == W - 1:
            print(cnt)
            return

        if r < H - 1:
            if s[r + 1][c] == CHAR[mode]:
                heappush(h, (cnt, r + 1, c, mode))
            else:
                heappush(h, (cnt + int(mode == WHITE), r + 1, c, 1 - mode))

        if c < W - 1:
            if s[r][c + 1] == CHAR[mode]:
                heappush(h, (cnt, r, c + 1, mode))
            else:
                heappush(h, (cnt + int(mode == WHITE), r, c + 1, 1 - mode))


if __name__ == '__main__':
    main()

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

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
dist={}
queue=set()
dist[(0,0)]=0
queue.add((0,0))
for i in range(1,H+1):
  for j in range(1,W+1):
    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 dist[q]<d:
      min_q=q
      d=dist[q]
      
  #print(min_q,d)
  if min_q==None:
    break
    
  queue.remove(min_q)
  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)])