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: Accepted

Solution code:
import collections
from collections import deque

h,w= map(int, input().split())
s= [list(input()) for i in range(h)]

# １行目、一列目を囲う
for i in range(h):
    s[i]=['#']+s[i]
s=[['#']*(w+1)]+s

dp=[[0]*(w+1) for i in range(h+1)]
# 各マスに到達する最小の操作回数
for i in range(w+1):
    dp[0][i]+=1
for i in range(h+1):
    dp[i][0]+=1


for i in range(1,h+1):
    for j in range(1,w+1):
        if i==1 and j==1:
            if s[i][j]=='#':
                dp[i][j]+=1

        elif i==1:
            if s[i][j]=='#' and s[i][j-1]=='.':
                dp[i][j]+=dp[i][j-1]+1
            else:
                dp[i][j]=dp[i][j-1]
        elif j==1:
            if s[i][j]=='#' and s[i-1][j]=='.':
                dp[i][j]=dp[i-1][j]+1
            else:
                dp[i][j]=dp[i-1][j]

        elif dp[i-1][j]==dp[i][j-1]:
            if s[i][j]=='#' and s[i-1][j]=='.' and s[i][j-1]=='.':
                dp[i][j]=dp[i-1][j]+1
            else:
                dp[i][j]=dp[i-1][j]

        elif dp[i-1][j]<dp[i][j-1]:
            if s[i][j]=='#' and s[i-1][j]=='.':
                dp[i][j]=dp[i-1][j]+1
            else:
                dp[i][j]=dp[i-1][j]
        else:
            if s[i][j]=='#' and s[i][j-1]=='.':
                dp[i][j]=dp[i][j-1]+1
            else:
                dp[i][j]=dp[i][j-1]




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

Submission status: Accepted

Solution code:
import sys

sys.setrecursionlimit(10 ** 6)
int1 = lambda x: int(x) - 1
p2D = lambda x: print(*x, sep="\n")
def II(): return int(sys.stdin.readline())
def MI(): return map(int, sys.stdin.readline().split())
def LI(): return list(map(int, sys.stdin.readline().split()))
def LLI(rows_number): return [LI() for _ in range(rows_number)]
def SI(): return sys.stdin.readline()[:-1]

def main():
    inf=10**9
    h,w=MI()
    ss=[SI() for _ in range(h)]
    cc=[[0]*w for _ in range(h)]
    if ss[0][0]=="#":cc[0][0]=1
    for i in range(h):
        for j in range(w):
            if (i,j)==(0,0):continue
            u=l=inf
            if i-1>=0:
                u=cc[i-1][j]
                if ss[i][j]=="#" and ss[i-1][j]==".":u+=1
            if j-1>=0:
                l=cc[i][j-1]
                if ss[i][j]=="#" and ss[i][j-1]==".":l+=1
            cc[i][j]=min(u,l)
    print(cc[h-1][w-1])

main()

Submission status: Accepted

Solution code:
from heapq import heappop, heappush

h, w = map(int, input().split())
s = [list(input()) for _ in range(h)]

def dijkstra(graph, n, s):
    d = [float("inf")] * n
    d[s] = 0
    q = []
    heappush(q, (0, s))
    while q:
        dist, v = heappop(q)
        if d[v] < dist: continue
        for nv, cost in graph[v]:
            if d[nv] > d[v] + cost:
                d[nv] = d[v] + cost
                heappush(q, (d[nv], nv))
    return d

n = h*w+1
g = [list() for _ in range(n)]
for i in range(h):
    for j in range(w-1):
        cid = i*w + j
        g[cid].append((cid+1, int(s[i][j] == "." and s[i][j+1] == "#")))
for i in range(h-1):
    for j in range(w):
        cid = i*w + j
        g[cid].append((cid+w, int(s[i][j] == "." and s[i+1][j] == "#")))
g[n-1].append((0, int(s[0][0] == "#")))

print(dijkstra(g, n, n-1)[n-2])

Submission status: Accepted

Solution code:
# coding: utf-8
H, W = list(map(int, input().split()))
S = []
for _ in range(H):
    S.append(list(input()))

grid = [[0 for _ in range(W)] for _ in range(H)]

for h in range(1,H):
  if S[h-1][0] == '#' and S[h][0] == '.':
    grid[h][0] = grid[h-1][0] + 1
  else:
    grid[h][0] = grid[h-1][0]
    
for w in range(1,W):
  if S[0][w-1] == '#' and S[0][w] == '.':
    grid[0][w] = grid[0][w-1] + 1
  else:
    grid[0][w] = grid[0][w-1]
for w in range(1,W):
  for h in range(1,H):
    if S[h-1][w] == '#' and S[h][w] == '.':
      next_h = grid[h-1][w] + 1
    else:
      next_h = grid[h-1][w]      
    if S[h][w-1] == '#' and S[h][w] == '.':
      next_w = grid[h][w-1] + 1
    else:
      next_w = grid[h][w-1]
    grid[h][w] = min([next_w, next_h])
if S[H-1][W-1] == '#':
  grid[H-1][W-1] += 1
print(grid[H-1][W-1])

Submission status: Accepted

Solution code:
import collections

h,w=map(int,input().split())
board=[list(input()) for _ in range(h)]
q=collections.deque()
if board[0][0]=='#':
  q.append((0,0,1,1))
else:
  q.append((0,0,0,0))
dp=[[10**18]*w for _ in range(h)]
ans=10**18
while len(q)!=0:
  x,y,cnt,flag=q.popleft()
  if x==w-1 and y==h-1:
    ans=min(ans,cnt)
  else:
    if x!=w-1:
      if flag==0:
        if board[y][x+1]=='#':
          if dp[y][x+1]>cnt+1:
            q.append((x+1,y,cnt+1,1))
            dp[y][x+1]=cnt+1
        else:
          if dp[y][x+1]>cnt:
            q.append((x+1,y,cnt,0))
            dp[y][x+1]=cnt
      else:
        if board[y][x+1]=='#':
          if dp[y][x+1]>cnt:
            q.append((x+1,y,cnt,1))
            dp[y][x+1]=cnt
        else:
          if dp[y][x+1]>cnt:
            q.append((x+1,y,cnt,0))
            dp[y][x+1]=cnt
    if y!=h-1:
      if flag==0:
        if board[y+1][x]=='#':
          if dp[y+1][x]>cnt+1:
            q.append((x,y+1,cnt+1,1))
            dp[y+1][x]=cnt+1
        else:
          if dp[y+1][x]>cnt:
            q.append((x,y+1,cnt,0))
            dp[y+1][x]=cnt
      else:
        if board[y+1][x]=='#':
          if dp[y+1][x]>cnt:
            q.append((x,y+1,cnt,1))
            dp[y+1][x]=cnt
        else:
          if dp[y+1][x]>cnt:
            q.append((x,y+1,cnt,0))
            dp[y+1][x]=cnt
print(dp[-1][-1])

Submission status: Accepted

Solution code:
import sys
from heapq import heapify, heappush, heappop

read = sys.stdin.read
readline = sys.stdin.readline

H, W = map(int, readline().split())
s = tuple(map(str, read().split()))
INF = 10 ** 10
grid = [[INF] * W for _ in range(H)]
if s[0][0] == '#':
    start = (1, (0, 0))
else:
    start = (0, (0, 0))
heap = [start]
heapify(heap)
while heap:
    d, (x, y) = heappop(heap)
    if grid[x][y] != INF:
        continue
    grid[x][y] = d
    for i, j in ((0, 1), (1, 0)):
        new_x = x + i
        new_y = y + j
        if new_x == H or new_y == W:
            continue
        if grid[new_x][new_y] <= d:
            continue
        if s[x][y] == '.' and s[new_x][new_y] == '#':
            heappush(heap, (d + 1, (new_x, new_y)))
        else:
            heappush(heap, (d, (new_x, new_y)))

print(grid[-1][-1])

Submission status: Accepted

Solution code:
import sys
from heapq import heapify, heappush, heappop

read = sys.stdin.read
readline = sys.stdin.readline

H, W = map(int, readline().split())
s = tuple(map(str, read().split()))
INF = 10 ** 10
grid = [[INF] * W for _ in range(H)]
if s[0][0] == '#':
    grid[0][0] = 1
else:
    grid[0][0] = 0
start = (grid[0][0], (0, 0))
heap = [start]
heapify(heap)
while heap:
    d, (x, y) = heappop(heap)
    for i, j in ((0, 1), (1, 0)):
        new_x = x + i
        new_y = y + j
        if new_x == H or new_y == W:
            continue
        if grid[new_x][new_y] <= d:
            continue
        if s[x][y] == '.' and s[new_x][new_y] == '#':
            grid[new_x][new_y] = d + 1
            heappush(heap, (d + 1, (new_x, new_y)))
        else:
            grid[new_x][new_y] = d
            heappush(heap, (d, (new_x, new_y)))

print(grid[-1][-1])

Submission status: Accepted

Solution code:
import sys
from collections import deque

read = sys.stdin.read
readline = sys.stdin.readline

H, W = map(int, readline().split())
s = tuple(map(str, read().split()))
INF = 10 ** 10
grid = [[INF] * W for _ in range(H)]
start = (0, 0)
queue = deque([start])
grid[0][0] = 0
while queue:
    x, y = queue.pop()
    for i, j in ((0, 1), (1, 0)):
        new_x = x + i
        new_y = y + j
        if new_x >= H or new_y >= W:
            continue
        else:
            if s[x][y] == '.' and s[new_x][new_y] == '#':
                cnt = grid[x][y] + 1
                if grid[new_x][new_y] > cnt:
                    grid[new_x][new_y] = cnt
                    queue.append((new_x, new_y))
            else:
                if grid[new_x][new_y] > grid[x][y]:
                    grid[new_x][new_y] = grid[x][y]
                    queue.append((new_x, new_y))

answer = grid[H - 1][W - 1]
if s[0][0] == '#':
    answer += 1
print(answer)

Submission status: Accepted

Solution code:
H,W=map(int,input().split())
s=[]
count=[[10**9 for _ in range(W)] for i in range(H)]
for i in range(H):
    S=input()
    s.append(S)
if s[0][0]=="#":
    count[0][0]=1
else:
    count[0][0]=0
for i in range(H):
    for j in range(W):
        if i==0 and j==0:
            continue
        val1=10**9
        val2=10**9
        if i==0:
            pass
        else:
            val1=count[i-1][j]
            if s[i][j]=="#" and s[i-1][j]==".":
                val1+=1
        if j==0:
            pass
        else:
            val2=count[i][j-1]
            if s[i][j]=="#" and s[i][j-1]==".":
                val2+=1
        count[i][j]=min(val1,val2)
print(count[-1][-1])

Submission status: Accepted

Solution code:
INF = int(1e9) + 7
h, w = map(int, input().split())
s = []
for i in range(h):
    s.append(list(input()))

dp = [[INF] * w for i in range(h)]
if s[0][0] == '#':
    dp[0][0] = 1
else:
    dp[0][0] = 0
#print(dp)

for i in range(h):
    for j in range(w):
        if i == 0 and j == 0:
            continue
        val1 = dp[i-1][j]
        if s[i][j] == '#' and s[i-1][j] == '.':
            val1 += 1
        val2 = dp[i][j-1]
        if s[i][j] == '#' and s[i][j-1] == '.':
            val2 += 1
        dp[i][j] = min(val1, val2)
        #print(i, j,val1, val2)
print(dp[h-1][w-1])
#print(dp)

Submission status: Accepted

Solution code:
h, w = map(int, input().split())
s = []
score = [[0] * w for i in range(h)]
for i in range(h):
  s.append(list(input()))
  for j in range(w):
    if i == 0:
      if j == 0:
        score[0][0] = 1 if s[0][0] == '#' else 0
      else:
        score[0][j] = score[0][j-1]
        if s[0][j] == '#' and s[0][j-1] != '#':
          score[0][j] += 1
    else:
      if j == 0:
        score[i][0] = score[i-1][0]
        if s[i][0] == '#' and s[i-1][0] != '#':
          score[i][0] += 1
      else:
        r = score[i][j-1]
        if s[i][j] == '#' and s[i][j-1] != '#':
          r += 1
        d = score[i-1][j]
        if s[i][j] == '#' and s[i-1][j] != '#':
          d += 1
        score[i][j] += min(r, d)
print(score[-1][-1])

Submission status: Accepted

Solution code:
from collections import deque

def solve():
    H, W = map(int, input().split())
    A = [list(input()) for _ in range(H)]
    INF = 10 ** 9
    d = [[INF] * W for i in range(H)]
    d[0][0] = 1 if A[0][0] == '#' else 0

    prepare = 1 if A[0][0] == '#' else 0
    q = deque([(prepare, 0, 0)])
    while q:
        c, x, y = q.popleft()
        for a, b in [(1,0), (0,1)]:
            nx, ny = x+a, y+b
            if nx >= W or ny >= H: continue
            k = 1 if A[y][x] != A[ny][nx] else 0
            if c+k >= d[ny][nx]: continue
            d[ny][nx] = c+k
            q.append((c+k, nx, ny))

    return (d[H-1][W-1]+1)//2

print(solve())

Submission status: Accepted

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

ans = [[0] * W for _ in range(H)]

if grid[0][0] == "#":
    ans[0][0] = 1

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

        r = H*W
        d = H*W
        if j > 0 and grid[i][j] != grid[i][j-1] and grid[i][j-1] == ".":
            r = 1 + ans[i][j-1]
        elif j > 0:
            r = ans[i][j-1]

        if i > 0 and grid[i][j] != grid[i-1][j] and grid[i-1][j] == ".":
            d = 1 + ans[i-1][j]
        elif i > 0:
            d = ans[i-1][j]
        ans[i][j] = min(r, d)

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

Submission status: Accepted

Solution code:
h, w = map(int, input().split())
S = []
for _ in range(h):
    s = str(input())
    S.append(s)

DP = [[0 for _ in range(w)] for _ in range(h)]

if S[0][0] == '.':
    DP[0][0] = 0
else:
    DP[0][0] = 1

ren = False
if DP[0][0] == 1:
    ren = True

for i in range(1,h):
    if S[i][0] == '.':
        DP[i][0] = DP[i-1][0]
        ren = False
    elif ren == False and S[i][0] == '#':
        DP[i][0] = DP[i-1][0] + 1
        ren = True
    elif ren == True and S[i][0] == '#':
        DP[i][0] = DP[i-1][0]
        ren = True

ren = False
if DP[0][0] == 1:
    ren = True
for j in range(1,w):
    if S[0][j] == '.':
        DP[0][j] = DP[0][j-1]
        ren = False
    elif ren == False and S[0][j] == '#':
        DP[0][j] = DP[0][j-1] + 1
        ren = True
    elif ren == True and S[0][j] == '#':
        DP[0][j] = DP[0][j-1]
        ren = True

for i in range(1,h):
    for j in range(1,w):
        if S[i][j] == '.':
            DP[i][j] = min(DP[i-1][j], DP[i][j-1])
        elif S[i][j] == '#':
            res_i = 0
            res_j = 0
            if S[i-1][j] == '.':
                res_i = 1
            if S[i][j-1] == '.':
                res_j = 1
            DP[i][j] = min(DP[i-1][j] + res_i, DP[i][j-1] + res_j)

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

Submission status: Accepted

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

inf = 10**18
dp = [[inf] * W for _ in range(H)]
if grid[0][0] == "#":
    dp[0][0] = 1
else:
    dp[0][0] = 0

for i in range(H):
    for j in range(W):
        if i != 0:
            tmp = dp[i - 1][j] + int(grid[i][j]=="#" and grid[i - 1][j]==".")
            dp[i][j] = min(dp[i][j], tmp)
        if j != 0:
            tmp = dp[i][j - 1] + int(grid[i][j]=="#" and grid[i][j - 1]==".")
            dp[i][j] = min(dp[i][j], tmp)

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

Submission status: Accepted

Solution code:
h, w = map(int, input().split())
s_list = []  # h, w
dp_dict = {}
for i in range(h):
    s = input()
    temp_list = []
    for temp in s:
        if temp == "#":
            temp_list.append(1)
        else:
            temp_list.append(0)
    s_list.append(temp_list)


def search(x, y, black):
    res = 0
    if (x, y, black) in dp_dict:
        return dp_dict[(x, y, black)]
    if x == w-1 and y == h-1:
        if s_list[y][x] == 1:
            if black:
                res = 0
            else:
                res = 1
        else:
            res = 0
    elif x == w-1:
        if s_list[y][x] == 1:
            if black:
                res = search(x, y+1, True)
            else:
                res = search(x, y+1, True)+1
        else:
            res = search(x, y+1, False)
    elif y == h-1:
        if s_list[y][x] == 1:
            if black:
                res = search(x+1, y, True)
            else:
                res = search(x+1, y, True)+1
        else:
            res = search(x+1, y, False)
    else:
        if s_list[y][x] == 1:
            if black:
                res = min([search(x+1, y, True), search(x, y+1, True)])
            else:
                res = min([search(x+1, y, True), search(x, y+1, True)])+1
        else:
            res = min([search(x+1, y, False), search(x, y+1, False)])
    dp_dict[(x, y, black)] = res
    return res


print(search(0, 0, False))

Submission status: Accepted

Solution code:
from collections import deque
h,w=map(int,input().split())
field=[["*" for i in range(w+2)]]+[["*"]+list(input())+["*"] for i in range(h)]+[["*" for i in range(w+2)]]
cost=[[500 for i in range(w+2)] for j in range(h+2)]
cost[1][1]=0
ans=0
for i in range(1,h+1):
    for j in range(1,w+1):
        color=field[i][j]
        if color=="." and field[i][j+1]=="#":
            cost[i][j+1]=min(cost[i][j]+1,cost[i][j+1])
        else:cost[i][j+1]=min(cost[i][j],cost[i][j+1])
        if color=="." and field[i+1][j]=="#":
            cost[i+1][j]=min(cost[i][j]+1,cost[i+1][j])
        else:cost[i+1][j]=min(cost[i][j],cost[i+1][j])
print(cost[h][w] if field[1][1]=="." else cost[h][w]+1)

Submission status: Accepted

Solution code:
import bisect,collections,copy,itertools,math,string
def I(): return int(input())
def S(): return input()
def LI(): return list(map(int,input().split()))
def LS(): return list(input().split())
##################################################
H,W = LI()
S = [S() for _ in range(H)]
dp = [[-1]*W for _ in range(H)]
for i in range(H):
    for j in range(W):
        judge = 1 if S[i][j]=='#' else 0
        if i==0: #0行目
            if j==0:
                dp[0][0] = judge
            else:
                dp[0][j] = dp[0][j-1]+judge*(0 if S[0][j-1]=='#' else 1)
        else: #0行目以外
            if j==0:
                dp[i][0] = dp[i-1][0]+judge*(0 if S[i-1][j]=='#' else 1)
            else:
                temp1 = dp[i][j-1]+judge*(0 if S[i][j-1]=='#' else 1)
                temp2 = dp[i-1][j]+judge*(0 if S[i-1][j]=='#' else 1)
                dp[i][j] = min(temp1,temp2)
print(dp[-1][-1])

Submission status: Accepted

Solution code:
##!/usr/bin/env python
## -*- coding: utf-8 -*-
#import sys
#import os
#f = open('input.txt', 'r')
#sys.stdin = f
#input = sys.stdin.readline
# A　range flip find route

h, w = map(int, input().split())

dp = [[0 for i in range(w)] for j in range(h)]

maze = []
for i in range(h):
    sub = list(input())
    maze.append(sub)

if maze[0][0] == "#":
    dp[0][0] = 1
for i in range(1, w):
    if maze[0][i - 1] == "." and maze[0][i] == "#":
        dp[0][i] = dp[0][i - 1] + 1

    else:
        dp[0][i] = dp[0][i - 1]
for j in range(1, h):
    if maze[j - 1][0] == "." and maze[j][0] == "#":
        dp[j][0] = dp[j - 1][0] + 1
    else:
        dp[j][0] = dp[j - 1][0]

for i in range(1, h):
    for j in range(1, w):
        d = dp[i - 1][j]
        e = dp[i][j - 1]
        if maze[i - 1][j] == "." and maze[i][j] == "#":
            d += 1
        if maze[i][j - 1] == "." and maze[i][j] == "#":
            e += 1
        dp[i][j] = min(d, e)
print(dp[h - 1][w - 1])

Submission status: Accepted

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

dp = [[-1]*W for i in range(H)]
if S[0][0] == "#":
    dp[0][0] = 1
else:
    dp[0][0] = 0
    
for w in range(1,W):
    if S[0][w] == "#" and S[0][w-1] == ".":
        dp[0][w] = dp[0][w-1] + 1
    else:
        dp[0][w] = dp[0][w-1]
        
for h in range(1,H):
    if S[h][0] == "#" and S[h-1][0] == ".":
        dp[h][0] = dp[h-1][0] + 1
    else:
        dp[h][0] = dp[h-1][0]
        
for h in range(1,H):
    for w in range(1,W):
        if S[h][w] == "#" and S[h][w-1] == ".":
            dw = dp[h][w-1] + 1
        else:
            dw = dp[h][w-1]
            
        if S[h][w] == "#" and S[h-1][w] == ".":
            dh = dp[h-1][w] + 1
        else:
            dh = dp[h-1][w]
            
        dp[h][w] = min(dw,dh)
        
print(dp[-1][-1])

Submission status: Accepted

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

dp = []
for i in range(h):
    dp.append([0 for j in range(w)])

def need_or_not(a,b): # aからbに移るときに操作が必要なら1,必要ないなら0
    if a == "." and b == "#":
        return 1
    return 0

for i in range(h):
    for j in range(w):
        if i == 0:
            if j != 0:
                dp[i][j] = dp[i][j-1] + need_or_not(s[i][j-1], s[i][j])
            else:
                if s[0][0] == "#":
                    dp[0][0] = 1
        else:
            if j!= 0:
                dp[i][j] = min(dp[i-1][j] + need_or_not(s[i-1][j], s[i][j]), dp[i][j-1] + need_or_not(s[i][j-1], s[i][j]))
            else:
                dp[i][j] = dp[i-1][j] + need_or_not(s[i-1][j], s[i][j])

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

Submission status: Accepted

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

Submission status: Accepted

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

if maze[0][0] == '#':
    dist[0][0] = 1
else:
    dist[0][0] = 0

for w in range(1, W):
    if maze[0][w-1] == '.' and maze[0][w] == '#':
        dist[0][w] = dist[0][w-1] + 1
    else:
        dist[0][w] = dist[0][w-1]

for h in range(1, H):
    if maze[h-1][0] == '.' and maze[h][0] == '#':
        dist[h][0] = dist[h-1][0] + 1
    else:
        dist[h][0] = dist[h-1][0]

for h in range(1, H):
    for w in range(1, W):
        if maze[h][w-1] == '.' and maze[h][w] == '#':
            dw = dist[h][w-1] + 1
        else:
            dw = dist[h][w-1]
        if maze[h-1][w] == '.' and maze[h][w] == '#':
            dh = dist[h-1][w] + 1
        else:
            dh = dist[h-1][w]
        dist[h][w] = min(dw, dh)

print(dist[-1][-1])

Submission status: Accepted

Solution code:
from itertools import *
from heapq import *

def solve(H, W, grid):
  goal = (H-1, W-1)
  fixed = set()
  candicates = [(grid[0,0], (0, 0))]
  while 1:
    dist, p = heappop(candicates)
    if p == goal:
      return dist
    if p in fixed:
      continue
    fixed.add(p)
    for i in range(2):
      p1 = p[0]+i, p[1]+(1-i)
      if not (p1[0]<H and p1[1]<W) or p1 in fixed:
        continue
      x, y = p
      x1, y1 = p1
      heappush(candicates, (dist+(grid[p1] & ~grid[p]), p1))
  return None

H, W = map(int, input().split())
grid = {(i,j): int(c=="#") for i in range(H) for j, c in enumerate(input())}

print(solve(H, W, grid))

Submission status: Accepted

Solution code:
#!/usr/bin/env python3

import sys

sys.setrecursionlimit(10 ** 6)

class Logger:
	def __init__(self, is_debug):
		self.debug = is_debug
	def print(self, *arg):
		if self.debug:
			print("logger:", *arg)
	def plane(self, lst, sep=" ", space=0):
		if self.debug:
			longest = space
			for i in range(len(lst)):
				for j in range(len(lst[i])):
					longest = max(longest, len(str(lst[i][j])))
			for i in range(len(lst)):
				for j in range(len(lst[i])):
					print("logger:", " "*(longest-len(str(lst[i][j])))+str(lst[i][j]), end=sep)
				print()

def main():
	h, w = map(int, sys.stdin.readline().split())
	s = [list(sys.stdin.readline().rstrip())[::-1] for i in [0]*h][::-1]
	cost = [[0]*w for i in [0]*h]
	for y in range(h):
		for x in range(w):
			if y == 0 and x == 0:
				if s[y][x] == "#":
					cost[y][x] = 1
			elif y == 0:
				if s[y][x] == "#" and s[y][x-1] != "#":
					cost[y][x] = cost[y][x-1] + 1
				else:
					cost[y][x] = cost[y][x-1]
			elif x == 0:
				if s[y][x] == "#" and s[y-1][x] != "#":
					cost[y][x] = cost[y-1][x] + 1
				else:
					cost[y][x] = cost[y-1][x]
			else:
				if s[y][x] == "#" and s[y-1][x] != "#":
					cost[y][x] = cost[y-1][x] + 1
				else:
					cost[y][x] = cost[y-1][x]
				if s[y][x] == "#" and s[y][x-1] != "#":
					cost[y][x] = min(cost[y][x], cost[y][x-1] + 1)
				else:
					cost[y][x] = min(cost[y][x], cost[y][x-1])
	logger = Logger(0)
	logger.print(h, w)
	print(cost[h-1][w-1])

main()

Submission status: Accepted

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

dp = [[float('inf') for _ in range(w)] for _ in range(h)]
if field[0][0] == '#':
    dp[0][0] = 1
else:
    dp[0][0] = 0

for i in range(h):
    for j in range(w):
        for di, dj in ((1, 0), (0, 1)):
            next_i = i + di
            next_j = j + dj
            if next_i >= h or next_j >= w:
                continue
            if field[i][j] == '.' and field[next_i][next_j] == '#':
                dp[next_i][next_j] = min(dp[next_i][next_j], dp[i][j] + 1)
            else:
                dp[next_i][next_j] = min(dp[next_i][next_j], dp[i][j])

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

Submission status: Accepted

Solution code:
h, w = map(int, input().split())
s = [] # h, w
for i in range(h):
    s += [','.join(input()).split(',')]

cost = [[10000 for i in range(w)] for j in range(h)]

# h: j,  w: i - j
for hh in range(h):
    for ww in range(w):
        # 初期地点
        if hh == ww == 0:
            cost[0][0] = 0 if s[0][0] == '.' else 1

        if hh < h - 1:
            if s[hh][ww] == '.' and s[hh + 1][ww] == '#':
                cost[hh + 1][ww] = min(cost[hh][ww] + 1, cost[hh + 1][ww])
            else:
                cost[hh + 1][ww] = min(cost[hh][ww], cost[hh + 1][ww])
        if ww < w - 1:
            if s[hh][ww] == '.' and s[hh][ww + 1] == '#':
                cost[hh][ww + 1] = min(cost[hh][ww] + 1, cost[hh][ww + 1])
            else:
                cost[hh][ww + 1] = min(cost[hh][ww], cost[hh][ww + 1])

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

Submission status: Accepted

Solution code:
# coding: utf-8
# Your code here!

import sys
sys.setrecursionlimit(10**6)
readline = sys.stdin.readline
read = sys.stdin.read

h,w = [int(i) for i in readline().split()]
b = [readline().strip() for _ in range(h)]

INF = 10**9

dp0 = [[INF]*w for _ in range(h)]
#dp1 = [[INF]*w for _ in range(h)]

if b[-1][-1] == "#":
    dp0[-1][-1] = 1
#    dp0[-1][-1] = INF
else:
    dp0[-1][-1] = 0
#    dp1[-1][-1] = 0

for i in range(h-1,-1,-1):
    for j in range(w-1,-1,-1):
        if b[i][j] == "#":
            r = INF
            if i != h-1: r = min(r,dp0[i+1][j] + (1 if b[i+1][j]=="." else 0))
            if j != w-1: r = min(r,dp0[i][j+1] + (1 if b[i][j+1]=="." else 0))
            #dp1[i][j] = min(dp1[i][j],r)
            dp0[i][j] = min(dp0[i][j],r)
            
        else:
            r = INF
            if i != h-1: r = min(r,dp0[i+1][j])
            if j != w-1: r = min(r,dp0[i][j+1])
            dp0[i][j] = min(dp0[i][j],r)
            #dp1[i][j] = min(dp0[i][j],r)


#print(dp0)
#print(dp1)

print(dp0[0][0])
#print(dp0)

Submission status: Accepted

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

inf=float("inf")
ans=[[inf]*W for _ in range(H)]

if s[0][0]==".":
    ans[0][0]=0
else:
    ans[0][0]=1

for i in range(H):
    for j in range(W):
        if j!=W-1:
            if s[i][j]=="." and s[i][j+1]=="#":
                ans[i][j+1]=min(ans[i][j]+1,ans[i][j+1])
            else:
                ans[i][j+1]=min(ans[i][j],ans[i][j+1])
        if i!=H-1:
            if s[i][j]=="." and s[i+1][j]=="#":
                ans[i+1][j]=min(ans[i][j]+1,ans[i+1][j])
            else:
                ans[i+1][j]=min(ans[i][j],ans[i+1][j]) 

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

Submission status: Accepted

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

dp=[[H*W]*W for i in range(H)]
dp[0][0]=0
for i in range(1,W):
    if S[0][i]==S[0][i-1]:
        dp[0][i]=dp[0][i-1]
    else:
        dp[0][i]=dp[0][i-1]+1
for i in range(1,H):
    if S[i][0]==S[i-1][0]:
        dp[i][0]=dp[i-1][0]
    else:
        dp[i][0]=dp[i-1][0]+1

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

if S[0][0]==S[-1][-1] and S[0][0]==".":
    print(dp[-1][-1]//2)
elif S[0][0]==S[-1][-1] and S[0][0]=="#":
    print(dp[-1][-1]//2+1)
else:
    print((dp[-1][-1]+1)//2)

Submission status: Accepted

Solution code:
import itertools
 
H,W=map(int, input().split())
garden=[]
 
for i in range(H):
    garden.append(list(input().replace(".","1").replace("#","0")))
 
dct=[(1,0),(0,1)]
d=[ [i+j for i in range(W)] for j in range(H)]

for i, j in itertools.product(range(H),range(W)):
    color=garden[i][j]
    for each in dct:
        di,dj=each[0],each[1]
        if i+di<H and j+dj< W and  garden[i+di][j+dj]==color:
            d[i+di][j+dj]=min(d[i+di][j+dj],d[i][j])

        elif i+di<H and j+dj< W:
            d[i+di][j+dj]=min(d[i+di][j+dj],d[i][j]+1)

if int(garden[0][0])+int(garden[H-1][W-1])==0:
  print(int((d[H-1][W-1]+1)/2)+1)
else:
  print(int((d[H-1][W-1]+1)/2))

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
import sys, math, itertools, collections, bisect
input = lambda: sys.stdin.buffer.readline().rstrip().decode('utf-8')
inf = float('inf') ;mod = 10**9+7
mans = inf ;ans = 0 ;count = 0 ;pro = 1

dydx4 = ((-1,0),(0,-1),(0,1),(1,0))
h,w = map(int,input().split())
S = [input() for i in range(h)]
dp = [[inf]*w for i 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-1 >= 0:
      if S[i-1][j] == "." and S[i][j] == "#":
        dp[i][j] = min(dp[i][j],dp[i-1][j] + 1)
      else:
        dp[i][j] = min(dp[i][j],dp[i-1][j])

    if j-1 >= 0:
      if S[i][j-1] == "." and S[i][j] == "#":
        dp[i][j] = min(dp[i][j],dp[i][j-1] + 1)
      else:
        dp[i][j] = min(dp[i][j],dp[i][j-1])
print(dp[h-1][w-1])

Submission status: Accepted

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

dp=[[10**9]*w for i in range(h)]
if a[0][0]==".":
    dp[0][0]=0
else:
    dp[0][0]=1
    
for i in range(h):
    for j in range(w):
        if i!=0:
            if a[i-1][j]=="." and a[i][j]=='#':
                dp[i][j]=min(dp[i][j],dp[i-1][j]+1)
            else:
                dp[i][j]=min(dp[i][j],dp[i-1][j])
        if j!=0:
            if a[i][j-1]=="." and a[i][j]=='#':
                dp[i][j]=min(dp[i][j],dp[i][j-1]+1)
            else:
                dp[i][j]=min(dp[i][j],dp[i][j-1])
print(dp[-1][-1])