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 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
    """
    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 s == "#":
      ans += 1               
    if visited[h-1][w-1] != 0:
        
        print(ans)
        sys.exit()
    if s == '#':
      s = "."
    else:
      s = "#"
    bfs()
        
bfs()

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[0][0] == "#":
  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:
h,w = map(int, input().split())
sw = [input() for _ in range(h)]
#sw = list(sw)
print(sw[0])
"""
flag = [0][0]
for :
    if 
"""

Submission status: Wrong Answer

Solution code:
import sys
import re
import heapq


# グラフの初期化
def initialize_graph(node_list_x_name, node_list_y_name, score_list):
    graph = {}
    for node1, node2, cost in zip(node_list_x_name, node_list_y_name, score_list):
        graph = set_new_node(graph, node1, node2)
        graph[node1][node2] = int(cost)
        graph[node2][node1] = int(cost)
    return graph


def set_new_node(graph, node1, node2):
    if not node1 in graph.keys():
        graph[node1] = {}
    if not node2 in graph.keys():
        graph[node2] = {}
    return graph


# ダイクストラ法によって最短経路問題を解く
def solve_by_dijkstra(graph, W, H):
    # ノード毎のSTARTからの最小コスト
    min_dist_dict = {}
    # ノードに最小コストで辿り着く場合の直前のノード
    prev_node_dict = {}
    q = []
    heapq.heappush(q, (0, '0_0'))

    prev_node = ''

    while True:
        # 確定したノードから遷移可能なノードのうち
        # 最小のコストと遷移先ノードをmin_dist_dictとprev_node_dictに設定
        dist, node = heapq.heappop(q)
        min_dist_dict[node] = dist
        prev_node_dict[node] = prev_node
        # もしGOALノードの最小コストが確定したらループを抜ける
        if node == (str(H - 1) + '_' + str(W - 1)):
            return min_dist_dict, prev_node_dict
        prev_node = node
        # 確定したノードから遷移可能なノードについて
        # コストを計算し，キュー(q)に追加する
        culc_min_dist_and_put(graph, q, node, min_dist_dict, prev_node_dict)


def culc_min_dist_and_put(graph, q, departure_node, min_dist_dict, prev_node_dict):
    # 直前に確定したノードから遷移可能なすべてのノードについて繰り返し
    for arrival_node in graph[departure_node].keys():
        # 遷移可能なノードについて，直前に確定したノードから遷移した場合のコストを計算
        tmp_d = min_dist_dict[departure_node] + graph[departure_node][arrival_node]
        # 過去に遷移先ノードの最小コストを計算済みかどうか
        if arrival_node in min_dist_dict.keys():
            # 過去に計算していたSTARTからの最小コストより直前に確定したノードから遷移した場合の
            # コストが小さかった場合，最小コストを更新
            if tmp_d < min_dist_dict[arrival_node]:
                min_dist_dict[arrival_node] = tmp_d
                heapq.heappush(q, (min_dist_dict[arrival_node], arrival_node))
        else:
            min_dist_dict[arrival_node] = tmp_d
            heapq.heappush(q, (min_dist_dict[arrival_node], arrival_node))


def main():
    H, W = map(int, input().split())
    s = [None] * H
    for i in range(H):
        s[i] = input()

    node_list_x1 = [[i, j] for i in range(H - 1) for j in range(W - 1)]
    node_list_x2 = [[H - 1, i] for i in range(W - 1)]
    node_list_x3 = [[i, W - 1] for i in range(H - 1)]

    node_list_y1 = [[i, j + 1] for i in range(H - 1) for j in range(W - 1)]
    node_list_y2 = [[i + 1, j] for i in range(H - 1) for j in range(W - 1)]
    node_list_y3 = [[H - 1, i + 1] for i in range(W - 1)]
    node_list_y4 = [[i + 1, W - 1] for i in range(H - 1)]

    node_list_x = node_list_x1 * 2 + node_list_x2 + node_list_x3
    node_list_y = node_list_y1 + node_list_y2 + node_list_y3 + node_list_y4

    score_list = []
    for x, y in zip(node_list_x, node_list_y):
        if s[x[0]][x[1]] == s[y[0]][y[1]]:
            score_list.append(0)
        else:
            score_list.append(1)

    node_list_x_name = [str(x[0]) + '_' + str(x[1]) for x in node_list_x]
    node_list_y_name = [str(y[0]) + '_' + str(y[1]) for y in node_list_y]

    graph = initialize_graph(node_list_x_name, node_list_y_name, score_list)
    min_dist_dict, prev_node_dict = solve_by_dijkstra(graph, W, H)
    # GOALノードからprev_node_dictをたどって経路を復元
    # print('Route : H_W ', end='')
    node = (str(H - 1) + '_' + str(W - 1))
    while True:
        if node == '0_0':
            print()
            break
        # print(' ← ' + prev_node_dict[node], end='')
        node = prev_node_dict[node]

    if W == 1 or H == 1:
        if s[0][0] == '.':
            print(str(min_dist_dict[(str(H - 1) + '_' + str(W - 1))] - 1))
        else:
            print(str(min_dist_dict[(str(H - 1) + '_' + str(W - 1))]))
    else:
        if s[0][0] == '.':
            if min_dist_dict[(str(H - 1) + '_' + str(W - 1))] == 0:
                print(0)
            else:
                print(str(min(H, W, min_dist_dict[(str(H - 1) + '_' + str(W - 1))]) - 1))
        else:
            print(str(min(H, W, min_dist_dict[(str(H - 1) + '_' + str(W - 1))])))


if __name__ == '__main__':
    main()
    sys.exit(0)

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

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
    """
    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:
        if s == "#" and C[h-1][w-1] == "#":
          ans += 1
        print(ans)
        sys.exit()
    if s == "#":
      ans += 1
    if s == '#':
      s = "."
    else:
      s = "#"
    bfs()
        
bfs()

Submission status: Wrong Answer

Solution code:
import sys
import re
import heapq


# グラフの初期化
def initialize_graph(node_list_x_name, node_list_y_name, score_list):
    graph = {}
    for node1, node2, cost in zip(node_list_x_name, node_list_y_name, score_list):
        graph = set_new_node(graph, node1, node2)
        graph[node1][node2] = int(cost)
        graph[node2][node1] = int(cost)
    return graph


def set_new_node(graph, node1, node2):
    if not node1 in graph.keys():
        graph[node1] = {}
    if not node2 in graph.keys():
        graph[node2] = {}
    return graph


# ダイクストラ法によって最短経路問題を解く
def solve_by_dijkstra(graph, W, H):
    # ノード毎のSTARTからの最小コスト
    min_dist_dict = {}
    # ノードに最小コストで辿り着く場合の直前のノード
    prev_node_dict = {}
    q = []
    heapq.heappush(q, (0, '0_0'))

    prev_node = ''

    while True:
        # 確定したノードから遷移可能なノードのうち
        # 最小のコストと遷移先ノードをmin_dist_dictとprev_node_dictに設定
        dist, node = heapq.heappop(q)
        min_dist_dict[node] = dist
        prev_node_dict[node] = prev_node
        # もしGOALノードの最小コストが確定したらループを抜ける
        if node == (str(H - 1) + '_' + str(W - 1)):
            return min_dist_dict, prev_node_dict
        prev_node = node
        # 確定したノードから遷移可能なノードについて
        # コストを計算し，キュー(q)に追加する
        culc_min_dist_and_put(graph, q, node, min_dist_dict, prev_node_dict)


def culc_min_dist_and_put(graph, q, departure_node, min_dist_dict, prev_node_dict):
    # 直前に確定したノードから遷移可能なすべてのノードについて繰り返し
    for arrival_node in graph[departure_node].keys():
        # 遷移可能なノードについて，直前に確定したノードから遷移した場合のコストを計算
        tmp_d = min_dist_dict[departure_node] + graph[departure_node][arrival_node]
        # 過去に遷移先ノードの最小コストを計算済みかどうか
        if arrival_node in min_dist_dict.keys():
            # 過去に計算していたSTARTからの最小コストより直前に確定したノードから遷移した場合の
            # コストが小さかった場合，最小コストを更新
            if tmp_d < min_dist_dict[arrival_node]:
                min_dist_dict[arrival_node] = tmp_d
                heapq.heappush(q, (min_dist_dict[arrival_node], arrival_node))
        else:
            min_dist_dict[arrival_node] = tmp_d
            heapq.heappush(q, (min_dist_dict[arrival_node], arrival_node))


def main():
    H, W = map(int, input().split())
    s = [None] * H
    for i in range(H):
        s[i] = input()

    node_list_x1 = [[i, j] for i in range(H - 1) for j in range(W - 1)]
    node_list_x2 = [[H - 1, i] for i in range(W - 1)]
    node_list_x3 = [[i, W - 1] for i in range(H - 1)]

    node_list_y1 = [[i, j + 1] for i in range(H - 1) for j in range(W - 1)]
    node_list_y2 = [[i + 1, j] for i in range(H - 1) for j in range(W - 1)]
    node_list_y3 = [[H - 1, i + 1] for i in range(W - 1)]
    node_list_y4 = [[i + 1, W - 1] for i in range(H - 1)]

    node_list_x = node_list_x1 * 2 + node_list_x2 + node_list_x3
    node_list_y = node_list_y1 + node_list_y2 + node_list_y3 + node_list_y4

    score_list = []
    for x, y in zip(node_list_x, node_list_y):
        if s[x[0]][x[1]] == s[y[0]][y[1]]:
            score_list.append(0)
        else:
            score_list.append(1)

    node_list_x_name = [str(x[0]) + '_' + str(x[1]) for x in node_list_x]
    node_list_y_name = [str(y[0]) + '_' + str(y[1]) for y in node_list_y]

    graph = initialize_graph(node_list_x_name, node_list_y_name, score_list)
    min_dist_dict, prev_node_dict = solve_by_dijkstra(graph, W, H)
    # GOALノードからprev_node_dictをたどって経路を復元
    # print('Route : H_W ', end='')
    node = (str(H - 1) + '_' + str(W - 1))
    while True:
        if node == '0_0':
            print()
            break
        # print(' ← ' + prev_node_dict[node], end='')
        node = prev_node_dict[node]

    if W == 1 or H == 1:
        if s[0][0] == '.':
            print(str(min_dist_dict[(str(H - 1) + '_' + str(W - 1))] - 1))
        else:
            print(str(min_dist_dict[(str(H - 1) + '_' + str(W - 1))]))
    else:
        if s[0][0] == '.':
            print(str(min(H, W, min_dist_dict[(str(H - 1) + '_' + str(W - 1))]) - 1))
        else:
            print(str(min(H, W, min_dist_dict[(str(H - 1) + '_' + str(W - 1))])))


if __name__ == '__main__':
    main()
    sys.exit(0)

Submission status: Wrong Answer

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

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


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)
    next_x = x-1
    next_y = y-1
    if 0 <= next_x:
        p.append(W*y+next_x)
    if 0 <= next_y:
        p.append(W*next_y+x)
    return p

k = min(R, key=R.get)
U[k] = True
while R:
    # print('k:{}'.format(k))
    p = get_search_address(k)
    # print('p:{}'.format(p))
    for n in p:
        # print('n:{}'.format(n))
        if S[n] == '#':
            # print('#')
            if not U[n]:
                # print('test1')
                T[n] = T[k]+1
                R[n] = T[n]
                U[n] = True
            else:
                # print('test2')
                if T[n] > T[k]+1:
                    # print('test3')
                    T[n] = T[k]+1
                    R[n] = T[n]
        else:
            # print('.')
            if not U[n]:
                # print('test4')
                T[n] = T[k]
                R[n] = T[n]
                U[n] = True
            else:
                # print('test5')
                if T[n] > T[k]:
                    # print('test6')
                    T[n] = T[k]
                    R[n] = T[n]
    k = min(R, key=R.get)

    del R[k]
    # print('R:{}'.format(R))
    # print('T:{}'.format(T))

print(T[H*W-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:
                        dp[ny][nx] = dp[y][x]
                        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()
"""
3 3
###
###
###
"""

Submission status: Wrong Answer

Solution code:
H,W = map(int,input().split())
A=[] #appendのために宣言が必要
while True:
    try:
        A.append(list(input()))
    except:
        break;

if A[0][0]=="#":
    A[0][0] =1
else:
    A[0][0] = 0

for j in range(W):
    for i in range(H):
        if i==0 and j==0:
            continue

        if j ==0 and i!=0 and A[i][j]=="#":
            A[i][j]=A[i-1][j]+1
        elif j ==0 and i!=0 and A[i][j]==".":
            A[i][j]=A[i-1][j]
        elif j !=0 and i==0 and A[i][j]=="#":
            A[i][j]=A[i][j-1]+1
        elif j !=0 and i==0 and A[i][j]==".":
            A[i][j]=A[i][j-1]
        elif i!=0 and j!=0 and A[i][j]=="#":
            A[i][j] = min(A[i][j-1],A[i-1][j])+1
        elif i!=0 and j!=0 and A[i][j]==".":
            A[i][j] = min(A[i][j-1],A[i-1][j])

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

Submission status: Wrong Answer

Solution code:
import itertools
h, w = map(int, input().split())
map_lst = []
for i in range(h):
    map_lst.append(list(input()))
b_lst = [[-1] * w for i in range(h)]
b_lst[0][0] = 0
e_lst = [[0, 0]]
#be_r, be_c:調べる前の座標, r, c:調べる座標
def main(be_r, be_c, r, c, bw, cnt):
    # print(r, c)
    if b_lst[r][c] != -1:
        return
    if map_lst[be_r][be_c] == map_lst[r][c]:
        b_lst[r][c] = cnt
        if c < w-1: main(r, c, r, c+1, map_lst[r][c], cnt)
        if r < h-1: main(r, c, r+1, c, map_lst[r][c], cnt)
    else:
        b_lst[r][c] = cnt + 1
        e_lst.append([r, c])

cnt_b = 0
while True:
    tmp_lst = e_lst
    if tmp_lst == []:
        break
    e_lst = []
    # print(tmp_lst, b_lst)
    for i in tmp_lst:
        r, c = i[0], i[1]
        if c < w-1: main(r, c, r, c+1, map_lst[r][c], cnt_b)
        if r < h-1: main(r, c, r+1, c, map_lst[r][c], cnt_b)
    cnt_b += 1
if map_lst[0][0] == '.':
    print(b_lst[-1][-1]//2)
else:
    print(b_lst[-1][-1]+1//2)

Submission status: Wrong Answer

Solution code:
import itertools
H, W = map(int, input().split())
k = H + W -2
lis = [list(input()) for i in range(H)]
count = 0
if lis[0][0] == '#':
  count += 1

s = []
for i in itertools.permutations(['+']*(W-1) + ['-']*(H-1)):
  x = 0
  y = 0
  risuto = list(i)
  for n in range(k):
    if risuto[n] == '-':
      if lis[y+1][x] == '#':
        count += 1
        y += 1
        break
    else:
        if lis[y][x+1] == '#':
          count += 1
          x += 1
    s.append(count)
print(min(s))

Submission status: Wrong Answer

Solution code:
import sys
from collections import deque
sys.setrecursionlimit(10**7)
import numpy as np
inf=float("inf")


def DFS(x,y,num):
    S[x][y]="."
    D[x][y]=num
    for a,b in ((0,1),(0,-1),(1,0),(-1,0)):
        X,Y=x+a,y+b
        if S[X][Y]=="#" and 1<=X<=h and 1<=Y<=w:
            DFS(X,Y,num)


def BFS(x,y):
    color[x][y]="gray"
    D[x][y]=0 if S[x][y]!="#" else 1
    queue=deque([[x,y]])

    while len(queue)!=0:
        a,b=queue.popleft()
        for c,d in [[0,1],[1,0]]:
            X,Y=a+c,b+d
            if color[X][Y]=="white" and (1<=X<=h and 1<=Y<=w):
                color[X][Y]="gray"
                if S[X][Y]=="#":
                    if a==1 and b==1:D[X][Y]=1
                    else:D[X][Y]=min(D[X-1][Y]+1,D[X][Y-1]+1)
                    DFS(X,Y,D[X][Y])
                elif S[X][Y]=="." and D[X][Y]==inf:
                    D[X][Y]=min(D[X-1][Y],D[X][Y-1])
                queue.append([X,Y])
                #print(np.array(D))
        color[a][b]="black"
    #print(np.array(D))
    return D[h][w]


h,w=map(int,input().split())
S=[["#"]+list(input())+["#"] for _ in range(h)]
S.insert(0,["#"]*(w+2))
S.append(["#"]*(w+2))

color=[["white" for _ in range(w+2)] for _ in range(h+2)]
D=[[inf for _ in range(w+2)] for _ in range(h+2)]

print(BFS(1,1))

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]
    S[0, i] = "."
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]
    S[i, 0] = "."


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

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

        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]

        dp[i, j] = min(tmp1, tmp2)
# print(dp)
print(dp[-1, -1])

Submission status: Wrong Answer

Solution code:
h,w=map(int,input().split())
s=[list(input()) for i in range(h)]
x=[[0]*(w+2)]*(h+2)
flag=0
if s[0][0]==".":
  x[0][0]=0
  flag=0
else:
  x[0][0]=1
  flag=1
for i in range(0,h):
  for j in range(0,w):
    if i!=0 and j!=0:
      if s[i][j]==".":
        flag=0
        if i==0 and j!=0:
          x[i][j]=x[i][j-1]
        elif i!=0 and j==0:
          x[i][j]=x[i-1][j]
        elif i!=0 and j!=0:
          x[i][j]=min(x[i][j-1],x[i-1][j])
        
      elif s[i][j]=="#":
        if i==0 and j!=0 and s[i][j-1]=="#":
          x[i][j]=x[i][j-1]
        elif i==0 and j!=0 and s[i][j-1]!="#":
          x[i][j]=x[i][j-1]+1
      
        elif i!=0 and j==0 and s[i-1][j]=="#":
          x[i][j]=x[i-1][j]
        elif i!=0 and j==0 and s[i-1][j]!="#":
          x[i][j]=x[i-1][j]+1
        
        elif i!=0 and j!=0 and (s[i-1][j]=="#" or s[i][j-1]=="#"):
          x[i][j]=min(x[i][j-1],x[i-1][j])
        
        elif i!=0 and j!=0 and s[i-1][j]!="#" and s[i][j-1]=="#":
          x[i][j]=min(x[i][j-1],x[i-1][j]+1)
        
        elif i!=0 and j!=0 and s[i-1][j]=="#" and s[i][j-1]!="#":
          x[i][j]=min(x[i][j-1]+1,x[i-1][j])
print(x[h-1][w-1])

Submission status: Wrong Answer

Solution code:
import sys
import re
import heapq


# グラフの初期化
def initialize_graph(node_list_x_name, node_list_y_name, score_list):
    graph = {}
    for node1, node2, cost in zip(node_list_x_name, node_list_y_name, score_list):
        graph = set_new_node(graph, node1, node2)
        graph[node1][node2] = int(cost)
        graph[node2][node1] = int(cost)
    return graph


def set_new_node(graph, node1, node2):
    if not node1 in graph.keys():
        graph[node1] = {}
    if not node2 in graph.keys():
        graph[node2] = {}
    return graph


# ダイクストラ法によって最短経路問題を解く
def solve_by_dijkstra(graph, W, H):
    # ノード毎のSTARTからの最小コスト
    min_dist_dict = {}
    # ノードに最小コストで辿り着く場合の直前のノード
    prev_node_dict = {}
    q = []
    heapq.heappush(q, (0, '0_0'))

    prev_node = ''

    while True:
        # 確定したノードから遷移可能なノードのうち
        # 最小のコストと遷移先ノードをmin_dist_dictとprev_node_dictに設定
        dist, node = heapq.heappop(q)
        min_dist_dict[node] = dist
        prev_node_dict[node] = prev_node
        # もしGOALノードの最小コストが確定したらループを抜ける
        if node == (str(H - 1) + '_' + str(W - 1)):
            return min_dist_dict, prev_node_dict
        prev_node = node
        # 確定したノードから遷移可能なノードについて
        # コストを計算し，キュー(q)に追加する
        culc_min_dist_and_put(graph, q, node, min_dist_dict, prev_node_dict)


def culc_min_dist_and_put(graph, q, departure_node, min_dist_dict, prev_node_dict):
    # 直前に確定したノードから遷移可能なすべてのノードについて繰り返し
    for arrival_node in graph[departure_node].keys():
        # 遷移可能なノードについて，直前に確定したノードから遷移した場合のコストを計算
        tmp_d = min_dist_dict[departure_node] + graph[departure_node][arrival_node]
        # 過去に遷移先ノードの最小コストを計算済みかどうか
        if arrival_node in min_dist_dict.keys():
            # 過去に計算していたSTARTからの最小コストより直前に確定したノードから遷移した場合の
            # コストが小さかった場合，最小コストを更新
            if tmp_d < min_dist_dict[arrival_node]:
                min_dist_dict[arrival_node] = tmp_d
                heapq.heappush(q, (min_dist_dict[arrival_node], arrival_node))
        else:
            min_dist_dict[arrival_node] = tmp_d
            heapq.heappush(q, (min_dist_dict[arrival_node], arrival_node))


def main():
    H, W = map(int, input().split())
    s = [None] * H
    for i in range(H):
        s[i] = input()

    node_list_x1 = [[i, j] for i in range(H - 1) for j in range(W - 1)]
    node_list_x2 = [[H - 1, i] for i in range(W - 1)]
    node_list_x3 = [[i, W - 1] for i in range(H - 1)]

    node_list_y1 = [[i, j + 1] for i in range(H - 1) for j in range(W - 1)]
    node_list_y2 = [[i + 1, j] for i in range(H - 1) for j in range(W - 1)]
    node_list_y3 = [[H - 1, i + 1] for i in range(W - 1)]
    node_list_y4 = [[i + 1, W - 1] for i in range(H - 1)]

    node_list_x = node_list_x1 * 2 + node_list_x2 + node_list_x3
    node_list_y = node_list_y1 + node_list_y2 + node_list_y3 + node_list_y4

    score_list = []
    for x, y in zip(node_list_x, node_list_y):
        if s[x[0]][x[1]] == s[y[0]][y[1]]:
            score_list.append(0)
        else:
            score_list.append(1)

    node_list_x_name = [str(x[0]) + '_' + str(x[1]) for x in node_list_x]
    node_list_y_name = [str(y[0]) + '_' + str(y[1]) for y in node_list_y]

    graph = initialize_graph(node_list_x_name, node_list_y_name, score_list)
    min_dist_dict, prev_node_dict = solve_by_dijkstra(graph, W, H)
    # GOALノードからprev_node_dictをたどって経路を復元
    print('Route : H_W ', end='')
    node = (str(H - 1) + '_' + str(W - 1))
    while True:
        if node == '0_0':
            print()
            break
        print(' ← ' + prev_node_dict[node], end='')
        node = prev_node_dict[node]

    if W == 1 or H == 1:
        if s[0][0] == '.':
            print(str(min_dist_dict[(str(H - 1) + '_' + str(W - 1))] - 1))
        else:
            print(str(min_dist_dict[(str(H - 1) + '_' + str(W - 1))]))
    else:
        if s[0][0] == '.':
            print(str(min(H, W, min_dist_dict[(str(H - 1) + '_' + str(W - 1))]) - 1))
        else:
            print(str(min(H, W, min_dist_dict[(str(H - 1) + '_' + str(W - 1))])))


if __name__ == '__main__':
    main()
    sys.exit(0)