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, *S = open(0).read().split()
H, W = [int(_) for _ in [H, W]]
dist = [[float('inf')] * W for _ in range(H)]
dist[0][0] = 0
stack = [0]
while True:
    if not stack:
        break
    i = stack.pop()
    x, y = divmod(i, W)
    d = dist[x][y]
    for dx, dy in ((1, 0), (0, 1), (-1, 0), (0, -1)):
        nx, ny = x + dx, y + dy
        if 0 <= nx < H and 0 <= ny < W:
            if S[nx][ny] == '#' and S[x][y] == '.':
                if dist[nx][ny] > d + 1:
                    dist[nx][ny] = d + 1
                    stack += [nx * W + ny]
            elif dist[nx][ny] > d:
                dist[nx][ny] = d
                stack += [nx * W + ny]
ans = dist[-1][-1]
if S[0][0] == '#':
    ans += 1
print(ans)

Submission status: Wrong Answer

Solution code:
#!/usr/bin/env python3

import sys
sys.setrecursionlimit(10**7)

INF = 10**7
DIRECTION = [[0,1],[1,0]]

def solve(h,w,board):
    dp = [[0]*w for _ in range(h)]
    def isSharp(y,x):
        return board[y][x] == '#'
    for y in range(h):
        if y == 0:
            dp[0][0] = isSharp(0,0)
        else:
            dp[y][0] = dp[y-1][0] + isSharp(y,0)
        for x in range(w-1):
            if y == 0:
                dp[y][x+1] = dp[y][x] + isSharp(y,x+1)
            else:
                dp[y][x+1] = min(dp[y][x], dp[y-1][x+1]) + isSharp(y,x+1)

    
    return dp[-1][-1]

def main():
    H,W = map(int,input().split())
    board = [input() for _ in range(H)]
    print('{}\n'.format(solve(H,W,board)))
    # write c


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
H, W = map(int, input().split())
s = []
for i in range(H):
  s.append(str(input()))
ans = [[100000]*W for i in range(H)]
  
l = [[0, 0]]
tmp = []
if s[0][0] == '.':
  ans[0][0] = 0
else:
  ans[0][0] = 1
  
for p in range(100000):
  for i in l:
    if (i[0]<H-1) and ([i[0]+1, i[1]] not in tmp):
      tmp.append([i[0]+1, i[1]])
    if (i[1]<W-1) and ([i[0], i[1]+1] not in tmp):
      tmp.append([i[0], i[1]+1])
  for n in tmp:
    if n[0] == 0:
      if s[n[0]][n[1]] == '#':
        ans[n[0]][n[1]] = ans[n[0]][n[1]-1] + 1
      else:
        ans[n[0]][n[1]] = ans[n[0]][n[1]-1]
    elif n[1] == 0:
      if s[n[0]][n[1]] == '#':
        ans[n[0]][n[1]] = ans[n[0]-1][n[1]] + 1
      else:
        ans[n[0]][n[1]] = ans[n[0]-1][n[1]]
    elif s[n[0]][n[1]] == '#':
      ans[n[0]][n[1]] = min(ans[n[0]-1][n[1]]+1, ans[n[0]][n[1]-1]+1)
    else:
      ans[n[0]][n[1]] = min(ans[n[0]-1][n[1]], ans[n[0]][n[1]-1])
  if ans[H-1][W-1] < 100000:
    break
  else:
    l = tmp
    tmp = []
print(ans[H-1][W-1])

Submission status: Wrong Answer

Solution code:
H, W = map(int, input().split())
s = []
for i in range(H):
  s.append(str(input()))
ans = [[100000]*W for i in range(H)]
  
l = [[0, 0]]
tmp = []
if s[0][0] == '.':
  ans[0][0] = 0
else:
  ans[0][0] = 1
  
for p in range(100000):
  for i in l:
    if (i[0]<H-1) and ([i[0]+1, i[1]] not in tmp):
      tmp.append([i[0]+1, i[1]])
    if (i[1]<W-1) and ([i[0], i[1]+1] not in tmp):
      tmp.append([i[0], i[1]+1])
  for n in tmp:
    if n[0] == 0:
      if s[n[0]][n[1]] == '#':
        ans[n[0]][n[1]] = ans[n[0]][n[1]-1] + 1
      else:
        ans[n[0]][n[1]] = ans[n[0]][n[1]-1]
    elif n[1] == 0:
      if s[n[0]][n[1]] == '#':
        ans[n[0]][n[1]] = ans[n[0]-1][n[1]] + 1
      else:
        ans[n[0]][n[1]] = ans[n[0]-1][n[1]]
    elif s[n[0]][n[1]] == '#':
      ans[n[0]][n[1]] = min(ans[n[0]-1][n[1]]+1, ans[n[0]][n[1]-1]+1)
    else:
      ans[n[0]][n[1]] = min(ans[n[0]-1][n[1]], ans[n[0]][n[1]-1])
  if [H-1, W-1] in tmp:
    break
  else:
    l = tmp
    tmp = []
print(ans[H-1][W-1])

Submission status: Wrong Answer

Solution code:
H, W = map(int, input().split())
s = []
for i in range(H):
  s.append(str(input()))
ans = [[10000]*W for i in range(H)]
  
l = [[0, 0]]
tmp = []
if s[0][0] == '.':
  ans[0][0] = 0
else:
  ans[0][0] = 1
  
for p in range(10000):
  for i in l:
    if (i[0]<H-1) and ([i[0]+1, i[1]] not in tmp):
      tmp.append([i[0]+1, i[1]])
    if (i[1]<W-1) and ([i[0], i[1]+1] not in tmp):
      tmp.append([i[0], i[1]+1])
  for n in tmp:
    if n[0] == 0:
      if s[n[0]][n[1]] == '#':
        ans[n[0]][n[1]] = ans[n[0]][n[1]-1] + 1
      else:
        ans[n[0]][n[1]] = ans[n[0]][n[1]-1]
    elif n[1] == 0:
      if s[n[0]][n[1]] == '#':
        ans[n[0]][n[1]] = ans[n[0]-1][n[1]] + 1
      else:
        ans[n[0]][n[1]] = ans[n[0]-1][n[1]]
    elif s[n[0]][n[1]] == '#':
      ans[n[0]][n[1]] = min(ans[n[0]-1][n[1]]+1, ans[n[0]][n[1]-1]+1)
    else:
      ans[n[0]][n[1]] = min(ans[n[0]-1][n[1]], ans[n[0]][n[1]-1])
  if [H-1, W-1] in tmp:
    break
  else:
    l = tmp
    tmp = []
print(ans[H-1][W-1])

Submission status: Wrong Answer

Solution code:
H, W = map(int, input().split())
s = []
for i in range(H):
  s.append(str(input()))
  
l = [[0, 0]]
tmp = []
if s[0][0] == '.':
  ans = 0
else:
  ans = 1
for p in range(10000):
  for i in l:
    if (i[0]<H-1) and ([i[0]+1, i[1]] not in tmp):
      tmp.append([i[0]+1, i[1]])
    if (i[1]<W-1) and ([i[0], i[1]+1] not in tmp):
      tmp.append([i[0], i[1]+1])
  flag = True
  for n in tmp:
    if s[n[0]][n[1]] == '.':
      flag = False
      break
  if flag:
    ans += 1
  if [H-1, W-1] in tmp:
    break
  else:
    l = tmp
    tmp = []
print(ans)

Submission status: Wrong Answer

Solution code:
from pprint import pprint
H, W = map(int, input().split())
s = ["-1"]
dp = [[1000] * (W + 1) for _ in range(H + 1)]
for _ in range(H):
    s.append(input())
s = list(map(lambda x: " " + x, s))
for y in range(1, H + 1):
    for x in range(1, W + 1):
        if y == 1 and x == 1:
            if s[y][x] == "#":
                dp[y][x] = 1
            else:
                dp[y][x] = 0
            continue
        if x == 1:
            if s[y][x] == "#":
                if s[y - 1][x] == "#":
                    dp[y][x] = dp[y - 1][x]
                else:
                    dp[y][x] = dp[y - 1][x] + 1
            else:
                dp[y][x] = dp[y - 1][x]
        elif y == 1:
            if s[y][x] == "#":
                if s[y][x - 1] == "#":
                    dp[y][x] = dp[y][x - 1]
                else:
                    dp[y][x] = dp[y][x - 1] + 1
            else:
                dp[y][x] = dp[y][x - 1]
        else:
            if s[y][x] == "#":
                if s[y][x - 1] == "#":
                    dp[y][x] = dp[y][x - 1]
                if s[y - 1][x] == "#":
                    dp[y][x] = min(dp[y][x], dp[y - 1][x])
                if s[y][x - 1] != "#" and s[y - 1][x] != "#":
                    dp[y][x] = min(dp[y][x - 1], dp[y - 1][x]) + 1
            else:
                dp[y][x] = min(dp[y][x - 1], dp[y - 1][x])
pprint(dp)
print(dp[H][W])

Submission status: Wrong Answer

Solution code:
H, W = map(int, input().split())
s = ["-1"]
dp = [[1000] * (W + 1) for _ in range(H + 1)]
for _ in range(H):
    s.append(input())
s = list(map(lambda x: " " + x, s))
for y in range(1, H + 1):
    for x in range(1, W + 1):
        if y == 1 and x == 1:
            if s[y][x] == "#":
                dp[y][x] = 1
            else:
                dp[y][x] = 0
            continue
        if x == 1:
            if s[y][x] == "#":
                if s[y - 1][x] == "#":
                    dp[y][x] = dp[y - 1][x]
                else:
                    dp[y][x] = dp[y - 1][x] + 1
            else:
                dp[y][x] = dp[y - 1][x]
        elif y == 1:
            if s[y][x] == "#":
                if s[y][x - 1] == "#":
                    dp[y][x] = dp[y][x - 1]
                else:
                    dp[y][x] = dp[y][x - 1] + 1
            else:
                dp[y][x] = dp[y][x - 1]
        else:
            if s[y][x] == "#":
                if s[y][x - 1] == "#":
                    dp[y][x] = dp[y][x - 1]
                if s[y - 1][x] == "#":
                    dp[y][x] = min(dp[y][x], dp[y - 1][x])
                else:
                    dp[y][x] = min(dp[y][x - 1], dp[y - 1][x]) + 1
            else:
                dp[y][x] = min(dp[y][x - 1], dp[y - 1][x])
#print(dp)
print(dp[H][W])

Submission status: Wrong Answer

Solution code:
from collections import deque
H, W = map(int, input().split())
# H, W = 100, 100
maze = []
for _ in range(H):
    maze.append(list(input()))
    # maze.append(['#'] * W)
costs = []
for _ in range(H):
    costs.append([float('inf')] * W)
if maze[0][0] == '.':
    costs[0][0] = 0
else:
    costs[0][0] = 1
dx_list = [0, 1]
dy_list = [1, 0]
q = deque()
q.append([0, 0])

while q:
    x, y = q.popleft()
    if x == W - 1 and y == H - 1:
        break
    for dx, dy in zip(dx_list, dy_list):
        next_x = x + dx
        next_y = y + dy
        if 0 <= next_x <= W - 1 and 0 <= next_y <= H - 1 and costs[next_y][next_x] == float('inf'):
            if maze[next_y][next_x] == '#':
                costs[next_y][next_x] = min(costs[y][x] + 1, costs[next_y][next_x])
                q.append([next_x, next_y])
            else:
                costs[next_y][next_x] = min(costs[y][x], costs[next_y][next_x])
                q.appendleft([next_x, next_y])
# print(*costs, sep='\n')
print(costs[-1][-1])

Submission status: Wrong Answer

Solution code:
from collections import deque
H, W = map(int, input().split())
# H, W = 100, 100
maze = []
for _ in range(H):
    maze.append(list(input()))
    # maze.append(['#'] * W)
costs = []
for _ in range(H):
    costs.append([float('inf')] * W)
if maze[0][0] == '.':
    costs[0][0] = 0
else:
    costs[0][0] = 1
dx_list = [0, 1, 0, -1]
dy_list = [1, 0, -1, 0]
q = deque()
q.append([0, 0, costs[0][0]])
cnt = []
for _ in range(H):
    cnt.append([0] * W)

while q:
    x, y, cost = q.popleft()
    if x == W - 1 and y == H - 1:
        break
    for dx, dy in zip(dx_list, dy_list):
        next_x = x + dx
        next_y = y + dy
        if 0 <= next_x <= W - 1 and 0 <= next_y <= H - 1 and cnt[next_y][next_x] < 4:
            if maze[next_y][next_x] == '#':
                costs[next_y][next_x] = min(costs[y][x] + 1, costs[next_y][next_x])
            else:
                costs[next_y][next_x] = min(costs[y][x], costs[next_y][next_x])
            q.append([next_x, next_y, costs[next_y][next_x]])
            cnt[next_y][next_x] += 1
# print(*costs)
print(costs[-1][-1])

Submission status: Wrong Answer

Solution code:
import sys

h, w = map(int, input().split())
s = [list(x.rstrip()) for x in sys.stdin.readlines()]
dp = [[10**6]*w for _ in range(h)]
if s[0][0] == "#":
    dp[0][0] = 1
else:
    dp[0][0] = 0

for j in range(w):
    for i in range(h):
        for k in range(2):
            nx, ny = i + (k + 1)%2, j + k%2
            if nx >= w or ny >= h:
                continue
            else:
                add = 0
                if s[ny][nx] == "#" and s[j][i] == ".":
                    add = 1
                dp[ny][nx] = min(dp[ny][nx], dp[j][i] + add)
print(dp[h-1][w-1])

Submission status: Wrong Answer

Solution code:
import sys

h, w = map(int, input().split())
s = [list(x.rstrip()) for x in sys.stdin.readlines()]
dp = [[10**6]*w for _ in range(h)]
if s[0][0] == "#":
    dp[0][0] = 1
else:
    dp[0][0] = 0

for i in range(h):
    for j in range(w):
        for k in range(2):
            nx, ny = i + (k + 1)%2, j + k%2
            if nx >= w or ny >= h:
                continue
            else:
                add = 0
                if s[ny][nx] == "#" and s[j][i] == ".":
                    add = 1
                dp[ny][nx] = min(dp[ny][nx], dp[j][i] + add)
print(dp[h-1][w-1])

Submission status: Wrong Answer

Solution code:
import sys

h, w = map(int, input().split())
s = [list(x.rstrip()) for x in sys.stdin.readlines()]
dp = [[1000]*w for _ in range(h)]
if s[0][0] == "#":
    dp[0][0] = 1
else:
    dp[0][0] = 0

for i in range(h):
    for j in range(w):
        for k in range(2):
            nx, ny = i + (k + 1)%2, j + k%2
            if nx >= w or ny >= h:
                continue
            else:
                add = 0
                if s[ny][nx] == "#" and s[j][i] == ".":
                    add = 1
                dp[ny][nx] = min(dp[ny][nx], dp[j][i] + add)
print(dp[h-1][w-1])

Submission status: Wrong Answer

Solution code:
import sys
import math
import copy
import heapq
from functools import cmp_to_key
from bisect import bisect_left, bisect_right
from collections import defaultdict, deque, Counter
sys.setrecursionlimit(1000000)

# input aliases
input = sys.stdin.readline
getS = lambda: input().strip()
getN = lambda: int(input())
getList = lambda: list(map(int, input().split()))
getZList = lambda: [int(x) - 1 for x in input().split()]

INF = float("inf")
MOD = 10**9 + 7
divide = lambda x: pow(x, MOD-2, MOD)

def nck(n, k, kaijyo):
    return (npk(n, k, kaijyo) * divide(kaijyo[k])) % MOD

def npk(n, k, kaijyo):
    if k == 0 or k == n:
        return n % MOD
    return (kaijyo[n] * divide(kaijyo[n-k])) % MOD

def fact_and_inv(SIZE):
    inv = [0] * SIZE  # inv[j] = j^{-1} mod MOD
    fac = [0] * SIZE  # fac[j] = j! mod MOD
    finv = [0] * SIZE  # finv[j] = (j!)^{-1} mod MOD
    inv[1] = 1
    fac[0] = fac[1] = 1
    finv[0] = finv[1] = 1
    for i in range(2, SIZE):
        inv[i] = MOD - (MOD // i) * inv[MOD % i] % MOD
        fac[i] = fac[i - 1] * i % MOD
        finv[i] = finv[i - 1] * inv[i] % MOD

    return fac, finv

def renritsu(A, Y):
    # example 2x + y = 3, x + 3y = 4
    # A = [[2,1], [1,3]])
    # Y = [[3],[4]] または [3,4]
    A = np.matrix(A)
    Y = np.matrix(Y)
    Y = np.reshape(Y, (-1, 1))
    X = np.linalg.solve(A, Y)

    # [1.0, 1.0]
    return X.flatten().tolist()[0]

class TwoDimGrid:
    # 2次元座標 -> 1次元
    def __init__(self, h, w, wall="o"):
        self.h = h
        self.w = w
        self.size = (h+2) * (w+2)
        self.wall = wall
        self.get_grid()
        self.init_cost()

    def get_grid(self):
        grid = [self.wall * (self.w + 2)]
        for i in range(self.h):
            grid.append(self.wall + getS() + self.wall)

        grid.append(self.wall * (self.w + 2))
        self.grid = grid
    def init_cost(self):
        self.cost = [INF] * self.size

    def pos(self, x, y):
        # 壁も含めて0-indexed 元々の座標だけ考えると1-indexed
        return y * (self.w + 2) + x
    def getgrid(self, x, y):
        return self.grid[y][x]
    def get(self, x, y):
        return self.cost[self.pos(x, y)]
    def set(self, x, y, v):
        self.cost[self.pos(x, y)] = v
        return
    def show(self):
        for i in range(self.h+2):
            print(self.cost[(self.w + 2) * i:(self.w + 2) * (i+1)])
    def showsome(self, tgt):
        for t in tgt:
            print(t)
        return
    def showsomejoin(self, tgt):
        for t in tgt:
            print("".join(t))
        return

    def search(self):
        grid = self.grid
        move = [(0, 1), (0, -1), (1, 0), (-1, 0)]
        move_eight = [(0, 1), (0, -1), (1, 0), (-1, 0), (1, 1), (1, -1), (-1, 1), (-1, -1)]
        d = deque()
        d.append((1,1))
        self.set(1,1,0)
        while(d):
            cx, cy = d.popleft()
            cc = self.get(cx, cy)
            if self.getgrid(cx, cy) == self.wall:
                continue
            for dx, dy in [(1, 0), (0, 1)]:
                nx, ny = cx + dx, cy + dy
                if self.getgrid(cx, cy) == self.getgrid(nx, ny):
                    if self.get(nx, ny) > cc:
                        d.append((nx, ny))
                        self.set(nx, ny, cc)
                else:
                    if self.get(nx, ny) > cc + 1:
                        d.append((nx, ny))
                        self.set(nx, ny, cc + 1)

        # self.show()
        ans = (self.get(self.w, self.h) + 1) // 2
        if self.getgrid(1,1) == "#":
            ans += 1
        print(ans)

def soinsu(n):
    ret = defaultdict(int)
    for i in range(2, int(math.sqrt(n) + 2)):
        if n % i == 0:
            while True:
                if n % i == 0:
                    ret[i] += 1
                    n //= i
                else:
                    break

    if not ret:
        return {n: 1}
    return ret


def solve():
    h, w = getList()
    G = TwoDimGrid(h, w)
    G.search()




def main():
    n = getN()
    for _ in range(n):
        solve()

    return
if __name__ == "__main__":
    # main()
    solve()

Submission status: Wrong Answer

Solution code:
h,w=map(int,input().split())
s=[0]*h
t=[0]*h
for i in range(h):
  st=str(input())
  st=list(st)
  s[i]=st
  tt=[0]*w
  t[i]=tt
if s[0][0]=="#":
  t[0][0]=1
for i in range(1,h):
  t[i][0]=t[i-1][0]
  if s[i][0]=="#":
    t[i][0]=t[i-1][0]+1
for i in range(1,w):
  t[0][i]=t[0][i-1]
  if s[0][i]=="#":
    t[0][i]=t[0][i-1]+1
for i in range(1,w):
  for j in range(1,h):
    t[j][i]=min(t[j-1][i],t[j][i-1])
    if s[j][i]=="#":
      t[j][i]=t[j][i]+1
print(t[h-1][w-1])

Submission status: Wrong Answer

Solution code:
h,w=map(int,input().split())
s=[0]*h
t=[0]*h
for i in range(h):
  st=str(input())
  st=list(st)
  s[i]=st
  tt=[0]*w
  t[i]=tt
if s[0][0]=="#":
  t[0][0]=1
for i in range(1,h):
  t[i][0]=t[i-1][0]
  if s[i][0]=="#":
    t[i][0]=t[i-1][0]+1
for i in range(1,w):
  t[0][i]=t[0][i-1]
  if s[0][i]=="#":
    t[0][i]=t[0][i-1]+1
for i in range(1,w):
  for j in range(1,h):
    t[j][i]=min(t[j-1][i],t[j][i-1])
    if s[j][i]=="#":
      t[j][i]=t[j][i-1]+1
print(t[h-1][w-1])

Submission status: Wrong Answer

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

dp = [[0]*(W+1) for _ in range(H+1)]
for h in range(H+1):
    dp[h][0] = H*2
for w in range(W+1):
    dp[0][w] = W*2
dp[0][1] = 0

for h in range(H):
    for w in range(W):
        dp[h+1][w+1] = min(dp[h][w+1], dp[h+1][w])
        if S[h][w] == "#":
            dp[h+1][w+1] += 1

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

Submission status: Wrong Answer

Solution code:
H,W = map(int,input().split())
Map = [0] * H
for i in range(H):
    Map[i] = list(input())

dp = [[float('inf')]*W for _ in range(H)]
if Map[0][0] == '#':
    dp[0][0] = 1
    for i in range(H):
        for j in range(W):
            if Map[i][j] == '.':
                Map[i][j] = '#'
            else:
                Map[i][j] = '.'
else:
    dp[0][0] = 0
for y in range(H):
    for x in range(W):
        if y > 0:
            if Map[y][x] == '#' and Map[y-1][x] == '.':
                dp[y][x] = min(dp[y][x],dp[y-1][x]+1)
            else:
                dp[y][x] = min(dp[y][x],dp[y-1][x])
        if x > 0:
            if Map[y][x] == '#' and Map[y][x-1] == '.':
                dp[y][x] = min(dp[y][x],dp[y][x-1]+1)
            else:
                dp[y][x] = min(dp[y][x],dp[y][x-1])
print(dp[-1][-1])

Submission status: Wrong Answer

Solution code:
H,W = map(int,input().split())
Map = [0] * H
for i in range(H):
    Map[i] = list(input())

dp = [[float('inf')]*W for _ in range(H)]
if Map[0][0] == '#':
    dp[0][0] = 1
    Map[0][0] = '.'
else:
    dp[0][0] = 0
for y in range(H):
    for x in range(W):
        if y > 0:
            if Map[y][x] == '#' and Map[y-1][x] == '.':
                dp[y][x] = min(dp[y][x],dp[y-1][x]+1)
            else:
                dp[y][x] = min(dp[y][x],dp[y-1][x])
        if x > 0:
            if Map[y][x] == '#' and Map[y][x-1] == '.':
                dp[y][x] = min(dp[y][x],dp[y][x-1]+1)
            else:
                dp[y][x] = min(dp[y][x],dp[y][x-1])
print(dp[-1][-1])

Submission status: Wrong Answer

Solution code:
#!/usr/bin/env python3
from collections import deque

h, w = map(int, input().split())
maze = [[i == "#" for i in input()] for _ in range(h)]

dx = [1, 0]
dy = [0, 1]

que = deque([])
que.append((0, 0, maze[0][0], 1 if maze[0][0] else 0))
count = [10**5] * (h + w - 1)

while que:
    x, y, b, c = que.pop()
    if c >= count[x + y]:
        continue
    count[x + y] = c
    if x == h - 1 and y == w - 1:
        continue
    for i in range(2):
        nx = x + dx[i]
        ny = y + dy[i]

        if not (0 <= nx < h and 0 <= ny < w):
            continue
        que.append((nx, ny, maze[nx][ny], c + (not b and maze[nx][ny])))
print(count[-1])

Submission status: Wrong Answer

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

for h in range(1,H+1):
    for w in range(1,W+1):
        if (w==1)&(h==1):continue
        if A[h-1][w-1] == "#":
            B[h][w] = min(B[h][w-1],B[h-1][w])+1
        else:
            B[h][w] = min(B[h][w-1],B[h-1][w])

print(B[H][W])

Submission status: Wrong Answer

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

minimum = float("inf")

stack = [[0,0,0]]
while stack:
    x,y,n = stack.pop()
    if A[y][x] == "#":n+=1
    if (x>=W-1)&(y>=H-1):
        if minimum>n:minimum=n
        break
    if x<W-1:stack.append([x+1,y,n])
    if y<H-1:stack.append([x,y+1,n])

print(minimum)

Submission status: Wrong Answer

Solution code:

#!/usr/bin/python
# -*- coding: utf-8 -*-

import numpy as np

def int_mtx(N):
    x = []
    for _ in range(N):
        x.append(list(input()))
    return x

def int_map():
    return map(int,input().split())

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


H,W = int_map()
s = int_mtx(H)

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

if s[0][0] == "#":
    dp[0][0] = 1

for r in range(0,H-1):
    if s[r+1][0] == ".":
        dp[r+1][0] = dp[r][0]
    else:
        dp[r+1][0] = dp[r][0] + 1

for c in range(0,W-1):
    if s[0][c+1] == ".":
        dp[0][c+1] = dp[0][c]
    else:
        dp[0][c+1] = dp[0][c]+1


for i in range(1,min(H,W)):
    for r in range(i,H):
        if s[r][i] == ".":
            dp[r][i] = min(dp[r-1][i],dp[r][i-1])
        else:
            dp[r][i] = min(dp[r-1][i],dp[r][i-1])+1
    
    for c in range(i,W):
        if s[i][c] == ".":
            dp[i][c] = min(dp[i-1][c],dp[i][c-1])
        else:
            dp[i][c] = min(dp[i-1][c],dp[i][c-1])+1

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

Submission status: Wrong Answer

Solution code:

#!/usr/bin/python
# -*- coding: utf-8 -*-

import numpy as np

def int_mtx(N):
    x = []
    for _ in range(N):
        x.append(list(input()))
    return x

def int_map():
    return map(int,input().split())

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


H,W = int_map()
s = int_mtx(H)

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

if s[0][0] == "#":
    dp[0][0] = 1

for r in range(0,H-1):
    if s[r+1][0] == ".":
        dp[r+1][0] = dp[r][0]
    else:
        dp[r+1][0] = dp[r][0] + 1

for c in range(0,W-1):
    if s[0][c+1] == ".":
        dp[0][c+1] = dp[0][c]
    else:
        dp[0][c+1] = dp[0][c]+1


for i in range(1,min(H,W)):
    for r in range(i,H):
        if s[r][i] == ".":
            dp[r][i] = min(dp[r-1][i],dp[r][i-1])
        else:
            dp[r][i] = min(dp[r-1][i],dp[r][i-1])+1
    
    for c in range(i,W):
        if s[i][c] == ".":
            dp[i][c] = min(dp[i-1][c],dp[i][c-1])
        else:
            dp[i][c] = min(dp[i-1][c],dp[i][c-1])+1

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

Submission status: Wrong Answer

Solution code:

#!/usr/bin/python
# -*- coding: utf-8 -*-

import numpy as np

def int_mtx(N):
    x = []
    for _ in range(N):
        x.append(list(input()))
    return x

def int_map():
    return map(int,input().split())

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


H,W = int_map()
s = int_mtx(H)

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

if s[0][0] == "#":
    dp[0][0] = 1

for r in range(0,H-1):
    if s[r+1][0] == ".":
        dp[r+1][0] = dp[r][0]
    else:
        dp[r+1][0] = dp[r][0] + 1

for c in range(0,W-1):
    if s[0][c+1] == ".":
        dp[0][c+1] = dp[0][c]
    else:
        dp[0][c+1] = dp[0][c]+1


for i in range(1,min(H,W)):
    for r in range(i,H):
        if s[r][i] == ".":
            dp[r][i] = min(dp[r-1][i],dp[r][i-1])
        else:
            dp[r][i] = min(dp[r-1][i],dp[r][i-1])+1
    
    for c in range(i,W):
        if s[i][c] == ".":
            dp[i][c] = min(dp[i-1][c],dp[i][c-1])
        else:
            dp[i][c] = min(dp[i-1][c],dp[i][c-1])+1

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

Submission status: Wrong Answer

Solution code:
def getN():
    return int(input())
def getNM():
    return map(int, input().split())
def getList():
    return list(map(int, input().split()))
def getArray(intn):
    return [int(input()) for i in range(intn)]
def input():
    return sys.stdin.readline().rstrip()
def rand_N(ran1, ran2):
    return random.randint(ran1, ran2)
def rand_List(ran1, ran2, rantime):
    return [random.randint(ran1, ran2) for i in range(rantime)]
def rand_ints_nodup(ran1, ran2, rantime):
  ns = []
  while len(ns) < rantime:
    n = random.randint(ran1, ran2)
    if not n in ns:
      ns.append(n)
  return sorted(ns)

def rand_query(ran1, ran2, rantime):
  r_query = []
  while len(r_query) < rantime:
    n_q = rand_ints_nodup(ran1, ran2, 2)
    if not n_q in r_query:
      r_query.append(n_q)
  return sorted(r_query)

from collections import defaultdict, deque, Counter
from sys import exit
from decimal import *
import heapq
import math
from fractions import gcd
import random
import string
import copy
from itertools import combinations, permutations, product
from operator import mul
from functools import reduce
from bisect import bisect_left, bisect_right

import sys
sys.setrecursionlimit(1000000000)
mod = 10 ** 9 + 7

#############
# Main Code #
#############

H, W = getNM()
maze = []
for i in range(H):
    s = input()
    maze.append(list(s))
dp = [[-1] * W for i in range(H)]
dp[0][0] = 0

pos = deque([[0, 0]])
dx = [1, 0]
dy = [0, 1]

ans = 0
while len(pos) > 0:
    x, y = pos.popleft()
    if x == W - 1 and y == H - 1:
        ans = dp[H - 1][W - 1]
    for i in range(2):
        nx = x + dx[i]
        ny = y + dy[i]
        if 0 <= nx < W and 0 <= ny < H and (dp[ny][nx] == -1 or dp[ny][nx] > dp[y][x] + 1):
            if maze[ny][nx] == "#" and maze[y][x] == ".":
                dp[ny][nx] = dp[y][x] + 1
            else:
                dp[ny][nx] = dp[y][x]
            pos.append([nx, ny])
if maze[0][0] == "#":
    print(ans + 1)
else:
    print(ans)

Submission status: Wrong Answer

Solution code:
from itertools import *
from collections import *
h,w=map(int,input().split())
s=[]
a=[[float("inf")] *w for j in range(h)]
for i in range(h):
    s.append(list(input()))
ans=0
if s[0][0]=="#":
    ans+=1
    s[0][0]="."
if s[h-1][w-1]=="#":
    ans+=1
    s[h-1][w-1]="."
que=deque()
que.append((0,0))
l=[(0,1),(1,0)]
a[0][0]=ans
while que:
    x,y=que.popleft()
    for xx,yy in l:
        nx,ny=xx+x,yy+y
        if nx<h and ny<w:
            if s[nx][ny]=="#":
                    a[nx][ny]=min(a[x][y]+1,a[nx][ny])
                    if (nx,ny) not in que:
                        que.append((nx,ny))
            if s[nx][ny]==".":
                    a[nx][ny]=min(a[x][y],a[nx][ny])
                    if (nx,ny) not in que:
                        que.append((nx,ny))
print(a[h-1][w-1])

Submission status: Wrong Answer

Solution code:
from itertools import *
from collections import *
h,w=map(int,input().split())
s=[]
a=[[float("inf")] *w for j in range(h)]
for i in range(h):
    s.append(list(input()))
ans=0
if s[0][0]=="#":
    ans+=1
    s[0][0]="."
if s[h-1][w-1]=="#":
    ans+=1
    s[h-1][w-1]="."
que=deque()
que.append((0,0))
l=[(0,1),(1,0)]
a[0][0]=ans
while que:
    x,y=que.popleft()
    for xx,yy in l:
        nx,ny=xx+x,yy+y
        if nx<h and ny<w:
            if s[nx][ny]=="#":
                if a[nx][ny]>a[x][y]:
                    a[nx][ny]=a[x][y]+1
                    que.append((nx,ny))
            if s[nx][ny]==".":
                if a[nx][ny]>a[x][y]:
                    a[nx][ny]=a[x][y]
                    que.append((nx,ny))
print(a[h-1][w-1])

Submission status: Wrong Answer

Solution code:
from itertools import *
from collections import *
h,w=map(int,input().split())
s=[]
a=[[float("inf")] *w for j in range(h)]
for i in range(h):
    s.append(list(input()))
ans=0
if s[0][0]=="#":
    ans+=1
    s[0][0]="."
if s[h-1][w-1]=="#":
    ans+=1
    s[h-1][w-1]="."
que=deque()
que.append((0,0))
l=[(0,1),(1,0)]
a[0][0]=ans
while que:
    x,y=que.popleft()
    for xx,yy in l:
        nx,ny=xx+x,yy+y
        if nx<h and ny<w:
            if s[nx][ny]=="#":
                if a[nx][ny]>a[x][y]+1:
                    a[nx][ny]=a[x][y]+1
                    que.append((nx,ny))
            if s[nx][ny]==".":
                if a[nx][ny]>a[x][y]:
                    a[nx][ny]=a[x][y]
                    que.append((nx,ny))
print(a[h-1][w-1])

Submission status: Wrong Answer

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

dp = [[0 for x in range(w)] for y in range(h)]
if grid[0][0] == '#':
    dp[0][0] = 1
else:
    dp[0][0] = 0

for i in range(1, w):
    if grid[0][i] == '.':
        dp[0][i] = dp[0][i-1]
    else:
        if grid[0][i-1] == '.':
            dp[0][i] = dp[0][i-1]+1
        else:
            dp[0][i] = dp[0][i-1]

for i in range(1, h):
    if grid[i][0] == '.':
        dp[i][0] = dp[i-1][0]
    else:
        if grid[i-1][0] == '.':
            dp[i][0] = dp[i-1][0]+1
        else:
            dp[i][0] = dp[i-1][0]

for i in range(1, h):
    for j in range(1, w):
        if grid[i][j] == '.':
            dp[i][j] = min(dp[i-1][j], dp[i][j-1])
        else:
            if grid[i-1][j] == '#' and grid[i][j-1] == '#':
                dp[i][j] = min(dp[i-1][j], dp[i][j-1])
            elif grid[i-1][j] == '#':
                dp[i][j] = dp[i-1][j]
            elif grid[i-1][j] == '#':
                dp[i][j] = dp[i][j-1]
            else:
                dp[i][j] = min(dp[i-1][j], dp[i][j-1]) + 1

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

Submission status: Wrong Answer

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

dp = [[h * w] * w for _ in range(h)]
dp[0][0] = int(s[0][0] == '#')
for i in range(h):
    for j in range(w):
        if i + 1 < h:
            dp[i + 1][j] = min(dp[i + 1][j],
                               dp[i][j] + int(s[i + 1][j] == '#'))
        if j + 1 < w:
            dp[i][j + 1] = min(dp[i][j + 1],
                               dp[i][j] + int(s[i][j + 1] == '#'))
print(dp[-1][-1])