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
input = sys.stdin.readline

H, W = map(int, input().split())
field = ['' for _ in range(H)]
seen = [[False for _ in range(W)] for _ in range(H)]
seen_black = [[False for _ in range(W)] for _ in range(H)]

dx = [1, 0, -1, 0]
dy = [0, 1, 0, -1]
stop = (0, 0)
next_start = (0,0)
def dfs(h, w):
    global stop
    seen[h][w] = True
    for dir in range(4):
        nh = h + dx[dir]
        nw = w + dy[dir]
        
        if nh < 0 or nh >= H or nw < 0 or nw >= W:
            continue
        if field[nh][nw] == '#':
            step = max(stop[0]+stop[1], nh+nw)
            if step != stop[0]+stop[1]:stop = (nh, nw)
            continue
        if seen[nh][nw] == True:
            continue
        dfs(nh, nw)
def dfs_black(h, w):
    global next_start
    seen_black[h][w] = True
    for dir in range(4):
        nh = h + dx[dir]
        nw = w + dy[dir]
        
        if nh < 0 or nh >= H or nw < 0 or nw >= W:
            continue
        if field[nh][nw] == '.':
            step = max(next_start[0]+next_start[1], nh+nw)
            if step != next_start[0]+next_start[1]:next_start = (nh, nw)
            continue
        if seen_black[nh][nw] == True:
            continue
        dfs(nh, nw)    

for h in range(H):
    field[h] = input().rstrip("\r\n")

sh, sw, gh, gw = 0, 0, H-1, W-1
ans = 0
is_next = True
if field[sh][sw] == "#":
    is_next = False
else:
    is_next = True

while seen[gh][gw] != True:
    if is_next:
        dfs(sh,sw)
        sh, sw = stop
        is_next = False
    else:
        ans += 1
        if sh == gh and sw == gw:
            break
        dfs_black(sh,sw)
        sh, sw = next_start
        is_next = True
print(ans)

Submission status: Wrong Answer

Solution code:
from sys import stdin,setrecursionlimit
setrecursionlimit(10**6) 
h,w = map(int,stdin.readline().rstrip().split())
li = [stdin.readline().rstrip() for _ in range(h)]
inf = 10**10
lin = [False]*(h+w-1)
for i in range(h):
    for j in range(w):
        now = i+j
        if li[i][j] == ".":
            lin[now] = True
point = 0
for i in lin:
    if not i:
        point += 1
print(point)

Submission status: Wrong Answer

Solution code:
H,W=map(int,input().split())
table=[[0]*W for i in range(H)]
for i in range(H):
  s=str(input())
  for j in range(W):
    if s[j]=='#':
      table[i][j]=1
    else:
      pass
for i in range(H):
  for j in range(W):
    if i==0:
      if j==0:
        pass
      else:
        table[i][j]+=table[i][j-1]
    else:
      if j>=1:
        x,y=table[i-1][j],table[i][j-1]
        table[i][j]+=min(x,y)
      else:
        table[i][j]+=table[i-1][j]
ans=table[H-1][W-1]
print(ans)

Submission status: Wrong Answer

Solution code:
H, W = map(int, input().split())
field = [list(input()) for _ in range(H)]
from functools import lru_cache
import sys
sys.setrecursionlimit(10**9)

count = [float('inf')]
@lru_cache(maxsize=10**9)
def dfs(x,y,cnt):
    if x==H-1 and y==W-1:
        if count[0] > cnt:
            count[0] = cnt
        return
    if y < W-1:
        if field[x][y]=='#':
            cnt += 1
        dfs(x,y+1,cnt)
    if x < H-1:
        if field[x][y]=='#':
            cnt += 1
        dfs(x+1,y,cnt)


if field[0][0]=='#':
    dfs(0,0,1)
else:
    dfs(0,0,0)

print(count[0])

Submission status: Wrong Answer

Solution code:
import sys
input = sys.stdin.readline

n, m = map(int, input().split())
counts = [0]
dp = [[0 for i in range(m)]for j in range(n)]
grid = [[0 for i in range(m)]for j in range(n)]
for row in range(n):
    temp = input()
    for col in range(m):
        grid[row][col] = temp[col]

if grid[0][0] == '.':
    dp[0][0] = 1
else:
    dp[0][0] = 0
for i in range(n):
    for j in range(m):
        if i == 0:
            if grid[i][j] == '.':
                dp[i][j] = dp[i][j-1] + 1
            else:
                dp[i][j] = dp[i][j - 1]
        if j == 0:
            if grid[i][j] == '.':
                dp[i][j] = dp[i-1][j] + 1
            else:
                dp[i][j] = dp[i-1][j]
        else:
            if grid[i][j] == '.':
                dp[i][j] = max(dp[i][j-1], dp[i-1][j]) + 1
            else:
                dp[i][j] = max(dp[i][j-1], dp[i-1][j])
print(n+m-1-dp[n-1][m-1])

Submission status: Wrong Answer

Solution code:
# input
H, W = [int(_) for _ in input().split(' ')]
cheese = [[float(1) if a=='.' else float('inf') for a in input()] for _ in range(H)]
#print(H,W)
#print(cheese)
START = [0,0]
START.append(0)
GOAL = [H-1, W-1]

#process
point = []
point.insert(0, START)
minimum = float('inf')

while True:
    #print(point)
    # que has element or not
    if len(point)==0:
        break
    # break condition
    h, w, count = point.pop()
    if h==GOAL[0] and w==GOAL[1]:
        if minimum>count:
            minimum = count
        if count==0:
            break
    if not minimum==float('inf'):
        #print('nyan')
        for i,p in enumerate(point):
            if p[2]>=minimum:
                point.pop(i)
    # explore
    for i in range(0,2):
        h_, w_, count_ = h + [1,0][i], w + [0,1][i], count
        if h_>=0 and h_<H and w_>=0 and w_<W:
            if cheese[h_][w_]==float('inf'):
                count_+=1
            point.insert(0, [h_,w_,count_])

print(minimum)

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=True) + (not b) if last_b else INF,
        solve(h, w - 1, last_b=True) + (not b) if last_b else INF,
        solve(h - 1, w, last_b=False)+ b,
        solve(h, w - 1, last_b=False)+b ,
    )


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

Submission status: Wrong Answer

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

count = [ [0 for _ in range(w)] for _ in range(h) ]

for h_i in range(h):
    for w_i in range(w):
        c = 1 if square[h_i][w_i] == '#' else 0
        if h_i == 0 and w_i == 0:
            if square[0][0] == '#':
                count[0][0] = 1
        elif h_i == 0:
            count[h_i][w_i] = c + count[h_i][w_i - 1]
        elif w_i == 0:
            count[h_i][w_i] = c + count[h_i - 1][w_i]
        else:
            count[h_i][w_i] = c + min(count[h_i - 1][w_i], count[h_i][w_i - 1])

print(count[-1][-1])

Submission status: Wrong Answer

Solution code:
#!/usr/bin/env python3
from collections import defaultdict,deque
from heapq import heappush, heappop
from bisect import bisect_left, bisect_right
import sys, random, itertools, math
sys.setrecursionlimit(10**5)
input = sys.stdin.readline
sqrt = math.sqrt
def LI(): return list(map(int, input().split()))
def LF(): return list(map(float, input().split()))
def LI_(): return list(map(lambda x: int(x)-1, input().split()))
def II(): return int(input())
def IF(): return float(input())
def LS(): return list(map(list, input().split()))
def S(): return list(input().rstrip())
def IR(n): return [II() for _ in range(n)]
def LIR(n): return [LI() for _ in range(n)]
def FR(n): return [IF() for _ in range(n)]
def LFR(n): return [LI() for _ in range(n)]
def LIR_(n): return [LI_() for _ in range(n)]
def SR(n): return [S() for _ in range(n)]
def LSR(n): return [LS() for _ in range(n)]
mod = 1000000007
inf = float("INF")

#solve
def solve():
    h,w = LI()
    s = SR(h)
    b = [[inf] * w for i in range(h)]
    q = [(s[0][0] == "#", (0, 0))]
    b[0][0] = s[0][0] == "#"
    while q:
        p, xy = heappop(q)
        y, x = xy
        z = s[y][x]
        if z == ".":
            for mx, my in [(0, 1), (0, -1), (-1, 0), (1, 0)]:
                txm = mx + x
                tym = my + y
                xm = txm
                ym = tym
                if 0 <= xm < w and 0 <= ym < h:
                    for xm in range(xm, w):
                        if s[ym][xm] == z:
                            if b[ym][xm] > p:
                                b[ym][xm] = p
                                heappush(q, (p, (ym, xm)))
                            else:
                                break
                        else:
                            break
                    xm = txm
                    ym = tym
                    for xm in range(xm, -1, -1):
                        if s[ym][xm] == z:
                            if b[ym][xm] > p:
                                b[ym][xm] = p
                                heappush(q, (p, (ym, xm)))
                            else:
                                break
                        else:
                            break
                    xm = txm
                    ym = tym
                    for ym in range(ym, h):
                        if s[ym][xm] == z:
                            if b[ym][xm] > p:
                                b[ym][xm] = p
                                heappush(q, (p, (ym, xm)))
                            else:
                                break
                        else:
                            break
                    xm = txm
                    ym = tym
                    for ym in range(ym, -1, -1):
                        if s[ym][xm] == z:
                            if b[ym][xm] > p:
                                b[ym][xm] = p
                                heappush(q, (p, (ym, xm)))
                            else:
                                break
                        else:
                            break
                    xm = txm
                    ym = tym
                    for xm in range(xm, w):
                        if s[ym][xm] != z:
                            if b[ym][xm] > p + 1:
                                b[ym][xm] = p + 1
                                heappush(q, (p + 1, (ym, xm)))
                        else:
                            break
                    xm = txm
                    ym = tym
                    for ym in range(ym, h):
                        if s[ym][xm] != z:
                            if b[ym][xm] > p + 1:
                                b[ym][xm] = p + 1
                                heappush(q, (p + 1, (ym, xm)))
                        else:
                            break
                    xm = txm
                    ym = tym
                    for xm in range(xm, -1, -1):
                        if s[ym][xm] != z:
                            if b[ym][xm] > p + 1:
                                b[ym][xm] = p + 1
                                heappush(q, (p + 1, (ym, xm)))
                        else:
                            break
                    xm = txm
                    ym = tym
                    for ym in range(ym, -1, -1):
                        if s[ym][xm] != z:
                            if b[ym][xm] > p + 1:
                                b[ym][xm] = p + 1
                                heappush(q, (p + 1, (ym, xm)))
                        else:
                            break
        else:
            for mx, my in [(0, 1), (0, -1), (-1, 0), (1, 0)]:
                txm = mx + x
                tym = my + y
                xm = txm
                ym = tym
                if 0 <= xm < w and 0 <= ym < h:
                    for xm in range(xm, w):
                        if s[ym][xm] == z:
                            if b[ym][xm] > p:
                                b[ym][xm] = p
                                heappush(q, (p, (ym, xm)))
                            else:
                                break
                        else:
                            if b[ym][xm] > p:
                                b[ym][xm] = p
                                heappush(q, (p, (ym, xm)))
                            break
                    xm = txm
                    ym = tym
                    for xm in range(xm, -1, -1):
                        if s[ym][xm] == z:
                            if b[ym][xm] > p:
                                b[ym][xm] = p
                                heappush(q, (p, (ym, xm)))
                            else:
                                break
                        else:
                            if b[ym][xm] > p:
                                b[ym][xm] = p
                                heappush(q, (p, (ym, xm)))
                            break
                    xm = txm
                    ym = tym
                    for ym in range(ym, h):
                        if s[ym][xm] == z:
                            if b[ym][xm] > p:
                                b[ym][xm] = p
                                heappush(q, (p, (ym, xm)))
                            else:
                                break
                        else:
                            if b[ym][xm] > p:
                                b[ym][xm] = p
                                heappush(q, (p, (ym, xm)))
                            break
                    xm = txm
                    ym = tym
                    for ym in range(ym, -1, -1):
                        if s[ym][xm] == z:
                            if b[ym][xm] > p:
                                b[ym][xm] = p
                                heappush(q, (p, (ym, xm)))
                            else:
                                break
                        else:
                            if b[ym][xm] > p:
                                b[ym][xm] = p
                                heappush(q, (p, (ym, xm)))
                            break
                

    print(b[-1][-1] if b[-1][-1] else 0)

    return


#main
if __name__ == '__main__':
    solve()

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]
    if l[0][i] != l[0][i-1]:
        dp[0][i] += 1
for i in range(1, H):
    dp[i][0] = dp[i-1][0]
    if l[i][0] != l[i-1][0]:
        dp[i][0] += 1

for i in range(1, H):
    for j in range(1, W):
        a, b = dp[i-1][j], dp[i][j-1]
        if l[i-1][j] != l[i][j]:
            a += 1
        if l[i][j-1] != l[i][j]:
            b += 1
        dp[i][j] = min(a, b)
if l[0][0] == l[H-1][W-1] == 0:
    print(dp[H-1][W-1] // 2)
elif l[0][0] + l[H-1][W-1] == 1:
    print(dp[H-1][W-1])
else:
    print(max(1, (dp[H-1][W-1] + 1)//2))

Submission status: Wrong Answer

Solution code:
import itertools
k = input()

heigh, wight = k.split(' ')


list_ = []
for i in range(0, int(heigh)):
  f = input()
  list_.append([g for g in f.replace('#', '黒').replace('.', '白')])

list_.reverse()

sg = 'a' * (int(heigh) - 1) + 'b' * (int(wight) -1)
l_ = list(sg)



result_counts = []

for l__ in list(itertools.permutations(l_)):
    count = 0
    x, y = 0, 0
    now = list_[y][x]
    for s in l__:
        if s == 'a':
            x = x + 1
        else:
            y = y + 1
        next_ = list_[y][x]
        if now == '黒' and next_== '白':
            count += 1
        now = next_
    if now == '黒':
        count += 1
    result_counts.append(count)

print(min(result_counts))

Submission status: Wrong Answer

Solution code:
input = raw_input
h, w = map(int, input().split(" "))
gh = h - 1
gw = w - 1

#dot_coords = []
#for hi in range(h):
#    wi = 0
#    for c in input():
#        if c == ".":
#            dot_coords.append((wi, hi))
#        wi += 1
        
maps = [input() for _ in range(h)]
num_maps = [[None for _ in range(w)] for _ in range(h)]

count = 0
def find(sx, sy, cur_cost):
    next_cost_coord = []
    global count
    num_r = 1
    found = False
    routes = [(sx, sy)]
    num_maps[sy][sx] = cur_cost
    count += 1

    pre = False
    if sx == 1 and sy == 1:
        pre = True

    while num_r >= 1 and not found:
        x, y = routes[0]
        routes = routes[1:]
        num_r -= 1

        for nx, ny in [(x+1, y), (x, y+1)]:
            if pre:
                pass
                #print("lennummap", len(num_maps))
                #print(num_maps, ny, nx)
                #print(x, y, nx, ny, num_maps[ny][nx], gw, gh, "routes", routes)

            if nx <= gw and ny <= gh and num_maps[ny][nx] is None:
                #print(x, y, nx, ny, num_maps[ny][nx], gw, gh, "routes", routes)
                #print("nxny", nx, ny, cur_cost)
                if maps[ny][nx] == ".":
                    num_maps[ny][nx] = cur_cost
                    if nx == gw and ny == gh:
                        found = True
                    else:
                        routes.append((nx, ny))
                        num_r += 1
                elif num_maps[ny][nx] is None:
                    next_cost_coord.append((nx, ny))
    return next_cost_coord, found

cur_coords = [(0, 0)]
if maps[0][0] == ".":
    cur_cost = 0
else:
    cur_cost = 1

while True:   
    #print("cur_cost", cur_cost, "cur_coords", cur_coords)
    next_coords = []
    for sx, sy in cur_coords:
        cur_nc_coord, found = find(sx, sy, cur_cost)
        next_coords += cur_nc_coord
        #print(cur_nc_coord, num_maps)
        found = num_maps[gh][gw] is not None
        if found:
            break
    #print("cur_cost", cur_cost,"num_maps", num_maps)
    if found:
        break
    else:
        #print("test")
        cur_coords = next_coords
        assert len(cur_coords) >= 1
        cur_cost += 1
        #print("cur_cost", cur_cost)

out = num_maps[gh][gw]
print(out)
#print(count)

Submission status: Wrong Answer

Solution code:
def dp(i, j, black='#', memo={}):
    if (i, j, black) in memo:
        return memo[i, j, black]
    elif i < 0 or j < 0:
        return float('inf')
    elif i == 0 and j == 0:
        return 1 if grid[i][j] == black else 0
    elif grid[i][j] == black:
        not_flip = 1 + min(dp(i - 1, j, black, memo), dp(i, j - 1, black, memo))
        flip = 1 + min(dp(i - 1, j, '.', memo), dp(i, j - 1, '.', memo))
        res = min(not_flip, flip)
        memo[i, j, black] = res
        return res
    else:
        res = min(dp(i - 1, j, black, memo), dp(i, j - 1, black, memo))
        memo[i, j, black] = res
        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

memo = {}
print(min(dp(H - 1, W - 1, '#', memo), 1 + dp(H - 1, W - 1, '.', memo)))

Submission status: Wrong Answer

Solution code:
import sys
import copy
sys.setrecursionlimit(100000)
h, w = map(int, input().split())
mapping = [0]*h
for i in range(h):
  mapping[i] = input()
ans = [[[-1, -1, -1] for j in range(w)] for i in range(h)]
def dp(i, j):
  if ans[i][j][0] >= 0:
    pass
  else:
    if i == 0 and j == 0:
      if mapping[i][j] == ".":
        ans[i][j] = [0, 0, 0]
      else:
        ans[i][j] = [1, 0, 0]
    elif i == 0:
      if mapping[i][j] == ".":
        ans[i][j] = dp(i, j-1)
        ans[i][j][1], ans[i][j][2] = i, j
      else:
        ans[i][j] = dp(i, j-1)
        if mapping[i][j-1] == ".":
          ans[i][j][1], ans[i][j][2] = i, j
          ans[i][j][0] += 1
    elif j == 0:
      if mapping[i][j] == ".":
        ans[i][j] = dp(i-1, j)
        ans[i][j][1], ans[i][j][2] = i, j
      else:
        ans[i][j] = dp(i-1, j)
        if mapping[i-1][j] == ".":
          ans[i][j][1], ans[i][j][2] = i, j
          ans[i][j][0] += 1
    else:
      if mapping[i][j] == ".":
        k = min([dp(i-1, j)[0], dp(i, j-1)[0]])
        ans[i][j] = [k, i, j]
      else:
        p = copy.deepcopy(dp(i-1, j))
        if mapping[i-1][j] == ".":
          p[1], p[2] = i, j
          p[0] += 1
        q = copy.deepcopy(dp(i, j-1))
        if mapping[i][j-1] == ".":
          q[1], q[2] = i, j
          q[0] += 1
        if p[0] < q[0]:
          ans[i][j] = p
        elif p[0] > q[0]:
          ans[i][j] = q
        elif p[1]+p[2] < q[1]+q[2]:
          ans[i][j] = q
        else:
          ans[i][j] = p
  return ans[i][j]

answer = dp(h-1, w-1)
print(answer[0])

Submission status: Wrong Answer

Solution code:
white = 0
black = 1
temp = []
def resolve(board, H, W):
    now = [0, 0]
    if board[0][0] == black:
        temp.append([0, 0])
    while now != [H-1, W-1]:
        now = check(board, now)
    return len(temp)
def check(board, now):
    if now[0] > len(board) -2 or board[now[0]+1][now[1]]==black:
        if now[1] > len(board[0]) -2 or board[now[0]][now[1]+1]==black:
            if now[1] < len(board[0]) -1:
                temp.append([now[0], now[1]+1])
                return [now[0], now[1]+1]
            elif now[0] < len(board) -1:
                temp.append([now[0]+1, now[1]])
                return [now[0]+1, now[1]]
        else:
            return [now[0], now[1]+1]
    else:
        return [now[0]+1, now[1]]
def change(board, r0, c0, r1, c1):
    for r in range(r0, r1 + 1):
        for c in range(c0, c1 + 1):
            board[r][c] = 1 - board[r][c]
def main():
    H, W = map(int, input().split())
    board = [[white for i in range(W)] for j in range(H)]
    for i in range(H):
        s = input()
        for j in range(W):
            if s[j] == ".":
                board[i][j] = white
            else:
                board[i][j] = black
    n = resolve(board, H, W)
    print(n)
if __name__ == "__main__":
    main()

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
if s[0][0] == '#':
    cost = 1
else:
    cost = 0
now = deque()
now.append([r,c, cost])
check = set((0,0))
while True:
    cur = now.popleft()
    r = cur[0]
    c = cur[1]
    cost = cur[2]
    if r == H-1 and c == W-1:
        break
    if c < W-1 and s[r][c + 1] == '.':
        if (r,c+1) not in check:
            now.appendleft([r,c+1,cost])
            check.add((r,c+1))
    if r < H-1 and s[r + 1][c] == '.':
        if (r+1,c) not in check:
            now.appendleft([r+1,c,cost])
            check.add((r+1,c))
    flag = False
    if c < W-1 and s[r][c + 1] == '#':
        if (r,c+1) not in check:
            now.append([r,c+1,cost+1])
            check.add((r,c+1))
    if r < H-1 and s[r + 1][c] == '#':
        if (r+1,c) not in check:
            now.append([r+1,c,cost+1])
            check.add((r+1,c))

print(cost)

Submission status: Wrong Answer

Solution code:
#!/usr/bin/env python3
from collections import defaultdict,deque
from heapq import heappush, heappop
from bisect import bisect_left, bisect_right
import sys, random, itertools, math
sys.setrecursionlimit(10**5)
input = sys.stdin.readline
sqrt = math.sqrt
def LI(): return list(map(int, input().split()))
def LF(): return list(map(float, input().split()))
def LI_(): return list(map(lambda x: int(x)-1, input().split()))
def II(): return int(input())
def IF(): return float(input())
def LS(): return list(map(list, input().split()))
def S(): return list(input().rstrip())
def IR(n): return [II() for _ in range(n)]
def LIR(n): return [LI() for _ in range(n)]
def FR(n): return [IF() for _ in range(n)]
def LFR(n): return [LI() for _ in range(n)]
def LIR_(n): return [LI_() for _ in range(n)]
def SR(n): return [S() for _ in range(n)]
def LSR(n): return [LS() for _ in range(n)]
mod = 1000000007
inf = float("INF")

#solve
def solve():
    h,w = LI()
    s = SR(h)
    b = [[inf] * w for i in range(h)]
    q = [(s[0][0] == "#", (0, 0))]
    b[0][0] = s[0][0] == "#"
    while q:
        p, xy = heappop(q)
        y, x = xy
        z = s[y][x]
        for mx, my in [(0, 1), (0, -1), (-1, 0), (1, 0)]:
            txm = mx + x
            tym = my + y
            xm = txm
            ym = tym
            if 0 <= xm < w and 0 <= ym < h:
                for xm in range(xm, w):
                    if s[ym][xm] == z:
                        if b[ym][xm] > p:
                            b[ym][xm] = p
                            heappush(q, (p, (ym, xm)))
                        else:
                            break
                    else:
                        break
                xm = txm
                ym = tym
                for xm in range(xm, -1, -1):
                    if s[ym][xm] == z:
                        if b[ym][xm] > p:
                            b[ym][xm] = p
                            heappush(q, (p, (ym, xm)))
                        else:
                            break
                    else:
                        break
                xm = txm
                ym = tym
                for ym in range(ym, h):
                    if s[ym][xm] == z:
                        if b[ym][xm] > p:
                            b[ym][xm] = p
                            heappush(q, (p, (ym, xm)))
                        else:
                            break
                    else:
                        break
                xm = txm
                ym = tym
                for ym in range(ym, -1, -1):
                    if s[ym][xm] == z:
                        if b[ym][xm] > p:
                            b[ym][xm] = p
                            heappush(q, (p, (ym, xm)))
                        else:
                            break
                    else:
                        break
                xm = txm
                ym = tym
                for xm in range(xm, w):
                    if s[ym][xm] != z:
                        if b[ym][xm] > p + 1:
                            b[ym][xm] = p + 1
                            heappush(q, (p + 1, (ym, xm)))
                    else:
                        break
                xm = txm
                ym = tym
                for ym in range(ym, h):
                    if s[ym][xm] != z:
                        if b[ym][xm] > p + 1:
                            b[ym][xm] = p + 1
                            heappush(q, (p + 1, (ym, xm)))
                    else:
                        break
                xm = txm
                ym = tym
                for xm in range(xm, -1, -1):
                    if s[ym][xm] != z:
                        if b[ym][xm] > p + 1:
                            b[ym][xm] = p + 1
                            heappush(q, (p + 1, (ym, xm)))
                    else:
                        break
                xm = txm
                ym = tym
                for ym in range(ym, -1, -1):
                    if s[ym][xm] != z:
                        if b[ym][xm] > p + 1:
                            b[ym][xm] = p + 1
                            heappush(q, (p + 1, (ym, xm)))
                    else:
                        break

    print(b[-1][-1] if b[-1][-1] else 0)

    return


#main
if __name__ == '__main__':
    solve()

Submission status: Wrong Answer

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

ls = [[0]*W for _ in range(H)]
ls[0][0] = int(bool(s[0][0]=="#"))

for i in range(1,W):
    ls[0][i] = ls[0][i-1]+ int(bool(s[0][i]=="." and s[0][i-1]=="#"))
    
for j in range(1,H):
    ls[j][0] = ls[j-1][0]+ int(bool(s[j][0]=="." and s[j-1][0]=="#"))

for i in range(1,W):
    for j in range(1,H):
        ls[j][i] = min(ls[j][i-1]+ int(bool(s[j][i]=="." and s[j][i-1]=="#")),
                       ls[j-1][i]+ int(bool(s[j][i]=="." and s[j-1][i]=="#")))
        
print(ls[-1][-1])

Submission status: Wrong Answer

Solution code:
from collections import deque

h,w = map(int,input().split())
F = [input() for _ in range(h)]
direct = [[0,1],[1,0]]
que = deque()
que.append([0,0])
INF = 10**5
dp = [[INF]*w for _ in range(h)]


dp[0][0] = 0

while len(que)>0:  
  x,y = que.popleft()    
  for dy,dx in direct:    
    ny = y+dy
    nx = x+dx
    if (0 <= nx < w) and (0 <= ny < h):
      if F[ny][nx] == F[y][x]:    
        if dp[ny][nx] > dp[y][x]:
          dp[ny][nx] = dp[y][x]
          que.append([ny,nx])
      else:        
        if dp[ny][nx] > dp[y][x] + 1 :        
          dp[ny][nx] = dp[y][x] + 1          
          que.append([ny,nx])   

ans = (dp[-1][-1]+1)//2
if F[0][0] == '#':
  ans += 1
print(ans)

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)

prev = ""
for y in range(h):
    for x in range(w):
        if y == 0 and x == 0: 
            val = 0
            prev = ""
        elif y == 0 or ansList[y - 1][x] > ansList[y][x - 1]:
            val = ansList[y][x - 1]
            prev = map[y][x - 1]
        elif x == 0 or ansList[y - 1][x] < ansList[y][x - 1]:
            val = ansList[y - 1][x]
            prev = map[y - 1][x]
        if x > 0 and y > 0 and ansList[y - 1][x] == ansList[y][x - 1] and (map[y - 1][x] != map[y][x - 1]):
            val = ansList[y - 1][x]
            prev = "#"
        elif x > 0 and y > 0 and ansList[y - 1][x] == ansList[y][x - 1] and (map[y - 1][x] == map[y][x - 1]):
            val = ansList[y - 1][x]
            prev = map[y - 1][x]

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