Problem:


Score : 400 points

Problem Statement

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

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

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

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

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

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

Constraints

2 \leq H, W \leq 100

Input

Input is given from Standard Input in the following format:

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

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

Output

Print the minimum number of operations needed.

Sample Input 1

3 3
.##
.#.
##.

Sample Output 1

1

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

Sample Input 2

2 2
#.
.#

Sample Output 2

2

Sample Input 3

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

Sample Output 3

0

No operation may be needed.

Sample Input 4

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

Sample Output 4

4



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


Sample output:
1

Submission status: Wrong Answer

Solution code:
import sys
import re
import math
import collections
import decimal
import bisect
import itertools
import fractions
import functools
import copy
import heapq
import decimal
import statistics
import queue

sys.setrecursionlimit(10000001)
INF = 10**10
MOD = 10 ** 9 + 7

ni = lambda: int(sys.stdin.readline())
ns = lambda: map(int, sys.stdin.readline().split())
na = lambda: list(map(int, sys.stdin.readline().split()))


# ===CODE===
def main():
    h, w = ns()
    mat = [list(input()) for _ in range(h)]

    ans_mat = [[INF for _ in range(w)] for _ in range(h)]
    if mat[0][0] == "#":
        ans_mat[0][0] = 1
    else:
        ans_mat[0][0] = 0

    for y in range(h):
        for x in range(w):
            if x + 1 < w:
                if mat[y][x + 1] == "#":
                    ans_mat[y][x + 1] = min(ans_mat[y][x + 1], ans_mat[y][x] + 1)
                else:
                    ans_mat[y][x + 1] = min(ans_mat[y][x + 1], ans_mat[y][x])

            if y + 1 < h:
                if mat[y + 1][x] == "#":
                    ans_mat[y + 1][x] = min(ans_mat[y + 1][x], ans_mat[y][x] + 1)
                else:
                    ans_mat[y + 1][x] = min(ans_mat[y + 1][x], ans_mat[y][x])

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


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
import sys
import re
import math
import collections
import decimal
import bisect
import itertools
import fractions
import functools
import copy
import heapq
import decimal
import statistics
import queue

sys.setrecursionlimit(10000001)
INF = sys.maxsize
MOD = 10 ** 9 + 7

ni = lambda: int(sys.stdin.readline())
ns = lambda: map(int, sys.stdin.readline().split())
na = lambda: list(map(int, sys.stdin.readline().split()))


# ===CODE===
def main():
    h, w = ns()
    mat = [list(input()) for _ in range(h)]

    ans_mat = [[INF for _ in range(w)] for _ in range(h)]
    if mat[0][0] == "#":
        ans_mat[0][0] = 1
    else:
        ans_mat[0][0] = 0

    for y in range(h):
        for x in range(w):
            if x + 1 < w:
                if mat[y][x + 1] == "#":
                    ans_mat[y][x + 1] = min(ans_mat[y][x + 1], ans_mat[y][x] + 1)
                else:
                    ans_mat[y][x + 1] = min(ans_mat[y][x + 1], ans_mat[y][x])

            if y + 1 < h:
                if mat[y + 1][x] == "#":
                    ans_mat[y + 1][x] = min(ans_mat[y + 1][x], ans_mat[y][x] + 1)
                else:
                    ans_mat[y + 1][x] = min(ans_mat[y + 1][x], ans_mat[y][x])

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


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

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

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

for i in range(H):
    for j in range(W):
        c = []
        if 0 <= i - 1 < H:
            c.append(dp[i - 1][j])
        if 0 <= j - 1 < W:
            c.append(dp[i][j - 1])
        if len(c) > 0:
            dp[i][j] = min(c)
        if s[i][j] == '#':
            dp[i][j] += 1
print(dp[H - 1][W - 1])

Submission status: Wrong Answer

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

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

for i in range(H):
    for j in range(W):
        c = []
        if 0 <= i - 1 < H:
            c.append(dp[i - 1][j])
        if 0 <= j - 1 < W:
            c.append(dp[i][j - 1])
        if len(c) > 0:
            dp[i][j] = min(c)
        if s[i][j] == '#':
            dp[i][j] += 1
print(dp)
print(dp[H - 1][W - 1])

Submission status: Wrong Answer

Solution code:
n,m=map(int,input().split())
l=[]
for i in range(n):
    l.append(input())
dp=[]
for i in range(n):
    dp.append([0]*m)
if l[-1][-1]=='#':
    dp[-1][-1]=1
else:
    dp[-1][-1]=0
for i in range(m-2,-1,-1):
    if l[n-1][i]=='#':
        dp[n-1][i]=1+dp[n-1][i+1]
    else:
        dp[n-1][i]=dp[n-1][i+1]
for i in range(n-2,-1,-1):
    if l[i][m-1]=='#':
        dp[i][m-1]=1+dp[i+1][m-1]
    else:
        dp[i][m-1]=dp[i+1][m-1]
for i in range(n-2,-1,-1):
    for j in range(m-2,-1,-1):
        if l[i][j]=='#':
            dp[i][j]=1+min(dp[i+1][j],dp[i][j+1])
        else:
            dp[i][j]=min(dp[i+1][j],dp[i][j+1])
print(dp[0][0])

Submission status: Wrong Answer

Solution code:
h, w = map(int, input().split())
maze = list(input() for i in range(h))
count = [[float('inf')]*w for i in range(h)]
count[0][0] = 0 if maze[0][0] == "." else 1

for i in range(h):
  for j in range(w):
    here = 0 if maze[i][j] == "." else 1
    a = min(count[max(0, i-1)][j] + here, count[i][max(0, j-1)] + here)
    count[i][j] = min(count[i][j], a)
    
print(count[h-1][w-1])

Submission status: Wrong Answer

Solution code:
import sys
sys.stdin.readline

H, W = map(int, input().split())
board = [[[0,1][a == "#"] for a in input()] for i in range(H)]
Y = [[0]*W for _ in range(H)]

for i in range(H):
    for j in range(W):
        a = []
        if j == 0:
            pass
        else:
            if board[i][j-1] == False and board[i][j]:
                a.append(Y[i][j-1] + 1)
            else:
                a.append(Y[i][j-1])
        if i == 0:
            pass
        else:
            if board[i-1][j] == False and board[i][j]:
                a.append(Y[i-1][j] + 1)
            else:
                a.append(Y[i-1][j])
        if i + j == 0:
            a.append(0)
        Y[i][j] = min(a)

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

Submission status: Wrong Answer

Solution code:
import sys
sys.stdin.readline

H, W = map(int, input().split())
board = [[[0,1][a == "#"] for a in input()] for i in range(H)]
Y = [[0]*W for _ in range(H)]

for i in range(H):
    for j in range(W):
        a = []
        if j == 0:
            pass
        else:
            if board[i][j-1] == False and board[i][j]:
                a.append(Y[i][j-1] + 1)
            else:
                a.append(Y[i][j-1])
        if i == 0:
            pass
        else:
            if board[i-1][j] == False and board[i][j]:
                a.append(Y[i-1][j] + 1)
            else:
                a.append(Y[i-1][j])
        if i + j == 0:
            a.append(0)
        Y[i][j] = min(a)
        print(Y[i][j])

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

Submission status: Wrong Answer

Solution code:
import sys
sys.stdin.readline

H, W = map(int, input().split())
board = [[[0,1][a == "#"] for a in input()] for i in range(H)]
Y = [[0]*W for _ in range(H)]

for i in range(H):
    for j in range(W):
        a = []
        if j == 0:
            pass
        else:
            if board[i][j-1] == False and board[i][j]:
                a.append(Y[i][j-1] + 1)
            else:
                a.append(Y[i][j-1])
        if i == 0:
            pass
        else:
            if board[i-1][j] == False and board[i][j]:
                a.append(Y[i-1][j] + 1)
            else:
                a.append(Y[i-1][j])
        if i + j == 0:
            continue
        Y[i][j] = min(a)

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



'''
for i in range(H-1):
    for j in range(W-1):
        if board[i+1][j] == False or board[i][j+1] == False:
            pass
        else:
            count += 1
'''

Submission status: Wrong Answer

Solution code:
from sys import stdin, stdout
from collections import deque, defaultdict
import math as m

rl = lambda: stdin.readline()
rll = lambda: stdin.readline().split()
rli = lambda: map(int, stdin.readline().split())

INF, NINF = float('inf'), float('-inf')

def main():
	H, W = rli()
	M = []
	#0 white, 1 black
	for _ in range(H):
		row = list(rll()[0])
		row = list(map(lambda x: 0 if x == "." else 1, row))
		M.append(row)

	dp = [[INF if i != 0 and j != 0 else 0 for j in range(W)] for i in range(H)]
	dp[0][0] = 1 if M[0][0] == 1 else 0
	for c in range(1, W):
		if M[0][c-1] == 0:
			if M[0][c] == 1:
				dp[0][c] = dp[0][c-1] + 1
		else:
			dp[0][c] = dp[0][c-1]
	for r in range(1, H):
		if M[r-1][0] == 0:
			if M[r][0] == 1:
				dp[r][0] = dp[r-1][0] + 1
		else:
			dp[r][0] = dp[r-1][0]
	dbg = lambda r, c: r == 1 and c == 1
	for r in range(1, H):
		for c in range(1, W):
			c1, c2 = INF, INF
			if M[r-1][c] == 0 and M[r][c] == 1:
				c1 = dp[r-1][c] + 1
			if M[r][c-1] == 0 and M[r][c] == 1:
				c2 = dp[r][c-1] + 1
			c1 = dp[r-1][c] if c1 == INF else c1 
			c2 = dp[r][c-1] if c2 == INF else c2
			dp[r][c] = min(c1, c2)
	print(dp[-1][-1])
	stdout.close()

if __name__ == "__main__":
	main()

Submission status: Wrong Answer

Solution code:
import sys

H, W = map(int, input().split())
G = [list(sys.stdin.readline().strip()) for _ in range(H)]

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

DP[0][0] = int(G[0][0] == "#")
for i in range(1, H):
    DP[i][0] = DP[i - 1][0] + int(G[i][0] == "#")
for j in range(1, W):
    DP[0][j] = DP[0][j - 1] + int(G[0][j] == "#")

for i in range(1, H):
    for j in range(1, W):
        t = int(G[i][j] == "#")
        DP[i][j] = min(DP[i - 1][j] + int(t and G[i - 1][j] == "."), DP[i][j - 1] + int(t and G[i][j - 1] == "."))

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

Submission status: Wrong Answer

Solution code:
import sys

H, W = map(int, input().split())
G = [list(sys.stdin.readline().strip()) for _ in range(H)]

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

DP[0][0] = int(G[0][0] == "#")
for i in range(1, H):
    DP[i][0] = DP[i - 1][0] + int(G[i][0] == "#")
for j in range(1, W):
    DP[0][j] = DP[0][j - 1] + int(G[0][j] == "#")

for i in range(1, H):
    for j in range(1, W):
        t = int(G[i][j] == "#")
        DP[i][j] = min(DP[i - 1][j] + t, DP[i][j - 1] + t)

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

Submission status: Wrong Answer

Solution code:
H, W = map(int, input().split())
s = []
for _ in range(H):
  s.append(input())
  
def main(H, W, s):
  # 動的計画法
  
  INF = float('inf')
  dp = [[INF]*W for _ in range(H)]
  if s[0][0] == '#':
    dp[0][0] = 1
  else:
    dp[0][0] = 0

  dx = (1, 0)
  dy = (0, 1)
  for i in range(H):
    for j in range(W):
      for dir_ in range(2):  # 右に行くか下に行くかの2通り
        ni = i + dx[dir_]
        nj = j + dy[dir_]
        if ni >= H or nj >= W:
          continue
        add = 0
        if s[ni][nj] == '#' and s[i][j] == '.':
          add = 1
        dp[ni][nj] = min(dp[ni][nj], dp[i][j] + add)
        
  print(dp)

  return dp[H-1][W-1]

print(main(H, W, s))

Submission status: Wrong Answer

Solution code:
H, W = [int(a) for a in input().split()]
grid = []
for _ in range(H):
    grid.append(list(input()))
paths = [[[0, 0]]]
test = False
while True:
    newpaths = []
    for path in paths:
        lastNode = path[-1]
        if lastNode == [H-1, W-1]:
            test = True
            break
        if lastNode[0] < H-1:
            path2 = path+[[lastNode[0]+1, lastNode[1]]]
            newpaths.append(path2)
        if lastNode[1] < W-1:
            path1 = path+[[lastNode[0], lastNode[1]+1]]
            newpaths.append(path1)
    if test:
        break
    else:
        paths = newpaths
test = False
attempts = []
for path in paths:
    att = 0
    for [x, y] in path:
        if grid[x][y] == '#' and test == False:
            test = True
            att = att+1
        if grid[x][y] == '.':
            test = False
    attempts.append(att)
print(min(attempts))

Submission status: Wrong Answer

Solution code:
import sys


def main():
    dp = [[float("inf")] * W for _ in range(H)]

    for y in range(H):
        for x in range(W):
            if x == 0 and y == 0:
                if s[0][0] == "#":
                    dp[0][0] = 1
                else:
                    dp[0][0] = 0
            elif x == 0:
                if s[y][x] == "#":
                    dp[y][x] = dp[y - 1][x] + 1
                else:
                    dp[y][x] = dp[y - 1][x]
            elif y == 0:
                if s[y][x] == "#":
                    dp[y][x] = dp[y][x - 1] + 1
                else:
                    dp[y][x] = dp[y][x - 1]
            else:
                if s[y][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])

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


if __name__ == "__main__":
    H, W = map(int, sys.stdin.readline().split())
    s = [list(sys.stdin.readline().rstrip()) for _ in range(H)]
    main()

Submission status: Wrong Answer

Solution code:
def main():

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

    dp = [[0 for _ in range(W+1)] for _ in range(H+1)]
    for i in range(H+1):
        dp[i][0] = float('inf')
    for i in range(W+1):
        dp[0][i] = float('inf')
    dp[0][1] = 0
    for i in range(H):
        for j in range(W):
            dp[i+1][j+1] = 0
            if s[i][j] == '#':
                dp[i+1][j+1] += 1
            dp[i+1][j+1] += min(dp[i][j+1], dp[i+1][j])
    # print(dp)
    return dp[H][W]

if __name__ == '__main__':
    print(main())

Submission status: Wrong Answer

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

S = [input() for _ in range(H)]

INF = 10 ** 5
dp = [[INF] * (W + 1) for _ in range(H + 1)]
dp[0][0] = int(S[0][0] == '#')

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

        # 横移動
        if j == 0:
            v1 = INF
        else:
            v1 = int(S[i][j - 1] == '#' and S[i][j] != '#') + dp[i][j - 1]

        # 縦移動
        if i == 0:
            v2 = INF
        else:
            v2 = int(S[i - 1][j] == '#' and S[i][j] != '#') + dp[i - 1][j]

        dp[i][j] = min(v1, v2, dp[i][j])
ans = dp[H - 1][W - 1]
print(ans)

Submission status: Wrong Answer

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

S = [input() for _ in range(H)]

INF = 10 ** 5
dp = [[INF] * (W + 1) for _ in range(H + 1)]
dp[0][0] = int(S[0][0] == '#')

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

        # 横移動
        if j == 0:
            v1 = INF
        else:
            v1 = int('.' != S[i][j]) + dp[i][j - 1]

        # 縦移動
        if i == 0:
            v2 = INF
        else:
            v2 = int('.' != S[i][j]) + dp[i - 1][j]

        dp[i][j] = min(v1, v2, dp[i][j])
print(dp[H - 1][W - 1])

Submission status: Wrong Answer

Solution code:
from collections import deque


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

S = [input() for _ in range(H)]


"""
移動先の色が同じであれば、その部分は一回の操作でひっくり返せるので、黒から黒へ連続で移動していても操作回数は一回でOK

"""
INF = float("inf")
costs = [[INF for _ in range(W)] for _ in range(H)]

costs[0][0] = 0 if S[0][0] == "." else 1

q = deque()
q.append((costs[0][0], 0, 0))

while q:
    curr_cost, y, x = q.popleft()
    for dy, dx in [(1,0), (0,1)]:
        if y + dy >= H or x + dx >= W:
            continue
        nxt_cost = curr_cost if S[y][x] == S[y+dy][x+dx] else curr_cost + 1
        if nxt_cost < costs[y+dy][x+dx]:
            costs[y+dy][x+dx] = nxt_cost
            q.append((nxt_cost, y+dy, x+dx))


print(costs[-1][-1] // 2)

Submission status: Wrong Answer

Solution code:
1

Submission status: Wrong Answer

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

dp = [[float('inf') for _ in range(W)] for _ in range(H)]
dp[0][0] = 1 if S[0][0] == '#' else 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] + (1 if S[i + 1][j] == '#' else 0))
        if j + 1 < W:
            dp[i][j + 1] = min(dp[i][j + 1], dp[i][j] + (1 if S[i][j + 1] == '#' else 0))

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

Submission status: Wrong Answer

Solution code:

def solve(arr,matrix,n,m):
    maxx=0
    if n>0:
        if arr[0][0]=="#":
            matrix[0][0]=1
        maxx=max(maxx,matrix[0][0])
        for col in range(1,m):
            matrix[0][col]=matrix[0][col-1]
            if arr[0][col]=="#":
                matrix[0][col]+=1
            maxx=max(maxx,matrix[0][col])

        for row in range(1,n):    
            matrix[row][0]=matrix[row-1][0]
            if arr[row][0]=="#":
                matrix[row][0]+=1
            maxx=max(maxx,matrix[row][0])

        for row in range(1,n):
            for col in range(1,m):
                matrix[row][col]=min(matrix[row-1][col],matrix[row][col-1])
                if arr[row][col]=="#":
                    matrix[row][col]+=1
                maxx=max(maxx,matrix[row][col])
        return matrix[n-1][m-1]        



n,m=map(int,input().split())
arr=[int(0) for i in range(n)]
matrix=[int(0) for i in range(n)]
for i in range(n):
    arr[i]=list(input())
    matrix[i]=[int(0) for _ in range(m)]



print(solve(arr,matrix,n,m))

Submission status: Wrong Answer

Solution code:
h, w = map(int, input().split())
M = [list(input()) for _ in range(h)]
count = [[int(1e5) for _ in range(w)] for _ in range(h)]

count[0][0] = 1 if M[0][0] == '#' else 0
for x in range(1, w):
    v = 1 if M[0][x] == '#' else 0
    count[0][x] = count[0][x - 1] + v
for y in range(1, h):
    v = 1 if M[y][0] == '#' else 0
    count[y][0] = count[y - 1][0] + v

# for r in M: print(r)

for y in range(1, h):
    for x in range(1, w):
        v = 1 if M[y][x] == '#' else 0
        v1 = count[y-1][x]
        v2 = count[y][x - 1]
        count[y][x] = min(count[y - 1][x], count[y][x - 1]) + v

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

Submission status: Wrong Answer

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

mat = [[] for _ in range(h)]

for i in range(h):
    mat[i] = input()

dp = [[float("inf")] * w for _ in range(h)]

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

for i in range(h):
    for j in range(w):

        if mat[i][j] == "#":
            add = 1
        else:
            add = 0

        if j - 1 >= 0:
            top = dp[i][j - 1]
        else:
            top = float("inf")

        if i - 1 >= 0:
            left = dp[i - 1][j]
        else:
            left = float("inf")

        dp[i][j] = min(dp[i][j], left + add, top + add)

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

Submission status: Wrong Answer

Solution code:
import numpy as np

H,W = input().split()
H,W=int(H),int(W)
P=[0]*H
for i in range(H):
    P[i] = input()

dp=np.zeros((H,W),dtype='u8')
if P[0][0]=='#':
    dp[0][0]=1
else:
    dp[0][0]=0

def DP(x,y):
    global dp
    if 0<=x<=W-1 and 0<=y<=H-1:
        return dp[y][x]
    else:
        return 9999999

for l in range(1,H+W):
    for i in range(l+1):
        if i<H and l-i<W:
            if P[i][l-i]=='#':
                a=DP(i-1,l-i)
                b=DP(i,l-i-1)
                if a < 9999999:
                    if P[i-1][l-i]=='.':
                        a+=1
                if b <  9999999:
                    if P[i][l-i-1]=='.':
                        b+=1
                dp[i][l-i]=min(a,b)
            else:
                #print(i,l-i,DP(i-1,l-i),DP(i,l-i-1))
                dp[i][l-i]=min(DP(i-1,l-i),DP(i,l-i-1))
print(dp[H-1][W-1])

Submission status: Wrong Answer

Solution code:
import numpy as np

H,W = input().split()
H,W=int(H),int(W)
P=[0]*H
for i in range(H):
    P[i] = input()

dp=np.zeros((H,W),dtype='u8')
if P[0][0]=='#':
    dp[0][0]=1
else:
    dp[0][0]=0

def DP(x,y):
    global dp
    if 0<=x<=W-1 and 0<=y<=H-1:
        return dp[y][x]
    else:
        return 9999999

for l in range(1,H+W):
    for i in range(l+1):
        if i<H and l-i<W:
            if P[i][l-i]=='#':
                #print(i,l-i, DP(i-1,l-i),DP(i,l-i-1))
                dp[i][l-i]=min(DP(i-1,l-i),DP(i,l-i-1))+1
            else:
                #print(i,l-i,DP(i-1,l-i),DP(i,l-i-1))
                dp[i][l-i]=min(DP(i-1,l-i),DP(i,l-i-1))
print(dp[H-1][W-1])

Submission status: Wrong Answer

Solution code:
import numpy as np

H,W = input().split()
H,W=int(H),int(W)
P=[0]*H
for i in range(H):
    P[i] = input()

dp=np.zeros((H,W),dtype='u8')
if P[0][0]=='#':
    dp[0][0]=1
else:
    dp[0][0]=0

def DP(x,y):
    global dp
    if 0<=x<=W-1 and 0<=y<=H-1:
        return dp[y][x]
    else:
        return 9999999

for l in range(1,H+W):
    for i in range(l):
        if i<H and l-i<W:
            if P[i][l-i]=='#':
                #print(i,l-i, DP(i-1,l-i),DP(i,l-i-1))
                dp[i][l-i]=min(DP(i-1,l-i),DP(i,l-i-1))+1
            else:
                #print(i,l-i,DP(i-1,l-i),DP(i,l-i-1))
                dp[i][l-i]=min(DP(i-1,l-i),DP(i,l-i-1))
print(dp[H-1][W-1])

Submission status: Wrong Answer

Solution code:
H,W = map(int,input().split())
S = [list(input()) for i in range(H)]
from collections import deque


global ans 
ans = 10**9+7
def dfs(now,color,num):
    global ans
    dire = ((1, 0), (0, 1))
    
    que = deque([now]) # (sx, sy)からスタート
    while que:
        x, y = que.popleft()
        flag = True
        for dx, dy in dire:
            nx,ny = x+dx,y+dy
            if (nx,ny)==(H-1,W-1):
                ans = min(ans,num)
                return
            if 0<=nx<H and 0<=ny<W and S[nx][ny] == color:
                que.append((nx,ny))
                flag = False
        if flag:
            
            if color=='.':
                
                dfs((x,y),'#',num+1)

            else:
                dfs((x,y),'.',num+1)

if S[0][0]=='.':
    dfs((0,0),'.',0)
else:
    dfs((0,0),'#',1)
print(ans)

Submission status: Wrong Answer

Solution code:
H, W = [int(x) for x in input().split()]

S = []
for h in range(H):
    r = input()
    S.append(r)

A = [[float("INF")] * 105 for _ in range(105)]
A[0][0] = (1 if S[0][0] == '#' else 0)


for h in range(H):
    for w in range(W):
        if h!= 0:
            if S[h][w] == '#':
                if S[h-1][w] == '#':
                    A[h][w] = min(A[h][w], A[h-1][w])
                else:
                    A[h][w] = min(A[h][w], A[h-1][w]) + 1
            else:
                A[h][w] = min(A[h][w], A[h-1][w])

        if w!= 0:
            if S[h][w] == '#':
                if S[h][w-1] == '#':
                    A[h][w] = min(A[h][w], A[h][w-1])
                else:
                    A[h][w] = min(A[h][w], A[h][w-1]) + 1
            else:
                A[h][w] = min(A[h][w], A[h][w-1])

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

Submission status: Wrong Answer

Solution code:
H, W = [int(x) for x in input().split()]

S = []
for h in range(H):
    r = input()
    S.append(r)

A = [[float("INF")] * 105 for _ in range(105)]
A[0][0] = 0

for h in range(H):
    for w in range(W):
        if h!= 0:
            A[h][w] = min(A[h][w], A[h-1][w])
        if w!= 0:
            A[h][w] = min(A[h][w], A[h][w-1])
        A[h][w] += (1 if S[h][w] == '#' else 0)

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

Submission status: Wrong Answer

Solution code:
H, W = [int(x) for x in input().split()]

S = []
for h in range(H):
    r = input()
    S.append(r)

A = [[999999999] * 105 for _ in range(105)]
A[0][0] = (1 if S[0][0] == '#' else 0)

for h in range(H):
    for w in range(W):
        Z = 1 if S[h][w] == '#' else 0
        if h!= 0:
            A[h][w] = min(A[h][w], A[h-1][w])
        if w!= 0:
            A[h][w] = min(A[h][w], A[h][w-1])
        if not (h==0 and w==0):
           A[h][w] = A[h][w] + Z

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

Submission status: Wrong Answer

Solution code:
h,w = map(int, raw_input().split(' '))
mat = [raw_input() for _ in range(h)] 
dp =[[0] * len(mat[0]) for _ in range(len(mat))]
for i in range(len(mat)):
	for j in range(len(mat[0])):
		dp[i][j] += 1 if mat[i][j] == '#' else 0
		if not(i == 0 and j == 0):
			dp[i][j] += min(dp[i-1][j] if i-1>=0 else +float('inf'),dp[i][j-1] if j-1>=0 else +float('inf'))
print dp[-1][-1]

Submission status: Wrong Answer

Solution code:
h,w = map(int, raw_input().split(' '))
mat = [raw_input() for _ in range(h)] 
dp =[[0] * len(mat[0]) for _ in range(len(mat))]
for i in range(len(mat)):
	for j in range(len(mat[0])):
		dp[i][j] += 1 if mat[i][j] == '#' else 0
		if not(i == 0 and j == 0):
			dp[i][j] += min(dp[i-1][j] if i-1>=0 else +2000,dp[i][j-1] if j-1>=0 else +2000)
print dp[-1][-1]

Submission status: Wrong Answer

Solution code:
h,w = map(int, raw_input().split(' '))
mat = [raw_input() for _ in range(h)] 
dp =[[0] * len(mat[0]) for _ in range(len(mat))]
for i in range(len(mat)):
	for j in range(len(mat[0])):
		dp[i][j] += 1 if mat[i][j] == '#' else 0
		if i or j:
			dp[i][j] += min(dp[i-1][j] if i-1>=0 else +200,dp[i][j-1] if j-1>=0 else +200)
print dp[-1][-1]

Submission status: Wrong Answer

Solution code:
import sys
import collections

sys.setrecursionlimit(10 ** 8)

input = sys.stdin.readline


def main():
    H, W = [int(x) for x in input().split()]
    S = [list(input().strip()) for _ in range(H)]

    dp = [[10 ** 9] * W for j in range(H)]

    if S[0][0] == '#':
        S[0][0] = '.'
        dp[0][0] = 1
    else:
        dp[0][0] = 0

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

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


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

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

Submission status: Wrong Answer

Solution code:
h,w=map(int,input().split())
field=[list(input()) for i in range(h)]
ans=[[0]*w]*h
def black(i,j):
  if field[i][j]=='#':
    return 1
  else:
    return 0
for i in range(h):
  for j in range(w):
    if i==0 and j==0:
      ans[0][0]=black(0,0)
    elif i==0:
      ans[i][j]=ans[i][j-1]+black(i,j)
    elif j==0:
      ans[i][j]=ans[i-1][j]+black(i,j)
    else:
      ans[i][j]=min(ans[i-1][j],ans[i][j-1])+black(i,j)
print(ans[-1][-1])

Submission status: Wrong Answer

Solution code:

#ライブラリインポート
from collections import defaultdict

con = 10 ** 9 + 7
#入力受け取り
def getlist():
	return list(map(int, input().split()))

#処理内容
def main():
	H, W = getlist()
	L = []
	for i in range(H):
		l = list(input())
		L.append(l)

	DP = [[0] * W for i in range(H)]
	#初期化
	if L[0][0] == "#":
		DP[0][0] = 1
	for i in range(1, H):
		if L[i][0] == "#":
			DP[i][0] += DP[i - 1][0] + 1
		else:
			DP[i][0] += DP[i - 1][0]
	for i in range(1, W):
		if L[0][i] == "#":
			DP[0][i] += DP[0][i - 1] + 1
		else:
			DP[0][i] += DP[0][i - 1]

	for i in range(1, H):
		for j in range(1, W):
			if L[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])


if __name__ == '__main__':
	main()

Submission status: Wrong Answer

Solution code:
maze = []
cnt = []
H,W = None,None

def dfs(x,y):
    if x< H-1:
        if cnt[x][y] + (maze[x+1][y]=="#") < cnt[x+1][y]:
            cnt[x+1][y] = cnt[x][y] + (maze[x+1][y]=="#")
            dfs(x+1,y)

    if y< W-1:
        if cnt[x][y] + (maze[x][y+1]=="#") < cnt[x][y+1]:
            cnt[x][y+1] = cnt[x][y] + (maze[x][y+1]=="#")
            dfs(x,y+1)


def main():
    INF = pow(10,6)
    global H,W,maze,cnt
    H,W = map(int,input().split())
    cnt = [[INF for i in range(W)] for j in range(H)]
    for i in range(H):
        tmp = list(input())
        maze.append(tmp)

    cnt[0][0] = 1 if maze[0][0]=="#" else 0
    dfs(x=0,y=0)
    print(cnt[H-1][W-1])
    return

if __name__ == "__main__":
    main()

Submission status: Wrong Answer

Solution code:
# https://atcoder.jp/contests/agc043/tasks/agc043_a
h, w = map(int, input().split())
matrix = []
for _ in range(h):
    row = list(input())
    matrix.append(row)

dp = [[float('inf')] * (w + 1) for _ in range(h + 1)]
dp[0][0] = 0
if matrix[0][0] == '#':
    dp[0][0] += 1

for i in range(h):
    for j in range(w):
        if matrix[i][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 matrix[i][j] == '#':
            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])

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

Submission status: Wrong Answer

Solution code:

from functools import lru_cache
import sys
sys.setrecursionlimit(10 ** 9)


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

ans = 0
for i in range(h):
    maze[i] = input()

INF = 10000

@lru_cache(None)
def dfs(y,x,flg,cnt):
    if y == h-1 and x ==w-1:
        return cnt
    ans = [INF]
    for (ny, nx) in [(y+1, x), (y, x+1)]:
        if 0 <= nx < w and 0 <= ny < h:
            if maze[ny][nx] != maze[y][x]:
                if flg == 0: ans.append(dfs(ny,nx,1,cnt))
                else: ans.append(dfs(ny,nx,0,cnt+1))
            else:
                ans.append(dfs(ny,nx,flg,cnt))
    return(min(ans))

print(dfs(0,0,(0 if maze[0][0]=='.' else 1),(0 if maze[0][0]=='.' else 1)))

Submission status: Wrong Answer

Solution code:
from functools import lru_cache
import sys
sys.setrecursionlimit(10 ** 9)


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

ans = 0
for i in range(h):
    maze[i] = input()

INF = 10000

@lru_cache(None)
def dfs(y,x,flg,cnt):
    if y == h-1 and x ==w-1:
        return cnt
    ans = [INF]
    for (ny, nx) in [(y+1, x), (y, x+1)]:
        if 0 <= nx < w and 0 <= ny < h:
            if maze[ny][nx] != maze[y][x]:
                if flg == 0: ans.append(dfs(ny,nx,1,cnt))
                else: ans.append(dfs(ny,nx,0,cnt+1))
            else:
                ans.append(dfs(ny,nx,flg,cnt))
    return(min(ans))

print(dfs(0,0,(0 if maze[0][0]=='.' else 1),(0 if maze[0][0]=='.' else 1)))