Problem:


Score : 400 points

Problem Statement

Consider a grid with H rows and W columns of squares. Let (r, c) denote the square at the r-th row from the top and the c-th column from the left.
Each square is painted black or white.

The grid is said to be good if and only if the following condition is satisfied:

From (1, 1), we can reach (H, W) by moving one square right or down repeatedly, while always being on a white square.

Note that (1, 1) and (H, W) must be white if the grid is good.

Your task is to make the grid good by repeating the operation below. Find the minimum number of operations needed to complete the task. It can be proved that you can always complete the task in a finite number of operations.

Choose four integers r_0, c_0, r_1, c_1(1 \leq r_0 \leq r_1 \leq H, 1 \leq c_0 \leq c_1 \leq W). For each pair r, c (r_0 \leq r \leq r_1, c_0 \leq c \leq c_1), invert the color of (r, c) - that is, from white to black and vice versa.

Constraints

2 \leq H, W \leq 100

Input

Input is given from Standard Input in the following format:

H W
s_{11} s_{12} \cdots s_{1W}
s_{21} s_{22} \cdots s_{2W}
 \vdots
s_{H1} s_{H2} \cdots s_{HW}

Here s_{rc} represents the color of (r, c) - # stands for black, and . stands for white.

Output

Print the minimum number of operations needed.

Sample Input 1

3 3
.##
.#.
##.

Sample Output 1

1

Do the operation with (r_0, c_0, r_1, c_1) = (2, 2, 2, 2) to change just the color of (2, 2), and we are done.

Sample Input 2

2 2
#.
.#

Sample Output 2

2

Sample Input 3

4 4
..##
#...
###.
###.

Sample Output 3

0

No operation may be needed.

Sample Input 4

5 5
.#.#.
#.#.#
.#.#.
#.#.#
.#.#.

Sample Output 4

4



Sample input:
3 3
.##
.#.
##.


Sample output:
1

Submission status: Wrong Answer

Solution code:
H, W = 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])


for _ in range(100):
    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],dp[h][w+1]+a[h][w],dp[h+1][w]+a[h][w],dp[h][w])

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

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 (count_>=distance[h_][w_]):
                #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 minimum==START[2]:
            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 heapq
 
h,w=map(int,input().split())
S=[]
for i in range(h):
    S.append(input())
    
visited=[[0]*w for _ in range(h)]
 
q=[(0,0,0)]
 
heapq.heapify(q)
visited=[[0]*w for _ in range(h)]
cnt=0
D=[[0]*w for _ in range(h)]
while q:
    cnt,px,py=heapq.heappop(q)
    D[px][py]=min(cnt,D[px][py])
    if  visited[px][py]==1:
        continue
    visited[px][py]=1

    for x,y in [(1,0),(0,1)]:
        if x+px>=h or y+py>=w:
            continue
        if S[px+x][py+y]!=S[px][py]:
            heapq.heappush(q,(cnt+1,px+x,py+y))
        else:
            heapq.heappush(q,(cnt,px+x,py+y))
if D[h-1][w-1]==0 and S[0][0]=='#':
    print(1)
else:
    print(D[h-1][w-1]+1//2)

Submission status: Wrong Answer

Solution code:
# -*- coding: utf-8 -*-

#############
# Libraries #
#############

import sys
input = sys.stdin.readline

import math
from collections import deque
from fractions import gcd
from functools import lru_cache


#############
# Constants #
#############

MOD = 10**9 +7
INF = float('inf')

#############
# Functions #
#############

######INPUT######
def inputI(): return int(input().strip())
def inputS(): return input().strip()
def inputIL(): return list(map(int,input().split()))
def inputSL(): return list(map(str,input().split()))
def inputILs(n): return list(int(input()) for _ in range(n))
def inputSLs(n): return list(input().strip() for _ in range(n))
def inputILL(n): return [list(map(int, input().split())) for _ in range(n)]
def inputSLL(n): return [list(map(str, input().split())) for _ in range(n)]

#####Inverse#####
def inv(n): return pow(n, MOD-2, MOD)

######Combination######
kaijo_memo = []
def kaijo(n):
  if(len(kaijo_memo) > n):
    return kaijo_memo[n]
  if(len(kaijo_memo) == 0):
    kaijo_memo.append(1)
  while(len(kaijo_memo) <= n):
    kaijo_memo.append(kaijo_memo[-1] * len(kaijo_memo) % MOD)
  return kaijo_memo[n]

gyaku_kaijo_memo = []
def gyaku_kaijo(n):
  if(len(gyaku_kaijo_memo) > n):
    return gyaku_kaijo_memo[n]
  if(len(gyaku_kaijo_memo) == 0):
    gyaku_kaijo_memo.append(1)
  while(len(gyaku_kaijo_memo) <= n):
    gyaku_kaijo_memo.append(gyaku_kaijo_memo[-1] * pow(len(gyaku_kaijo_memo),MOD-2,MOD) % MOD)
  return gyaku_kaijo_memo[n]

def nCr(n,r):
  if(n == r):
    return 1
  if(n < r or r < 0):
    return 0
  ret = 1
  ret = ret * kaijo(n) % MOD
  ret = ret * gyaku_kaijo(r) % MOD
  ret = ret * gyaku_kaijo(n-r) % MOD
  return ret

######Factorization######
def factorization(n):
    arr = []
    temp = n
    for i in range(2, int(-(-n**0.5//1))+1):
        if temp%i==0:
            cnt=0
            while temp%i==0:
                cnt+=1
                temp //= i
            arr.append([i, cnt])
    if temp!=1:
        arr.append([temp, 1])

    if arr==[]:
        arr.append([n, 1])
    return arr

#####LCM#####
def lcm(a, b):
    return a * b // gcd (a, b)

#############
# Main Code #
#############

H,W = inputIL()
s = []
for i in range(H):
  s.append(list(inputS()))

dp = [[INF for __ in range(W)] for ___ in range(H)]

for i in range(H):
  for j in range(W):
    if i==0 and j==0: 
      dp[i][j] = 0
    if i!=0:
      
      if s[i][j] == s[i-1][j]:
        dp[i][j] = min(dp[i-1][j],dp[i][j])
      else:
        dp[i][j] = min(dp[i-1][j]+1,dp[i][j])
    if j!=0:
      if s[i][j] == s[i][j-1]:
        dp[i][j] = min(dp[i][j-1],dp[i][j])
      else:
        dp[i][j] = min(dp[i][j-1]+1,dp[i][j])

if s[0][0] == ".":
  print((dp[-1][-1])//2)
else:
  print((dp[-1][-1]//2+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])

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],dp[h][w+1]+a[h][w],dp[h+1][w]+a[h][w],dp[h][w])

for _ in range(100):
    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],dp[h][w+1]+a[h][w],dp[h+1][w]+a[h][w],dp[h][w])

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

Submission status: Wrong Answer

Solution code:
from collections import deque
h,w = map(int,input().split())
m = []
k = [[-1 for _ in range(w)] for _ in range(h)]
count = 0
cl =[]
for i in range(h):
  m.append(list(input()))

def bfs_w(cx,cy,count,cl,gx,gy,flg,k):
  dx = [0,1]
  dy = [1,0]
  d = deque()
  d.appendleft([cx,cy])
  if flg == 1:
    count += 1
    key = '.'
    flg =0
  else :
    key = '#'
    flg = 1
    
  while d:
    n = d.pop()
    x = n[0]
    y = n[1]

    
    nowhere = 0
    lo = []
    for i in range(2):
      nx = x + dx[i]
      ny = y + dy[i] 

      if(nx == gx and ny == gy and m[ny][nx] != key):
        cl.append(count) 
        break
        
      elif nx < w and ny < h and m[ny][nx] != key:
        if k[ny][nx] >=0 and k[ny][nx] <= count:
          break
        else:
          d.appendleft([nx,ny])
          k[ny][nx] = count
      
      else:
        nowhere += 1
    if nowhere == 2:
      bfs_w(x,y,count,cl,gx,gy,flg,k)  

if m[0][0] == '.':
  bfs_w(0,0,count,cl,w-1,h-1,0,k)
else:
  bfs_w(0,0,count,cl,w-1,h-1,1,k)
  
print(min(cl))

Submission status: Wrong Answer

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

Submission status: Wrong Answer

Solution code:
# -*- coding: utf-8 -*-
import itertools


def change(val):
    # 黒なら1
    if val == '#':
        return 1

    # 白なら0
    return 0


# def calc_root(board):


def main():
    h, w = map(int, input().split())
    board = [[change(s) for s in input()] for i in range(h)]

    cnt = 200
    for move in itertools.product(range(0, 2), repeat=h + w - 2):

        if sum(move) != h - 1:
            continue

        x, y, z = 0, 0, board[0][0]
        temp_root = [(x, y, z)]
        change_cnt = 0
        if board[y][x] == 1:
            change_cnt += 1

        x_cnt = 0
        y_cnt = 0
        sum_x_cnt = 1
        sum_y_cnt = 1
        for hko in move:
            now_z = 0
            # 0なら横移動
            if hko == 0:
                x += 1
                now_z = board[y][x]
                if now_z == 1:
                    x_cnt += 1
                else:
                    x_cnt = 0
                y_cnt = 0
            else:
                y += 1
                now_z = board[y][x]
                if now_z == 1:
                    y_cnt += 1
                else:
                    y_cnt = 0
                x_cnt = 0

            sum_x_cnt = max(sum_x_cnt, x_cnt)
            sum_y_cnt = max(sum_y_cnt, y_cnt)
            z += now_z
            temp_root.append((x, y, z))

        print((move, z, sum_x_cnt, sum_y_cnt))
        cnt = min(cnt, z - sum_x_cnt - sum_y_cnt + 2)

    print(cnt)


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
class Square:
  def __init__(self):
    self.color = '.'
    self.direction = 'None'
    self.x = 0
    
def check(a, b, direction = 'W'):
  target = Square()
  target.color = b.color
  if b.color == '.':
    target.direction = 'None'
    target.x = a.x
  else:
    if a.color == '.':
      # 白→黒
      target.direction = 'ALL'
      target.x = a.x + 1
    else:
      # 黒→黒
      if a.direction == 'ALL' or direction == a.direction:
        target.direction = direction
        target.x = a.x
      else:
        target.direction = 'ALL'
        target.x = a.x + 1        
  return target


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

board = [[Square() for _ in range(W)] for _ in range(H)]

for j in range(H):
  s = list(input())
  for i in range(W):
    board[j][i].color = s[i]
  
"""
None, x -> . : None, x
None, x -> # : ALL, x+1
ALL, x -> # : W, x or H, x
ALL, x -> . : None, x
W, x -> # : ALL, x+1 or W, x
"""

if board[0][0].color == '.':
  board[0][0].direction = 'None'
  board[0][0].x = 0
else:
  board[0][0].direction = 'ALL'
  board[0][0].x = 1

for i in range(1, W):
  board[0][i] = check(board[0][i-1], board[0][i], 'W')

for j in range(1, H):
  board[j][0] = check(board[j-1][0], board[j][0], 'H')
  
for j in range(1, H):
  for i in range(1, W):
    H_status = check(board[j-1][i], board[j][i], 'H')
    W_status = check(board[j][i-1], board[j][i], 'W')
    if H_status.x < W_status.x:
      board[j][i] = H_status
    elif H_status.x > W_status.x:
      board[j][i] = W_status
    else:
      if board[j][i] == '.':
        board[j][i] = H_status
      else:
        H_status.direction = 'ALL'
        board[j][i] = H_status

        
print(board[H-1][W-1].x)

Submission status: Wrong Answer

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

field = []
for i in range(H):
  field.append(list(input()))
  field[i].append('.')

field.append(['.' for i in range(W + 1)])

cnt_field = [[1000 for i in range(W + 1)] for j in range(H + 1)]

# field[0][0]の初期化
if field[0][0] == '.':
  cnt_field[0][0] = 0
else:
  cnt_field[0][0] = 1

# filedの走査
for i in range(1, H + W):
  if i <= H and i <= W:
    cnt = i
    ini_x = i - 1
    ini_y = 0

  elif i > min(H, W) and i < max(H, W):
    if H <= W:
      cnt = H
      ini_x = i - 1
      ini_y = 0
    else:
      cnt = W
      ini_x = W - 1 
      ini_y = i - W
    
  else:
    cnt = min(H, W) - i % max(H, W)
    ini_x = W - 1
    ini_y = i - W


  for j in range(cnt):
    score = cnt_field[ini_y + j][ini_x - j]
    # 右の場合
    if field[ini_y + j][ini_x - j + 1] == '.':
      r_flag = 0
    else:
      r_flag = 1

    if cnt_field[ini_y + j][ini_x - j] + r_flag <= cnt_field[ini_y + j][ini_x - j + 1]:
      cnt_field[ini_y + j][ini_x - j + 1] = cnt_field[ini_y + j][ini_x - j] + r_flag
    
    # 下の場合
    if field[ini_y + j + 1][ini_x - j] == '.':
      d_flag = 0
    else:
      d_flag = 1
    
    if cnt_field[ini_y + j][ini_x - j] + d_flag <= cnt_field[ini_y + j + 1][ini_x - j]:
      cnt_field[ini_y + j + 1][ini_x - j] = cnt_field[ini_y + j][ini_x - j] + d_flag

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

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)]
if C[h-1][w-1] == "#":
  ans += 1
def bfs():
    global ans
    global s
    """
    for i in range(h):
      for j in range(w):
        print(C[i][j],end="")
      print("")
    print("=-------------")
    """
    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:
        
        print(ans)
        sys.exit()
    if s == "#":
      ans += 1
    if s == '#':
      s = "."
    else:
      s = "#"
    bfs()
        
bfs()

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:
# Code for A - Range Flip Find Route
# Use input() to fetch data from STDIN

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

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

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

# init
if S[0, 0] == "#":
    dp[0, 0] = 1
else:
    dp[0, 0] = 0

for i in range(1, W):
    if S[0, i] == "#":
        if S[0, i] == S[0, i-1]:
            dp[0, i] = dp[0, i-1]
        else:
            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] == "#":
        if S[i, 0] == S[i-1, 0]:
            dp[i, 0] = dp[i-1, 0]
        else:
            dp[i, 0] = dp[i-1, 0]+1
    else:
        dp[i, 0] = dp[i-1, 0]

# print(dp)

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

        tmp2 = dp[i, j-1]
        if S[i, j] == "#":
            tmp2 += 1

        # if S[i, j] == "#":
        #     if S[i, j] == S[i, j-1]:
        #         tmp2 = dp[i, j-1]
        #     else:
        #         tmp2 = dp[i, j-1]+1
        # else:
        #     tmp2 = dp[i, j-1]
        # if S[i, 0] == "#":
        #     tmp2 += 1

        dp[i, j] = min(tmp1, tmp2)
# print(dp)
print(dp[-1, -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]-1)

Submission status: Wrong Answer

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

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

R = 0
C = 0

result = 0

if BanList[0][0] == '#':
    BanList[0][0] = '.'
    result += 1

while 'true':
    if R == H - 1 and C == W - 1:
        if BanList[R][C] == '#':
            BanList[R][C] = '.'
            result += 1
        break
    elif R == H - 1:
        if BanList[R][C + 1] == '#':
            BanList[R][C + 1] = '.'
            result += 1
        C += 1
    elif C == W - 1:
        if BanList[R + 1][C] == '#':
            BanList[R + 1][C] = '.'
            result += 1
        R += 1
    elif BanList[R + 1][C] == '.' and BanList[R][C + 1] == '#':
        R += 1
    elif BanList[R + 1][C] == '#' and BanList[R][C + 1] == '.':
        C += 1
    elif BanList[R + 1][C] == '.' and BanList[R][C + 1] == '.':
        if R > C:
            C += 1
        else:
            R += 1
    else:
        Rtmp = R
        Ctmp = C
        tmp = 0
        
        onelimit = -1
        twolimit = -1
        for i in range(C + 1, W):
            if BanList[R][i] == '.':
                onelimit = 1
            if BanList[R + 1][i] == '.':
                twolimit = 1
                if i - C > tmp and onelimit != 1:
                    Rtmp = R + 1
                    Ctmp = i
                    tmp = i - C
                    
            if R + 2 >= H:
                continue
            elif BanList[R + 2][i] == '.':
                if i - C + 1 > tmp and twolimit != 1:
                    Rtmp = R + 2
                    Ctmp = i
                    tmp = i - C + 1
        
        onelimit = -1
        twolimit = -1
        for i in range(R + 1, H):
            if BanList[i][C] == '.':
                onelimit = 1
            if BanList[i][C + 1] == '.':
                twolimit = 1
                if i - R > tmp and onelimit != 1:
                    Rtmp = i
                    Ctmp = C + 1
                    tmp = i - R
                
            if C + 2 >= W:
                continue
            if BanList[i][C + 2] == '.':
                if i - R + 1 > tmp and twolimit != 1:
                    Rtmp = i
                    Ctmp = C + 2
                    tmp = i - R + 1
        if tmp != 0: 
            R = Rtmp
            C = Ctmp
            result += 1
        else:
            if R > C:
                BanList[R][C + 1] = '.'
                C += 1
            else:
                BanList[R + 1][C] = '.'
                R += 1
            result += 1

print(result)

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 < H_END or j < W_END:
        return float('inf')
    elif i == H_END and j == W_END:
        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
queue = [(0, 0)]
seen = {(0, 0)}
while queue:
    new = []
    for i, j in queue:
        if grid[i][j] == '#':
            break
        else:
            i_next = i + 1
            j_next = j + 1
            if i_next < H and (i_next, j) not in seen:
                new.append((i_next, j))
                seen.add((i_next, j))
            if j_next < W and (i, j_next) not in seen:
                new.append((i, j_next))
                seen.add((i, j_next))
    queue = new

res = float('inf')
for H_END, W_END in seen:
    memo = {}
    temp = min(dp(H - 1, W - 1, '#', memo), 1 + dp(H - 1, W - 1, '.', memo))
    res = min(res, temp)
print(res)

Submission status: Wrong Answer

Solution code:
import heapq
 
h,w=map(int,input().split())
S=[]
for i in range(h):
    S.append(input())
    
visited=[[0]*w for _ in range(h)]
 
q=[(0,0,0)]
 
heapq.heapify(q)
visited=[[0]*w for _ in range(h)]
cnt=0
 
while q:
    cnt,px,py=heapq.heappop(q)
    if  visited[px][py]==1:
        continue
    visited[px][py]=1
    if px==h-1 and py==w-1:
        if cnt==0 and S[0][0]=='#':
            print(1)
        elif cnt%2==0:
            print(cnt//2)
        else:
            print(cnt//2+1)
        break
    for x,y in [(1,0),(0,1)]:
        if x+px>=h or y+py>=w:
            continue
        if S[px+x][py+y]!=S[px][py]:
            heapq.heappush(q,(cnt+1,px+x,py+y))
        else:
            heapq.heappush(q,(cnt,px+x,py+y))

Submission status: Wrong Answer

Solution code:
# pythonだとデフォルトの再帰処理回数の上限に引っかかってしまうので、それを変更
import sys
sys.setrecursionlimit(1000000)

def dfs(x, y):
    d[x][y] = 1

    # 移動4方向をループ
    for i in range(4):

        nx = x + dx[i]
        ny = y + dy[i]

        print('nx')
        print(nx)
        print('ny')
        print(ny)

        # nx と ny が範囲内か、行ったことがないか、黒色ではないかを判定
        if 0 <= nx and nx < n and 0 <= ny and ny < m and d[nx][ny] == 0 and c[nx][ny] != "#":
                dfs(nx, ny)
        # else :
        #     count = count + 1
        #         dfs(nx, ny)

n, m = map(int, input().split())
c = [list(input()) for i in range(n)]

# 何回書き換える必要があるか記録
count = 0

# 到達したかどうか（0は未到達、1は到達済み）
d = [[0] * m for i in range(n)]

# 移動する4方向
dx = [1, 0, -1, 0]
dy = [0, 1, 0, -1]

# スタート地点から dfs を始める
for i in range(n):
    for j in range(m):
            dfs(0, 0)

# # ゴール地点に到達したかどうか
# for i in range(n):
#     for j in range(m):
#         if d[n][m] == 1:
#             print("Yes")
#             exit()

# print('d[0][0]')
# print(d[0][0])

if d[n-1][m-1] == 1:
    print(count)
else:
    print("No")

Submission status: Wrong Answer

Solution code:

def search(answer,x,y):
    if x == h-1 and y == w-1:
        ans.append(answer)
                    
    if  0 <= y < w and 0 <= x+1 < h and maze[x+1][y] == "#":
        answer += 1
        search(answer,x+1,y)
        
    elif 0 <= y < w and 0 <= x+1 < h and maze[x+1][y] != "#":
        search(answer,x+1,y)
        
    if 0 <= y+1 < w and 0 <= x < h and maze[x][y+1] == "#":
        answer += 1
        search(answer,x,y+1)
        
    elif 0 <= y+1 < w and 0 <= x < h and maze[x][y+1] != "#":
        search(answer,x,y+1)
                
    
h,w = map(int,input().split())
maze = [list(input()) for _ in range(h)]
answer = 0
if maze[0][0] == "#":
    maze[0][0] = "."
    answer += 1
    
if maze[h-1][w-1] == "#":
    maze[h-1][w-1] = "."
    answer += 1

ans=[]
search(answer,0,0)
answer = h*w
for a in ans:
    if a < answer:
        answer = a

print(answer)

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[h-1-i][w-1-j] == '.':
                dpw[i][j] = 0
                dpb[i][j] = 1
            else:
                dpw[i][j] = 1
                dpb[i][j] = 0
        elif i == 0:
            if maze[h-1-i][w-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[h-1-i][w-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[h-1-i][w-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[h-1][w-1], dpb[h-1][w-1]+1))

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 = "#"   
if C[h-1][w-1] == "#":
    ans += 1
dy_dx = [[1,0],[0,1]]
visited1 = [[0 for i in range(w)] for i in range(h)]
def bfs():
    global ans
    global s
    """
    for i in range(h):
      for j in range(w):
        print(C[i][j],end="")
      print("")
    print("=-------------")
    """
    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:
        print(ans)
        sys.exit()
    if s == "#":
        ans += 1
    if s == '#':
        s = "."
    else:
        s = "#"
    bfs()
        
bfs()