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: Wrong Answer

Solution code:
from collections import deque
t,*g=open(0)
f=g[0][0]=="#"
h,w=map(int,t.split())
vis=[[-1]*w for _ in range(h)]
vis[0][0]=0
q=deque([(0,0)])
while q and vis[-1][-1]<0:
	cy,cx=q.popleft()
	for dy,dx in ((-1,0),(0,-1),(0,1),(1,0)):
		ny,nx=cy+dy,cx+dx
		if not(0<=ny<h and 0<=nx<w) or vis[ny][nx]>=0:
			continue
		if g[ny][nx]==".":
			vis[ny][nx]=vis[cy][cx]
			q.appendleft((ny,nx))
		else:
			vis[ny][nx]=vis[cy][cx] + 1
			q.append((ny, nx))
print(vis[-1][-1]+f)

Submission status: Wrong Answer

Solution code:
import sys,collections as cl,bisect as bs
sys.setrecursionlimit(100000)
input = sys.stdin.readline
mod = 10**9+7
Max = sys.maxsize
def l(): #intのlist
    return list(map(int,input().split()))
def m(): #複数文字
    return map(int,input().split())
def onem(): #Nとかの取得
    return int(input())
def s(x): #圧縮
    a = []
    if len(x) == 0:
        return []
    aa = x[0]
    su = 1
    for i in range(len(x)-1):
        if aa != x[i+1]:
            a.append([aa,su])
            aa = x[i+1]
            su = 1
        else:
            su += 1
    a.append([aa,su])
    return a
def jo(x): #listをスペースごとに分ける
    return " ".join(map(str,x))
def max2(x): #他のときもどうように作成可能
    return max(map(max,x))
def In(x,a): #aがリスト(sorted)
    k = bs.bisect_left(a,x)
    if k != len(a) and a[k] ==  x:
        return True
    else:
        return False
"""
def nibu(x,n,r):
    ll = 0
    rr = r
    while True:
        mid = (ll+rr)//2

    if rr == mid:
        return ll
    if (ここに評価入れる):
        rr = mid
    else:
        ll = mid+1
"""


H,W = m()

po = [list(input()) for i in range(H)]

aaa = [[mod for i in range(W)] for j in range(H)]


if po[0][0] == "#":
    aaa[0][0] = 1
else:
    aaa[0][0] = 0

for i in range(H):
    if i == 0:
        for j in range(1,W):
            if po[i][j] == "#":
                aaa[i][j] = min(aaa[i][j],aaa[i][j-1]+1)
            else:
                aaa[i][j] = min(aaa[i][j],aaa[i][j-1])

    else:
        for j in range(W):
            if j == 0:
                if po[i][j] == "#":
                    aaa[i][j] = min(aaa[i][j],aaa[i-1][j]+1)
                else:
                    aaa[i][j] = min(aaa[i][j],aaa[i-1][j])
            else:
                if po[i][j] == "#":
                    aaa[i][j] = min(aaa[i][j],aaa[i][j-1]+1,aaa[i-1][j]+1)
                else:
                    aaa[i][j] = min(aaa[i][j],aaa[i][j-1],aaa[i-1][j])
print(aaa[-1][-1])

Submission status: Wrong Answer

Solution code:
def main():
    n, m = list(map(int, input().strip().split()))

    mat = [input() for _ in range(n)]

    dp = [[10**17 for _ in range(m)] for _ in range(n)]

    dp[0][0] = (mat[0][0]=='#')

    for i in range(n):
        for j in range(m):
            if i-1 >= 0: dp[i][j] = min(dp[i][j], dp[i-1][j] + (mat[i][j]=='#'))
            if j-1 >= 0: dp[i][j] = min(dp[i][j], dp[i][j-1] + (mat[i][j]=='#'))

    print(dp[-1][-1])

if __name__ == "__main__": main()

Submission status: Wrong Answer

Solution code:
H, W = map(int, input().split())
S = [input() for _ in range(H)]
dp = [[100000]*W for _ in range(H)]
dp[0][0] = int(S[0][0]=="#")
for x in range(1, W):
    dp[0][x] = dp[0][x-1] + int(S[0][x]=="#")
for y in range(1, H):
    dp[y][0] = dp[y-1][0] + int(S[y][0]=="#")
    for x in range(1, W):
        dp[y][x] = min(dp[y][x-1], dp[y-1][x]) + int(S[y][x]=="#")
print(dp[-1][-1])

Submission status: Wrong Answer

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

dp = [0] * w
dp[0] = int(field[0][0] == '#')
for j in range(1, w):
    dp[j] = dp[j - 1] + int(field[0][j] == '#')

for i in range(1, h):
    ndp = [0] * w
    ndp[0] = dp[0] + int(field[i][0] == '#')
    for j in range(1, w):
        ndp[j] = min(ndp[j - 1], dp[j]) + int(field[i][j] == '#')
    dp = ndp
print(dp[-1])

Submission status: Wrong Answer

Solution code:
import bisect
import collections
import sys

sys.setrecursionlimit(100000)
input = sys.stdin.readline
ACMOD = 1000000007
INF = 1 << 32


def lmi():
    return list(map(int, input().split()))


def llmi(n):
    return [lmi() for _ in range(n)]


H, W = lmi()
S = [input().strip() for _ in range(W)]

import functools


@functools.lru_cache(maxsize=None)
def solve(h, w):
    if h < 0 or w < 0:
        return INF
    if h == 0 and w == 0:
        return int(S[0][0] == '#')
    return min(solve(h-1,w),solve(h,w-1)) + int(S[h][w] == '#')

print(solve(H-1,W-1))

Submission status: Wrong Answer

Solution code:
h,w = map(int,input().split())
a = [list(input()) for i in range(h)]
dp = [[1000 for i in range(w)] for j in range(h)]
if a[0][0] == ".":
  dp[0][0] = 0
else:
  dp[0][0] = 1
for i in range(h):
  for j in range(w):
    if i == j == 0:
      continue
    if i>0:
      dp[i][j] = dp[i-1][j]
    if j>0:
      dp[i][j] = min(dp[i][j],dp[i][j-1])
    if a[i][j] == "#":
      dp[i][j] += 1
print(dp[-1][-1])

Submission status: Wrong Answer

Solution code:
from collections import deque
import sys
input = sys.stdin.readline

H, W = map(int, input().split())
s = [input() for _ in range(H)]
queue = deque()
queue.append((0, 0))
dist = [[-1] * W for _ in range(H)]
dist[0][0] = 1 if s[0][0] == '#' else 0
while queue:
    i, j = queue.popleft()
    for di, dj in [(1, 0), (0, 1)]:
        ni, nj = i+di, j+dj
        if 0 <= ni < H and 0 <= nj < W and dist[ni][nj] == -1:
            if s[ni][nj] == '#':
                dist[ni][nj] = dist[i][j] + 1
                queue.append((ni, nj))
            else:
                dist[ni][nj] = dist[i][j]
                queue.appendleft((ni, nj))
print(dist[H-1][W-1])

Submission status: Wrong Answer

Solution code:
import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

H,W = map(int,readline().split())
S = ''.join(read().decode().split())

INF = 10 ** 9
dp = [INF] * (H*W)
dp[0] = 0
for n in range(H*W):
    x,y = divmod(n,W)
    dp[n] += (S[n] == '#')
    if x < H - 1:
        if dp[n+W] > dp[n]:
            dp[n+W] = dp[n]
    if y < W - 1:
        if dp[n+1] > dp[n]:
            dp[n+1] = dp[n]

print(dp[-1])

Submission status: Wrong Answer

Solution code:
a=int()

Submission status: Time Limit Exceeded

Solution code:
import sys, math, re
from functools import lru_cache
from itertools import combinations
sys.setrecursionlimit(10**9)
MOD = 10**9+7

def input():
    return sys.stdin.readline()[:-1]

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

def ii():
    return int(input())

def i2(n):
    tmp = [list(mi()) for i in range(n)]
    return [list(i) for i in zip(*tmp)]

def main():
    H, W = mi()
    s = [input() for i in range(H)]
    pathes = []

    for t in combinations(range(H+W-2), H-1):
        now = (0, 0)
        path = [now]

        for i in range(H+W-2):
            if i in t:
                now = (now[0]+1, now[1])
            else:
                now = (now[0], now[1]+1)

            path.append(now)

        pathes.append(path)

    ans = math.inf
    for path in pathes:
        cnt = 0
        if s[0][0] == '#':
            cnt += 1

        if s[H-1][W-1] == '#':
            cnt += 1
            
        for i in range(len(path)-1):
            if s[path[i][0]][path[i][1]] != s[path[i+1][0]][path[i+1][1]]:
                cnt += 1

        ans = min(ans, cnt // 2)

    print(ans)



if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
from collections import*
H,W=map(int,input().split());M=[input()for _ in"_"*H];C=[[999]*W for _ in"_"*H];C[0][0]=0;q=deque([[0,0]])
while q:
  x,y=q.popleft()
  for i,j in [[1,0],[0,1]]:
    h,w=x+i,y+j
    if H>h and W>w:C[h][w]=min([C[h-1][w]+(M[h-1][w]<"."),999][0>h],[C[h][w-1]+(M[h][w-1]<"."),999][0>w]);q.append([h,w])
print(C[-1][-1]+(M[-1][-1]<"."))

Submission status: Time Limit Exceeded

Solution code:
import sys
from collections import deque

input = sys.stdin.readline
H, W = map(int, input().split())

grid = []
for _ in range(H):
    grid.append(list(input().strip()))

q = deque()
# x, y, count, pre color
q.append((0, 0, 1 if grid[0][0] == "#" else 0, grid[0][0]))

visited = [[-1 for _ in range(W)] for _ in range(H)]
ans = float("inf")
while q:
    x, y, count, pre = q.popleft()
    # print(x, y, count, pre)
    v_score = visited[y][x]
    if v_score != -1 and v_score < count:
        continue
    visited[y][x] = count

    for dx, dy in ((1, 0), (0, 1)):
        nx = x + dx
        ny = y + dy
        nc = count
        if nx < 0 or W <= nx or ny < 0 or H <= ny:
            continue
        n_color = grid[ny][nx]
        if n_color != pre and n_color == "#":
            nc += 1
        if nx == W-1 and ny == H-1:
            ans = min(ans, nc)
            print(ans)
            sys.exit()
        else:
            if count == nc:
                q.appendleft((nx, ny, nc, n_color))
            else:
                q.append((nx, ny, nc, n_color))

# print(visited)
print(ans)

Submission status: Time Limit Exceeded

Solution code:
import sys
from collections import deque

input = sys.stdin.readline
H, W = map(int, input().split())

grid = []
for _ in range(H):
    grid.append(list(input().strip()))

q = deque()
# x, y, count, pre color
q.append((0, 0, 1 if grid[0][0] == "#" else 0, grid[0][0]))

visited = [[-1 for _ in range(W)] for _ in range(H)]
ans = float("inf")
while q:
    x, y, count, pre = q.popleft()
    # print(x, y, count, pre)
    if visited[y][x] != -1 and visited[y][x] < count:
        continue
    visited[y][x] = count

    for dx, dy in ((1, 0), (0, 1)):
        nx = x + dx
        ny = y + dy
        nc = count
        if nx < 0 or W <= nx or ny < 0 or H <= ny:
            continue
        if grid[ny][nx] != pre and grid[ny][nx] == "#":
            nc += 1
        if nx == W-1 and ny == H-1:
            ans = min(ans, nc)
            print(ans)
            sys.exit()
        else:
            if count == nc:
                q.appendleft((nx, ny, nc, grid[ny][nx]))
            else:
                q.append((nx, ny, nc, grid[ny][nx]))

# print(visited)
print(ans)

Submission status: Time Limit Exceeded

Solution code:
import sys
from collections import deque

input = sys.stdin.readline
H, W = map(int, input().split())

grid = []
for _ in range(H):
    grid.append(list(input().strip()))

q = deque()
# x, y, count, pre color
q.append((0, 0, 1 if grid[0][0] == "#" else 0, grid[0][0]))

visited = [[-1 for _ in range(W)] for _ in range(H)]
ans = float("inf")
while q:
    x, y, count, pre = q.popleft()
    # print(x, y, count, pre)
    if visited[y][x] != -1 and visited[y][x] < count:
        continue
    visited[y][x] = count

    for dx, dy in ((1, 0), (0, 1)):
        nx = x + dx
        ny = y + dy
        nc = count
        if nx < 0 or W <= nx or ny < 0 or H <= ny:
            continue
        if grid[ny][nx] != pre and grid[ny][nx] == "#":
            nc += 1
        if nx == W-1 and ny == H-1:
            ans = min(ans, nc)
        else:
            if count == nc:
                q.appendleft((nx, ny, nc, grid[ny][nx]))
            else:
                q.append((nx, ny, nc, grid[ny][nx]))

# print(visited)
print(ans)

Submission status: Time Limit Exceeded

Solution code:
import sys
from collections import deque

input = sys.stdin.readline
H, W = map(int, input().split())

grid = []
for _ in range(H):
    grid.append(list(input().strip()))

q = deque()
# x, y, count, pre color
q.append((0, 0, 1 if grid[0][0] == "#" else 0, grid[0][0]))

visited = [[-1 for _ in range(W)] for _ in range(H)]
ans = float("inf")
while q:
    x, y, count, pre = q.popleft()
    # print(x, y, count, pre)
    if visited[y][x] != -1 and visited[y][x] < count:
        continue
    visited[y][x] = count

    for dx, dy in ((1, 0), (0, 1)):
        nx = x + dx
        ny = y + dy
        nc = count
        if nx < 0 or W <= nx or ny < 0 or H <= ny:
            continue
        if grid[ny][nx] != pre and grid[ny][nx] == "#":
            nc += 1
        if nx == W-1 and ny == H-1:
            ans = min(ans, nc)
        else:
            q.append((nx, ny, nc, grid[ny][nx]))

# print(visited)
print(ans)

Submission status: Time Limit Exceeded

Solution code:
from collections import deque
H,W = map(int,input().split())
A = [input().strip() for _ in range(H)]
d = 0
if A[0][0]=="#":
    d += 1
que = deque([(0,0,d)])
hist = [[H*W for _ in range(W)] for _ in range(H)]
hist[0][0] = d
while que:
    i,j,d = que.popleft()
    if j+1<W and A[i][j+1]==A[i][j]:
        hist[i][j+1] = min(hist[i][j+1],d)
        que.append((i,j+1,hist[i][j+1]))
    elif j+1<W and A[i][j+1]!=A[i][j]:
        hist[i][j+1] = min(hist[i][j+1],d+1)
        que.append((i,j+1,hist[i][j+1]))
    if i+1<H and A[i+1][j]==A[i][j]:
        hist[i+1][j] = min(hist[i+1][j],d)
        que.append((i+1,j,hist[i+1][j]))
    elif i+1<H and A[i+1][j]!=A[i][j]:
        hist[i+1][j] = min(hist[i+1][j],d+1)
        que.append((i+1,j,hist[i+1][j]))
m = hist[H-1][W-1]
print((m+1)//2)

Submission status: Time Limit Exceeded

Solution code:
from collections import deque

H, W = [int(x) - 1 for x in input().split()]

board = []

for _ in range(H+1):
    r = list([x for x in input()])
    board.append(r)

queue = deque()

if board[0][0] == '#':
    queue.appendleft((0, 0, 1))
else:
    queue.appendleft((0, 0, 0))

while queue:
    r, c, count = queue.popleft()

    if r == H and c == W:
        print(count)
        exit()

    if r + 1 <= H:
        if board[r + 1][c] == '.':
            queue.appendleft((r+1, c, count))
        else:
            queue.append((r+1, c, count+1))

    if c + 1 <= W:
        if board[r][c+1] == '.':
            queue.appendleft((r, c+1, count))
        else:
            queue.append((r, c+1, count+1))

Submission status: Time Limit Exceeded

Solution code:
from itertools import combinations
h, w = map(int, input().split())
s = [list(input()) for i in range(h)]
x = list(combinations(list(range(h+w-2)), h-1))
ans = float("inf")
for i in x:
    pos = [0, 0]
    cnt = 0
    for j in range(h+w-2):
        if s[pos[0]][pos[1]] == "#":
            cnt += 1
        if j in i:
            pos[0] += 1
        else:
            pos[1] += 1
    ans = min(ans, cnt)
if s[h-1][w-1] == "#":
    ans += 1
print(ans)

Submission status: Time Limit Exceeded

Solution code:
from collections import deque

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

dp=[[float('inf')]*w for i in range(h)]

cnt=0
for i in range(h):
  if maze[i][0]=='#':
    cnt+=1
  dp[i][0]=cnt


cnt=0
for i in range(w):
  if maze[0][i]=='#':
    cnt+=1
  dp[0][i]=cnt
  
Q=deque()

Q.append((1,1))

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

while Q:
  x,y=Q.popleft()
  if maze[x][y]=='#':
    dp[x][y]=min(dp[x-1][y],dp[x][y-1])+1
  
  else:
    dp[x][y]=min(dp[x-1][y],dp[x][y-1])
  
  if x==h-1 and y==w-1:
    break

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

    if 0<=nx<h and 0<=ny<w and dp[nx][ny]==float('inf'):
      Q.append((nx,ny))


print(dp[-1][-1])

Submission status: Time Limit Exceeded

Solution code:
from collections import deque

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

dp=[[float('inf')]*w for i in range(h)]

cnt=0
for i in range(h):
  if maze[i][0]=='#':
    cnt+=1
  dp[i][0]=cnt


cnt=0
for i in range(w):
  if maze[0][i]=='#':
    cnt+=1
  dp[0][i]=cnt
  
Q=deque()

Q.append((1,1))

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

while Q:
  x,y=Q.popleft()
  if maze[x][y]=='#':
    dp[x][y]=min(dp[x-1][y],dp[x][y-1])+1
  
  else:
    dp[x][y]=min(dp[x-1][y],dp[x][y-1])

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

    if 0<=nx<h and 0<=ny<w:
      Q.append((nx,ny))


print(dp[-1][-1])

Submission status: Time Limit Exceeded

Solution code:
import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
 
H,W = map(int,readline().split())
S = ''.join(read().decode().split())
 
INF = 10 ** 9
N = H*W
U = 250
dp = [[INF] * U for _ in range(N)]
# そのマスをいじる回数 → 総回数の最小値
dp[0] = list(range(U))
for n in range(H*W):
    for i in range(U-1,0,-1):
        if dp[n][i-1]> dp[n][i]:
            dp[n][i-1] = dp[n][i]
    for i in range(1,U):
        if dp[n][i-1] + 1 < dp[n][i]:
            dp[n][i] = dp[n][i-1] + 1
    s = S[n]
    if s == '#':
        for i in range(0,U,2):
            dp[n][i] = INF
    else:
        for i in range(1,U,2):
            dp[n][i] = INF
    x,y = divmod(n,W)
    to = []
    if y < W - 1:
        to.append(n+1)
    if x < H - 1:
        to.append(n+W)
    for m in to:
        for i in range(U):
            if dp[m][i] > dp[n][i]:
                dp[m][i] = dp[n][i]

print(min(dp[-1]))

Submission status: Time Limit Exceeded

Solution code:
# https://atcoder.jp/contests/agc043/tasks/agc043_a

import sys
# sys.setrecursionlimit(100000)


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


def input_int():
    return int(input())


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


ans = (100 * 100) + 1


def main():
    global ans
    h, w = input_int_list()
    grid = []
    grid.append(["#"] * (w + 2))
    for _ in range(h):
        grid.append(["#"] + list(input()) + ["#"])
    grid.append(["#"] * (w + 2))

    def search(x, y, cnt):
        global ans
        if cnt > ans:
            return

        if grid[y][x] == "#":
            cnt += 1

        if y == h and x == w:
            ans = min(ans, cnt)
            return
        else:
            if y < h:
                search(x, y + 1, cnt)
            if x < w:
                search(x + 1, y, cnt)
    search(1, 1, 0)
    print(ans)
    return


if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
# https://atcoder.jp/contests/agc043/tasks/agc043_a

import sys
# sys.setrecursionlimit(100000)


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


def input_int():
    return int(input())


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


def main():
    h, w = input_int_list()
    grid = []
    grid.append(["#"] * (w + 2))
    for _ in range(h):
        grid.append(["#"] + list(input()) + ["#"])
    grid.append(["#"] * (w + 2))
    ans = set()

    def search(x, y, cnt):
        if grid[y][x] == "#":
            cnt += 1

        if y == h and x == w:
            ans.add(cnt)
            return
        else:
            if y < h:
                search(x, y + 1, cnt)
            if x < w:
                search(x + 1, y, cnt)
    search(1, 1, 0)
    print(min(ans))
    return


if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
h, w = map(int, input().split())
hw = [input() for _ in range(h)]
ans = h+w
pvs = None

def dfs(x, y, cnt, pvs):
    global ans
    if hw[x][y] == "#" and pvs != "#":
        cnt += 1
        pvs = "#"
    elif hw[x][y] == "#" and pvs == "#":
        pass
    elif hw[x][y] == ".":
        pvs = "."
    if x == h-1 and y == w-1:
        ans = min(ans, cnt)
        return ans
    if x < h-1 and y == w-1:
        dfs(x+1, y, cnt, pvs)
    if x == h-1 and y < w-1:
        dfs(x, y+1, cnt, pvs)
    if x < h-1 and y < w-1:
        dfs(x+1, y, cnt, pvs)
        dfs(x, y+1, cnt, pvs)

dfs(0, 0, 0, pvs)
print(ans)

Submission status: Time Limit Exceeded

Solution code:
import queue
h, w = map(int, input().split())
s = [list(input()) for _ in range(h)]
ans = float('inf')
q = queue.Queue()
vals = [[float('inf')]*w for _ in range(h)]

if s[0][0] == '#':
    q.put([0, 0, 1])
else:
    q.put([0, 0, 0])

while not q.empty():
    a = q.get()
    if a[0] == h-1 and a[1] == w-1:
        ans = min(ans, a[2])
        
    if a[0]+1 < h:
        if s[a[0]+1][a[1]] == '.':
            q.put([a[0]+1, a[1], a[2]])
            vals[a[0]+1][a[1]] = a[2]
        elif vals[a[0]][a[1]]+1 <= vals[a[0]+1][a[1]]:
            q.put([a[0]+1, a[1], a[2]+1])
            vals[a[0]+1][a[1]] = a[2]+1

    if a[1]+1 < w:
        if s[a[0]][a[1]+1] == '.':
            q.put([a[0], a[1]+1, a[2]])
        elif vals[a[0]][a[1]]+1 <= vals[a[0]][a[1]+1]:
            q.put([a[0], a[1]+1, a[2]+1])
            vals[a[0]][a[1]+1] = a[2]+1
print(ans)

Submission status: Time Limit Exceeded

Solution code:
import queue
h, w = map(int, input().split())
s = [list(input()) for _ in range(h)]
ans = float('inf')
q = queue.Queue()

if s[0][0] == '#':
    q.put([0, 0, 1])
else:
    q.put([0, 0, 0])

while not q.empty():
    a = q.get()
    if ans <= a[2]:
        continue
    
    if a[0] == h-1 and a[1] == w-1:
        ans = min(ans, a[2])
        
    if a[0]+1 < h and a[1]+1 < w:
        if s[a[0]+1][a[1]] == '.' and s[a[0]][a[1]+1] == '.':
            q.put([a[0]+1, a[1], a[2]])
            q.put([a[0], a[1]+1, a[2]])
        elif s[a[0]+1][a[1]] == '.' and s[a[0]][a[1]+1] == '#':
            q.put([a[0]+1, a[1], a[2]])
        elif s[a[0]+1][a[1]] == '#' and s[a[0]][a[1]+1] == '.':
            q.put([a[0], a[1]+1, a[2]])
        else:
            q.put([a[0]+1, a[1], a[2]+1])
            q.put([a[0], a[1]+1, a[2]+1])
    elif a[0]+1 < h:
        if s[a[0]+1][a[1]] == '.':
            q.put([a[0]+1, a[1], a[2]])
        else:
            q.put([a[0]+1, a[1], a[2]+1])
    elif a[1]+1 < w:
        if s[a[0]][a[1]+1] == '.':
            q.put([a[0], a[1]+1, a[2]])
        else:
            q.put([a[0], a[1]+1, a[2]+1])
        
print(ans)

Submission status: Time Limit Exceeded

Solution code:
import queue
h, w = map(int, input().split())
s = [list(input()) for _ in range(h)]
ans = float('inf')
q = queue.Queue()

if s[0][0] == '#':
    q.put([0, 0, 1])
else:
    q.put([0, 0, 0])

while not q.empty():
    a = q.get()
    if ans <= a[2]:
        continue
    
    if a[0] == h-1 and a[1] == w-1:
        ans = min(ans, a[2])
        
    if a[0]+1 < h:
        if s[a[0]+1][a[1]] == '#':
            q.put([a[0]+1, a[1], a[2]+1])
        else:
            q.put([a[0]+1, a[1], a[2]])

    if a[1]+1 < w:
        if s[a[0]][a[1]+1] == '#':
            q.put([a[0], a[1]+1, a[2]+1])
        else:
            q.put([a[0], a[1]+1, a[2]])
print(ans)

Submission status: Time Limit Exceeded

Solution code:
import queue
h, w = map(int, input().split())
s = [list(input()) for _ in range(h)]
ans = []
q = queue.Queue()

if s[0][0] == '#':
    q.put([0, 0, 1])
else:
    q.put([0, 0, 0])

while not q.empty():
    a = q.get()
    if a[0] == h-1 and a[1] == w-1:
        ans.append(a[2])

    if a[0]+1 < h:
        if s[a[0]+1][a[1]] == '#':
            q.put([a[0]+1, a[1], a[2]+1])
        elif s[a[0]+1][a[1]] != '#':
            q.put([a[0]+1, a[1], a[2]])

    if a[1]+1 < w:
        if s[a[0]][a[1]+1] == '#':
            q.put([a[0], a[1]+1, a[2]+1])
        elif s[a[0]][a[1]+1] != '#':
            q.put([a[0], a[1]+1, a[2]])
print(min(ans))

Submission status: Time Limit Exceeded

Solution code:
#!/usr/bin/env python3

import sys
sys.setrecursionlimit(10**7)

INF = 10**7
DIRECTION = [[0,1],[1,0]]

def solve(h,w,board):
    # memo = [[-1]*w for _ in range(h)]
    def dfs(y,x,gy,gx,cnt=0):
        if y == gy and x == gx:
            return cnt + (board[y][x] == '#')
        if not (0 <= y < h and 0 <= x < w):
            return INF
        res = INF
        for d in DIRECTION:
            ny = y + d[0]
            nx = x + d[1]
            res = min(res,dfs(ny,nx,gy,gx,cnt+(board[y][x]=='#')))
        return res

    return dfs(0,0,h-1,w-1)



def main():
    H,W = map(int,input().split())
    board = [input() for _ in range(H)]
    print(solve(H,W,board))
    # write c


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
#!/usr/bin/env python3
from collections import deque

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

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

que = deque([])
que.append((0, 0, maze[0][0], 1 if maze[0][0] else 0))
count = 10**5

while que:
    x, y, b, c = que.pop()
    if x == h - 1 and y == w - 1:
        count = min(count, c)
    elif c < count:
        for i in range(2):
            nx = x + dx[i]
            ny = y + dy[i]

            if not (0 <= nx < h and 0 <= ny < w):
                continue
            que.append((nx, ny, maze[nx][ny], c + (not b and maze[nx][ny])))
print(count)

Submission status: Time Limit Exceeded

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

minimum = H+W

stack = [[0,0,0]]
while stack:
    x,y,n = stack.pop()
    if A[y][x] == "#":n+=1
    if (x>=W-1)&(y>=H-1):
        if minimum>n:minimum=n
    if x<W-1:stack.append([x+1,y,n])
    if y<H-1:stack.append([x,y+1,n])

print(minimum)

Submission status: Time Limit Exceeded

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

minimum = float("inf")

stack = [[0,0,0]]
while stack:
    x,y,n = stack.pop()
    if A[y][x] == "#":n+=1
    if (x>=W-1)&(y>=H-1):
        if minimum>n:minimum=n
    if x<W-1:stack.append([x+1,y,n])
    if y<H-1:stack.append([x,y+1,n])

print(minimum)

Submission status: Time Limit Exceeded

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

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

minimum = float("inf")
def go(x,y,n):
    if A[y][x] == "#":n+=1
    if (y>=H-1)&(x>=W-1):
        global minimum
        if minimum>n:minimum=n
        return
    if y<H-1:go(x,y+1,n)
    if x<W-1:go(x+1,y,n)

go(0,0,0)
print(minimum)

Submission status: Time Limit Exceeded

Solution code:
def getN():
    return int(input())
def getNM():
    return map(int, input().split())
def getList():
    return list(map(int, input().split()))
def getArray(intn):
    return [int(input()) for i in range(intn)]
def input():
    return sys.stdin.readline().rstrip()
def rand_N(ran1, ran2):
    return random.randint(ran1, ran2)
def rand_List(ran1, ran2, rantime):
    return [random.randint(ran1, ran2) for i in range(rantime)]
def rand_ints_nodup(ran1, ran2, rantime):
  ns = []
  while len(ns) < rantime:
    n = random.randint(ran1, ran2)
    if not n in ns:
      ns.append(n)
  return sorted(ns)

def rand_query(ran1, ran2, rantime):
  r_query = []
  while len(r_query) < rantime:
    n_q = rand_ints_nodup(ran1, ran2, 2)
    if not n_q in r_query:
      r_query.append(n_q)
  return sorted(r_query)

from collections import defaultdict, deque, Counter
from sys import exit
from decimal import *
import heapq
import math
from fractions import gcd
import random
import string
import copy
from itertools import combinations, permutations, product
from operator import mul
from functools import reduce
from bisect import bisect_left, bisect_right

import sys
sys.setrecursionlimit(1000000000)
mod = 10 ** 9 + 7

#############
# Main Code #
#############

H, W = getNM()
maze = []
for i in range(H):
    s = input()
    maze.append(list(s))
dp = [[float('inf')] * W for i in range(H)]
dp[0][0] = 0

pos = deque([[0, 0]])
dx = [1, 0]
dy = [0, 1]

while len(pos) > 0:
    x, y = pos.popleft()
    for i in range(2):
        nx = x + dx[i]
        ny = y + dy[i]
        if 0 <= nx < W and 0 <= ny < H:
            if maze[ny][nx] == "#" and maze[y][x] == ".":
                dp[ny][nx] = min(dp[ny][nx], dp[y][x] + 1)
            else:
                dp[ny][nx] = min(dp[ny][nx], dp[y][x])
            pos.append([nx, ny])

ans = dp[H - 1][W - 1]

if maze[0][0] == "#":
    print(ans + 1)
else:
    print(ans)

Submission status: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(10**6)
def S(): return sys.stdin.readline().rstrip()
def IL(): return map(int,sys.stdin.readline().rstrip().split())

def DFS(count,i,j):
    if w<=i or h<=j:
        return
    if mp[j][i]=='#':
        count += 1
    if i==w-1 and j==h-1:
        global c
        if c==-1:
            c = count
        else:
            c = min(count,c)
        if c==0:
            print(c)
            exit()
        return

    right = mp[j][i+1] if i+1<w else '#'
    down = mp[j+1][i] if j+1<h else '#'
    if (right=='#' and down=='#') or (right=='.' and down=='.'):
        for rep in range(na):
            DFS(count,i+dx[rep],j+dy[rep])
    elif right=='#':
        DFS(count,i,j+1)
    elif down=='#':
        DFS(count,i+1,j)

def Main():
    DFS(0,0,0)
    print(c)
    return

if __name__=='__main__':
    h,w = IL()
    mp = [S() for _ in range(h)]
    c = -1
    dy = [0,1]
    dx = [1,0]
    na = len(dy)
    Main()

Submission status: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(10**6)
def S(): return sys.stdin.readline().rstrip()
def IL(): return map(int,sys.stdin.readline().rstrip().split())

def DFS(count,i,j):
    if w<=i or h<=j:
        return
    if mp[j][i]=='#':
        count += 1
    if i==w-1 and j==h-1:
        global c
        if c==-1:
            c = count
        else:
            c = min(count,c)
        if c==0:
            print(c)
            exit()
        return
    for rep in range(na):
        DFS(count,i+dx[rep],j+dy[rep])

def Main():
    DFS(0,0,0)
    print(c)
    return

if __name__=='__main__':
    h,w = IL()
    mp = [S() for _ in range(h)]
    c = -1
    dy = [0,1]
    dx = [1,0]
    na = len(dy)
    Main()

Submission status: Time Limit Exceeded

Solution code:
from collections import deque
h, w = map(int, input().split())
S = [list(input()) for _ in range(h)]

#BFS
## 距離の初期化
D = [[10000]*w for _ in range(h)]
D[0][0] = 0 if S[0][0]=='.' else 1
## キューの初期化.
que = deque([[0,0]])
## 探索方向の初期化.
directs = [[0,1],[1,0]]
## キューが尽きるまで探索を行う.
while que:
    ### 現在地の取得.
    hi, wi = que.pop()
    ### 以下の移動方向を探索する.
    for dh,dw in directs:
        #### 迷路の範囲外の場合は探索しない.
        if not (0<=hi+dh<h and 0<=wi+dw<w): continue
        #### 白から黒に移る場合、コストが増える.
        if S[hi][wi]!=S[hi+dh][wi+dw] and S[hi+dh][wi+dw]=='#':
            D[hi+dh][wi+dw] = min(D[hi+dh][wi+dw], D[hi][wi]+1)
        else:
            D[hi+dh][wi+dw] = min(D[hi+dh][wi+dw], D[hi][wi])
        que.appendleft([hi+dh, wi+dw])
print(D[-1][-1])