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 heapq


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

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

    start_point = (0, 0)
    # goal_point = (H - 1, W - 1)

    queue = []
    heapq.heappush(queue, (start_point, 1))
    heapq.heappush(queue, (start_point, 2))

    tests = ((1, 0), (0, 1))

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

    while queue:
        queue_next = []

        for _ in range(len(queue)):
            (y, x), pdr = heapq.heappop(queue)

            for dy, dx in tests:
                ny = y + dy
                nx = x + dx

                if nx >= W or ny >= H:
                    continue

                ndr = 1 if dy == 1 else 2

                if S[ny][nx] == S[y][x] == "#":
                    if (pdr == 1 and ndr == 1) or (pdr == 2 and ndr == 2):
                        if dp[ny][nx] <= dp[y][x]:
                            continue
                        else:
                            dp[ny][nx] = dp[y][x]
                            heapq.heappush(queue_next, ((ny, nx), ndr))
                    else:
                        if pdr == 1 and ndr == 2:
                            if S[y][x - 1] == "#":
                                if dp[ny][nx] <= dp[y][x]:
                                    continue
                                else:
                                    dp[ny][nx] = dp[y][x]
                                    heapq.heappush(queue_next, ((ny, nx), ndr))
                            else:
                                if dp[ny][nx] <= dp[y][x] + 1:
                                    continue
                                else:
                                    dp[ny][nx] = dp[y][x] + 1
                                    heapq.heappush(queue_next, ((ny, nx), ndr))
                        elif pdr == 2 and ndr == 1:
                            if S[y - 1][x] == "#":
                                if dp[ny][nx] <= dp[y][x]:
                                    continue
                                else:
                                    dp[ny][nx] = dp[y][x]
                                    heapq.heappush(queue_next, ((ny, nx), ndr))
                            else:
                                if dp[ny][nx] <= dp[y][x] + 1:
                                    continue
                                else:
                                    dp[ny][nx] = dp[y][x] + 1
                                    heapq.heappush(queue_next, ((ny, nx), ndr))

                elif S[ny][nx] == ".":
                    if dp[ny][nx] <= dp[y][x]:
                        continue
                    else:
                        dp[ny][nx] = dp[y][x]
                        heapq.heappush(queue_next, ((ny, nx), ndr))

                elif S[y][x] == "." and S[ny][nx] == "#":
                    if dp[ny][nx] <= dp[y][x] + 1:
                        continue
                    else:
                        dp[ny][nx] = dp[y][x] + 1
                        heapq.heappush(queue_next, ((ny, nx), ndr))

        queue = queue_next

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


main()

Submission status: Wrong Answer

Solution code:
import sys
import copy
h,w = map(int,input().split())
C = [list(input()) for i in range(h)]
ans = 0
check = 0
for i in range(h):
    if len(C[i]) == C[i].count('#'):
        check += 1        
if check == h:
    print(1)
    sys.exit()
s = "#"   
dy_dx = [[1,0],[0,1]]
visited1 = [[0 for i in range(w)] for i in range(h)]
def bfs():
    global ans
    global s
    
    queue = []
    visited = copy.deepcopy(visited1)

    queue.append([0,0])
    visited[0][0] = 1
  
    while len(queue) > 0:
        now = queue.pop(0)
        for k in range(2):
            y = now[0]+dy_dx[k][0]
            x = now[1]+dy_dx[k][1]
            if 0 <= y < h and 0 <= x < w:
                if C[y][x] != s and visited[y][x] == 0:
                    visited[y][x] = visited[now[0]][now[1]]+1
                    C[y][x] = s
                    C[now[0]][now[1]] = s
                    queue.append([y,x])
                    
    if visited[h-1][w-1] != 0:
        if s == ".":
          ans += 1
        print(ans)
        sys.exit()
    if s == "#":
      ans += 1
    if s == '#':
      s = "."
    else:
      s = "#"
    bfs()
        
bfs()

Submission status: Wrong Answer

Solution code:
from collections import deque
q = deque()
h,w=map(int,input().split())
global finished 
finished = set()
c=[]
for i in range(h):
    c.append(list(map(str,input())))
cans=[[300 for _ in range(w)] for _ in range(h)]
#print(cans)
q.append([0,0,0])
if c[h-1][w-1]=='#':
    asd=1
else:
    asd=0
c[h-1][w-1]='s'

def check(x,y):
    if 0<=x and x<h:
        if 0<=y and y<w:
            return True
    return False
global ans
ans=1000

def search():
    while (q):
        x,y,count=q.pop()
        #print("DF")
        global ans
        
        if check(x,y)==False :
            continue

        else:
            if c[x][y]=='#':
                if cans[x][y]==300 or count+1<cans[x][y]:
                    cans[x][y]=count+1
                    q.append([x,y+1,count+1])
                    q.append([x+1,y,count+1])
                else:
                    continue
            else:
                if cans[x][y]==300 or count<cans[x][y]:
                    cans[x][y]=count
                    q.append([x,y+1,count])
                    q.append([x+1,y,count])
                else:
                    continue
                #print(ans)
     
search()
           
print(cans[h-1][w-1]+asd)

Submission status: Wrong Answer

Solution code:
import heapq

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

mat=[]
for i in range(H):
  array=[x=='.' for x in input()]
  mat.append(array)
#print(mat)

dist=[]
for i in range(H):
  dist.append([-1]*W)

if mat[0][0]:
  dist[0][0]=0
else:
  dist[0][0]=1
  
for i in range(1,H):
  if mat[i-1][0] and not mat[i][0]:
    dist[i][0]=dist[i-1][0]+1
  else:
    dist[i][0]=dist[i-1][0]
    
for j in range(1,W):
  if mat[0][j-1] and not mat[0][j]:
    dist[0][j]=dist[0][j-1]+1
  else:
    dist[0][j]=dist[0][j-1]+1
    
for i in range(1,H):
  for j in range(1,W):
    if mat[i-1][j] and not mat[i][j]:
      dist1=dist[i-1][j]+1
    else:
      dist1=dist[i-1][j]
    
    if mat[i][j-1] and not mat[i][j]:
      dist2=dist[i][j-1]+1
    else:
      dist2=dist[i][j-1]
      
    dist[i][j]=min(dist1,dist2)
    
print(dist[H-1][W-1])

Submission status: Wrong Answer

Solution code:
from collections import deque
import sys
sys.setrecursionlimit(10 ** 9)
h, w = map(int, input().split())
maze = [[-1 for i in range(w)] for j in range(h)]

INF = h*w
countBlack = [[INF for i in range(w)] for j in range(h)]

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

sx=0
sy=0
queue = deque()
queue.append((sy,sx))
countBlack[sy][sx] = int(maze[0][0]== '#')

while queue:
    y, x = queue.popleft()
    for i,j in [(1,0),(0,1)]:
        ny, nx = y+i, x+j
        if 0 <= nx < w and 0 <= ny < h:
            if countBlack[ny][nx] >= countBlack[y][x]+1:
                if maze[ny][nx] == '#':
                    countBlack[ny][nx] = countBlack[y][x] + 1
                else:
                    countBlack[ny][nx] = countBlack[y][x]
                queue.append((ny, nx))

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

Submission status: Wrong Answer

Solution code:
from collections import deque
h, w = map(int, input().split())
mas = [list(input()) for _ in range(h)]
mass = [[] for _ in range(h)]
cnt_i = [True] * h
cnt_j = [True] * w
for i, row in enumerate(mas):
    for j, v in enumerate(row):
        if i == 0 and j == 0:
            mass[i].append(mas[i][j])
            continue
        if cnt_i[i] or cnt_j[j]:
            mass[i].append(mas[i][j])
            if mas[i][j] == "#":
                cnt_i[i] = False
                cnt_j[j] = False
        else:
            if mas[i-1][j] == mas[i][j-1] == ".":
                mass[i].append(mas[i][j])
            else:
                mass[i].append(".")
inf = 10**9
q = deque([[0, 0]])
depth = [[inf]*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

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

        else:
            if depth[x+1][y] > depth[x][y]:
                depth[x + 1][y] = depth[x][y]
                q.appendleft([x+1, y])

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

        else:
            if depth[x][y+1] > depth[x][y]:
                depth[x][y+1] = depth[x][y]
                q.appendleft([x, y+1])


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

Submission status: Wrong Answer

Solution code:
H, W = map(int, input().rstrip().split())
D = []
for h in range(H):
    D.append(list(input().rstrip()))
# print(*D, sep='\n')
d = {}
for i in range(1, H + W):  # i: total
    for h in range(i):
        if h > H - 1:
            h = H - 1
        w = i - h - 1
        if w > W - 1 or h > H - 1 or w < 0 or h < 0:
            continue
        # print(h, w)
        if (h - 1, w) in d.keys() and (h, w - 1) in d.keys():
            d[(h, w)] = min(d[(h - 1, w)], d[(h, w - 1)])
        elif (h - 1, w) in d.keys():
            d[(h, w)] = d[(h - 1, w)]
        elif (h, w - 1) in d.keys():
            d[(h, w)] = d[(h, w - 1)]
        else:
            d[(h, w)] = 0
        if D[h][w] == '#':
            d[(h, w)] += 1
print(d[(H - 1, W - 1)])

Submission status: Wrong Answer

Solution code:
H, W = map(int, input().split())
a = []
a.append([10**10]*(W+1))
for _ in range(H):
    temp = list(input())
    i = [1 if i == "." else 100000 for i in temp]
    i.append(10**10)
    i.insert(0,10**10)
    a.append(i)
a.append([10**10]*(W+1))

ans = 0

if a[1][1]==100000:
    a[1][1]=1
    ans += 1

if a[H][W]==100000:
    a[H][W]=1
    ans += 1

dp = []
dp.append([10**10]*(W+2))
for _ in range(H):
    i = [0 for i in range(W)]
    i.append(10**10)
    i.insert(0,10**10)
    dp.append(i)
dp.append([10**10]*(W+2))
dp[1][1]=1


cnt = 1
h_temp = 1
w_temp = 1

for i in range(2,H+W):
    if i <= min(H,W):
        cnt += 1
    elif i > max(H,W):
        cnt -= 1
    else:
        cnt = cnt
    if i <= H:
        h_temp += 1
    if i > H:
        w_temp += 1
    
    for j in range(cnt):
        h = h_temp-j
        w = w_temp+j

        dp[h][w] = min(dp[h-1][w]+a[h][w],dp[h][w-1]+a[h][w])

print(ans+int(dp[H][W]/100000))

Submission status: Wrong Answer

Solution code:
import copy
H, W = map(int, input().split())
s = [[0] * W]
minus = 0
tmp = [list(input()) for _ in range(H)]
for i in range(H):
    s.append(tmp[i])
if s[1][0] == '#':
    minus = 1
    for i in range(W):
        s[0][i] = 1
else:
    s[0][0] = 0

scopy = copy.deepcopy(s)
for i in range(1, H + 1):
    for j in range(W):
        if s[i][j] == '#':
            if j != 0 and i == 1:
                s[i][j] = s[i][j - 1] + 1
            elif j != 0:
                s[i][j] = min(s[i - 1][j] + 1, s[i][j - 1] + 1)
            else:
                s[i][j] = s[i - 1][j] + 1
            for k in range(i, H + 1):
                if k == i:
                    for l in range(j, W):
                        if l == j: continue
                        if s[k][l] != '.':
                            s[k][l] = s[i][j]
                        else:
                            break
                else:
                    if s[k][j] != '.':
                        s[k][j] = s[i][j]
                    else:
                        break
        elif s[i][j] == '.':
            index = 0
            if scopy[i][j] == '#':
                index += 1
            if j != 0 and i == 1:
                s[i][j] = s[i][j - 1] + index
            elif j != 0:
                s[i][j] = min(s[i - 1][j] + index, s[i][j - 1] + index)
            else:
                s[i][j] = s[i - 1][j] + index
print(s[-1][-1] - minus)

Submission status: Wrong Answer

Solution code:
import copy
H, W = map(int, input().split())
s = [[0] * W]
minus = 0
tmp = [list(input()) for _ in range(H)]
for i in range(H):
    s.append(tmp[i])
if s[1][0] == '#':
    minus = 1
    for i in range(W):
        s[0][i] = 1
else:
    s[0][0] = 0

scopy = copy.deepcopy(s)
for i in range(1, H + 1):
    for j in range(W):
        if s[i][j] == '#':
            if j != 0 and i == 1:
                s[i][j] = s[i][j - 1] + 1
            elif j != 0:
                s[i][j] = min(s[i - 1][j] + 1, s[i][j - 1] + 1)
            else:
                s[i][j] = s[i - 1][j] + 1
            for k in range(i, H + 1):
                if k == i:
                    for l in range(j, W):
                        if l == j: continue
                        if s[k][l] != '.':
                            s[k][l] = s[i][j]
                        else:
                            break
                else:
                    if s[k][j] != '.':
                        s[k][j] = s[i][j]
                    else:
                        break
        elif s[i][j] == '.':
            index = 0
            if scopy[i][j] == '#':
                index += 1
            if j != 0 and i == 1:
                s[i][j] = s[i][j - 1] + index
            elif j != 0:
                s[i][j] = min(s[i - 1][j] + index, s[i][j - 1] + index)
            else:
                s[i][j] = s[i - 1][j] + index
print(s)
print(s[-1][-1] - minus)

Submission status: Wrong Answer

Solution code:
H,W = map(int,input().split())
A = []
for i in range(H):
    b = list(input())
    A.append(b)
dp = [[10**9 for i in range(W)] for i in range(H)]


if A[0][0] == ".":
    dp[0][0] = 0
else:
    dp[0][0] = 1

p = []
for i in range(H):
    for j in range(W):
        p.append([i,j])

t = 1
i = 0
j = 0
while(True):
    if i < H-1:
        if A[i+1][j] == ".":
            dp[i+1][j] = min(dp[i+1][j],dp[i][j])
        else:
            dp[i + 1][j] = min(dp[i + 1][j], dp[i][j] + 1)
    if j < W-1:
        if A[i][j+1] == ".":
            dp[i][j+1] = min(dp[i][j+1],dp[i][j])
        else:
            dp[i][j+1] = min(dp[i][j+1], dp[i][j]+1)

    i = p[t][0]
    j = p[t][1]
    t += 1
    if i == H-1 and j == W-1:
        break

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

Submission status: Wrong Answer

Solution code:
from bisect import bisect_left as bl, bisect_right as br, insort
import sys
import heapq
# from math import *
from collections import defaultdict as dd, deque
def data(): return sys.stdin.readline().strip()
def mdata(): return map(int, data().split())
# sys.setrecursionlimit(1000000)
mod = 998244353

def dijkstra(h,w):

    dist=[[100000000000000000 for i in range(w)] for j in range(h)]
    dist[0][0]=0
    vis=[[0]*w for i in range(h)];

    s=[]
    heapq.heapify(s)
    heapq.heappush(s,(0 ,0,0));

    while len(s)!=0 :

        wei,x,y = heapq.heappop(s)
        if vis[x][y]==1:
            continue
        vis[x][y] = 1

        for i in mat[x][y]:
            a,b=i
            w = mat[x][y][i]
            if dist[x][y] + w < dist[a][b] :
                dist[a][b] = dist[x][y] + w
                heapq.heappush(s,(dist[a][b],a,b))
    return dist

h,w=mdata()
mat=[[{} for i in range(w)] for j in range(h)]
mat1=[[0 for i in range(w)] for j in range(h)]
for i in range(h):
    l=data()
    for j in range(w):
        mat1[i][j]=l[j]
for i in range(h):
    for j in range(w):
        if j<w-1:
            if mat1[i][j+1]!='#':
                mat[i][j][(i,j+1)]=0
            else:
                mat[i][j][(i,j + 1)] = 10000000
        if i!=h-1:
            if mat1[i+1][j]!='#':
                mat[i][j][(i+1,j)]=0
            else:
                mat[i][j][(i+1,j)] = 10000000
ans=dijkstra(h,w)[h-1][w-1]//10000000
if mat1[0][0]=='#':
    ans+=1
print(ans)

Submission status: Wrong Answer

Solution code:


def isBlack(p):
    if p == "#":
        return True
    else:
        return False

def blackCount(p):
    if p == "#":
        return 1
    else:
        return 0


def dfs(x,y,count):
    global minValue

    # print(f'x=#{x},y=#{y}')
    if y == h or x == w:
        return 0

    point = board[y][x]
    count += blackCount(point)
    if y == (h-1) and x == (w-1):
        return count

    if x < w-1 and not isBlack(board[y][x+1]):
        return dfs(x+1,y,count)
    elif y < h-1 and not isBlack(board[y+1][x]):
        return dfs(x,y+1,count)
    else:
        if x == w-1:
            return dfs(x, y + 1, count)
        elif y == h-1:
            return dfs(x+1,y,count)
        else:
            return dfs(x+1,y+1,count+1)

if __name__=="__main__":
    h, w = [int(x) for x in input().split()]
    board = [list(input()) for _ in range(h)]
    # minValue = h + w
    # q = queue.Queue()
    # q.put((1,1))
    # q.put((2,3))
    # print(q.get())
    print(dfs(0,0,0))

Submission status: Wrong Answer

Solution code:
import sys
import copy
h,w = map(int,input().split())
C = [list(input()) for i in range(h)]
ans = 0
check = 0
for i in range(h):
    if len(C[i]) == C[i].count('#'):
        check += 1        
if check == h:
    print(1)
    sys.exit()
s = "#"   
dy_dx = [[1,0],[0,1]]
visited1 = [[0 for i in range(w)] for i in range(h)]
def bfs():
    global ans
    global s
    
    queue = []
    visited = copy.deepcopy(visited1)

    queue.append([0,0])
    visited[0][0] = 1
  
    while len(queue) > 0:
        now = queue.pop(0)
        for k in range(2):
            y = now[0]+dy_dx[k][0]
            x = now[1]+dy_dx[k][1]
            if 0 <= y < h and 0 <= x < w:
                if C[y][x] != s and visited[y][x] == 0:
                    visited[y][x] = visited[now[0]][now[1]]+1
                    C[y][x] = s
                    C[now[0]][now[1]] = s
                    queue.append([y,x])
                    
        if visited[h-1][w-1] != 0:
            if s == ".":
              ans += 1
            print(ans)
            sys.exit()
    if s == "#":
      ans += 1
    if s == '#':
      s = "."
    else:
      s = "#"
    bfs()
        
bfs()

Submission status: Wrong Answer

Solution code:
import numpy as np
direction = [(0, 1), (1, 0)]


def solver():
    h, w = map(int, input().split())
    S = [list(input()) for _ in range(h)]
    S_cnt = [[np.inf for _ in range(w)] for _ in range(h)]
    if S[0][0] == "#":
        S_cnt[0][0] = 1
    else:
        S_cnt[0][0] = 0

    # q = deque([(0, 0)])
    q = [(0, 0)]
    for ch, cw in q:
        # print(ch, cw)
        for mh, mw in direction:
            nh = ch + mh
            nw = cw + mw
            if nh == h or nw == w:
                continue

            cnt = S_cnt[ch][cw]
            if S[nh][nw] == "#":
                cnt = cnt + 1

            if S_cnt[nh][nw] > cnt:
                S_cnt[nh][nw] = cnt
                q.append((nh, nw))

            # print(S_cnt)
    print(S_cnt[h-1][w-1])


if __name__ == '__main__':
    solver()

Submission status: Wrong Answer

Solution code:
# import bisect
# import heapq
# from copy import deepcopy
from collections import deque

# from collections import Counter
# from itertools import accumulate
# from itertools import permutations
import numpy as np
# import math
# mod = 10**9 + 7


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

s = np.array(s)


def bfs(start):
    seen = [[False] * w for _ in range(h)]
    que = deque()
    que.append(start)
    mx = 0
    lx, ly = start

    while que:
        xy = que.popleft()
        x, y = xy[0], xy[1]
        if sum(xy) >= mx:
            mx = sum(xy)
            lx, ly = x, y
        seen[x][y] = True
        for i, j in ([0, 1], [1, 0]):

            if not (0 <= x + i <= h - 1 and 0 <= y + j <= w - 1) or s[x + i][y + j] == '#':
                continue

            que.append([x + i, y + j])

    return lx, ly

def bfs2(r,c):
    seen = [[False] * w for _ in range(h)]
    que = deque()
    que.append([r,c])
    mx = 0
    lx, ly = r,c

    while que:
        xy = que.popleft()
        x, y = xy[0], xy[1]
        if (x+1-r)*(y+1-c) > mx:
            mx = (x+1-r)*(y+1-c)
            lx, ly = x, y
        seen[x][y] = True
        for i, j in ([0, 1], [1, 0]):

            if not (0 <= x+i <= h - 1 and 0 <= y + j <= w - 1):
                continue

            elif not '.' in s[r:x+i+1, c:y+j+1]:
                x += i
                y += j
                que.append([x,y])
    return lx, ly

r,c = 0,0
count = 0
while 1:
    if count == 0 and s[r][c] == '.':
        r, c = bfs([r, c])
    elif count == 0 and s[r][c] == '#':
        r,c = bfs2(r,c)
        count += 1

    r,c = bfs([r,c])
    if r==h-1 and c==w-1:
        break

    if 0<=r+1<=h-1 and 0<=c<=w-1:
        r,c = bfs2(r+1,c)
        count += 1

    elif 0<=r<=h-1 and 0<=c+1<=w-1:
        r,c = bfs2(r,c+1)
        count += 1


print(count)

Submission status: Wrong Answer

Solution code:
from collections import defaultdict as dd
dp = dd(lambda: dd(int))


def recur(arr, i, j):
    if i in dp.keys():
        if j in dp[i].keys():
            return dp[i][j]
    if i >= h-1 and j >= w-1:
        return int(mat[i][j] == '#')
    if i >= h-1:
        return recur(arr, i, j+1)+int(mat[i][j] == '#')
    if j >= w-1:
        return recur(arr, i+1, j)+int(mat[i][j] == '#')
    dp[i][j] = min(recur(arr, i+1, j)+int(mat[i][j] == '#'), recur(arr, i, j+1)+int(mat[i][j] == '#'))
    return dp[i][j]


h, w = map(int, input().split())
mat = []
for i in range(h):
    mat.append(list(input()))
print(recur(mat, 0, 0))

Submission status: Wrong Answer

Solution code:

#####

import numpy as np
# from numpy import int32, int8
from collections import deque

#####

def getIntList(inp):
	return [int(_) for _ in inp]


from sys import stdin
import sys
sys.setrecursionlimit(10**8)

def getInputs():
	inputs=[]
	for line in stdin:
		line=line.split()
		inputs.append(line)
	return inputs


def travel(colors, h, w, row0, col0, targetColor, flipSize, nextParams: deque, usedRC0: set):
	
	if (row0,col0) in usedRC0: return None
	
# 	print()
# 	print("row0",row0,"col0",col0,"flipSize",flipSize)
	
	visited=np.zeros((h-row0, w-col0), np.bool)
	visited[0,0]=True
	next=set()
	nextUsedRC0=set()
	nextUsedRC0.add((row0,col0))
	for hi in range(row0, h):
		for wi in range(col0, w):
			c=colors[hi,wi]==targetColor
			if hi>0 and visited[hi-1-row0,wi-col0]:
				hwi=(hi,wi)
				if c:
					visited[hi-row0,wi-col0]=True
					if hwi in usedRC0:
						usedRC0.update(nextUsedRC0)
						return None
					nextUsedRC0.add(hwi)
				else:
					next.add(hwi)
			if wi>0 and visited[hi-row0,wi-1-col0]:
				hwi=(hi,wi)
				if c:
					visited[hi-row0,wi-col0]=True
					if hwi in usedRC0:
						usedRC0.update(nextUsedRC0)
						return None
					nextUsedRC0.add(hwi)
				else:
					next.add(hwi)
		if not visited[hi-row0].any(): break
	usedRC0.update(nextUsedRC0)
	
	if visited[h-1-row0,w-1-col0]:
# 		print("found")
		print(flipSize)
		sys.exit(0)
					
# 	print("next",next)
	
	if len(next)==0: return None
	
	if targetColor: nextFlipSize=flipSize+1
	else: nextFlipSize=flipSize
	
# 	next=sorted(next, key=lambda x: -(x[0]+x[1]))
	
	for nrc in next:
		if nrc in usedRC0: continue
		p=(colors, h, w, nrc[0], nrc[1], not targetColor, nextFlipSize)
		nextParams.append(p)


def main(inputs):
	h,w=getIntList(inputs[0])
	colors=np.empty((h,w),np.bool)
	for hi in range(h):
		for wi in range(w):
			colors[hi,wi]=inputs[1+hi][0][wi]=="."


# 	h=20
# 	w=20
# 	np.random.seed(0)
# 	colors=np.random.randint(0,2,(h,w))

# 	from matplotlib import pyplot as plt
# 	for hi in range(h):
# 		for wi in range(w):
# 			plt.annotate(str((hi,wi)), (wi-0.5,hi), color="g")
# 	plt.imshow(colors)
# 	plt.show()
			
# 	print(colors.astype(np.int32))
	
	if colors[0,0]: nextFlipSize=0
	else: nextFlipSize=1
	
	nextParams=deque()
	p=(colors, h, w, 0, 0, colors[0,0], nextFlipSize)
	nextParams.append(p)
	
	usedRC0=set()
	while len(nextParams)>0:
		param=nextParams.popleft()
		travel(*param, nextParams=nextParams, usedRC0=usedRC0)


if __name__=="__main__":
	inputs=getInputs()
# 	inputs=simInputs()
	main(inputs)

Submission status: Wrong Answer

Solution code:
h, w = map(int, input().split())
l = [input() for i in range(h)]
cnt = 0
for j in l:
    j.count(".")
    cnt += 1
print(h * w - cnt)

Submission status: Wrong Answer

Solution code:
h, w = map(int, input().split())
ans = []
for i in range(h):
    ans.append([9999999999] * w)
arr = []
for i in range(h):
    s = list(input())
    arr.append(s)
if arr[0][0] == '#': ans[0][0] = 1
else: ans[0][0] = 0
for i in range(h):
    for j in range(w):
        if i == 0 and j == 0: continue
        if j - 1 >= 0: 
            ans[i][j] = min(ans[i][j], ans[i][j - 1])
        if i - 1 >= 0: ans[i][j] = min(ans[i][j], ans[i - 1][j])
        if arr[i][j] == '#':
            chh = 0
            if j - 1 >= 0:
                if ans[i][j] == ans[i][j - 1]:
                    if arr[i][j - 1] == '.':
                        ans[i][j] -= -1
                        chh = 1
            if i - 1 >= 0:
                if ans[i][j] == ans[i - 1][j]:
                    if chh == 1: 
                        if arr[i - 1][j] == '#': ans[i][j] += -1
                    elif arr[i - 1][j] == '.':
                        ans[i][j] -= -1
print(ans[h - 1][w - 1])

Submission status: Wrong Answer

Solution code:
import sys
import heapq

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

def removeWalls(wallPointH,wallPointW):
  if maze[wallPointH][wallPointW]=="#":
    changeTo = "."
  elif maze[wallPointH][wallPointW]=="1":
    changeTo = "0"
  if maze[wallPointH][wallPointW]=="#" or maze[wallPointH][wallPointW]=="1":
    maze[wallPointH][wallPointW]=changeTo
    if wallPointH+1 <= H-1:
      removeWalls(wallPointH+1,wallPointW)
    if wallPointW+1 <= W-1:
      removeWalls(wallPointH,wallPointW+1)

que = [[0,0,0]]
heapq.heapify(que)
count = 0
      
while que:
  qu = heapq.heappop(que)
  if qu[0]==1:
    heapq.heappush(que, qu)
    count += 1
    for q in que:#いったん"#"の撤去作業を行う
      q[0]=0
      removeWalls(q[1],q[2])
  else:#queの中身にまだ進める場所があるなら
    nowH = qu[1]
    nowW = qu[2]
    if nowH==H-1 and nowW==W-1:#ゴールの場合
      print(count)
      sys.exit()
    else:#それ以外の場合
      #右近傍と下近傍、それぞれマップの中ならqueに格納。
      if nowH+1 <= H-1:
        if maze[nowH+1][nowW]=="#":#queへの登録＆その場所をマーキングして、ほかのルートから踏み込まないようにする
          maze[nowH+1][nowW]=="1"
          heapq.heappush(que, [1,nowH+1,nowW])
        elif maze[nowH+1][nowW]==".":#queへの登録＆その場所をマーキングして、ほかのルートから踏み込まないようにする
          maze[nowH+1][nowW]=="0"
          heapq.heappush(que, [0,nowH+1,nowW])
      if nowW+1 <= W-1:
        if maze[nowH][nowW+1]=="#":#queへの登録＆その場所をマーキングして、ほかのルートから踏み込まないようにする
          maze[nowH][nowW+1]=="1"
          heapq.heappush(que, [1,nowH,nowW+1])
        elif maze[nowH][nowW+1]==".":#queへの登録＆その場所をマーキングして、ほかのルートから踏み込まないようにする
          maze[nowH][nowW+1]=="0"
          heapq.heappush(que, [0,nowH,nowW+1])

Submission status: Wrong Answer

Solution code:
r, c= map(int, input().split())
list = []
for i in range(r):
    st = input()
    tempo = []
    for j in range(c):
        tempo.append(st[j])
    list.append(tempo)
print(len(list[0][0]))
count = 0
if (list[0][0] == '#'):
    count += 1

Submission status: Wrong Answer

Solution code:
import collections

h, w = map(int, input().split())
s = [[" "]*(w+2)]
for _ in range(h):
    s.append([" "] + list(map(str, input())) + [" "])

s.append([" "]*(w+2))

b = [[float("inf")]*(w+2) for _ in range(h+2)]
b[1][1] = 1 if s[1][1] == "#" else 0


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

q = collections.deque([[1, 1]])

while len(q) != 0:
    x, y = q.pop()

    for _dx, _dy in zip(dx, dy):
        nx = x + _dx
        ny = y + _dy

        if b[ny][nx] == float("inf") and s[ny][nx] != " ":
            b[ny][nx] = min(b[ny-1][nx], b[ny][nx-1])
            if s[ny][nx] == "#" and (s[ny-1][nx] != "#" or s[ny][nx-1] != "#"):
                b[ny][nx] += 1

            q.appendleft([nx, ny])

"""
for _b in b:
    print(_b)
"""

print(b[h][w])

Submission status: Wrong Answer

Solution code:
H, W = map(int, input().split())
table = []
for i in range(H):
    table.append([(True if x == "." else False) for x in list(input())])

colormap = [[0 for _ in range(W)] for _ in range(H)]
colormap[0][0] = 0 if table[0][0] else 1

def update(i,j):

    tmp_A = 200
    tmp_B = 200
    
    if 0 < i < H and j < W:
        if table[i-1][j] == table[i][j]:
            tmp_A = colormap[i-1][j]
        else:
            tmp_A = colormap[i-1][j] + 1
        
    if i < H and 0 < j < W:
        if table[i][j-1] == table[i][j]:
            tmp_B = colormap[i][j-1]
        else:
            tmp_B = colormap[i][j-1] + 1
    
    colormap[i][j] = min(tmp_A, tmp_B)

for i in range(H):
    for j in range(W):
        if not(i == 0 and j ==0):
            update(i, j)
    # print(colormap)

# 必要反転回数
plus = 1 if not table[0][0] else 0
print(colormap[H-1][W-1] // 2 + plus)