Problem:


Score : 400 points

Problem Statement

Consider a grid with H rows and W columns of squares. Let (r, c) denote the square at the r-th row from the top and the c-th column from the left.
Each square is painted black or white.

The grid is said to be good if and only if the following condition is satisfied:

From (1, 1), we can reach (H, W) by moving one square right or down repeatedly, while always being on a white square.

Note that (1, 1) and (H, W) must be white if the grid is good.

Your task is to make the grid good by repeating the operation below. Find the minimum number of operations needed to complete the task. It can be proved that you can always complete the task in a finite number of operations.

Choose four integers r_0, c_0, r_1, c_1(1 \leq r_0 \leq r_1 \leq H, 1 \leq c_0 \leq c_1 \leq W). For each pair r, c (r_0 \leq r \leq r_1, c_0 \leq c \leq c_1), invert the color of (r, c) - that is, from white to black and vice versa.

Constraints

2 \leq H, W \leq 100

Input

Input is given from Standard Input in the following format:

H W
s_{11} s_{12} \cdots s_{1W}
s_{21} s_{22} \cdots s_{2W}
 \vdots
s_{H1} s_{H2} \cdots s_{HW}

Here s_{rc} represents the color of (r, c) - # stands for black, and . stands for white.

Output

Print the minimum number of operations needed.

Sample Input 1

3 3
.##
.#.
##.

Sample Output 1

1

Do the operation with (r_0, c_0, r_1, c_1) = (2, 2, 2, 2) to change just the color of (2, 2), and we are done.

Sample Input 2

2 2
#.
.#

Sample Output 2

2

Sample Input 3

4 4
..##
#...
###.
###.

Sample Output 3

0

No operation may be needed.

Sample Input 4

5 5
.#.#.
#.#.#
.#.#.
#.#.#
.#.#.

Sample Output 4

4



Sample input:
3 3
.##
.#.
##.


Sample output:
1

Submission status: Wrong Answer

Solution code:
import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
sys.setrecursionlimit(10 ** 7)

from math import ceil

h, w = map(int, readline().split())
s = [input() for i in range(h)]
dp = [[float('inf')] * w for j in range(h)]
if s[0][0] == '#':
    dp[0][0] = 1
else:
    dp[0][0] = 0
for i in range(h):
    if h - 1 != i:
        for j in range(w):
            if w - 1 != j:
                cnt = 0
                if s[i][j + 1] != s[i][j]:
                    cnt += 1
                dp[i][j + 1] = min(dp[i][j + 1], dp[i][j] + cnt)
            cnt = 0
            if s[i + 1][j] != s[i][j]:
                cnt += 1
            dp[i + 1][j] = min(dp[i + 1][j], dp[i][j] + cnt)
print(ceil(dp[-1][-1] / 2))

Submission status: Wrong Answer

Solution code:
h,w=map(int,input().split())
s=[input() for i in range(h)]
ans=[[0]*w]*h
if s[0][0]=='#':
  ans[0][0]=1
for i in range(1,w):
  if s[0][i-1]=='.' and s[0][i]=='#':
    ans[0][i]=ans[0][i-1]+1
  else:
    ans[0][i]=ans[0][i-1]

for i in range(1,h):
  if s[i-1][0]=='.' and s[i][0]=='#':
    ans[i][0]=ans[i-1][0]+1
  else:
    ans[i][0]=ans[i-1][0]

for i in range(1,h):
  for j in range(1,w):
    if s[i-1][j]=='.' and s[i][j]=='#':
      ans1=ans[i-1][j]+1
    else:
      ans1=ans[i-1][j]
    if s[i][j-1]=='.' and s[i][j]=='#':
      ans2=ans[i][j-1]+1
    else:
      ans2=ans[i][j-1]
    ans[i][j]=min(ans1,ans2)

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

Submission status: Wrong Answer

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

h,w = map(int,input().split())
sij = [input() for i in range(h)]

dp = [[10**18 for i in range(w)] for j in range(h)]

dp[0][0] = 0

for i in range(w-1):
    if sij[0][i+1] != sij[0][i]:
        dp[0][i+1] = dp[0][i]+1
    else:
        dp[0][i+1] = dp[0][i]
        
for i in range(h-1):
    if sij[i+1][0] != sij[i][0]:
        dp[i+1][0] = dp[i][0]+1
    else:
        dp[i+1][0] = dp[i][0]

for i in range(1,h):
    for j in range(1,w):
        #print(i,j)
        if sij[i-1][j] != sij[i][j]:
            sita = dp[i-1][j]+1
        else:
            sita = dp[i-1][j]
        if sij[i][j-1] != sij[i][j]:
            yoko = dp[i][j-1]+1
        else:
            yoko = dp[i][j-1]
        #print(i,j,sita,yoko)
        dp[i][j] = min(sita,yoko)

add = 0

if sij[0][0] == '#':
    add = 1

if dp[h-1][w-1] == 1:
    print(1)
else:
    print(dp[h-1][w-1]//2+add)

Submission status: Wrong Answer

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

h,w = map(int,input().split())
sij = [input() for i in range(h)]

dp = [[10**18 for i in range(w)] for j in range(h)]

dp[0][0] = 0

for i in range(w-1):
    if sij[0][i+1] != sij[0][i]:
        dp[0][i+1] = dp[0][i]+1
    else:
        dp[0][i+1] = dp[0][i]
        
for i in range(h-1):
    if sij[i+1][0] != sij[i][0]:
        dp[i+1][0] = dp[i][0]+1
    else:
        dp[i+1][0] = dp[i][0]

for i in range(1,h):
    for j in range(1,w):
        #print(i,j)
        if sij[i-1][j] != sij[i][j]:
            sita = dp[i-1][j]+1
        else:
            sita = dp[i-1][j]
        if sij[i][j-1] != sij[i][j]:
            yoko = dp[i][j-1]+1
        else:
            yoko = dp[i][j-1]
        #print(i,j,sita,yoko)
        dp[i][j] = min(sita,yoko)

add = 0

if sij[0][0] == '#':
    add = 1

if dp[h-1][w-1] == 1:
    print(1+add)
else:
    print(dp[h-1][w-1]//2+add)

Submission status: Wrong Answer

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

h,w = map(int,input().split())
sij = [input() for i in range(h)]

dp = [[10**18 for i in range(w)] for j in range(h)]

dp[0][0] = 0

for i in range(w-1):
    if sij[0][i+1] != sij[0][i]:
        dp[0][i+1] = dp[0][i]+1
    else:
        dp[0][i+1] = dp[0][i]
        
for i in range(h-1):
    if sij[i+1][0] != sij[i][0]:
        dp[i+1][0] = dp[i][0]+1
    else:
        dp[i+1][0] = dp[i][0]

for i in range(1,h):
    for j in range(1,w):
        #print(i,j)
        if sij[i-1][j] != sij[i][j]:
            sita = dp[i-1][j]+1
        else:
            sita = dp[i-1][j]
        if sij[i][j-1] != sij[i][j]:
            yoko = dp[i][j-1]+1
        else:
            yoko = dp[i][j-1]
        #print(i,j,sita,yoko)
        dp[i][j] = min(sita,yoko)

add = 0

#print(dp)

if sij[0][0] == '#':
    add = 1

print(dp[h-1][w-1]//2+add)

Submission status: Wrong Answer

Solution code:
INF = float('inf')

def main():
    H,W = map(int,input().split())
    mat = [list(input()) for _ in range(H)]
    dp = [[INF] * W for _ in range(H)]
    if mat[0][0] == "#":
        dp[0][0] = 1
    else:
        dp[0][0] = 0
    for i in range(H):
        for j in range(W):
            if i == 0 and j == 0:
                continue
            if i == 0:
                dp[i][j] = dp[i][j - 1]
                if mat[i][j] == "#":
                    dp[i][j] += 1
            elif j == 0:
                dp[i][j] = dp[i - 1][j]
                if mat[i][j] == "#":
                    dp[i][j] += 1
            else:
                dp[i][j] = min(dp[i - 1][j], dp[i][j - 1])
                if mat[i][j] == "#":
                    dp[i][j] += 1
    print(dp[H-1][W-1])

if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
from collections import deque
INFTY = 10**3
def flip(x):
    if x=="#":
        return "."
    else:
        return "#"
H,W = map(int,input().split())
S = [input().strip() for _ in range(H)]
hist = [[INFTY for _ in range(W)] for _ in range(H)]
for i in range(H):
    for j in range(W):
        if hist[i][j]<INFTY:continue
        if i==0 and j==0:
            d = 0
        elif i==0 and j>0:
            d = hist[i][j-1]+1
        elif i>0 and j==0:
            d = hist[i-1][j]+1
        else:
            d = min(hist[i-1][j],hist[i][j-1])+1
        que = deque([(i,j,d,S[i][j])])
        hist[i][j] = d
        while que:
            i1,j1,d1,a1 = que.popleft()
            if j1+1<W and hist[i1][j1+1]>=INFTY and S[i1][j1+1]==a1:
                hist[i1][j1+1]=d1
                que.append((i1,j1+1,d1,a1))
            if i1+1<H and hist[i1+1][j1]>=INFTY and S[i1+1][j1]==a1:
                hist[i1+1][j1]=d1
                que.append((i1+1,j1,d1,a1))
if S[0][0]=="#" and S[H-1][W-1]=="#":
    print(1+(hist[H-1][W-1])//2)
else:
    print((hist[H-1][W-1])//2)

Submission status: Wrong Answer

Solution code:
import numpy as np

H, W = map(int, input().split())
temp = [list(input().replace("#","0").replace(".","1")) for i in range(H)]
masu = [[int(temp[i][j]) for j in range(W)] for i in range(H)]


dp = np.zeros((H, W))
dp_flag = np.zeros((H, W))

if masu[0][0] == 0:
    dp[0][0] = 1
else:
    dp[0][0] = 0

for i in range(0,H):
    for j in range(0,W):
        if i == 0:
            a = 100000
        else:
            if masu[i][j] != masu[i-1][j]:
                if dp_flag[i-1][j] == 1:
                    dp_flag[i][j] = 0
                    a = dp[i-1][j]
                else:
                    dp_flag[i][j] = 1
                    a = dp[i-1][j] + 1
            else:
                a = dp[i-1][j]
        if j == 0:
            b = 100000
        else:
            if masu[i][j] != masu[i][j-1]:
                if dp_flag[i][j-1] == 1:
                    dp_flag[i][j] = 0
                    b = dp[i][j-1]
                else:
                    dp_flag[i][j] = 1
                    b = dp[i][j-1] + 1
            else:
                b = dp[i][j-1]
        if not(a == 100000 and b == 100000):
            dp[i][j] = min([a, b])
print(int(dp[H-1][W-1]))

Submission status: Wrong Answer

Solution code:
import numpy as np

H, W = map(int, input().split())
temp = [list(input().replace("#","0").replace(".","1")) for i in range(H)]
masu = [[int(temp[i][j]) for j in range(W)] for i in range(H)]


dp = np.zeros((H, W))
dp_flag = np.zeros((H, W))

if masu[0][0] == 0:
    dp[0][0] = 1
else:
    dp[0][0] = 0

for i in range(0,H):
    for j in range(0,W):
        if i == 0:
            a = 100000
        else:
            if masu[i][j] != masu[i-1][j]:
                if dp_flag[i-1][j] == 1:
                    a = dp[i-1][j]
                else:
                    dp_flag[i][j] = 1
                    a = dp[i-1][j] + 1
            else:
                a = dp[i-1][j]
        if j == 0:
            b = 100000
        else:
            if masu[i][j] != masu[i][j-1]:
                if dp_flag[i][j-1] == 1:
                    b = dp[i][j-1]
                else:
                    dp_flag[i][j] = 1
                    b = dp[i][j-1] + 1
            else:
                b = dp[i][j-1]
        if a != 100000 or b != 100000:
            dp[i][j] = min([a, b])
print(int(dp[H-1][W-1]))

Submission status: Wrong Answer

Solution code:
import numpy as np

H, W = map(int, input().split())
temp = [list(input().replace("#","0").replace(".","1")) for i in range(H)]
masu = [[int(temp[i][j]) for j in range(W)] for i in range(H)]


dp = np.zeros((H, W))
dp_flag = np.zeros((H, W))

if masu[0][0] == 0:
    dp[0][0] = 1
    masu[0][0] = 1
else:
    dp[0][0] = 0

for i in range(0,H):
    for j in range(0,W):
        if i == 0:
            a = 100000
        else:
            if masu[i][j] != masu[i-1][j]:
                if dp_flag[i-1][j] == 1:
                    a = dp[i-1][j]
                else:
                    dp_flag[i][j] = 1
                    a = dp[i-1][j] + 1
            else:
                a = dp[i-1][j]
        if j == 0:
            b = 100000
        else:
            if masu[i][j] != masu[i][j-1]:
                if dp_flag[i][j-1] == 1:
                    b = dp[i][j-1]
                else:
                    dp_flag[i][j] = 1
                    b = dp[i][j-1] + 1
            else:
                b = dp[i][j-1]
        if a != 100000 or b != 100000:
            dp[i][j] = min([a, b])
print(int(dp[H-1][W-1]))

Submission status: Wrong Answer

Solution code:
import numpy as np

H, W = map(int, input().split())
temp = [list(input().replace("#","0").replace(".","1")) for i in range(H)]
masu = [[int(temp[i][j]) for j in range(W)] for i in range(H)]


dp = np.zeros((H, W))

if masu[0][0] == 0:
    dp[0][0] = 1
    masu[0][0] = 1
else:
    dp[0][0] = 0

for i in range(0,H):
    for j in range(0,W):
        if i == 0:
            a = 100000
        else:
            if masu[i][j] != masu[i-1][j]:
                a = dp[i-1][j] + 1
            else:
                a = dp[i-1][j]
        if j == 0:
            b = 100000
        else:
            if masu[i][j] != masu[i][j-1]:
                b = dp[i][j-1] + 1
            else:
                b = dp[i][j-1]
        if a != 100000 or b != 100000:
            dp[i][j] = min([a, b])
print(int(dp[H-1][W-1]))

Submission status: Wrong Answer

Solution code:
import numpy as np

H, W = map(int, input().split())
temp = [list(input().replace("#","0").replace(".","1")) for i in range(H)]
masu = [[int(temp[i][j]) for j in range(W)] for i in range(H)]


dp = np.zeros((H, W))

if masu[0][0] == 0:
    dp[0][0] = 1
    masu[0][0] = 1
else:
    dp[0][0] = 0

for i in range(1,H):
    for j in range(1,W):
        if i == 0:
            a = 100000
        else:
            if masu[i][j] != masu[i-1][j]:
                a = dp[i-1][j] + 1
            else:
                a = dp[i-1][j]
        if j == 0:
            b = 100000
        else:
            if masu[i][j] != masu[i][j-1]:
                b = dp[i][j-1] + 1
            else:
                b = dp[i][j-1]
        dp[i][j] = min([a, b])
print(int(dp[H-1][W-1]))

Submission status: Wrong Answer

Solution code:
import numpy as np

H, W = map(int, input().split())
temp = [list(input().replace("#","0").replace(".","1")) for i in range(H)]
masu = [[int(temp[i][j]) for j in range(W)] for i in range(H)]


dp = np.zeros((H, W))
dp[0][0] = 0

for i in range(1,H):
    for j in range(1,W):
        if i == 0:
            a = 100000
        else:
            if masu[i][j] != masu[i-1][j]:
                a = dp[i-1][j] + 1
            else:
                a = dp[i-1][j]
        if j == 0:
            b = 100000
        else:
            if masu[i][j] != masu[i][j-1]:
                b = dp[i][j-1] + 1
            else:
                b = dp[i][j-1]
        dp[i][j] = min([a, b])
print(int(dp[H-1][W-1]))

Submission status: Wrong Answer

Solution code:
import numpy as np
import scipy
H,W = (int(x) for x in input().split())
lines = [input() for i in range(H)]
dp = [[0] * W for _ in range(H)]
if lines[0][0] == "#":
    dp[0][0] = 1
q = r = dp[0][0]
for i in range(H):
    for j in range(W):
        if i == j == 0: continue
        elif lines[i][j] == "#" and lines[i][j-1] == ".":
            q = dp[i][j-1] + 1
        if i > 0:
            if lines[i][j] == "#" and lines[i-1][j] == ".":
                r = dp[i-1][j] + 1
        else: 
            dp[i][j] = q
            continue
        dp[i][j] = min(q,r)
        q = dp[i][j]
print(dp[H-1][W-1])

Submission status: Wrong Answer

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

dist = [[10**7] * W for _ in range(H)]
dist[0][0] = 0

for i in range(H):
    for j in range(W):
        if j != W-1:
            if S[i][j+1] == '.' or S[i][j] == '#':
                dist[i][j+1] = min(dist[i][j], dist[i][j+1])
            else:
                dist[i][j+1] = min(dist[i][j]+1, dist[i][j+1])
        if i != H-1:
            if S[i+1][j] == '.' or S[i][j] == '#':
                dist[i+1][j] = min(dist[i][j], dist[i+1][j])
            else:
                dist[i+1][j] = min(dist[i][j]+1, dist[i+1][j])

if S[H-1][W-1] == '#':
    dist[H-1][W-1] += 1
print(dist[H-1][W-1])

Submission status: Wrong Answer

Solution code:
import math
import sys
sys.setrecursionlimit(1000000)

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

dist = [[-1] * W for _ in range(H)]
move = ((1, 0), (0, 1))


def dfs(ci, cj, d):
    dist[ci][cj] = d
    if ci == H-1 and cj == W-1:
        return
    for di, dj in move:
        ni = ci+di
        nj = cj+dj
        if ni <= H-1 and nj <= W-1 and S[ci][cj] == S[ni][nj]:
            dfs(ni, nj, d)


for i in range(H):
    for j in range(W):
        if dist[i][j] == -1:
            if i == 0 and j == 0:
                # d = 0
                if S[0][0] == '.':
                    d = 0
                else:
                    d = 1
            elif i == 0:
                d = dist[i][j-1]+1
            elif j == 0:
                d = dist[i-1][j]+1
            else:
                d = min(dist[i][j-1], dist[i-1][j])+1
            dfs(i, j, d)
print(math.ceil(dist[H-1][W-1]/2))

Submission status: Wrong Answer

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

cnts = [[0 for _ in range(W)] for _ in range(H)]
for h in range(H):
    for w in range(W):
        if S[h][w] == "#":
            cnts[h][w] += 1
        if h == 0 and w == 0:
            continue

        y = h - 1
        x = w - 1
        tmp = float('inf')
        if 0 <= y:
            tmp = min(tmp, cnts[y][w])
        if 0 <= x:
            tmp = min(tmp, cnts[h][x])
        cnts[h][w] += tmp
print(cnts[H - 1][W - 1])

Submission status: Wrong Answer

Solution code:
H,W=list(map(int, input().split()))
graph = []
dp = []
for _ in range(H):
    graph.append(list(input()))
    dp.append([10**4]*W)

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

for h in range(H):
    for w in range(W):
        # 右に行く
        leftx = w - 1
        if 0 <= leftx <= W - 1:
            if graph[h][w] == "#":
                dp[h][w] = min(dp[h][w],dp[h][leftx] + 1)
            else:
                dp[h][w] = min(dp[h][w],dp[h][leftx])

        # 下にいく
        righty = h - 1
        if 0 <= righty <= H - 1:
            if graph[h][w] == "#":
                dp[h][w] = min(dp[h][w],dp[righty][w] + 1)
            else:
                dp[h][w] = min(dp[h][w],dp[righty][w])

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

Submission status: Wrong Answer

Solution code:
# coding: utf-8
H, W = list(map(int, input().split()))
S = []
for _ in range(H):
    S.append(list(input()))

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

for h in range(1,H):
  if S[h-1][0] == '#' and S[h][0] == '.':
    grid[h][0] = grid[h-1][0] + 1
  else:
    grid[h][0] = grid[h-1][0]
    
for w in range(1,W):
  if S[0][w-1] == '#' and S[0][w] == '.':
    grid[0][w] = grid[0][w-1] + 1
  else:
    grid[0][w] = grid[0][w-1]
for w in range(1,W):
  for h in range(1,H):
    if S[h-1][w] == '#' and S[h][w] == '.':
      next_h = grid[h-1][w] + 1
    else:
      next_h = grid[h-1][w]      
    if S[h][w-1] == '#' and S[h][w] == '.':
      next_w = grid[h][w-1] + 1
    else:
      next_w = grid[h][w-1]
    grid[h][w] = min([next_w, next_h])
if S[H-1][W-1] == '#':
  grid[H-1][W-1] += 1
print(grid[H-1][W-1])
for x in grid:
  print(x)

Submission status: Wrong Answer

Solution code:
import collections

h,w=map(int,input().split())
board=[list(input()) for _ in range(h)]
q=collections.deque()
if board[0][0]=='#':
  q.append((0,0,1,1))
else:
  q.append((0,0,0,0))
checked=[[0]*w for _ in range(h)]
checked[0][0]=1
ans=10**18
while len(q)!=0:
  x,y,cnt,flag=q.popleft()
  if x==w-1 and y==h-1:
    ans=min(ans,cnt)
  else:
    if x!=w-1:
      if flag==0:
        if board[y][x+1]=='#':
          if checked[y][x+1]==0:
            q.append((x+1,y,cnt+1,1))
            checked[y][x+1]=1
        else:
          if checked[y][x+1]==0:
            q.append((x+1,y,cnt,0))
            checked[y][x+1]=1
      else:
        if board[y][x+1]=='#':
          if checked[y][x+1]==0:
            q.append((x+1,y,cnt,1))
            checked[y][x+1]=1
        else:
          if checked[y][x+1]==0:
            q.append((x+1,y,cnt,0))
            checked[y][x+1]=1
    if y!=h-1:
      if flag==0:
        if board[y+1][x]=='#':
          if checked[y+1][x]==0:
            q.append((x,y+1,cnt+1,1))
            checked[y+1][x]=1
        else:
          if checked[y+1][x]==0:
            q.append((x,y+1,cnt,0))
            checked[y+1][x]=1
      else:
        if board[y+1][x]=='#':
          if checked[y+1][x]==0:
            q.append((x,y+1,cnt,1))
            checked[y+1][x]=1
        else:
          if checked[y+1][x]==0:
            q.append((x,y+1,cnt,0))
            checked[y+1][x]=1
print(ans)

Submission status: Wrong Answer

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

_w = list(range(H+W-2))

changes = []
for path in itertools.combinations(_w,W-1):
    state = [0, 0]
    pathway = [0] * (H+W-2)
    path = list(path)
    change = 0
    for i in path:
        pathway[i] = 1
    # init Flag
    black_flag = True if S[0][0] == '#' else False
    
    for go in pathway:
        state[go] += 1
        if S[state[0]][state[1]] == '#':
            if black_flag:
                continue
            else:
                black_flag = True
        else:
            if black_flag:
                change += 1
            else:
                continue
    changes.append(change)
print(min(changes))
#print(changes)

Submission status: Wrong Answer

Solution code:
import sys
from heapq import heapify, heappush, heappop

read = sys.stdin.read
readline = sys.stdin.readline

H, W = map(int, readline().split())
s = tuple(map(str, read().split()))
INF = 10 ** 10
grid = [[INF] * W for _ in range(H)]
if s[0][0] == '#':
    grid[0][0] = 1
else:
    grid[0][0] = 0
start = (grid[0][0], (0, 0))
heap = [start]
heapify(heap)
while heap:
    d, (x, y) = heappop(heap)
    if x == H - 1 and y == W - 1:
        print(d)
        exit()
    for i, j in ((0, 1), (1, 0)):
        new_x = x + i
        new_y = y + j
        if new_x == H or new_y == W:
            continue
        if grid[new_x][new_y] != INF:
            continue
        if s[x][y] == '.' and s[new_x][new_y] == '#':
            grid[new_x][new_y] = d + 1
            heappush(heap, (d + 1, (new_x, new_y)))
        else:
            grid[new_x][new_y] = d
            heappush(heap, (d, (new_x, new_y)))

Submission status: Wrong Answer

Solution code:
import sys
from heapq import heapify, heappush, heappop

read = sys.stdin.read
readline = sys.stdin.readline

H, W = map(int, readline().split())
s = tuple(map(str, read().split()))
INF = 10 ** 10
grid = [[INF] * W for _ in range(H)]
if s[0][0] == '#':
    grid[0][0] = 1
else:
    grid[0][0] = 0
start = (grid[0][0], (0, 0))
heap = [start]
heapify(heap)
while heap:
    d, (x, y) = heappop(heap)
    for i, j in ((0, 1), (1, 0)):
        new_x = x + i
        new_y = y + j
        if new_x == H or new_y == W:
            continue
        if grid[new_x][new_y] != INF:
            continue
        if s[x][y] == '.' and s[new_x][new_y] == '#':
            grid[new_x][new_y] = d + 1
            heappush(heap, (d + 1, (new_x, new_y)))
        else:
            grid[new_x][new_y] = d
            heappush(heap, (d, (new_x, new_y)))

print(grid[-1][-1])

Submission status: Wrong Answer

Solution code:
import sys
from heapq import heapify, heappush, heappop

read = sys.stdin.read
readline = sys.stdin.readline

H, W = map(int, readline().split())
s = tuple(map(str, read().split()))
INF = 10 ** 10
grid = [[INF] * W for _ in range(H)]
start = (0, (0, 0))
heap = [start]
heapify(heap)
grid[0][0] = 0
while heap:
    d, (x, y) = heappop(heap)
    for i, j in ((0, 1), (1, 0)):
        new_x = x + i
        new_y = y + j
        if new_x >= H or new_y >= W:
            continue
        if grid[new_x][new_y] != INF:
            continue
        if s[x][y] == '.' and s[new_x][new_y] == '#':
            grid[new_x][new_y] = d + 1
            heappush(heap, (d + 1, (new_x, new_y)))
        else:
            grid[new_x][new_y] = d
            heappush(heap, (d, (new_x, new_y)))

answer = grid[-1][-1]
if s[0][0] == '#':
    answer += 1

print(answer)

Submission status: Wrong Answer

Solution code:
import sys
from heapq import heapify, heappush, heappop

read = sys.stdin.read
readline = sys.stdin.readline

H, W = map(int, readline().split())
s = tuple(map(str, read().split()))
INF = 10 ** 10
grid = [[INF] * W for _ in range(H)]
start = (0, (0, 0))
heap = [start]
heapify(heap)
grid[0][0] = 0
while heap:
    d, (x, y) = heappop(heap)
    for i, j in ((0, 1), (1, 0)):
        new_x = x + i
        new_y = y + j
        if new_x >= H or new_y >= W:
            continue
        if grid[new_x][new_y] != INF:
            continue
        if s[x][y] != s[new_x][new_y]:
            grid[new_x][new_y] = d + 1
            heappush(heap, (d + 1, (new_x, new_y)))
        else:
            grid[new_x][new_y] = d
            heappush(heap, (d, (new_x, new_y)))

if s[0][0] == '#' and s[-1][-1] == '#':
    print((grid[-1][-1] - 2) // 2 + 2)
else:
    print(grid[-1][-1] // 2)

Submission status: Wrong Answer

Solution code:
import sys
from heapq import heapify, heappush, heappop

read = sys.stdin.read
readline = sys.stdin.readline

H, W = map(int, readline().split())
s = tuple(map(str, read().split()))
INF = 10 ** 10
grid = [[INF] * W for _ in range(H)]
start = (0, (0, 0))
heap = [start]
heapify(heap)
grid[0][0] = 0
while heap:
    d, (x, y) = heappop(heap)
    for i, j in ((0, 1), (1, 0)):
        new_x = x + i
        new_y = y + j
        if new_x >= H or new_y >= W:
            continue
        if grid[new_x][new_y] != INF:
            continue
        if s[x][y] != s[new_x][new_y]:
            grid[new_x][new_y] = d + 1
            heappush(heap, (d + 1, (new_x, new_y)))
        else:
            grid[new_x][new_y] = d
            heappush(heap, (d, (new_x, new_y)))

answer = (grid[-1][-1] + 1) // 2
if s[0][0] == '#':
    answer += 1
print(answer)

Submission status: Wrong Answer

Solution code:
import sys
from collections import deque

read = sys.stdin.read
readline = sys.stdin.readline

H, W = map(int, readline().split())
s = tuple(map(str, read().split()))
INF = 10 ** 10
grid = [[INF] * W for _ in range(H)]
start = (0, 0)
queue = deque([start])
grid[0][0] = 0
while queue:
    x, y = queue.pop()
    for i, j in ((0, 1), (1, 0)):
        new_x = x + i
        new_y = y + j
        if new_x >= H or new_y >= W:
            continue
        else:
            if s[x][y] != s[new_x][new_y]:
                cnt = grid[x][y] + 1
                if grid[new_x][new_y] > cnt:
                    grid[new_x][new_y] = cnt
                    queue.append((new_x, new_y))
            else:
                if grid[new_x][new_y] > grid[x][y]:
                    grid[new_x][new_y] = grid[x][y]
                    queue.append((new_x, new_y))

answer = grid[H - 1][W - 1] // 2
if s[0][0] == '#':
    answer += 1
print(answer)

Submission status: Wrong Answer

Solution code:
#!/usr/bin/env python3
# -*- coding:utf-8 -*-

import sys
from collections import deque

def main():
    input = sys.stdin.readline
    H,W = map(int,input().split())
    Gd = [list(input()) for _ in range(H)]
    INF = H*W
    Rt = [[INF]*W for _ in range(H)]
    for i in range(H):
        for j in range(W):
            if i==0 and j==0:
                Rt[i][j] = (Gd[i][j] == '#')
            elif i==0:
                Rt[i][j] = Rt[i][j-1] + (Gd[i][j] == '#')
            elif j==0:
                Rt[i][j] = Rt[i-1][j] + (Gd[i][j] == '#')
            else:
                Rt[i][j] = min(Rt[i-1][j], Rt[i][j-1]) + (Gd[i][j] == '#')
    print(Rt[H-1][W-1])

if __name__=='__main__':
    main()

Submission status: Wrong Answer

Solution code:
# A - Range Flip Find Route
h,w=map(int,input().split())
s=[input() for i in range(h)]
dp=[[0]*(w+1) for i in range(h+1)]

for i in range(h):
    for j in range(w):
        if i-1>=0 and j-1>=0: 
            dp[i][j]=min(dp[i][j-1],dp[i-1][j])
        if i==0 and j-1>=0:
            dp[i][j]+=dp[i][j-1]
        if j==0 and i-1>=0:
            dp[i][j]+=dp[i-1][j]
        if s[i][j]=='#':
            dp[i][j]+=1

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

Submission status: Wrong Answer

Solution code:
h, w = map(int, input().split())
s = []
score = [[0] * w for i in range(h)]
for i in range(h):
  s.append(list(input()))
  for j in range(w):
    score[i][j] = 1 if s[i][j] == '#' else 0
    if i == 0:
      if j != 0:
        score[0][j] += score[0][j-1]
    else:
      if j != 0:
        score[i][j] += min(score[i-1][j], score[i][j-1])
      else:
        score[i][0] += score[i-1][0]
print(score[-1][-1])

Submission status: Wrong Answer

Solution code:
from collections import deque

def solve():
    H, W = map(int, input().split())
    A = [list(input()) for _ in range(H)]
    INF = 10 ** 9
    d = [[INF] * W for i in range(H)]
    d[0][0] = 1 if A[0][0] == '#' else 0

    prepare = 1 if A[0][0] == '#' else 0
    q = deque([(prepare, 0, 0)])
    while q:
        c, x, y = q.popleft()
        for a, b in [(1,0), (0,1)]:
            nx, ny = x+a, y+b
            if nx >= W or ny >= H: continue
            k = 1 if A[ny][nx] == '#' else 0
            if c+k >= d[ny][nx]: continue
            d[ny][nx] = c+k
            q.append((c+k, nx, ny))

    return (d[H-1][W-1]+1)//2

print(solve())

Submission status: Wrong Answer

Solution code:
from collections import deque

def solve():
    H, W = map(int, input().split())
    A = [list(input()) for _ in range(H)]
    INF = 10 ** 9
    d = [[INF] * W for i in range(H)]
    d[0][0] = 1 if A[0][0] == '#' else 0

    prepare = 1 if A[0][0] == '#' else 0
    q = deque([(prepare, 0, 0)])
    while q:
        c, x, y = q.popleft()
        for a, b in [(1,0), (0,1)]:
            nx, ny = x+a, y+b
            if nx >= W or ny >= H: continue
            k = 1 if A[ny][nx] == '#' else 0
            if c+k >= d[ny][nx]: continue
            d[ny][nx] = c+k
            q.append((c+k, nx, ny))

    return d[H-1][W-1]

print(solve())

Submission status: Wrong Answer

Solution code:
from collections import deque

def solve():
    H, W = map(int, input().split())
    A = [list(input()) for _ in range(H)]
    INF = 10 ** 9
    d = [[INF] * W for i in range(H)]
    d[0][0] = 0

    def bfs(x,y,G):
        prepare = 1 if A[y][x] == '#' else 0
        q = deque([(x, y, prepare)])
        MOVE = [(1,0), (0,1)]
        while q:
            z = q.popleft()
            for (a, b) in MOVE:
                w, h, c = z
                w_n, h_n = w+a, h+b

                if w_n >= W or h_n >= H: continue
                if A[h_n][w_n] == '#': c += 1
                if c >= d[h_n][w_n]: continue

                d[h_n][w_n] = min(d[h_n][w_n], c)
                q.append((w_n, h_n, c))

    bfs(0, 0, A)
    return (d[H-1][W-1]+1)//2

print(solve())

Submission status: Wrong Answer

Solution code:
from collections import deque

def solve():
    H, W = map(int, input().split())
    A = [list(input()) for _ in range(H)]
    INF = 10 ** 9
    d = [[INF] * W for i in range(H)]
    d[0][0] = 0

    def bfs(x,y,G):
        prepare = 1 if A[y][x] == '#' else 0
        q = deque([(x, y, prepare)])
        MOVE = [(1,0), (0,1)]
        while q:
            z = q.popleft()
            for (a, b) in MOVE:
                w, h, c = z
                w_n, h_n = w+a, h+b

                if w_n >= W or h_n >= H: continue
                if A[h_n][w_n] == '#': c += 1
                if c >= d[h_n][w_n]: continue

                d[h_n][w_n] = min(d[h_n][w_n], c)
                q.append((w_n, h_n, c))

    bfs(0, 0, A)
    return d[H-1][W-1]

print(solve())