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:
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 = [[0 for i in range(w)]for j in range(h)]
for i in range(h):
    for j in range(w):
        flag = False
        if li[i][j] == "#":
            lin[i][j] += 1
        if i == 0 and j == 0:
            continue
        if j-1 >= 0:
            k = lin[i][j-1]
            if lin[i][j-1] == "#" and lin[i][j] == "#":
                flag = True
        else:
            k = inf
        if i-1 >= 0:
            l = lin[i-1][j]
            if lin[i-1][j] == "#" and lin[i][j] == "#":
                flag = True
        else:
            l = inf
        lin[i][j] += min(k,l)
        if flag:
            lin[i][j] -= 1
print(lin[h-1][w-1]+1)

Submission status: Wrong Answer

Solution code:
from collections import deque

def search(x, s):
    for i in range(1,H+1):
        for j in range(1,W+1):
            if s[i][j] == '.' and (s[i-1][j] == x or s[i][j-1] == x):
                s[i][j] = x
    for i in range(1,H+1):
        for j in range(1,W+1):
            if s[i][j] == '#' and s[i-1][j] in ('x', x, x+1) and s[i][j-1]  in ('x', x, x+1):
                s[i][j] = x+1
    return s

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

s = [['x']*(W+2)] + [['x'] + list(input()) + ['x'] for _ in range(H)] + [['x']*(W+2)]
if s[1][1] == '#':
    ans, x, s[1][1] = 1, 0, 0
    for i in range(1,H+1):
        for j in range(1,W+1):
            if s[i][j] == '#' and s[i-1][j] in ('x', x) and s[i][j-1]  in ('x', x):
                s[i][j] = x
else:
    ans, x, s[1][1] = 0, 0, 0

while s[H][W] == '.' or s[H][W] == '#':
    s = search(x, s)
    x += 1
print(ans + s[H][W])

Submission status: Wrong Answer

Solution code:
from collections import defaultdict as dd
dp = dd(lambda: dd(int))


def recur(arr, i, j):
    if i in dp.keys():
        if j in dp[i].keys():
            return dp[i][j]
    if i >= h and j >= w:
        return 0
    if i >= h:
        dp[i-1][j] = recur(arr, i, j+1)+(0, 1)[mat[i-1][j] == '#']
        return dp[i-1][j]
    if j >= w:
        dp[i][j-1] = recur(arr, i+1, j)+(0, 1)[mat[i][j-1] == '#']
        return dp[i][j-1]
    dp[i][j] = min(recur(arr, i+1, j)+(0, 1)[mat[i][j] == '#'], recur(arr, i, j+1)+(0, 1)[mat[i][j] == '#'])
    return dp[i][j]


h, w = map(int, input().split())
mat = []
for i in range(h):
    mat.append(list(input()))
print(recur(mat, 0, 0))

Submission status: Wrong Answer

Solution code:
import sys
input = sys.stdin.readline
h,w=map(int,input().split())
infi=10**10
D=[list(input()) for _ in range(h)]
kotae=[[(infi,0)]*(w) for _ in range(h)]
# D[i][j]はD[h-1][w-1]まで
cnt=0
flag=0
ren=0
for i in range(h):
    if D[i][0]=='#':
        cnt+=1
        if flag:
            ren+=1
        flag=1
    else:
        flag=0
        ren=0
    kotae[i][0]=(cnt,ren)
cnt=0
flag=0
ren=0
for j in range(w):
    if D[0][j]=='#':
        cnt+=1
        if flag:
            ren+=1
        flag=1
    else:
        flag=0
        ren=0
    kotae[0][j]=(cnt,ren)
ren_sum=0
for i in range(h-1):
    for j in range(w-1):
        if kotae[i][j+1][0]-kotae[i][j+1][1] >= kotae[i+1][j][0]-kotae[i+1][j][1]:
            cur_kotae=kotae[i][j+1][0]
            cur_ren=kotae[i][j+1][1]
        else:
            cur_kotae=kotae[i+1][j][0]
            cur_ren=kotae[i+1][j][1]
        if D[i+1][j+1]=='#':
            cur_kotae+=1
            if cur_ren>0:
                cur_ren+=1
        else:
            cur_ren=0
        kotae[i+1][j+1]=(cur_kotae, cur_ren)
print(kotae[h-1][w-1][0]-kotae[h-1][w-1][1])

Submission status: Wrong Answer

Solution code:
H, W = map(int, input().split())
a = []
a.append([10**10]*(W+1))
for _ in range(H):
    temp = list(input())
    i = [1 if i == "." else 100000 for i in temp]
    i.append(10**10)
    i.insert(0,10**10)
    a.append(i)
a.append([10**10]*(W+1))

ans = 0

if a[1][1]==100000:
    a[1][1]=1
    ans += 1

if a[H][W]==100000:
    a[H][W]=1
    ans += 1

dp = []
dp.append([10**10]*(W+2))
for _ in range(H):
    i = [0 for i in range(W)]
    i.append(10**10)
    i.insert(0,10**10)
    dp.append(i)
dp.append([10**10]*(W+2))
dp[1][1]=1


cnt = 1
h_temp = 1
w_temp = 0

for i in range(2,H+W):
    if i <= min(H,W):
        cnt += 1
    elif i >= max(H,W):
        cnt -= 1
    else:
        cnt = cnt
    if i <= H:
        h_temp += 1
    if i > W:
        w_temp += 1
        
    for j in range(cnt):
        h = h_temp-j
        w = 1+ w_temp+j

        dp[h][w] = min(dp[h-1][w]+a[h][w],dp[h][w-1]+a[h][w])

print(ans+int(dp[H][W]/100000))

Submission status: Wrong Answer

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

from collections import deque
import sys
white = deque()
black = deque()
black.append((0, 0))
if s[0][0]=='.':
    cnt = 0
else:
    cnt = 1
while len(black)>0:
    white = black
    black = deque()
    while len(white)>0:
        r, c = white.popleft()
        if r+1<h:
            if s[r][c]=='.' and s[r+1][c]=='#':
                if (r+1, c) not in black:
                    black.append((r+1, c))
            else:
                if r+1==h-1 and c==w-1:
                    print(cnt)
                    sys.exit()
                if (r+1, c) not in white:
                    white.append((r+1, c))
        if c+1<w:
            if s[r][c]=='.' and s[r][c+1]=='#':
                if (r, c+1) not in black:
                    black.append((r, c+1))
            else:
                if r+1==h-1 and c==w-1:
                    print(cnt)
                    sys.exit()
                if (r, c+1) not in white:
                    white.append((r, c+1))
    cnt += 1

print(cnt-1)

Submission status: Wrong Answer

Solution code:
import sys
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)  
  #最初のマスが黒かった時    
  else:
    l_b.append([h,w])           
#####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]] 
l_b =[]


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

  cnt = cnt+1

  l_w = []
  b = max(l_b)
  bdfs(b[0],b[1],grid,seen,l_w)
  if seen[H-1][W-1] == True:
    break

###
print(cnt)

Submission status: Wrong Answer

Solution code:
import numpy as np
h, w = map(int, input().split())
s = [input() for _ in range(h)]

dp = np.zeros(h * w).reshape(h, w)

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

for i in range(h - 1):
    for j in range(w - 1):
        if s[i + 1][j + 1] == "." or (s[i][j + 1] == s[i + 1][j + 1] and s[i + 1][j + 1] == s[i + 1][j]):
            dp[i + 1][j + 1] = min(dp[i][j + 1], dp[i + 1][j])
        elif s[i][j + 1] == s[i + 1][j + 1] and s[i + 1][j + 1] != s[i + 1][j]:
            dp[i + 1][j + 1] = min(dp[i][j + 1], dp[i + 1][j] + 1)
        elif s[i][j + 1] != s[i + 1][j + 1] and s[i + 1][j + 1] == s[i + 1][j]:
            dp[i + 1][j + 1] = min(dp[i][j + 1] + 1, dp[i + 1][j])
        else:
            dp[i + 1][j + 1] = min(dp[i][j + 1] + 1, dp[i + 1][j] + 1)
    
if s[h - 1][w - 1] == "#" and (s[0][0] != "#" or (dp[h - 2][w - 1] != 1 and dp[h - 1][w - 2] == 1)):
    dp[h- 1][w - 1] += 1

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

Submission status: Wrong Answer

Solution code:
h, w = map(int, input().split())
s = [input() for i in range(h)]
yoko_lis =[]
tate_lis =[]
cnt = 0
for i in range(h):
    a=s[i].count("#")
    yoko_lis.append(a)
for i in range(h):
   for i1 in range(w):  
    if s[i][i1]=="#":
        cnt+=1
   tate_lis.append(cnt)     
print(min(yoko_lis)+min(tate_lis))

Submission status: Wrong Answer

Solution code:
h, w = list(map(int, input().split(" ")))
matrix = []
result = []
r_0 = ""
c_0 = ""
r_1 = ""
c_1 = ""

for i in range(h):
    matrix.append(input())
    
def check(x, y, count, r_0, c_0, r_1, c_1):
  if x > (h - 1):
    return
  if y > (w - 1):
    return

  if matrix[x][y] == "#":
    if result and min(result) < count:
      return
    count += 1
    if r_0 == "" and c_0 == "" and r_1 == "" and c_1 == "":
      r_0 = x
      c_0 = y
      r_1 = x
      c_1 = y
    elif r_0 != "" and c_0 != "":
      r_1 = x
      c_1 = y
      if (r_1 - r_0) != (c_1 - c_0):
        return
      if (c_0 - r_0) != (c_1 - r_1):
        return 
  if x == (w - 1) and y == (h - 1):
    result.append(count)
  check(x+1, y, count, r_0, c_0, r_1, c_1)
  check(x, y+1, count, r_0, c_0, r_1, c_1)

check(0, 0, 0, r_0, c_0, r_1, c_1)
min_result = min(result) if result else 0
print(min_result)

Submission status: Wrong Answer

Solution code:
import copy
n,m=map(int,input().split())
l=[]
for i in range(n):
    s=list(input())
    l.append(s)
flag=0
s=copy.deepcopy(l)
#print(l)
black=0
white=0
if(l[0][0]=="#"):
    l[0][0]=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])
#for first half
if(s[0][0]=="."):
    s[0][0]=1 
else:
    s[0][0]=0;
count=0
for i in range(1,n):
    if(s[i][0]=="."):
        s[i][0]=s[i-1][0]+2
    else:
        s[i][0]=s[i-1][0]
for i in range(1,m):
    if( s[0][i]=="."):
        s[0][i]=s[0][i-1]+1 
    else:
        s[0][i]=s[0][i-1]

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

print(min(l[n-1][m-1],(s[n-1][m-1]+1)))
#print(mb)
#print(white)
'''if(l[0][0]==1):
    if mb>white:
        print(mb+1)
    else:
        print(mb)
else:
    print(mb)'''

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 j in range(w+1):
    for i in range(h+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

# 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:
h,w =map(int,input().split())
ls = []
for i in range(h):
    ls.append(list(input()))
ma = [[(10**9)]*w for i in range(h)]
fl =  [[-1]*w for i in range(h)]
if ls[0][0] == "." :
    ma[0][0] = 0
else: ma[0][0] =1
delta = [(-1,0),(0,-1)]
for y in range(h):
    for x in range(w):
        for dy,dx in delta:
            if 0<=y+dy<=h-1 and 0<=x+dx<=w-1 :
                if ls[y][x] == ls[y+dy][x+dx]:
                    fl[y][x] = fl[y+dy][x+dx]
                else:
                    fl[y][x] = fl[y+dy][x+dx]*(-1)
                ma[y][x] = min(ma[y][x],ma[y+dy][x+dx]+max(fl[y][x],0))
print(ma[h-1][w-1])

Submission status: Wrong Answer

Solution code:
import heapq
import sys

readline = sys.stdin.buffer.readline


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

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

    start_point = (0, 0)
    # goal_point = (H - 1, W - 1)
    dr = 0  # 前の進行方向(1,2)

    queue = []
    heapq.heappush(queue, (start_point, dr))

    tests = ((1, 0), (0, 1))

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

    while queue:
        queue_next = []

        for _ in range(len(queue)):
            (y, x), pdr = heapq.heappop(queue)

            for dy, dx in tests:
                ny = y + dy
                nx = x + dx

                if nx >= W or ny >= H:
                    continue

                ndr = 1 if dy == 1 else 2

                if S[ny][nx] == S[y][x] == "#":
                    if (pdr == 1 and ndr == 1) or (pdr == 2 and ndr == 2):
                        if dp[ny][nx] <= dp[y][x]:
                            continue
                        else:
                            dp[ny][nx] = dp[y][x]
                            heapq.heappush(queue_next, ((ny, nx), ndr))
                    else:
                        if dp[ny][nx] <= dp[y][x] + 1:
                            continue
                        else:
                            dp[ny][nx] = dp[y][x] + 1
                        heapq.heappush(queue_next, ((ny, nx), ndr))

                elif S[ny][nx] == ".":
                    if dp[ny][nx] <= dp[y][x]:
                        continue
                    else:
                        dp[ny][nx] = dp[y][x]
                        heapq.heappush(queue_next, ((ny, nx), ndr))

                elif S[y][x] == "." and S[ny][nx] == "#":
                    if dp[ny][nx] <= dp[y][x] + 1:
                        continue
                    else:
                        dp[ny][nx] = dp[y][x] + 1
                        heapq.heappush(queue_next, ((ny, nx), ndr))

        queue = queue_next

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


main()

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  town[new_h][new_w] != "#" and visited_list[new_h][new_w] > cnt:
                visited_list[new_h][new_w] = cnt
                stack.append([new_h, new_w, cnt])
            elif town[h][w] == "#" and town[new_h][new_w] == "#" and visited_list[new_h][new_w] > cnt + 1:
                visited_list[new_h][new_w] = cnt
                stack.append([new_h, new_w, cnt])
            elif town[new_h][new_w] == "#" and visited_list[new_h][new_w] > cnt + 1:
                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 numpy as np
h, w = map(int, input().split())
s = [input() for _ in range(h)]

dp = np.zeros(h * w).reshape(h, w)

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

for i in range(h - 1):
    for j in range(w - 1):
        if s[i + 1][j + 1] == "." or (s[i][j + 1] == s[i + 1][j + 1] and s[i + 1][j + 1] == s[i + 1][j]):
            dp[i + 1][j + 1] = min(dp[i][j + 1], dp[i + 1][j])
        elif s[i][j + 1] == s[i + 1][j + 1] and s[i + 1][j + 1] != s[i + 1][j]:
            dp[i + 1][j + 1] = min(dp[i][j + 1], dp[i + 1][j] + 1)
        elif s[i][j + 1] != s[i + 1][j + 1] and s[i + 1][j + 1] == s[i + 1][j]:
            dp[i + 1][j + 1] = min(dp[i][j + 1] + 1, dp[i + 1][j])
        else:
            dp[i + 1][j + 1] = min(dp[i][j + 1] + 1, dp[i + 1][j] + 1)
    
if s[h - 1][w - 1] == "#" and not (s[0][0] == "#" and (dp[h - 2][w - 1] == 1 or dp[h - 1][w - 2] == 1)):
    dp[h- 1][w - 1] += 1

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

Submission status: Wrong Answer

Solution code:
H, W = map(int, input().split())

field = []
for i in range(H):
  field.append(list(input()))
  field[i].append('.')

field.append(['.' for i in range(W + 1)])

cnt_field = [[H + W for i in range(W + 1)] for j in range(H + 1)]

if field[0][0] == '.':
  cnt_field[0][0] = 0
else:
  cnt_field[0][0] = 1

for i in range(1, H + W):
  if i < H:
    cnt = i
    ini_x = i - 1
    ini_y = 0
  elif H <= i and i <= W:
    cnt = H
    ini_x = i - 1
    ini_y = 0
  else:
    cnt = H - i % W
    ini_x = W - 1
    ini_y = i - W


  for j in range(cnt):
    score = cnt_field[ini_y + j][ini_x - j]
    # 右の場合
    if field[ini_y + j][ini_x - j + 1] == '.':
      r_flag = 0
    else:
      r_flag = 1

    if cnt_field[ini_y + j][ini_x - j] + r_flag <= cnt_field[ini_y + j][ini_x - j + 1]:
      cnt_field[ini_y + j][ini_x - j + 1] = cnt_field[ini_y + j][ini_x - j] + r_flag
    
    # 下の場合
    if field[ini_y + j + 1][ini_x - j] == '.':
      d_flag = 0
    else:
      d_flag = 1
    
    if cnt_field[ini_y + j][ini_x - j] + d_flag <= cnt_field[ini_y + j + 1][ini_x - j]:
      cnt_field[ini_y + j + 1][ini_x - j] = cnt_field[ini_y + j][ini_x - j] + d_flag

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

Submission status: Wrong Answer

Solution code:
import sys
from heapq import heappop, heappush
sys.setrecursionlimit(10000000)

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

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

while len(que):
    dist, px, py, flg = heappop(que)
    if d[h-1][w-1] < dist:
      break
    for dx, dy in [(0, 1), (1, 0)]:
        qx, qy = px + dx, py + dy
        if not (0 <= qx < h and 0 <= qy < w):
          continue
        if d[qx][qy] > dist + (flg and c[qx][qy]=='#'):
            if flg and c[qx][qy]=='#':
              d[qx][qy] = dist + 1
              heappush(que, (d[qx][qy], qx, qy, False))
            elif flg:
              d[qx][qy] = dist
              heappush(que, (d[qx][qy], qx, qy, True))
            if flg==False and c[qx][py]=='#':
              d[qx][qy] = dist
              heappush(que, (d[qx][qy], qx, qy, False))
            elif flg == False:
              d[qx][qy] = dist
              heappush(que, (d[qx][qy], qx, qy, True))
print(d[h-1][w-1])

Submission status: Wrong Answer

Solution code:
dp = dict()


def recur(arr, i, j):
    if i >= h and j >= w:
        return 0
    if i >= h:
        return recur(arr, i, j+1)+(0, 1)[mat[i-1][j] == '#']
    if j >= w:
        return recur(arr, i+1, j)+(0, 1)[mat[i][j-1] == '#']
    if i in dp.keys():
        if j in dp[i].keys():
            return dp[i][j]
    if i not in dp.keys():
        dp[i] = dict()
    if j not in dp[i].keys():
        dp[i][j] = 0
    dp[i][j] = min(recur(arr, i+1, j)+(0, 1)[mat[i][j] == '#'], recur(arr, i, j+1)+(0, 1)[mat[i][j] == '#'])
    return dp[i][j]


h, w = map(int, input().split())
mat = []
for i in range(h):
    mat.append(list(input()))
print(recur(mat, 0, 0))

Submission status: Wrong Answer

Solution code:
h,w=map(int,input().split())
s=[list(input()) for i in range(h)]
count=0
x=0
y=0
pos=[[0,0,0]]
def stansaku(kyori,pos):
  while len(pos)>0:
    x,y,count = pos.pop(0)
    if x<h-1 and s[x+1][y]==".":
      pos.append([x+1,y,count+1])
      if kyori[0]<(count+1):
        kyori[0]=count+1
        kyori[1]=x+1
        kyori[2]=y
    if y<w-1 and s[x][y+1]==".":
      pos.append([x,y+1,count+1])
      if kyori[0]<(count+1):
   	    kyori[0]=count+1
   	    kyori[1]=x
   	    kyori[2]=y+1  
  return kyori

def ktansaku(kyori,pos):
  while len(pos)>0:
    x,y,count = pos.pop(0)
    if x<h-1 and s[x+1][y]=="#":
      pos.append([x+1,y,count+1])
      if kyori[0]<(count+1):
        kyori[0]=count+1
        kyori[1]=x+1
        kyori[2]=y
    if y<w-1 and s[x][y+1]=="#":
      pos.append([x,y+1,count+1])
      if kyori[0]<(count+1):
   	    kyori[0]=count+1
   	    kyori[1]=x
   	    kyori[2]=y+1  
  return kyori

    
if s[0][0]==".":
  flag=0
else:
  flag=1
  count+=1
ans=0
anss=[]
while ans<h+w-3:
  if flag==1:
    count+=1
    if x==0 and y==0:
      pos=[[0,0,0]]
      anss=ktansaku([0,0,0],pos)
      ans+=anss[0]
      x=anss[1]
      y=anss[2]
      flag=0
    else:
      pos=[[x,y,0]]
      anss=ktansaku([x,y,0],pos)
      ans+=anss[0]
      x=anss[1]
      y=anss[2]
      flag=0
  else:
    if x==0 and y==0:
      pos=[[0,0,0]]
      anss=stansaku([0,0,0],pos)
      ans+=anss[0]
      x=anss[1]
      y=anss[2]
      flag=1
    else:
      pos=[[x,y,0]]
      anss=stansaku([x,y,0],pos)
      ans+=anss[0]
      x=anss[1]
      y=anss[2]
      flag=1
print(count)

Submission status: Wrong Answer

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

for h in range(H):
    for w in range(W):
        if h==0:
            if w==0: #原点
                if s[h][w]=="#":
                    M[h][w]=1
            elif w>0: #最上行
                if s[h][w]==".":
                    M[h][w]=M[h][w-1]
                else:
                    if M[h][w-1]=="#":
                        M[h][w]=M[h][w-1]
                    else:
                        M[h][w]=M[h][w-1]+1
        elif w==0: #最左列
            if s[h][w]==".":
                M[h][w]=M[h-1][w]
            else:
                if M[h-1][w]=="#":
                    M[h][w]=M[h-1][w]
                else:
                    M[h][w]=M[h-1][w]+1
        else: #一般的な位置
            if s[h][w]==".":
                M[h][w]=min(M[h-1][w],M[h][w-1])
            else:
                if M[h-1][w]=="#" or M[h][w-1]=="#":
                    M[h][w]=min(M[h-1][w],M[h][w-1])
                else:
                    M[h][w]=min(M[h-1][w],M[h][w-1])+1
print(M[H-1][W-1])

Submission status: Wrong Answer

Solution code:
import sys
from collections import deque
sys.setrecursionlimit(10**7)
import numpy as np


def DFS(x,y,num):
    S[x][y]="."
    D[x][y]=num
    for a,b in ((0,1),(0,-1),(1,0),(-1,0)):
        X,Y=x+a,y+b
        if S[X][Y]=="#" and 1<=X<=h and 1<=Y<=w:
            DFS(X,Y,num)


def BFS(x,y):
    color[x][y]="gray"
    D[x][y]=0 if S[x][y]!="#" else 1
    queue=deque([[x,y]])

    while len(queue)!=0:
        a,b=queue.popleft()
        for c,d in [[0,1],[1,0]]:
            X,Y=a+c,b+d
            if color[X][Y]=="white" and (1<=X<=h and 1<=Y<=w):
                color[X][Y]="gray"
                if S[X][Y]=="#":
                    if (a==1 and b==1) and D[1][1]==1:D[X][Y]=D[a][b]
                    else:D[X][Y]=min(D[X-1][Y]+1,D[X][Y-1]+1)
                    DFS(X,Y,D[X][Y])
                elif S[X][Y]=="." and D[X][Y]==inf:
                    D[X][Y]=min(D[X-1][Y],D[X][Y-1])
                queue.append([X,Y])
                #print(np.array(D))
        color[a][b]="black"
    #print(np.array(D))
    return D[h][w]


h,w=map(int,input().split())
S=[["#"]+list(input())+["#"] for _ in range(h)]
S.insert(0,["#"]*(w+2))
S.append(["#"]*(w+2))

inf=float("inf")
color=[["white" for _ in range(w+2)] for _ in range(h+2)]
D=[[inf for _ in range(w+2)] for _ in range(h+2)]

print(BFS(1,1))

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:
import numpy as np
h, w = map(int, input().split())
s = [input() for _ in range(h)]

dp = np.zeros(h * w).reshape(h, w)

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

for i in range(h - 1):
    for j in range(w - 1):
        if s[i + 1][j + 1] == "." or (s[i][j + 1] == s[i + 1][j + 1] and s[i + 1][j + 1] == s[i + 1][j]):
            dp[i + 1][j + 1] = min(dp[i][j + 1], dp[i + 1][j])
        elif s[i][j + 1] == s[i + 1][j + 1] and s[i + 1][j + 1] != s[i + 1][j]:
            dp[i + 1][j + 1] = min(dp[i][j + 1], dp[i + 1][j] + 1)
        elif s[i][j + 1] != s[i + 1][j + 1] and s[i + 1][j + 1] == s[i + 1][j]:
            dp[i + 1][j + 1] = min(dp[i][j + 1] + 1, dp[i + 1][j])
        else:
            dp[i + 1][j + 1] = min(dp[i][j + 1] + 1, dp[i + 1][j] + 1)
    
if s[h - 1][w - 1] == "#" and not (s[0][0] == "#" and dp[h - 2][w - 1] == 1 or dp[h - 1][w - 2] == 1):
    dp[h- 1][w - 1] += 1

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