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 copy
import sys
h,w = map(int,input().split())
c = [list(input()) for i in range(h)]
ans = 0
flag = 0
check = 0
for i in range(h):
    if len(c[i]) == c[i].count('#'):
        check += 1
        
if check == h:
    print(1)
    sys.exit()
    
def bfs(count):
    global ans
    C = copy.deepcopy(c)
    
    queue = []
    visited = [[0 for i in range(w)] for i in range(h)]

    queue.append([0,0])
    visited[0][0] = 1

    dy_dx = [[1,0],[0,1]]
    while len(queue) > 0:
        now = queue.pop(0)
        for k in range(2):
            y = now[0]+dy_dx[k][0]
            x = now[1]+dy_dx[k][1]
            if 0 <= y < h and 0 <= x < w:
                if C[y][x] != "#" and visited[y][x] == 0:
                    visited[y][x] = visited[now[0]][now[1]]+1
                    queue.append([y,x])
                    
        if visited[h-1][w-1] != 0:
            print(ans)
            sys.exit()
            
    for i in range(h):
        for j in range(w):
            if visited[i][j] != 0:
                if i+1 < h:
                  c[i+1][j] = '.'
                  if i+2 < h:
                      c[i+2][j] = '.'
                if j+1 < w:
                  c[i][j+1] = '.'
                  if j+2 < w:
                      c[i][j+2] = '.'
    ans += 1
        
if c[0][0] == '#':
  c[0][0] == '.'
  ans += 1


for i in range(10000):
    bfs(i)

Submission status: Wrong Answer

Solution code:


def solve(M, h, w):
    dp = {}
    dp[(h-1, w-1)] = 0
    if M[h-1][w-1]=='#':
        dp[(h-1, w-1)] = 1

    for col in range(w-2, -1, -1):
        dp[(h-1, col)] = dp[(h-1, col+1)]
        if M[h-1][col]=='#':
            dp[(h-1, col)] += 1

    for row in range(h-2, -1, -1):
        dp[(row, w-1)] = dp[(row+1, w-1)]
        if M[row][w-1] == '#':
            dp[(row, w-1)] += 1

        for col in range(w-2, -1, -1):
            dp[(row, col)] = min(dp[(row, col+1)], dp[(row+1, col)])
            if M[row][col] == '#':
                dp[(row, col)] += 1

    print(dp[(0, 0)])
h, w = map(int, input().split())

M = []
for i in range(h):
    a = list(input())
    M.append(a)

solve(M, h, w)

Submission status: Wrong Answer

Solution code:
H, W = map(int, input().split())
S = [0]*(H+2)
S[0] = '*'*(W+2)
S[H+1] = '*'*(W+2)
for i in range(1,H+1):
  S[i] = '*'+input()+'*'


unsearched_nodes = list(range(1,H*W+1)) # 未探索ノード
distance= [10000]*(W*H+1)
#print(unsearched_nodes,distance)
previous_move = [[-1]*(W+2) for _ in range(H+2)] # 最短経路でそのノードのひとつ前に到達するノードのリスト
distance[1] = 0 # 初期のノードの距離は0とする
if S[1][1]=='#':
  distance[1] = 1
while len(unsearched_nodes) != 0: #未探索ノードがなくなるまで繰り返す
    # まず未探索ノードのうちdistanceが最小のものを選択する
  posible_min_distance = 10001 # 最小のdistanceを見つけるための一時的なdistance。初期値は inf に設定。
  for node_index in unsearched_nodes: # 未探索のノードのループ
    #print(node_index)
    if posible_min_distance > distance[node_index]: 
      posible_min_distance = distance[node_index] # より小さい値が見つかれば更新
      target_min_index = node_index
  #print(unsearched_nodes,target_min_index,distance)
  unsearched_nodes.remove(target_min_index) # ここで探索するので未探索リストから除去
	
  dh = [0,1,0,-1]
  dw = [1,0,-1,0]
  target_h = (target_min_index-1) // W + 1
  target_w = target_min_index % W
  if target_w == 0:
    target_w = W
  for i in range(4):
    h = target_h + dh[i]
    w = target_w + dw[i]
    ind = (h-1)*W+w
    route_dis = 0
    if S[h][w]=='*':
      continue
    if S[h][w]=='#':
      if S[target_h][target_w]=='.':
        route_dis = 1
      elif i%2^previous_move[target_h][target_w]==1:
        route_dis = 1  
    if distance[ind] > distance[target_min_index] + route_dis:
      distance[ind] = distance[target_min_index] + route_dis # 過去に設定されたdistanceよりも小さい場合はdistanceを更新
      previous_move[h][w] = 0 if i%2==0 else 1
      
  #print(distance)
print(distance[-1])
#print(*ans, sep='\n')

Submission status: Wrong Answer

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

H, W = map(int, input().split())
field = [list(input()) for _ in range(H)]
next_list = []
now_list = [(0,0)]
ok = "."
cnt = 0
goal = 0
while goal == 0:
    next_list = set()
    while len(now_list) > 0:
        x, y = now_list.pop()
        if x == W-1 and y == H-1:
            goal = 1
            break
        for nx, ny in ((1,0),(0,1)):
            nx += x
            ny += y
            if nx >= W or ny >= H:
                continue
            if field[ny][nx] == ok:
                next_list.add((nx,ny))
    if goal == 1:
        pass
    elif len(next_list) > 0:
        now_list = list(next_list)
    else:
        now_list = [[x,y]]
        if ok == ".":
            cnt += 1
            ok = "#"
        else:
            ok = "."

if field[0][0] == "#":
    cnt += 1

print(cnt)

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)]
aa = [[[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] = 3
            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] = 3
                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)
                            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 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])
                            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 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])
                            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])

if po[0][0] == ".":
    aa[0][0] = [2,3]
else:
    aa[0][0] = [1,0]

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

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

print(aaa)
print(aa)
print(min(aaa[-1][-1][0],aa[-1][-1][0]))

Submission status: Wrong Answer

Solution code:
from collections import deque

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

ans = 10**9

visited_list = [[10**9]*W for _ in range(H)]

if C[0][0] == "#": 
    stack = deque([[0, 0, 1]])
    visited_list[0][0] = 1
else:
    stack = deque([[0, 0, 0]])
    visited_list[0][0] = 0

def dfs(town, visited_list, stack):
    global ans
    while len(stack) > 0:
        h, w, cnt = stack.pop()
        if h == H-1 and w == W-1 and ans > cnt:
            ans = cnt
            continue
        for j, k in ([1, 0], [0, 1]):
            new_h, new_w = h+j, w+k
            if new_h < 0 or new_h >= H or new_w < 0 or new_w >= W:
                continue
            if  visited_list[new_h][new_w] > cnt and town[new_h][new_w] != "#":
                visited_list[new_h][new_w] = cnt
                stack.append([new_h, new_w, cnt])
            elif visited_list[new_h][new_w] > cnt + 1 and town[new_h][new_w] == "#":
                visited_list[new_h][new_w] = cnt + 1
                # print("a " + str(cnt+1))
                stack.append([new_h, new_w, cnt+1])
    return ans

print(dfs(C, visited_list, stack))

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] == '#')
    if b:
        return min(solve(h - 1, w, last_b=True) + (not last_b),
                   solve(h, w - 1, last_b=True) + (not last_b),
                   )
    return min(
        solve(h - 1, w, last_b=False),
        solve(h, w - 1, last_b=False),
        solve(h - 1, w, last_b=True) + 1,
        solve(h, w - 1, last_b=True) + 1,
        # 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())
table = []
for i in range(H):
    table.append([(True if x == "." else False) for x in list(input())])

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

def update(i,j):

    tmp_A = 1000
    tmp_B = 1000
    
    if 0 < i < H and j < W:
        if table[i-1][j] == table[i][j]:
            tmp_A = colormap[i-1][j]
        else:
            tmp_A = colormap[i-1][j] + 1
        
    if i < H and 0 < j < W:
        if table[i][j-1] == table[i][j]:
            tmp_B = colormap[i][j-1]
        else:
            tmp_B = colormap[i][j-1] + 1
    
    colormap[i][j] = min(tmp_A, tmp_B)
    
for k in range(1, H + W):
    # print("k={}".format(k))
    for i in range(k + 1):
        if i < H and k - i < W:
            # print("({},{})".format(i, k -i), end="")
            update(i, k - i)
    # print(colormap)

# 必要反転回数
plus = 1 if not table[0][0] else 0
print(colormap[H-1][W-1] // 2 + plus)

Submission status: Wrong Answer

Solution code:
from collections import deque
import copy
 
h,w = map(int, input().split())
s = []
for i in range(h):
    s.append(list(input()))
 
 
# h x w のマップのリストを整形
t_tmp = []
for i in range(h):
    tmp = []
    for j in range(w):
        tmp.append(s[i][j])
    t_tmp.append(tmp)
 
 
# 現在地とその距離
if s[0][0] == '#':
    q = deque([(0,0,1)])
    min_value = 1
else:
    q = deque([(0,0,0)])
    min_value = 0
 
# スタートを設定してsをコピー
t = copy.deepcopy(t_tmp)
#print(t)
tmp_list = []


while q:
    #print(q)
    x,y,c = q.popleft()
    if c > min_value:
        continue
    #print(x, y ,c)
    if (x+1, y+2) == (w, h) or (x+2, y+1) == (w, h):
        #print('continue')
        continue
    pass_ = 0
    #if (x+1,y+1) == (h,w):
    #    continue
 
    for dx, dy in [(1,0),(0,1)]:
        # 壁を超えるか否か
        nx, ny = x+dx, y+dy
        if 0<=nx<h and 0<=ny<w and t[nx][ny] == '.':
            t[nx][ny] = '#'
            q.append((nx,ny,c))
            pass_ = 1
            if (nx+1,ny+2) == (h, w):
                if t[nx][ny+1] == '.':
                    tmp_list.append(c)
                elif t[nx][ny+1] == '#':
                    tmp_list.append(c+1)
            elif (nx+2,ny+1) == (h, w):
                if t[nx+1][ny] == '.':
                    tmp_list.append(c)
                elif t[nx+1][ny] == '#':
                    tmp_list.append(c+1)
 
    if pass_ == 0:
        for dx, dy in [(1,0),(0,1)]:
            # 壁を超えるか否か
            nx, ny = x+dx, y+dy
            if 0<=nx<h and 0<=ny<w and t[nx][ny] == '#':
                t[nx][ny] = '#'
                q.append((nx,ny,c+1))
                
                if (nx+1,ny+2) == (h, w):
                    if t[nx][ny+1] == '.':
                        tmp_list.append(c+1)
                    elif t[nx][ny+1] == '#':
                        tmp_list.append(c+2)
 
                elif (nx+2,ny+1) == (h, w):
                    if t[nx+1][ny] == '.':
                        tmp_list.append(c+1)
                    elif t[nx+1][ny] == '#':
                        tmp_list.append(c+2)

    if pass_ == 1:
        min_value = c
    elif pass_ == 0:
        min_value = c+1

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

Submission status: Wrong Answer

Solution code:
# -*- coding: utf-8 -*-

#入力
H, W = map(int,input().split())
s = [list(map(str,list(input()))) for i in range(H)] 

#初期値
count1 = 0
count2 = 0
conti = 0
j = 0
k = 0

if s[j][k]=='#':
    count1 += 1
    count2 += 1


while  j+1<H or k+1<W:
    if j+1!=H and s[j+1][k] == '.':
        j += 1
        conti = 0
    elif k+1!=W and s[j][k+1] == '.':
        k += 1
        conti = 0
    elif j+1!=H and s[j+1][k] == '#' :
        if conti == 0:
            count1 += 1
            conti = 1
        else:
            conti += 1
            j+=1
    elif k+1!=W and s[j][k+1] == '#':
        if conti == 0:
            count1 += 1
            conti = 1
        else:
            conti += 1
            k+=1

j = 0
k = 0
    
while  j+1<H or k+1<W:
    if k+1!=W and s[j][k+1] == '.':
        k += 1
        conti = 0
    elif j+1!=H and s[j+1][k] == '.':
        j += 1
        conti = 0
    elif k+1!=W and s[j][k+1] == '#':
        if conti == 0:
            count2 += 1
            conti = 1
        else:
            conti += 1
        k+=1
    elif j+1!=H and s[j+1][k] == '#' :
        if conti == 0:
            count2 += 1
            conti = 1
        else:
            conti += 1
        j+=1
    

if count1<count2:
    count=count1
else:
    count=count2

print(count)

Submission status: Wrong Answer

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

result = [[10**5 for i in range(w)] for j in range(h)]
result[0][0] = 0
for i in range(h):
    for j in range(w):
        if j > 0:
            result[i][j] = result[i][j-1]+(sw[i][j-1]!=sw[i][j])
        if i > 0:
            result[i][j] = min(result[i][j], result[i-1][j]+(sw[i-1][j]!=sw[i][j]))


if sw[0][0]=="#":
    print(min(1+result[h-1][w-1]//2, result[h-1][w-1]//2+1))
else:
    print(min(2+result[h-1][w-1]//2, result[h-1][w-1]//2))

Submission status: Wrong Answer

Solution code:
from collections import deque
h, w = map(int,input().split())
map = []
for i in range(h):
    map.append(list(input()))
queue = deque()
if map[0][0] == '#':
    queue.append([1,0,0])#[y,x,num]
else:
    queue.append([0,0,0])#[y,x,num]
min = 10**10
while queue:
    num,y,x= queue.popleft()
    if map[y][x] == '#':
        num = num+1
    if y == h-1 and x == w-1:
        if min > num:
            min = num
            continue
    if y+1 < h:
        queue.append([num,y+1,x])
    if x+1 < w:
        queue.append([num,y,x+1])
print(min)

Submission status: Wrong Answer

Solution code:
import sys

h, w = map(int, input().split())
s = [sys.stdin.readline().rstrip() for i in range(h)]
ans = [[0]*(w+2) for i in range(h+2)]
for i in range(h):
    for j in range(w):
        if s[i][j] == "#":
            ans[i+1][j+1] = min(ans[i+1][j], ans[i][j+1]) + 1
        else:
            ans[i+1][j+1] = min(ans[i+1][j], ans[i][j+1])

        if i == 0 and j == 0:
            ans[i][j+2] = ans[i+1][j+1]
            ans[i+2][j] = ans[i+1][j+1]
        elif i == 0:
            ans[i][j+2] = ans[i+1][j+1]
        elif j == 0:
            ans[i+2][j] = ans[i+1][j+1]

print(ans[h][w])

Submission status: Wrong Answer

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

def solve(grid, h, w):
    if h == 0 or w == 0:
        return 0
    color = grid[0][0]
    cnt = 0
    if color == '#':
        cnt += 1
    dist = [[-1] * w for _ in range(h)]
    dist[0][0] = cnt
    q = []
    q.append((0, 0))
    current_color_cluster = [(0, 0)]
    while q and dist[h - 1][w - 1] == -1:
        new_q = []
        for i, j in q:
            for ii, jj in ((i + 1, j), (i, j + 1)):
                if 0 <= ii < h and 0 <= jj < w and dist[ii][jj] == -1 and grid[ii][jj] == color:
                    dist[ii][jj] = cnt
                    new_q.append((ii, jj))
        if new_q:
            current_color_cluster.extend(new_q)
            q = new_q
        elif dist[h - 1][w - 1] == -1:
            if color == '#':
                cnt += 1
            color = '#' if color == '.' else '.'
            q = current_color_cluster
            current_color_cluster = []
    return dist[h - 1][w - 1]

print(solve(grid, h, w))

Submission status: Wrong Answer

Solution code:
H, W = map(int, input().split())
def change(x):
    if x == '#':
        return 1
    else:
        return 0
field = list()
for i in range(H):
    field.append(list(map(change,[i for i in input()])))

vector = [[1, 0], [0, 1]]
check_list = [[0 for _ in range(W)] for i in range(H)]
check_list[0][0] = 1
count_list = [[[0, [0, 0], 0] for _ in range(W)] for i in range(H)]
count_list[0][0][0] = field[0][0]
count_list[0][0][2] = field[0][0]
zahyo_check = [[(0, 0)]]
for i in range(H+W-2):
    zahyo = zahyo_check[i]
    zahyo_kari = list()
    for (y, x) in zahyo:
        for (dy, dx) in vector:
            v = count_list[y][x][0]
            y_k = y + dy
            x_k = x + dx
            try:
                v += field[y_k][x_k]
                if check_list[y_k][x_k] == 0:
                    count_list[y_k][x_k][0] = v
                    count_list[y_k][x_k][1] = [y, x]
                    count_list[y_k][x_k][2] = count_list[y][x][2]
                    if field[y_k][x_k] == 1:
                        y_f, x_f = count_list[y_k][x_k][1]
                        if field[y_f][x_f] == 0:
                            count_list[y_k][x_k][2] += 1
                    check_list[y_k][x_k] = 1
                    zahyo_kari.append((y_k, x_k))
                else:
                    if v < count_list[y_k][x_k][0]:
                        count_list[y_k][x_k][0] = v
                        count_list[y_k][x_k][1] = [y, x]
                        count_list[y_k][x_k][2] = count_list[y][x][2]
                        if field[y_k][x_k] == 1:
                            y_f, x_f = count_list[y_k][x_k][1]
                            if field[y_f][x_f] == 0:
                                count_list[y_k][x_k][2] += 1
                    elif v == count_list[y_k][x_k][0]:
                        count = count_list[y][x][2]
                        if field[y_k][x_k] == 1:
                            y_f, x_f = count_list[y_k][x_k][1]
                            if field[y_f][x_f] == 0:
                                count += 1
                                if count < count_list[y_k][x_k][2]:
                                    count_list[y_k][x_k][2] = count
                        
            except:
                pass
    zahyo_check.append(zahyo_kari)

print(count_list[H-1][W-1][2])

Submission status: Wrong Answer

Solution code:
import copy

h,w = list(map(int,input().split()))
s = []
ss = []
hc = 0
wc = 0
res = 0

for i in range(h):
    s.append(list(input()))

h = h-1
w = w-1
ss = copy.deepcopy(s)

for i in range(h+1):
    for j in range(w+1):
        if i != 0 and j != 0:
            if ss[i-1][j] < ss[i][j-1]:
                ss[i][j] = ss[i-1][j]
            else:
                ss[i][j] = ss[i][j-1]
        elif i != 0:
            ss[i][j] = ss[i-1][j]
        elif j != 0:
            ss[i][j] = ss[i][j-1]
        else:
            ss[i][j] = 0

        if s[i][j] == "#":
            ss[i][j] = ss[i][j] + 1


print(ss[h][w])

            
# while True:
#     if s[hc][wc] == "#":
#         res += 1
    
#     if hc == h and wc == w:
#         break
    
#     if hc < h and wc == w:        
#         hc += 1
#     elif hc == h and wc < w: 
#         wc += 1
#     else:
#         if s[hc+1][wc] == ".":
#             hc += 1
#         elif s[hc][wc+1] == ".":
#             wc += 1
#         else:
#             wc += 1

# hc = h
# wc = w
# res1 = 0
# while True:
#     if s[hc][wc] == "#":
#         res1 += 1
    
#     if hc == 0 and wc == 0:
#         break
    
#     if hc > 0 and wc == 0:        
#         hc -= 1
#     elif hc == h and wc > 0: 
#         wc -= 1
#     else:
#         if s[hc-1][wc] == ".":
#             hc -= 1
#         elif s[hc][wc-1] == ".":
#             wc -= 1
#         else:
#             wc -= 1

# if res < res1:
#     print(res)
# else:
#     print(res1)

Submission status: Wrong Answer

Solution code:
from collections import deque

h,w = map(int,input().split())
base = []

for i in range(h):
  base.append(input())
  
seen = [-1]*(h*w)
q = deque([])
q.append([0,0])
now_ini = base[0][0]

if now_ini == ".":
  seen[0] = 0
elif now_ini == "#":
  seen[0] = 1

while q:
  r,c = q.popleft()
  now = base[r][c]
  
  if (0<=r-1) and (seen[(r-1)*w+c] == -1):
    if now == base[r-1][c]:
      sign = 0
    elif (now != base[r-1][c]) and (now == "."):
      sign = 1
    elif (now != base[r-1][c]) and (now == "#"):
      sign = 2
      
    if sign == 0:
      q.appendleft([r-1,c])
      seen[(r-1)*w+c] = seen[r*w+c]
    elif sign == 1 :
      q.append([r-1,c])
      seen[(r-1)*w+c] = seen[r*w+c] + 1
    elif sign == 2:
      q.append([r-1,c])
      seen[(r-1)*w+c] = seen[r*w+c]
      
  if (0<=c-1) and (seen[r*w+c-1] == -1):
    if now == base[r][c-1]:
      sign = 0
    elif now != base[r][c-1] and (now == "."):
      sign = 1
    elif (now != base[r][c-1]) and (now == "#"):
      sign = 2
      
    if sign == 0:
      q.appendleft([r,c-1])
      seen[r*w+c-1] = seen[r*w+c]
    elif (sign == 1):
      q.append([r,c-1])
      seen[r*w+c-1] = seen[r*w+c] + 1
    elif (sign == 2):
      q.append([r,c-1])
      seen[r*w+c-1] = seen[r*w+c]
      
      
  if (r+1<h) and (seen[(r+1)*w+c] == -1):
    if now == base[r+1][c]:
      sign = 0
    elif (now != base[r+1][c]) and (now == "."):
      sign = 1
    elif (now != base[r+1][c]) and (now == "#"):
      sign = 2
      
    if sign == 0:
      q.appendleft([r+1,c])
      seen[(r+1)*w+c] = seen[r*w+c]
    elif sign == 1:
      q.append([r+1,c])
      seen[(r+1)*w+c] = seen[r*w+c] + 1
    elif (sign == 2):
      q.append([r+1,c])
      seen[(r+1)*w+c] = seen[r*w+c]
      
  if (c+1<w) and (seen[r*w+c+1] == -1):
    if now == base[r][c+1]:
      sign = 0
    elif now != base[r][c+1] and (now == "."):
      sign = 1
    elif (now != base[r][c+1]) and (now == "#"):
      sign = 2
      
    if sign == 0:
      q.appendleft([r,c+1])
      seen[r*w+c+1] = seen[r*w+c]
    elif sign == 1:
      q.append([r,c+1])
      seen[r*w+c+1] = seen[r*w+c] + 1
    elif (sign == 2):
      q.append([r,c+1])
      seen[r*w+c+1] = seen[r*w+c]
      
      
print(seen[w*h-1])

Submission status: Wrong Answer

Solution code:
H,W = map(int,input().split())
A = []
for i in range(H):
    b = list(input())
    A.append(b)
dp = [[10**9 for i in range(W)] for i in range(H)]


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

i = 0
j = 0

p = []
for i in range(H):
    for j in range(W):
        p.append([i,j])

t = 0
while(True):
    if i < H-1 and A[i+1][j] == ".":
        dp[i+1][j] = min(dp[i+1][j],dp[i][j])
        if j-1 >= 0:
            dp[i+1][j] = min(dp[i+1][j-1],dp[i+1][j])
    if j < W-1 and A[i][j+1] == ".":
        dp[i][j+1] = min(dp[i][j+1],dp[i][j])
        if i-1 >= 0:
            dp[i][j+1] = min(dp[i][j+1],dp[i-1][j+1])
    if i < H-1 and A[i+1][j] == "#":
        dp[i+1][j] = min(dp[i+1][j], dp[i][j]+1)
        if j-1 >= 0:
            dp[i+1][j] = min(dp[i+1][j-1]+1, dp[i+1][j])
    if j < W-1 and A[i][j+1] == "#":
        dp[i][j+1] = min(dp[i][j+1], dp[i][j]+1)
        if i-1 >= 0:
            dp[i][j+1] = min(dp[i][j+1], dp[i-1][j+1]+1)

    i = p[t][0]
    j = p[t][1]
    t += 1
    if i == H-1 and j == W-1:
        break

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

Submission status: Wrong Answer

Solution code:
from collections import deque
H, W = map(int, input().split())
m = [list(input()) for i in range(0, H)]
counts = [[-1] * W for i in range(0, H)]
si, sj = 0, 0
if m[si][sj] == '#':
    counts[si][sj] = 1
else:
    counts[si][sj] = 0

q = deque([[si, sj]])
while q:
    i, j = q.popleft()
    for movei, movej in [[1, 0], [0, 1]]:
        ni, nj = i + movei, j + movej
        if (H <= ni or W <= nj):
            continue

        if m[ni][nj] == '#':
            c = counts[i][j] + 1
        else:
            c = counts[i][j]

        if counts[ni][nj] < 0:
            counts[ni][nj] = c
            if ni < H and nj < W:        
                q.append([ni, nj])
        else:
            if counts[ni][nj] > c:
                counts[ni][nj] = c
print(counts[H-1][W-1])