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:
#!/usr/bin/env python3
import sys
import heapq
from collections import deque

def solve(H: int, W: int, s: "List[str]"):
    minScore = 10**16
    def isBlock(x,y):
        return s[y][x] == "#"
    first = isBlock(0,0)
    current = set([(0,0)])
    next = set()
    map = [[None for j in range(H)] for i in range(W)]
    map[0][0] = (1,True) if first else (0,False)
    def addNextIfCan(x,y,prevScore,prevBlock):
        if x >= W or y >= H:
            return
        c = isBlock(x,y)
        next.add((x,y))
        cScore = prevScore + 1 if c and not prevBlock else prevScore
        if map[x][y] == None:
            map[x][y] = (cScore,c)
        if map[x][y][0] > prevScore:
            map[x][y] = (cScore,c)
        elif c and map[x][y][0] == prevScore:
            map[x][y] = (cScore,c)
    while len(current) > 0:
        while len(current) > 0:
            n = current.pop()
            prevScore = map[n[0]][n[1]][0]
            prevBlock = map[n[0]][n[1]][1]
            addNextIfCan(n[0]+1,n[1],prevScore,prevBlock)
            addNextIfCan(n[0],n[1]+1,prevScore,prevBlock)
        current = next
        next = set()
    print(map[W-1][H-1][0])
    return


# Generated by 1.1.6 https://github.com/kyuridenamida/atcoder-tools  (tips: You use the default template now. You can remove this line by using your custom template)
def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    H = int(next(tokens))  # type: int
    W = int(next(tokens))  # type: int
    s = [next(tokens) for _ in range(H)]  # type: "List[str]"
    solve(H, W, s)

if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
h, w = map(int, input().split())
s = [list(input()) for _ in range(h)]
dp = [[float('inf') for i in range(w)] for j in range(h)]
cnt = 0
total = 0
for i in range(w):
    if s[0][i] == '#':
        cnt += 1
        if total == 0:
            total = 1
    dp[0][i] = total
    if s[0][i] == '.':
        if cnt > 0:
            total += 1
            cnt = 0
total = 0
cnt = 0
for i in range(h):
    if s[i][0] == '#':
        cnt += 1
        if total == 0:
            total = 1
    dp[i][0] = total
    if s[i][0] == '.':
        if cnt > 0:
            total += 1
            cnt = 0
for i in range(1,h):
    for j in range(1,w):
        if s[i][j] == '#':
            if s[i-1][j] == '#':
                dp[i][j] = min(dp[i-1][j], dp[i][j-1] + 1)
            if s[i][j-1] == '#':
                dp[i][j] = min(dp[i][j], dp[i][j-1], dp[i-1][j] + 1)
            dp[i][j] = min(dp[i][j], dp[i-1][j] + 1, 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:
# -*- coding: utf-8 -*-

import sys

def input(): return sys.stdin.readline().strip()
def list2d(a, b, c): return [[c] * b for i in range(a)]
def list3d(a, b, c, d): return [[[d] * c for j in range(b)] for i in range(a)]
def list4d(a, b, c, d, e): return [[[[e] * d for j in range(c)] for j in range(b)] for i in range(a)]
def ceil(x, y=1): return int(-(-x // y))
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(N=None): return list(MAP()) if N is None else [INT() for i in range(N)]
def Yes(): print('Yes')
def No(): print('No')
def YES(): print('YES')
def NO(): print('NO')
sys.setrecursionlimit(10 ** 9)
INF = 10 ** 18
MOD = 10 ** 9 + 7

def build_grid(H, W, intv, _type, space=True, padding=False):
    # 入力がスペース区切りかどうか
    if space:
        _input = lambda: input().split()
    else:
        _input = lambda: input()
    _list = lambda: list(map(_type, _input()))
    # 余白の有無
    if padding:
        offset = 1
    else:
        offset = 0
    grid = list2d(H+offset*2, W+offset*2, intv)
    for i in range(offset, H+offset):
        row = _list()
        for j in range(offset, W+offset):
            grid[i][j] = row[j-offset]
    return grid

H, W = MAP()
grid = build_grid(H, W, '*', str, space=0, padding=1)

prevh = list2d(H+2, W+2, 0)
prevw = list2d(H+2, W+2, 0)
for i in range(1, H+1):
    for j in range(W, 0, -1):
        if grid[i][j] == '#':
            prevw[i][j] = prevw[i][j+1] + 1
        else:
            prevw[i][j] = 0
for j in range(1, W+1):
    for i in range(H, 0, -1):
        if grid[i][j] == '#':
            prevh[i][j] = prevh[i+1][j] + 1
        else:
            prevh[i][j] = 0

dp = list2d(H+2, W+2, INF)
dp[1][1] = 0 if grid[1][1] == '.' else 1
for i in range(1, H+1):
    for j in range(1, W+1):
        if grid[i][j+1] == '.':
            dp[i][j+1] = min(dp[i][j+1], dp[i][j])
        elif grid[i][j+1] == '#':
            nxtw = j+1 + prevw[i][j+1] - 1
            nxth = i + prevh[i][nxtw] - 1
            dp[nxth][nxtw] = min(dp[nxth][nxtw], dp[i][j] + 1)
            dp[nxth][nxtw+1] = min(dp[nxth][nxtw+1], dp[i][j] + 1)
            dp[nxth+1][nxtw] = min(dp[nxth+1][nxtw], dp[i][j] + 1)
            nxth = i + prevh[i][j+1] - 1
            nxtw = j+1 + prevw[nxth][j+1] - 1
            dp[nxth][nxtw] = min(dp[nxth][nxtw], dp[i][j] + 1)
            dp[nxth][nxtw+1] = min(dp[nxth][nxtw+1], dp[i][j] + 1)
            dp[nxth+1][nxtw] = min(dp[nxth+1][nxtw], dp[i][j] + 1)
        if grid[i+1][j] == '.':
            dp[i+1][j] = min(dp[i][j+1], dp[i][j])
        elif grid[i+1][j] == '#':
            nxtw = j + prevw[i+1][j] - 1
            nxth = i+1 + prevh[i+1][nxtw] - 1
            dp[nxth][nxtw] = min(dp[nxth][nxtw], dp[i][j] + 1)
            dp[nxth][nxtw+1] = min(dp[nxth][nxtw+1], dp[i][j] + 1)
            dp[nxth+1][nxtw] = min(dp[nxth+1][nxtw], dp[i][j] + 1)
            nxth = i+1 + prevh[i+1][j] - 1
            nxtw = j + prevw[nxth][j] - 1
            dp[nxth][nxtw] = min(dp[nxth][nxtw], dp[i][j] + 1)
            dp[nxth][nxtw+1] = min(dp[nxth][nxtw+1], dp[i][j] + 1)
            dp[nxth+1][nxtw] = min(dp[nxth+1][nxtw], dp[i][j] + 1)
ans = dp[H][W]
print(ans)

Submission status: Wrong Answer

Solution code:
def valid(x, y):
    if 0 <= x < h and 0 <= y < w:
        return True
    return False


def revert_column(arr, t):
    for i in range(h):
        arr[i][t] = ('.', '#')[arr[i][t] == '.']
    return arr


def revert_row(arr, t):
    for i in range(w):
        arr[t][i] = ('.', '#')[arr[t][i] == '.']
    return arr


h, w = map(int, input().split())
mat = []
for i in range(h):
    mat.append(list(input()))
i, j = 0, 0
answer = 0
if mat[i][j] == '#':
    answer = 1
    mat = revert_row(mat, 0)
while i < h and j < w:
    if valid(i+1, j):
        if mat[i+1][j] == '.':
            i += 1
            continue
    if valid(i, j+1):
        if mat[i][j+1] == '.':
            j += 1
            continue
    if i == h-1 and j == w-1:
        break
    answer += 1
    if valid(i, j+1):
        mat = revert_column(mat, j+1)
    elif valid(i+1, j):
        mat = revert_row(mat, i+1)
print(answer)

Submission status: Wrong Answer

Solution code:
import sys
import heapq
sys.setrecursionlimit(100000)

h, w = map(int, input().split())
c = [input() for _ in range(h)]
 
d=[[100000]*w for _ in range(h)]
 
def bfs():
    if c[0][0] == '.':
        que = [(0, (0, 0))]
        heapq.heapify(que)
        d[0][0] = 0
    else:
        que = [(1, (0, 0))]
        heapq.heapify(que)
        d[0][0] = 1
    while len(que):
        _, (qx, qy) = heapq.heappop(que)
        if _ > d[h-1][w-1]:
          return
        for dx,dy in [[1,0], [0,1]]:
            px, py = qx+dx, qy+dy
            if 0<=px<h and 0<=py<w and d[px][py]>d[qx][qy]:
                d[px][py]=min(d[px][py], d[qx][qy] + (c[px][py]=='#'))
                heapq.heappush(que, (d[px][py], (px , py)))
bfs()
print(d[h-1][w-1])

Submission status: Wrong Answer

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

dp = {}


# Y, X, （使った）Count
def rec(y, x, c):
    if (y, x, c) in dp:
        return dp[(y, x, c)]
    if y == h - 1 and x == w - 1:
        if table[y][x] == "#":
            c += 1
        dp[(y, x, c)] = c
        return c
    if y < 0 or h <= y or x < 0 or w <= x:
        print("は？")
        print(10.0 / 0)
    ret = 10**8
    steps = [0, 1, 0]
    for i in range(2):
        next_x, next_y = x + steps[i], y + steps[i + 1]
        if 0 <= next_y < h and 0 <= next_x < w:
            if table[next_y][next_x] == "#":
                ret = min(rec(next_y, next_x, c + 1), ret)
            else:
                ret = min(rec(next_y, next_x, c), ret)
        else:
            continue
    dp[(y, x, c)] = ret
    return ret


print(rec(0, 0, 0))

Submission status: Wrong Answer

Solution code:
H, W = map(int, input().split())
def change(x):
    if x == '#':
        return 1
    else:
        return 0
field = list()
for i in range(H):
    field.append(list(map(change,[i for i in input()])))

vector = [[1, 0], [0, 1]]
check_list = [[0 for _ in range(W)] for i in range(H)]
check_list[0][0] = 1
count_list = [[0 for _ in range(W)] for i in range(H)]
count_list[0][0] = field[0][0]
zahyo_check = [[(0, 0)]]
for i in range(H+W-2):
    zahyo = zahyo_check[i]
    zahyo_kari = list()
    for (y, x) in zahyo:
        for (dy, dx) in vector:
            v = count_list[y][x]
            y_k = y + dy
            x_k = x + dx
            try:
                v += field[y_k][x_k]
                if check_list[y_k][x_k] == 0:
                    count_list[y_k][x_k] = v
                    check_list[y_k][x_k] = 1
                    zahyo_kari.append((y_k, x_k))
                else:
                    if v < count_list[y_k][x_k]:
                        count_list[y_k][x_k] = v
            except:
                pass
    zahyo_check.append(zahyo_kari)

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

Submission status: Wrong Answer

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


q = deque([[0, 0]])
depth = [[-1]*w for _ in range(h)]
visited = [[False]*w for _ in range(h)]
if mass[0][0] == "#":
    depth[0][0] = 1
else:
    depth[0][0] = 0

visited[0][0] = True
while True:
    x, y = q.popleft()
    if x == h-1 and y == w-1:
        break
    if x < h-1:
        if visited[x+1][y]:
            pass
        elif mass[x+1][y] == "#":
            q.append([x+1, y])
            depth[x+1][y] = depth[x][y] + 1
            visited[x+1][y] = True
        else:
            q.appendleft([x+1, y])
            depth[x+1][y] = depth[x][y]
            visited[x+1][y] = True

    if y < w-1:
        if visited[x][y+1]:
            pass
        elif mass[x][y+1] == "#":
            q.append([x, y+1])
            depth[x][y+1] = depth[x][y] + 1
            visited[x][y+1] = True
        else:
            q.appendleft([x, y+1])
            depth[x][y+1] = depth[x][y]
            visited[x][y+1] = True

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

Submission status: Wrong Answer

Solution code:
# coding: utf-8
H,W=map(int,input().split())
MAP=[]
d=[]
INF=10**9

for i in range(H):
    line=list(input())
    MAP.append(line)
    d.append([INF for j in range(W)])

if MAP[0][0]==".":
    d[0][0]=0
else:
    d[0][0]=1

for i in range(H):
    for j in range(W):
        if i==0 and j==0:
            continue
        
        if i!=0 and j!=0:
            if MAP[i][j]==".":
                d[i][j]=min(d[i][j-1],d[i-1][j])
                
            else: 
                if MAP[i][j-1]==MAP[i-1][j]==".":
                    d[i][j]=min(d[i][j-1],d[i-1][j])+1
                    
                elif MAP[i][j-1]==MAP[i-1][j]=="#":
                    d[i][j]=min(d[i][j-1],d[i-1][j])
                    
                elif MAP[i][j-1]==".":
                    d[i][j]=min(d[i][j-1]+1,d[i-1][j])
                    
                elif MAP[i-1][j]==".":
                    d[i][j]=min(d[i][j-1],d[i-1][j]+1)
                    
        elif i==0:
            if MAP[i][j]==".":
                d[i][j]=d[i][j-1]
                
            else: 
                if MAP[i][j-1]==".":
                    d[i][j]=d[i][j-1]+1
                    
                elif MAP[i][j-1]=="#":
                    d[i][j]=d[i][j-1]
                    
                elif MAP[i][j-1]==".":
                    d[i][j]=d[i][j-1]+1
                    
        elif j==0:
            if MAP[i][j]==".":
                d[i][j]=d[i-1][j]
                
            else: 
                if MAP[i-1][j]==".":
                    d[i][j]=d[i-1][j]+1
                    
                elif MAP[i][j-1]=="#":
                    d[i][j]=d[i-1][j]
                    
                elif MAP[i-1][j]==".":
                    d[i][j]=d[i-1][j]+1

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

Submission status: Wrong Answer

Solution code:
H,W=map(int,input().split())
s=[input() for i in range(H)]
m=[[None]*W for i in range(H)]
if s[0][0]==".":
    m[0][0]=0
    t=0
else:
    m[0][0]=1
    t=1
for i in range(1,W):
    if s[0][i-1]!=s[0][i]:
        t+=1
    m[0][i]=t
t=m[0][0]
for i in range(1,H):
    if s[i-1][0]!=s[i][0]:
        t+=1
    m[i][0]=t
for i in range(1,H):
    for j in range(1,W):
        if s[i][j]==s[i-1][j] and s[i][j]==s[i][j-1]:
            m[i][j]=min(m[i-1][j],m[i][j-1])
        elif s[i][j]==s[i-1][j]:
            m[i][j]=m[i-1][j]
        elif s[i][j]==s[i][j-1]:
            m[i][j]=m[i][j-1]
        else:
            m[i][j]=min(m[i-1][j],m[i][j-1])+1
print((m[-1][-1]+1)//2)

Submission status: Wrong Answer

Solution code:
import sys; sys.setrecursionlimit(2147483647); input = sys.stdin.readline
from math import floor, ceil, sqrt, factorial, log
from collections import Counter, defaultdict, deque
from operator import itemgetter
INF = float('inf'); MOD = 10**9+7
def I(): return int(input())
def MI(): return map(int, input().split())
def LI(): return list(MI())
def LIR(n): return [LI() for i in range(n)]
def IS(): return input().rstrip()

def judge(i, j):
    if i+1 == H and j+1 == W:
        if s[i][j] == '.': return 0
        else: return 1
    elif i+1 == H:
        if s[i][j] == '.': return judge(i, j+1)
        else: return judge(i, j+1)+1
    elif j+1 == W:
        if s[i][j] == '.': return judge(i+1, j)
        else: return judge(i+1, j)+1
    else:
        if s[i][j] == '.':
            if s[i+1][j] == '.': return judge(i+1, j)
            elif s[i][j+1] == '.': return judge(i, j+1)
            else: return min(judge(i+1, j)+1, judge(i, j+1)+1)
        else:
            if s[i+1][j] == '.': return judge(i+1, j)
            elif s[i][j+1] == '.': return judge(i, j+1)
            else: return min(judge(i+1, j)+1, judge(i, j+1)+1)
        

H, W = MI()
s = [IS() for i in range(H)]
print(judge(0, 0))

Submission status: Wrong Answer

Solution code:
import numpy as np
H, W = map(int, input().split())

S = [np.array(list(str(input())))=="#" for i in range(H)]
S = np.array(S)

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

dp[0,:] = np.cumsum(S[0,:])
dp[:,0] = np.cumsum(S[:,0])

for i in range(1, H):
    for j in range(1, W):
        if S[i,j] == True:
            dp[i,j]+=1
        dp[i,j]+=min(dp[i-1,j], dp[i,j-1])

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

Submission status: Wrong Answer

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

for i in range(H):
    for j in range(W):
        if i == 0 and j == 0:
            if mas[i][j] == "#":
                ans[i][j] = 1
            else :
                ans[i][j] = 0
        elif i == 0:
            if mas[i][j] =="#":
                ans[i][j] = ans[i][j-1] + 1
            else:
                ans[i][j] = ans[i][j-1]
        elif j == 0:
            if mas[i][j] =="#":
                ans[i][j] = ans[i-1][j] + 1
            else:
                ans[i][j] = ans[i-1][j]
        else:
            if ans[i][j-1] <= ans[i-1][j]:
                if mas[i][j] =="#":
                    ans[i][j] = ans[i][j-1] + 1
                else:
                    ans[i][j] = ans[i][j-1]
            else:
                if mas[i][j] =="#":
                    ans[i][j] = ans[i-1][j] + 1
                else:
                    ans[i][j] = ans[i-1][j]

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

Submission status: Wrong Answer

Solution code:
from collections import deque

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

for ki,i in enumerate(ss):
  mini_g = list()
  for kj,j in enumerate(i):
    a = list()
    if ki != 0:
      a.append((ki-1, kj, 0 if ss[ki][kj] == "." else 1))
    if kj != 0:
      a.append((ki, kj-1, 0 if ss[ki][kj] == "." else 1))
    if ki != h-1:
      a.append((ki+1, kj, 0 if ss[ki][kj] == "." else 1))
    if kj != w-1:
      a.append((ki, kj+1, 0 if ss[ki][kj] == "." else 1))
    mini_g.append(a)
  G.append(mini_g)
   
dist = [[10 ** 9] * w for i in range(h)]
s = [0,0]    
S = deque([s])
T = deque()
dist[0][0] = 0
d = 0
if ss[0][0] == "#":
  d = 1
while S:
  while S:
    i,j = S.popleft()
    for ki,kj,c in G[i][j]:
      if d+c < dist[ki][kj]:
        dist[ki][kj] = d+c
        if c:
          T.append([ki,kj])
        else:
          S.append([ki,kj])
  S,T = T,S
  d += 1

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

Submission status: Wrong Answer

Solution code:
import numpy as np
H, W = map(int, input().split())

S = [np.array(list(str(input())))=="#" for i in range(H)]
S = np.array(S)
print(S)

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

dp[0,:] = np.cumsum(S[0,:])
dp[:,0] = np.cumsum(S[:,0])

for i in range(1, H):
    for j in range(1, W):
        if S[i,j] == True:
            dp[i,j]+=1
        dp[i,j]+=min(dp[i-1,j], dp[i,j-1])

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

Submission status: Wrong Answer

Solution code:
import sys; sys.setrecursionlimit(2147483647); input = sys.stdin.readline
from math import floor, ceil, sqrt, factorial, log
from collections import Counter, defaultdict, deque
from operator import itemgetter
INF = float('inf'); MOD = 10**9+7
def I(): return int(input())
def MI(): return map(int, input().split())
def LI(): return list(MI())
def LIR(n): return [LI() for i in range(n)]
def IS(): return input().rstrip()

def judge(i, j):
    if i+1 == H and j+1 == W:
        if s[i][j] == '.': return 0
        else: return 1
    elif i+1 == H:
        if s[i][j] == '.': return judge(i, j+1)
        else: return judge(i, j+1)+1
    elif j+1 == W:
        if s[i][j] == '.': return judge(i+1, j)
        else: return judge(i+1, j)+1
    else:
        if s[i][j] == '.':
            if s[i+1][j] == '.': return judge(i+1, j)
            elif s[i][j+1] == '.': return judge(i, j+1)
            else: return judge(i+1, j)+1
        else:
            if s[i+1][j] == '.': return judge(i+1, j)
            elif s[i][j+1] == '.': return judge(i, j+1)
            else: return judge(i+1, j)+1
        

H, W = MI()
s = [IS() for i in range(H)]
print(judge(0, 0))

Submission status: Wrong Answer

Solution code:
def main():
    from heapq import heappush, heappop

    NOT_PAINTING = 0
    DOWN = 1
    RIGHT = 2
    BOTH = 3

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

    h = []
    x = int(s[0][0] == '#')
    if x:
        heappush(h, (x, 0, 0, BOTH))
    else:
        heappush(h, (x, 0, 0, NOT_PAINTING))

    while h:
        cnt, r, c, way = heappop(h)
        if r == H - 1 and c == W - 1:
            print(cnt)
            return

        if r < H - 1:
            nr, nc = r + 1, c
            x = int(s[nr][nc] == '#')
            if x:
                if way == BOTH or way == DOWN:
                    heappush(h, (cnt, nr, nc, DOWN))
                else:
                    heappush(h, (cnt + 1, nr, nc, BOTH))
            else:
                heappush(h, (cnt, nr, nc, NOT_PAINTING))
        if c < W - 1:
            nr, nc = r, c + 1
            x = int(s[nr][nc] == '#')
            if x:
                if way == BOTH or way == RIGHT:
                    heappush(h, (cnt, nr, nc, RIGHT))
                else:
                    heappush(h, (cnt + 1, nr, nc, BOTH))
            else:
                heappush(h, (cnt, nr, nc, NOT_PAINTING))


if __name__ == '__main__':
    main()

# import sys
#
# input = sys.stdin.readline
# sys.setrecursionlimit(10 ** 7)
# rstrip()
# int(input())
# map(int, input().split())

Submission status: Wrong Answer

Solution code:
import sys
import heapq
sys.setrecursionlimit(100000)

h, w = map(int, input().split())
c = [input() for _ in range(h)]
 
d=[[100000]*w for _ in range(h)]
 
def bfs():
    if c[0][0] == '.':
        que = [(0, (0, 0))]
        heapq.heapify(que)
        d[0][0] = 0
    else:
        que = [(1, (0, 0))]
        heapq.heapify(que)
        d[0][0] = 1
    while len(que):
        _, (qx, qy) = heapq.heappop(que)
        for dx,dy in [[1,0], [0,1]]:
            px, py = qx+dx, qy+dy
            if 0<=px<h and 0<=py<w and d[px][py]>d[qx][qy]:
                d[px][py]=d[qx][qy] + (c[px][py]=='#')
                heapq.heappush(que, (d[px][py], (px , py)))
bfs()
print(d[h-1][w-1])

Submission status: Wrong Answer

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

dp[0][0] = 1 if lines[0][0] == '#' else 0

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

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

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

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

Submission status: Wrong Answer

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

ans = 0
dp = [[0]*w for i in range(h)]
if masu[0][0] == "#":
    dp[0][0] = 1

for i in range(1,h):
    if masu[i][0] == "#":
        dp[i][0] = dp[i-1][0]+1
    else:
        dp[i][0] = dp[i-1][0]

for j in range(1,w):
    if masu[0][j] == "#":
        dp[0][j] = dp[0][j-1]+1
    else:
        dp[0][j] = dp[0][j-1]


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

Submission status: Wrong Answer

Solution code:
x = 1
y = 1


class Mass:
    def __init__(self):
        self.lines = []
        self.h, self.w = map(int, input().split())
        for x in range(self.h):
            self.lines.append(list(input()))
        self.x = 1
        self.y = 1

    def get_now(self):
        return self.lines[self.y-1][self.x-1]

    def get(self, x_, y_):
        try:
            return self.lines[y_-1][x_-1]
        except Exception:
            return None

    def get_forward(self):
        try:
            return self.lines[self.y-1][self.x]
        except Exception:
            return None

    def get_down(self):
        try:
            return self.lines[self.y][self.x-1]
        except Exception:
            return None

    def nearly_white(self):
        for m in range(0, 101):
            for z in range(0, 101):
                if m == z == 0:
                    continue
                t = self.get(self.x+z, self.y+m)
                if not t:
                    break

                if t == '.':
                    if z >= m:
                        return 'x'
                    return 'y'


mass = Mass()

i = 0

while True:
    if mass.get_now() == "#":
        i += 1

    if mass.get_down() == ".":
        mass.y += 1
        continue
    if mass.get_forward() == ".":
        mass.x += 1
        continue

    if mass.get_down() is None and mass.get_forward() is None:
        break

    if mass.get_down() is None:
        mass.x += 1
        continue
    if mass.get_forward() is None:
        mass.y += 1
        continue

    if mass.nearly_white() == 'x':
        mass.x += 1
        continue
    mass.y += 1

print(i)

Submission status: Wrong Answer

Solution code:
#!/usr/bin/env python3
import sys, math, itertools, collections, bisect
input = lambda: sys.stdin.buffer.readline().rstrip().decode('utf-8')
inf = float('inf') ;mod = 10**9+7
mans = inf ;ans = 0 ;count = 0 ;pro = 1
dydx4 = ((-1,0),(0,-1),(0,1),(1,0))
h,w = map(int,input().split())
S = [input() for i in range(h)]
D = [[inf]*w for i in range(h)]
import heapq
hq = []
# (cost,x,y)

def disktra(g,s):
    n=len(g)
    dist = [inf]*n
    dist[s] = 0
    hq=[]
    heapq.heappush(hq,(dist[s],s))
    while hq:
        cost,u =heapq.heappop(hq)
        if dist[u] < cost:
            continue
        for v,c in g[u]:
            if dist[v] <= dist[u] +c:
                continue
            dist[v] = dist[u] + c
            heapq.heappush(hq,(dist[v],v))
    return dist

hq.append((int(S[0][0] == "#"),0,0))
while hq:
  cost,y,x = heapq.heappop(hq)
  if D[y][x] < cost:continue
  for dy,dx in dydx4:
    nx,ny = x+dx,y+dy
    if not (0 <= ny < h and 0 <= nx < w):continue
    if S[ny][nx] == "." or S[ny][nx] == S[y][x] == "#":
      if D[ny][nx] <= cost:continue
      D[ny][nx] = cost
      heapq.heappush(hq,(cost,ny,nx)) 
    else:
      if D[ny][nx] <= cost + 1:continue
      D[ny][nx] = cost + 1
      heapq.heappush(hq,(cost+1,ny,nx)) 
print(D[h-1][w-1])
# print(*D,sep = "\n")

Submission status: Wrong Answer

Solution code:
import sys
import heapq
sys.setrecursionlimit(100000)

h, w = map(int, input().split())
c = [input() for _ in range(h)]
 
d=[[100000]*w for _ in range(h)]
 
def bfs():
    if c[0][0] == '.':
        que = [(0, (0, 0))]
        heapq.heapify(que)
        d[0][0] = 0
    else:
        que = [(1, (0, 0))]
        heapq.heapify(que)
        d[0][0] = 1
    while len(que):
        _, (qx, qy) = heapq.heappop(que)
        for dx,dy in [[1,0], [0,1]]:
            px, py = qx+dx, qy+dy
            if 0<=px<h and 0<=py<w and d[px][py]>d[qx][qy]:
                d[px][py]=d[qx][qy] + (c[px][py]=='#')
                heapq.heappush(que, (d[px][py], (px , py)))
bfs()
print(d)

Submission status: Wrong Answer

Solution code:
import sys
from collections import deque
input = sys.stdin.readline

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

s = []

for _ in range(H):
    s.append(input().strip())

r = 0
c = 0
now = deque()
now.append([r,c])
if s[0][0] == '#':
    cost = 1
else:
    cost = 0

while True:
    cur = now.popleft()
    r = cur[0]
    c = cur[1]
    if r == H-1 and c == W-1:
        break
    if c < W-1 and s[r][c + 1] == '.':
        now.append([r,c+1])
    if r < H-1 and s[r + 1][c] == '.':
        now.append([r+1,c])
    if now == deque():
        flag = False
        if c < W-1 and s[r][c + 1] == '#':
            cost += 1
            flag = True
            now.append([r,c+1])
        if r < H-1 and s[r + 1][c] == '#':
            if not flag:
                cost += 1
            now.append([r+1,c])

r = 0
c = 0
now = deque()
now.append([r,c])
if s[0][0] == '#':
    cost2 = 1
else:
    cost2 = 0

while True:
    cur = now.popleft()
    r = cur[0]
    c = cur[1]
    if r == H-1 and c == W-1:
        break
    if r < H-1 and s[r + 1][c] == '.':
        now.append([r+1,c])
    if c < W-1 and s[r][c + 1] == '.':
        now.append([r,c+1])
    if now == deque():
        flag = False
        if r < H-1 and s[r + 1][c] == '#':
            cost2 += 1
            flag = True
            now.append([r+1,c])
        if c < W-1 and s[r][c + 1] == '#':
            if not flag:
                cost2 += 1
            now.append([r,c+1])

print(min(cost, cost2))