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:
def print_list(L):
    for i in L:print(i)

h,w = map(int,input().split())
s = []
dp = [[100000]*w for i in range(h)]
for i in range(h):
    tl = input()
    s.append(tl)

dp[0][0] = int(s[0][0] == '#')
for e,i in enumerate(s):
    for f,j in enumerate(i):
        for x,y in [(0,1),(1,0)]:
            if e+x>=h or f+y>=w:
                # print(22,e,f,x,y)
                continue 
            if s[e+x][f+y] == '#':
                dp[e+x][f+y] = min(dp[e][f]+1,dp[e+x][f+y])
            else:
                dp[e+x][f+y]=min(dp[e][f],dp[e+x][f+y])
        
    # print_list(dp)
# print(dp)
print(dp[h-1][w-1])

Submission status: Wrong Answer

Solution code:
a=input()
print(a)

Submission status: Wrong Answer

Solution code:
from heapq import heappop, heappush, heapify

H, W = map(int, input().split())
S = [input() for _ in range(H)]

# moving direction 
dx = [1,0] 
dy = [0,1]

# heap: (counter,x,y) 
heap = [(1, 0, 0)]
heapify(heap)

# memorize visited points
visited = [[0 for j in range(W)] for i in range(H)]
visited[0][0] = 1

while heap: # use BFS and increase counter if the mark is different from the previous one
    c, x, y = heappop(heap) # prioritize a point having less counter
    for i in range(2): # check if go right or down
        nx, ny = x + dx[i], y + dy[i]
        if not (0 <= nx < H and 0 <= ny < W): # check if within the map
            continue
        if visited[nx][ny]: # ignore if already visited
            continue
        if S[x][y] == S[nx][ny]: # if new one is as same as previous one
            visited[nx][ny] = c
            heappush(heap, (c, nx, ny))
        else: # if not same as previous 
            visited[nx][ny] = c + 1
            heappush(heap, (c + 1, nx, ny))
    print(visited)

if S[0][0] == '#':  # if the start is black, increase the counter
    print((visited[-1][-1]+1)//2)
else:
    print(visited[-1][-1]//2)

Submission status: Wrong Answer

Solution code:
h,w=map(int,input().split())
grid=[[1 if s=='#' else 0 for s in list(input())] for i in range(h)]
#print(grid)
maxi=10**5
from collections import deque
visited=[[maxi]*w for _ in range(h)]
def bfs(s):
    q=deque()
    q.append(s)
    visited[s[0]][s[1]]=grid[s[0]][s[1]]
    for r in range(h):
        for c in range(w):
            if r>=1:
                visited[r][c]=min(visited[r][c],visited[r-1][c]+grid[r][c])
            if c>=1:
                visited[r][c]=min(visited[r][c],visited[r][c-1]+grid[r][c])

bfs([0,0])
print(visited[-1][-1])

Submission status: Wrong Answer

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

s=[]

for r in range(H):
    s.append(list(input()))

c=[[200]*W for i in range(H)]
if s[0][0]==".":
    c[0][0]=0
else:
    c[0][0]=1

def rec(y,x):
    if c[y][x]!=200:
        return c[y][x]
    elif y==0 and x!=0:
        temp=rec(y,x-1)
        if s[y][x]!=s[y][x-1]:
            if s[y][x]==".":
                temp+=1
        c[y][x]=temp
        return temp
    elif y!=0 and x==0:
        temp=rec(y-1,x)
        if s[y][x]!=s[y-1][x]:
            if s[y][x]==".":
                temp+=1
        c[y][x]=temp
        return temp
    else:
        temp1 = rec(y, x - 1)
        if s[y][x] != s[y][x-1]:
            if s[y][x] == ".":
                temp1 += 1
        temp2 = rec(y - 1, x)
        if s[y][x] != s[y - 1][x]:
            if s[y][x] == ".":
                temp2 += 1
        temp=min(temp1,temp2)
        c[y][x]=temp
        return temp

ans=rec(H-1,W-1)

print(ans)

Submission status: Wrong Answer

Solution code:
from queue import deque

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

inf = 10**10

dx = [1,0,-1,0]
dy = [0,1,0,-1]
que = deque()

#そのマスにたどり着くまでに色が変わった最小の回数を保存するリスト
flip_count = [[inf for i in range(w)]for j in range(h)]

que.append([0,0])

if li[0][0] == "#":
    flip_count[0][0] = 1
else:
    flip_count[0][0] = 0

# 幅優先探索
while que:
    k = que.popleft()
    y = k[0]
    x = k[1]
    
    for i,j in zip(dx,dy):
        nx = x + i
        ny = y + j

        # 外にはみ出しているか
        if nx < 0 or nx >= w or ny < 0 or ny >= h:
            continue

        if li[ny][nx] != li[y][x]: 
            flip_count[y][x] = min(flip_count[y][x],flip_count[ny][nx]+1)
        else:
            flip_count[y][x] = min(flip_count[y][x],flip_count[ny][nx])

        if flip_count[ny][nx] == inf:
            que.append([ny,nx])
        
if flip_count[-1][-1] == "#":
    flip_count[-1][-1] += 1

print(flip_count[-1][-1]//2)

Submission status: Wrong Answer

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

s=[]

for r in range(H):
    s.append(list(input()))

c=[[200]*W for i in range(H)]
if s[0][0]==".":
    c[0][0]=0
else:
    c[0][0]=1

def rec(y,x):
    if c[y][x]!=200:
        return c[y][x]
    elif y==0 and x!=0:
        temp=rec(y,x-1)
        if s[y][x]=="#":
            temp+=1
        c[y][x]=temp
        return temp
    elif y!=0 and x==0:
        temp=rec(y-1,x)
        if s[y][x]=="#":
            temp+=1
        c[y][x]=temp
        return temp
    else:
        temp=min(rec(y,x-1),rec(y-1,x))
        if s[y][x]=="#":
            temp+=1
        c[y][x]=temp
        return temp

ans=rec(H-1,W-1)

print(ans)

Submission status: Wrong Answer

Solution code:
import numpy as np
import sys
read = sys.stdin.read
readline = sys.stdin.readline
readlines = sys.stdin.readlines
H, W = map(int, input().split())

I = [list(map(str, input())) for _ in range(H)]

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

for i in range(H):
	for j in range(W):
		if i == 0 and j == 0:
			continue
		if i == 0:
			dp[i][j] = dp[i][j-1] if I[i][j] == I[i][j-1] else dp[i][j-1] + 1
			continue
		if j == 0:
			dp[i][j] = dp[i-1][j] if I[i][j] == I[i-1][j] else dp[i-1][j] + 1
			continue

		dp[i][j] = dp[i][j-1] if I[i][j] == I[i][j-1] else dp[i][j-1] + 1
		if I[i][j] == I[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)	

t = dp[-1][-1]
ans = -(-t//2)

if I[0][0] == "#":
	ans += 1

print(ans)

Submission status: Wrong Answer

Solution code:
import numpy as np

def func(x,y):
    if y-x == 2:
        return 1
    else:
        return 0


H,W = map(int,input().split())
l = [input() for i in range(H)]

d = np.zeros((H,W))
dp = np.zeros((H,W))

for i in range(H):
    for j in range(W):
        if l[i][j] == "#":
            d[i][j] = 1
        else:
            d[i][j] = -1

if d[0][0] == 1:
    dp[0][0] = 1
    d *= -1

for i in range(H-1):
    dp[i+1][0] = dp[i][0]+func(d[i][0],d[i+1][0])

for i in range(W-1):
    dp[0][i+1] = dp[0][i]+func(d[0][i],d[0][i+1])

for i in range(H-1):
    for j in range(W-1):
        dp[i+1][j+1]=min(dp[i][j+1]+func(d[i][j+1],d[i+1][j+1]),dp[i+1][j]+func(d[i+1][j],d[i+1][j+1]))

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

Submission status: Wrong Answer

Solution code:
import sys, re, os
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, radians, acos, atan, asin, log, log10
from itertools import permutations, combinations, product, accumulate
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
from fractions import gcd
def debug(*args):
    if debugmode:
        print(*args)
def input(): return sys.stdin.readline().strip()
def STR(): return input()
def INT(): return int(input())
def FLOAT(): return float(input())
def MAP(): return map(int, input().split())
def S_MAP(): return map(str, input().split())
def LIST(): return list(map(int, input().split()))
def S_LIST(): return list(map(str, input().split()))
def lcm(a, b): return a * b // gcd(a, b)
sys.setrecursionlimit(10 ** 9)
inf = sys.maxsize
mod = 10 ** 9 + 7
dx = [0, 1, 0, -1, 1, -1, -1, 1]
dy = [1, 0, -1, 0, 1, -1, 1, -1]
debugmode = True

h, w = MAP()
s = [STR() for _ in range(h)]
memo = [[-1 for _ in range(w)] for _ in range(h)]
memo[-1][-1] = 1 if s[-1][-1] == '#' else 0
for i in reversed(range(h)):
    for j in reversed(range(w)):
        res = 0 if i == h - 1 and j == w - 1 else inf
        for k in range(2):
            if j + dx[k] < w and i + dy[k] < h:
                res = min(res, memo[i + dy[k]][j + dx[k]])
        res += 1 if s[i][j] == '#' else 0
        memo[i][j] = res
print(memo[0][0])


'''
def func(y, x):
    if y == h - 1 and x == w - 1:
        pass
    else:
        res = inf
        for i in range(2):
            if x + dx[i] < w and y + dy[i] < h:
                tmp = 1 if s[y][x] == '#' else 0
                if memo[y + dy[i]][x + dx[i]] == -1:
                    func(y + dy[i], x + dx[i])
                res = min(res, memo[y + dy[i]][x + dx[i]] + tmp)
        memo[y][x] = res
'''

Submission status: Wrong Answer

Solution code:
import sys, re, os
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, radians, acos, atan, asin, log, log10
from itertools import permutations, combinations, product, accumulate
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
from fractions import gcd
def debug(*args):
    if debugmode:
        print(*args)
def input(): return sys.stdin.readline().strip()
def STR(): return input()
def INT(): return int(input())
def FLOAT(): return float(input())
def MAP(): return map(int, input().split())
def S_MAP(): return map(str, input().split())
def LIST(): return list(map(int, input().split()))
def S_LIST(): return list(map(str, input().split()))
def lcm(a, b): return a * b // gcd(a, b)
sys.setrecursionlimit(10 ** 9)
inf = sys.maxsize
mod = 10 ** 9 + 7
dx = [0, 1, 0, -1, 1, -1, -1, 1]
dy = [1, 0, -1, 0, 1, -1, 1, -1]
debugmode = True

h, w = MAP()
s = [STR() for _ in range(h)]
memo = [[-1 for _ in range(w)] for _ in range(w)]
memo[-1][-1] = 1 if s[-1][-1] == '#' else 0
for i in reversed(range(h)):
    for j in reversed(range(w)):
        res = 0 if i == h - 1 and j == w - 1 else inf
        for k in range(2):
            if j + dx[k] < w and i + dy[k] < h:
                res = min(res, memo[i + dy[k]][j + dx[k]])
        res += 1 if s[i][j] == '#' else 0
        memo[i][j] = res
print(memo[0][0])

Submission status: Wrong Answer

Solution code:
import sys, re, os
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, radians, acos, atan, asin, log, log10
from itertools import permutations, combinations, product, accumulate
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
from fractions import gcd
def debug(*args):
    if debugmode:
        print(*args)
def input(): return sys.stdin.readline().strip()
def STR(): return input()
def INT(): return int(input())
def FLOAT(): return float(input())
def MAP(): return map(int, input().split())
def S_MAP(): return map(str, input().split())
def LIST(): return list(map(int, input().split()))
def S_LIST(): return list(map(str, input().split()))
def lcm(a, b): return a * b // gcd(a, b)
sys.setrecursionlimit(10 ** 9)
inf = sys.maxsize
mod = 10 ** 9 + 7
dx = [0, 1, 0, -1, 1, -1, -1, 1]
dy = [1, 0, -1, 0, 1, -1, 1, -1]
debugmode = True

def func(y, x):
    if y == h - 1 and x == w - 1:
        pass
    else:
        res = inf
        for i in range(2):
            if x + dx[i] < w and y + dy[i] < h:
                tmp = 1 if s[y][x] == '#' else 0
                if memo[y + dy[i]][x + dx[i]] == -1:
                    func(y + dy[i], x + dx[i])
                res = min(res, memo[y + dy[i]][x + dx[i]] + tmp)
        memo[y][x] = res

h, w = MAP()
s = [STR() for _ in range(h)]
memo = [[-1 for _ in range(w)] for _ in range(w)]
memo[-1][-1] = 1 if s[h - 1][w - 1] == '#' else 0
func(0, 0)
print(memo[0][0])

Submission status: Wrong Answer

Solution code:
import sys, re, os
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, radians, acos, atan, asin, log, log10
from itertools import permutations, combinations, product, accumulate
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
from fractions import gcd
def debug(*args):
    if debugmode:
        print(*args)
def input(): return sys.stdin.readline().strip()
def STR(): return input()
def INT(): return int(input())
def FLOAT(): return float(input())
def MAP(): return map(int, input().split())
def S_MAP(): return map(str, input().split())
def LIST(): return list(map(int, input().split()))
def S_LIST(): return list(map(str, input().split()))
def lcm(a, b): return a * b // gcd(a, b)
sys.setrecursionlimit(10 ** 9)
inf = sys.maxsize
mod = 10 ** 9 + 7
dx = [0, 1, 0, -1, 1, -1, -1, 1]
dy = [1, 0, -1, 0, 1, -1, 1, -1]
debugmode = True

def func(y, x):
    if y == h - 1 and x == w - 1:
        tmp = 0 if s[-1][-1] == '.' else 1
        memo[-1][-1] = tmp
    else:
        res = inf
        for i in range(2):
            if x + dx[i] < w and y + dy[i] < h:
                tmp = 0 if s[y][x] == '.' else 1
                if memo[y + dy[i]][x + dx[i]] == -1:
                    func(y + dy[i], x + dx[i])
                res = min(res, memo[y + dy[i]][x + dx[i]] + tmp)
        memo[y][x] = res

h, w = MAP()
s = [STR() for _ in range(h)]
memo = [[-1 for _ in range(w)] for _ in range(w)]
memo[-1][-1] = 1 if s[h - 1][w - 1] == '#' else 0
func(0, 0)
print(memo[0][0])

Submission status: Wrong Answer

Solution code:
H,W,*L = open(0).read().split()
H,W = map(int, (H,W))
dp = [[0]*W for i in range(H)]
for i in range(1,H):
  if L[i][0]!=L[i-1][0]:
    dp[i][0] = dp[i-1][0]+1
  else:
    dp[i][0] = dp[i-1][0]
for j in range(1,W):
  if L[0][j]!=L[0][j-1]:
    dp[0][j] = dp[0][j-1]+1
  else:
    dp[0][j] = dp[0][j-1]
for i in range(1,H):
  for j in range(1,W):
    if L[i][j]!=L[i-1][j] and L[i][j]!=L[i][j-1]:
      dp[i][j] = min(dp[i-1][j],dp[i][j-1])+1
    elif L[i][j]!=L[i-1][j]:
      dp[i][j] = min(dp[i-1][j]+1,dp[i][j-1])
    elif L[i][j]!=L[i][j-1]:
      dp[i][j] = min(dp[i-1][j],dp[i][j-1]+1)
    else:
      dp[i][j] = min(dp[i-1][j],dp[i][j-1])
ans = dp[H-1][W-1]//2 if L[0][0]=='.' else dp[H-1][W-1]//2+1
print(ans)

Submission status: Wrong Answer

Solution code:
H,W,*L = open(0).read().split()
H,W = map(int, (H,W))
dp = [[0]*W for i in range(H)]
if L[0][0]=='#':
  dp[0][0] = 1
for i in range(1,H):
  if L[i][0]=='#':
    dp[i][0] = dp[i-1][0]+1
  else:
    dp[i][0] = dp[i-1][0]
for j in range(1,W):
  if L[0][j]=='#':
    dp[0][j] = dp[0][j-1]+1
  else:
    dp[0][j] = dp[0][j-1]
for i in range(1,H):
  for j in range(1,W):
    if L[i][j]=='#':
      dp[i][j] = min(dp[i-1][j],dp[i][j-1])+1
    else:
      dp[i][j] = min(dp[i-1][j],dp[i][j-1])
print(dp[H-1][W-1])

Submission status: Wrong Answer

Solution code:
h,w=map(int,input().split())
dp=[[0]*w for i in range(h)]
s=input()
for i in range(w):
    if s[i]=="#":
        dp[0][i]=dp[0][i-1]+1
    else:
        dp[0][i]=dp[0][i-1]
for i in range(1,h):
    s=input()
    for j in range(w):
        if j==0:
            if s[j]=="#":
                dp[i][j]=dp[i-1][j]+1
            else:
                dp[i][j]=dp[i-1][j]
            continue
        if s[j]=="#":
            dp[i][j]=min(dp[i-1][j],dp[i][j-1])+1
        else:
            dp[i][j]=min(dp[i-1][j],dp[i][j-1])
print(dp[-1][-1])

Submission status: Wrong Answer

Solution code:
from heapq import heappush, heappop

H, W = map(int, input().split())
s = [[i == '.' for i in input()] for _ in range(H)]

dist = [[float('inf')] * W for _ in range(H)]
dist[0][0] = 0

h = [(0, 0, 0)]
while h :
  cc, cy, cx = heappop(h)
  for dy, dx in ((1, 0), (0, 1)) :
    ny, nx = cy + dy, cx + dx
    if 0 <= ny < H and 0 <= nx < W :
      nc = cc + (s[ny][nx] != s[cy][cx])
      if nc < dist[ny][nx] :
        heappush(h, (nc, ny, nx))
        dist[ny][nx] = nc
        
print((dist[H-1][W-1] + 1) // 2 + 1 - s[0][0])

Submission status: Wrong Answer

Solution code:
from heapq import heappush, heappop

H, W = map(int, input().split())
s = [[i == '.' for i in input()] for _ in range(H)]

dist = [[float('inf')] * W for _ in range(H)]
dist[0][0] = 0

h = [(0, 0, 0)]
while h :
  cc, cy, cx = heappop(h)
  for dy, dx in ((1, 0), (0, 1)) :
    ny, nx = cy + dy, cx + dx
    if 0 <= ny < H and 0 <= nx < W :
      nc = cc + (s[ny][nx] != s[cy][cx])
      if nc < dist[ny][nx] :
        heappush(h, (nc, ny, nx))
        dist[ny][nx] = nc
        
print(dist[H-1][W-1] // 2 + 1 - s[0][0])

Submission status: Wrong Answer

Solution code:
h, w = map(int, input().split())
s = [[1 if i == "#" else 0 for i in input()] for _ in range(h)]
dp = [[0 for _ in range(w)] for _ in range(h)]
dp[0][0] += s[0][0]
for wi in range(1, w):
    dp[0][wi] = s[0][wi] + dp[0][wi-1]
for hi in range(1, h):
    dp[hi][0] = dp[hi-1][0] + s[hi][0]
    for wi in range(1, w):
        dp[hi][wi] = min(dp[hi-1][wi] + s[hi][wi], dp[hi][wi-1] + s[hi][wi])
print(dp[h-1][w-1])

Submission status: Wrong Answer

Solution code:
import math  # noqa
import bisect  # noqa
import queue  # noqa


if __name__ == '__main__':
    H, W = map(int, input().split())
    S = [[s for s in input()] for _ in range(H)]

    INF = 1000000005
    traj = [[INF for _ in range(W)] for _ in range(H)]
    que = queue.Queue()
    que.put((0, 0))
    traj[0][0] = 0 if S[0][0] == '.' else 1
    while not que.empty():
        h, w = que.get()
        d = ((1, 0), (0, 1), (-1, 0), (0, -1))
        for dh, dw in d:
            nh = h + dh
            nw = w + dw
            if nh < 0 or H <= nh or nw < 0 or W <= nw:
                continue
            cost = traj[h][w]
            if S[h][w] == '.' and S[nh][nw] == '#':
                cost += 1
            if cost < traj[nh][nw]:
                traj[nh][nw] = cost
                que.put((nh, nw))

    print(traj[-1][-1])

Submission status: Wrong Answer

Solution code:
import math  # noqa
import bisect  # noqa
import queue  # noqa


if __name__ == '__main__':
    H, W = map(int, input().split())
    S = [[s for s in input()] for _ in range(H)]

    INF = 1000000005
    traj = [[INF for _ in range(W)] for _ in range(H)]
    que = queue.Queue()
    que.put((0, 0))
    traj[0][0] = 0 if S[0][0] == '.' else 1
    while not que.empty():
        h, w = que.get()
        d = ((1, 0), (0, 1), (-1, 0), (0, -1))
        for dh, dw in d:
            nh = h + dh
            nw = w + dw
            if nh < 0 or H <= nh or nw < 0 or W <= nw:
                continue
            cost = traj[h][w]
            if S[nh][nw] == '#':
                cost += 1
            if cost < traj[nh][nw]:
                traj[nh][nw] = cost
                que.put((nh, nw))

    print(traj[-1][-1])

Submission status: Wrong Answer

Solution code:
import itertools
H,W  = list(map(int,input().split(" ")))
maze = [input() for _ in range(H)]
MAX = 10 ** 10
dp = [[MAX] * W for _ in range(H)  ]
dp[0][0] =1 if maze[0][0] == "#" else 0
for h in range(H):
    for w in range(W):
        # 上からの移動がありうるか判定
        add = 1 if maze[h][w] == "#" else 0
        if   0 < h :
            dp[h][w] = min(dp[h][w], add + dp[h - 1][w])
        if 0 < w:
            dp[h][w] = min(dp[h][w], add + dp[h][w - 1])
print(dp[-1][-1])

Submission status: Wrong Answer

Solution code:
# python3.4.2用
import math
import fractions
import bisect
import collections
import itertools
import heapq
import string
import sys
import copy
from decimal import *
from collections import deque
sys.setrecursionlimit(10**7)
MOD = 10**9+7
INF = float('inf') #無限大
def gcd(a,b):return fractions.gcd(a,b) #最大公約数
def lcm(a,b):return (a*b) // fractions.gcd(a,b) #最小公倍数
def iin(): return int(sys.stdin.readline()) #整数読み込み
def ifn(): return float(sys.stdin.readline()) #浮動小数点読み込み
def isn(): return sys.stdin.readline().split() #文字列読み込み
def imn(): return map(int, sys.stdin.readline().split()) #整数map取得
def imnn(): return map(lambda x:int(x)-1, sys.stdin.readline().split()) #整数-1map取得
def fmn(): return map(float, sys.stdin.readline().split()) #浮動小数点map取得
def iln(): return list(map(int, sys.stdin.readline().split())) #整数リスト取得
def iln_s(): return sorted(iln()) # 昇順の整数リスト取得
def iln_r(): return sorted(iln(), reverse=True) # 降順の整数リスト取得
def fln(): return list(map(float, sys.stdin.readline().split())) # 浮動小数点リスト取得
def join(l, s=''): return s.join(l) #リストを文字列に変換
def perm(l, n): return itertools.permutations(l, n) # 順列取得
def perm_count(n, r): return math.factorial(n) // math.factorial(n-r) # 順列の総数
def comb(l, n): return itertools.combinations(l, n) # 組み合わせ取得
def comb_count(n, r): return math.factorial(n) // (math.factorial(n-r) * math.factorial(r)) #組み合わせの総数
def two_distance(a, b, c, d): return ((c-a)**2 + (d-b)**2)**.5 # 2点間の距離
def m_add(a,b): return (a+b) % MOD
def lprint(l): print(*l, sep='\n')
def sieves_of_e(n):
    is_prime = [True] * (n+1)
    is_prime[0] = False
    is_prime[1] = False
    for i in range(2, int(n**0.5)+1):
        if not is_prime[i]: continue
        for j in range(i * 2, n+1, i): is_prime[j] = False
    return is_prime

H,W = imn()

s = [input() for _ in range(H)]
d = [[INF for _ in range(W)] for _ in range(H)]
d[0][0] = 0
if s[0][0] == '#': d[0][0] = 1

xd = [1, 0]
yd = [0, 1]
que = deque([(0, 0)])
cnt = 0
while len(que) > 0:
    cnt += 1
    point = que.popleft()
    x = point[0]
    y = point[1]
    if x == W-1 and y == H-1: continue
    for i in range(2):
        nx = x + xd[i]
        ny = y + yd[i]
        if nx >= W or ny >= H: continue
        if s[ny][nx] == '#': 
            if d[ny][nx] > d[y][x]+1:
                d[ny][nx] = d[y][x]+1
                que.append((nx,ny))
        else:
            if d[ny][nx] > d[y][x]:
                d[ny][nx] = d[y][x]
                que.append((nx,ny))
print(d[H-1][W-1])

Submission status: Wrong Answer

Solution code:
h,w = map(int,input().split())
s = [list(str(input())) for i in range(h)]
dp = [[10 ** 10] * w for i in range(h)]
if s[0][0] == "#":dp[0][0] = 1
else:dp[0][0] = 0
for i in range(w):
    for j in range(h):
        if s[j][i] == "#":
            s[j][i] = 1
        else:
            s[j][i] = 0
for i in range(1,h+w-1):
    for j in range(i+1):
        if 0 < j < h and 0 <= i-j < w:
            dp[j][i-j] = min(dp[j-1][i-j]+s[j][i-j],dp[j][i-j])
        if 0 < i-j < w and 0 <= j < h:
            dp[j][i-j] = min(dp[j][i-j-1]+s[j][i-j],dp[j][i-j])
print(dp[h-1][w-1])

Submission status: Wrong Answer

Solution code:
h,w = map(int,input().split())
s = [list(str(input())) for i in range(h)]
if s[0][0] == "#":
    s[0][0] = "."
    now = {(0,0,1)}
else:
    now = {(0,0,0)}
ans = 10000
for turn in range(h + w -2):
    gone = set()
    for y,x,cnt in now:
        if y+1 < h:
            if s[y+1][x] == "#":
                gone.add((y+1,x,cnt+1))
            else:
                gone.add((y+1,x,cnt))
        if x+1 < w:
            if s[y][x+1] == "#":
                gone.add((y,x+1,cnt+1))
            else:
                gone.add((y,x+1,cnt))
    now = gone
for y,x,cnt in now:
    if y == h-1 and x == w-1:
        ans = min(ans,cnt)
print(ans)

Submission status: Wrong Answer

Solution code:
import sys

sys.setrecursionlimit(10 ** 7)
rl = sys.stdin.readline


def solve():
    H, W = map(int, rl().split())
    s = [list(input()) for _ in range(H)]
    
    dp = [[0] * W for _ in range(H)]
    dp[0][0] = s[0][0] == '#'
    for i in range(1, W):
        dp[0][i] = dp[0][i - 1] + (s[0][i - 1] == '.' and s[0][i] == '#')
    for i in range(1, H):
        dp[i][0] = dp[i - 1][0] + (s[i - 1][0] == '.' and s[i][0] == '#')
    
    for i in range(1, H):
        for j in range(1, W):
            dy = s[i - 1][j] == '.' and s[i][j] == '#'
            dx = s[i][j - 1] and s[i][j] == '#'
            dp[i][j] = min(dp[i - 1][j] + dy, dp[i][j - 1] + dx)
    print(dp[-1][-1])


if __name__ == '__main__':
    solve()

Submission status: Wrong Answer

Solution code:
import sys

sys.setrecursionlimit(10 ** 7)
rl = sys.stdin.readline


def solve():
    H, W = map(int, rl().split())
    s = [list(input()) for _ in range(H)]
    
    dp = [[0] * W for _ in range(H)]
    dp[0][0] = s[0][0] == '#'
    for i in range(1, W):
        dp[0][i] = dp[0][i - 1] + (s[0][i] == '#')
    for i in range(1, H):
        dp[i][0] = dp[i - 1][0] + (s[i][0] == '#')
    
    for i in range(1, H):
        for j in range(1, W):
            dp[i][j] = min(dp[i - 1][j], dp[i][j - 1]) + (s[i][j] == '#')
    print(dp[-1][-1])


if __name__ == '__main__':
    solve()

Submission status: Wrong Answer

Solution code:
h, w = map(int, input().split())

def banpei_grid(H,W):
   S = ["#" * (W + 2)]
   for i in range(H):
       S += ["#" + input()+ "#"]
   S += ["#" * (W + 2)]
   return S

s = banpei_grid(h, w)

INF = float("inf")
table = [[INF for i in range(w+1)] for j in range(h+1)]
table[1][1] = 1 if s[1][1] == "#" else 0

from itertools import product
for i, j in product(range(h), range(w)):
    if i == 0 and j == 0:
        continue
    i += 1
    j += 1
    table[i][j] = min(table[i-1][j], table[i][j-1])

    if s[i][j] == "#":
        table[i][j] += 1

print(table[h][w])

Submission status: Wrong Answer

Solution code:
h, w = map(int, input().split())

def banpei_grid(H,W):
   S = ["#" * (W + 2)]
   for i in range(H):
       S += ["#" + input()+ "#"]
   S += ["#" * (W + 2)]
   return S

s = banpei_grid(h, w)
print(s)
INF = float("inf")
table = [[INF for i in range(w+1)] for j in range(h+1)]

print(table)

table[1][1] = 1 if s[1][1] == "#" else 0
print(table)
from itertools import product
for i, j in product(range(h), range(w)):
    if i == 0 and j == 0:
        continue
    i += 1
    j += 1
    table[i][j] = min(table[i-1][j], table[i][j-1])

    if s[i][j] == "#":
        table[i][j] += 1

print(table[h][w])

Submission status: Wrong Answer

Solution code:
# coding: utf-8
# Your code here!
H,W=map(int,input().split())

meizu=[]
for _ in range(H):
    meizu.append(list(input()))

dp=[[10**9 for w in range(W)] for h in range(H)]
dp[0][0]=1 if meizu[0][0]=="#" else 0

for h in range(H):
    for w in range(W):
        if h!=H-1:
            dp[h+1][w]=min(dp[h+1][w],dp[h][w]+1 if meizu[h+1][w]=="#" else dp[h][w])
        if w!=W-1:
            dp[h][w+1]=min(dp[h][w+1],dp[h][w]+1 if meizu[h][w+1]=="#" else dp[h][w])
    
print(dp[-1][-1])

Submission status: Wrong Answer

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

# スタート地点が黒の場合、始めからカウント1が追加される
if masu[0][0] == '#':
    dp[0][0] = 1

for i in range(H):
    for j in range(W):
        # i=0（1行目）は上から進入することは付加
        # よってa（上の行からきた場合のコスト）はfloatと仮置き
        if i==0:
            a = float('inf')
        else:
            # 白から黒に切り替わった場合、+1
            if masu[i][j]=='#' and masu[i-1][j]=='.':
                a = dp[i-1][j] + 1
            # 色が連続していたり、黒から白に変わった場合はカウントなし
            else:
                a = dp[i-1][j]
        # j=0（1列目）は左から進入することは付加
        # よってb（左の列からきた場合のコスト）はfloatと仮置き
        if j==0:
            b = float('inf')
        else:
            # 白から黒に切り替わった場合、+1
            if masu[i][j]=="#" and masu[i][j-1]==".":
                b = dp[i][j-1] + 1
            # 色が連続していたり、黒から白に変わった場合はカウントなし
            else:
                b = dp[i][j-1]
        if a!=float('inf') or b!=float('inf'):
            dp[i][j] = min(a, b)

        print(dp)
    
print()
print(dp)

Submission status: Wrong Answer

Solution code:
# A - Range Flip Find Route
h,w=map(int,input().split())
s=[input() for i in range(h)]
dp=[[0]*(w+1) for i in range(h+1)]

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

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

Submission status: Wrong Answer

Solution code:
'''input
5 5
.#.#.
#.#.#
.#.#.
#.#.#
.#.#.
'''

import sys
import math
from collections import Counter

debug = 0
readln = sys.stdin.readline
#sys.setrecursionlimit(1000000)

def write(s):
    sys.stdout.write(str(s))

def writeln(s):
    sys.stdout.write(str(s))
    sys.stdout.write('\n')

def readint():
    return int(readln().strip())

def readints():
    return map(int, readln().split())

def readstr():
    return readln().strip()

def readstrs():
    return readln().split()

def dbg(*args):
    if debug: print(' '.join(map(str, args)))


h,w = readints()
mat = []
dp = [[0] * w for _ in xrange(h)]
for _ in xrange(h):
    mat.append(readstr())

def getdp(r, c, cur):
    if r < 0 and c == 0 or c < 0 and r == 0:
        old = 0
    elif r < 0 or c < 0:
        return 2**31
    else:
        old = dp[r][c]

    if cur == '#' and mat[r][c] == '.':
        return old + 1
    else:
        return old

def solve(h, w):
    global dp
    for r in xrange(h):
        for c in xrange(w):
            cur = mat[r][c]
            dp[r][c] = min(getdp(r-1, c, cur), getdp(r, c-1, cur))
    dbg(dp)
    return dp[h-1][w-1]

print solve(h, w)

Submission status: Wrong Answer

Solution code:
'''input
5 5
.#.#.
#.#.#
.#.#.
#.#.#
.#.#.
'''

import sys
import math
from collections import Counter

debug = 0
readln = sys.stdin.readline
#sys.setrecursionlimit(1000000)

def write(s):
    sys.stdout.write(str(s))

def writeln(s):
    sys.stdout.write(str(s))
    sys.stdout.write('\n')

def readint():
    return int(readln().strip())

def readints():
    return map(int, readln().split())

def readstr():
    return readln().strip()

def readstrs():
    return readln().split()

def dbg(*args):
    if debug: print(' '.join(map(str, args)))


h,w = readints()
mat = []
dp = [[0] * w for _ in xrange(h)]
for _ in xrange(h):
    mat.append(readstr())

def getdp(r, c, cur):
    if r < 0 and c == 0 or c < 0 and r == 0:
        old = 0
    elif r < 0 or c < 0:
        old = 2**31
    else:
        old = dp[r][c]

    if cur == '#' and mat[r][c] == '.':
        return old + 1
    else:
        return old

def solve(h, w):
    global dp
    for r in xrange(h):
        for c in xrange(w):
            cur = mat[r][c]
            dp[r][c] = min(getdp(r-1, c, cur), getdp(r, c-1, cur))
    dbg(dp)
    return dp[h-1][w-1]

print solve(h, w)