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 *
H,W=map(int,input().split())
S=[input() for i in range(H)]
count=0
stack=deque([[0,0,0,S[0][0]=="#"]])
RuiW=[[0] for i in range(H)]
RuiH=[[0] for i in range(W)]
if S[0][0]=="#":
    RuiW[0][0]=1
    RuiH[0][0]=1

for h in range(H):
    flag=0
    for w in range(1,W):
        RuiW[h].append(RuiW[h][-1]+bool(S[h][w]=="#" and S[h][w-1]=="."))
for w in range(W):
    for h in range(1,H):
        RuiH[w].append(RuiH[w][-1]+bool(S[h][w]=="#" and S[h-1][w]=="."))

Range=range(1,100)
idle_max=10**9
visited=[[idle_max for i in range(W)] for m in range(H)]
#print(RuiW)
#print(RuiH)
while stack:
    h,w,m,Flag=stack.popleft()
    for i in Range:
        if h+i>=H:
            break
        M=RuiH[w][h+i]-(RuiH[w][h]-RuiH[w][h]%2)+m

        if visited[h+i][w]>M:
            visited[h+i][w]=M
            stack.append([h+i,w,M,0])
    for i in Range:
        if w+i>=W:
            break
        M=RuiW[h][w+i]-(RuiW[h][w]-RuiW[h][w]%2)+m
        if visited[h][w+i]>M:
            visited[h][w+i]=M
            stack.append([h,w+i,M,0])
#print(visited)
print(visited[-1][-1])

Submission status: Time Limit Exceeded

Solution code:
def calc_count(s):
  return s.count('#')

def rec_memo(i, j, c):
  global h,w,last_raw
  if i < h and j < w and maze[i][j] == "#":
    c += 1
    
  if i == h-1 and j < w:
    res = calc_count(last_raw[j:]) + c
  elif j == w-1 and i < h:
    res = calc_count(last_col[i:]) + c
  elif i < h and j < w:
    res = min(rec_memo(i+1, j, c), rec_memo(i, j+1, c))

  return res

"""
  if i == h-1 and j == w-1:
    res = c
  elif i == h-1 and j < w:
    res = rec_memo(i, j+1, c)
  elif j == w-1 and i < h:
    res = rec_memo(i+1, j, c)
  elif i < h and j < w:
    res = min(rec_memo(i+1, j, c), rec_memo(i, j+1, c))
  return res
"""

h, w = map(int, input().split())
#print(h)
#print(w)
maze = [list(input()) for i in range(h)]
#print(maze)
last_raw = maze[h-1]
temp = []
for i in range(h):
  temp.append(maze[i][w-1])

last_col = "".join(temp)

print(rec_memo(0, 0, 0))

Submission status: Time Limit Exceeded

Solution code:
from decimal import *
from heapq import heappush, heappop, heapify
from collections import deque, defaultdict, Counter
import itertools
from itertools import permutations, combinations, accumulate
import sys
import bisect
import string
import math
import time


def I(): return int(input())


def S(): return input()


def MI(): return map(int, input().split())


def MS(): return map(str, input().split())


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


def LI_(): return [int(i)-1 for i in input().split()]


def StoI(): return [ord(i)-97 for i in input()]


def ItoS(nn): return chr(nn+97)


def input(): return sys.stdin.readline().rstrip()


def show(*inp, end='\n'):
    if show_flg:
        print(*inp, end=end)


YNL = {False: 'No', True: 'Yes'}
YNU = {False: 'NO', True: 'YES'}
MOD = 10**9+7
inf = float('inf')
IINF = 10**10
l_alp = string.ascii_lowercase
u_alp = string.ascii_uppercase
ts = time.time()
sys.setrecursionlimit(10**6)
nums = ['1', '2', '3', '4', '5', '6', '7', '8', '9', '10']

show_flg = False
# show_flg = True

BLOCK = '#'
ROAD = '.'


def print_matrix(mat):
    for i in range(len(mat)):
        print(*mat[i])


def bfs(graph, initial, goal, H, W):
    options = [(1, 0), (0, 1)]
    q = deque([initial])
    dist = [[10**9 for i in range(W)] for i in range(H)]
    dist[initial[0]][initial[1]] = 0 if graph[initial[0]][initial[1]] == ROAD else 1

    while len(q) != 0:
        p = q.popleft()

        for d in options:
            i = p[0] + d[0]
            j = p[1] + d[1]

            if i >= 0 and i < H and j >= 0 and j < W:
                if graph[i][j] == BLOCK:
                    dist[i][j] = min(dist[i][j], dist[p[0]][p[1]] + 1)
                else:
                    dist[i][j] = min(dist[p[0]][p[1]], dist[i][j])
                q.append((i, j))

    # print_matrix(dist)
    return dist[goal[0]][goal[1]]


def main():
    H, W = MI()
    graph = [None] * H

    for i in range(H):
        graph[i] = list(S())

        for j in range(W):
            if graph[i][j] == 'S':
                pass

    ret = bfs(graph, (0, 0), (H-1, W-1), H, W)
    print(ret)


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
def rec_memo(i, j, c):
  global h,w  
  if i < h and j < w and maze[i][j] == "#":
    c += 1

  if i == h-1 and j == w-1:
    res = c
  elif i == h-1 and j < w:
    res = rec_memo(i, j+1, c)
  elif j == w-1 and i < h:
    res = rec_memo(i+1, j, c)
  elif i < h and j < w:
    res = min(rec_memo(i+1, j, c), rec_memo(i, j+1, c))
  
  return res

h, w = map(int, input().split())
#print(h)
#print(w)
maze = [list(input()) for i in range(h)]
#print(maze)

print(rec_memo(0, 0, 0))

Submission status: Time Limit Exceeded

Solution code:
from sys import stdin, setrecursionlimit
from collections import deque

setrecursionlimit(10 ** 9)

H, W = map(int, stdin.readline().split())
field = [list(stdin.readline().rstrip()) for _ in range(H)]

inf = 10 ** 9

flip_cnt = [[inf] * W for _ in range(H)]
direction = [[0, 1], [1, 0]]

q = deque([])


def bfs(h, w):
    q.append([h, w])

    while q:

        h, w = q.popleft()

        for dh, dw in direction:
            nh = h + dh
            nw = w + dw

            if nh >= H or nw >= W:
                continue

            q.append([nh, nw])

            if field[nh][nw] == field[h][w]:
                flip_cnt[nh][nw] = min(flip_cnt[nh][nw], flip_cnt[h][w])
            else:
                flip_cnt[nh][nw] = min(flip_cnt[nh][nw], flip_cnt[h][w] + 1)


flip_cnt[0][0] = 0
bfs(0, 0)

if field[0][0] == field[H - 1][W - 1] == "#":
    flip_cnt[H - 1][W - 1] += 1

print((flip_cnt[H - 1][W - 1] + 1) // 2)

# for f in flip_cnt:
#     print(f)

Submission status: Time Limit Exceeded

Solution code:
from collections import deque
h, w =  map(int, input().split())
s = [[i for i in list(str(input()))] for i in range(h)]
INF = 10**9
dp = [[INF for _ in range(w)] for _ in range(h)]

if s[0][0] == "#":
    dp[0][0] = 1
else:
    dp[0][0] = 0

que = deque()
que.append((0, 0))
while len(que) > 0:
    y, x = que.popleft()
    if y + 1 < h:
        if s[y+1][x] == "#":
            dp[y+1][x] = min(dp[y+1][x], dp[y][x]+1)
        else:
            dp[y+1][x] = min(dp[y+1][x], dp[y][x])
        que.append((y+1, x))
    if x + 1 < w:
        if s[y][x+1] == "#":
            dp[y][x+1] = min(dp[y][x+1], dp[y][x]+1)
        else:
            dp[y][x+1] = min(dp[y][x+1], dp[y][x])
        que.append((y, x+1))
print(dp[h-1][w-1])

Submission status: Time Limit Exceeded

Solution code:
import sys

H, W = list(map(int, input().split()))
Z = []

for i in range(H):
    Z += list(map(str, input().split()))

# 右下パターン網羅し、リスト化
#a = []

h = H - 1 
w = W - 1
tmp = h + w
# for で列を回し、一番小さいパターンを設定

flag2 = 10**10
Y = ""
def dfs(x, y, Y):
    global flag2
    flag = 0
    if x >= W:
        return False
    if y >= H:
        return False
    if flag2 <= Y.count('#'):
        return False
    t = x + y
    if t == tmp:
        Y += Z[y][x]
        flag = Y.count('#')
        if flag2 > flag:
            flag2 = flag
        return False
    if dfs(x+1, y, Y + Z[y][x]):
        return True
    if dfs(x, y+1, Y + Z[y][x]):
        return True
    return False

dfs(0, 0, Y)
print(flag2)

Submission status: Time Limit Exceeded

Solution code:
# Author: cr4zjh0bp
# Created: Fri Mar 20 22:48:43 UTC 2020
import sys
 
stdin = sys.stdin
inf = 1 << 60
mod = 1000000007
 
ni      = lambda: int(ns())
nin     = lambda y: [ni() for _ in range(y)]
na      = lambda: list(map(int, stdin.readline().split()))
nan     = lambda y: [na() for _ in range(y)]
nf      = lambda: float(ns())
nfn     = lambda y: [nf() for _ in range(y)]
nfa     = lambda: list(map(float, stdin.readline().split()))
nfan    = lambda y: [nfa() for _ in range(y)]
ns      = lambda: stdin.readline().rstrip()
nsn     = lambda y: [ns() for _ in range(y)]
ncl     = lambda y: [list(ns()) for _ in range(y)]
nas     = lambda: stdin.readline().split()

from collections import deque

h, w = na()
m = nsn(h)

def bfs():
    q = deque()
    al = 0
    f = False
    if m[0][0] == '#':
        al += 1
        f = True
    q.append((0, 0, al, f))
    d = [[inf] * w for _ in range(h)]
    res = inf
    dx, dy = [0, 1], [1, 0]
    while len(q):
        p = q.popleft()
        x, y, l, flag = p
        for i in range(2):
            nx, ny = x + dx[i], y + dy[i]
            if nx >= 0 and nx < w and ny >= 0 and ny < h:
                nl = l
                if m[ny][nx] == '#':
                    if not flag:
                        nl += 1
                    q.append((nx, ny, nl, True))
                else:
                    q.append((nx, ny, nl, False))
                d[ny][nx] = min(d[ny][nx], nl)
    return d[h - 1][w - 1]

print(bfs())

Submission status: Time Limit Exceeded

Solution code:
import copy
from collections import deque


def bfs(s1,s2):
    que = deque()
    que.append([0, 0])
    cs = copy.deepcopy(s)
    if cs[s1][s2] == '#':
        cs[s1][s2] = 1
    else:
        cs[s1][s2] = 0
    while len(que) != 0:
        p = que.popleft()
        for i in range(2):
            nextX = p[0] + moveR[i]
            nextY = p[1] + moveC[i]
            if 0 <= nextX and nextX < H\
                and 0 <= nextY and nextY < W:
                if cs[nextX][nextY] == '#':
                    cs[nextX][nextY] = cs[p[0]][p[1]] + 1
                elif cs[nextX][nextY] == '.':
                    cs[nextX][nextY] = cs[p[0]][p[1]]
                else:
                    tmp = 0
                    if s[nextX][nextY] == '#':
                        tmp = 1
                    cs[nextX][nextY] = min(cs[p[0]][p[1]] + tmp, cs[nextX][nextY])
                que.append([nextX, nextY])
    print(cs[-1][-1])

H, W = map(int, input().split())
s = [list(input()) for _ in range(H)]
ans = 10 ** 9
moveR = [0, 1]
moveC = [1, 0]
bfs(0,0)

Submission status: Time Limit Exceeded

Solution code:
import sys

H, W = list(map(int, input().split()))
Z = []

for i in range(H):
    Z += list(map(str, input().split()))

# 右下パターン網羅し、リスト化
#a = []

h = H - 1 
w = W - 1
tmp = h + w
# for で列を回し、一番小さいパターンを設定

flag2 = 0
Y = ""
def dfs(x, y, Y):
    global flag2
    flag = 0
    if x >= W:
        return False
    if y >= H:
        return False
    t = x + y
    if t == tmp:
        Y += Z[y][x]
        flag = Y.count('.')
        if flag2 < flag:
            flag2 = flag
        return False
    if dfs(x+1, y, Y + Z[y][x]):
        return True
    if dfs(x, y+1, Y + Z[y][x]):
        return True
    return False

dfs(0, 0, Y)
flag2 = H + W - 1 - flag2
print(flag2)

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 < w and ny < h:

            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:
import queue
H,W = map(int,input().split())

start_point = [0,0]
goal_point = [H,W]
graph = [list(input()) for _ in range(H)]
# print(graph)
# graph = []
# for i in range(H):
#     graph.append(input())
#100000000
dist = [[0 for _ in range(W)] for _ in range(H)]
not_visit = [[False for _ in range(W)] for _ in range(H)]
dx = [1,0]
dy = [0,1]
q = queue.Queue()
q.put([start_point[0],start_point[1]])
# print(q.get())
if graph[0][0] == "#":
    dist[0][0] = 1


# def DFS(graph,start_point,goal_point):
#     not_visited = []
#     not_visited=[[True for i in range(W)] for j in range(H)]
#     stack = [start_point]#1.始点のノードを探索待ちスタックに追加


#     not_visited[start_point[0]][start_point[1]] = False
#     while len(stack) != 0:#2.探索待ちスタックにノードが無ければ終了
#           now_point = stack.pop()#2.探索待ちスタックにノードがあれば取り出す
#         #   print(now_point)
#           for i in range(2):
#                 if now_point[0]+1 == goal_point[0] and now_point[1]+1 == goal_point[1]:#3.取り出したノードが目的のノードであれば探索終了
#                     print(0)
#                     return False
#                 else:
#                     serch_point = [now_point[0]+dx[i],now_point[1]+dy[i]]#4.取り出したノードに隣接するノード
#                     if 0 <= serch_point[0] < H and 0 <= serch_point[1] < W:#4.隣接するノードが迷路の範囲内かどうか判定
#                         if graph[serch_point[0]][serch_point[1]] != "#" and not_visited[serch_point[0]][serch_point[1]]:#4.未探索のノードを探索待ちスタックに追加
#                             stack.append([serch_point[0],serch_point[1]])
#                             not_visited[serch_point[0]][serch_point[1]] = False
#     return True
# if DFS(graph, start_point, goal_point):
while not q.empty():
    v = q.get()
    h,w = v[0],v[1]
    # print(v)
    for i in range(2):
        nh = h + dx[i]
        nw = w + dy[i]
        # print(dist)
        # print("{},{}".format(nh,nw))
        if nh < 0 or nh >= H or nw < 0 or nw >= W:
            continue
        # if dist[nh][nw] != -1:#探索済みか判定
            # continue
        # print(graph[nh][nw])
        if graph[nh][nw] == "#":
            if not_visit[nh][nw]:
                dist[nh][nw] = min(dist[nh][nw],dist[h][w]+1)
            else:
                dist[nh][nw] = dist[h][w]+1
                not_visit[nh][nw] = True
        else:
            # dist[nh][nw] = min(dist[h][w],dist[nh][nw])
            if not_visit[nh][nw]:
                dist[nh][nw] = min(dist[h][w],dist[nh][nw])
            else:
                not_visit[nh][nw] = True
                dist[nh][nw] = dist[h][w]
        # print(dist)
        # print(dist[h][w])
        
        q.put([nh,nw])
print(dist[W-1][H-1])

Submission status: Time Limit Exceeded

Solution code:
import sys

H, W = list(map(int, input().split()))
Z = []

for i in range(H):
    Z += list(map(str, input().split()))

# 右下パターン網羅し、リスト化
#a = []

h = H - 1 
w = W - 1
tmp = h + w
# for で列を回し、一番小さいパターンを設定

X = []
Y = ""
def dfs(x, y, Y):
    global X
    if x >= W:
        return False
    if y >= H:
        return False
    t = x + y
    if t == tmp:
        Y += Z[y][x]
        X.append(Y)
        return False
    if dfs(x+1, y, Y + Z[y][x]):
        return True
    if dfs(x, y+1, Y + Z[y][x]):
        return True
    return False

dfs(0, 0, Y)

flag2 = 0
for a in X:
    flag = 0
    flag = a.count('.')
    if flag2 < flag:
        flag2 = flag
flag2 = H + W - 1 - flag2
print(flag2)

Submission status: Time Limit Exceeded

Solution code:
import sys

H, W = list(map(int, input().split()))
Z = []

for i in range(H):
    Z += list(map(str, input().split()))

# 右下パターン網羅し、リスト化
#a = []

h = H - 1 
w = W - 1
tmp = h + w
# for で列を回し、一番小さいパターンを設定

X = []
Y = ""
def dfs(x, y, Y):
    global X
    if x >= W:
        return False
    if y >= H:
        return False
    t = x + y
    if t == tmp:
        Y += Z[y][x]
        X.append(Y)
        return False
    if dfs(x+1, y, Y + Z[y][x]):
        return True
    if dfs(x, y+1, Y + Z[y][x]):
        return True
    return False

dfs(0, 0, Y)

flag2 = 0
for a in X:
    flag = 0
    for b in a:
        if b == '.':
            flag += 1
    if flag2 < flag:
        flag2 = flag
flag2 = H + W - 1 - flag2
print(flag2)

Submission status: Time Limit Exceeded

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

ans=float("inf")
def dfs(px,py,sw):
  global ans
  if px==W-1 and py==H-1:
    ans=min(ans,sw)
  else:
    if px==W-1:
      if S[py+1][px]=="." and S[py][px]=="#":
        dfs(px,py+1,sw+1)
      else:
        dfs(px,py+1,sw)
    elif py==H-1:
      if S[py][px+1]=="." and S[py][px]=="#":
        dfs(px+1,py,sw+1)
      else:
        dfs(px+1,py,sw)
    else:
      if S[py+1][px]=="." and S[py][px]=="#":
        dfs(px,py+1,sw+1)
      else:
        dfs(px,py+1,sw)
      if S[py][px+1]=="." and S[py][px]=="#":
        dfs(px+1,py,sw+1)
      else:
        dfs(px+1,py,sw)

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

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]
count=0
if maps[0][0]=="#":
    count+=1



nummin=0
first=True
while flag:



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

        if first:
            nummin=now[2]
            first=False
        if now[2]<nummin:
            nummin=now[2]


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





    if now[0]+1<H:
        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<W:
        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


    now=que.pop()

print(nummin+count)

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]
count=0
if maps[0][0]=="#":
    count+=1



nummin=0
first=True
while flag:
    


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

        if first:
            nummin=now[2]
            first=False
        if now[2]<nummin:
            nummin=now[2]


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





    if now[0]+1<H:
        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<W:
        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


    now=que.pop()

print(nummin+count)

Submission status: Time Limit Exceeded

Solution code:
import sys
import re
import heapq


# グラフの初期化
def initialize_graph(node_list_x_name, node_list_y_name, score_list):
    graph = {}
    for node1, node2, cost in zip(node_list_x_name, node_list_y_name, score_list):
        graph = set_new_node(graph, node1, node2)
        graph[node1][node2] = int(cost)
        # graph[node2][node1] = int(cost)
    return graph


def set_new_node(graph, node1, node2):
    if not node1 in graph.keys():
        graph[node1] = {}
    if not node2 in graph.keys():
        graph[node2] = {}
    return graph


# ダイクストラ法によって最短経路問題を解く
def solve_by_dijkstra(graph, W, H):
    # ノード毎のSTARTからの最小コスト
    min_dist_dict = {}
    # ノードに最小コストで辿り着く場合の直前のノード
    prev_node_dict = {}
    q = []
    heapq.heappush(q, (0, '0_0'))

    prev_node = ''

    while True:
        # 確定したノードから遷移可能なノードのうち
        # 最小のコストと遷移先ノードをmin_dist_dictとprev_node_dictに設定
        dist, node = heapq.heappop(q)
        min_dist_dict[node] = dist
        prev_node_dict[node] = prev_node
        # もしGOALノードの最小コストが確定したらループを抜ける
        if node == (str(H - 1) + '_' + str(W - 1)):
            return min_dist_dict, prev_node_dict
        prev_node = node
        # 確定したノードから遷移可能なノードについて
        # コストを計算し，キュー(q)に追加する
        culc_min_dist_and_put(graph, q, node, min_dist_dict, prev_node_dict)


def culc_min_dist_and_put(graph, q, departure_node, min_dist_dict, prev_node_dict):
    # 直前に確定したノードから遷移可能なすべてのノードについて繰り返し
    for arrival_node in graph[departure_node].keys():
        # 遷移可能なノードについて，直前に確定したノードから遷移した場合のコストを計算
        tmp_d = min_dist_dict[departure_node] + graph[departure_node][arrival_node]
        # 過去に遷移先ノードの最小コストを計算済みかどうか
        if arrival_node in min_dist_dict.keys():
            # 過去に計算していたSTARTからの最小コストより直前に確定したノードから遷移した場合の
            # コストが小さかった場合，最小コストを更新
            if tmp_d < min_dist_dict[arrival_node]:
                min_dist_dict[arrival_node] = tmp_d
                heapq.heappush(q, (min_dist_dict[arrival_node], arrival_node))
        else:
            min_dist_dict[arrival_node] = tmp_d
            heapq.heappush(q, (min_dist_dict[arrival_node], arrival_node))


def main():
    H, W = map(int, input().split())
    s = [None] * H
    for i in range(H):
        s[i] = input()

    node_list_x1 = [[i, j] for i in range(H - 1) for j in range(W - 1)]
    node_list_x2 = [[H - 1, i] for i in range(W - 1)]
    node_list_x3 = [[i, W - 1] for i in range(H - 1)]

    node_list_y1 = [[i, j + 1] for i in range(H - 1) for j in range(W - 1)]
    node_list_y2 = [[i + 1, j] for i in range(H - 1) for j in range(W - 1)]
    node_list_y3 = [[H - 1, i + 1] for i in range(W - 1)]
    node_list_y4 = [[i + 1, W - 1] for i in range(H - 1)]

    node_list_x = node_list_x1 * 2 + node_list_x2 + node_list_x3
    node_list_y = node_list_y1 + node_list_y2 + node_list_y3 + node_list_y4

    score_list = [int((s[x[0]][x[1]] == '.') and (s[y[0]][y[1]] == '#'))
                  for x, y in zip(node_list_x, node_list_y)]
    # score_list = []
    # for x, y in zip(node_list_x, node_list_y):
    #     if (s[x[0]][x[1]] == '.') and (s[y[0]][y[1]] == '#'):
    #         score_list.append(1)
    #     else:
    #         score_list.append(0)

    node_list_x_name = [str(x[0]) + '_' + str(x[1]) for x in node_list_x]
    node_list_y_name = [str(y[0]) + '_' + str(y[1]) for y in node_list_y]

    graph = initialize_graph(node_list_x_name, node_list_y_name, score_list)
    min_dist_dict, prev_node_dict = solve_by_dijkstra(graph, W, H)
    # GOALノードからprev_node_dictをたどって経路を復元
    # print('Route : H_W ', end='')
    node = (str(H - 1) + '_' + str(W - 1))
    while True:
        if node == '0_0':
            print()
            break
        # print(' ← ' + prev_node_dict[node], end='')
        node = prev_node_dict[node]

    if s[0][0] == '#':
        print(str(min_dist_dict[(str(H - 1) + '_' + str(W - 1))]+1))
    else:
        print(str(min_dist_dict[(str(H - 1) + '_' + str(W - 1))]))


if __name__ == '__main__':
    main()
    sys.exit(0)

Submission status: Time Limit Exceeded

Solution code:
from collections import deque
import copy

h,w = map(int, input().split())
t = []
for i in range(h):
    t.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 t[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)
    if (q[0][0]+1, q[0][1]+2) == (w, h) or (q[0][0]+2, q[0][1]+1) == (w, h):
        q.pop(0)
        continue
    else:
        x,y,c = q[0]
        q.pop(0)

    
        #print('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] == '.':
                    if tmp_min > c:
                        tmp_min = c
                elif t[nx][ny+1] == '#':
                    if tmp_min > c+1:
                        tmp_min = c+1
            elif (nx+2,ny+1) == (h, w):
                if t[nx+1][ny] == '.':
                    if tmp_min > c:
                        tmp_min = c
                elif t[nx+1][ny] == '#':
                    if tmp_min > c+1:
                        tmp_min = 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] == '.':
                    if tmp_min > c+1:
                        tmp_min = c+1
                elif t[nx][ny+1] == '#':
                    if tmp_min > c+2:
                        tmp_min = c+2

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

#print(tmp_list)
print(tmp_min)

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

Submission status: Time Limit Exceeded

Solution code:
# TLE

import numpy as np
import sys
sys.setrecursionlimit(2000)



def solve(M, num1):

    Mr = np.copy(M)
    Mc = np.copy(M)


    H = M.shape[0]
    W = M.shape[1]

    ret = 0

    # if M.sum() == 0:
    if num1 == 0:
        return ret
    elif H == W == 1:
        return M[0][0]


    del_row = 100000
    del_col = 100000
    num1r = num1
    num1c = num1
    retr = 0
    retc = 0
    if H > 1:
        if Mr[0][0] == 1:
            h = 1
            w = 1
            # while h < H and M[:h + 1, :w].sum() == (h + 1) * w:
            while h < H and Mr[h][0] == 1:
                h += 1
            # while w < W and Mr[:h, :w + 1].sum() == h * (w + 1):
            while w < W and Mr[:h, w:w + 1].sum() == h:
                w += 1

            for i in range(h):
                for j in range(w):
                    Mr[i][j] = 0
                    num1r -= 1
            retr += 1

        del_row = solve(Mr[1:, :], num1r)


    if W > 1:

        if Mc[0][0] == 1:

            h = 1
            w = 1

            # while w < W and Mc[:h, :w + 1].sum() == h * (w + 1):
            while w < W and Mc[0][w] == 1:
                w += 1
            # while h < H and Mc[:h + 1, :w].sum() == (h + 1) * w:
            while h < H and Mc[h:h + 1, :w].sum() == w:
                h += 1


            for i in range(h):
                for j in range(w):
                    Mc[i][j] = 0
                    num1c -= 1
            retc += 1

        del_col = solve(Mc[:, 1:], num1c)

    return min(retr + del_row, retc + del_col)


H, W = [int(x) for x in input().split()]
s = [list(input()) for i in range(H)]
M = np.array([[ (0 if s[i][j] == '.' else 1) for j in range(W) ] for i in range(H)])

print(solve(M, M.sum()) )

Submission status: Time Limit Exceeded

Solution code:
import sys
#input = sys.stdin.buffer.readline
 
def main():
    H,W = map(int,input().split())
    s = [list(input()) for _ in range(H)]

    def ch(x,y):
        if x == H-1 and y == W-1:
            return 0
        else:
            if s[x][y] == ".":
                if y == W-1:
                    if s[x+1][y] == ".":
                        return ch(x+1,y)
                    else:
                        return ch(x+1,y)+1
                elif x == H-1:
                    if s[x][y+1] == ".":
                        return ch(x,y+1)
                    else:
                        return ch(x,y+1)+1
                else:
                    if s[x][y] == s[x+1][y]:
                        a = ch(x+1,y)
                    else:
                        a = ch(x+1,y)+1
                    if s[x][y] == s[x][y+1]:
                        b = ch(x,y+1)
                    else:
                        b = ch(x,y+1)+1
                    return min(a,b)
            else:
                if y == W-1:
                    return ch(x+1,y)
                elif x == H-1:
                    return ch(x,y+1)
                else:
                    return min(ch(x+1,y),ch(x,y+1))

    if s[0][0] == "#":
        a = 1
    else:
        a = 0
    print(a+ch(0,0))
    
if __name__ == "__main__":
    main()

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, z = 0, 0, board[0][0]
        temp_root = [(x, y, z)]
        change_cnt = 0
        if board[y][x] == 1:
            change_cnt += 1

        x_cnt = 0
        y_cnt = 0
        sum_x_cnt = 1
        sum_y_cnt = 1
        for hko in move:
            now_z = 0
            # 0なら横移動
            if hko == 0:
                x += 1
                now_z = board[y][x]
                if now_z == 1:
                    x_cnt += 1
                else:
                    x_cnt = 0
                y_cnt = 0
            else:
                y += 1
                now_z = board[y][x]
                if now_z == 1:
                    y_cnt += 1
                else:
                    y_cnt = 0
                x_cnt = 0

            sum_x_cnt = max(sum_x_cnt, x_cnt)
            sum_y_cnt = max(sum_y_cnt, y_cnt)
            z += now_z
            temp_root.append((x, y, z))

        cnt = min(cnt, z - sum_x_cnt - sum_y_cnt + 2)

    print(cnt)


if __name__ == '__main__':
    main()