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 = list(map(int, input().split()))

mymap = []
for i in range(H):
    mymap.append(input())

memo = [10000] * H * W
memo[0] = 0

def walk(x, y):
    val = memo[x * W + y]
    if val == 10000:
        tmp = []
        if x != 0: # up
            tmp.append(walk(x-1, y))
        if y != 0: # left
            tmp.append(walk(x, y-1))
        val = min(tmp)
    if mymap[x][y] == '#':
        val += 1
    memo[x * W + y] = val
    return val

walk(H-1, W-1)
#print(memo)
print(memo[H*W-1])

Submission status: Wrong Answer

Solution code:
H, W = map(int, input().split())
temp = [[i for i in input()] for j in range(H)]
S = [[] for i in range(H)]
for a in range(H):
    for b in range(W):
        if temp[a][b] == "#":
            S[a].append(1)
        else:
            S[a].append(0)

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

for i in range(1, H):
    dp[i][0] = dp[i-1][0] + S[i][0]

for j in range(1, W):
    dp[0][j] = dp[0][j-1] + S[0][j]

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

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

Submission status: Wrong Answer

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

mymap = []
for i in range(H):
    mymap.append(input())

memo = [10000] * H * W
memo[0] = 0
def walk(x, y):
    if x == H-1 and y == W-1:
        if mymap[x][y] == '#':
            memo[x * W + y] += 1
        return
    if x != H-1: # down
        if mymap[x+1][y] == '#':
            #if memo[(x+1) * W + y] > memo[x * W + y] + 1:
            if memo[(x+1) * W + y] == 10000:
                memo[(x+1) * W + y] = memo[x * W + y] + 1
        else:
            #if memo[(x+1) * W + y] > memo[x * W + y]:
            if memo[(x+1) * W + y] == 10000:
                memo[(x+1) * W + y] = memo[x * W + y]
        walk(x+1, y)
    if y != W-1: # right
        if mymap[x][y+1] == '#':
            #if memo[x * W + (y+1)] > memo[x * W + y] + 1:
            if memo[x * W + (y+1)] == 10000:
                memo[x * W + (y+1)] = memo[x * W + y] + 1
        else:
            #if memo[x * W + (y+1)] > memo[x * W + y]:
            if memo[x * W + (y+1)] == 10000:
                memo[x * W + (y+1)] = memo[x * W + y]
        walk(x, y+1)

walk(0, 0)
print(memo[H*W-1])

Submission status: Wrong Answer

Solution code:

h,w = map(int,input().split())

def isvalid(r,c):
    return 0 <= r < h and 0 <= c < w

g = [input() for _ in range(h)]
d = [1,0,-1,0]
queue = [(0,0)]
dist = [[1000000]* w for _ in range(h)]
dist[0][0] = 0
if g[0][0] == '#':
    dist[0][0] = 1
while len(queue) > 0:
    next_queue = []
    for r,c in queue:
        for i in range(4):
            cos = dist[r][c]
            nr = r + d[i]
            nc = c + d[1^i]
            if not isvalid(nr,nc):
                continue
            if  g[r][c] != g[nr][nc]:
                cos += 1
            if cos < dist[nr][nc]:
                dist[nr][nc] = cos
                next_queue.append((nr,nc))
    queue = next_queue
print((dist[h-1][w-1] + 1)//2)

Submission status: Wrong Answer

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


def main() -> None:
    H, W = rmi()
    s = []
    for h in range(H):
        line = list(map(lambda c: c == '.', list(r())))
        s.append(line)
    dp = []
    for _ in range(H):
        dp.append([-1] * W)
    dp[0][0] = 0 if s[0][0] else 1
    for h in range(1, H):
        dp[h][0] = dp[h - 1][0] if s[h][0] else dp[h - 1][0] + 1
    for w in range(1, W):
        dp[0][w] = dp[0][w - 1] if s[0][w] else dp[0][w - 1] + 1
    for h in range(1, H):
        for w in range(1, W):
            minimum = min(dp[h - 1][w], dp[h][w - 1])
            dp[h][w] = minimum if s[h][w] else minimum + 1
    print(dp[h][w])


def r() -> str:
    return input().strip()


def ri() -> int:
    return int(r())


def rmi(delim: str = ' ') -> tuple:
    return tuple(map(int, input().split(delim)))


def w(data) -> None:
    print(data)


def wm(*data, delim: str = ' ') -> None:
    print(delim.join(map(str, data)))


if __name__ == '__main__':
    import sys
    sys.setrecursionlimit(10 ** 9)
    main()

Submission status: Wrong Answer

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


def main() -> None:
    H, W = rmi()
    s = []
    for h in range(H):
        line = list(map(lambda c: c == '.', list(r())))
        s.append(line)
    dp = []
    for _ in range(H):
        dp.append([-1] * W)
    dp[0][0] = 0
    for h in range(1, H):
        dp[h][0] = dp[h - 1][0] if s[h][0] else dp[h - 1][0] + 1
    for w in range(1, W):
        dp[0][w] = dp[0][w - 1] if s[0][w] else dp[0][w - 1] + 1
    for h in range(1, H):
        for w in range(1, W):
            minimum = min(dp[h - 1][w], dp[h][w - 1])
            dp[h][w] = minimum if s[h][w] else minimum + 1
    print(dp[h][w])


def r() -> str:
    return input().strip()


def ri() -> int:
    return int(r())


def rmi(delim: str = ' ') -> tuple:
    return tuple(map(int, input().split(delim)))


def w(data) -> None:
    print(data)


def wm(*data, delim: str = ' ') -> None:
    print(delim.join(map(str, data)))


if __name__ == '__main__':
    import sys
    sys.setrecursionlimit(10 ** 9)
    main()

Submission status: Wrong Answer

Solution code:
H, W = map(int, input().split())
maze = []
dp = [[float('inf') for _ in range(W)] for __ in range(H) ]

for _ in range(H):
    maze.append(list(input()))

if maze[0][0] == '#':
    dp[0][0] = 1
else:
    dp[0][0] = 0


direction = [[1, 0], [0, 1]]

start = [[0, 0]]

while not [H-1, W-1] in start:

    for s in start:
        r = []
        x, y = s
        for x1, y1 in direction:
            if x+x1 == H or y+y1 == W:
                continue
            if dp[x+x1][y+y1] < dp[x][y]:
                continue
            if maze[x][y] != maze[x+x1][y+y1] and maze[x+x1][y+y1] == '#':
                dp[x+x1][y+y1] = dp[x][y] + 1
            else:
                dp[x+x1][y+y1] = dp[x][y]
            if start[-1] != [x+x1, y+y1]:
                start.append([x+x1, y+y1])


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

Submission status: Wrong Answer

Solution code:
H, W = map(int, input().split())
maze = []
dp = [[float('inf') for _ in range(W)] for __ in range(H) ]

for _ in range(H):
    maze.append(list(input()))

if maze[0][0] == '#':
    dp[0][0] = 1
else:
    dp[0][0] = 0


direction = [[1, 0], [0, 1]]

start = [[0, 0]]

while not [H-1, W-1] in start:

    for s in start:
        r = []
        x, y = s
        for x1, y1 in direction:
            if x+x1 == H or y+y1 == W:
                continue
            if dp[x+x1][y+y1] < dp[x][y]:
                continue
            if maze[x+x1][y+y1] == '#':
                dp[x+x1][y+y1] = dp[x][y] + 1
            else:
                dp[x+x1][y+y1] = dp[x][y]
            if start[-1] != [x+x1, y+y1]:
                start.append([x+x1, y+y1])


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

Submission status: Wrong Answer

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

h, w = list(map(int, input().split()))

ss = [list(str(input())) for _ in range(h)]

dp = [[100*100 for _ in range(w+1)] for i in range(h+1)]  # dp[h][w]

# for i in range(w+1):
#     dp[0][i] = 10000
# for i in range(h+1):
#     dp[i][0] = 10000

dp[0][1] = 0
dp[1][0] = 0

for h_tmp in range(0, h):
    for w_tmp in range(0, w):
        # print(h_tmp+1, w_tmp+1)
        # print(dp[h_tmp][w_tmp+1], dp[h_tmp+1][w_tmp])

        if ss[h_tmp][w_tmp] == "#":
            dp[h_tmp+1][w_tmp+1] = min(dp[h_tmp][w_tmp+1],
                                       dp[h_tmp+1][w_tmp]) + 1

        else:
            dp[h_tmp+1][w_tmp+1] = min(dp[h_tmp][w_tmp+1],
                                       dp[h_tmp+1][w_tmp])
# print(dp)
print(dp[-1][-1])

Submission status: Wrong Answer

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

h, w = list(map(int, input().split()))

ss = [list(str(input())) for _ in range(h)]

dp = [[100*100 for _ in range(w+1)] for i in range(h+1)]  # dp[h][w]

for i in range(w+1):
    dp[0][i] = 100
for i in range(h+1):
    dp[i][0] = 100

dp[0][1] = 0
dp[1][0] = 0

for h_tmp in range(0, h):
    for w_tmp in range(0, w):
        # print(h_tmp+1, w_tmp+1)
        # print(dp[h_tmp][w_tmp+1], dp[h_tmp+1][w_tmp])

        if ss[h_tmp][w_tmp] == "#":
            dp[h_tmp+1][w_tmp+1] = min(dp[h_tmp][w_tmp+1],
                                       dp[h_tmp+1][w_tmp]) + 1

        else:
            dp[h_tmp+1][w_tmp+1] = min(dp[h_tmp][w_tmp+1],
                                       dp[h_tmp+1][w_tmp])
# print(dp)
print(dp[-1][-1])

Submission status: Wrong Answer

Solution code:
def resolve():
    '''
    code here
    '''
    import collections
    H, W = [int(item) for item in input().split()]

    grid = [[item for item in input()] for _ in range(H)]
    chk_list = []

    for i in range(H):
        for j in range(W):
            if grid[i][j] == '.':
                chk_list.append(i + j)

    num_cunt = collections.Counter(chk_list)
    
    all_list = list(range(H+W-1))
    for k in num_cunt.keys():
        all_list.remove(k)

    if len(all_list) >=2:
            
        cnt = 1
        prev = sorted(all_list)[0]
        for i in sorted(all_list)[1:]:
            if i == prev+1:
                pass
            else:
                cnt += 1

            prev = i
        
    else:
        cnt = len(all_list)

    print(cnt)


if __name__ == "__main__":
    resolve()

Submission status: Wrong Answer

Solution code:
def resolve():
    '''
    code here
    '''
    import collections
    H, W = [int(item) for item in input().split()]

    grid = [[item for item in input()] for _ in range(H)]
    chk_list = []

    for i in range(H):
        for j in range(W):
            if grid[i][j] == '.':
                chk_list.append(i + j)

    num_cunt = collections.Counter(chk_list)
    
    all_list = list(range(H+W-1))
    for k in num_cunt.keys():
        all_list.remove(k)

    print(len(all_list))



if __name__ == "__main__":
    resolve()

Submission status: Wrong Answer

Solution code:
import sys
sys.setrecursionlimit(10**6)
def main():
    h, w = map(int, input().split())
    s = [input() for _ in range(h)]
    dp = [[10**5] * w for _ in range(h)]
    def func(temp, now):
        x, y = now
        if y > h - 1 or x > w - 1:
            return 10**6
        if s[y][x] == "#":
            temp += 1
        if x == w-1 and y == h-1:
            return temp
        if dp[y][x] <= temp:
            return 10**6
        dp[y][x] = temp
        piyo = []
        return min(func(temp, (x + 1, y)), func(temp, (x, y + 1)))
    print(func(0, (0, 0)))
main()

Submission status: Wrong Answer

Solution code:
import sys
sys.setrecursionlimit(10**6) #再帰関数の上限
import math
from copy import copy, deepcopy
from operator import itemgetter
from bisect import bisect_left, bisect, bisect_right#2分探索
#bisect_left(l,x), bisect(l,x)#aはソート済みである必要あり。aの中からx未満の要素数を返す。rightだと以下
from collections import deque 
#deque(l), pop(), append(x), popleft(), appendleft(x)
##listでqueの代用をするとO(N)の計算量がかかってしまうので注意
from collections import Counter#文字列を個数カウント辞書に、
#S=Counter(l),S.most_common(x),S.keys(),S.values(),S.items()
from itertools import accumulate#累積和
#list(accumulate(l))
from heapq import heapify,heappop,heappush
#heapify(q),heappush(q,a),heappop(q) #q=heapify(q)としないこと、返り値はNone
#import fractions#古いatcoderコンテストの場合GCDなどはここからimportする


def input(): return sys.stdin.readline()[:-1]
def printl(li): print(*li, sep="\n")
def argsort(s, return_sorted=False): 
    inds=sorted(range(len(s)), key=lambda k: s[k])
    if return_sorted: return inds, [s[i] for i in inds]
    return inds
def alp2num(c,cap=False): return ord(c)-97 if not cap else ord(c)-65
def num2alp(i,cap=False): return chr(i+97) if not cap else chr(i+65)

def dfs(H,W,L):
    d=0
    c=True
    if L[0][0]==False:
        d=1
        c=False
    q=deque([(d*10000,c)])
    dxs=((0,1),(1,0))
    visited=[False]*10000
    while len(q):
        
        #print(q)
        dxy,c=q.popleft()#ここをpopleftにすると幅優先探索BFSになる
        d,xy=divmod(dxy,10000)
        x,y=divmod(xy,100)
        if visited[xy]: continue
        visited[xy]=True
        if x==H-1 and y==W-1:
            return d
        for dx in dxs:
            nx=x+dx[0]
            ny=y+dx[1]
            if nx>=H or ny>=W:
                continue
            if visited[nx*100+ny]:continue

            if L[nx][ny] or c==False:
                q.appendleft((d*10000+nx*100+ny,True))
            else:
                q.append(((d+1)*10000+nx*100+ny,False))

                


def main():
    mod = 10**9+7
    #w.sort(key=itemgetter(1),reversed=True)  #二個目の要素で降順並び替え

    #N = int(input())
    H,W = map(int, input().split())
    #A = tuple(map(int, input().split())) #1行ベクトル
    L = list(list(input()) for i in range(H)) #改行ベクトル
    #S = tuple(tuple(map(int, input().split())) for i in range(N)) #改行行列
    #Lt=[[True]*H for _ in range(W)]
    for i in range (H):
        for j in range(W):
            if L[i][j]=='#':
                L[i][j]=False
            else:
                L[i][j]=True
            
    ans=dfs(H,W,L)

    print(ans)


if __name__ == "__main__":
    main()

Submission status: Wrong Answer

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

dp = [[0]*(w+1) for i in range(h+1)]
#dp[i][j] = i,jでの最小の操作回数

if grid[0][0] == '#':
    dp[0][0] += 1

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

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

for x in range(1,h):
    for y in range(1,w):
        p = 0
        if grid[x][y] == '#':
            p += 1
        dp[x][y] = p + min(dp[x][y-1], dp[x-1][y])
print(dp[h-1][w-1])
#print(dp)

Submission status: Wrong Answer

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

grid_to_num = {"#":1, ".":0}

blacks[0][0] = grid_to_num[grid[0][0]]
for j in range(1, W):
    blacks[0][j] = blacks[0][j-1] + grid_to_num[grid[0][j]]
for i in range(1, H):
    blacks[i][0] = blacks[i-1][0] + grid_to_num[grid[i][0]]
    for j in range(1, W):
        blacks[i][j] = min(blacks[i][j-1], blacks[i-1][j]) + grid_to_num[grid[i][j]]

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

Submission status: Wrong Answer

Solution code:
#A
H,W = map(int,input().split())
G = [list(str(input())) for _ in range(H)]
inf = float("inf")

dist = [[inf for w in range(W)] for h in range(H)]

if G[0][0] == "#":
    dist[0][0] = 1
else:
    dist[0][0] = 0

for i in range(H):
    for j in range(W):
        if i == 0 and j == 0:
            pass
        elif j == 0:
            dist[i][j] = dist[i-1][j]
            if G[i][j] == "#" and G[i-1][j] != "#":
                dist[i][j]+=1
        elif i == 0:
            dist[i][j] = dist[i][j-1]
            if G[i][j] == "#" and G[i-1][j] != "#":
                dist[i][j]+=1
        else:
            d1 = dist[i-1][j]
            d2 = dist[i][j-1]
            if G[i][j] == "#" and G[i-1][j] != "#":
                d1+=1
            if G[i][j] == "#" and G[i-1][j] != "#":
                d2+=1
            dist[i][j] = min(d1,d2)
        

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

Submission status: Wrong Answer

Solution code:
#A
H,W = map(int,input().split())
G = [list(str(input())) for _ in range(H)]
inf = float("inf")

dist = [[inf for w in range(W)] for h in range(H)]

if G[0][0] == "#":
    dist[0][0] = 1
else:
    dist[0][0] = 0

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

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

Submission status: Wrong Answer

Solution code:
#dpでできないかな？
import sys
input = sys.stdin.readline
sys.setrecursionlimit(10**7)
from collections import Counter, deque
from collections import defaultdict
from itertools import combinations, permutations, accumulate, groupby, product
from bisect import bisect_left,bisect_right
from heapq import heapify, heappop, heappush
from math import floor, ceil,pi,cos,radians,sqrt
from operator import itemgetter
def I(): return int(input())
def MI(): return map(int, input().split())
def LI(): return list(map(int, input().split()))
def LI2(): return [int(input()) for i in range(n)]
def MXI(): return [[LI()]for i in range(n)]
def SI(): return input().rstrip()
def printns(x): print('\n'.join(x))
def printni(x): print('\n'.join(list(map(str,x))))
#inf = 10**17
mod = 10**9 + 7
inf=10**3

h,w=MI()
lis=[[1 for i in range(w+2)] for j in range(h+2)]
for i in range(h):
    s=SI()
    for j in range(w):
        if s[j]==".":
            lis[i+1][j+1]=0
#print(lis)
if lis[0][0]== 1:
    count=0
else:
    count=1
step=[1,0],[0,1]
valis=[[inf for i in range(w+2)] for j in range(h+2)]
valis[1][1]=count
#print(valis)
def dfs(x,y):
    if x==0 or y==0 or x==w+1 or y==h+1:
        return
    else:
        for u,t in step:
            if x+u<=h and y+t<=w:
                valis[x+u][y+t]=min(valis[x+u][y+t],valis[x][y]+lis[x+u][y+t])
                dfs(x+u,y+t)
dfs(1,1)
#print(valis)
print(valis[h][w])

Submission status: Wrong Answer

Solution code:
#dpでできないかな？
import sys
input = sys.stdin.readline
sys.setrecursionlimit(10**7)
from collections import Counter, deque
from collections import defaultdict
from itertools import combinations, permutations, accumulate, groupby, product
from bisect import bisect_left,bisect_right
from heapq import heapify, heappop, heappush
from math import floor, ceil,pi,cos,radians,sqrt
from operator import itemgetter
def I(): return int(input())
def MI(): return map(int, input().split())
def LI(): return list(map(int, input().split()))
def LI2(): return [int(input()) for i in range(n)]
def MXI(): return [[LI()]for i in range(n)]
def SI(): return input().rstrip()
def printns(x): print('\n'.join(x))
def printni(x): print('\n'.join(list(map(str,x))))
#inf = 10**17
mod = 10**9 + 7
inf=10**3

h,w=MI()
lis=[[1 for i in range(w+2)] for j in range(h+2)]
for i in range(h):
    s=SI()
    for j in range(w):
        if s[j]==".":
            lis[i+1][j+1]=0
#print(lis)
if lis[0][0]== 1:
    count=0
else:
    count=1
step=[1,0],[0,1]
valis=[[inf for i in range(w+2)] for j in range(h+2)]
valis[1][1]=count
#print(valis)
def dfs(x,y):
    if x==0 or y==0 or x==w+1 or y==h+1:
        return
    else:
        for u,t in step:
            if x+u<=h and y+t<=w:
                valis[x+u][y+t]=min(valis[x+u][y+t],valis[x][y]+lis[x+u][y+t])
                dfs(x+u,y+t)
dfs(1,1)
print(valis)
print(valis[h][w])

Submission status: Wrong Answer

Solution code:
#dpでできないかな？
import sys
input = sys.stdin.readline
sys.setrecursionlimit(10**7)
from collections import Counter, deque
from collections import defaultdict
from itertools import combinations, permutations, accumulate, groupby, product
from bisect import bisect_left,bisect_right
from heapq import heapify, heappop, heappush
from math import floor, ceil,pi,cos,radians,sqrt
from operator import itemgetter
def I(): return int(input())
def MI(): return map(int, input().split())
def LI(): return list(map(int, input().split()))
def LI2(): return [int(input()) for i in range(n)]
def MXI(): return [[LI()]for i in range(n)]
def SI(): return input().rstrip()
def printns(x): print('\n'.join(x))
def printni(x): print('\n'.join(list(map(str,x))))
#inf = 10**17
mod = 10**9 + 7
inf=10**3

h,w=MI()
lis=[[1 for i in range(w+2)] for j in range(h+2)]
for i in range(h):
    s=SI()
    for j in range(w):
        if s[j]==".":
            lis[i+1][j+1]=0
#print(lis)
if lis[0][0]== 1:
    count=0
else:
    count=1
step=[1,0],[0,1]
valis=[[inf for i in range(w+2)] for j in range(h+2)]
valis[1][1]=count
#print(valis)
def dfs(x,y):
    if x==0 or y==0 or x==w+1 or y==h+1:
        return
    else:
        for u,t in step:
            if x+u<=h and y+t<=w:
                valis[x+u][y+t]=min(valis[x+u][y+t],valis[x][y]+lis[x+u][y+t])
                dfs(x+u,y+t)
dfs(1,1)
#print(valis)
print(valis[w][h])

Submission status: Wrong Answer

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


#def sur(x):
#    res=[]
#    if x+1<=w-1:
#        res.append((x+1,y))
#    if y+1<=h-1:
#        res.append((x,y+1))
#    return res


dp=[[-1]*w for index1 in range(h)]
if s[0][0]=='.':
    dp[0][0]=0
else:
    dp[0][0]=1

for index2 in range(1,w):
    if s[0][index2]=='#':
        dp[0][index2]=dp[0][index2-1]+1
    else:
        dp[0][index2]=dp[0][index2-1]

for index3 in range(1,h):
    if s[index3][0]=='#':
        dp[index3][0]=dp[index3-1][0]+1
    else:
        dp[index3][0]=dp[index3-1][0]



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



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

Submission status: Wrong Answer

Solution code:
from itertools import combinations

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

dp = [[float("inf")] * W for _ in range(H)]
if s[0][0] == "#":
    dp[0][0] = 1
else:
    dp[0][0] = 0

dxdy = [(1, 0), (0, 1)]
for y in range(W):
    for x in range(H):
        for dx, dy in dxdy:
            nx = x + dx
            ny = y + dy
            if nx >= W or ny >= H: continue
            add = 0
            if s[ny][nx] == '#' and s[y][x] == '.': add = 1
            dp[ny][nx] = min(dp[ny][nx], dp[y][x] + add)

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

Submission status: Wrong Answer

Solution code:
from itertools import combinations

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

dp = [[float("inf")] * W for _ in range(H)]
if s[0][0] == ".":
    dp[0][0] = 0
else:
    dp[0][0] = 1

dxdy = [(1, 0), (0, 1)]
for y in range(W):
    for x in range(H):
        for dx, dy in dxdy:
            nx = x + dx
            ny = y + dy
            if nx >= W or ny >= H: continue
            if s[ny][nx] == '#' and s[y][x] == '.':
                dp[ny][nx] = min(dp[ny][nx], dp[y][x] + 1)
            else:
                dp[ny][nx] = dp[y][x]

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

Submission status: Wrong Answer

Solution code:
from itertools import combinations

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

dp = [[float("inf")] * W for _ in range(H)]
if s[0][0] == ".":
    dp[0][0] = 0
else:
    dp[0][0] = 1

dxdy = [(1, 0), (0, 1)]
for y in range(W):
    for x in range(H):
        for dx, dy in dxdy:
            nx = x + dx
            ny = y + dy
            if nx >= W or ny >= H: continue
            if s[ny][nx] == '#' and s[y][x] == '.':
                dp[ny][nx] = min(dp[ny][nx], dp[y][x] + 1)
            else:
                dp[ny][nx] = min(dp[ny][nx], dp[y][x])

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)]
visit = [[float("inf") for _ in range(w)] for _j in range(h)]
visit[0][0] = 0
for i in range(h):
    for j in range(w):
        if i-1 >= 0:
            visit[i][j] = visit[i-1][j]+(s[i][j]!=s[i-1][j])
        if j-1 >= 0:
            visit[i][j] = min(visit[i][j], visit[i][j-1]+(s[i][j]!=s[i][j-1]))
if s[0][0] == s[h-1][w-1]:
    print(visit[h-1][w-1]//2)
else:
    print(visit[h-1][w-1]//2 +1)

Submission status: Wrong Answer

Solution code:
from sys import stdin, stdout

int_in = lambda: int(stdin.readline())
arr_in = lambda: [int(x) for x in stdin.readline().split()]
mat_in = lambda rows: [arr_in() for y in range(rows)]
str_in = lambda: stdin.readline().strip()
out = lambda o: stdout.write("{}\n".format(o))
arr_out = lambda o: out(" ".join(map(str, o)))
bool_out = lambda o: out("YES" if o else "NO")
tests = lambda: range(1, int_in() + 1)


def solve(h, w, matrix):
    dp = [[float("inf") for x in range(w)] for y in range(h)]
    dp[0][0] = 1 if matrix[0][0] == "#" else 0
    for row in range(h):
        for col in range(w):
            dp[row][col] = 1 if matrix[row][col] == "#" else 0
            if row > 0 and col > 0:
                dp[row][col] += min(dp[row-1][col], dp[row][col-1])
            elif row > 0:
                dp[row][col] += dp[row-1][col]
            elif col > 0:
                dp[row][col] += dp[row][col-1]
    return dp[h-1][w-1]


if __name__ == "__main__":
    h, w = arr_in()
    matrix = [str_in() for x in range(h)]
    out(solve(h, w, matrix))

Submission status: Wrong Answer

Solution code:
h, w = map(int, input().split())
s = [input() for _i in range(h)]
visit = [[float("inf") for _ in range(w)] for _j in range(h)]
visit[0][0] = (s[0][0]=="#")
for i in range(h):
    for j in range(w):
        if i-1 >= 0:
            visit[i][j] = min(visit[i][j], visit[i-1][j]+(s[i][j]=="#"))
        if j-1 >= 0:
            visit[i][j] = min(visit[i][j], visit[i][j-1]+(s[i][j]=="#"))
print(visit[h-1][w-1])

Submission status: Wrong Answer

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

before = s[0][0]
ans = [[0 for i in range(w)] for j in range(h)]
for i, row in enumerate(s):
    for j, index in enumerate(row):
        if i == j == 0:
            if before == "#":
                ans[i][j] = 1
        elif i == 0:
            if s[i][j] == s[i][j - 1]:
                ans[i][j] = ans[i][j - 1]
            else:
                ans[i][j] = ans[i][j - 1] + 1
        elif j == 0:
            if s[i][j] == s[i - 1][j]:
                ans[i][j] = ans[i - 1][j]
            else:
                ans[i][j] = ans[i - 1][j] + 1
        else:
            if s[i][j] == s[i - 1][j]:
                a1 = ans[i - 1][j]
            else:
                a1 = ans[i - 1][j] + 1
            if s[i][j] == s[i][j - 1]:
                a2 = ans[i][j - 1]
            else:
                a2 = ans[i][j - 1] + 1
            s[i][j] = min(a1, a2)
        before = index
print(ans[-1][-1])

Submission status: Wrong Answer

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

before = s[0][0]
for i, row in enumerate(s):
    for j, index in enumerate(row):
        if i == j == 0:
            if before == "#":
                s[i][j] = 1
            else:
                s[i][j] = 0
        elif i == 0:
            s[i][j] = s[i][j - 1]
        elif j == 0:
            s[i][j] = s[i - 1][j]
        else:
            s[i][j] = min(s[i - 1][j], s[i][j - 1])
        if index != before:
            s[i][j] += 1
        before = index
print(s[-1][-1])

Submission status: Wrong Answer

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

plus = 0
for i, row in enumerate(s):
    for j, index in enumerate(row):
        if i == j == 0:
            s[i][j] = 0
        elif i == 0:
            s[i][j] = s[i][j - 1]
        elif j == 0:
            s[i][j] = s[i - 1][j]
        else:
            s[i][j] = min(s[i - 1][j], s[i][j - 1])
        if index == "#":
            s[i][j] += 1
print(s[-1][-1])

Submission status: Wrong Answer

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

result=list()
for i in range(h):
    line=list()
    for j in range(w):
        line.append(0)
    result.append(line)
def se(x,y):
    if x==0 and y==0:
        if s[0][0]=="#":
            result[x][y]=1
        else:
            result[x][y]=0
    if x==0:
        if s[x][y-1]!=s[x][y]:
            result[x][y]=result[x][y-1]+1
        else:
            result[x][y]=result[x][y-1]
    if y==0:
        if s[x-1][y]!=s[x][y]:
            result[x][y]=result[x-1][y]+1
        else:
            result[x][y]=result[x-1][y]
    else:
        if s[x][y-1]!=s[x][y]:
            a=result[x][y-1]+1
        else:
            a=result[x][y-1]
        if s[x-1][y]!=s[x][y]:
            b=result[x-1][y]+1
        else:
            b=result[x-1][y]
        result[x][y]=min(a,b)
        
for i in range(h):
    for j in range(w):
        se(i,j)
        
if s[h-1][w-1]=="#":
    result[h-1][w-1]+=1
else:
    pass

print(result)
print(int(result[h-1][w-1]/2))

Submission status: Wrong Answer

Solution code:
h,w=map(int,input().split())
s=list()
for i in range(h):
    line=str(input())
    s.append(line)
    
result=[[0]*w]*h
def se(x,y):
    if x==0 and y==0:
        if s[0][0]=="#":
            result[x][y]=1
        else:
            result[x][y]=0
    if x==0:
        if s[x][y-1]!=s[x][y]:
            result[x][y]=result[x][y-1]+1
        else:
            result[x][y]=result[x][y-1]
    if y==0:
        if s[x-1][y]!=s[x][y]:
            result[x][y]=result[x-1][y]+1
        else:
            result[x][y]=result[x-1][y]
    else:
        if s[x][y-1]!=s[x][y]:
            a=result[x][y-1]+1
        else:
            a=result[x][y-1]
        if s[x-1][y]!=s[x][y]:
            b=result[x-1][y]+1
        else:
            b=result[x-1][y]
        result[x][y]=min(a,b)
        
for i in range(h):
    for j in range(w):
        se(i,j)
        
if s[h-1][w-1]=="#":
    result[h-1][w-1]+=1
else:
    pass
            
print(int(result[h-1][w-1]/2))