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());M=[input()for _ in"_"*H];D=[[0]*-~W for _ in"_"*-~H]
for i in range(H):
  for j in range(W):D[i+1][j+1]=min([D[i][j+1]+(M[i][j]<M[i-1][j]),999][i<1],[D[i+1][j]+(M[i][j]!=M[i][j-1]),999][j<1],999*(i+j>0))
print(D[-1][-1]+(M[0][0]<"."))

Submission status: Wrong Answer

Solution code:
H,W=map(int,input().split());M=[input()for _ in"_"*H];D=[[0]*-~W for _ in"_"*-~H]
for i in range(H):
  for j in range(W):D[i+1][j+1]=min([D[i][j+1],999][i<1],[D[i+1][j],999][j<1],999*(i+j>0))+(M[i][j]<".")
print(D[-1][-1])

Submission status: Wrong Answer

Solution code:
from collections import*
H,W=map(int,input().split());M=[input()for _ in"_"*H]
L=[[M[j][min(i,H+W-i,H,W)-j-1]<"."for j in range(min(i,H+W-i,H,W))] for i in range(1,H+W)]
for i in range(1,H+W-1):
  for j in range(len(L[i])):
    L[i][j]+=min([L[i-1][j-1],999][j<0],L[i-1][j] if j<len(L[i-1]) else 999,L[i-1][j+1] if len(L[i-1])>len(L[i]) else 999)
print(L[-1][-1])

Submission status: Wrong Answer

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

maze = []
for i in range(h):
    t = list(input())
    maze.append(t)
    
dx = [1, 0]
dy = [0, 1]


dp = [[10000]*w for i in range(h)]
if maze[0][0] == "#":
    dp[0][0] = 1
else:
    dp[0][0] = 0

for x in range(h):
    for y in range(w):
        for dxi, dyi in zip(dx, dy):
            if not (0<=x+dxi<w and 0<=y+dyi<h):
                continue
            dp[y+dyi][x+dxi] = min(dp[y+dyi][x+dxi], dp[y][x]+(maze[y][x]=="." and maze[y+dyi][x+dxi]=="#"))

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

Submission status: Wrong Answer

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


for i in range(H):
    A.append(input())

if A[0][0] == '#':
    dp[0][0] = 1

for i in range(1, W):
    check = 0
    if A[0][i] == '#':
        check = 1
    dp[0][i] = dp[0][i - 1] + check

for i in range(1, H):
    check = 0
    if A[i][0] == '#':
        check = 1
    dp[i][0] = dp[i - 1][0] + check

for i in range(1, H):
    for j in range(1, W):

        check = 0
        if A[i][j] == '#':
            check = 1

        dp[i][j] = min(dp[i - 1][j], dp[i][j - 1]) + check

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

Submission status: Wrong Answer

Solution code:
from collections import deque
H,W = map(int,input().split()); INF = float("inf")
G = []
for i in range(H):
  temp = str(input()); temp = list(temp)
  G.append(temp)
#print(G)
Q = deque([])
visited = [[INF]*W for _ in range(H)]
if G[0][0] == ".":
  visited[0][0] = 0
else:
  visited[0][0] = 1
Q.append((0,0))
dxdy = [(1,0),(-1,0),(0,1),(0,-1)]
while Q:
  x,y = Q.popleft()
  for i in range(4):
    nx = x + dxdy[i][0]
    ny = y + dxdy[i][1]
    if nx < 0 or nx >= H or ny < 0 or ny >= W: #枠外
      continue
    if visited[nx][ny] != INF: #訪問済み
      continue
    if G[nx][ny] == ".": #行ける箇所ならばそのまま
      if G[x][y] == ".": 
        visited[nx][ny] = visited[x][y]
        Q.appendleft((nx,ny))
      else:
        if visited[nx][ny] < visited[x][y]:
          continue
        visited[nx][ny] = visited[x][y]
        Q.append((nx,ny))        
    else: #＃の場合は前による。
      if G[x][y] == ".": #前が行けるところならばここで増える
        if visited[nx][ny] < visited[x][y]+1:
          continue
        visited[nx][ny] = visited[x][y]+1
        Q.append((nx,ny))
      else:
        if visited[nx][ny] < visited[x][y]:
          continue
        visited[nx][ny] = visited[x][y]
        Q.append((nx,ny))
#print(visited)
print(visited[-1][-1])

Submission status: Wrong Answer

Solution code:
from collections import deque
H,W = map(int,input().split()); INF = float("inf")
G = []
for i in range(H):
  temp = str(input()); temp = list(temp)
  G.append(temp)
#print(G)
Q = deque([])
visited = [[INF]*W for _ in range(H)]
if G[0][0] == ".":
  visited[0][0] = 0
else:
  visited[0][0] = 1
Q.append((0,0))
dxdy = [(1,0),(-1,0),(0,1),(0,-1)]
while Q:
  x,y = Q.popleft()
  for i in range(4):
    nx = x + dxdy[i][0]
    ny = y + dxdy[i][1]
    if nx < 0 or nx >= H or ny < 0 or ny >= W: #枠外
      continue
    if visited[nx][ny] != INF: #訪問済み
      continue
    if G[nx][ny] == ".": #行ける箇所ならばそのまま
      if G[x][y] == ".": 
        visited[nx][ny] = visited[x][y]
        Q.appendleft((nx,ny))
      else:
        if visited[nx][ny] < visited[x][y]:
          continue
        visited[nx][ny] = visited[x][y]
        Q.append((nx,ny))        
    else: #＃の場合は前による。
      if G[x][y] == ".": #前が行けるところならばここで増える
        if visited[nx][ny] < visited[x][y]+1:
          continue
        visited[nx][ny] = visited[x][y]+1
        Q.append((nx,ny))
      else:
        if visited[nx][ny] < visited[x][y]:
          continue
        visited[nx][ny] = visited[x][y]
        Q.appendleft((nx,ny))
#print(visited)
print(visited[-1][-1])

Submission status: Wrong Answer

Solution code:
from collections import deque
H,W = map(int,input().split()); INF = float("inf")
G = []
for i in range(H):
  temp = str(input()); temp = list(temp)
  G.append(temp)
#print(G)
Q = deque([])
visited = [[INF]*W for _ in range(H)]
if G[0][0] == ".":
  visited[0][0] = 0
else:
  visited[0][0] = 1
Q.append((0,0))
dxdy = [(1,0),(-1,0),(0,1),(0,-1)]
while Q:
  x,y = Q.popleft()
  for i in range(4):
    nx = x + dxdy[i][0]
    ny = y + dxdy[i][1]
    if nx < 0 or nx >= H or ny < 0 or ny >= W: #枠外
      continue
    if visited[nx][ny] != INF: #訪問済み
      continue
    if G[nx][ny] == ".": #行ける箇所ならばそのまま
      if G[x][y] == ".": 
        visited[nx][ny] = visited[x][y]
        Q.appendleft((nx,ny))
      else:
        visited[nx][ny] = visited[x][y]
        Q.append((nx,ny))        
    else: #＃の場合は前による。
      if G[x][y] == ".": #前が行けるところならばここで増える
        visited[nx][ny] = visited[x][y]+1
        Q.append((nx,ny))
      else:
        visited[nx][ny] = visited[x][y]
        Q.appendleft((nx,ny))
#print(visited)
print(visited[-1][-1])

Submission status: Wrong Answer

Solution code:
from collections import deque
H,W = map(int,input().split()); INF = float("inf")
G = []
for i in range(H):
  temp = str(input()); temp = list(temp)
  G.append(temp)
#print(G)
Q = deque([])
visited = [[INF]*W for _ in range(H)]
if G[0][0] == ".":
  visited[0][0] = 0
else:
  visited[0][0] = 1
Q.append((0,0))
dxdy = [(1,0),(-1,0),(0,1),(0,-1)]
while Q:
  x,y = Q.popleft()
  for i in range(4):
    nx = x + dxdy[i][0]
    ny = y + dxdy[i][1]
    if nx < 0 or nx >= H or ny < 0 or ny >= W: #枠外
      continue
    if visited[nx][ny] != INF: #訪問済み
      continue
    if G[nx][ny] == ".": #行ける箇所ならばそのまま
      visited[nx][ny] = visited[x][y]
      Q.appendleft((nx,ny))
    else: #＃の場合は前による。
      if G[x][y] == ".": #前が行けるところならばここで増える
        visited[nx][ny] = visited[x][y]+1
        Q.append((nx,ny))
      else:
        visited[nx][ny] = visited[x][y]
        Q.appendleft((nx,ny))
#print(visited)
print(visited[-1][-1])

Submission status: Wrong Answer

Solution code:
from collections import deque

H, W = [int(x) - 1 for x in input().split()]

board = []

for _ in range(H+1):
    r = list([x for x in input()])
    board.append(r)

queue = deque()

if board[0][0] == '#':
    queue.appendleft((0, 0, 1))
else:
    queue.appendleft((0, 0, 0))

ended = set()

while queue:
    r, c, count = queue.popleft()
    ended.add((r, c))

    if r == H and c == W:
        print(count)
        exit()

    if r + 1 <= H:
        if not (r+1, c) in ended:
            if board[r + 1][c] == '.':
                queue.appendleft((r+1, c, count))
            else:
                queue.append((r+1, c, count+1))

    if c + 1 <= W:
        if not (r, c+1) in ended:
            if board[r][c+1] == '.':
                queue.appendleft((r, c+1, count))
            else:
                queue.append((r, c+1, count+1))

Submission status: Wrong Answer

Solution code:
H,W = map(int,input().split())
A = [input().strip() for _ in range(H)]
dp = [[0 for _ in range(W)] for _ in range(H)]
if A[H-1][W-1]=="#":
    dp[H-1][W-1] = 1
else:
    dp[H-1][W-1] = 0
for j in range(W-2,-1,-1):
    dp[H-1][j] = dp[H-1][j+1]
    if A[H-1][j]=="#":
        dp[H-1][j] += 1
for i in range(H-2,-1,-1):
    dp[i][W-1] = dp[i+1][W-1]
    if A[i][W-1]=="#":
        dp[i][W-1] += 1
for i in range(H-2,-1,-1):
    for j in range(W-2,-1,-1):
        dp[i][j] = min(dp[i+1][j],dp[i][j+1])
        if A[i][j]=="#":
            dp[i][j] += 1
print(dp[0][0])

Submission status: Wrong Answer

Solution code:
from collections import deque
H,W = map(int,input().split()); INF = float("inf")
G = []
for i in range(H):
  temp = str(input()); temp = list(temp)
  G.append(temp)
#print(G)
Q = deque([])
visited = [[INF]*W for _ in range(H)]
if G[0][0] == ".":
  visited[0][0] = 0
else:
  visited[0][0] = 1
Q.append((0,0))
dxdy = [(1,0),(-1,0),(0,1),(0,-1)]
while Q:
  x,y = Q.popleft()
  for i in range(4):
    nx = x + dxdy[i][0]
    ny = y + dxdy[i][1]
    if nx < 0 or nx >= H or ny < 0 or ny >= W: #枠外
      continue
    if visited[nx][ny] != INF: #訪問済み
      continue
    if G[nx][ny] == ".": #行ける箇所ならばそのまま
      visited[nx][ny] = visited[x][y]
      Q.appendleft((nx,ny))
    else: #＃の場合は前による。
      if G[x][y] == ".": #前が行けるところならばここで増える
        visited[nx][ny] = visited[x][y]+1
      else:
        visited[nx][ny] = visited[x][y]
      Q.append((nx,ny))
#print(visited)
print(visited[-1][-1])

Submission status: Wrong Answer

Solution code:
INF = 10 ** 8
H, W = map(int,input().split())
L = []
for _ in range(H):
    L.append(list(input()))
dp = [[INF for i in range(W+1)] for j in range(H+1)]
d = {'.':0, '#':1}

dp[0][1] = 0

for i in range(H):
    for j in range(W):
        dp[i+1][j+1] = min(dp[i][j+1], dp[i+1][j]) + d[L[i][j]]
print(dp[-1][-1])

Submission status: Wrong Answer

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

Submission status: Wrong Answer

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

Submission status: Wrong Answer

Solution code:
import math,string,itertools,fractions,heapq,collections,re,array,bisect,sys,random,time, copy

sys.setrecursionlimit(10**7)
inf = 10**20
mod = 10**9 + 7

stdin = sys.stdin

ni = lambda: int(ns())
na = lambda: list(map(int, stdin.readline().split()))
ns = lambda: stdin.readline().rstrip()  # ignore trailing spaces

h, w = na()
m = [ns() for i in range(h)]
visited = [[0] * w for i in range(h)]

now = 0
def dfs(m, y, x, visited):
    dx = [-1, 0, 1, 0]
    dy = [0, -1, 0, 1]
    if m[y][x] == '#' and visited[y][x] == 0:
        visited[y][x] = now
        for i, j in zip(dx, dy):
            nx = x + i
            ny = y + j
            if 0 <= ny < h and 0 <= nx < w:
                dfs(m, ny, nx, visited)
ct = 0
for y in range(h):
    for x in range(w):
        if m[y][x] == '#' and visited[y][x] == 0:
            ct += 1
            now += 1
            dfs(m, y, x, visited)

root = [[[] for _ in range(w)] for _ in range(h)]
dp= [[inf] * w for _ in range(h)]
dp[0][0] = 0
tmp = [x for x in range(1, 101)]
for y in range(h):
    for x in range(w):
        if y == 0 and x == 0:
            if m[0][0] == '#':
                root[0][0].append(1)
                continue
            else:
                continue
        if x - 1 >= 0:
            l = copy.copy(root[y][x-1])
        else:
            l = copy.copy(tmp)
        if y - 1 >= 0:
            u = copy.copy(root[y-1][x])
        else:
            u = copy.copy(tmp)
        if m[y][x] == '#':
            p = visited[y][x]
            if p not in l:
                l.append(p)
            if p not in u:
                u.append(p)
        if len(l) < len(u):
            root[y][x] = copy.copy(l)
        else:
            root[y][x] = copy.copy(u)
        """
        if x - 1 >= 0 and y - 1 >= 0:
            if len(root[y][x-1]) <= len(root[y-1][x]):
                root[y][x] = copy.copy(root[y][x-1])
            else:
                root[y][x] = copy.copy(root[y-1][x])
        elif x - 1 >= 0:
            root[y][x] = copy.copy(root[y][x-1])
        else:
            root[y][x] = copy.copy(root[y-1][x])
        
        if m[y][x] == '#':
            p = visited[y][x]
            if p not in root[y][x]:
                (root[y][x]).append(p)
        """
print(len(root[h-1][w-1]))

Submission status: Wrong Answer

Solution code:
import math,string,itertools,fractions,heapq,collections,re,array,bisect,sys,random,time, copy

sys.setrecursionlimit(10**7)
inf = 10**20
mod = 10**9 + 7

stdin = sys.stdin

ni = lambda: int(ns())
na = lambda: list(map(int, stdin.readline().split()))
ns = lambda: stdin.readline().rstrip()  # ignore trailing spaces

h, w = na()
m = [ns() for i in range(h)]
visited = [[0] * w for i in range(h)]

now = 0
def dfs(m, y, x, visited):
    dx = [-1, 0, 1, 0]
    dy = [0, -1, 0, 1]
    if m[y][x] == '#' and visited[y][x] == 0:
        visited[y][x] = now
        for i, j in zip(dx, dy):
            nx = x + i
            ny = y + j
            if 0 <= ny < h and 0 <= nx < w:
                dfs(m, ny, nx, visited)
ct = 0
for y in range(h):
    for x in range(w):
        if m[y][x] == '#' and visited[y][x] == 0:
            ct += 1
            now += 1
            dfs(m, y, x, visited)

root = [[[] for _ in range(w)] for _ in range(h)]
dp= [[inf] * w for _ in range(h)]
dp[0][0] = 0
tmp = [x for x in range(1, 101)]
for y in range(h):
    for x in range(w):
        if y == 0 and x == 0:
            continue
        if x - 1 >= 0:
            l = copy.copy(root[y][x-1])
        else:
            l = copy.copy(tmp)
        if y - 1 >= 0:
            u = copy.copy(root[y-1][x])
        else:
            u = copy.copy(tmp)
        if m[y][x] == '#':
            p = visited[y][x]
            if p not in l:
                l.append(p)
            if p not in u:
                u.append(p)
        if len(l) < len(u):
            root[y][x] = copy.copy(l)
        else:
            root[y][x] = copy.copy(u)
        """
        if x - 1 >= 0 and y - 1 >= 0:
            if len(root[y][x-1]) <= len(root[y-1][x]):
                root[y][x] = copy.copy(root[y][x-1])
            else:
                root[y][x] = copy.copy(root[y-1][x])
        elif x - 1 >= 0:
            root[y][x] = copy.copy(root[y][x-1])
        else:
            root[y][x] = copy.copy(root[y-1][x])
        
        if m[y][x] == '#':
            p = visited[y][x]
            if p not in root[y][x]:
                (root[y][x]).append(p)
        """
print(len(root[h-1][w-1]))

Submission status: Wrong Answer

Solution code:
import math,string,itertools,fractions,heapq,collections,re,array,bisect,sys,random,time, copy

sys.setrecursionlimit(10**7)
inf = 10**20
mod = 10**9 + 7

stdin = sys.stdin

ni = lambda: int(ns())
na = lambda: list(map(int, stdin.readline().split()))
ns = lambda: stdin.readline().rstrip()  # ignore trailing spaces

h, w = na()
m = [ns() for i in range(h)]
visited = [[0] * w for i in range(h)]

now = 0
def dfs(m, y, x, visited):
    dx = [-1, 0, 1, 0]
    dy = [0, -1, 0, 1]
    if m[y][x] == '#' and visited[y][x] == 0:
        visited[y][x] = now
        for i, j in zip(dx, dy):
            nx = x + i
            ny = y + j
            if 0 <= ny < h and 0 <= nx < w:
                dfs(m, ny, nx, visited)
ct = 0
for y in range(h):
    for x in range(w):
        if m[y][x] == '#' and visited[y][x] == 0:
            ct += 1
            now += 1
            dfs(m, y, x, visited)

root = [[[] for _ in range(w)] for _ in range(h)]
dp= [[inf] * w for _ in range(h)]
dp[0][0] = 0
for y in range(h):
    for x in range(w):
        if x - 1 >= 0 and y - 1 >= 0:
            if len(root[y][x-1]) <= len(root[y-1][x]):
                root[y][x] = copy.copy(root[y][x-1])
            else:
                root[y][x] = copy.copy(root[y-1][x])
        elif x - 1 >= 0:
            root[y][x] = copy.copy(root[y][x-1])
        else:
            root[y][x] = copy.copy(root[y-1][x])
        
        if m[y][x] == '#':
            p = visited[y][x]
            if p not in root[y][x]:
                (root[y][x]).append(p)
print(len(root[h-1][w-1]))

Submission status: Wrong Answer

Solution code:
import math,string,itertools,fractions,heapq,collections,re,array,bisect,sys,random,time

sys.setrecursionlimit(10**7)
inf = 10**20
mod = 10**9 + 7

stdin = sys.stdin

ni = lambda: int(ns())
na = lambda: list(map(int, stdin.readline().split()))
ns = lambda: stdin.readline().rstrip()  # ignore trailing spaces

H, W = na()
m = [ns() for _ in range(H)]
dp = [[inf] * W for _ in range(H)]

dp[0][0] = 0
for i in range(H):
    for j in range(W):
        if i - 1 >= 0:
            dp[i][j] = min(dp[i][j], dp[i-1][j])
        if j - 1 >= 0:
            dp[i][j] = min(dp[i][j], dp[i][j-1])
        if m[i][j] == '#':
            dp[i][j] += 1 
print(dp[H-1][W-1])

Submission status: Wrong Answer

Solution code:
import math
from functools import lru_cache

@lru_cache(maxsize = None)
def count_change_point_min(r , c , current_color):
    min_values = list()
    if r != h-1:
        min_values.append(count_change_point_min(r+1, c, S[r][c]))
    if c != w-1:
        min_values.append(count_change_point_min(r, c+1, S[r][c]))
    if len(min_values) == 0:
        min_values.append(0)
        
    return min(min_values) + (0 if S[r][c] == current_color else 1)
    
    
h,w = map(int,input().split())
S = list()
for _ in range(h):
    S.append(list(input()))
    
print (math.floor(count_change_point_min(0, 0, S[0][0]) / 2) + (0 if S[0][0] == "." else 1))

Submission status: Wrong Answer

Solution code:
import math
from functools import lru_cache

@lru_cache(maxsize = None)
def count_change_point_min(r , c , current_color):
    min_values = list()
    if r != h-1:
        min_values.append(count_change_point_min(r+1, c, S[r][c]))
    if c != w-1:
        min_values.append(count_change_point_min(r, c+1, S[r][c]))
    if len(min_values) == 0:
        min_values.append(0)
        
    return min(min_values) + (0 if S[r][c] == current_color else 1)
    
    
h,w = map(int,input().split())
S = list()
for _ in range(h):
    S.append(list(input()))
    
print (math.ceil(count_change_point_min(0, 0, S[0][0]) / 2))

Submission status: Wrong Answer

Solution code:
h,w=map(int,input().split())
m=[]
for i in range(h):
  m.append(list(map(lambda x:int(x=="#"),list(input()))))
s=[[100000 for i in range(w+1)] for j in range(h+1)]
s[-1][0]=0
for i in range(h):
  for j in range(w):
    s[i][j]=min(s[i-1][j],s[i][j-1])+m[i][j]
print(s[-2][-2])

Submission status: Wrong Answer

Solution code:
h,w=map(int,input().split())
m=[]
for i in range(h):
  m.append(list(map(lambda x:int(x=="#"),list(input())))+[1])
m.append([1 for i in range(w+1)])
s=[[0 for i in range(w)]+[100000] for j in range(h)]+[[100000 for i in range(w)]]
s[-1][0]=0
for i in range(h):
  for j in range(w):
    s[i][j]=min(s[i-1][j],s[i][j-1])+m[i][j]
print(s[-2][-2])

Submission status: Wrong Answer

Solution code:
h,w=map(int,input().split())
m=[]
for i in range(h):
  m.append(list(map(lambda x:int(x=="#"),list(input())))+[1])
m.append([1 for i in range(w+1)])
s=[[0 for i in range(w)]+[1000] for j in range(h)]+[[1000 for i in range(w)]]
s[-1][0]=0
for i in range(h):
  for j in range(w):
    s[i][j]=min(s[i-1][j],s[i][j-1])+m[i][j]
print(s[-2][-2])

Submission status: Wrong Answer

Solution code:
from collections import deque
h, w = list(map(int, input().split()))
grid = [input() for _ in range(h)]

ans = [[10000]*w for _ in range(h)]
ans[0][0] = 0 if grid[0][0] == "." else 1

queue = deque([(0, 0)])

while len(queue) > 0:
    x, y = queue.popleft()

    for xo, yo in [(0, 1), (1, 0)]:
        xnext, ynext = x+xo, y+yo

        if xnext >= w or ynext >= h:
            continue

        if grid[y][x] == "#" and grid[ynext][xnext] == ".":
            if ans[y][x] + 1 < ans[ynext][xnext]:
                ans[ynext][xnext] = ans[y][x] + 1
                queue.append((xnext, ynext))
        else:
            if ans[y][x] < ans[ynext][xnext]:
                ans[ynext][xnext] = ans[y][x]
                queue.append((xnext, ynext))

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

Submission status: Wrong Answer

Solution code:

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

dp=[[float('inf')]*w for i in range(h)]

cnt=0
for i in range(h):
  if maze[i][0]=='#':
    cnt+=1
  dp[i][0]=cnt


cnt=0
for i in range(w):
  if maze[0][i]=='#':
    cnt+=1
  dp[0][i]=cnt

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


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

Submission status: Wrong Answer

Solution code:
# https://atcoder.jp/contests/agc043/tasks/agc043_a

import sys
# sys.setrecursionlimit(100000)


def input():
    return sys.stdin.readline().strip()


def input_int():
    return int(input())


def input_int_list():
    return [int(i) for i in input().split()]


ans = (100 * 100) + 1


def main():
    global ans
    h, w = input_int_list()
    grid = []
    grid.append(["#"] * (w + 2))
    for _ in range(h):
        grid.append(["#"] + list(input()) + ["#"])
    grid.append(["#"] * (w + 2))

    dp = [[101 for _ in range(w + 2)] for _ in range(h + 2)]
    if grid[1][1] == "#":
        dp[1][1] = 1
    else:
        dp[1][1] = 0
    for i in range(1, h + 1):
        for j in range(1, w + 1):
            # 下のマスを評価
            if grid[i + 1][j] == "#":
                dp[i + 1][j] = min(dp[i + 1][j], dp[i][j] + 1)
            else:
                dp[i + 1][j] = min(dp[i + 1][j], dp[i][j])
            # 右のマスを評価
            if grid[i][j + 1] == "#":
                dp[i][j + 1] = min(dp[i][j + 1], dp[i][j] + 1)
            else:
                dp[i][j + 1] = min(dp[i][j + 1], dp[i][j])

    print(dp[h][w])
    return


if __name__ == "__main__":
    main()

Submission status: Wrong Answer

Solution code:
# https://atcoder.jp/contests/agc043/tasks/agc043_a

import sys
# sys.setrecursionlimit(100000)


def input():
    return sys.stdin.readline().strip()


def input_int():
    return int(input())


def input_int_list():
    return [int(i) for i in input().split()]


ans = (100 * 100) + 1


def main():
    global ans
    h, w = input_int_list()
    grid = []
    grid.append(["#"] * (w + 2))
    for _ in range(h):
        grid.append(["#"] + list(input()) + ["#"])
    grid.append(["#"] * (w + 2))

    dp = [[101] + [0 for _ in range(w)] + [101] for _ in range(h + 1)]
    dp[0] = [101] * (w + 2)
    dp[0][1] = 0
    dp[1][0] = 0
    for i in range(1, h + 1):
        for j in range(1, w + 1):
            if grid[i][j] == "#":
                dp[i][j] = min(dp[i - 1][j], dp[i][j - 1]) + 1
            else:
                dp[i][j] = min(dp[i - 1][j], dp[i][j - 1])

    print(dp[h][w])
    return


if __name__ == "__main__":
    main()

Submission status: Wrong Answer

Solution code:
# https://atcoder.jp/contests/agc043/tasks/agc043_a

import sys
# sys.setrecursionlimit(100000)


def input():
    return sys.stdin.readline().strip()


def input_int():
    return int(input())


def input_int_list():
    return [int(i) for i in input().split()]


ans = (100 * 100) + 1


def main():
    global ans
    h, w = input_int_list()
    grid = []
    grid.append(["#"] * (w + 2))
    for _ in range(h):
        grid.append(["#"] + list(input()) + ["#"])
    grid.append(["#"] * (w + 2))

    dp = [[101] + [0 for _ in range(w)] + [101] for _ in range(h + 1)]
    dp[0] = [101] * (w + 2)
    dp[0][1] = 0
    dp[1][0] = 0
    for i in range(1, h + 1):
        for j in range(1, w + 1):
            if grid[i][j] == "#":
                dp[i][j] = min(dp[i - 1][j], dp[i][j - 1]) + 1
            else:
                dp[i][j] = min(dp[i - 1][j], dp[i][j - 1])
    for line in dp:
        print(line)
    print(dp[h][w])
    return


if __name__ == "__main__":
    main()

Submission status: Wrong Answer

Solution code:
h, w = map(int, input().split())
hw = [input() for _ in range(h)]
ans = h+w
pvs = hw[0][0]

def dfs(x, y, cnt, pvs):
    global ans
    if ans < cnt:
        return ans
    else:
        if hw[x][y] == "#" and pvs == ".":
            cnt += 1
            pvs = "#"
        elif hw[x][y] == "#" and pvs == "#":
            pass
        elif hw[x][y] == ".":
            pvs = "."
        if x == h-1 and y == w-1:
            ans = min(ans, cnt)
            return ans
        if x < h-1 and y == w-1:
            dfs(x+1, y, cnt, pvs)
        if x == h-1 and y < w-1:
            dfs(x, y+1, cnt, pvs)
        if x < h-1 and y < w-1:
            dfs(x+1, y, cnt, pvs)
            dfs(x, y+1, cnt, pvs)

dfs(0, 0, 0, pvs)
print(ans)

Submission status: Wrong Answer

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

from collections import deque
def bfs(h,w,S):
    maze=[[10**9]*(w)for _ in range(h)]
    maze[0][0]=1*(S[0][0]=='#')
    que=deque([[0,0]])
    while que:
        y,x=que.popleft()
        for i,j in [(1,0),(0,1)]:
            nexty,nextx=y+i,x+j
            if 0<=nexty<h and 0<=nextx<w:
                dist1=S[nexty][nextx]
                dist2=maze[nexty][nextx]
            else:
                continue
            if dist1!='#':
                if dist2>maze[y][x]:
                    maze[nexty][nextx]=maze[y][x]
                    que.append([nexty,nextx])
            else:
                if dist2>maze[y][x]+1:
                    maze[nexty][nextx]=maze[y][x]+1
                    que.append([nexty,nextx])
    return maze

A=bfs(H,W,S)
print(A[H-1][W-1])

Submission status: Wrong Answer

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

from collections import deque
def bfs(h,w,S):
    maze=[[10**9]*(W)for _ in range(H)]
    maze[0][0]=1*(S[0][0]=='#')
    que=deque([[0,0]])
    while que:
        y,x=que.popleft()
        for i,j in [(1,0),(0,1)]:
            nexty,nextx=y+i,x+j
            if 0<=nexty<h and 0<=nextx<w:
                dist1=S[nexty][nextx]
                dist2=maze[nexty][nextx]
            else:
                continue
            if dist1!='#':
                if dist2>maze[y][x]:
                    maze[nexty][nextx]=maze[y][x]
                    que.append([nexty,nextx])
            else:
                if dist2>maze[y][x]+1:
                    maze[nexty][nextx]=maze[y][x]+1
                    que.append([nexty,nextx])
    return maze

A=bfs(H,W,S)
print(A[H-1][W-1])

Submission status: Wrong Answer

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

memo = [[10*5]*W for _ in range(H)]
mp = [input() for _ in range(H)]

if mp[0][0] == '#':
  memo[0][0] = 1
else:
  memo[0][0] = 0

for i in range(H):
  for j in range(W):
    if i > 0:
      if mp[i-1][j] == '.' and mp[i][j] == '#':
        memo[i][j] = min(memo[i][j],memo[i-1][j]+1)
      else:
        memo[i][j] = min(memo[i][j],memo[i-1][j])
    if j > 0:
      if mp[i][j-1] == '.' and mp[i][j] == '#':
        memo[i][j] = min(memo[i][j],memo[i][j-1]+1)
      else:
        memo[i][j] = min(memo[i][j],memo[i][j-1])
        
print(memo[-1][-1])

Submission status: Wrong Answer

Solution code:
import queue
h, w = map(int, input().split())
s = [list(input()) for _ in range(h)]
ans = float('inf')
q = queue.Queue()
vals = [[float('inf')]*w for _ in range(h)]

if s[0][0] == '#':
    q.put([0, 0, 1])
else:
    q.put([0, 0, 0])

while not q.empty():
    a = q.get()
    if a[0] == h-1 and a[1] == w-1:
        ans = min(ans, a[2])
        
    if a[0]+1 < h:
        if s[a[0]+1][a[1]] == '.':
            q.put([a[0]+1, a[1], a[2]])
            vals[a[0]+1][a[1]] = a[2]
        elif vals[a[0]][a[1]]+1 < vals[a[0]+1][a[1]]:
            q.put([a[0]+1, a[1], a[2]+1])
            vals[a[0]+1][a[1]] = a[2]+1

    if a[1]+1 < w:
        if s[a[0]][a[1]+1] == '.':
            q.put([a[0], a[1]+1, a[2]])
        elif vals[a[0]][a[1]]+1 < vals[a[0]][a[1]+1]:
            q.put([a[0], a[1]+1, a[2]+1])
            vals[a[0]][a[1]+1] = a[2]+1
print(ans)

Submission status: Wrong Answer

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

#solution:dp

dp=[[float('inf') for _ in range(w)] for _ in range(h)]
dp[0][0] = 0 if s[0][0] == '.' else 1

def update(dp, i, j, ni, nj):
    if s[ni][nj]=='.':
        dp[ni][nj]=min(dp[i][j],dp[ni][nj])
    elif s[i][j]=='#':
        dp[ni][nj]=min(dp[i][j],dp[ni][nj])
    else:
        dp[ni][nj]=min(dp[i][j]+1,dp[ni][nj])
    
for i in range(h):
    for j in range(w):
        if i+1<h:
            update(dp,i,j,i+1,j)
        if j+1<w:
            update(dp,i,j,i,j+1)
print(dp[h-1][w-1])
print(dp)

Submission status: Wrong Answer

Solution code:
import collections
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
Q = collections.deque([0])
while True:
    if not Q:
        break
    i = Q.popleft()
    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
                    Q += [nx * W + ny]
            elif dist[nx][ny] > d:
                dist[nx][ny] = d
                Q += [nx * W + ny]
ans = dist[-1][-1]
if S[0][0] == '#':
    ans += 1
print(ans)