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:
from heapq import heappush,heappop,heapify
from collections import deque,defaultdict,Counter
from itertools import permutations,combinations,groupby
import sys,bisect,string,math,time,functools,random
def Golf():*a,=map(int,open(0))
def I():return int(input())
def S_():return input()
def IS():return input().split()
def LS():return [i for i in input().split()]
def LI():return [int(i) for i in input().split()]
def LI_():return [int(i)-1 for i in input().split()]
def NI(n):return [int(input()) for i in range(n)]
def NI_(n):return [int(input())-1 for i in range(n)]
def StoLI():return [ord(i)-97 for i in input()]
def ItoS(n):return chr(n+97)
def LtoS(ls):return ''.join([chr(i+97) for i in ls])
def GI(V,E,Directed=False,index=0):
    org_inp=[];g=[[] for i in range(n)]
    for i in range(E):
        inp=LI();org_inp.append(inp)
        if index==0:inp[0]-=1;inp[1]-=1
        if len(inp)==2:
            a,b=inp;g[a].append(b)
            if not Directed:g[b].append(a)
        elif len(inp)==3:
            a,b,c=inp;aa=(inp[0],inp[2]);bb=(inp[1],inp[2]);g[a].append(bb)
            if not Directed:g[b].append(aa)
    return g,org_inp
def GGI(h,w,search=None,replacement_of_found='.',mp_def={'#':1,'.':0}):
#h,w,g,sg=GGI(h,w,search=['S','G'],replacement_of_found='.',mp_def={'#':1,'.':0}) # sample usage
    mp=[1]*(w+2);found={}
    for i in range(h):
        s=input()
        for char in search:
            if char in s:
                found[char]=((i+1)*(w+2)+s.index(char)+1)
                mp_def[char]=mp_def[replacement_of_found]
        mp+=[1]+[mp_def[j] for j in s]+[1]
    mp+=[1]*(w+2)
    return h+2,w+2,mp,found
def TI(n):return GI(n,n-1)
def bit_combination(k,n=2):return [[tb//(n**bt)%n for bt in range(k)] for tb in range(n**k)]
def show(*inp,end='\n'):
    if show_flg:print(*inp,end=end)

YN=['YES','NO'];Yn=['Yes','No']
mo=10**9+7
inf=float('inf')
l_alp=string.ascii_lowercase
#sys.setrecursionlimit(10**7)
input=lambda: sys.stdin.readline().rstrip()

def ran_input():
    n=random.randint(4,16)
    rmin,rmax=1,10
    a=[random.randint(rmin,rmax) for _ in range(n)]
    return n,a

show_flg=False
show_flg=True

h,w=LI()
h,w,g,sg=GGI(h,w,search=['S','G'],replacement_of_found='.',mp_def={'#':1,'.':0})
dp=[10**6]*(h*w)
dp[h+1]=g[h+1]

for j in range(h*w-h):
    if (j+1)%w!=w-1:
        dp[j+1]=min(dp[j]+1 if (g[j],g[j+1])==(0,1) else dp[j],dp[j+1])
    if (j+w)//w!=h:
        dp[j+w]=min(dp[j]+1 if (g[j],g[j+w])==(0,1) else dp[j],dp[j+w])

print(dp[(h-2)*w+w-2])

Submission status: Wrong Answer

Solution code:
def main():
    H,W = map(int,input().split())
    S = [[s for s in input()] for _ in range(H)]
    dp = [[2**60 for _ in range(W)] for _ in range(H)]
    if S[0][0] == '#':dp[0][0] = 1
    else:dp[0][0] = 0
    for i in range(H):
        for j in range(W):
            if i>0:dp[i][j] = min(dp[i][j],dp[i-1][j])
            if j > 0:dp[i][j] = min(dp[i][j],dp[i][j-1])
            if S[i][j] == '.':
                if i+1<H:
                    if S[i+1][j] == "#":
                        dp[i+1][j] = min(dp[i+1][j],dp[i][j]+1)
                if j+1<W:
                    if S[i][j+1] == "#":
                        dp[i][j+1] = min(dp[i][j+1],dp[i][j]+1)
    print(dp[-1][-1])


if __name__ == "__main__":
    main()

Submission status: Wrong Answer

Solution code:
from heapq import heappush,heappop,heapify
from collections import deque,defaultdict,Counter
from itertools import permutations,combinations,groupby
import sys,bisect,string,math,time,functools,random
def Golf():*a,=map(int,open(0))
def I():return int(input())
def S_():return input()
def IS():return input().split()
def LS():return [i for i in input().split()]
def LI():return [int(i) for i in input().split()]
def LI_():return [int(i)-1 for i in input().split()]
def NI(n):return [int(input()) for i in range(n)]
def NI_(n):return [int(input())-1 for i in range(n)]
def StoLI():return [ord(i)-97 for i in input()]
def ItoS(n):return chr(n+97)
def LtoS(ls):return ''.join([chr(i+97) for i in ls])
def GI(V,E,Directed=False,index=0):
    org_inp=[];g=[[] for i in range(n)]
    for i in range(E):
        inp=LI();org_inp.append(inp)
        if index==0:inp[0]-=1;inp[1]-=1
        if len(inp)==2:
            a,b=inp;g[a].append(b)
            if not Directed:g[b].append(a)
        elif len(inp)==3:
            a,b,c=inp;aa=(inp[0],inp[2]);bb=(inp[1],inp[2]);g[a].append(bb)
            if not Directed:g[b].append(aa)
    return g,org_inp
def GGI(h,w,search=None,replacement_of_found='.',mp_def={'#':1,'.':0}):
#h,w,g,sg=GGI(h,w,search=['S','G'],replacement_of_found='.',mp_def={'#':1,'.':0}) # sample usage
    mp=[1]*(w+2);found={}
    for i in range(h):
        s=input()
        for char in search:
            if char in s:
                found[char]=((i+1)*(w+2)+s.index(char)+1)
                mp_def[char]=mp_def[replacement_of_found]
        mp+=[1]+[mp_def[j] for j in s]+[1]
    mp+=[1]*(w+2)
    return h+2,w+2,mp,found
def TI(n):return GI(n,n-1)
def bit_combination(k,n=2):return [[tb//(n**bt)%n for bt in range(k)] for tb in range(n**k)]
def show(*inp,end='\n'):
    if show_flg:print(*inp,end=end)

YN=['YES','NO'];Yn=['Yes','No']
mo=10**9+7
inf=float('inf')
l_alp=string.ascii_lowercase
#sys.setrecursionlimit(10**7)
input=lambda: sys.stdin.readline().rstrip()

def ran_input():
    n=random.randint(4,16)
    rmin,rmax=1,10
    a=[random.randint(rmin,rmax) for _ in range(n)]
    return n,a

show_flg=False
show_flg=True

h,w=LI()
h,w,g,sg=GGI(h,w,search=['S','G'],replacement_of_found='.',mp_def={'#':1,'.':0})
dp=[10**6]*(h*w)
dp[h+1]=g[h+1]

for j in range(h*w-h):
    
    if (j+1)%w!=0:
        dp[j+1]=min(dp[j]+1 if (g[j],g[j+1])==(0,1) else dp[j],dp[j+1])
    if (j+w)//w!=h:
        dp[j+w]=min(dp[j]+1 if (g[j],g[j+w])==(0,1) else dp[j],dp[j+w])

print(dp[(h-2)*w+w-2])

Submission status: Wrong Answer

Solution code:
def main():
    H,W = map(int,input().split())
    S = [[s for s in input()] for _ in range(H)]
    dp = [[2**60 for _ in range(W)] for _ in range(H)]
    if S[0][0] == '#':dp[0][0] = 1
    else:dp[0][0] = 0
    for i in range(H):
        for j in range(W):
            if S[i][j] == '.':
                if i>0:dp[i][j] = min(dp[i][j],dp[i-1][j])
                if j > 0:dp[i][j] = min(dp[i][j],dp[i][j-1])
                if i+1<H:
                    if S[i+1][j] == "#":
                        dp[i+1][j] = min(dp[i+1][j],dp[i][j]+1)
                if j+1<W:
                    if S[i][j+1] == "#":
                        dp[i][j+1] = min(dp[i][j+1],dp[i][j]+1)
    print(dp[-1][-1])


if __name__ == "__main__":
    main()

Submission status: Wrong Answer

Solution code:
#!usr/bin/env python3
from collections import defaultdict, deque
from heapq import heappush, heappop
from itertools import permutations, accumulate
import sys
import math
import bisect
def LI(): return [int(x) for x in sys.stdin.readline().split()]
def I(): return int(sys.stdin.readline())
def LS():return [list(x) for x in sys.stdin.readline().split()]
def S():
    res = list(sys.stdin.readline())
    if res[-1] == "\n":
        return res[:-1]
    return res
def IR(n):
    return [I() for i in range(n)]
def LIR(n):
    return [LI() for i in range(n)]
def SR(n):
    return [S() for i in range(n)]
def LSR(n):
    return [LS() for i in range(n)]

sys.setrecursionlimit(1000000)
mod = 1000000007

d = [(1,0),(0,1)]
def solve():
    h,w = LI()
    s = [input() for i in range(h)]
    bfs = [[-1]*w for i in range(h)]
    bfs[0][0] = 1&(s[0][0] == "#")
    q = deque([(0,0)])
    while q:
        y,x = q.popleft()
        if (y,x) == (h-1,w-1):
            print(bfs[y][x])
            return
        b = bfs[y][x]
        for dy,dx in d:
            ny,nx = y+dy,x+dx
            if 0 <= ny < h and 0 <= nx < w:
                if bfs[ny][nx] < 0:
                    if s[ny][nx] == "#":
                        nb = b+1
                        q.append((ny,nx))
                    else:
                        nb = b
                        q.appendleft((ny,nx))
                    bfs[ny][nx] = nb
    return

#Solve
if __name__ == "__main__":
    solve()

Submission status: Wrong Answer

Solution code:
def main():
    H,W = map(int,input().split())
    S = [[s for s in input()] for _ in range(H)]
    dp = [[2**60 for _ in range(W)] for _ in range(H)]
    if S[0][0] == '#':dp[0][0] = 1
    else:dp[0][0] = 0
    for i in range(H):
        for j in range(W):
            if S[i][j] == '.':
                if i+1<H:
                    if S[i+1][j] == "#":
                        dp[i+1][j] = min(dp[i+1][j],dp[i][j]+1)
                if j+1<W:
                    if S[i][j+1] == "#":
                        dp[i][j+1] = min(dp[i][j+1],dp[i][j]+1)
    print(dp[-1][-1])


if __name__ == "__main__":
    main()

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=[[10**9]*w for _ in range(h)]
D[0][0]=0
for i in range(h):
    for j in range(w):
        for x,y in [(0,1),(1,0)]:
            if i+x>=h or j+y>=w:
                continue
            if S[i][j]!=S[i+x][j+y]:
                D[i+x][j+y]=min(D[i][j]+1,D[i+x][j+y])
            else:
                D[i+x][j+y]=D[i][j]
                
                
                
                
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:
#!/usr/bin/env python3
from collections import defaultdict,deque
from heapq import heappush, heappop
from bisect import bisect_left, bisect_right
import sys, random, itertools, math
sys.setrecursionlimit(10**5)
input = sys.stdin.readline
sqrt = math.sqrt
def LI(): return list(map(int, input().split()))
def LF(): return list(map(float, input().split()))
def LI_(): return list(map(lambda x: int(x)-1, input().split()))
def II(): return int(input())
def IF(): return float(input())
def LS(): return list(map(list, input().split()))
def S(): return list(input().rstrip())
def IR(n): return [II() for _ in range(n)]
def LIR(n): return [LI() for _ in range(n)]
def FR(n): return [IF() for _ in range(n)]
def LFR(n): return [LI() for _ in range(n)]
def LIR_(n): return [LI_() for _ in range(n)]
def SR(n): return [S() for _ in range(n)]
def LSR(n): return [LS() for _ in range(n)]
mod = 1000000007
inf = float("INF")

#solve
def solve():
    h,w = LI()
    s = SR(h)
    b = [[inf] * w for i in range(h)]
    q = [(s[0][0] == "#", (0, 0))]
    b[0][0] = s[0][0] == "#"
    while q:
        p, xy = heappop(q)
        y, x = xy
        z = s[y][x]
        for mx, my in [(0, 1), (0, -1), (-1, 0), (1, 0)]:
            mx += x
            my += y
            if 0 <= mx < w and 0 <= my < h:
                if b[my][mx] > p + (z != s[my][mx] and s[my][mx] != "."):
                    b[my][mx] = p + (z != s[my][mx] and s[my][mx] != ".")
                    heappush(q, (p + (z != s[my][mx] and s[my][mx] != "."), (my, mx)))
    # print(b)
    print(b[-1][-1] if b[-1][-1] else 0)

    return


#main
if __name__ == '__main__':
    solve()

Submission status: Wrong Answer

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

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

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

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

Submission status: Wrong Answer

Solution code:
H, W = map(int,input().split())
MAP = []
INF = 10 ** 8
for _ in range(H):
    MAP.append(input())

dp = [[0 for i in range(W)] for i in range(H)]

for i in range(H):
    for j in range(W):
        if i == 0 and j == 0:
            if MAP[i][j] == "#":
                dp[i][j] = 1
        elif i == 0:
            flag = 0
            if MAP[i][j] == "#" and MAP[i][j-1] == ".":
                flag = 1
            dp[i][j] = flag + dp[i][j-1]
        elif j == 0:
            flag = 1
            if MAP[i][j] == "#" and MAP[i-1][j] == ".":
                flag = 1
            dp[i][j] = flag + dp[i-1][j]
        else:
            flag1 = 0
            flag2 = 0
            if MAP[i][j] == "#" and MAP[i][j-1] == ".":
                flag1 = 1
            if MAP[i][j] == "#" and MAP[i-1][j] == ".":
                flag2 = 1
            dp[i][j] = min(dp[i][j-1]+flag1,dp[i-1][j]+flag2)
        

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

Submission status: Wrong Answer

Solution code:
from collections import deque

h, w = map(int, input().split())
S = [[int(c == '.') for c in input()] for _ in range(h)]
dp = [[h+w]*w for _ in range(h)]
dp[0][0] = int(S[0][0] == 0)

queue = [deque() for i in range(h+w)]
queue[int(S[0][0] == 0)].append((0, 0))
def bfs(val):
    while queue[val]:
        x, y = queue[val].popleft()
        for dx, dy in [(1,0), (0,1), (-1,0), (0,-1)]:
            if x+dx not in (-1, w) and y+dy not in (-1, h):
                if S[y+dy][x+dx]:
                    if val < dp[y+dy][x+dx]:
                        dp[y+dy][x+dx] = val
                        queue[val].append((x+dx, y+dy))
                else:
                    if val+1 < dp[y+dy][x+dx]:
                        dp[y+dy][x+dx] = val+1
                        queue[val+1].append((x+dx, y+dy))
        if val + 1 < h+w:
            bfs(val+1)
            
bfs(int(S[0][0] == 0))
print(dp[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 = [int((s[x[0]][x[1]] == '.') and (s[y[0]][y[1]] == '#'))
                  for x, y in zip(node_list_x, node_list_y)]
    # score_list = []
    # for x, y in zip(node_list_x, node_list_y):
    #     if (s[x[0]][x[1]] == '.') and (s[y[0]][y[1]] == '#'):
    #         score_list.append(1)
    #     else:
    #         score_list.append(0)

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


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

Submission status: Wrong Answer

Solution code:
#!/usr/bin/env python3
from collections import defaultdict,deque
from heapq import heappush, heappop
from bisect import bisect_left, bisect_right
import sys, random, itertools, math
sys.setrecursionlimit(10**5)
input = sys.stdin.readline
sqrt = math.sqrt
def LI(): return list(map(int, input().split()))
def LF(): return list(map(float, input().split()))
def LI_(): return list(map(lambda x: int(x)-1, input().split()))
def II(): return int(input())
def IF(): return float(input())
def LS(): return list(map(list, input().split()))
def S(): return list(input().rstrip())
def IR(n): return [II() for _ in range(n)]
def LIR(n): return [LI() for _ in range(n)]
def FR(n): return [IF() for _ in range(n)]
def LFR(n): return [LI() for _ in range(n)]
def LIR_(n): return [LI_() for _ in range(n)]
def SR(n): return [S() for _ in range(n)]
def LSR(n): return [LS() for _ in range(n)]
mod = 1000000007
inf = float("INF")

#solve
def solve():
    h,w = LI()
    s = SR(h)
    b = [[inf] * w for i in range(h)]
    q = [(s[0][0] == "#", (0, 0))]
    b[0][0] = s[0][0] == "#"
    while q:
        p, xy = heappop(q)
        y, x = xy
        z = s[y][x]
        for mx, my in [(0, 1), (0, -1), (-1, 0), (1, 0)]:
            mx += x
            my += y
            if 0 <= mx < w and 0 <= my < h:
                if b[my][mx] > p + (z != s[my][mx] and z != "."):
                    b[my][mx] = p + (z != s[my][mx] and z != ".")
                    heappush(q, (p + (z != s[my][mx] and z != "."), (my, mx)))
    # print(b)
    print(b[-1][-1] if b[-1][-1] else 0)

    return


#main
if __name__ == '__main__':
    solve()

Submission status: Wrong Answer

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

dp = [[0] * (W+1) for h in range(H+1)]
if S[0][0] == '#':
    dp[1][1] = 1

for h in range(1, H+1):
    for w in range(1, W+1):
        if h >= 2 and w >= 2:
            if S[h-1][w-1] == '.':
                dp[h][w] = min(dp[h][w-1], dp[h-1][w])
            else:
                if S[h-1][w-2] == S[h-2][w-1] == '.':
                    dp[h][w] = min(dp[h-1][w], dp[h][w-1]) + 1
                elif S[h-1][w-2] == '#' and S[h-2][w-1] == '.':
                    dp[h][w] = min(dp[h][w-1], dp[h-1][w]+1)
                elif S[h-1][w-2] == '.' and S[h-2][w-1] == '#':
                    dp[h][w] = min(dp[h][w-1]+1, dp[h-1][w])
                else:
                    dp[h][w] = min(dp[h][w-1], dp[h-1][w])
        elif h >= 2:
            if S[h-1][w-1] == '.':
                dp[h][w] = dp[h-1][w]
            else:
                if S[h-2][w-1] == '.':
                    dp[h][w] = dp[h-1][w] + 1
                else:
                    dp[h][w] = dp[h-1][w]            
        else:
            if S[h-1][w-1] == '.':
                dp[h][w] = dp[h][w-1]
            else:
                if S[h-1][w-2] == '.':
                    dp[h][w] = dp[h][w-1] + 1
                else:
                    dp[h][w] = dp[h][w-1]


print(dp[H][W])

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]+1)//2)
else:
  print((dp[-1][-1]+1)//2+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]] == '.') and (s[y[0]][y[1]] == '#'):
            score_list.append(1)
        else:
            score_list.append(0)

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


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

Submission status: Wrong Answer

Solution code:
#!/usr/bin/env python3
from collections import defaultdict,deque
from heapq import heappush, heappop
from bisect import bisect_left, bisect_right
import sys, random, itertools, math
sys.setrecursionlimit(10**5)
input = sys.stdin.readline
sqrt = math.sqrt
def LI(): return list(map(int, input().split()))
def LF(): return list(map(float, input().split()))
def LI_(): return list(map(lambda x: int(x)-1, input().split()))
def II(): return int(input())
def IF(): return float(input())
def LS(): return list(map(list, input().split()))
def S(): return list(input().rstrip())
def IR(n): return [II() for _ in range(n)]
def LIR(n): return [LI() for _ in range(n)]
def FR(n): return [IF() for _ in range(n)]
def LFR(n): return [LI() for _ in range(n)]
def LIR_(n): return [LI_() for _ in range(n)]
def SR(n): return [S() for _ in range(n)]
def LSR(n): return [LS() for _ in range(n)]
mod = 1000000007
inf = float("INF")

#solve
def solve():
    h,w = LI()
    s = SR(h)
    b = [[inf] * w for i in range(h)]
    q = [(s[0][0] == "#", (0, 0))]
    b[0][0] = s[0][0] == "#"
    while q:
        p, xy = heappop(q)
        y, x = xy
        z = s[y][x]
        for mx, my in [(0, 1), (0, -1), (-1, 0), (1, 0)]:
            mx += x
            my += y
            if 0 <= mx < w and 0 <= my < h:
                if b[my][mx] > p + (z != s[my][mx]):
                    b[my][mx] = p + (z != s[my][mx])
                    heappush(q, (p + (z != s[my][mx]), (my, mx)))
    print(b[-1][-1] if b[-1][-1] else 0)

    return


#main
if __name__ == '__main__':
    solve()