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())
S = []
for _ in range(h):
    s = str(input())
    S.append(s)

DP = [[0 for _ in range(w)] for _ in range(h)]

if S[0][0] == '.':
    DP[0][0] = 0
else:
    DP[0][0] = 1

ren = False
for i in range(1,h):
    if S[i][0] == '.':
        DP[i][0] = DP[i-1][0]
        ren = False
    elif ren == False and S[i][0] == '#':
        DP[i][0] = DP[i-1][0] + 1
        ren = True
    elif ren == True and S[i][0] == '#':
        DP[i][0] = DP[i-1][0]
        ren = True

ren = False
for j in range(1,w):
    if S[0][j] == '.':
        DP[0][j] = DP[0][j-1]
        ren = False
    elif ren == False and S[0][j] == '#':
        DP[0][j] = DP[0][j-1] + 1
        ren = True
    elif ren == True and S[0][j] == '#':
        DP[0][j] = DP[0][j-1]
        ren = True

for i in range(1,h):
    for j in range(1,w):
        if S[i][j] == '.':
            DP[i][j] = min(DP[i-1][j], DP[i][j-1])
        elif S[i][j] == '#':
            res_i = 0
            res_j = 0
            if S[i-1][j] == '.':
                res_i = 1
            if S[i][j-1] == '.':
                res_j = 1
            DP[i][j] = min(DP[i-1][j] + res_i, DP[i][j-1] + res_j)

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

Submission status: Wrong Answer

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

inf = float('inf')

from collections import deque
dx = [0, 1]
dy = [1, 0]

q = deque()
d = [[inf for _ in range(W)] for _ in range(H)]
if S[0][0] == '#':
    d[0][0] = 1
    q.append([0, 0, 1])
else:
    d[0][0] = 0
    q.append([0, 0, 0])
while q:
    p = q.popleft()
    # if p == [H - 1, W - 1]:
    #     break
    for i in range(2):
        nx = p[1] + dx[i]
        ny = p[0] + dy[i]
        if nx >= 0 and nx < W and ny >= 0 and ny < H:
            if S[ny][nx] == '#':
                c = 1
            else:
                c = 0
            if p[2] + c < d[ny][nx]:
                d[ny][nx] = p[2] + c
                q.append([ny, nx, p[2] + c])
print(d[H - 1][W - 1])

Submission status: Wrong Answer

Solution code:
from collections import deque
h,w=map(int,input().split())
field=[["*" for i in range(w+2)]]+[["*"]+list(input())+["*"] for i in range(h)]+[["*" for i in range(w+2)]]
cost=[[500 for i in range(w+2)] for j in range(h+2)]
cost[1][1]=0
ans=0
for i in range(1,h+1):
    for j in range(1,w+1):
        color=field[i][j]
        if color=="." and field[i][j+1]=="#":
            cost[i][j+1]=min(cost[i][j]+1,cost[i][j+1])
        else:cost[i][j+1]=min(cost[i][j],cost[i][j+1])
        if color=="." and field[i+1][j]=="#":
            cost[i+1][j]=min(cost[i][j]+1,cost[i+1][j])
        else:cost[i+1][j]=min(cost[i][j],cost[i+1][j])
print(cost[h][w] if field[0][0]=="." else cost[h][w]+1)

Submission status: Wrong Answer

Solution code:
from collections import deque
h,w=map(int,input().split())
field=[["*" for i in range(w+2)]]+[["*"]+list(input())+["*"] for i in range(h)]+[["*" for i in range(w+2)]]
cost=[[500 for i in range(w+2)] for j in range(h+2)]
cost[1][1]=0
ans=0
for i in range(1,h+1):
    for j in range(1,w+1):
        color=field[i][j]
        if color=="." and field[i][j+1]=="#":
            cost[i][j+1]=min(cost[i][j]+1,cost[i][j+1])
        else:cost[i][j+1]=min(cost[i][j],cost[i][j+1])
        if color=="." and field[i+1][j]=="#":
            cost[i+1][j]=min(cost[i][j]+1,cost[i+1][j])
        else:cost[i+1][j]=min(cost[i][j],cost[i+1][j])
print(cost[h][w] if field[h][w]=="." else cost[h][w]+1)

Submission status: Wrong Answer

Solution code:
from collections import deque
h,w=map(int,input().split())
ans=0
field=[["*" for i in range(w+2)]]+[["*"]+list(input())+["*"] for i in range(h)]+[["*" for i in range(w+2)]]
queue=deque([(1,1)])
move=[(0,1),(1,0)]
cost=[[-1 for i in range(w+2)] for j in range(h+2)]
cost[1][1]=0
ans=0
while queue:
    flg=0
    pos=queue.popleft()
    color=field[pos[0]][pos[1]]
    for i in move:
      if field[pos[0]+i[0]][pos[1]+i[1]]=="*":continue
      if cost[pos[0]+i[0]][pos[1]+i[1]]!=-1:continue
      if field[pos[0]+i[0]][pos[1]+i[1]]=="#" and field[pos[0]][pos[1]]==".":
          queue.append((pos[0]+i[0],pos[1]+i[1]))
          cost[pos[0]+i[0]][pos[1]+i[1]]=cost[pos[0]][pos[1]]+1
      else:
          queue.appendleft((pos[0]+i[0],pos[1]+i[1]))
          cost[pos[0]+i[0]][pos[1]+i[1]]=cost[pos[0]][pos[1]]
print(cost[h][w] if field[1][1]=="." else cost[h][w]+1)

Submission status: Wrong Answer

Solution code:
from collections import deque
h,w=map(int,input().split())
ans=0
field=[["*" for i in range(w+2)]]+[["*"]+list(input())+["*"] for i in range(h)]+[["*" for i in range(w+2)]]
queue=deque([(1,1)])
move=[(0,1),(1,0)]
cost=[[-1 for i in range(w+2)] for j in range(h+2)]
cost[1][1]=0
ans=0
while queue:
    flg=0
    pos=queue.popleft()
    color=field[pos[0]][pos[1]]
    for i in move:
      if field[pos[0]+i[0]][pos[1]+i[1]]=="*":continue
      if cost[pos[0]+i[0]][pos[1]+i[1]]!=-1:continue
      if field[pos[0]+i[0]][pos[1]+i[1]]=="#" and field[pos[0]][pos[1]]==".":
          queue.append((pos[0]+i[0],pos[1]+i[1]))
          cost[pos[0]+i[0]][pos[1]+i[1]]=cost[pos[0]][pos[1]]+1
      else:
          queue.appendleft((pos[0]+i[0],pos[1]+i[1]))
          cost[pos[0]+i[0]][pos[1]+i[1]]=cost[pos[0]][pos[1]]
print(cost[h][w])

Submission status: Wrong Answer

Solution code:
import numpy as np
h,w = [int(i) for i in input().split()]
s = np.zeros((h,w),dtype=int)
for i in range(h):
    for j,v in enumerate(input()):
        s[i][j] = 1 if v == '#' else 2

s_r = np.zeros((h,w),dtype=int)

m = h * w + 1
for i in range(h-1,-1,-1):
    for j in range(w-1,-1,-1):
        r = m
        if 0 <= j + 1 < w:
            r = s_r[i][j + 1]
        if 0 <= i + 1 < h:
            r = min(r, s_r[i + 1][j])
        if r == m:
            r = 0
        if s[i][j] == 1:
            r += 1
        s_r[i][j] = r
print(s_r[0][0])

Submission status: Wrong Answer

Solution code:
import bisect,collections,copy,itertools,math,string
def I(): return int(input())
def S(): return input()
def LI(): return list(map(int,input().split()))
def LS(): return list(input().split())
##################################################
H,W = LI()
S = [S() for _ in range(H)]
dp = [[-1]*W for _ in range(H)]
for i in range(H):
    for j in range(W):
        judge = 1 if S[i][j]=='#' else 0
        if i==0: #0行目
            if j==0:
                dp[0][0] = judge
            else:
                dp[0][j] = dp[0][j-1]+judge
        else: #0行目意外
            if j==0:
                dp[i][0] = dp[i-1][0]+judge
            else:
                dp[i][j] = min(dp[i][j-1],dp[i-1][j])+judge
print(dp[-1][-1])

Submission status: Wrong Answer

Solution code:
import sys
sys.setrecursionlimit(700000)

def s_in():
    return input()

def n_in():
    return int(input())

def l_in():
    return list(map(int, input().split()))

h, w = l_in()
S = [s_in() for _ in range(h)]
dp = [[0 for _ in range(w)] for _ in range(h)]


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] + int(S[i][j] != S[i][j-1])
            continue
        if j == 0:
            dp[i][j] = dp[i-1][j] + int(not S[i][j] == S[i-1][j])
            continue

        dp[i][j] = min(dp[i][j-1] + int(not S[i][j] == S[i][j-1]),
                       dp[i-1][j] + int(not S[i][j] == S[i-1][j]))


res = dp[h-1][w-1]
if res%2 == 0:
    print(res//2)
else:
    print(res//2+int(S[0][0] == '#'))

Submission status: Wrong Answer

Solution code:
import sys
sys.setrecursionlimit(700000)

def s_in():
    return input()

def n_in():
    return int(input())

def l_in():
    return list(map(int, input().split()))

h, w = l_in()
S = [s_in() for _ in range(h)]
dp = [[0 for _ in range(w)] for _ in range(h)]


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] + int(S[i][j] != S[i][j-1])
            continue
        if j == 0:
            dp[i][j] = dp[i-1][j] + int(not S[i][j] == S[i-1][j])
            continue

        dp[i][j] = min(dp[i][j-1] + int(not S[i][j] == S[i][j-1]),
                       dp[i-1][j] + int(not S[i][j] == S[i-1][j]))


res = dp[h-1][w-1]
if res%2 == 0:
    print(res//2)
else:
    print(res+int(S[0][0] == '#'))

Submission status: Wrong Answer

Solution code:
import sys
sys.setrecursionlimit(700000)

def s_in():
    return input()

def n_in():
    return int(input())

def l_in():
    return list(map(int, input().split()))

h, w = l_in()
S = [s_in() for _ in range(h)]
dp = [[0 for _ in range(w)] for _ in range(h)]


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] + int(S[i][j] != S[i][j-1])
            continue
        if j == 0:
            dp[i][j] = dp[i-1][j] + int(not S[i][j] == S[i-1][j])
            continue

        dp[i][j] = min(dp[i][j-1] + int(not S[i][j] == S[i][j-1]),
                       dp[i-1][j] + int(not S[i][j] == S[i-1][j]))

print(dp[h-1][w-1]//2+int(S[0][0] == '#'))

Submission status: Wrong Answer

Solution code:
# coding: utf-8
import queue
H, W = map(int,input().split())
field = [list(input()) for _ in range(H)]
dist = [[0 for _ in range(W)] for _ in range(H)]
check = [[False for _ in range(W)] for _ in range(H)]
q = queue.Queue()
q.put([0,0])

while not q.empty():
    p = q.get()
    h, w = p[0], p[1]
    if h >= H or w >= W:
        continue
    elif field[h][w] == ".":
        #値の更新
        dist[h][w] = min(dist[h-1][w], dist[h][w-1])
        check[h][w] = True
        #周辺のput
        q.put([h,w+1])
        q.put([h+1,w])
    elif field[h][w] == '#' and check[h][w] == False:
        #長方形の判定 
        dh = 0
        while field[h+dh][w] == '#':
            dh += 1
            if h+dh == H:
                break
        cnt = [0] * dh
        for j in range(dh):
            dw = 0
            while field[h+j][w+dw] == '#':
                dw += 1
                if w+dw == W:
                    break
            cnt[j] = dw
        dw = min(cnt)
        #値の更新
        c = min(dist[h-1][w], dist[h][w-1]) + 1
        for j in range(dh):
            for i in range(dw):
                if check[h+j][w+i] == False:
                    dist[h+j][w+i] = c
                    check[h+j][w+i] = True
        #周辺のput
        for j in range(dh):
            q.put([h+j, w+dw])
        for i in range(dw):
            q.put([h+dh, w+i])
    
print(dist[-1][-1])

Submission status: Wrong Answer

Solution code:
from itertools import *
from heapq import *

def solve(H, W, grid):
  goal = (H-1, W-1)
  fixed = set()
  candicates = [(grid[0,0], (0, 0))]
  while 1:
    dist, p = heappop(candicates)
    if p == goal:
      return dist
    if p in fixed:
      continue
    fixed.add(p)
    for i,j in product([1,-1], [0,1]):
      p1 = p[0]+i*j, p[1]+i*(1-j)
      if not (0<=p1[0]<H and 0<=p1[1]<W) or p1 in fixed:
        continue
      x, y = p
      x1, y1 = p1
      heappush(candicates, (dist+(grid[p1] & ~grid[p]), p1))
  return None

H, W = map(int, input().split())
grid = {(i,j): [".", "#"].index(c) for i in range(H) for j, c in enumerate(input())}

print(solve(H, W, grid))

Submission status: Wrong Answer

Solution code:
import numpy as np
h,w = [int(i) for i in input().split()]
s = np.zeros((h,w),dtype=int)
for i in range(h):
    for j,v in enumerate(input()):
        s[i][j] = 1 if v == '#' else 2
print(s)

s_r = np.zeros((h,w),dtype=int)

def func(i,j):
    global s,h,w
    if i == h - 1 and j == w - 1:
        return 0 if s[i][j] == 2 else 1
    else:
        r = h * w + 1
        if 0 <= j + 1 < w:
            r = s_r[i][j + 1]
        if 0 <= i + 1 < h:
            if r > s_r[i + 1][j]:
                r = s_r[i + 1][j]
        r += 0 if s[i][j] == 2 else 1
        return r
def move(i,j):
    global s,h,w
    s_r[i][j] = func(i,j)

    if 0 <= j - 1 < w:
        s_r[i][j - 1] = func(i,j - 1)
        move(i,j - 1)
    if 0 <= i - 1 < w:
        s_r[i - 1][j] = func(i - 1,j)
        move(i - 1,j)
move(h - 1,w - 1)
print(s_r[0][0])

Submission status: Wrong Answer

Solution code:
from itertools import *
from heapq import *

def solve(H, W, grid):
  goal = (H-1, W-1)
  fixed = set()
  candicates = [(grid[0], (0, 0))]
  while 1:
    dist, p = heappop(candicates)
    if p == goal:
      return dist
    if p in fixed:
      continue
    fixed.add(p)
    for i,j in product([1,-1], [0,1]):
      y, x = p[0]+i*j, p[1]+i*(1-j)
      if not (0<=y<H and 0<=x<W) or (y, x) in fixed:
        continue
      heappush(candicates, (dist+(1-grid[W*p[0]+p[1]])*grid[W*y+x], (y, x)))
  return None

H, W = map(int, input().split())
grid = list(chain.from_iterable(map([".", "#"].index, input()) for i in range(H)))
print(solve(H, W, grid))

Submission status: Wrong Answer

Solution code:
from itertools import product, chain
from heapq import heappop, heappush

def solve(H, W, grid):
  goal = (H-1, W-1)
  fixed = set()
  candicates = [(grid[0], (0, 0))]
  while 1:
    dist, p = heappop(candicates)
    if p == goal:
      return dist
    if p in fixed:
      continue
    fixed.add(p)
    for i,j in product([1,-1], [0,1]):
      y, x = p[0]+i*j, p[1]+i*(1-j)
      if not (0<=y<H and 0<=x<W) or (y,x) in fixed:
        continue
      heappush(candicates, (dist+grid[W*y+x], (y, x)))
  return None

H, W = map(int, input().split())
grid = list(chain.from_iterable(map([".", "#"].index, input()) for i in range(H)))
print(solve(H, W, grid))

Submission status: Wrong Answer

Solution code:
# coding: utf-8
# Your code here!

import sys
sys.setrecursionlimit(10**6)
readline = sys.stdin.readline
read = sys.stdin.read

h,w = [int(i) for i in readline().split()]
b = [readline() for _ in range(h)]

INF = 10**9

dp0 = [[INF]*w for _ in range(h)]
#dp1 = [[INF]*w for _ in range(h)]

if b[-1][-1] == "#":
    dp0[-1][-1] = 1
#    dp0[-1][-1] = INF
else:
    dp0[-1][-1] = 0
#    dp1[-1][-1] = 0

for i in range(h-1,-1,-1):
    for j in range(w-1,-1,-1):
        if b[i][j] == "#":
            r = INF
            if i != h-1: r = min(r,dp0[i+1][j] + (1 if b[i+1][j]=="." else 0))
            if j != w-1: r = min(r,dp0[i][j+1] + (1 if b[i][j+1]=="." else 0))
            #dp1[i][j] = min(dp1[i][j],r)
            dp0[i][j] = min(dp0[i][j],r)
            
        else:
            r = INF
            if i != h-1: r = min(r,dp0[i+1][j])
            if j != w-1: r = min(r,dp0[i][j+1])
            dp0[i][j] = min(dp0[i][j],r)
            #dp1[i][j] = min(dp0[i][j],r)


#print(dp0)
#print(dp1)

print(dp0[0][0])
#print(dp0)

Submission status: Wrong Answer

Solution code:
h, w = map(int, input().split())
s = [] # h, w
for i in range(h):
    s += [','.join(input()).split(',')]

cost = [[0 for i in range(w)] for j in range(h)]

# h: j,  w: i - j
for hh in range(h):
    for ww in range(w):
        if hh == ww == 0:
            cost[0][0] = 0
        elif ww == 0:
            cost[hh][ww] = cost[hh - 1][ww] + 0 if s[hh][ww] == '.' else 1
        elif hh == 0:
            cost[hh][ww] = cost[hh][ww - 1] + 0 if s[hh][ww] == '.' else 1
        else:
            cost[hh][ww] = min(cost[hh][ww - 1], cost[hh - 1][ww])

        cost[hh][ww] += 0 if s[hh][ww] == '.' else 1

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

Submission status: Wrong Answer

Solution code:
h, w = map(int, input().split())
s = [] # h, w
for i in range(h):
    s += [','.join(input()).split(',')]

cost = [[0 for i in range(w)] for j in range(h)]

# h: j,  w: i - j
for hh in range(h):
    for ww in range(w):
        if hh == ww == 0:
            cost[0][0] = 0
        elif ww == 0:
            cost[hh][ww] = cost[hh - 1][ww] + 0 if s[hh][ww] == '.' else 1
        elif hh == 0:
            cost[hh][ww] = cost[hh][ww - 1] + 0 if s[hh][ww] == '.' else 1
        else:
            cost[hh][ww] = cost[hh][ww - 1] if cost[hh][ww - 1] < cost[hh - 1][ww] else cost[hh - 1][ww]
            
        cost[hh][ww] += 0 if s[hh][ww] == '.' else 1

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

Submission status: Wrong Answer

Solution code:
h, w = map(int, input().split())
s = [] # h, w
for i in range(h):
    s += [','.join(input()).split(',')]

cost = [[0 for i in range(w)] for j in range(h)]

# h: j,  w: i - j
for hh in range(h):
    for ww in range(w):
        if hh == ww == 0:
            cost[0][0] = 0 if s[0][0] == '.' else 1
        elif ww == 0:
            cost[hh][ww] = cost[hh - 1][ww] + 0 if s[hh][ww] == '.' else 1
        elif hh == 0:
            cost[hh][ww] = cost[hh][ww - 1] + 0 if s[hh][ww] == '.' else 1
        else:
            cost[hh][ww] = cost[hh][ww - 1] if cost[hh][ww - 1] < cost[hh - 1][ww] else cost[hh - 1][ww]
            cost[hh][ww] += 0 if s[hh][ww] == '.' else 1

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

Submission status: Wrong Answer

Solution code:
# coding: utf-8
# Your code here!

import sys
sys.setrecursionlimit(10**6)
readline = sys.stdin.readline
read = sys.stdin.read

h,w = [int(i) for i in readline().split()]
b = [readline() for _ in range(h)]

INF = 10**9

dp0 = [[INF]*w for _ in range(h)]
dp1 = [[INF]*w for _ in range(h)]

if b[-1][-1] == "#":
    dp1[-1][-1] = 0
    dp0[-1][-1] = 1
else:
    dp0[-1][-1] = dp1[-1][-1] = 0

for i in range(h-1,-1,-1):
    for j in range(w-1,-1,-1):
        if b[i][j] == "#":
            r = INF
            if i != h-1: r = min(r,1 + dp1[i+1][j])
            if j != w-1: r = min(r,1 + dp1[i][j+1])
            dp0[i][j] = min(dp0[i][j],r)

            r = INF
            if i != h-1: r = min(r,dp0[i+1][j])
            if j != w-1: r = min(r,dp0[i][j+1])
            dp1[i][j] =  min(dp1[i][j],r)
            
        else:
            r = INF
            if i != h-1: r = min(r,dp0[i+1][j])
            if j != w-1: r = min(r,dp0[i][j+1])
            dp0[i][j] =  min(dp0[i][j],r)
            
            r = INF
            if i != h-1: r = min(r,dp1[i+1][j] + 1)
            if j != w-1: r = min(r,dp1[i][j+1] + 1)
            dp1[i][j] = min(dp1[i][j],r)


#print(dp0)
#print(dp1)

if b[0][0] == "#":
    print(min(dp1[0][0],dp0[0][0]+1))
else:
    print(min(dp0[0][0],dp1[0][0]+1))

Submission status: Wrong Answer

Solution code:
h, w = map(int, input().split())
s = []  # h, w
for i in range(h):
    s += [','.join(input()).split(',')]

cost = [[1 if s[0][0] == '#' else 0 for i in range(w)] for j in range(h)]

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

            if s[j][i - j] == '#':
                cost[j][i - j] += 1

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

Submission status: Wrong Answer

Solution code:
h, w = map(int, input().split())
s = [] # h, w
for i in range(h):
    s += [','.join(input()).split(',')]

cost = [[0 for i in range(w)] for j in range(h)]
tmp = w if w > h else h

# h: j,  w: i - j
for i in range(h + w - 1):
    for j in range(tmp):
        if j < h and i - j < w and j >= 0 and i - j >= 0:
            if j == 0:
                cost[j][i - j] = cost[j][i - j - 1]
            elif i - j == 0:
                cost[j][i - j] = cost[j - 1][i - j]
            else:
                cost[j][i - j] = cost[j - 1][i - j] if cost[j - 1][i - j] < cost[j][i - j - 1] else cost[j][i - j - 1]

            if s[j][i - j] == '#':
                cost[j][i - j] += 1

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

Submission status: Wrong Answer

Solution code:
h, w = map(int, input().split())
s = []  # h, w
for i in range(h):
    s += [','.join(input()).split(',')]

cost = [[1 if s[0][0] == '#' else 0 for i in range(w)] for j in range(h)]

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

            if s[j][i - j] == '#':
                cost[j][i - j] += 1

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

Submission status: Wrong Answer

Solution code:
h, w = map(int, input().split())
s = [] # h, w
for i in range(h):
    s += [','.join(input()).split(',')]

cost = [[1 if s[0][0] == '#' else 0 for i in range(w)] for j in range(h)]

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

            if s[j][i - j] == '#':
                cost[j][i - j] += 1

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

Submission status: Wrong Answer

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

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

for i in range(H):
    for j in range(W):
        if i == j == 0:
            dp[i][j] = int(grid[i][j] == "#")
        elif i == 0:
            dp[i][j] = dp[i][j - 1] + int(grid[i][j] == "#")
        elif j == 0:
            dp[i][j] = dp[i - 1][j] + int(grid[i][j] == "#")
        else:
            dp[i][j] = min(dp[i][j-1], dp[i - 1][j]) + (grid[i][j] == "#")

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

Submission status: Wrong Answer

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

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

for i in range(H):
    for j in range(W):
        if i == j == 0:
            dp[i][j] = (grid[i][j] == "#")
        elif i == 0:
            dp[i][j] = dp[i][j - 1] + (grid[i][j] == "#")
        elif j == 0:
            dp[i][j] = dp[i - 1][j] + (grid[i][j] == "#")
        else:
            dp[i][j] = min(dp[i][j-1], dp[i - 1][j]) + (grid[i][j] == "#")

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

Submission status: Wrong Answer

Solution code:
H,W = list(map(int, input().split()))
B = []
for _ in range(H):
  B.append(input())
  
A = [[999999 for _ in range(W)] for _ in range(H)]
A[0][0] = 0 if B[0][0] == "." else 1

for i in range(H):
  for j in range(W):
    if i+j == 0:
      continue
    X,Y = 999999, 999999
    if i > 0:
      X = A[i-1][j] 
      X += 1 if B[i-1][j] != B[i][j] else 0
    if j > 0:
      Y = A[i][j-1]
      Y += 1 if B[i][j-1] != B[i][j] else 0
    A[i][j] = min(X,Y)
    
print(A[H-1][W-1])

Submission status: Wrong Answer

Solution code:
H,W = list(map(int, input().split()))
B = []
for _ in range(H):
  B.append(input())
  
A = [[999999 for _ in range(W)] for _ in range(H)]
A[0][0] = 0 if B[0][0] == "." else 1

for i in range(H):
  for j in range(W):
    if i+j == 0:
      continue
    now = 0 if B[i][j] == "." else 1
    X = A[i-1][j] if i > 0 else 999999
    Y = A[i][j-1] if j > 0 else 999999
    A[i][j] = min(X,Y) + now
    
print(A[H-1][W-1])

Submission status: Wrong Answer

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

dp = [[float("inf")] * (w + 10) for _ in range(h + 10)]
if s[0][0] == "#":
    dp[0][0] = 1
else:
    dp[0][0] = 0

for r in range(h):
    for c in range(w):
        if c + 1 < w:
            if s[r][c+1] == "#":
                dp[r][c+1] = min(dp[r][c+1], dp[r][c]) + 1
            else:
                dp[r][c+1] = min(dp[r][c+1], dp[r][c])
        if r + 1 < h:
            if s[r+1][c] == "#":
                dp[r+1][c] = min(dp[r+1][c], dp[r][c]) + 1
            else:
                dp[r+1][c] = min(dp[r+1][c], dp[r][c])

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

Submission status: Wrong Answer

Solution code:
from itertools import product
from heapq import heappush, heappop

class Dijkstra:
    def __init__(self, N):
        self.N = N # #vertices
        self.E = [[] for _ in range(N)]

    def add_edge(self, init, end, weight, undirected=False):
        self.E[init].append((end, weight))
        if undirected: self.E[end].append((init, weight))
    
    def distance(self, s):
        INF = float('inf')
        self.dist = [INF] * self.N # the distance of each vertex from s
        self.prev = [-1] * self.N # the previous vertex of each vertex on a shortest path from s
        rem = self.N # #(remaining vertices)
        heap = []
        heappush(heap, (0, -1, s))
        while heap and rem:
            d, p, v = heappop(heap)
            if d == self.dist[v]: continue # (s,v)-shortest path is already calculated
            self.dist[v] = d; self.prev[v] = p
            rem -= 1
            for u, c in self.E[v]:
                temp = d + c
                if self.dist[u] > temp: heappush(heap, (temp, v, u))
        return self.dist

H, W = map(int, input().split())
dijkstra = Dijkstra(H * W)

def vtx(i, j): return i*W + j
def coord(n): return divmod(n, W)

grid = [input() for _ in range(H)] # |string| = W
E = [[] for _ in range(H * W)]
ans = 0 if grid[0][0] == '.' else 1
for i, j in product(range(H), range(W)):
    v = vtx(i, j)
    check = [vtx(i+dx, j+dy) for dx, dy in [(1, 0), (0, 1)] if i+dx <= H-1 and j+dy <= W-1]
    for u in check:
        x, y = coord(u)
        if grid[i][j] == '.' and grid[x][y] == '#':
            dijkstra.add_edge(v, u, 1)
        else:
            dijkstra.add_edge(v, u, 0)
dist = dijkstra.distance(0)
ans += dist[vtx(H-1, W-1)]
print(ans)

Submission status: Wrong Answer

Solution code:
r,c=map(int,input().split())


def minCost(cost, m, n): 

	tc = [[0 for x in range(c)] for x in range(r)]

	tc[0][0] = cost[0][0] 

	for i in range(1, m+1): 
		tc[i][0] = tc[i-1][0] + cost[i][0] 

	for j in range(1, n+1): 
		tc[0][j] = tc[0][j-1] + cost[0][j] 

	for i in range(1, m+1): 
		for j in range(1, n+1): 
			tc[i][j] = min( tc[i-1][j], tc[i][j-1]) + cost[i][j] 

	return tc[m][n] 

 
a=[]
x=0
for i in range(r):
    s=input().replace('.','0').replace('#','1')
    ss=[int(i) for i in s]
    a.append(ss)
print(minCost(a,r-1,c-1))

Submission status: Wrong Answer

Solution code:
from itertools import product
from collections import deque

def zero_one_bfs(E, s, init=0):
    N = len(E)
    order = [-1] * N # a bfs ordering of each vertex
    dist = [-1] * N # the distance of each vertex from s
    dq = deque([(s, init)]) # (vertex, dist)
    num = 0 # current ordering
    while dq:
        v, d = dq.popleft()
        if order[v] < 0: # visited v for the first time
            order[v] = num; dist[v] = d
            num += 1
            for u, w in E[v]:
                if order[u] >= 0: continue
                if w == 0: dq.appendleft((u, d))
                else: dq.append((u, d+1))
    return order, dist

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

def vtx(i, j): return i*W + j
def coord(n): return divmod(n, W)

grid = [input() for _ in range(H)] # |string| = W
E = [[] for _ in range(H * W)]
for i, j in product(range(H), range(W)):
    v = vtx(i, j)
    check = [vtx(i+dx, j+dy) for dx, dy in [(1, 0), (0, 1)] if i+dx <= H-1 and j+dy <= W-1]
    for u in check:
        x, y = coord(u)
        if grid[i][j] == '.' and grid[x][y] == '#':
            E[v].append((u, 1))
            E[u].append((v, 0))
        elif grid[i][j] == '#' and grid[x][y] == '.':
            E[v].append((u, 0))
            E[u].append((v, 1))
        else:
            E[v].append((u, 0))
            E[u].append((v, 0))
_, dist = zero_one_bfs(E, 0, 0 if grid[0][0] == '.' else 1)
print(dist[vtx(H-1, W-1)])

Submission status: Wrong Answer

Solution code:
from itertools import product
from collections import deque

def zero_one_bfs(E, s):
    N = len(E)
    order = [-1] * N # a bfs ordering of each vertex
    dist = [-1] * N # the distance of each vertex from s
    dq = deque([(s, 0)]) # (vertex, dist)
    num = 0 # current ordering
    while dq:
        v, d = dq.popleft()
        if order[v] < 0: # visited v for the first time
            order[v] = num; dist[v] = d
            num += 1
            for u, w in E[v]:
                if order[u] >= 0: continue
                if w == 0: dq.appendleft((u, d))
                else: dq.append((u, d+1))
    return order, dist

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

def vtx(i, j): return i*W + j
def coord(n): return divmod(n, W)

grid = [input() for _ in range(H)] # |string| = W
E = [[] for _ in range(H * W)]
ans = 0 if grid[0][0] == '.' else 1
for i, j in product(range(H), range(W)):
    v = vtx(i, j)
    check = [vtx(i+dx, j+dy) for dx, dy in [(1, 0), (0, 1)] if i+dx <= H-1 and j+dy <= W-1]
    for u in check:
        x, y = coord(u)
        if grid[i][j] == '.' and grid[x][y] == '#':
            E[v].append((u, 1))
            E[u].append((v, 0))
        elif grid[i][j] == '#' and grid[x][y] == '.':
            E[v].append((u, 0))
            E[u].append((v, 1))
        else:
            E[v].append((u, 0))
            E[u].append((v, 0))
_, dist = zero_one_bfs(E, 0)
ans += dist[vtx(H-1, W-1)]
print(ans)

Submission status: Wrong Answer

Solution code:
h, w = map(int, input().split())
s = [[str(i) for i in input().split()] for i in range(h)]
for i in range(h):
    s[i] = list(s[i][0])
import copy
l = [0] * w
hw = [0] * h
for i in range(h):
    hw[i] = copy.copy(l)
if s[0][0] == "#":
    hw[0][0] = 1
for i in range(w - 1):
    if s[0][i + 1] == "#":
        hw[0][i + 1] = hw[0][i] + 1
    else:
        hw[0][i + 1] = hw[0][i]
for i in range(h - 1):
    if s[i + 1][0] == "#":
        hw[i + 1][0] = hw[i][0] + 1
    else:
        hw[i + 1][0] = hw[i][0]
for i in range(w - 1):
    for j in range(h - 1):
        if s[j + 1][i + 1] == "#":
            hw[j + 1][i + 1] = min(hw[j][i + 1], hw[j + 1][i]) + 1
        else:
            hw[j + 1][i + 1] = min(hw[j][i + 1], hw[j + 1][i])
ans = hw[h - 1][w - 1]
print(ans)