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 or aaa[i-1][j][1] == 1:
                        if aaa[i][j-1][1] == 0 or aaa[i][j-1][1] == 2:
                            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)
                            if aaa[i][j-1][0] > aaa[i-1][j][0]+1:
                                aaa[i][j][1] = 2
                            elif aaa[i][j-1][0] < aaa[i-1][j][0]+1:
                                aaa[i][j][1] = 1
                            else:
                                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)
                            if aaa[i][j-1][0] > aaa[i-1][j][0]+1:
                                aaa[i][j][1] = 2
                            elif aaa[i][j-1][0] < aaa[i-1][j][0]+1:
                                aaa[i][j][1] = 1
                            else:
                                aaa[i][j][1] = 3
                    elif aaa[i-1][j][1] == 2:
                        if aaa[i][j-1][1] == 0 or aaa[i][j-1][1] == 2:
                            aaa[i][j][0] = min(aaa[i][j][0],aaa[i][j-1][0]+1,aaa[i-1][j][0])
                            if aaa[i][j-1][0]+1 > aaa[i-1][j][0]:
                                aaa[i][j][1] = 2
                            elif aaa[i][j-1][0]+1 < aaa[i-1][j][0]:
                                aaa[i][j][1] = 1
                            else:
                                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])
                            if aaa[i][j-1][0] > aaa[i-1][j][0]:
                                aaa[i][j][1] = 2
                            elif aaa[i][j-1][0] < aaa[i-1][j][0]:
                                aaa[i][j][1] = 1
                            else:
                                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])
                            if aaa[i][j-1][0] > aaa[i-1][j][0]:
                                aaa[i][j][1] = 2
                            elif aaa[i][j-1][0] < aaa[i-1][j][0]:
                                aaa[i][j][1] = 1
                            else:
                                aaa[i][j][1] = 3
                    elif aaa[i-1][j][1] == 3:
                        if aaa[i][j-1][1] == 0 or aaa[i][j-1][1] == 2:
                            aaa[i][j][0] = min(aaa[i][j][0],aaa[i][j-1][0]+1,aaa[i-1][j][0])
                            if aaa[i][j-1][0]+1 > aaa[i-1][j][0]:
                                aaa[i][j][1] = 2
                            elif aaa[i][j-1][0]+1 < aaa[i-1][j][0]:
                                aaa[i][j][1] = 1
                            else:
                                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])
                            if aaa[i][j-1][0] > aaa[i-1][j][0]:
                                aaa[i][j][1] = 2
                            elif aaa[i][j-1][0] < aaa[i-1][j][0]:
                                aaa[i][j][1] = 1
                            else:
                                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])
                            if aaa[i][j-1][0] > aaa[i-1][j][0]:
                                aaa[i][j][1] = 2
                            elif aaa[i][j-1][0] < aaa[i-1][j][0]:
                                aaa[i][j][1] = 1
                            else:
                                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:
# -*- coding: utf-8 -*-
import bisect
import heapq
import math
import random
import sys
from collections import Counter, defaultdict, deque
from decimal import ROUND_CEILING, ROUND_HALF_UP, Decimal
from functools import lru_cache, reduce
from itertools import combinations, combinations_with_replacement, product, permutations
from operator import add, mul, sub

sys.setrecursionlimit(100000)
input = sys.stdin.readline
INF = 2**62-1

def read_int():
    return int(input())


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


def read_float():
    return float(input())


def read_float_n():
    return list(map(float, input().split()))


def read_str():
    return input().strip()


def read_str_n():
    return list(map(str, input().split()))


def error_print(*args):
    print(*args, file=sys.stderr)


def mt(f):
    import time

    def wrap(*args, **kwargs):
        s = time.time()
        ret = f(*args, **kwargs)
        e = time.time()

        error_print(e - s, 'sec')
        return ret

    return wrap


def BellmanFord(g, s):
    V = list(g.keys())
    for v in g.values():
        V.extend(list(v.keys()))
    V = set(V)

    dist = defaultdict(lambda: sys.maxsize)
    pred = defaultdict(lambda: -1)

    dist[s] = 0

    N = len(V)
    for i in range(N+1):
        for u in g:
            for v in g[u]:
                if dist[v] > dist[u] + g[u][v]:
                    if i == N:
                        return 'inf'
                    dist[v] = dist[u] + g[u][v]
                    pred[v] = u
    return dist



@mt
def slv(H, W, S):
    g = defaultdict(dict)
    for i in range(H):
        for j in range(W):
            for x, y in ((0, 1), (1, 0), (0, -1), (-1, 0)):
                if 0 <= i + x < H and 0 <= j+y < W:
                    if S[i][j] == '.' and S[i+x][j+y] == '#':
                        c = 1
                    else:
                        c = 0
                    g[(i, j)][(i+x, j+y)] = c
    g[0][(0, 0)] = 1 if S[0][0] == '#' else 0

    def bfs(s=0):
        q = deque()
        q.append(s)
        d = defaultdict(lambda: sys.maxsize)
        d[s] = 0
        while q:
            u = q.popleft()
            for v, c in g[u].items():
                if d[u] + c < d[v]:
                    d[v] = d[u] + c
                    if c == 0:
                        q.appendleft(v)
                    else:
                        q.append(v)

        return d

    return bfs()[(H-1, W-1)]


def main():
    H, W = read_int_n()
    S = [read_str() for _ in range(H)]
    print(slv(H, W, S))

    # H = 100
    # W = 100
    # S = [''.join(random.choices('.#', k=W)) for _ in range(H)]
    # print(slv(H, W, S))


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
# import numpy as np
# import math
# import copy
from collections import deque
import sys
input = sys.stdin.readline
# sys.setrecursionlimit(10000)


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

    INF = 10 ** 9 + 7

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

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

    for i in range(H):
        for j in range(W):
            cost = 0
            if s[i][j] == '#':
                cost += 1
            if (i == 0) & (j == 0):
                continue
            elif i == 0:
                dp[i][j] = min(dp[i][j],dp[i][j-1] + cost)
            elif j == 0:
                dp[i][j] = min(dp[i][j],dp[i-1][j] + cost)
            else:
                dp[i][j] = min(dp[i][j],dp[i][j-1] + cost)
                dp[i][j] = min(dp[i][j],dp[i-1][j] + cost)

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



main()

Submission status: Wrong Answer

Solution code:
def cost(nx, ny, mx, my):
    if f[ny][nx]=='.' and f[my][mx]=='#': return 1
    return 0
a = 0
H, W = [int(i) for i in input().split()]
N = H*W
f = [list(input()) for _ in range(H)]
if f[0][0]=='#':
    f[0][0]='.'
    a += 1
if f[H-1][W-1]=='#':
    f[H-1][W-1]='.'
    a += 1
G = [[] for _ in range(N)]
for h in range(H):
    for w in range(W):
        i = h*W+w
        # d
        if h<H-1:
            G[i].append((i+W, cost(w, h, w, h+1)))
        if w<W-1:
            G[i].append((i+1, cost(w, h, w+1, h)))

# G = [
#     [(1, 1), (3, 0)],
#     [(2, 0), (4, 0)],
#     [(5, 0)],
#     [(4, 1), (6, 1)],
#     [(5, 0), (7, 0)],
#     [(8, 0)],
#     [(7, 0)],
#     [(8, 0)],
#     [],
# ]
# print(G)
from collections import deque
# s: 開始頂点
s = 0
# N: 頂点数
# G: グラフ
# G[v][i] = (w, d): 辺v-wのコストは d (0 or 1)
# G = [[] for i in range(N)]
dist = [10**9] * N
S = deque([s])
T = deque()
dist[s] = 0

d = 0
while S:
    while S:
        v = S.popleft()
        for w, c in G[v]:
            if d+c < dist[w]:
                dist[w] = d+c
                if c:
                    T.append(w)
                else:
                    S.append(w)
    S, T = T, S
    d += 1

print(dist[-1]+a)

Submission status: Wrong Answer

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

dp=[[0]*W]*H
#print(s)

for h in range(H):
    for w in range(W):
        #print(s[h][w],dp[h][w])
        if s[h][w]==".":
            if h!=0 and w==0:
                dp[h][w]=dp[h-1][w]
            elif h==0 and w!=0:
                dp[h][w]=dp[h][w-1]
            elif h==0 and w==0:
                pass
            else:
                dp[h][w]=min(dp[h-1][w],dp[h][w-1])
        else:
            if s[h][w]=="#":
                if h!=0 and w==0:
                    dp[h][w]=dp[h-1][w]+1
                elif h==0 and w!=0:
                    dp[h][w]=dp[h][w-1]+1
                elif h==0 and w==0:
                    dp[h][w]=1
                else:
                    dp[h][w]=min(dp[h-1][w],dp[h][w-1])+1
        #print(s[h][w],dp[h][w])
#print(dp)
print(dp[H-1][W-1])

Submission status: Wrong Answer

Solution code:
H, W = map(int,input().split())
l = [list(input()) for _ in range(H)]
lmemo = [[-1] * W for _ in range(H)]
def DFS(r, c, cnt):
  if l[r][c] == '#':
    cnt += 1
  if r == H - 1 and c == W - 1:
    return cnt
  
  if c + 1 >= W:
    if lmemo[r + 1][c] != -1:
      cnt = lmemo[r + 1][c]
    else:
      cnt = DFS(r + 1, c, cnt)
      lmemo[r + 1][c] = cnt
  elif r + 1 >= H:
    if lmemo[r][c + 1] != -1:
      cnt = lmemo[r][c + 1]
    else:
      cnt = DFS(r, c + 1, cnt)
      lmemo[r][c + 1] = cnt
  else:
    if lmemo[r][c + 1] != -1:
      a = lmemo[r][c + 1]
    else:
      a = DFS(r, c + 1, cnt)
      lmemo[r][c + 1] = a
    if lmemo[r + 1][c] != -1:
      b = lmemo[r + 1][c]
    else:
      b = DFS(r + 1, c, cnt)
      lmemo[r + 1][c] = b
    cnt = min(a, b)
  return cnt

print(DFS(0, 0, 0))

Submission status: Wrong Answer

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

    now = [0,0]
    cnt = 0
    if s[0][0] == '#':
        cnt += 1
        # s[0][0] = '.'
    if s[h-1][w-1] == '#':
        cnt += 1
        # s[h-1][w-1] = '.'

    dp = [[-1] * w for i in range(h)]
    dp[0][0] = cnt

    for i in range(h):
        for j in range(w):
            tmp_up = 100000
            tmp_left = 100000
            change  = 0
            if s[i][j] == '#':
                change = 1
            if i == 0 and j == 0:
                continue
            if i != 0:
                if s[i-1][j] == '#' and s[i][j] == '#':
                    tmp_up = dp[i-1][j]
                else:
                    tmp_up = dp[i-1][j] + change
            if j != 0:
                if s[i][j-1] == '#' and s[i][j] == '#':
                    tmp_left = dp[i][j-1]
                else:

                    tmp_left = dp[i][j-1] + change

            dp[i][j] = min(tmp_up,tmp_left)


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

if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
# -*- coding: utf-8 -*-
"""
Created on Sat Mar 21 20:57:37 2020

@author: naoki
"""

import math
#f = open("C:/Users/naoki/Desktop/Atcoder/input.txt")
H,W = map(int,input().split())
tizu = [list(str(input().replace('\n',''))) for _ in range(H)]

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

if tizu[0][0] == "#":
    memo[0][0] = 1
else:
    memo[0][1] = 0

for i in range(1,H):
    if tizu[0][i] == tizu[0][i-1]:
        memo[0][i] = memo[0][i-1]
    else:
        memo[0][i] = memo[0][i-1] + 1

for k in range(1,H):
    for j in range(W):
        if tizu[k][j] == tizu[k-1][j]:
            memo[k][j] = memo[k-1][j]
        else:
            memo[k][j] = memo[k-1][j] + 1
    for j in range(1,W):
        if tizu[k][j] == tizu[k][j-1]:
            temp = memo[k][j-1]
        else:
            temp = memo[k][j-1] + 1
        if temp < memo[k][j]:
            memo[k][j] = temp
for k in range(H):
    for j in range(W):
        memo[k][j] = int(math.ceil(memo[k][j]/2))
print(memo[-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] == "#":
        if s[1][i] != "#":
            s2[0][i + 2] = s2[0][i + 1] + 1
        else:
            s2[0][i + 2] = s2[0][i + 1]
    else:
        s2[0][i + 2] = s2[0][i + 1]
for i in range(h - 1):
    if s[i + 1][1] == "#":
        if s[i][1] != "#":
            s2[i + 2][0] = s2[i + 1][0] + 1
        else:
            s2[i + 2][0] = s2[i + 1][0]
    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:
            if s[i][j + 1] == "#":
                if s[i + 1][j] == "#":
                    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)
            else:
                if s[i + 1][j] == "#":
                    s2[i + 1][j + 1] = min(s2[i][j + 1] + 1, s2[i + 1][j])
                else:
                    s2[i + 1][j + 1] = min(s2[i][j + 1], s2[i + 1][j] + 1) + 1
print(s2[h][w])

Submission status: Wrong Answer

Solution code:
from collections import deque
# 計算量O(|V|)
# G[v]: 頂点vに隣接する頂点list
# V: 頂点数
D = ((1,0), (0,1), (-1,0), (0, -1))
INF = 10 ** 10


def BFS(H, W, S):
    dist = [[INF] * W for _ in range(H)]
    que = deque([(0,0)])
    dist[0][0] = 0

    while que:
        v = que.popleft()
        #print(dist)
        for d in D:
            w = (v[0]+d[0], v[1]+d[1])
            if 0 <= w[0] < H and 0 <= w[1] < W:
                if dist[w[0]][w[1]] == INF:
                    que.append(w)
                if S[v[0]][v[1]] != S[w[0]][w[1]]:
                    dist[w[0]][w[1]] = min(dist[v[0]][v[1]]+1, dist[w[0]][w[1]])
                else:
                    dist[w[0]][w[1]] = dist[v[0]][v[1]]

    return dist[-1][-1]


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

if S[0][0] == "#":
    ans = BFS(H, W, S)// 2 + 1
    print(ans)
else:
    ans = BFS(H, W, S) // 2
    print(ans)

Submission status: Wrong Answer

Solution code:
import collections
h, w = [int(_) for _ in input().split()]
S = [list('.' * (w + 1))] + [['.'] + list(input()) for _ in range(h)]
B = [[99999] * (w + 1) for _ in range(h + 1)]
B[1][1] = 0 if S[1][1] == '.' else 1
cand = collections.deque([(1, 2), (2, 1)])
while cand:
    x, y = cand.popleft()
    if B[x][y] == 99999:
        B[x][y] = min(B[x][y - 1] + (S[x][y] == '#' != S[x][y - 1]),
                      B[x - 1][y] + (S[x][y] == '#' != S[x - 1][y]))
        if x < h:
            cand += [(x + 1, y)]
        if y < w:
            cand += [(x, y + 1)]
print(B)

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

def bfs(sy, sx):
    dist = [[float('inf')]*w for _ in range(h)]
    dist[0][0] = 0
    if c[0][0] == '#':
        dist[0][0] = 1
    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] == '#' and c[y][x] != '#':
                    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])

Submission status: Wrong Answer

Solution code:
h,w= [int(x) for x in input().split()]
maze = [[] for _ in range(h)]
for i in range(h):
  c = input()
  for j in range(w):
    maze[i].append(c[j])
#print(maze)

maps = [[100 for _ in range(w)] for _ in range(h)]

if maze[0][0] == ".":
  maps[0][0] = 0
else:
  maps[0][0] = 1

count = 0
for i in range(1,h):
  if maze[i][0] ==".":
    maps[i][0] = maps[i-1][0]
  else:
    maps[i][0] = maps[i-1][0]+1
    
for i in range(1,w):
  if maze[0][i] ==".":
    maps[0][i] = maps[0][i-1]
  else:
    maps[0][i] = maps[0][i-1]+1

#for i in maps:
#  print(i)
for i in range(1,h):
  for j in range(1,w):
    if maze[i][j] == ".":
      t = 0
    else:
      t = 1
    maps[i][j] = min(maps[i-1][j],maps[i][j-1]) + t
print(maps[-1][-1])

Submission status: Wrong Answer

Solution code:
import heapq
def A():
    H, W = map(int, input().split())
    maze = []
    for i in range(H):
        maze.append(input())
    # if maze[0][0] == '.':
    #     q = [[0, (0, 0)]]
    # else:
    #     q = [[1, (0, 0)]]
    # heapq.heapify(q)
    # while q:
    #     #print(q)
    #     cost, cur = heapq.heappop(q)
    #     if cur[0] == H-1 and cur[1] == W-1:
    #         print(cost)
    #         return
    #     for direction in [(0, 1), (1, 0)]:
    #         new_r, new_c = cur[0]+direction[0], cur[1]+direction[1]
    #         if new_r >= 0 and new_c >= 0 and new_r < H and new_c < W:
    #             if maze[new_r][new_c]=='.':
    #                 heapq.heappush(q, [cost, (new_r, new_c)])
    #             else:
    #                 heapq.heappush(q, [cost+1, (new_r, new_c)])
    memo = [[float('inf') for i in range(W)] for j in range(H)]
    if maze[H-1][W-1] == '.':
        memo[H-1][W-1] = 0
    else:
        memo[H-1][W-1] = 1
    def dfs(r, c):
        if memo[r][c] < float('inf'):
            return memo[r][c]
        if maze[r][c] == '.':
            cur_cost = 0
        else:
            cur_cost = 1
        minimum_next = float('inf')
        if r+1 < H:
            minimum_next = dfs(r+1, c)
        if c+1 < W:
            minimum_next = min(minimum_next, dfs(r, c+1))
        res = cur_cost+minimum_next
        memo[r][c] = res
        return res
    print(dfs(0, 0))

A()

Submission status: Wrong Answer

Solution code:
from collections import deque
import sys
sys.setrecursionlimit(10 ** 9)
# import numpy as np
# 答えの提出の時にi+1とj+1は忘れないように
h, w = map(int, input().split())
maze = [[-1 for i in range(w)] for j in range(h)]

INF = h*w
countBlack = [[INF for i in range(w)] for j in range(h)]

for i in range(h):
    maze[i] = input()

sx=0
sy=0
queue = deque()
queue.append((sy,sx))
countBlack[sy][sx] = int(maze[0][0]== '#')

while queue:
    y, x = queue.popleft()
    for i,j in [(1,0),(0,1)]:
        ny, nx = y+i, x+j
        if 0 <= nx < w and 0 <= ny < h:
            if countBlack[y][x]+1 > countBlack[ny][nx]:
                continue
            if maze[ny][nx] == '#':
                countBlack[ny][nx] = countBlack[y][x] + 1
            else:
                countBlack[ny][nx] = countBlack[y][x]
            if ny != h-1 or nx != w-1:
                queue.append((ny, nx))

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

Submission status: Wrong Answer

Solution code:
import numpy as np

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

s=[]

for i in range(H):
    s.append(str(input()))
    
# s[i][0] to s[i][W-1] 

pat_mat=[]

for i in range(H):
    if i ==0:
        if s[0][0] == ".":
            pat_mat.append([0])
        else:
            pat_mat.append([1])
        if W>1:
            for j in range(1,W):
                if s[0][j] == ".":
                    pat_mat[0].append(pat_mat[0][j-1])
                else:

                    pat_mat[0].append(int(pat_mat[0][j-1]+1))
    else:
        if s[i][0] == ".":
            pat_mat.append([pat_mat[i-1][0]])
        else:
            pat_mat.append([pat_mat[i-1][0]+1])
        if W>1:
            for j in range(1,W):
                if s[i][j] == ".":
                    pat_mat[i].append(min(pat_mat[i][j-1],pat_mat[i-1][j]))
                else:

                    pat_mat[i].append(min(pat_mat[i][j-1]+1,pat_mat[i-1][j]+1))
                    
print(int(pat_mat[H-1][W-1]))

Submission status: Wrong Answer

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

H, W = map(int, input().split())

s = []

for _ in range(H):
    s.append(input().strip())

r = 0
c = 0
now = deque()
now.append([r,c])
if s[0][0] == '#':
    cost = 1
else:
    cost = 0

while True:
    cur = now.popleft()
    r = cur[0]
    c = cur[1]
    if r == H-1 and c == W-1:
        break
    if c < W-1 and s[r][c + 1] == '.':
        now.append([r,c+1])
    if r < H-1 and s[r + 1][c] == '.':
        now.append([r+1,c])
    if now == deque():
        flag = False
        if c < W-1 and s[r][c + 1] == '#':
            cost += 1
            flag = True
            now.append([r,c+1])
        if r < H-1 and s[r + 1][c] == '#':
            if not flag:
                cost += 1
            now.append([r+1,c])

print(cost)

Submission status: Wrong Answer

Solution code:
h, w = map(int, input().split())
a = []
for _ in range(h):
    # for __ in range(w):
    #a.append(list(map(str, input().rstrip().split())))
    a.append(input())
#for i in range(h):
    #print(a[i])

b = [[0 for i in range(w + 1)] for j in range(h + 1)]
temp = 0
for i in range(h):
    s = str(a[i])
    #s = a[i]
    #print(s)
    for j in range(len(s)):
        # print(a[i][j])

        if s[j] == '.':
            temp = 0
        elif s[j] == '#':
            temp = 1
        
        #print(temp)
        if i == 0:
            b[i + 1][j + 1] = b[i + 1][j] + temp
        elif j == 0:
            b[i + 1][j + 1] = b[i][j + 1] + temp
        else:
            b[i + 1][j + 1] = min(b[i][j + 1], b[i + 1][j]) + temp
print(b[h][w])

Submission status: Wrong Answer

Solution code:
H,W=map(int,input().split())
L=[]
l=["*" for i in range(W+2)]
L.append(l)
for i in range(H):
    s=["*"]+list(input())+["*"]
    L.append(s)
L.append(l)
#print(L)

X=[1,-1,0,0]
Y=[0,0,1,-1]

cnt=0
if L[1][1]=="#":
    cnt+=1
    Q=[[1,1]]
    for i in range(10**6):
        if i==len(Q):
            break
        L[Q[i][0]][Q[i][1]]="."
        for j in range(4):
            if L[Q[i][0]+X[j]][Q[i][1]+Y[j]]=="#":
                Q.append([Q[i][0]+X[j],Q[i][1]+Y[j]])
if L[H][W]=="#":
    cnt+=1
    Q=[[H,W]]
    for i in range(10**6):
        if i==len(Q):
            break
        L[Q[i][0]][Q[i][1]]="."
        for j in range(4):
            if L[Q[i][0]+X[j]][Q[i][1]+Y[j]]=="#":
                Q.append([Q[i][0]+X[j],Q[i][1]+Y[j]])
C=[[10000 for i in range(W+2)]for j in range(H+2)]
Q=[(0,1,1)]
#print(L)
import heapq
heapq.heapify(Q)
for i in range(10**6):
    if len(Q)==0:
        break
    d,h,w=Q[0]
    heapq.heappop(Q)
    if C[h][w]==10000:
        C[h][w]=d
        for j in range(4):
            if C[h+X[j]][w+Y[j]]==10000 and L[h+X[j]][w+Y[j]]!="*":
                if L[h+X[j]][w+Y[j]]=="." and L[h][w]=="#":
                    heapq.heappush(Q,(d+1,h+X[j],w+Y[j]))
                else:
                    heapq.heappush(Q,(d,h+X[j],w+Y[j]))
print(C[H][W]+cnt)
#print(cnt)
#print(L)
#print(C)
#print(Q)

Submission status: Wrong Answer

Solution code:
# import numpy as np
# import math
# import copy
from collections import deque
import sys
input = sys.stdin.readline
# sys.setrecursionlimit(10000)


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

    INF = 10 ** 9 + 7

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

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

    for i in range(H):
        for j in range(W):
            if (i == 0) & (j == 0):
                continue
            cost = 0
            if s[i][j] == '#':
                cost += 1
            dp[i][j] = min(dp[i][j],dp[i][j-1] + cost)
            dp[i][j] = min(dp[i][j],dp[i-1][j] + cost)

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



main()

Submission status: Wrong Answer

Solution code:
from collections import deque
# 計算量O(|V|)
# G[v]: 頂点vに隣接する頂点list
# V: 頂点数
D = ((1,0), (0,1), (-1,0), (0, -1))
INF = 10 ** 10


def BFS(H, W, S):
    dist = [[INF] * W for _ in range(H)]
    que = deque([(0,0)])
    dist[0][0] = 0

    while que:
        v = que.popleft()
        #print(dist)
        for d in D:
            w = (v[0]+d[0], v[1]+d[1])
            if 0 <= w[0] < H and 0 <= w[1] < W:
                if dist[w[0]][w[1]] == INF:
                    que.append(w)
                if S[v[0]][v[1]] != S[w[0]][w[1]]:
                    dist[w[0]][w[1]] = min(dist[v[0]][v[1]]+1, dist[w[0]][w[1]])
                else:
                    dist[w[0]][w[1]] = dist[v[0]][v[1]]

    print(dist)
    return dist[-1][-1]


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

if S[0][0] == "#":
    ans = BFS(H, W, S)// 2 + 1
    print(ans)
else:
    ans = BFS(H, W, S) // 2
    print(ans)

Submission status: Wrong Answer

Solution code:
# -*- coding: utf-8 -*-
h, w = map(int, input().split())
s = [0]*h
dp = [[0 for i in range(w)] for i in range(h)]

for i in range(h):
    s[i] = input()

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

for j in range(1, w):
    if s[0][j] == "#":
        dp[0][j] = dp[0][j-1] + 1
    else:
        dp[0][j] = dp[0][j-1]

for i in range(1, h):
    if s[i][0] == "#":
        dp[i][0] = dp[i-1][0] + 1
    else:
        dp[i][0] = dp[i-1][0]

for i in range(1, h):
    for j in range(1,w):
        if s[i][j] == "#":
            dp[i][j] = min(dp[i-1][j], dp[i][j-1]) + 1
        else:
            dp[i][j] = min(dp[i-1][j], dp[i][j-1])

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

Submission status: Wrong Answer

Solution code:
def main():
    import collections
    H, W = map(int, input().split())
    s = [list(input()) for i in range(H)]
    t = [[0]*W for i in range(H)]
    if s[0][0] == "#":
        t[0][0] = 1

    for i in range(1, W):
        t[0][i] = t[0][i-1]
        if s[0][i] == "#":
            t[0][i] += 1
    for i in range(1, H):
        t[i][0] = t[i-1][0]
        if s[i][0] == "#":
            t[i][0] += 1

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

    print(t[-1][-1])


main()