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[ny-1][nx] == "#":
                                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[ny][nx-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 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:
#from collections import deque

H, W = map(int, input().split())
leng = 0
mapList=[] #appendのために宣言が必要
while True:
    try:
        mapList.append(input())
        leng+=1
    except:
        break;
        #または、quit(),os.exit()をして止める。
row = len(mapList[0])

#mapNum = []
#temp = []
#for i in range(leng):
#  for j in range(row):
#    if(mapList[i][j] == '.'):
#      temp.append(0)
#    elif(mapList[i][j] == '#'):
#      temp.append(1)
    #print(mapNum[i][j])
#  mapNum.append(temp)
  #print(mapNum[i])
#  temp=[]
#print(mapNum)


#maze = []
h = H - 1
w = W - 1
mini=0
if (h > w):
  mini = h-1
else:
  mini = w-1
score = [mini*2]


def bfs(p, q, count):
  if(mapList[p][q] == '#'):
    count += 1
  if(count>=max(score)):
    return
  if(p == h and q == w):
    #maze.append([p, q])
    score.append(count)
    return
  
  elif(p == h or p == leng):
    bfs(p, q+1, count)
  elif(q == w or q == row):
    bfs(p+1, q, count)
  else:
    bfs(p, q+1, count)
    bfs(p+1, q, count)
  return
#visited[sy][sx] = 0
  

     

#maze = [input() for i in range(R)]
point = [[0]*row for j in range(leng)]
bfs(0, 0, 0)

print(min(score))
#print(ind)
#print(maze[ind])

Submission status: Wrong Answer

Solution code:
import sys
input = sys.stdin.readline
sys.setrecursionlimit(1000000)

H, W = map(int, input().split())
field = ['' for _ in range(H)]
seen = [[False for _ in range(W)] for _ in range(H)]
seen_black = [[False for _ in range(W)] for _ in range(H)]

dx = [0, 1]
dy = [1, 0]
stop = (0, 0)
next_start = (0,0)
def dfs(h, w):
    global stop
    seen[h][w] = True
    for dir in range(2):
        nh = h + dx[dir]
        nw = w + dy[dir]
        
        if nh < 0 or nh >= H or nw < 0 or nw >= W:
            continue
        if field[nh][nw] == '#':
            if nh < stop[0] or nw < stop[0]:continue
            if nh+nw > stop[0]+stop[1]:
                stop = (nh, nw)
            continue
        if seen[nh][nw] == True:
            continue
        dfs(nh, nw)
def dfs_black(h, w):
    global next_start
    seen_black[h][w] = True
    for dir in range(2):
        nh = h + dx[dir]
        nw = w + dy[dir]
        
        if nh < 0 or nh >= H or nw < 0 or nw >= W:
            continue
        if field[nh][nw] == '.':
            if nh < next_start[0] or nw < next_start[0]:continue
            if nh+nw > next_start[0]+next_start[1]:
                next_start = (nh, nw)
            continue
        if seen_black[nh][nw] == True:
            continue
        dfs_black(nh, nw)    

for h in range(H):
    field[h] = input().rstrip("\r\n")

sh, sw, gh, gw = 0, 0, H-1, W-1
ans = 0
is_next = True
if field[sh][sw] == "#":
    is_next = False
else:
    is_next = True

while seen[gh][gw] != True and seen_black[gh][gw] != True:
    if is_next:
        dfs(sh,sw)
        sh, sw = stop
        is_next = False
    else:
        ans += 1
        dfs_black(sh,sw)
        sh, sw = next_start
        is_next = True
print(ans)

Submission status: Wrong Answer

Solution code:
# input
H, W = [int(_) for _ in input().split(' ')]
#cheese = [[float(1) if a=='.' else float('inf') for a in input()] for _ in range(H)]
cheese = [[a for a in input()] for _ in range(H)]
#print(H,W)
#print(cheese)
START = [0,0]
if cheese[0][0]=='#':
    START.append(1)
else:
    START.append(0)

GOAL = [H-1, W-1]

#process
point = []
point.insert(0, START)
minimum = float('inf')
distance = [[float('inf') for i in range(W)] for j in range(H)]

while True:
    #print(point)
    # break condition
    if not minimum==float('inf'):
        length = len(point)
        c = 0
        #print('nuan')
        for i in range(length):
            h_, w_, count_ = point[i-c]
            if (count_>=minimum) or (distance[h_][w_]<=count):
                #print('nyan')
                point.pop(i-c)
                c += 1
    # que has element or not
    if len(point)==0:
        break
    h, w, count = point.pop(0)
    if h==GOAL[0] and w==GOAL[1]:
        if minimum>count:
            minimum = count
        if count==0:
            break
    # embed count to distance
    if distance[h][w]>count:
        distance[h][w] = count    
    # explore
    for i in range(0,2):
        h_, w_, count_ = h + [1,0][i], w + [0,1][i], count  # priority w>h (2<=H, 100>=W)
        if h_>=0 and h_<H and w_>=0 and w_<W:
            if cheese[h_][w_]=='#':
                count_+=1
            point.insert(0, [h_,w_,count_])

print(minimum)

Submission status: Wrong Answer

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

H, W = map(int, input().split())
field = [list(input()) for _ in range(H)]
next_list = []
now_list = [(-1,0)]
ok = "."
cnt = 0
goal = 0
history = set()
history.add((-1,0))
while goal == 0:
    next_list = set()
    for x, y in now_list:
        if x == W-1 and y == H-1:
            goal = 1
            break
        for nx, ny in ((1,0),(0,1)):
            nx += x
            ny += y
            if nx >= W or ny >= H or nx < 0 or ny < 0:
                continue
            if field[ny][nx] == ok:
                next_list.add((nx,ny))
                history.add((nx,ny))
    if goal == 1:
        pass
    elif len(next_list) > 0:
        now_list = list(next_list)
    else:
        if ok == ".":
            now_list = list(history)
            
            cnt += 1
            ok = "#"
        else:
            ok = "."
        history = set()

print(cnt)

Submission status: Wrong Answer

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

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

for i in range(h):
    for j in range(w):
        if i == 0 and j == 0:
            if maze[-1-i][-1-j] == '.':
                dpw[i][j] = 0
                dpb[i][j] = 1
            else:
                dpw[i][j] = 1
                dpb[i][j] = 0
        elif i == 0:
            if maze[-1-i][-1-j] == '.':
                dpw[i][j] = dpw[i][j-1]
                dpb[i][j] = min(dpw[i][j-1]+1, dpb[i][j-1]+1)
            else:
                dpw[i][j] = min(dpw[i][j-1]+1, dpb[i][j-1]+1)
                dpb[i][j] = dpb[i][j-1]
        elif j == 0:
            if maze[-1-i][-1-j] == '.':
                dpw[i][j] = dpw[i-1][j]
                dpb[i][j] = min(dpw[i-1][j]+1, dpb[i-1][j]+1)
            else:
                dpw[i][j] = min(dpw[i-1][j]+1, dpb[i-1][j]+1)
                dpb[i][j] = dpb[i-1][j]
        else:
            if maze[-1-i][-1-j] == '.':
                dpw[i][j] = min(dpw[i-1][j], dpw[i][j-1])
                dpb[i][j] = min(dpw[i-1][j]+1, dpw[i][j-1]+1, dpb[i-1][j]+1, dpb[i][j-1]+1)
            else:
                dpw[i][j] = min(dpw[i-1][j]+1, dpw[i][j-1]+1, dpb[i-1][j]+1, dpb[i][j-1]+1)
                dpb[i][j] = min(dpb[i-1][j], dpb[i][j-1])

print(min(dpw[-1][-1], dpb[-1][-1]+1))

Submission status: Wrong Answer

Solution code:
import copy

h,w = list(map(int,input().split()))
s = []
ss = []

for i in range(h):
    s.append(list(input()))

ss = copy.deepcopy(s)

for i in range(h):
    for j in range(w):
        if i != 0 and j != 0:
            if ss[i-1][j] <= ss[i][j-1]:
                ss[i][j] = ss[i-1][j]
            else:
                ss[i][j] = ss[i][j-1]
        elif i != 0:
            ss[i][j] = ss[i-1][j]
        elif j != 0:
            ss[i][j] = ss[i][j-1]
        else:
            ss[i][j] = 0

        if s[i][j] == "#":
            ss[i][j] = ss[i][j] + 1

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

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.popleft()
        #print(q)
        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()
#for i in range(h):
 #   print(cans[i])
           
print(cans[h-1][w-1]+asd)

Submission status: Wrong Answer

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

w = 0
h = 0
cnt = 1 if A[h][w] == '#' else 0


def ccc(aa, ww):
    white = 0
    black = 0
    for a in aa:
        white += a[ww:].count('.')
        black += a[ww:].count('#')
    return white - black


while True:
    if h == H - 1:
        w += 1
    elif w == W - 1:
        h += 1
    else:
        right = ccc(A[h:], w + 1)
        bottom = ccc(A[h + 1:], w)
        if right > bottom:
            w += 1
        else:
            h += 1

    if A[h][w] == '#':
        cnt += 1

    if w == W - 1 and h == H - 1:
        break

print(cnt)

Submission status: Wrong Answer

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

for i in range(H):
    line = list(input())
    M.append(line)
matrix = np.array(M)




def reverse_row(M):
    col, row = M.shape
    M_c = M.copy()

    for i in range(1, row):
        if M_c[0, i] == ".":
            break
        else:
            M_c[0, i] = "."
    return M_c

def reverse_col(M):
    col, row = M.shape
    M_c = M.copy()

    for i in range(1, col):
        if M_c[i, 0] == ".":
            break
        else:
            M_c[i, 0] = "."
    return M_c

def route(M):
    print(M)
    col, row = M.shape
    print(col, row)
    if row == 1 and col == 1:
        return 0

    elif row == 1:
        if M[1, 0] == ".":
            return route(M[1:, :])
        else:
            M_r = reverse_col(M)
            return route(M_r[1:, :]) + 1

    elif col == 1:
        if M[0, 1] == ".":
            return route(M[:, 1:])
        else:
            M_r = reverse_row(M)
            return route(M_r[:, 1:]) + 1

    elif M[1, 0] == "." and M[0, 1] == ".":
        return min(route(M[1:, :]), route(M[:, 1:]))

    elif M[1, 0] == "." and M[0, 1] == "#":
        M_r = reverse_row(M)
        return min(route(M[1:, :]), route(M_r[:, 1:]) + 1)

    elif M[1, 0] == "#" and M[0, 1] == ".":
        M_r = reverse_col(M)
        return min(route(M_r[1:, :]) + 1, route(M[:, 1:]))

    elif M[1, 0] == "#" and M[0, 1] == "#":
        M_r1 = reverse_row(M)
        M_r2 = reverse_col(M)
        return min(route(M_r2[1:, :]) + 1, route(M_r1[:, 1:]) + 1)

def main():
    if matrix[0, 0] == "#":
        matrix[0, 0] = "."
        M_r1 = reverse_row(matrix)
        M_r2 = reverse_col(matrix)
        ans = min(route(M_r1) + 1, route(M_r2) + 1)
    else:
        ans = route(matrix)

    print(ans)

main()

Submission status: Wrong Answer

Solution code:
h,w=map(int,input().split())
c=[[1000]*w]*h
s=[[+(i=='#') for i in input()] for _ in range(h)]
c[0][0]=s[0][0]
for i in range(h):
  for j in range(w):
    for k,l in [[i-1,j],[i,j-1]]:
      if k<0 or l<0:continue
      if s[i][j]==0:
        c[i][j]=min(c[i][j],c[k][l])
      else:
        if s[k][l]==0:
          c[i][j]=min(c[i][j],c[k][l]+1)
        t=j+1
        if t<w:
          while s[i][t]==1:
            c[i][t]=min(c[i][t],c[i][j])
            t+=1
            if t==w:break
        t=i+1
        if t<h:
          while s[t][j]==1:
            c[t][j]=min(c[t][j],c[i][j])
            t+=1
            if t==h:break
print(c[h-1][w-1])

Submission status: Wrong Answer

Solution code:
H,W = map(int,input().split())
p = []
for i in range(H):
    b = list(input())
    b.append(".")
    p.append(b)

p.append(["."]*(W+1))
c = [[10**9]*(W+1) for i in range(H+1)]

if p[0][0] == ".":
    c[0][0] = 0
else:
    c[0][0] = 1

for i in range(H):
    for j in range(W):
        if p[i+1][j] == ".":
            c[i+1][j] = min(c[i][j],c[i+1][j])
        else:
            c[i+1][j] = min(c[i][j]+1, c[i+1][j])
        if p[i][j+1] == ".":
            c[i][j+1] = min(c[i][j],c[i][j+1])
        else:
            c[i][j+1] = min(c[i][j]+1,c[i][j+1])
  
print(c[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][j] == ".":
                mass[i].append(mas[i][j])
                cnt_i[i] = True
                cnt_j[j] = True
                continue
            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().split())
ls = []
for i in range(h):
    ls.append(list(input()))
ma = [[(10**9)]*w for i in range(h)]
fl =  [[-1]*w for i in range(h)]
if ls[0][0] == "." :
    ma[0][0] = 0
else:
    ma[0][0] =1
    fl[0][0] = 1
delta = [(-1,0),(0,-1)]
for y in range(h):
    for x in range(w):
        for dy,dx in delta:
            if 0<=y+dy<=h-1 and 0<=x+dx<=w-1 :
                if ls[y][x] == ls[y+dy][x+dx]:
                    fl[y][x] = fl[y+dy][x+dx]
                    ma[y][x] = ma[y+dy][x+dx]
                else:
                    fl[y][x] = fl[y+dy][x+dx]*(-1)
                    ma[y][x] = min(ma[y][x],ma[y+dy][x+dx]+max(fl[y][x],0))
print(ma[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 = 10**9
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:
def isWhite(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}')
    point = board[y][x]
    count += blackCount(point)
    if y == (h-1) and x == (w-1):
        return count

    if x < w-1 and isWhite(board[y][x + 1]):
        return dfs(x+1,y,count)
    elif y < h-1 and isWhite(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)]
    # print(board)
    # 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 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] == "#" and (s[1][2] != "#" or s[2][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:
# 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:
H, W = [int(x) for x in input().split()]
S = []

countW = 0

S = [list(map(str, list(input()))) for j in range(H)]

for i in (range(len(S))):
    countW = countW + S[i].count('.')

answer = H + W - countW
answer = answer - 1

if '#' == S[H-1][W-1]:
    answer = answer + 1

print(abs(answer))

Submission status: Wrong Answer

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

s = []
cost = []
for i in range(h):
    items = [1 if i == "#" else 0 for i in list(input())]
    s.append(list(items))
    cost.append(list(items))

for i in range(1, h):
    if s[i-1][0] == 0 and s[i][0] == 1:
        cost[i][0] = cost[i-1][0] + 1
    else:
        cost[i][0] = cost[i-1][0]
for i in range(1, w):
    if s[0][i-1] == 0 and s[0][i] == 1:
        cost[0][i] = cost[0][i-1] + 1
    else:
        cost[0][i] = cost[0][i-1]

for i in range(1, h):
    for j in range(1, w):
        if cost[i-1][j] < cost[i][j-1]:
            if s[i-1][j] == 0 and s[i][j] == 1:
                cost[i][j] = cost[i-1][j] + 1
            else:
                cost[i][j] = cost[i-1][j]
        else:
            if s[i][j-1] == 0 and s[i][j] == 1:
                cost[i][j] = cost[i][j-1] + 1
            else:
                cost[i][j] = cost[i][j-1]

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

Submission status: Wrong Answer

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

def bfs(r, c, count):
    global ans

    # マス目をいい状態にする
    if arr[r][c] == '#':
        count += 1

    # ゴールした場合終了
    if r == H - 1 and c == W - 1 :
        if ans == 0 or count < ans:
            ans = count
        return False

    # 下に進める場合は進む
    if r + 1 < H:
        bfs(r + 1, c, count)
    
    # 右に進める場合は進む
    if c + 1 < W:
        bfs(r, c + 1, count)
    
    return False

bfs(0, 0, 0)
print(ans)

Submission status: Wrong Answer

Solution code:
h,w=map(int,input().split())
l=[]
for _ in range(h):
    s=input()
    l.append([str(c) for c in s])
count=0
#print(l)
for i in range(h):
    for j in range(w):
        if l[i][j]=="." and l[i][min(w-1,j+1)]=="#" and l[min(h-1,i+1)][j]=="#":
            count+=1
if l[0][0]=="#":
    count+=1
if l[h-1][w-1]=="#":
    count+=1
print(count)

Submission status: Wrong Answer

Solution code:
# join 20/03/21
h,w=map(int,input().split())
c=[[100000]*w]*h
s=[[+(i=='#') for i in input()] for _ in range(h)]
c[0][0]=s[0][0]
for i in range(h):
  for j in range(w):
    for k,l in [[i-1,j],[i,j-1]]:
      if i-1<0 or j-1<0:continue
      else:
        if s[i][j]==0:
          c[i][j]=min(c[i][j],c[k][l])
        else:
          if s[k][l]==0:
            c[i][j]=min(c[i][j],c[k][l]+1)
          t=j+1
          if t<w:
            while s[i][t]==1:
              c[i][t]=min(c[i][t],c[i][j])
              t+=1
              if t==w:break
          t=i+1
          if t<h:
            while s[t][j]==1:
              c[t][j]=min(c[t][j],c[i][j])
              t+=1
              if t==h:break
print(c[h-1][w-1])

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:
                if S_cnt[nh][nw] == np.inf:
                    q.append((nh, nw))
                S_cnt[nh][nw] = cnt

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


if __name__ == '__main__':
    solver()

Submission status: Wrong Answer

Solution code:
h,w=map(int,input().split())
c=[[1000]*w]*h
s=[[+(i=='#') for i in input()] for _ in range(h)]
c[0][0]=s[0][0]
for i in range(h):
  for j in range(w):
    for k,l in [[i-1,j],[i,j-1]]:
      if i-1<0 or j-1<0:continue
      else:
        if s[i][j]==0:
          c[i][j]=min(c[i][j],c[k][l])
        else:
          if s[k][l]==0:
            c[i][j]=min(c[i][j],c[k][l]+1)
          t=j+1
          if t<w:
            while s[i][t]==1:
              c[i][t]=min(c[i][t],c[i][j])
              t+=1
              if t==w:break
          t=i+1
          if t<h:
            while s[t][j]==1:
              c[t][j]=min(c[t][j],c[i][j])
              t+=1
              if t==h:break
print(c[h-1][w-1])