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:
H,W=map(int,input().split())
table=[[0]*W for i in range(H)]
table1=[[0]*W for i in range(H)]
table2=[[0]*W for i in range(H)]
for i in range(H):
  s=str(input())
  for j in range(W):
    if s[j]=='#':
      table1[i][j]=1
    else:
      table2[i][j]=1
for i in range(H):
  for j in range(W):
    if i==0:
      if j==0:
        pass
      else:
        table1[i][j]+=table1[i][j-1]
        table2[i][j]+=table2[i][j-1]
        if table1[i][j]<=table2[i][j]+1:
          table[i][j]+=table1[i][j]
        else:
          table[i][j]+=(table2[i][j]+1)
    else:
      if j>=1:
        x,y=table1[i-1][j],table1[i][j-1]
        table1[i][j]+=min(x,y)
        X,Y=table2[i-1][j],table2[i][j-1]
        table2[i][j]+=min(X,Y)
        if table1[i][j]<=table2[i][j]+1:
          table[i][j]+=table1[i][j]
        else:
          table[i][j]+=(table2[i][j]+1)
      else:
        table1[i][j]+=table1[i-1][j]
        table2[i][j]+=table2[i-1][j]
        if table1[i][j]<=table2[i][j]+1:
          table[i][j]+=table1[i][j]
        else:
          table[i][j]+=(table2[i][j]+1)
print(table[H-1][W-1])

Submission status: Wrong Answer

Solution code:
h, w = [int(x) for x in input().split()]
input_ = [list(input()) for _ in range(h)]
memo = [[0 for i in range(w)] for _ in range(h)]


for i in range(h):
  w_ = input_[i]
  if i == 0:
    for x in range(len(w_)):
      if x == 0:
        if w_[x] == '#':
          memo[i][x] = 1
      else:
        if w_[x] == '#':
          memo[i][x] = memo[i][x-1] + 1
        else:
          memo[i][x] = memo[i][x-1]
  else:
    for x in range(len(w_)):
      if w_[x] == '#':
        if x==0:
          a = 10**9
          b = memo[i-1][x] + 1
        else:
          a = memo[i][x-1] + 1
          b = memo[i-1][x] + 1

        memo[i][x] = min(a, b)
      else:
        if x==0:
          a = 10**9
          b = memo[i-1][x]
        else:
          a = memo[i][x-1]
          b = memo[i-1][x]
        memo[i][x] = min(a, b)




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

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 = list([(0,0,1)])
else:
    q = list([(0,0,0)])
 
# スタートを設定してsをコピー
t = copy.deepcopy(t_tmp)
#print(t)
tmp_list = []
while q:
    print(q)
    q = list(set(q))

    x,y,c = q[0]
    q.pop(0)
    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] = '#'
            #if q.count((nx,ny,c)) == 0:
            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] = '#'
                #if q.count((nx,ny,c+1)) == 0:
                #    q.append((nx,ny,c+1))
                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 tmp_list == []:
    print('0')
else:
    print(min(tmp_list))

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])

Submission status: Wrong Answer

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

s = []
for i in range(h):
    p = input()
    u = []
    for j in p:
        u.append(j)
    s.append(u)

c = 0
if s[0][0] == "#" and s[h-1][w-1] == "#":
    c += 2
    s[0][0] = "S"
    s[h-1][w-1] = "G"
elif s[0][0] == "#" or s[h-1][w-1] == "#":
    c += 1
    s[0][0] = "S"
    s[h-1][w-1] = "T"
else:
    s[0][0] = "S"
    s[h-1][w-1] = "G"

sh = 0
sw = 0

def dfs(sh, sw, s, c):
    if s[sh][sw] == "G":
        print(c)
        exit()
        
    else:
        if sh+1 < h and s[sh+1][sw] != "#":
            sh += 1
            dfs(sh, sw, s,c)
        elif sw+1 < w and s[sh][sw+1] != "#":
            sw += 1
            dfs(sh, sw, s,c)
        elif( sw+1 < w and s[sh][sw+1] == "#" ) and (sh+1 < h and s[sh+1][sw] == "#"):
            
            print()
            s[sh][sw] = "Y"
            for b in s:
                print("".join(b))
            print()

            if sw+2 < w and s[sh][sw+2] != "#":
                c+=1
                s[sh][sw+1] = "T"
                sw += 1
                dfs(sh,sw,s,c)
            elif sh+2 < h and s[sh+2][sw] != "#":
                c+=1
                s[sh+1][sw] = "T"
                sh += 1
                dfs(sh,sw,s,c)
            elif (sh+2 < h and s[sh+2][sw] == "G") or (sw+2 < w and s[sh][sw+2] == "G"):
                print(c)

dfs(sh, sw, s, c)
#print()
#for i in s:
#    print("".join(i))

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 h == 1 and w == 1:
    if s[0][0] == "#":
        dp[0][0] == 1
    else:
        dp[0][0] == 0
elif h == 1:
    if s[h - 1][w - 1] == "#" and (s[0][0] == "#" and dp[h - 1][w - 2] != 1):
        dp[h- 1][w - 1] += 1
elif w == 1:
    if s[h - 1][w - 1] == "#" and (s[0][0] == "#" and dp[h - 2][w - 1] != 1):
        dp[h- 1][w - 1] += 1
else:
    if s[h - 1][w - 1] == "#" and (s[0][0] == "#" and (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:
import heapq
 
h,w=map(int,input().split())
S=[]
for i in range(h):
    S.append(input())
    
visited=[[0]*w for _ in range(h)]
 
q=[(0,0,0)]
 
heapq.heapify(q)
visited=[[0]*w for _ in range(h)]
cnt=0
 
while q:
    cnt,px,py=heapq.heappop(q)
    if  visited[px][py]==1:
        continue
    visited[px][py]=1
    if px==h-1 and py==w-1:
        if cnt==0 and S[0][0]=='#':
            print(0)
        elif cnt%2==0:
            print(cnt//2)
        else:
            print(cnt//2+1)
        break
    for x,y in [(1,0),(0,1)]:
        if x+px>=h or y+py>=w:
            continue
        if S[px+x][py+y]!=S[px][py]:
            heapq.heappush(q,(cnt+1,px+x,py+y))
        else:
            heapq.heappush(q,(cnt,px+x,py+y))

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()
s = "#"

C = copy.deepcopy(c)
    

dy_dx = [[1,0],[0,1]]
  
def bfs():
    global ans
    global s
    """
    for i in range(h):
      for j in range(w):
        print(C[i][j],end="")
      print("")
    print("-----------------")
    print(ans)
    """
    queue = []
    visited = [[0 for i in range(w)] for i in range(h)]

    queue.append([0,0])
    visited[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
                    C[y][x] = s
                    C[now[0]][now[1]] = s
                    queue.append([y,x])
                    
        if visited[h-1][w-1] != 0:
            if s == ".":
              ans += 1
            print(ans)
            sys.exit()
    if s == "#":
      ans += 1
    if s == '#':
      s = "."
    else:
      s = "#"
    bfs()
        
bfs()

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)] # 最短経路でそのノードのひとつ前に到達するノードのリスト
previous_color = [''] * (H*W+1)
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 previous_color[target_min_index]=='.':
        route_dis = 1 
    if distance[ind] > distance[target_min_index] + route_dis:
      distance[ind] = distance[target_min_index] + route_dis # 過去に設定されたdistanceよりも小さい場合はdistanceを更新
      previous_color[ind] =  S[target_h][target_w]
      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
def fastio():
    from io import StringIO
    from atexit import register
    global input
    sys.stdin = StringIO(sys.stdin.read())
    input = lambda : sys.stdin.readline().rstrip('\r\n')
    sys.stdout = StringIO()
    register(lambda : sys.__stdout__.write(sys.stdout.getvalue()))
fastio()

INF = 10**20
MOD = 10**9 + 7
I = lambda:list(map(int,input().split()))
# from math import gcd
from math import ceil
from collections import defaultdict as dd, Counter
from bisect import bisect_left as bl, bisect_right as br

h, w = I()
g = []
for i in range(h):
    g.append(list(input()))

dp = [[INF] * (w + 1) for i in range(h + 1)]
dp[0][0] = dp[1][0] = dp[0][1] = 0
for i in range(1, h + 1):
    for j in range(1, w + 1):
        dp[i][j] = min(dp[i - 1][j], dp[i][j - 1])
        if g[i - 1][j - 1] == '#':
            dp[i][j] += 1

print(dp[h][w])

Submission status: Wrong Answer

Solution code:
import copy
H, W = map(int, input().split())
s = [[0] * W]
minus = 0
tmp = [list(input()) for _ in range(H)]
for i in range(H):
    s.append(tmp[i])
if s[1][0] == '#':
    minus = 1
    for i in range(W):
        s[0][i] = 1
else:
    s[0][0] = 0

scopy = copy.deepcopy(s)
for i in range(1, H + 1):
    for j in range(W):
        if s[i][j] == '#':
            if j != 0 and i == 1:
                s[i][j] = s[i][j - 1] + 1
            elif j != 0:
                s[i][j] = min(s[i - 1][j] + 1, s[i][j - 1] + 1)
            else:
                s[i][j] = s[i - 1][j] + 1
            for k in range(i, H):
                if k == i:
                    for l in range(j, W):
                        if l == j: continue
                        if s[k][l] != '.':
                            s[k][l] = s[i][j]
                        else:
                            break
                else:
                    if s[k + 1][j] == '.':
                        s[k][j] = s[i][j]
                    else:
                        break
        else:
            index = 0
            if scopy[i][j] == '#':
                index += 1
            if j != 0 and i == 1:
                s[i][j] = s[i][j - 1] + index
            elif j != 0:
                s[i][j] = min(s[i - 1][j] + index, s[i][j - 1] + index)
            else:
                s[i][j] = s[i - 1][j] + index

print(s[-1][-1] - minus)

Submission status: Wrong Answer

Solution code:
h, w = map(int, input().split())
ans = []
for i in range(h):
    ans.append([9999999999] * w)
arr = []
for i in range(h):
    s = list(input())
    arr.append(s)
if arr[0][0] == '#': ans[0][0] = 1
else: ans[0][0] = 0
for i in range(h):
    for j in range(w):
        if i == 0 and j == 0: continue
        if j - 1 >= 0: 
            ans[i][j] = min(ans[i][j], ans[i][j - 1])
        if i - 1 >= 0: ans[i][j] = min(ans[i][j], ans[i - 1][j])
        if arr[i][j] == '#': 
            if j - 1 >= 0:
                if ans[i][j] == ans[i][j - 1]:
                    if arr[i][j - 1] == '.':
                        ans[i][j] -= -1
                        continue
            if i - 1 >= 0:
                if ans[i][j] == ans[i - 1][j]:
                    if arr[i - 1][j] == '.':
                        ans[i][j] -= -1
print(ans[h - 1][w - 1])

Submission status: Wrong Answer

Solution code:
H, W = map(int, input().rstrip().split())
D = []
for h in range(H):
    D.append(list(input().rstrip()))
# print(*D, sep='\n')
d = {}
for i in range(1, H + W):  # i: total
    for h in range(i):
        w = i - h - 1
        if h > H:
            h = H - 1
            w = i - h
        if w >= W or h >= H or w < 0 or h < 0:
            continue
        # print(h, w)
        if (h - 1, w) in d.keys() and (h, w - 1) in d.keys():
            d[(h, w)] = min(d[(h - 1, w)], d[(h, w - 1)])
        elif (h - 1, w) in d.keys():
            d[(h, w)] = d[(h - 1, w)]
        elif (h, w - 1) in d.keys():
            d[(h, w)] = d[(h, w - 1)]
        else:
            d[(h, w)] = 0
        if D[h][w] == '#':
            d[(h, w)] += 1
print(d[(H - 1, W - 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 h == 1 and w == 1:
    if s[0][0] == "#":
        dp[0][0] == 1
    else:
        dp[0][0] == 0
elif h == 1:
    if s[h - 1][w - 1] == "#" and (s[0][0] != "#" or dp[h - 1][w - 2] != 1):
        dp[h- 1][w - 1] += 1
elif w == 1:
    if s[h - 1][w - 1] == "#" and (s[0][0] != "#" or dp[h - 2][w - 1] != 1):
        dp[h- 1][w - 1] += 1
else:
    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:
import copy
H, W = map(int, input().split())
s = [[0] * W]
minus = 0
tmp = [list(input()) for _ in range(H)]
for i in range(H):
    s.append(tmp[i])
if s[1][0] == '#':
    minus = 1
    for i in range(W):
        s[0][i] = 1
else:
    s[0][0] = 0

scopy = copy.deepcopy(s)
for i in range(1, H + 1):
    for j in range(W):
        if s[i][j] == '#':
            if j != 0 and i == 1:
                s[i][j] = s[i][j - 1] + 1
            elif j != 0:
                s[i][j] = min(s[i - 1][j] + 1, s[i][j - 1] + 1)
            else:
                s[i][j] = s[i - 1][j] + 1
            for k in range(i, H):
                if k == i:
                    for l in range(j, W):
                        if l == j: continue
                        if s[k][l] == '#':
                            s[k][l] = s[i][j]
                        else:
                            break
                else:
                    if s[k + 1][j] == '#':
                        s[k][j] = s[i][j]
                    else:
                        break
        else:
            index = 0
            if scopy[i][j] == '#':
                index += 1
            if j != 0 and i == 1:
                s[i][j] = s[i][j - 1] + index
            elif j != 0:
                s[i][j] = min(s[i - 1][j] + index, s[i][j - 1] + index)
            else:
                s[i][j] = s[i - 1][j] + index

print(s[-1][-1] - minus)

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==h-1 and c==w-1:
                    print(cnt+1)
                    sys.exit()
                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+1==h-1 and c==w-1:
                    print(cnt+1)
                    sys.exit()
                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

Submission status: Wrong Answer

Solution code:
import heapq
 
h,w=map(int,input().split())
S=[]
for i in range(h):
    S.append(input())
    
visited=[[0]*w for _ in range(h)]
 
q=[(0,0,0)]
 
heapq.heapify(q)
visited=[[0]*w for _ in range(h)]
cnt=0
 
while q:
    cnt,px,py=heapq.heappop(q)
    if  visited[px][py]==1:
        continue
    visited[px][py]=1
    if px==h-1 and py==w-1:
        if cnt%2==0:
            print(cnt//2)
        else:
            print(cnt//2+1)
        break
    for x,y in [(1,0),(0,1)]:
        if x+px>=h or y+py>=w:
            continue
        if S[px+x][py+y]!=S[px][py]:
            heapq.heappush(q,(cnt+1,px+x,py+y))
        else:
            heapq.heappush(q,(cnt,px+x,py+y))

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

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 h == 1 and w == 1:
    if s[0][0] == "#":
        dp[0][0] == 1
    else:
        dp[0][0] == 0
elif h == 1:
    if s[h - 1][w - 1] == "#" and (s[0][0] != "#" or dp[h - 1][w - 2] == 1):
        dp[h- 1][w - 1] += 1
elif w == 1:
    if s[h - 1][w - 1] == "#" and (s[0][0] != "#" or dp[h - 2][w - 1] != 1):
        dp[h- 1][w - 1] += 1
else:
    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:
# a_5
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 = list([(0,0,1)])
else:
    q = list([(0,0,0)])
 
# スタートを設定してsをコピー
t = copy.deepcopy(t_tmp)
#print(t)
tmp_list = []
while q:
    #print(q)
    x,y,c = q[0]
    q.pop(0)
    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] = '#'
            if q.count((nx,ny,c)) == 0:
                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] = '#'
                if q.count((nx,ny,c+1)) == 0:
                    q.append((nx,ny,c+1))
                #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 tmp_list == []:
    print('0')
else:
    print(min(tmp_list))

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]-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

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

t = 1
i = 0
j = 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 < W-1 and A[i][j+1] == ".":
        dp[i][j+1] = min(dp[i][j+1],dp[i][j])
    if i < H-1 and A[i+1][j] == "#":
        dp[i+1][j] = min(dp[i+1][j], dp[i][j]+1)
    if j < W-1 and A[i][j+1] == "#":
        dp[i][j+1] = min(dp[i][j+1], dp[i][j]+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])