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
import resource
sys.setrecursionlimit(1000*1000)

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

#方向ベクトル 今回は右と下への移動のみを考える　
#つまり行と列番号を増やす向きのみ考える
dx = [1,0]
dy = [0,1]

#####白マスの中を泳ぐdfsの定義
def wdfs(h,w,grid,seen,l_b):
  #白マスの時にかぎり以下を行う
  if grid[h][w] == ".":
    seen[h][w] = True
    for i in range(2):
      new_h = h + dy[i]
      new_w = w + dx[i]

      #場外アウトしたり、移動先が壁の場合はスルー
      if (new_h<0 or new_w <0 or new_h>=H or new_w >= W ):
        continue
      #移動先が黒マスの時はスルー
      elif grid[new_h][new_w] == "#":
        l_b.append([new_h,new_w])
        continue
      #移動先が探索済みの場合スルー
      elif seen[new_h][new_w] == True:
        continue
      wdfs(new_h,new_w,grid,seen,l_b)       
#####dfsの定義

#####黒マスの中を泳ぐdfsの定義
def bdfs(h,w,grid,seen,l_w):
  seen[h][w] = True

  for i in range(2):
    new_h = h + dy[i]
    new_w = w + dx[i]

    #場外アウトの場合はスルー
    if (new_h<0 or new_w <0 or new_h>=H or new_w >= W ):
      continue
    #移動先が白マスの時はスルー
    elif grid[new_h][new_w] == ".":
      l_w.append([new_h,new_w])
      continue
    #移動先が探索済みの場合スルー
    elif seen[new_h][new_w] == True:
      continue
    bdfs(new_h,new_w,grid,seen,l_w)  
#####dfsの定義

#探索
seen = [ [False for i in range(W)] for i in range(H) ]
cnt = 0
l_w =[[0,0]]

#最初のマスが黒かった場合の場合わけ
if grid[0][0] == "#":
  grid[0][0] = "."
  cnt = cnt+1


while seen[H-1][W-1] == False:
  l_b =[]
  for w in l_w: 
    s1,s2 = w[0],w[1]
    wdfs(s1,s2,grid,seen,l_b)
  if seen[H-1][W-1] == True:
    break

  cnt = cnt+1

  l_w =[]
  for b in l_b:
    s1,s2 = b[0],b[1] #新しくさわられた黒マス
    bdfs(s1,s2,grid,seen,l_w)
  if seen[H-1][W-1] == True:
    break

###
print(cnt)

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:
    s = '.'
    flag = 1
else:
    s = '#'
    
def bfs(count):
    global ans
    global s
    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] != s 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:
            if flag == 1:
              print(visited[h-1][w-1])
            else:
            	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 j+1 < w:
                  c[i][j+1] = '.'
    ans += 1
        
if c[0][0] == '#':
  c[0][0] == '.'
  ans += 1


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

Submission status: Wrong Answer

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

dp = {}


# Y, X, （使った）Count
def rec(y, x):
    if (y, x) in dp:
        return dp[(y, x)]
    if y == h - 1 and x == w - 1:
        # dp[(y, x)] = c
        return 0
    if y < 0 or h <= y or x < 0 or w <= x:
        print(10.0 / 0)
    ret = 10**8
    steps = [0, 1, 0]
    for i in range(2):
        next_x, next_y = x + steps[i], y + steps[i + 1]
        if 0 <= next_y < h and 0 <= next_x < w:
            if table[next_y][next_x] == "#":
                # ret = min(rec(next_y, next_x, c) + 1, ret)
                ret = min(rec(next_y, next_x) + 1, ret)
            else:
                # ret = min(rec(next_y, next_x, c), ret)
                ret = min(rec(next_y, next_x), ret)
        else:
            continue
    # dp[(y, x, c)] = ret
    dp[(y, x)] = ret
    return ret


# print(rec(0, 0, 0))
p = 1 if table[0][0] == "#" else 0
print(rec(0, 0) + p)

Submission status: Wrong Answer

Solution code:
H, W = map(int,input().split())
l = [list(input()) for _ in range(H)]
#2D DP
dp = [[0] * (W + 1) for _ in range(H + 1)]
for i in range(W + 1):
  dp[0][i] = 99
for i in range(H + 1):
  dp[i][0] = 99
for i in range(1, H + 1):
  for j in range(1, W + 1):
    if i != 1 or j != 1:
      dp[i][j] = min(dp[i][j - 1], dp[i - 1][j])
    if l[i - 1][j - 1] == '#':
      dp[i][j] += 1 

print(dp[H][W])

Submission status: Wrong Answer

Solution code:
n,m=map(int,input().split())
l=[]
for i in range(n):
    s=list(input())
    l.append(s)
flag=0
save=l.copy()
#print(l)
black=0
white=0
for i in range(0,n):
    for j in range(0,m):
        if(l[i][j]=="#"):
            black+=1
        else:
            white+=1
if(l[0][0]=="#"):
    l[0][0]=1 
    white-=1
else:
    l[0][0]=0;
count=0
for i in range(1,n):
    if(l[i][0]=="#"):
        l[i][0]=l[i-1][0]+2
    else:
        l[i][0]=l[i-1][0]
for i in range(1,m):
    if( l[0][i]=="#"):
        l[0][i]=l[0][i-1]+1 
    else:
        l[0][i]=l[0][i-1]

for i in range(1,n):
    for j in range(1,m):
        if(l[i][j]=="#"):
            #print("test")
            l[i][j]=min(l[i-1][j],l[i][j-1])+1
        else:
            l[i][j]=min(l[i-1][j],l[i][j-1])
mb=l[n-1][m-1]
if(l[0][0]==1):
    if mb>white:
        print(mb+1)
    else:
        print(mb)
else:
    print(mb)

Submission status: Wrong Answer

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

result = [[10**9 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(result[-1][-1]-(sw[0][0]!=sw[-1][-1]))
else:
    print(result[h-1][w-1]//2 +(sw[0][0]!=sw[-1][-1]))

Submission status: Wrong Answer

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

road_count = 0
lis = [list('#'*(w+2))]
for _ in range(h):
    li = input()
    for i in li:
        if i == '.':
            road_count += 1
    li = '#' + li + '#'
    lis.append(list(li))
lis.append(list('#'*(w+2)))

#print(lis)
dp = [[999]*(w+2) for _ in range(h+2)]

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

#print(dp)
#(開始x,開始y)
step = [[1,1]]
while len(step)>0:
    x,y = step.pop(0)
    if x > h:
        continue
    if y > w:
        continue
    #print(x,y)
    if dp[x+1][y] == 999:
        step.append([x+1,y])
        if lis[x+1][y] != '#':
            dp[x+1][y] = min(dp[x][y],dp[x+1][y-1])
        else:
            dp[x+1][y] = min(dp[x][y],dp[x+1][y-1])+1
    if dp[x][y+1] == 999:
        step.append([x,y+1])
        if lis[x][y+1] != '#':
            dp[x][y+1] = min(dp[x][y],dp[x-1][y+1])
        else:
            dp[x][y+1] = min(dp[x][y],dp[x-1][y+1])+1
#print(lis)
#print(dp)
print(dp[h][w])

Submission status: Wrong Answer

Solution code:
h ,w = map(int,input().split())
board = [list(input()) for i in range(h)]
r = 0
c = 0
ans = 0
print(board[r][c])

Submission status: Wrong Answer

Solution code:
import random

h, w = map(int,input().split())
new_list = [list(input().split()) for _ in range(h)]
hw_list = []
for i in range(h):
  hw_list.append(list(new_list[i][0]))


print(random.randint(1,20))

Submission status: Wrong Answer

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

dp=[]
DP=[]
#print(s)

for h in range(H):
    dp.append([0]*W)
    DP.append([0]*W)
    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]
                DP[h][w]=DP[h-1][w]+1
            elif h==0 and w!=0:
                dp[h][w]=dp[h][w-1]
                DP[h][w]=DP[h][w-1]+1
            elif h==0 and w==0:
                dp[h][w]=0
                DP[h][w]=1
            else:
                dp[h][w]=min(dp[h-1][w],dp[h][w-1])
                DP[h][w]=min(DP[h-1][w],DP[h][w-1])+1
        else:
            if h!=0 and w==0:
                dp[h][w]=dp[h-1][w]+1
                DP[h][w]=DP[h-1][w]
            elif h==0 and w!=0:
                dp[h][w]=dp[h][w-1]+1
                DP[h][w]=DP[h][w-1]
            elif h==0 and w==0:
                dp[0][0]=1
                DP[0][0]=0
            else:
                dp[h][w]=min(dp[h-1][w],dp[h][w-1])+1
                DP[h][w]=min(DP[h-1][w],DP[h][w-1])
        #print(h,w)
        #for j in dp:
         #   print(j)
        #print(s[h][w],dp[h][w])
#print(dp)
print(min(dp[H-1][W-1],DP[H-1][W-1]))

Submission status: Wrong Answer

Solution code:
H, W = map(int,input().split())
l = [list(input()) for _ in range(H)]
#2D DP
dp = [[0] * (W + 1) for _ in range(H + 1)]
for i in range(W + 1):
  dp[0][i] = 99
for i in range(H + 1):
  dp[i][0] = 99
for i in range(1, H + 1):
  for j in range(1, W + 1):
    if i != 1 or j != 1:
      dp[i][j] = min(dp[i][j - 1], dp[i - 1][j])
    if l[i - 1][j - 1] == '#':
      dp[i][j] += 1 

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

Submission status: Wrong Answer

Solution code:
import random

h, w = map(int,input().split())
new_list = [list(input().split()) for _ in range(h)]
hw_list = []
for i in range(h):
  hw_list.append(list(new_list[i][0]))


print(random.randint(1,20))

Submission status: Wrong Answer

Solution code:
import itertools

h, w = map(int, input().split())

HW = []
for i in range(h):
    HW.append(input())
    
root = []
for i in range(h):
    for j in range(w):
        root.append([i, j])
root.pop(0)

search_root = []
for vv in itertools.combinations(root, (h - 1) + (w - 1)):
    # 一番目が初期値以外はスキップ
    if not(vv[0] == [0, 1] or vv[0] == [1, 0]): continue
    # 最後が最終値以外はスキップ
    if not(vv[-1] == [h -1, w - 1]): continue
    tmp = []
    print(vv)
    for v in vv:
        if tmp == []:
            tmp.append(v)
        else:
            # 右か下に移動するルート以外はスキップ
            if not(tmp[-1][0] == v[0] and tmp[-1][1] + 1 == v[1] \
                or tmp[-1][0] + 1 == v[0] and tmp[-1][1] == v[1]
                ): continue
            tmp.append(v)
    if len(tmp) == ((h - 1) + (w - 1)):
        tmp.insert(0, [0, 0])
        search_root.append(tmp)
        
search_count = []
for root in search_root:
    count = 0
    is_break = False
    for point in root:
        r, c = point[0], point[1]
        if HW[r][c] == "#":
            count += 1
            if search_count:
                if min(search_count) < count:
                    is_break = True
                    break
    if not is_break: search_count.append(count)
      
print(min(search_count))

Submission status: Wrong Answer

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

H, W = MAP()
S = [input() for i in range(H)]
# 1
dp = [[INF] * W for i in range(H)]
# 
if S[0][0] == ".":
    dp[0][0] = 0
else:
    dp[0][0] = 1

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

ans1 = dp[H-1][W-1]
# print(dp)
# print(ans1)


# 一回前半+1, ##
S_r = []
for i in range(H):
    l = []
    for j in range(W):
        if S[i][j] == ".":
            l.append("#")
        else:
            l.append(".")
    S_r.append(l)
dp = [[INF] * W for i in range(H)]
S = deepcopy(S_r)
if S[0][0] == ".":
    dp[0][0] = 0
else:
    dp[0][0] = 1

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

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

print(min(ans1, ans2+1))


exit()

# # 
# dp2 = deepcopy(dp)

# for i in range(1, W):
#     for j in range(1, H):
#         # nokori
#         if S[j][i] == ".":
#             dp2[j][i] = min(dp2[j-1][i], dp2[j][i-1])
#         else:
#             dp2[j][i] = min(dp2[j-1][i], dp2[j][i-1]) + 1
# print("h")
# print(*dp, sep="\n")





# print(dp2)
# print(ans1)


# exit()
# second



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

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

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

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

print(ans1, ans2)
print(min(ans1, ans2+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)]
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] = 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:
                            aaa[i][j][0] = min(aaa[i][j][0],aaa[i][j-1][0]+1,aaa[i-1][j][0]+1)
                            aaa[i][j][1] = 3
                        elif aaa[i][j-1][1] == 1:
                            aaa[i][j][0] = min(aaa[i][j][0],aaa[i][j-1][0],aaa[i-1][j][0]+1)
                            aaa[i][j][1] = 3
                        elif aaa[i][j-1][1] == 3:
                            aaa[i][j][0] = min(aaa[i][j][0],aaa[i][j-1][0],aaa[i-1][j][0]+1)
                            aaa[i][j][1] = 3
                    elif aaa[i-1][j][1] == 2:
                        if aaa[i][j-1][1] == 0:
                            aaa[i][j][0] = min(aaa[i][j][0],aaa[i][j-1][0]+1,aaa[i-1][j][0])
                            aaa[i][j][1] = 3
                        elif aaa[i][j-1][1] == 1:
                            aaa[i][j][0] = min(aaa[i][j][0],aaa[i][j-1][0],aaa[i-1][j][0])
                            aaa[i][j][1] = 3
                        elif aaa[i][j-1][1] == 3:
                            aaa[i][j][0] = min(aaa[i][j][0],aaa[i][j-1][0],aaa[i-1][j][0])
                            aaa[i][j][1] = 3
                    elif aaa[i-1][j][1] == 3:
                        if aaa[i][j-1][1] == 0:
                            aaa[i][j][0] = min(aaa[i][j][0],aaa[i][j-1][0]+1,aaa[i-1][j][0])
                            aaa[i][j][1] = 3
                        elif aaa[i][j-1][1] == 1:
                            aaa[i][j][0] = min(aaa[i][j][0],aaa[i][j-1][0],aaa[i-1][j][0])
                            aaa[i][j][1] = 3
                        elif aaa[i][j-1][1] == 3:
                            aaa[i][j][0] = min(aaa[i][j][0],aaa[i][j-1][0],aaa[i-1][j][0])
                            aaa[i][j][1] = 3
                else:
                    aaa[i][j][0] = min(aaa[i][j][0],aaa[i][j-1][0],aaa[i-1][j][0])

if po[0][0] == ".":
    aa[0][0] = [1,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:
                            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:
                            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:
                        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(min(aaa[-1][-1][0],aa[-1][-1][0]))

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] == "#") & (s[0][j-1] == "."):
        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] == "#") & (s[i-1][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] == "#":
            if s[i][j-1] == "#":
                if s[i-1][j] == "#":
                    dp[i][j] = min(dp[i - 1][j], dp[i][j - 1])
                else:
                    dp[i][j] = min(dp[i - 1][j] + 1, dp[i][j - 1]) + 1
            else:
                if s[i-1][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]) + 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:
import sys
import heapq
sys.setrecursionlimit(10000000)

h, w = map(int, input().split())
c = [input() for _ in range(h)]
 
d=[[100000]*w for _ in range(h)]

que = []
heapq.heapify(que)
if c[0][0] == '.':
    heapq.heappush(que, (0, (0, 0)))
    d[0][0] = 0
else:
    heapq.heappush(que, (1, (0, 0)))
    d[0][0] = 1

while len(que):
    _, (qx, qy) = heapq.heappop(que)
    if _ > d[h-1][w-1]:
        break
    for dx,dy in [[1,0], [0,1]]:
        px, py = qx+dx, qy+dy
        if 0<=px<h and 0<=py<w and d[px][py]>d[qx][qy]:
            d[px][py]=min(d[px][py], d[qx][qy] + (c[px][py]=='#'))
            heapq.heappush(que, (d[px][py], (px , py)))

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

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,0,-1,0]
Y=[0,1,0,-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(2):
            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:
H, W = map(int, input().split())
fields = []


def black_white(x):
    if x == '.':  # 白ならば1
        return 1
    elif x == '#':
        return -1  # 黒ならば-1


for i in range(H):
    fields.append(list(map(black_white, list(input()))))

if fields[0][0] == -1:
    cnt = 1
else:
    cnt = 0
positions = [(0, 0, cnt)]
cnts = []
while len(positions) > 0:
    r, c, cnt = positions.pop()
    if r == H-1 and c == W-1:
        print(cnt)
        break
    if r == H-1:
        pass
    elif r+1 <= H-1 and fields[r+1][c] == 1:
        tmp_r = r + 1
        while tmp_r+1 <= H-1 and fields[tmp_r+1][c] == 1:
            tmp_r += 1
        positions.append((tmp_r, c, cnt))
    elif r + 1 <= H-1:
        tmp_r = r + 1
        while tmp_r + 1 <= H-1 and fields[tmp_r+1][c] == -1:
            tmp_r += 1
        positions = [(tmp_r, c, cnt+1)] + positions
    if c == W-1:
        pass
    elif c+1 <= W-1 and fields[r][c+1] == 1:
        positions.append((r, c+1, cnt))
        tmp_c = c+1
        while tmp_c+1 <= W-1 and fields[r][tmp_c+1] == 1:
            tmp_c += 1
        positions.append((r, tmp_c, cnt))
    elif c+1 <= W-1:
        tmp_c = c+1
        while tmp_c+1 <= W-1 and fields[r][tmp_c+1] == -1:
            tmp_c += 1
        positions = [(r, tmp_c, cnt+1)] + positions

Submission status: Wrong Answer

Solution code:
import sys
from collections import deque
sys.setrecursionlimit(10 ** 6)
input = sys.stdin.readline
H, W = [int(x) for x in input().strip().split()]
G = [0 for _ in range(H)]
C = [[float('inf') for _ in range(W)] for _ in range(H)]

for h in range(H):
    G[h] = list(input().strip())

def dfs(r, c, cost):
    # print(' -- dfs --')
    C[r][c] = cost
    ret = deque([])
    q = deque([(r, c)])
    while q:
        cr, cc = q.popleft()
        # print('    cr = {}, cc = {}'.format(cr, cc))
        for i, j in [(0, 1), (1, 0), (0, -1), (-1, 0)]:
            if not(0 <= cr + i < H and 0 <= cc + j < W):
                continue
            if C[cr+i][cc+j] != float('inf'):
                continue
            if G[r][c] == G[cr+i][cc+j]:
                C[cr+i][cc+j] = cost
                q.append((cr+i, cc+j))
            else:
                ret.append((cr+i, cc+j))
    # print(ret)
    return ret

q = deque([(0, 0)])
cost = 0
while True:
    # print('q = {}'.format(q))
    nq = deque([])
    if G[q[0][0]][q[0][1]] == '#':
        cost += 1
    for r, c in q:
        # print('  r = {}, c = {}'.format(r, c))
        nq.extend(dfs(r, c, cost))
    q = nq
    # print(C)
    # print('nq = {}'.format(nq))
    if C[H-1][W-1] != float('inf'):
        print(C[H-1][W-1])
        exit()

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)]
colormap[0][0] = 0 if table[0][0] else 1

def update(i,j):

    tmp_A = 200
    tmp_B = 200
    
    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 - 1):
    # 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()

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

Submission status: Wrong Answer

Solution code:
h,w=map(int,input().split())
li=[[]]*h
for i in range(h):
  li[i]=[str(k) for k in input()]
  
lil=[[0 for i in range(w)] for j in range(h)]
#[h][w]=着くまでの最小操作回数
for i in range(h):
  for j in range(w):
    if i==0 and j==0:
      if li[0][0]==".":
        lil[0][0]=0
      else:
        lil[0][0]=1
    elif i==0:
      if li[i][j]==li[i][j-1]:
        lil[i][j]=lil[i][j-1]
      else :
        lil[i][j]=lil[i][j-1]+1
    elif j==0:
      if li[i][j]==li[i-1][j]:
        lil[i][j]=lil[i-1][j]
      else:
        lil[i][j]=lil[i-1][j]+1
    else:
      if li[i][j]==li[i-1][j]:
        ko=lil[i-1][j]
      else:
        ko=lil[i-1][j]+1
      if li[i][j]==li[i][j-1]:
        ks=lil[i][j-1]
      else :
        ks=lil[i][j-1]+1
      lil[i][j]=min(ko,ks)
print(lil[h-1][w-1])