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:
# 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]
START.append(0)
GOAL = [H-1, W-1]

#process
point = []
point.insert(0, START)
minimum = float('inf')

while True:
    #print(point)
    # break condition
    if not minimum==float('inf'):
        length = len(point)
        c = 0
        for i in range(length):
            if point[i-c][2]>=minimum:
                #print('nyan')
                point.pop(i-c)
                c += 1
    # que has element or not
    if len(point)==0:
        break
    h, w, count = point.pop()
    if h==GOAL[0] and w==GOAL[1]:
        if minimum>count:
            minimum = count
        if count==0:
            break

    # explore
    for i in range(0,2):
        h_, w_, count_ = h + [1,0][i], w + [0,1][i], count
        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 collections

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

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

r = [[-1]*(w+2) for _ in range(h+2)]
r[1][1] = 0

b = [[float("inf")]*(w+2) for _ in range(h+2)]
b[1][1] = 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 r[ny][nx] == -1 and s[ny][nx] != " ":
            b[ny][nx] = min(b[y][x], b[ny-1][nx], b[ny][nx-1])
            if s[ny][nx] == "#":
                b[ny][nx] += 1

            r[ny][nx] = r[y][x] + 1
            q.appendleft([nx, ny])

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

print(b[h][w] + (1 if s[1][1] == "#" else 0))

Submission status: Wrong Answer

Solution code:
from collections import deque

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

ans = 10**9

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

if C[0][0] == "#": 
    stack = deque([[0, 0, 1]])
    visited_list[0][0] = 1
else:
    stack = deque([[0, 0, 0]])
    visited_list[0][0] = 0

def dfs(town, visited_list, stack):
    global ans
    while len(stack) > 0:
        h, w, cnt = stack.pop()
        if h == H-1 and w == W-1 and ans > cnt:
            ans = cnt
            continue
        for j, k in ([1, 0], [0, 1]):
            new_h, new_w = h+j, w+k
            if new_h < 0 or new_h >= H or new_w < 0 or new_w >= W:
                continue
            if  town[new_h][new_w] != "#" and visited_list[new_h][new_w] > cnt:
                visited_list[new_h][new_w] = cnt
                stack.append([new_h, new_w, cnt])
            elif town[new_h][new_w] == "#" and visited_list[new_h][new_w] >= cnt + 1:
                visited_list[new_h][new_w] = cnt + 1
                # print("a " + str(cnt+1))
                stack.append([new_h, new_w, cnt+1])
    return ans

print(dfs(C, visited_list, stack))

Submission status: Wrong Answer

Solution code:
import numpy as np
h, w = map(int, input().split())
s = [input() for _ in range(h)]

dp = np.zeros(h * w).reshape(h, w)

if s[0][0] == "#":
    dp[0][0] = 1
else:
    dp[0][0] = 0
    
for i in range(h - 1):
    if s[i + 1][0] == "." or s[i][0] == s[i + 1][0]:
        dp[i + 1][0] = dp[i][0]
    else:
        dp[i + 1][0] = dp[i][0] + 1
for j in range(w - 1):
    if s[0][j + 1] == "." or s[0][j] == s[0][j + 1]:
        dp[0][j + 1] = dp[0][j]
    else:
        dp[0][j + 1] = dp[0][j] + 1

for i in range(h - 1):
    for j in range(w - 1):
        if s[i + 1][j + 1] == "." or (s[i][j + 1] == s[i + 1][j + 1] and s[i + 1][j + 1] == s[i + 1][j]):
            dp[i + 1][j + 1] = min(dp[i][j + 1], dp[i + 1][j])
        elif s[i][j + 1] == s[i + 1][j + 1] and s[i + 1][j + 1] != s[i + 1][j]:
            dp[i + 1][j + 1] = min(dp[i][j + 1], dp[i + 1][j] + 1)
        elif s[i][j + 1] != s[i + 1][j + 1] and s[i + 1][j + 1] == s[i + 1][j]:
            dp[i + 1][j + 1] = min(dp[i][j + 1] + 1, dp[i + 1][j])
        else:
            dp[i + 1][j + 1] = min(dp[i][j + 1] + 1, dp[i + 1][j] + 1)
    
if s[h - 1][w - 1] == "#" and (dp[h - 2][w - 1] != 1 and dp[h - 2][w - 1] != 1):
    dp[h- 1][w - 1] += 1

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

Submission status: Wrong Answer

Solution code:
print("wakaran")

Submission status: Wrong Answer

Solution code:
H, W = map(int, input().split())
S = []
ans = 0
for i in range(H):
    s = list(input())
    S.append(s)
#横に何回移動したか縦に何回移動したかでDP
dp = [[0 for i in range(W)]for j in range(H)]
#print(dp)
if S[0][0]=='#':
    dp[0][0]=1
if W==2:
    if S[0][1]=='#':
        dp[0][1]=dp[0][0]+1
    else:
        dp[0][1]=dp[0][0]
else:
    for i in range(1, W):
        if S[0][i]=='#':
            dp[0][i]=dp[0][i-1]+1
        else:
            dp[0][i]=dp[0][i-1]
    
if H==2:
    if S[1][0]=='#':
        dp[1][0]=dp[0][0]+1
    else:
        dp[1][0]=dp[0][0]
else:
    for j in range(1, H):
        if S[j][0]=='#':
            dp[j][0]=dp[j-1][0]+1
        else:
            dp[j][0]=dp[j-1][0]
#print(dp)
        
for i in range(1,H):
    for j in range(1,W):
        #print(i,j)
        #print(S[i][j])
        if S[i][j]=='#':
            dp[i][j]=min(dp[i-1][j],dp[i][j-1])+1
            #print(dp)
        else:
            dp[i][j]=min(dp[i-1][j],dp[i][j-1])
            #print(dp)
            
ans = dp[-1][-1]
    
print(ans)

Submission status: Wrong Answer

Solution code:
import math
h,w=map(int,input().split())
s=[]
dp=[]
for i in range(h):
    s.append(input())
    dp.append([1000]*w)
dp[0][0]=0 if s[0][0]=='.' else 1
for i in range(300):
    for j in range(300):
        a=i+1
        if j+1<h and a-j-1<w:
            dp[j+1][a-j-1]=min(dp[j+1][a-j-1],dp[j][a-j-1]+(s[j+1][a-j-1]=='#'))
        if a-j<w and j<h:
            dp[j][a-j]=min(dp[j][a-j],dp[j][a-j-1]+(s[j][a-j]=='#'))
print(dp[-1][-1])

Submission status: Wrong Answer

Solution code:
h,w = map(int,input().split())
s = [list(input()) for _ in range(h)]
dp = [[0 for _ in range(w)] for i in range(h)]
if s[0][0] == "#":
  dp[0][0] = 1
for i in range(1,w):
  if s[0][i] == "#":
    dp[0][i] = dp[0][i-1]+1
  else:
    dp[0][i] = dp[0][i-1]
for i in range(1,h):
  if s[i][0] == "#":
    dp[i][0] = dp[i-1][0]+1
  else:
    dp[i][0] = dp[i-1][0]
for i in range(1,h):
  for j in range(1,w):
    if s[i][j] == "#":
      if s[i-1][j] == "." and s[i][j-1] == ".":
        dp[i][j] = min(dp[i-1][j]+1,dp[i][j-1]+1)
      elif s[i-1][j] == ".":
        dp[i][j] = min(dp[i-1][j]+1,dp[i][j-1])
      elif s[i][j-1] == ".":
        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])
    else:      
      dp[i][j] = min(dp[i-1][j],dp[i][j-1])
#print(dp)
print(dp[-1][-1])

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 = [1, 0, -1, 0]
dy = [0, 1, 0, -1]
stop = (0, 0)
next_start = (0,0)
def dfs(h, w):
    global stop
    seen[h][w] = True
    for dir in range(4):
        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] == '#':
            step = max(stop[0]+stop[1], nh+nw)
            if step != 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(4):
        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] == '.':
            step = max(next_start[0]+next_start[1], nh+nw)
            if step != 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:
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)

route = [lines[H-1][W-1]]
pos = [H-1, W-1]
for _ in range(H+W-2):
  if pos[0] <= 0:
    route.append(lines[pos[0]][pos[1]-1])
    pos[1] -= 1
  elif pos[1] <= 0:
    route.append(lines[pos[0]-1][pos[1]])
    pos[0] -= 1
  elif dp[pos[0]-1][pos[1]] <= dp[pos[0]][pos[1]-1]:
    route.append(lines[pos[0]-1][pos[1]])
    pos[0] -= 1
  else:
    route.append(lines[pos[0]][pos[1]-1])
    pos[1] -= 1

prev_sharp = False
ans = 0
for c in route:
  if c == '#':
    if not prev_sharp:
      ans += 1
      prev_sharp = True
  else:
    prev_sharp = False

print(ans)

Submission status: Wrong Answer

Solution code:
input = raw_input
h, w = map(int, input().split(" "))
gh = h - 1
gw = w - 1

#dot_coords = []
#for hi in range(h):
#    wi = 0
#    for c in input():
#        if c == ".":
#            dot_coords.append((wi, hi))
#        wi += 1
        
maps = [list(input()) for _ in range(h)]
num_maps = [[None for _ in range(w)] for _ in range(h)]

count = 0
def find(sx, sy, cur_cost):
    next_cost_coord = []
    global count
    num_r = 1
    found = False
    routes = [(sx, sy)]
    num_maps[sy][sx] = cur_cost
    count += 1

    pre = False
    if sx == 1 and sy == 1:
        pre = True

    while num_r >= 1 and not found:
        x, y = routes[0]
        routes = routes[1:]
        num_r -= 1

        for nx, ny in [(x+1, y), (x, y+1)]:
            if pre:
                pass
                #print("lennummap", len(num_maps))
                #print(num_maps, ny, nx)
                #print(x, y, nx, ny, num_maps[ny][nx], gw, gh, "routes", routes)

            if nx <= gw and ny <= gh:
                if num_maps[ny][nx] is None:
                    if maps[ny][nx] == ".":
                        num_maps[ny][nx] = cur_cost
                        if nx == gw and ny == gh:
                            found = True
                            return next_cost_coord, found
                        else:
                            routes.append((nx, ny))
                            num_r += 1
                    else:
                        next_cost_coord.append((nx, ny))
    return next_cost_coord, found

cur_coords = [(0, 0)]
if maps[0][0] == ".":
    cur_cost = 0
else:
    cur_cost = 1

while True:   
    #print("cur_cost", cur_cost, "cur_coords", cur_coords)
    next_coords = []
    for sx, sy in cur_coords:
        cur_nc_coord, found = find(sx, sy, cur_cost)
        next_coords += cur_nc_coord
        #print(cur_nc_coord, num_maps)
        found = num_maps[gh][gw] is not None
        if found:
            break
    #print("cur_cost", cur_cost,"num_maps", num_maps)
    if found:
        break
    else:
        #print("test")
        cur_coords = set(next_coords)
        assert len(cur_coords) >= 1
        cur_cost += 1
        #print("cur_cost", cur_cost)

out = num_maps[gh][gw]
print(out)
#print(count)

Submission status: Wrong Answer

Solution code:
from collections import deque
h, w = map(int,input().split())
map = []
for i in range(h):
    map.append(list(input()))
queue = deque()
if map[0][0] == '#':
    queue.append([1,0,0])#[y,x,num]
else:
    queue.append([0,0,0])#[y,x,num]
min = 10**10
while queue:
    num,y,x= queue.popleft()
    if map[y][x] == '#':
        num = num+1
    if y == h-1 and x == w-1:
        if min > num:
            min = num
            continue
    if y+1 < h and num < min:
        queue.append([num,y+1,x])
    if x+1 < w and num < min:
        queue.append([num,y,x+1])
print(min)

Submission status: Wrong Answer

Solution code:
import math
h,w=map(int,input().split())
s=[]
dp=[]
for i in range(h):
    s.append(input())
    dp.append([1000]*w)
dp[0][0]=0 if s[0][0]=='.' else 1
for i in range(h+w-1):
    for j in range(i+1):
        a=i+1
        if j+1<h and a-j-1<w:
            dp[j+1][a-j-1]=min(dp[j+1][a-j-1],dp[j][a-j-1]+(s[j+1][a-j-1]=='#'))
        if a-j<w and j<h:
            dp[j][a-j]=min(dp[j][a-j],dp[j][a-j-1]+(s[j][a-j]=='#'))
print(dp[-1][-1])

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
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 W < 0 or H < 0:
                continue
            if field[ny][nx] == ok:
                next_list.add((nx,ny))
    if goal == 1:
        pass
    elif len(next_list) > 0:
        now_list = list(next_list)
    else:
        if ok == ".":
            cnt += 1
            ok = "#"
        else:
            ok = "."


print(cnt)

Submission status: Wrong Answer

Solution code:
H, W = map(int, input().split())
fields = []


def black_white(x):
    if x == '.':  # 白ならば1
        return 1
    elif x == '#':
        return -1  # 黒ならば-1


for i in range(H):
    fields.append(list(map(black_white, list(input()))))

if fields[0][0] == -1:
    cnt = 1
else:
    cnt = 0
positions = [(0, 0, cnt)]
cnts = []
max_r = 0
max_c = 0
min_cnt = 0
while len(positions) > 0:
    r, c, cnt = positions.pop()
    if r == H-1 and c == W-1:
        cnts.append(cnt)
        continue
    elif r < max_r and c < max_c and cnt > min_cnt:
        continue
    if r == H-1:
        pass
    elif r+1 <= H-1 and fields[r+1][c] == 1:
        tmp_r = r + 1
        while tmp_r+1 <= H-1 and fields[tmp_r+1][c] == 1:
            tmp_r += 1
        positions.append((tmp_r, c, cnt))
        max_r = max(tmp_r, max_r)
    elif r + 1 <= H-1:
        tmp_r = r + 1
        while tmp_r + 1 <= H-1 and fields[tmp_r+1][c] == -1:
            tmp_r += 1
        positions = [(tmp_r, c, cnt+1)] + positions
        max_r = max(tmp_r, max_r)
    if c == W-1:
        continue
    elif c+1 <= W-1 and fields[r][c+1] == 1:
        positions.append((r, c+1, cnt))
        tmp_c = c+1
        while tmp_c+1 <= W-1 and fields[r][tmp_c+1] == 1:
            tmp_c += 1
        positions.append((r, tmp_c, cnt))
        max_c = max(tmp_c, max_c)
    elif c+1 <= W-1:
        tmp_c = c+1
        while tmp_c+1 <= W-1 and fields[r][tmp_c+1] == -1:
            tmp_c += 1
        positions = [(r, tmp_c, cnt+1)] + positions
        max_c = max(tmp_c, max_c)

print(min(cnts))

Submission status: Wrong Answer

Solution code:
from sys import stdin,setrecursionlimit
setrecursionlimit(10**6) 
h,w = map(int,stdin.readline().rstrip().split())
li = [stdin.readline().rstrip() for _ in range(h)]
inf = 10**10
lin = [[0 for i in range(w)]for j in range(h)]
for i in range(h):
    for j in range(w):
        flag = False
        if li[i][j] == "#":
            lin[i][j] += 1
        if i == 0 and j == 0:
            continue
        if j-1 >= 0:
            k = lin[i][j-1]
            if lin[i][j-1] == "#" and lin[i][j] == "#":
                flag = True
        else:
            k = inf
        if i-1 >= 0:
            l = lin[i-1][j]
            if lin[i-1][j] == "#" and lin[i][j] == "#":
                flag = True
        else:
            l = inf
        lin[i][j] += min(k,l)
        if flag:
            lin[i][j] -= 1
print(lin[h-1][w-1])

Submission status: Wrong Answer

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

T = [-1] * H * W
if S[0] == '#':
    T[0] = 1
else:
    T[0] = 0
S[0] = '-'

k = 0
v = T[k]
R = {k:v}

def get_search_address(add):
    p = []
    x = add % W
    y = add // W
    next_x = x+1
    next_y = y+1
    if next_x <= (W-1):
        p.append(W*y+next_x)
    if next_y <= (H-1):
        p.append(W*next_y+x)
    return p

while R:
    k = min(R, key=R.get)
    # print('k:{}'.format(k))
    p = get_search_address(k)
    # print('p:{}'.format(p))
    for n in p:
        # print('n:{}'.format(n))
        if T[n] == -1:
            if S[n] == '-':
                if T[k]+1 < T[n]:
                    T[n] = T[k]+1
            elif S[n] == '#':
                T[n] = T[k]+1
                S[n] = '-'
                R[n] = T[n]
            else:
                T[n] = T[k]
                S[n] = '-'
                R[n] = T[n]
    del R[k]
    # print('R:{}'.format(R))
    # print('T:{}'.format(T))

print(T[H*W-1])

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] == '#': ans[i][j] -= -1
print(ans[h - 1][w - 1])

Submission status: Wrong Answer

Solution code:
def dp(i, j, black='#', memo={}):
    if (i, j, black) in memo:
        return memo[i, j, black]
    elif i < 0 or j < 0:
        return float('inf')
    elif i == 0 and j == 0:
        return 1 if grid[i][j] == black else 0
    elif grid[i][j] == black:
        not_flip = 1 + min(dp(i - 1, j, black, memo), dp(i, j - 1, black, memo))
        if black == '.':
            new = '#'
        else:
            new = '.'
        flip = 1 + min(dp(i - 1, j, new, memo), dp(i, j - 1, new, memo))
        res = min(not_flip, flip)
        memo[i, j, black] = res
        return res
    else:
        res = min(dp(i - 1, j, black, memo), dp(i, j - 1, black, memo))
        memo[i, j, black] = res
        return res


H, W = map(int, input().split())
grid = [[None] * W for _ in range(H)]
for i in range(H):
    for j, x in enumerate(input()):
        grid[i][j] = x

memo = {}
print(min(dp(H - 1, W - 1, '#', memo), 1 + dp(H - 1, W - 1, '.', memo)))

Submission status: Wrong Answer

Solution code:
h,w = map(int, input().split())
s = []
for i in range(h):
  s.append(list(input()))
a = [(0,0)]
n = "."
m = "#"
if s[0][0] == "#":
  ans = 1
  n = "#"
  m = "."
else:
  ans = 0
d = 0
while a != []:
  for i in a:
    t,u = i[0],i[1]
    del a[0]
    if t == h-1 and u == w-1:
      d = 1
      break
    if t < h-1 and u < w-1:
      if s[t+1][u] == n and s[t][u+1] == n:
        a.append((t+1,u))
        a.append((t,u+1))
      elif s[t+1][u] == n and s[t][u+1] == m:
        a.append((t+1,u))
      elif s[t+1][u] == m and s[t][u+1] == n:
        a.append((t,u+1))
      elif len(a) == 0:
        a.append((t,u))
        if n == ".":
          ans += 1
          n,m = "#","."
        else:
          n,m = ".","#"
    elif t < h-1:
      if s[t+1][u] == n:
        a.append((t+1,u))
      elif len(a) == 0:
        a.append((t,u))
        if n == ".":
          ans += 1
          n,m = "#","."
        else:
          n,m = ".","#"
    elif u < w-1:
      if s[t][u+1] == n:
        a.append((t,u+1))
      elif len(a) == 0:
        a.append((t,u))
        if n == ".":
          ans += 1
          n,m = "#","."
        else:
          n,m = ".","#"
  if d == 1:
    break
print(ans)

Submission status: Wrong Answer

Solution code:
import heapq
import sys

import numpy as np

readline = sys.stdin.buffer.readline


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)]
    dp = np.array([[10**9 for _ in range(W)] for _ in range(H)])

    start_point = (0, 0)
    # goal_point = (H - 1, W - 1)
    dr = 0  # 前の進行方向(1,2)

    queue = []
    heapq.heappush(queue, (start_point, dr))

    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 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())

maze = [["#"]*(W+2)]
for i in range(H):
    L = list("#" + input() + "#")
    maze.append(L)
maze.append(["#"]*(W+2))

count = 0

if maze[1][1] == "#":
    count += 1
    
pos = deque()
pos.append([1,1])

while len(pos) > 0:
    x,y = pos.pop()
    print(x,y,count,maze[x][y])
    
    if x == H and y==W :
        if maze[x][y] =="#":
            count += 1
            break
        else:
            break
    
    maze[x][y] = "#"
    
    if maze[x+1][y] != "#":
        pos.append([x+1,y])
    if maze[x][y+1] != "#":
        pos.append([x,y+1])
    if H > x and W > y: 
        if maze[x+1][y] == "#" and maze[x][y+1] == "#":
            count = +1
            pos.append([x+1,y])
            pos.append([x,y+1])
            
        
print(count)

Submission status: Wrong Answer

Solution code:
# from pprint import pprint
h, w = map(int, input().split())

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

for i in range(1, h):
    s[i][0] += s[i-1][0]
for i in range(1, w):
    s[0][i] += s[0][i-1]
# pprint(s)

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

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

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 = [(0,0)]
ok = "."
cnt = 0
goal = 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:
                continue
            if field[ny][nx] == ok:
                next_list.add((nx,ny))
    if goal == 1:
        pass
    elif len(next_list) > 0:
        now_list = list(next_list)
    else:
        if ok == ".":
            cnt += 1
            ok = "#"
        else:
            ok = "."

if field[0][0] == "#":
    cnt += 1

print(cnt)

Submission status: Wrong Answer

Solution code:
dp = list(list(-1 for i in range(100)) for j in range(100))
def solve(l, i, j):
	if i==0 and j==0:
		if l[0][0]=='#':
			return 1
		else:
			return 0
	else:
		if j!=0:
			if dp[i][j-1]==-1:
				dp[i][j-1] = solve(l, i, j-1)
		if i!=0:
			if dp[i-1][j]==-1:
				dp[i-1][j] = solve(l, i-1, j)
		if l[i][j]=='#':
			if(i==0):	
				return(dp[i][j-1]+1)
			if(j==0):	
				return(dp[i-1][j]+1)
			else:
				return(min(dp[i][j-1], dp[i-1][j])+1)
		else:
			if(i==0):	
				return(dp[i][j-1])
			if(j==0):	
				return(dp[i-1][j])
			else:
				return(min(dp[i][j-1], dp[i-1][j]))
from sys import stdin, stdout
h, w = stdin.readline().split()
h = int(h)
w = int(w)
l = [list(input()) for x in range(h)]
print(solve(l, h-1, w-1))

Submission status: Wrong Answer

Solution code:
from sys import stdin,setrecursionlimit
setrecursionlimit(10**6) 
h,w = map(int,stdin.readline().rstrip().split())
li = [stdin.readline().rstrip() for _ in range(h)]
inf = 10**10
lin = [[0 for i in range(w)]for j in range(h)]
for i in range(h):
    for j in range(w):
        if li[i][j] == "#":
            lin[i][j] += 1
        if i == 0 and j == 0:
            continue
        if j-1 >= 0:
            k = lin[i][j-1]
        else:
            k = inf
        if i-1 >= 0:
            l = lin[i-1][j]
        else:
            l = inf
        lin[i][j] += min(k,l)
print(lin[h-1][w-1])

Submission status: Wrong Answer

Solution code:
import sys


scan = sys.stdin.readline  # type: Callable[[], str]


def main():
    h, w = map(int, scan().rstrip().split())
    s = [[0 if e == "." else 1 for e in scan().rstrip()] for _ in range(h)]  # type: List[List[int]]

    cost = [[-1] * w for _ in range(h)]

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

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


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
H,W=map(int,input().split())
table=[[0]*W for i in range(H)]
table2=[[0]*W for i in range(H)]
for i in range(H):
  s=str(input())
  for j in range(W):
    if s[j]=='#':
      table[i][j]=1
    else:
      table2[i][j]=1
for i in range(H):
  for j in range(W):
    if i==0:
      if j==0:
        pass
      else:
        table[i][j]+=table[i][j-1]
        table2[i][j]+=table2[i][j-1]
    else:
      if j>=1:
        x,y=table[i-1][j],table[i][j-1]
        table[i][j]+=min(x,y)
        X,Y=table2[i-1][j],table2[i][j-1]
        table2[i][j]+=min(X,Y)
      else:
        table[i][j]+=table[i-1][j]
        table2[i][j]+=table2[i-1][j]
ans1=table[H-1][W-1]
ans2=table2[H-1][W-1]+1
print(min(ans1,ans2))

Submission status: Wrong Answer

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

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

#print(b)

for i in range(H):
	a[i]=list(input())
#print(a)
    
for j in range(1,W):
	b[0][j]=b[0][j-1]+int(not(a[0][j]==a[0][j-1]))

for i in range(1,H):
	b[i][0]=b[i-1][0]+int(not(a[i-1][0]==a[i][0]))
	for j in range(1,W):
		b[i][j]=min(b[i-1][j]+int(not(a[i-1][j]==a[i][j])),b[i][j-1]+int(not(a[i][j-1]==a[i][j])))
	
print(b[H-1][W-1]/2)

Submission status: Wrong Answer

Solution code:

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

A = []

point = 0
for i in range(H):
    P = input()
    P = list(P)
    if point == 0:
        A.append(P)
    else:
        A.vstack(P)
        
if A[0][0] == '.':
    num = 0
else:
    num = 1
if A[H-1][W-1] == '.':
    o = 1
else:
    num += 1
h = 0
w = 0
if H > W:
    while point <= W-2:
        if A[h+1][w] == '.':
            h += 1
        elif A[h][w+1] == '.':
            w += 1
            point += 1
        else:
            num += 1
            h += 1
            w += 1
            point += 1
    for i in range(H-W):
        if A[i+W][W-1] == '#':
            num +=1
            
elif H < W:
    while point <= H-2:
        if A[h+1][w] == '.':
            h += 1
            point += 1
        elif A[h][w+1] == '.':
            w += 1
            
        else:
            num += 1
            h += 1
            w += 1
            point += 1

    for i in range(H-W):
        if A[i+W][W-1] == '#':
            num +=1
        
else:
    while point <= W-2:
        if A[h+1][w] == '.':
            h += 1
            point += 1
        elif A[h][w+1] == '.':
            w += 1
            point += 1
        else:
            num += 1
            h += 1
            w += 1
            point += 1
print(num)