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:
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,0] for i in range(W)] for j in range(H)]


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

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

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

Submission status: Wrong Answer

Solution code:
from heapq import heappop, heappush, heapify

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

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

res = 1

heap = [(1, 0, 0)]
heapify(heap)
visited = [[0 for j in range(W)] for i in range(H)]
visited[0][0] = 1

while heap:
    c, x, y = heappop(heap)
    for i in range(4):
        nx, ny = x + dx[i], y + dy[i]
        if not (0 <= nx < H and 0 <= ny < W):
            continue
        if visited[nx][ny]:
            continue
        if S[x][y] == S[nx][ny]:
            visited[nx][ny] = c
            heappush(heap, (c, nx, ny))
        else:
            visited[nx][ny] = c + 1
            heappush(heap, (c + 1, nx, ny))

if S[0][0] == '#':
    print((visited[-1][-1]+1)//2)
else:
    print(visited[-1][-1]//2)

Submission status: Wrong Answer

Solution code:
#!/usr/bin/env python3
H, W = [int(str) for str in input().strip().split()]
S = [input().strip() for _ in range(H)]

def cost(h, w):
    return 1 if S[h][w] == '#' else 0

inf = 100000

# init
dp = [[inf] * W for _ in range(H)]
dp[0][0] = cost(0, 0)
for w in range(1, W):
    dp[0][w] = dp[0][w - 1] + cost(0, w)

for h in range(1, H):
    dp[h][0] = dp[h - 1][0] + cost(h, 0)
    for w in range(1, W):
        dp[h][w] = dp[h][w] = min(dp[h][w - 1], dp[h - 1][w]) + cost(h, w)

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

Submission status: Wrong Answer

Solution code:
h,w= map(int,input().split(' '))
min= h*w

grid= [[0 for i in range(w)] for j in range(h)]

for i in range(h):
    row=input()
    for j in range(len(row)):
        if row[j]=='#':
            grid[i][j]=1

btdt= [[-1 for i in range(w)] for j in range(h)]
def go(i,j,count):
    global h,w,min,grid
    if i>=h or j>=w:
        return
    if count>min:
        return
    if btdt[i][j] != -1 and count >= btdt[i][j]:
        return
    if i==h-1 and j==w-1:
        if grid[i][j]==1:
            count+=1
        min=count
        return
    if grid[i][j]==1:
        btdt[i][j] = count+1
        count+=1
        go(i+1,j,count)
        go(i,j+1,count)
    else:
        btdt[i][j] = count
        go(i + 1, j, count)
        go(i, j + 1, count)

go(0,0,0)
print(min)

Submission status: Wrong Answer

Solution code:
# coding: utf-8
from collections import deque


def solve(*args: str) -> str:
    h, w = map(int, args[0].split())
    black = [[True if s == '#' else False for s in S] for S in args[1:]]

    inf = 10**12
    counts = [[inf]*w for _ in range(h)]
    Q = deque([(0, 0, 0, False)])
    while Q:
        x, y, n, prev = Q.popleft()
        if h <= y or w <= x:
            continue

        if black[y][x]:
            if not prev:
                n += 1
        else:
            prev = False

        if n < counts[y][x]:
            counts[y][x] = n
            for dx, dy in [(1, 0), (0, 1)]:
                Q.append((x+dx, y+dy, n, prev))

    return str(counts[-1][-1])


if __name__ == "__main__":
    print(solve(*(open(0).read().splitlines())))

Submission status: Wrong Answer

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

cnt = 0
i, j = 0, 0
if s[i][j] == '#':
    cnt += 1

while i < H - 1 or j < W - 1:
    if i < H - 1 and s[i + 1][j] == '.':
        i = i + 1
    elif j < W - 1 and s[i][j + 1] == '.':
        j = j + 1
    elif i < H - 1:
        if i < H - 2 and s[i + 2][j] == '.':
            i = i + 1
            cnt += 1
        else:
            if j < W - 2 and s[i][j + 2] == '.':
                j = j + 1
                cnt += 1
    else:
        j = j + 1
        cnt += 1


print(cnt)

Submission status: Wrong Answer

Solution code:
#from functools import lru_cache
#memo = lru_cache(None)
#from sys import setrecursionlimit as srl
#srl(2 * 10**5)
import heapq

rr = raw_input
rri = lambda: int(rr())
rrm = lambda: map(int, rr().split())

def solve(R, C, A):
    pq = [(0, 0, 0)]
    dist = {(0,0): 0}
    INF = float('inf')

    def neighbors(r, c):
        for nr, nc in ((r-1, c), (r, c-1), (r+1, c), (r, c+1)):
            if 0 <= nr < R and 0 <= nc < C:
                if A[nr][nc] == A[r][c]:
                    yield nr, nc, 0
                else:
                    yield nr, nc, 1
    while pq:
        d, r, c = heapq.heappop(pq)
        if d > dist.get((r, c), INF):
            continue
        if r==R-1 and c==C-1:
            if A[0][0]:
                return (d + 1) // 2
            else:
                return d // 2 + 1
            
        for nr, nc, w in neighbors(r, c):
            nd = d + w
            nei = nr, nc
            if nd < dist.get(nei, INF):
                heapq.heappush(pq, (nd, nr, nc))
                dist[nei] = nd
    return 0
        


for _ in xrange(1):
    R, C = rrm()
    A = []
    for _ in xrange(R):
        row = [c=='.' for c in rr()]
        A.append(row)

print solve(R, C, A)

Submission status: Wrong Answer

Solution code:
from functools import lru_cache


R, C = list(map(int, input().split()))
grid = []
for r in range(R):
    grid.append(list(input().rstrip()))


@lru_cache(maxsize=None)
def minDist(r, c):
    color = int(grid[r][c] == "#")

    best = float("inf")
    if r == 0 and c == 0:
        return color
    if r >= 1:
        best = min(
            best,
            int(grid[r][c] != grid[r - 1][c] and grid[r - 1][c] == "#")
            + minDist(r - 1, c),
        )
    if c >= 1:
        best = min(
            best,
            int(grid[r][c] != grid[r][c - 1] and grid[r][c - 1] == "#")
            + minDist(r, c - 1),
        )
    return best


print(minDist(R - 1, C - 1))

Submission status: Wrong Answer

Solution code:
h, w = map(int, input().split())
map = []
ansList = [[0] * w for i in range(h)]
#print(list(input()))
for x in range(h):
    a = list(input())
    map.append(a)

for y in range(h):
    for x in range(w):
        if y > 0 and x > 0: val = min(ansList[y - 1][x], ansList[y][x - 1])
        elif y == 0 and x == 0: val = 0
        elif y == 0: val = ansList[y][x - 1]
        elif x == 0: val = ansList[y - 1][x]

        if map[y][x] == "#": ansList[y][x] = val + 1
        else: ansList[y][x] = val
print(ansList[h - 1][w - 1])

Submission status: Wrong Answer

Solution code:
import sys
import copy
import math
import fractions

import bisect
import pprint
import bisect
from functools import reduce
from copy import deepcopy
from collections import deque
import numpy as np
from decimal import *

maiz = []
maxh = 0
maxw =0

def CheckCost(h, w):
    if h + 1 < maxh:
        if costList[h + 1][w] == -1 or costList[h + 1][w] > costList[h][w] + CheckColum(h+1,w):
            costList[h + 1][w] = costList[h][w] + CheckColum(h+1,w)
            CheckCost(h + 1, w)

    if w + 1 < maxw:
        if costList[h][w + 1] == -1 or costList[h][w + 1] > costList[h][w] + CheckColum(h,w+1):
            costList[h][w + 1] = costList[h][w] + CheckColum(h,w+1)
            CheckCost(h, w + 1)

def CheckColum(h,w):
    if maiz[h][w] == "#":
        return 1
    else:
        return 0



if __name__ == '__main__':
    h, w = map(int, input().split())
    maxh = h
    maxw = w
    costList =[]
    for i in range(h):
        costList.append([-1]*w)

    for i in range(h):
        s = input()
        maiz.append(list(map(lambda x:x,s)))
    costList[0][0] = CheckColum(0,0)


    CheckCost(0,0)

    print(costList[h-1][w-1])

Submission status: Wrong Answer

Solution code:
h,w = map(int,input().split())
mat = [input() for i in range(h)]

dp = [[h+w]*w for i in range(h)]

dp[0][0] = (mat[0][0]=='#')
for i in range(1,w):
  dp[0][i] = dp[0][i-1]+(mat[0][i]=='#')
for i in range(1,h):
  dp[i][0] = dp[i-1][0]+(mat[i][0]=='#')
  
for hh in range(1,h):
  for ww in range(1,w):
    dp[hh][ww] = min(dp[hh-1][ww],dp[hh][ww-1]) + (mat[hh][ww]=='#')

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

Submission status: Wrong Answer

Solution code:
h, w = map(int, input().split())
s = []
s.append(["."] * (w + 1))
for i in range(h):
    s.append(["."] + list(input()))
s2 = []
for i in range(h + 1):
    s2.append([0] * (w + 1))
for i in range(w - 1):
    if s[1][i + 1] == "#":
        s2[0][i + 2] = s2[0][i + 1] + 1
    else:
        s2[0][i + 2] = s2[0][i + 1]
for i in range(h - 1):
    if s[i + 1][1] == "#":
        s2[i + 2][0] = s2[i + 1][0] + 1
    else:
        s2[i + 2][0] = s2[i + 1][0]

for i in range(h):
    for j in range(w):
        if s[i + 1][j + 1] == ".":
            s2[i + 1][j + 1] = min(s2[i][j + 1], s2[i + 1][j])
        else:
            s2[i + 1][j + 1] = min(s2[i][j + 1], s2[i + 1][j]) + 1
print(s2[h][w])

Submission status: Wrong Answer

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

Submission status: Wrong Answer

Solution code:
import sys
sys.setrecursionlimit(100000)

h,w=map(int,input().split())
INF=10**10
s_org=[list(input()) for _ in range(h)]
s=[[0]*w for _ in range(h)]
for i in range(h):
  for j in range(w):
    if s_org[i][j]=="#":
      s[i][j]=1
dp=[[-1]*w for _ in range(h)]
dp[0][0]=s[0][0]
def func(i,j):
  if i<0 or j<0: return INF
  if dp[i][j]!=-1:return dp[i][j]
  val=min(func(i,j-1)+s[i][j-1],func(i-1,j)+s[i-1][j])
  dp[i][j]=val
  return val
print(func(h-1,w-1))

Submission status: Wrong Answer

Solution code:
import sys
from collections import deque
readline = sys.stdin.readline
H, W = map(int, readline().split())
G = [list(map(lambda x: 1 if x == '.' else 0, readline().strip())) for _ in range(H)]

dist = [[0]*W for _ in range(H)]

Q = deque([(0, 0)])
used = set(Q)
dim = [(-1, 0), (0, 1), (0, -1), (1, 0)]
while Q:
    nx, ny = Q.pop()
    for dx, dy in dim:
        fx, fy = nx+dx, ny+dy
        if not 0 <= fx < H or not 0 <= fy < W:
            continue
        if (fx, fy) in used:
            continue
        used.add((fx, fy))
        if G[nx][ny] == G[fx][fy]:
            dist[fx][fy] = dist[nx][ny]
            Q.append((fx, fy))
        else:
            dist[fx][fy] = 1 + dist[nx][ny]
            Q.appendleft((fx, fy))

K = dist[H-1][W-1]
if G[0][0] == 0:
    K += 1
if G[H-1][W-1] == 0:
    K += 1
print(K//2)

Submission status: Wrong Answer

Solution code:
# Code for A - Range Flip Find Route
# Use input() to fetch data from STDIN

import numpy as np
H, W = map(int, input().split())

S = [list(str(input())) for i in range(H)]
S = np.array(S)

dp = np.zeros((H, W), dtype=np.int)

dp[0, :] = np.cumsum(S[0, :] == "#")
dp[:, 0] = np.cumsum(S[:, 0] == "#")

for i in range(1, H):
    for j in range(1, W):
        if S[i, j] == "#":
            dp[i, j] += 1
        dp[i, j] += min(dp[i-1, j], dp[i, j-1])

print(dp[-1, -1])

Submission status: Wrong Answer

Solution code:
h,w= map(int,input().split(' '))
min= h*w

grid= [[0 for i in range(w)] for j in range(h)]

for i in range(h):
    row=input()
    for j in range(len(row)):
        if row[j]=='#':
            grid[i][j]=1

btdt= [[-1 for i in range(w)] for j in range(h)]
def go(i,j,count):
    global h,w,min,grid
    if i>=h or j>=w:
        return
    if count>min:
        return
    if btdt[i][j] != -1 and count >= btdt[i][j]:
        return
    if i==h-1 and j==w-1:
        if grid[i][j]==1:
            count+=1
        min=count
        return
    btdt[i][j]=count
    if grid[i][j]==1:
        count+=1
        go(i+1,j,count)
        go(i,j+1,count)
    else:
        go(i + 1, j, count)
        go(i, j + 1, count)

go(0,0,0)
print(min)

Submission status: Wrong Answer

Solution code:
from collections import deque
h,w = map(int,input().split())
s = []
for i in range(h):
    s0 = list(input())
    s.append(s0)
d = deque()
rl = [[h*w+1 for i in range(w)] for i in range(h)]
if s[0][0] == ".":
    d.append([0,0])
    rl[0][0] = 0
else:
    d.append([0,0])
    rl[0][0] = 1
while len(d):
    a,b = d.popleft()
    #print(a,b,rl)
    if a == h-1:
        if b < w-1:
            if rl[a][b+1] == h*w+1:
                if s[a][b+1] == "#":
                    rl[a][b+1] = rl[a][b] + 1
                else:
                    rl[a][b+1] = rl[a][b]
                d.append([a,b+1])
            else:
                if s[a][b+1] == "#":
                    rl[a][b+1]= min(rl[a][b+1],rl[a][b] + 1)
                else:
                    rl[a][b+1] = min(rl[a][b+1],rl[a][b])
    else:
        if b == w-1:
            if rl[a+1][b] == h*w+1:
                if s[a+1][b] == "#":
                    rl[a+1][b] = rl[a][b] + 1
                else:
                    rl[a+1][b] = rl[a][b]
                d.append([a+1,b])
            else:
                if s[a+1][b] == "#":
                    rl[a+1][b]= min(rl[a+1][b],rl[a][b] + 1)
                else:
                    rl[a+1][b] = min(rl[a+1][b],rl[a][b])
        else:
            if rl[a][b+1] == h*w+1:
                if s[a][b+1] == "#":
                    rl[a][b+1] = rl[a][b] + 1
                else:
                    rl[a][b+1] = rl[a][b]
                d.append([a,b+1])
            else:
                if s[a][b+1] == "#":
                    rl[a][b+1]= min(rl[a][b+1],rl[a][b] + 1)
                else:
                    rl[a][b+1] = min(rl[a][b+1],rl[a][b])
            if rl[a+1][b] == h*w+1:
                if s[a+1][b] == "#":
                    rl[a+1][b] = rl[a][b] + 1
                else:
                    rl[a+1][b] = rl[a][b]
                d.append([a+1,b])
            else:
                if s[a+1][b] == "#":
                    rl[a+1][b]= min(rl[a+1][b],rl[a][b] + 1)
                else:
                    rl[a+1][b] = min(rl[a+1][b],rl[a][b])
print(rl[h-1][w-1])

Submission status: Wrong Answer

Solution code:
import sys
input=sys.stdin.readline
from math import *
n,m=map(int,input().split())
a=[]
for i in range(n):
    p=list(input().rstrip())
    a.append(p)
p=[[0 for i in range(m+1)] for j in range(n+1)]
for i in range(n):
    for j in range(m):
        if i==0 and j==0 and a[i][j]=='#':
            p[i][j]=1
        elif i==0:
            p[i][j]=p[i][j-1]+int(a[i][j]=='#')
        elif j==0:
            p[i][j]=p[i-1][j]+int(a[i][j]=='#')
        else:
            p[i][j]=min(p[i][j-1],p[i-1][j])+int(a[i][j]=='#')
print(p[n-1][m-1])

Submission status: Wrong Answer

Solution code:
from bisect import *
from collections import *
from itertools import *
import functools
import sys
import math
from decimal import *
from copy import *
from heapq import *
from fractions import *
getcontext().prec = 30
MAX = sys.maxsize
MAXN = 500010
MOD = 10**9+7
spf = [i for i in range(MAXN)]
spf[0]=spf[1] = -1
def sieve():
    for i in range(2,MAXN,2):
        spf[i] = 2
    for i in range(3,int(MAXN**0.5)+1):
        if spf[i]==i:
            for j in range(i*i,MAXN,i):
                if spf[j]==j:
                    spf[j]=i
def fib(n,m):
    if n == 0:
        return [0, 1]
    else:
        a, b = fib(n // 2)
        c = ((a%m) * ((b%m) * 2 - (a%m)))%m
        d = ((a%m) * (a%m))%m + ((b)%m * (b)%m)%m
        if n % 2 == 0:
            return [c, d]
        else:
            return [d, c + d]

def charIN(x= ' '):
    return(sys.stdin.readline().strip().split(x))

def arrIN(x = ' '):
    return list(map(int,sys.stdin.readline().strip().split(x)))

def ncr(n,r):
    num=den=1
    for i in range(r):
        num = (num*(n-i))%MOD
        den = (den*(i+1))%MOD

    return (num*(pow(den,MOD-2,MOD)))%MOD

def flush():
    return sys.stdout.flush()

'''*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*'''

h,w = arrIN()
a = [input() for _ in range(h)]
dp = [[0 for i in range(w)] for j in range(h)]
dp[0][0] = int(a[0][0]!='.')
for i in range(1,w):
    dp[0][i] = dp[0][i-1]+int(a[0][i]!='.')
for i in range(1,h):
    dp[i][0] = dp[i-1][0]+int(a[i][0]!='.')

for i in range(1,h):
    for j in range(1,w):
        dp[i][j] = min(dp[i-1][j],dp[i][j-1])+int(a[i][j]!='.')

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

Submission status: Wrong Answer

Solution code:
import sys, re, os
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, radians
from itertools import permutations, combinations, product, accumulate
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
from fractions import gcd
 
def input(): return sys.stdin.readline().strip()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def S_MAP(): return map(str, input().split())
def LIST(): return list(map(int, input().split()))
def S_LIST(): return list(map(str, input().split()))
 
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
mod = 10 ** 9 + 7

H, W = MAP()
S = [input() for i in range(H)]

dp = [[0] * W for i in range(H)]

# 
if S[0][0] == ".":
    dp[0][0] = 0
else:
    dp[0][0] = 1

# tate
for h in range(1, H):
    if S[h][0] == "#":
        dp[h][0] += dp[h-1][0] + 1
    else:
        dp[h][0] = dp[h-1][0]
# yoko
for w in range(1, W):
    if S[0][w] == "#":
        dp[0][w] += dp[0][w-1] + 1
    else:
        dp[0][w] = dp[0][w-1]
# print(dp)
# exit()
for i in range(1, H):
    for j in range(1, W):
        # nokori
        if S[i][j] == ".":
            dp[i][j] = min(dp[i-1][j], dp[i][j-1])
        else:
            dp[i][j] = min(dp[i-1][j], dp[i][j-1]) + 1
print(dp[H-1][W-1])

Submission status: Wrong Answer

Solution code:
from collections import deque
from functools import lru_cache

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

if not (H == 3 and W == 3):
    exit()

minDist = [[10**10] * W for _ in range(H)]
que = deque([(0, 0, 0 if S[0][0] == '.' else 1, S[0][0] == '.')])

while que:
    h, w, dist, isWhite = que.popleft()

    if minDist[h][w] <= dist:
        continue
    minDist[h][w] = dist

    if h + 1 < H:
        isNextWhite = S[h + 1][w] == '.'
        if isWhite and not isNextWhite:
            que.append((h + 1, w, dist + 1, isNextWhite))
        else:
            que.appendleft((h + 1, w, dist, isNextWhite))
    if w + 1 < W:
        isNextWhite = S[h][w + 1] == '.'
        if isWhite and not isNextWhite:
            que.append((h, w + 1, dist + 1, isNextWhite))
        else:
            que.appendleft((h, w + 1, dist, isNextWhite))

ans = minDist[H - 1][W - 1]
print(ans)

Submission status: Wrong Answer

Solution code:
from collections import deque
h, w = map(int, input().split())
c = [list(input()) for _ in range(h)]
moves = ((1, 0), (0, 1))
sy = 0
sx = 0
ty = h-1
tx = w-1
st = 0
if c[0][0] == '#':
    st = 1
        
def bfs(sy, sx):
    dist = [[float('inf')]*w for _ in range(h)]
    dist[sy][sx] = 0 
    q = deque([[sy, sx]])
    while q:
        y, x = q.popleft()
        #print(q)
        for dy, dx in moves:
            ny = y + dy 
            nx = x + dx 
            if 0 <= ny < h and 0 <= nx < w and dist[ny][nx] == float('inf'):
                if c[ny][nx] == '#':
                    dist[ny][nx] = dist[y][x] + 1
                    q.append([ny, nx])
                else:
                    dist[ny][nx] = dist[y][x]
                    q.appendleft([ny, nx])
 
    return dist 
 
dist = (bfs(0, 0))
print(dist[ty][tx] + st)

Submission status: Wrong Answer

Solution code:
#!/usr/bin/env python3
H, W = map(int, input().split())
s = [0 for i in range(H)]
for i in range(H):
    s[i] = str(input())

l = [[0 for i in range(W)] for j in range(H)]

for i in range(H):
    for j in range(W):
        if s[i][j] == '#':
            l[i][j] = 1

dp = [[0 for i in range(W)] for j in range(H)]

dp[0][0] = l[0][0]

for i in range(1, W):
    dp[0][i] = dp[0][i-1] + l[0][i]
for i in range(1, H):
    dp[i][0] = dp[i-1][0] + l[i][0]

for i in range(1, H):
    for j in range(1, W):
        dp[i][j] = min(dp[i-1][j], dp[i][j-1]) + l[i][j]

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

Submission status: Wrong Answer

Solution code:
from math import *
n,m=map(int,input().split())
a=[]
dp=[]
for i in range(n):
	a.append(input())
	dp.append([1000000000]*m)

for i in range(m):
	if(i==0):
		if(a[0][i]=='#'):
			dp[0][i]=1
		else:
			dp[0][i]=0
	else:
		if(a[0][i]=='#'):
			dp[0][i]=dp[0][i-1]+1
		else:
			dp[0][i]=dp[0][i-1]
for i in range(1,n):
	if(a[i][0]=='#'):
		dp[i][0]=dp[i-1][0]+1
	else:
		dp[i][0]=dp[i-1][0]

for i in range(1,n):
	for j in range(1,m):
		if(a[i][j]=='#'):
			dp[i][j]=min(dp[i-1][j]+1,dp[i][j-1]+1)
		else:
			dp[i][j]=min(dp[i-1][j],dp[i][j-1])
print(dp[-1][-1])

Submission status: Wrong Answer

Solution code:
from collections import deque
from functools import lru_cache

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

if H == 3 and W == 3:
    exit()

minDist = [[10**10] * W for _ in range(H)]
que = deque([(0, 0, 0 if S[0][0] == '.' else 1, S[0][0] == '.')])

while que:
    h, w, dist, isWhite = que.popleft()

    if minDist[h][w] <= dist:
        continue
    minDist[h][w] = dist

    if h + 1 < H:
        isNextWhite = S[h + 1][w] == '.'
        if isWhite and not isNextWhite:
            que.append((h + 1, w, dist + 1, isNextWhite))
        else:
            que.appendleft((h + 1, w, dist, isNextWhite))
    if w + 1 < W:
        isNextWhite = S[h][w + 1] == '.'
        if isWhite and not isNextWhite:
            que.append((h, w + 1, dist + 1, isNextWhite))
        else:
            que.appendleft((h, w + 1, dist, isNextWhite))

ans = minDist[H - 1][W - 1]
print(ans)

Submission status: Wrong Answer

Solution code:
h, w = map(int, input().split())
s = [list(input()) for _ in range(h)]
dp = [[float('inf') for i in range(w)] for j in range(h)]
cnt = 0
for i in range(w):
    if s[0][i] == '#':
        cnt += 1
    dp[0][i] = cnt
cnt = 0
for i in range(h):
    if s[i][0] == '#':
        cnt += 1
    dp[i][0] = cnt
for i in range(1,h):
    for j in range(1,w):
        if s[i][j] == '#':
            dp[i][j] = min(dp[i-1][j] + 1, dp[i][j-1] + 1)
        else:
            dp[i][j] = min(dp[i-1][j], dp[i][j-1])
print(dp[h-1][w-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, last_b=False):
    if h < 0 or w < 0:
        return INF
    if h == 0 and w == 0:
        return int(S[0][0] == '#')
    b = bool(S[h][w] == '#')
    return min(solve(h - 1, w, last_b=b), solve(h, w - 1, last_b=b)) + ((not last_b and b))


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

Submission status: Wrong Answer

Solution code:
import sys
sys.setrecursionlimit(100000)

h,w=map(int,input().split())
INF=10**10
s_org=[list(input()) for _ in range(h)]
s=[[0]*w for _ in range(h)]
for i in range(h):
  for j in range(w):
    if s_org[i][j]=="#":
      s[i][j]=1
dp=[[-1]*w for _ in range(h)]
dp[0][0]=s[0][0]
def func(i,j):
  if dp[i][j]!=-1:return dp[i][j]
  if i<0 or j<0: return INF
  val=min(func(i,j-1)+s[i][j-1],func(i-1,j)+s[i-1][j])
  dp[i][j]=val
  return val
print(func(h-1,w-1))

Submission status: Wrong Answer

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

op = [[0 for i in range(W)] for j in range(H)]
op[0][0] = int(map[0][0] == '#')
for i in range(1, H):
    op[0][i] = op[0][i-1] + int(map[0][i] == '#')
    op[i][0] = op[i-1][0] + int(map[i][0] == '#')
for i in range(1, H):
    for j in range(1, W):
        op[i][j] = min(op[i-1][j], op[i][j-1]) + int(map[i][j] == '#')
print(op[H-1][W-1])

Submission status: Wrong Answer

Solution code:
from functools import lru_cache

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

@lru_cache(maxsize=20000)
def cost(r,c):
  b = (1 if Map[r-1][c-1]=='#' else 0)
  if r==1 and c==1:
    return b
  elif r==1:
    return cost(r,c-1)+b
  elif c==1:
    return cost(r-1,c)+b
  else:
    return min(cost(r-1,c), cost(r,c-1))+b

print(cost(H,W))

Submission status: Wrong Answer

Solution code:
h, w = map(int, input().split())
dat = []
res = []
for i in range(h):
    l = input()
    dat.append(l)
    res.append([999999] * w)
dx = [0, -1, 1, 0]
dy = [-1, 0, 0, 1]
res[0][0] = 0
for hh in range(h):
    for ww in range(w):
        if hh == 0 and ww == 0:
            pass
        elif hh == 0:
            res[hh][ww] = res[hh][ww-1]
        elif ww == 0:
            res[hh][ww] = res[hh-1][ww]
        else:
            res[hh][ww] = min(res[hh-1][ww], res[hh][ww-1])
        if dat[hh][ww] == "#":
            res[hh][ww] += 1
print(res[h-1][w-1])
#print(res)

Submission status: Wrong Answer

Solution code:
def dp(i, j, memo={}):
    if (i, j) in memo:
        return memo[i, j]
    elif i < 0 or j < 0:
        return float('inf')
    elif i == 0 and j == 0:
        return 1 if grid[i][j] == '#' else 0
    elif grid[i][j] == '#':
        res = memo[i, j] = 1 + min(dp(i - 1, j, memo), dp(i, j - 1, memo))
        return res
    else:
        res = memo[i, j] = min(dp(i - 1, j, memo), dp(i, j - 1, memo))
        return res


H, W = map(int, input().split())
grid = [[None] * W for _ in range(H)]
for i in range(H):
    for j, x in enumerate(input()):
        grid[i][j] = x


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