AtCoder Grand Contest 043 - Range Flip Find Route

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.

Examples

Input

3 3
.##
.#.
##.


Output

1


Input

3 3
.##
.#.
.


Output

1


Input

2 2
.
.#


Output

2


Input

4 4
..##
...
.
.


Output

0


Input

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


Output

4

Source: atcoder | Difficulty: UNKNOWN_DIFFICULTY


Solutions:
(h, w) = map(int, input().split())
s = [list(input()) for _ in range(h)]
dp = [[h * w] * w for _ in range(h)]
dp[0][0] = 0 if s[0][0] == '.' else 1
for x0 in range(w):
	for y0 in range(h):
		for (i, j) in [(0, 1), (1, 0)]:
			x = x0 + i
			y = y0 + j
			if x < w and y < h:
				n = 1 if s[y0][x0] == '.' and s[y][x] == '#' else 0
				dp[y][x] = min(dp[y0][x0] + n, dp[y][x])
print(dp[-1][-1])


import sys
input = sys.stdin.readline
(H, W) = map(int, input().split())
S = [list(input()) for i in range(H)]
dp = [0] * W
if S[0][0] == '#':
	dp[0] = 1
for j in range(1, W):
	if S[0][j] != S[0][j - 1] and S[0][j - 1] == '.':
		dp[j] = dp[j - 1] + 1
	else:
		dp[j] = dp[j - 1]
for i in range(1, H):
	if S[i][0] != S[i - 1][0] and S[i - 1][0] == '.':
		dp[0] = dp[0] + 1
	for j in range(1, W):
		hidari = 1 if S[i][j] != S[i][j - 1] and S[i][j - 1] == '.' else 0
		ue = 1 if S[i][j] != S[i - 1][j] and S[i - 1][j] == '.' else 0
		dp[j] = min(dp[j - 1] + hidari, dp[j] + ue)
print(dp[-1])


(H, W) = map(int, input().split())
grid = [input() for _ in range(H)]
dp = [[10 ** 9] * (W + 1) for _ in range(H + 1)]
dp[0][1] = dp[1][0] = 0
for i in range(1, H + 1):
	for j in range(1, W + 1):
		if grid[i - 1][j - 1] == '.':
			dp[i][j] = min(dp[i - 1][j], dp[i][j - 1])
		else:
			dp[i][j] = min(dp[i - 1][j], dp[i][j - 1]) + 1
			if i >= 2 and grid[i - 2][j - 1] == '#':
				dp[i][j] = min(dp[i][j], dp[i - 1][j])
			if j >= 2 and grid[i - 1][j - 2] == '#':
				dp[i][j] = min(dp[i][j], dp[i][j - 1])
print(dp[-1][-1])


(h, w) = map(int, input().split())
s = [input() for _ in range(h)]
dp = [[0] * w for _ in range(h)]
if s[0][0] == '#':
	dp[0][0] = 1
for i in range(h):
	for j in range(w):
		if (i == 0) & (j != 0):
			dp[i][j] = dp[i][j - 1] + (s[i][j - 1] != s[i][j]) * 1
		elif (i != 0) & (j == 0):
			dp[i][j] = dp[i - 1][j] + (s[i - 1][j] != s[i][j]) * 1
		elif (i != 0) & (j != 0):
			dp[i][j] = min(dp[i][j - 1] + (s[i][j - 1] != s[i][j]) * 1, dp[i - 1][j] + (s[i - 1][j] != s[i][j]) * 1)
ans = (dp[-1][-1] + 1) // 2
print(ans)


import collections
(h, w) = [int(_) for _ in input().split()]
S = [list('.' * (w + 1))] + [['.'] + list(input()) for _ in range(h)]
B = [[99999] * (w + 1) for _ in range(h + 1)]
B[1][1] = 0 if S[1][1] == '.' else 1
cand = collections.deque([(1, 2), (2, 1)])
while cand:
	(x, y) = cand.popleft()
	if B[x][y] == 99999:
		B[x][y] = min(B[x][y - 1] + (S[x][y] == '#' != S[x][y - 1]), B[x - 1][y] + (S[x][y] == '#' != S[x - 1][y]))
		if x < h:
			cand += [(x + 1, y)]
		if y < w:
			cand += [(x, y + 1)]
print(B[-1][-1])


def main():
	import sys
	input = sys.stdin.buffer.readline
	(h, w) = map(int, input().split())
	(b, q) = (b'.' * w, range(w))
	for i in range(h):
		s = input()
		a = []
		for (x, y, z, c) in zip(b, b'.' + s, s, q):
			c += x == 46 > z
			i += y == 46 > z
			if i > c:
				i = c
			a += (i,)
		(b, q) = (s, a)
	print(i)
main()


(h, w) = map(int, input().split())
map1 = [list(input()) for _ in range(h)]
check_board = [[9000000000.0] * w for _ in range(h)]
for x in range(h):
	for y in range(w):
		map1[x][y] = 1 if map1[x][y] == '#' else 0
check_board[0][0] = map1[0][0]

def cal_ans(a, b, x, y):
	return ((map1[a][b] ^ map1[x][y]) & map1[a][b]) + check_board[x][y]
for x in range(h):
	for y in range(w):
		if x < h - 1:
			check_board[x + 1][y] = min(check_board[x + 1][y], cal_ans(x + 1, y, x, y))
		if y < w - 1:
			check_board[x][y + 1] = min(check_board[x][y + 1], cal_ans(x, y + 1, x, y))
print(check_board[-1][-1])


(h, w) = map(int, input().split())
m = [[1 if c == '#' else 0 for c in input()] for _ in range(h)]
n = [i[:] for i in m]
for i in range(1, h):
	n[i][0] = n[i - 1][0] + int(m[i - 1][0] - n[i][0] == -1)
for j in range(1, w):
	n[0][j] = n[0][j - 1] + int(m[0][j - 1] - n[0][j] == -1)
for i in range(1, h):
	for j in range(1, w):
		n[i][j] = min(n[i - 1][j] + int(m[i - 1][j] - n[i][j] == -1), n[i][j - 1] + int(m[i][j - 1] - n[i][j] == -1))
print(n[-1][-1])


def f(c):
	if c == '#':
		ret = 1
	else:
		ret = 0
	return ret
(h, w) = map(int, input().split())
s = [list(map(f, '#' * (w + 1)))]
for _ in range(h):
	s.append([1] + list(map(f, input())))
INF = 100 * 100
dp = [[[INF] * 2 for _ in range(w + 1)] for _ in range(h + 1)]
dp[1][1][s[1][1]] = s[1][1]
for (i, (row_u, row)) in enumerate(zip(s, s[1:]), 1):
	for (j, (el, eu, e)) in enumerate(zip(row, row_u[1:], row[1:]), 1):
		dp[i][j][e] = min(dp[i][j][e], dp[i - 1][j][eu] + (eu + e) % 2, dp[i][j - 1][el] + (el + e) % 2)
ans = dp[h][w][s[h][w]]
ans = (ans + 1) // 2
print(ans)


(h, w) = map(int, input().split())
s = [input() for _ in range(h)]
d = [[1000000] * w for _ in range(h)]
d[0][0] = 0
for i in range(h):
	for j in range(w):
		if i < h - 1:
			d[i + 1][j] = min(d[i + 1][j], d[i][j] + (1 if s[i][j] != s[i + 1][j] else 0))
		if j < w - 1:
			d[i][j + 1] = min(d[i][j + 1], d[i][j] + (1 if s[i][j] != s[i][j + 1] else 0))
ans = d[h - 1][w - 1]
if s[0][0] == '#':
	ans += 1
if s[h - 1][w - 1] == '#':
	ans += 1
print(ans // 2)


(h, w) = map(int, input().split())
S = [input() for _ in range(h)]
dp = [[0] * w for _ in range(h)]
if S[0][0] == '#':
	dp[0][0] = 1
for y in range(1, h):
	dp[y][0] = dp[y - 1][0] + 1 if S[y][0] == '#' and S[y - 1][0] == '.' else dp[y - 1][0]
for x in range(1, w):
	dp[0][x] = dp[0][x - 1] + 1 if S[0][x] == '#' and S[0][x - 1] == '.' else dp[0][x - 1]
for y in range(1, h):
	for x in range(1, w):
		a = dp[y - 1][x] + 1 if S[y][x] == '#' and S[y - 1][x] == '.' else dp[y - 1][x]
		b = dp[y][x - 1] + 1 if S[y][x] == '#' and S[y][x - 1] == '.' else dp[y][x - 1]
		dp[y][x] = min(a, b)
print(dp[h - 1][w - 1])


INF = 10 ** 9
(H, W) = map(int, input().split())
s = [list(input()) for _ in range(H)]
dp = [[INF 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 j != 0:
			cnt = 0
			if s[i][j] == '#' and s[i][j - 1] == '.':
				cnt += 1
			dp[i][j] = min(dp[i][j], dp[i][j - 1] + cnt)
		if i != 0:
			cnt = 0
			if s[i][j] == '#' and s[i - 1][j] == '.':
				cnt += 1
			dp[i][j] = min(dp[i][j], dp[i - 1][j] + cnt)
print(dp[-1][-1])


(H, W) = map(int, input().split())
S = [input() for i in range(H)]
from collections import deque
q = deque([(0, 0, 0)])
v = [[-1] * W for i in range(H)]
v[0][0] = 0
x = [(0, 1), (1, 0)]
while q:
	(i, j, d) = q.popleft()
	for (a, b) in x:
		if 0 <= i + a < H and 0 <= j + b < W and (v[i + a][j + b] < 0):
			if S[i + a][j + b] == S[i][j]:
				q.appendleft((i + a, j + b, d))
				v[i + a][j + b] = d
			else:
				q.append((i + a, j + b, d + 1))
				v[i + a][j + b] = d + 1
print(v[-1][-1] // 2 + (S[0][0] == '#' or S[-1][-1] == '#'))


import math
(h, w) = map(int, input().split())
g = [list(input()) for _ in range(h)]
dp = [[float('inf')] * w for _ in range(h)]
if g[0][0] == '.':
	dp[0][0] = 0
else:
	dp[0][0] = 1
for i in range(h):
	for j in range(w):
		for (di, dj) in zip((0, 1), (1, 0)):
			(ni, nj) = (i + di, j + dj)
			if ni >= h or nj >= w:
				continue
			if g[ni][nj] != g[i][j]:
				dp[ni][nj] = min(dp[ni][nj], dp[i][j] + 1)
			else:
				dp[ni][nj] = min(dp[ni][nj], dp[i][j])
print(math.ceil(dp[h - 1][w - 1] / 2))


def main():
	import sys
	b = sys.stdin.buffer
	(h, w) = map(int, b.readline().split())
	x = w + 1
	s = [5 - c // 8 for c in b.read()]
	dp = [10000] * h * x
	dp[0] = a = b = p = q = s[0]
	for i in range(w):
		t = s[i]
		b += a ^ t
		dp[i] = b
		a = t
	for i in range(x, h * x, x):
		t = s[i]
		q += p ^ t
		dp[i] = b = q
		a = p = t
		for j in range(i + 1, i + w):
			sj = s[j]
			b += a ^ sj
			k = j - x
			t = dp[k] + (s[k] ^ sj)
			if b > t:
				b = t
			dp[j] = b
			a = sj
	print(b + 1 >> 1)
main()


def main():
	(_, *s) = open(0)
	(b, q) = ('.' * 101, range(101))
	for (i, s) in enumerate(s):
		a = []
		for (x, y, z, c) in zip(b, '.' + s, s, q):
			c += x == '.' > z
			i += y == '.' > z
			if i > c:
				i = c
			a += (i,)
		(b, q) = (s, a)
	print(a[-2])
main()


(_, *s) = open(0)
(b, q) = ('.' * 101, range(101))
for (i, s) in enumerate(s):
	a = [i]
	for (x, y, z, c) in zip(b, '.' + s, s, q):
		a += (min(c + (x == '.' > z), a[-1] + (y == '.' > z)),)
	(b, q) = (s, a[1:])
print(a[-2])


(H, W) = map(int, input().split())
INF = H + W + W
grid = [[v for v in input()] for _ in range(H)]
dp = [[INF] * W for _ in range(H)]
DX = [0, 1]
DY = [1, 0]
dp[0][0] = 0
for x in range(H):
	for y in range(W):
		for (dx, dy) in zip(DX, DY):
			nx = x + dx
			ny = y + dy
			if 0 <= nx < H and 0 <= ny < W:
				if grid[x][y] == '.' and grid[x][y] != grid[nx][ny]:
					dp[nx][ny] = min(dp[nx][ny], dp[x][y] + 1)
				else:
					dp[nx][ny] = min(dp[nx][ny], dp[x][y])
if grid[0][0] == '#':
	dp[-1][-1] += 1
print(dp[-1][-1])


INF = 10 ** 9

def solve(h, w, s):
	dp = [[INF] * w for r in range(h)]
	dp[0][0] = int(s[0][0] == '#')
	for r in range(h):
		for c in range(w):
			for (dr, dc) in [(-1, 0), (0, -1)]:
				(nr, nc) = (r + dr, c + dc)
				if 0 <= nr < h and 0 <= nc < w:
					dp[r][c] = min(dp[r][c], dp[nr][nc] + (s[r][c] != s[nr][nc]))
	return (dp[h - 1][w - 1] + 1) // 2
(h, w) = map(int, input().split())
s = [input() for r in range(h)]
print(solve(h, w, s))


(h, w) = map(int, input().split())
s = []
for _ in range(h):
	s.append(input())
dp = [[h * w for i in range(w + 1)] for j in range(h + 1)]
dp[0][1] = 0
dp[1][0] = 0
for i in range(h):
	for j in range(w):
		dp[i + 1][j + 1] = min(dp[i][j + 1] + (s[i][j] == '#' and (i == 0 or s[i - 1][j] == '.')), dp[i + 1][j] + (s[i][j] == '#' and (j == 0 or s[i][j - 1] == '.')))
print(dp[-1][-1])


(H, W) = map(int, input().split())
s = [list(input()) for _ in range(H)]
dp = [[float('inf')] * W for _ in range(H)]
if s[0][0] == '#':
	dp[0][0] = 1
else:
	dp[0][0] = 0
dxdy = [(1, 0), (0, 1)]
for y in range(H):
	for x in range(W):
		for (dx, dy) in dxdy:
			nx = x + dx
			ny = y + dy
			if nx >= W or ny >= H:
				continue
			if s[ny][nx] == '#' and s[y][x] == '.':
				dp[ny][nx] = min(dp[ny][nx], dp[y][x] + 1)
			else:
				dp[ny][nx] = min(dp[ny][nx], dp[y][x])
print(dp[-1][-1])


(h, w) = map(int, input().split())
G = [['#'] * (w + 2) for i in range(h + 2)]
for i in range(1, h + 1):
	G[i] = ['#'] + list(input()) + ['#']
for i in range(h + 2):
	for j in range(w + 2):
		if G[i][j] == '.':
			G[i][j] = 0
		else:
			G[i][j] = 1
dp = [[1000] * (w + 2) for i in range(h + 2)]
dp[1][1] = 0
for i in range(1, h + 1):
	for j in range(1, w + 1):
		if i == 1 and j == 1:
			continue
		dp[i][j] = min(dp[i - 1][j] + (G[i - 1][j] + G[i][j]) % 2, dp[i][j - 1] + (G[i][j - 1] + G[i][j]) % 2)
ans = dp[h][w]
if G[1][1] == 1:
	ans = ans + 1
print((ans + 1) // 2)


(h, w) = map(int, input().split())
l = [list(input()) for i in range(h)]
dp = [[float('INF')] * w for i in range(h)]
if l[0][0] == '.':
	dp[0][0] = 0
else:
	dp[0][0] = 1
for i in range(h):
	for j in range(w):
		a = dp[i - 1][j]
		b = dp[i][j - 1]
		if l[i - 1][j] == '.' and l[i][j] == '#':
			a += 1
		if l[i][j - 1] == '.' and l[i][j] == '#':
			b += 1
		dp[i][j] = min(a, b, dp[i][j])
print(dp[-1][-1])


(h, w) = map(int, input().split())
S = []
for _ in range(h):
	S.append(input())
tbl = [[10 ** 3] * w for _ in range(h)]
if S[0][0] == '#':
	tbl[0][0] = 1
else:
	tbl[0][0] = 0
for i in range(h):
	for j in range(w):
		if i >= 1 and S[i][j] == '#' and (S[i - 1][j] == '.'):
			tbl[i][j] = min(tbl[i][j], tbl[i - 1][j] + 1)
		elif i >= 1:
			tbl[i][j] = min(tbl[i][j], tbl[i - 1][j])
		if j >= 1 and S[i][j] == '#' and (S[i][j - 1] == '.'):
			tbl[i][j] = min(tbl[i][j], tbl[i][j - 1] + 1)
		elif j >= 1:
			tbl[i][j] = min(tbl[i][j], tbl[i][j - 1])
print(tbl[h - 1][w - 1])


(H, W) = map(int, input().split())
S = ['.' * (W + 1)] + ['.' + input() for _ in range(H)]
dp = [[0] * (W + 1) for _ in range(H + 1)]
for h in range(H + 1):
	dp[h][0] = H * 2
for w in range(W + 1):
	dp[0][w] = W * 2
dp[0][1] = 0
for h in range(1, H + 1):
	for w in range(1, W + 1):
		dp[h][w] = min(dp[h - 1][w] + (S[h][w] != S[h - 1][w]), dp[h][w - 1] + (S[h][w] != S[h][w - 1]))
print((dp[-1][-1] + 1) // 2)


(h, w) = map(int, input().split())
s = []
for i in range(h):
	s.append(list(input()))
dp = [[float('inf') for _ in range(w)] for _ in range(h)]
dp[0][0] = 0 if s[0][0] == '.' else 1

def update(dp, i, j, ni, nj):
	if s[ni][nj] == '.':
		dp[ni][nj] = min(dp[i][j], dp[ni][nj])
	elif s[i][j] == '#':
		dp[ni][nj] = min(dp[i][j], dp[ni][nj])
	else:
		dp[ni][nj] = min(dp[i][j] + 1, dp[ni][nj])
for i in range(h):
	for j in range(w):
		if i + 1 < h:
			update(dp, i, j, i + 1, j)
		if j + 1 < w:
			update(dp, i, j, i, j + 1)
print(dp[h - 1][w - 1])


(h, w) = map(int, input().split())
L = [input() for i in range(h)]
dp = [[10 ** 9] * w for i in range(h)]
if L[0][0] == '.':
	dp[0][0] = 0
else:
	dp[0][0] = 1
li = ((1, 0), (0, 1))
for i in range(h):
	for j in range(w):
		for (dy, dx) in li:
			(ny, nx) = (i + dy, j + dx)
			if ny >= h or nx >= w:
				continue
			plus = 0
			if L[i][j] == '.' and L[ny][nx] == '#':
				plus = 1
			dp[ny][nx] = min(dp[i][j] + plus, dp[ny][nx])
print(dp[h - 1][w - 1])


def main():
	import sys
	input = sys.stdin.buffer.readline
	(h, w) = map(int, input().split())
	x = w + 1
	s = [c >> 3 for _ in range(h) for c in input()]
	dp = [10001] * h * x
	dp[0] = 5 - s[0]
	for i in range(1, w):
		dp[i] = dp[i - 1] + (s[i - 1] ^ s[i])
	for i in range(x, h * x, x):
		dp[i] = dp[i - x] + (s[i - x] ^ s[i])
		for j in range(1, w):
			k = i + j
			t = dp[k - 1] + (s[k - 1] ^ s[k])
			u = dp[k - x] + (s[k - x] ^ s[k])
			if t > u:
				t = u
			dp[k] = t
	print(dp[-2] + 1 >> 1)
main()


(H, W) = map(int, input().split())
s = [input() for _ in range(H)]
dp = [[float('inf') for _ in range(W)] for _ in range(H)]
if s[0][0] == '#':
	dp[0][0] = 1
else:
	dp[0][0] = 0
dx = [0, 1]
dy = [1, 0]
for i in range(H):
	for j in range(W):
		for k in range(2):
			ni = i + dx[k]
			nj = j + dy[k]
			if ni >= H or nj >= W:
				continue
			add = 0
			if s[i][j] == '.' and s[ni][nj] == '#':
				add += 1
			dp[ni][nj] = min(dp[ni][nj], dp[i][j] + add)
print(dp[H - 1][W - 1])


(H, W) = map(int, input().split())
s = [list(input()) for _ in range(H)]
dp = [[10001] * W for _ in range(H)]
if s[0][0] == '#':
	dp[0][0] = 1
else:
	dp[0][0] = 0
moves = [[1, 0], [0, 1]]
for y in range(H):
	for x in range(W):
		for m in moves:
			(ny, nx) = (y + m[0], x + m[1])
			if ny >= H or nx >= W:
				continue
			add = 0
			if s[y][x] == '.' and s[ny][nx] == '#':
				add = 1
			dp[ny][nx] = min(dp[ny][nx], dp[y][x] + add)
print(dp[-1][-1])


(h, w) = map(int, input().split())
b = [list(input()) for _ in range(h)]
ans = [w * [10 ** 9] for _ in range(h)]
ans[0][0] = (b[0][0] == '#') + 0
for i in range(h):
	for j in range(w):
		if i == j == 0:
			continue
		if i == 0:
			if b[0][j - 1] == '.' and b[0][j] == '#':
				ans[0][j] = ans[0][j - 1] + 1
			else:
				ans[0][j] = ans[0][j - 1]
		elif j == 0:
			if b[i - 1][0] == '.' and b[i][0] == '#':
				ans[i][0] = ans[i - 1][0] + 1
			else:
				ans[i][0] = ans[i - 1][0]
		else:
			ii = ans[i - 1][j]
			if b[i - 1][j] == '.' and b[i][j] == '#':
				ii += 1
			jj = ans[i][j - 1]
			if b[i][j - 1] == '.' and b[i][j] == '#':
				jj += 1
			ans[i][j] = min(ii, jj)
print(ans[-1][-1])


from itertools import count, repeat
h = int(input().split()[0])
a0 = repeat('.')
r0 = count()
for i in range(h):
	a = input()
	r = [i]
	for (x, y, z, u) in zip(a0, '.' + a, a, r0):
		r.append(min(u + (x + z == '.#'), r[-1] + (y + z == '.#')))
	a0 = a
	r0 = r[1:]
print(r[-1])


(h, w) = map(int, input().split())
S = []
for i in range(h):
	S.append(input())
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] = min(D[i][j], D[i + x][j + y])
if S[0][0] == '#':
	print(1 + D[h - 1][w - 1] // 2)
else:
	print(D[h - 1][w - 1] // 2 + (S[0][0] != S[h - 1][w - 1]))


(h, w) = map(int, input().split())
s = [input() for _ in range(h)]
dp = [[float('inf')] * w for _ in range(h)]
if s[0][0] == '#':
	dp[0][0] = 1
else:
	dp[0][0] = 0
dx = [1, 0]
dy = [0, 1]
for i in range(h):
	for j in range(w):
		for dir in range(2):
			ni = i + dy[dir]
			nj = j + dx[dir]
			if ni >= h or nj >= w:
				continue
			add = 0
			if s[ni][nj] == '#' and s[i][j] == '.':
				add = 1
			dp[ni][nj] = min(dp[ni][nj], dp[i][j] + add)
print(dp[-1][-1])


(H, W) = map(int, input().split())
table = [input() for _ in range(H)]
inf = 10 ** 9
dp = [[inf] * (W + 1) for _ in range(H + 1)]
dp[0][0] = 0 if table[0][0] == '.' else 1
for h in range(H):
	for w in range(W):
		flg = table[h][w] == '.' and (table[h][w + 1] == '#' if w < W - 1 else True)
		dp[h][w + 1] = min(dp[h][w + 1], dp[h][w] + 1 if flg else dp[h][w])
		flg = table[h][w] == '.' and (table[h + 1][w] == '#' if h < H - 1 else True)
		dp[h + 1][w] = dp[h][w] + 1 if flg else dp[h][w]
print(dp[H - 1][W - 1])


(H, W) = map(int, input().split())
S = [list(input()) for h in range(H)]
table = [[0 for w in range(W)] for h in range(H)]
table[0][0] = int(S[0][0] == '#')
for i in range(1, H):
	table[i][0] = table[i - 1][0] + int(S[i - 1][0] == '.' and S[i][0] == '#')
for j in range(1, W):
	table[0][j] = table[0][j - 1] + int(S[0][j - 1] == '.' and S[0][j] == '#')
for i in range(1, H):
	for j in range(1, W):
		table[i][j] = min(table[i - 1][j] + int(S[i - 1][j] == '.' and S[i][j] == '#'), table[i][j - 1] + int(S[i][j - 1] == '.' and S[i][j] == '#'))
print(table[-1][-1])


import sys
(H, W) = map(int, input().split())
S = [list(s.rstrip()) for s in sys.stdin.readlines()]
dp = [[10 ** 9] * W for _ in range(H)]
if S[0][0] == '#':
	dp[0][0] = 1
else:
	dp[0][0] = 0
for h in range(H):
	for w in range(W):
		for (a, b) in ((h + 1, w), (h, w + 1)):
			if a >= H or b >= W:
				continue
			elif S[h][w] == '.' and S[a][b] == '#':
				dp[a][b] = min(dp[a][b], dp[h][w] + 1)
			else:
				dp[a][b] = min(dp[a][b], dp[h][w])
print(dp[H - 1][W - 1])


def main():
	(H, W) = map(int, input().split())
	s = [input() for _ in range(H)]
	dp = [[H * W] * W for _ in range(H)]
	dp[0][0] = int(s[0][0] == '#')
	for r in range(H):
		for c in range(W):
			if r > 0:
				dp[r][c] = min(dp[r][c], dp[r - 1][c] + int(s[r][c] == '#' and s[r - 1][c] == '.'))
			if c > 0:
				dp[r][c] = min(dp[r][c], dp[r][c - 1] + int(s[r][c] == '#' and s[r][c - 1] == '.'))
	res = dp[H - 1][W - 1]
	print(res)
	return
main()


def main():
	import sys
	input = sys.stdin.buffer.readline
	(h, w) = map(int, input().split())
	s = input()
	a = b = x = y = s[0] == 35
	d = [(b, a)]
	d_add = d.append
	for i in range(1, w):
		f = s[i] == 35
		b += a ^ f
		a = f
		d_add((b, a))
	for _ in range(h - 1):
		s = input()
		f = s[0] == 35
		y += x ^ f
		b = y
		a = x = f
		p = [(b, a)]
		p_add = p.append
		for i in range(1, w):
			f = s[i] == 35
			b += a ^ f
			(c, g) = d[i]
			c += f ^ g
			if b > c:
				b = c
			a = f
			p_add((b, a))
		d = p
	print(b + 1 >> 1)
main()


(h, w) = list(map(int, input().split()))
s = [input() for _ in range(h)]
dp = [[1000] * (w + 1) for _ in range(h + 1)]
if s[0][0] == '.':
	dp[0][0] = 0
else:
	dp[0][0] = 1
for i in range(h):
	for j in range(w):
		if i - 1 >= 0:
			dp[i][j] = dp[i - 1][j] + (1 if s[i - 1][j] == '.' and s[i][j] == '#' else 0)
		if j - 1 >= 0:
			dp[i][j] = min(dp[i][j], dp[i][j - 1] + (1 if s[i][j - 1] == '.' and s[i][j] == '#' else 0))
print(dp[h - 1][w - 1])


def main():
	import sys
	b = sys.stdin.buffer
	(h, w) = map(int, b.readline().split())
	x = w + 1
	s = [c >> 3 for c in b.read()]
	dp = [10000] * h * x
	a = p = s[0]
	dp[0] = b = q = 5 - a
	for i in range(1, w):
		t = s[i]
		dp[i] = b = b + (a ^ t)
		a = t
	for i in range(x, h * x, x):
		t = s[i]
		dp[i] = q = q + (p ^ t)
		p = t
		for j in range(1, w):
			k = i + j
			sk = s[k]
			l = k - 1
			t = dp[l] + (s[l] ^ sk)
			l = k - x
			u = dp[l] + (s[l] ^ sk)
			if t > u:
				t = u
			dp[k] = t
	print(dp[-2] + 1 >> 1)
main()


(H, W) = map(int, input().split())
memo = [[10 ** 5] * W for _ in range(H)]
mp = [input() for _ in range(H)]
if mp[0][0] == '#':
	memo[0][0] = 1
else:
	memo[0][0] = 0
for i in range(H):
	for j in range(W):
		if i > 0:
			if mp[i - 1][j] == '.' and mp[i][j] == '#':
				memo[i][j] = min(memo[i][j], memo[i - 1][j] + 1)
			else:
				memo[i][j] = min(memo[i][j], memo[i - 1][j])
		if j > 0:
			if mp[i][j - 1] == '.' and mp[i][j] == '#':
				memo[i][j] = min(memo[i][j], memo[i][j - 1] + 1)
			else:
				memo[i][j] = min(memo[i][j], memo[i][j - 1])
print(memo[-1][-1])


(H, W) = map(int, input().split())
s = [0] * H
for i in range(H):
	s[i] = list(input())
dp = [[float('inf') for _ in range(W)] for _ in range(H)]
dp[0][0] = 1 if s[0][0] == '#' else 0
mv = [(-1, 0), (0, -1)]
for i in range(H):
	for j in range(W):
		if i == 0 and j == 0:
			pass
		else:
			tmp = float('inf')
			for k in mv:
				a = i + k[0]
				b = j + k[1]
				if 0 <= a <= H - 1 and 0 <= b <= W - 1:
					if s[i][j] == '#' and s[a][b] == '.':
						tmp = dp[a][b] + 1
					else:
						tmp = dp[a][b]
				dp[i][j] = min(dp[i][j], tmp)
print(dp[-1][-1])


(H, W) = map(int, input().split())
S = []
for _ in range(H):
	S.append(list(input()))
dp = [[100] * (W + 1) for _ in range(H + 1)]
dp2 = [[True] * (W + 1) for _ in range(H + 1)]
dp[0][1] = 0
for i in range(H):
	for j in range(W):
		if S[i][j] == '#':
			x = dp[i][j + 1] + 1 if dp2[i][j + 1] else dp[i][j + 1]
			y = dp[i + 1][j] + 1 if dp2[i + 1][j] else dp[i + 1][j]
			dp2[i + 1][j + 1] = False
		else:
			x = dp[i][j + 1]
			y = dp[i + 1][j]
			dp2[i + 1][j + 1] = True
		dp[i + 1][j + 1] = min(dp[i + 1][j + 1], x, y)
print(dp[-1][-1])


(h, w) = map(int, input().split())
a0 = '.' * w
r0 = [200] * w
for i in range(h):
	a = input()
	r = [i and 200]
	for (x, y, z, u) in zip(a0, '.' + a, a, r0):
		r.append(min(u + (x + z == '.#'), r[-1] + (y + z == '.#')))
	a0 = a
	r0 = r[1:]
print(r[-1])


(n, m) = map(int, input().split())
s = [list(input()) for i in range(n)]
ans = [[10 ** 9 + 7] * m for i in range(n)]
ans[0][0] = int(s[0][0] == '#')
for i in range(n):
	for j in range(m):
		if i > 0:
			ans[i][j] = min(ans[i][j], ans[i - 1][j] + int(s[i - 1][j] == '.' and s[i][j] == '#'))
		if j > 0:
			ans[i][j] = min(ans[i][j], ans[i][j - 1] + int(s[i][j - 1] == '.' and s[i][j] == '#'))
print(ans[n - 1][m - 1])


(H, W) = map(int, input().split())
g = []
for _ in range(H):
	g.append(list(input()))
dp = [[10 ** 9 for _ in range(W)] for __ in range(H)]
dp[0][0] = 1 if g[0][0] == '#' else 0
d = ([0, 1], [1, 0])
for ix in range(H):
	for jx in range(W):
		for (dx, dy) in d:
			ni = ix + dx
			nj = jx + dy
			if ni >= H or nj >= W:
				continue
			add = 0
			if g[ix][jx] == '.' and g[ni][nj] == '#':
				add += 1
			dp[ni][nj] = min(dp[ni][nj], dp[ix][jx] + add)
print(dp[H - 1][W - 1])


(H, W) = list(map(int, input().split()))
s = [list(input()) for _ in range(H)]
DP = [[0] * W for _ in range(H)]
if s[0][0] == '#':
	DP[0][0] = 1
for i in range(1, W):
	if s[0][i - 1] != s[0][i]:
		DP[0][i] = DP[0][i - 1] + 1
	else:
		DP[0][i] = DP[0][i - 1]
for i in range(1, H):
	DP[i][0] = DP[i - 1][0]
	if s[i][0] != s[i - 1][0]:
		DP[i][0] += 1
	for j in range(1, W):
		x = DP[i][j - 1]
		if s[i][j] != s[i][j - 1]:
			x += 1
		y = DP[i - 1][j]
		if s[i][j] != s[i - 1][j]:
			y += 1
		DP[i][j] = min(x, y)
print((DP[-1][-1] + 1) // 2)


import sys
(h, w) = map(int, input().split())
s = [list(x.rstrip()) for x in sys.stdin.readlines()]
dp = [[10 ** 6] * w for _ in range(h)]
if s[0][0] == '#':
	dp[0][0] = 1
else:
	dp[0][0] = 0
for j in range(h):
	for i in range(w):
		for k in range(2):
			(nx, ny) = (i + (k + 1) % 2, j + k % 2)
			if nx >= w or ny >= h:
				continue
			else:
				add = 0
				if s[ny][nx] == '#' and s[j][i] == '.':
					add = 1
				dp[ny][nx] = min(dp[ny][nx], dp[j][i] + add)
print(dp[h - 1][w - 1])


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


(H, W) = map(int, input().split())
s = [input() for _ in range(H)]
DP = [[1000] + [0] * W for _ in range(H + 1)]
re = [[0] * (W + 1) for _ in range(H + 1)]
DP[0] = [1000] * (W + 1)
DP[0][1] = DP[1][0] = 0
for i in range(1, H + 1):
	for j in range(1, W + 1):
		if s[i - 1][j - 1] == '.':
			DP[i][j] = min(DP[i - 1][j], DP[i][j - 1])
		else:
			u = DP[i - 1][j] + 1 - re[i - 1][j]
			l = DP[i][j - 1] + 1 - re[i][j - 1]
			DP[i][j] = min(u, l)
			re[i][j] = 1
print(DP[H][W])


(H, W) = list(map(int, input().split()))
grid = [['_'] * (W + 2)]
for i in range(H):
	grid.append(list('_' + input() + '_'))
grid.append(['_'] * (W + 2))
dp = [[float('inf')] * (W + 2) for i in range(H + 2)]
dp[0][1] = 0
for c in range(1, H + 1):
	for r in range(1, W + 1):
		if grid[c][r] == '#':
			left = dp[c][r - 1] + 1 if grid[c][r - 1] != '#' else dp[c][r - 1]
			up = dp[c - 1][r] + 1 if grid[c - 1][r] != '#' else dp[c - 1][r]
			dp[c][r] = min(left, up)
		else:
			dp[c][r] = min(dp[c][r - 1], dp[c - 1][r])
print(dp[H][W])


def main():
	import sys
	input = sys.stdin.buffer.readline
	(h, w) = map(int, input().split())
	(t, *s, _) = input()
	if t == 46:
		(c, f) = (0, False)
	else:
		(c, f) = (1, True)
	p = [(c, f)]
	for t in s:
		g = t == 35
		if g != f:
			c += 1
			f = not f
		p += ((c, f),)
	d = p
	for _ in range(h - 1):
		(t, *s, _) = input()
		(c, f) = d[0]
		g = t == 35
		if g != f:
			c += 1
			f = not f
		p = [(c, f)]
		for (i, t) in enumerate(s, 1):
			(e, h) = d[i]
			g = t == 35
			if h != g:
				e += 1
				h = not h
			if f != g:
				c += 1
				f = not f
			if e < c:
				(c, f) = (e, h)
			p += ((c, f),)
		d = p
	print(d[-1][0] + 1 >> 1)
main()


(H, W) = map(int, input().split())
s = [list(input()) for i in range(H)]
dp = [[10 ** 6 for j in range(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 > 0:
			if (s[i][j], s[i - 1][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 (s[i][j], s[i][j - 1]) == ('#', '.'):
				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])


(H, W) = map(int, input().split())
grid = [input() for _ in range(H)]
dp = [[float('inf')] * W for i in range(H)]
dp[0][0] = 1 if grid[0][0] == '#' else 0
for i in range(H):
	for j in range(W):
		for (y, x) in ((1, 0), (0, 1)):
			(ni, nj) = (i + y, j + x)
			if ni >= H or nj >= W:
				continue
			c = 0
			if grid[ni][nj] == '#' and grid[i][j] == '.':
				c = 1
			dp[ni][nj] = min(dp[ni][nj], dp[i][j] + c)
print(dp[H - 1][W - 1])


inm = lambda : map(int, input().split())
ins = lambda : input().strip()
BIG = 10 ** 18
(h, w) = inm()
s = []
for i in range(h):
	s.append(ins())
d = [[0] * w for i in range(h)]
d[0][0] = 1 if s[0][0] == '#' else 0
for i in range(h):
	for j in range(w):
		if i == 0 and j == 0:
			continue
		vx = BIG if i == 0 else d[i - 1][j] + (1 if s[i - 1][j] == '.' and s[i][j] == '#' else 0)
		vy = BIG if j == 0 else d[i][j - 1] + (1 if s[i][j - 1] == '.' and s[i][j] == '#' else 0)
		d[i][j] = min(vx, vy)
print(d[h - 1][w - 1])


import sys
INF = sys.maxsize
(H, W) = map(int, input().split())
m = []
for i in range(H):
	m.append([x for x in input()])
dp = [[INF] * W for _ in range(H)]
dp[0][0] = 0 if m[0][0] == '.' else 1
for i in range(H):
	for j in range(W):
		for (di, dj) in [(0, 1), (1, 0)]:
			ni = i + di
			nj = j + dj
			if ni < H and nj < W:
				dp[ni][nj] = min(dp[ni][nj], dp[i][j] + 1 if m[i][j] == '.' and m[ni][nj] == '#' else dp[i][j])
print(dp[-1][-1])


import sys
sys.setrecursionlimit(10 ** 6)
(h, w) = map(int, input().split())
s = [list(input()) for i in range(h)]
t = [['' for i in range(w)] for j in range(h)]
t[0][0] = 1 if s[0][0] == '#' else 0

def f(x, y):
	if t[x][y] != '':
		return t[x][y]
	else:
		t[x][y] = min(f(x - 1, y) + (s[x][y] == '#' and s[x][y] != s[x - 1][y]) if x > 0 else float('INF'), f(x, y - 1) + (s[x][y] == '#' and s[x][y] != s[x][y - 1]) if y > 0 else float('INF'))
		return t[x][y]
print(f(h - 1, w - 1))


(h, w) = map(int, input().split())
s = [list(input()) for _ in range(h)]
dx = [1, 0]
dy = [0, 1]
dp = [[10 ** 9] * 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):
		for d in range(2):
			new_i = i + dx[d]
			new_j = j + dy[d]
			if h <= new_i or w <= new_j:
				continue
			add = 0
			if s[new_i][new_j] == '#' and s[i][j] == '.':
				add = 1
			dp[new_i][new_j] = min(dp[new_i][new_j], dp[i][j] + add)
print(dp[-1][-1])


(h, w) = map(int, input().split())
s = [None for i in range(h)]
for i in range(h):
	s[i] = input()
dp = [[0] * w for i in range(h)]
dp[0][0] = int(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):
		cand1 = dp[i - 1][j] + (s[i - 1][j] == '.' and s[i][j] == '#')
		cand2 = dp[i][j - 1] + (s[i][j - 1] == '.' and s[i][j] == '#')
		dp[i][j] = min(cand1, cand2)
print(dp[-1][-1])


(H, W) = list(map(int, input().split()))
B = []
for _ in range(H):
	B.append(input())
A = [[999999 for _ in range(W)] for _ in range(H)]
A[0][0] = 0 if B[0][0] == '.' else 1
for i in range(H):
	for j in range(W):
		if i + j == 0:
			continue
		(X, Y) = (999999, 999999)
		if i > 0:
			X = A[i - 1][j]
			X += 1 if B[i - 1][j] == '.' and B[i][j] == '#' else 0
		if j > 0:
			Y = A[i][j - 1]
			Y += 1 if B[i][j - 1] == '.' and B[i][j] == '#' else 0
		A[i][j] = min(X, Y)
print(A[H - 1][W - 1])


(h, w) = map(int, input().split())
M = [list(input()) for _ in range(h)]
count = [[int(1e+18) for _ in range(w)] for _ in range(h)]
count[0][0] = 1 if M[0][0] == '#' else 0
for i in range(h):
	for j in range(w):
		if i + 1 < h:
			v = 1 if M[i][j] != M[i + 1][j] else 0
			count[i + 1][j] = min(count[i + 1][j], count[i][j] + v)
		if j + 1 < w:
			v = 1 if M[i][j] != M[i][j + 1] else 0
			count[i][j + 1] = min(count[i][j + 1], count[i][j] + v)
print((count[h - 1][w - 1] + 1) // 2)


import copy
import heapq
(H, W) = map(int, input().split())
S = [['.'] * (W + 1)]
for _ in range(H):
	s = list(input())
	s.insert(0, '.')
	S.append(s)
inf = float('inf')
dp = []
for _ in range(H + 1):
	dp.append([inf] * (W + 1))
if S[1][1] == '.':
	dp[1][1] = 0
else:
	dp[1][1] = 1
for i in range(1, H + 1):
	for j in range(1, W + 1):
		right = dp[i][j - 1]
		down = dp[i - 1][j]
		if S[i][j] == '#':
			if S[i - 1][j] == '.':
				down += 1
			if S[i][j - 1] == '.':
				right += 1
		dp[i][j] = min(dp[i][j], right, down)
print(dp[H][W])


(h, w) = map(int, input().split())
info = ['.' + 'x' * (w - 1)] + [input() for i in range(h)]
INF = 10 ** 5
h += 1
dp = [[INF] * w for i in range(h)]
dp[0][0] = 0
for i in range(h):
	for j in range(w):
		for (ii, jj) in [(i, j + 1), (i + 1, j)]:
			if not (0 <= ii < h and 0 <= jj < w):
				continue
			if info[ii][jj] == 'x':
				continue
			if info[i][j] != info[ii][jj] and info[ii][jj] == '#':
				dp[ii][jj] = min(dp[i][j] + 1, dp[ii][jj])
			else:
				dp[ii][jj] = min(dp[i][j], dp[ii][jj])
print(dp[-1][-1])


(H, W) = map(int, input().split())
s = [list(input()) for _ in range(H)]
dp = [[float('inf')] * W for _ in range(H)]
if s[0][0] == '#':
	dp[0][0] = 1
else:
	dp[0][0] = 0
for c in range(W):
	for r in range(H):
		if r > 0:
			count = 0
			if s[r - 1][c] == '.' and s[r][c] == '#':
				count = 1
			dp[r][c] = min(dp[r][c], dp[r - 1][c] + count)
		if c > 0:
			count = 0
			if s[r][c - 1] == '.' and s[r][c] == '#':
				count = 1
			dp[r][c] = min(dp[r][c], dp[r][c - 1] + count)
print(dp[H - 1][W - 1])


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


def main():
	(H, W) = map(int, input().split())
	s = [input() for _ in range(H)]
	dp = [[1 << 60] * W for _ in range(H)]
	dp[0][0] = int(s[0][0] == '#')
	for r in range(H):
		for c in range(W):
			t = dp[r][c]
			if r > 0:
				t = min(t, dp[r - 1][c] + int(s[r - 1][c] == '.' and s[r][c] == '#'))
			if c > 0:
				t = min(t, dp[r][c - 1] + int(s[r][c - 1] == '.' and s[r][c] == '#'))
			dp[r][c] = t
	print(dp[H - 1][W - 1])
main()


(H, W) = map(int, input().split())
S = [input() for i in range(H)]
from collections import deque
q = deque([(int(S[0][0] == '#'), 0, 0)])
INF = float('inf')
costs = [[INF] * W for _ in range(H)]
costs[0][0] = int(S[0][0] == '#')
while q:
	(k, x, y) = q.popleft()
	for (dx, dy) in [(1, 0), (0, 1)]:
		(nx, ny) = (x + dx, y + dy)
		if nx >= W:
			continue
		if ny >= H:
			continue
		c = int(S[y][x] != S[ny][nx])
		if k + c >= costs[ny][nx]:
			continue
		costs[ny][nx] = k + c
		q.append((k + c, nx, ny))
print((costs[-1][-1] + 1) // 2)


(H, W) = map(int, input().split())
a = [[0] * W for i in range(H)]
b = [[0] * W for i in range(H)]
for i in range(H):
	a[i] = list(input())
for j in range(1, W):
	b[0][j] = b[0][j - 1] + int(not a[0][j] == a[0][j - 1])
for i in range(1, H):
	b[i][0] = b[i - 1][0] + int(not a[i - 1][0] == a[i][0])
	for j in range(1, W):
		b[i][j] = min(b[i - 1][j] + int(not a[i - 1][j] == a[i][j]), b[i][j - 1] + int(not a[i][j - 1] == a[i][j]))
if a[0][0] == '.' and a[H - 1][W - 1] == '.':
	print(int(b[H - 1][W - 1] / 2))
elif a[0][0] == '#' and a[H - 1][W - 1] == '#':
	print(int(b[H - 1][W - 1] / 2 + 1))
else:
	print(int((b[H - 1][W - 1] + 1) / 2))


(H, W) = map(int, input().split())
S = [input() for _ in range(H)]
inf = 10 ** 6
L = [[inf] * W for _ in range(H)]
if S[0][0] == '.':
	L[0][0] = 0
else:
	L[0][0] = 1
for i in range(H):
	for j in range(W):
		n1 = inf
		n2 = inf
		if i > 0:
			if S[i - 1][j] == '.' and S[i][j] == '#':
				n1 = L[i - 1][j] + 1
			else:
				n1 = L[i - 1][j]
		if j > 0:
			if S[i][j - 1] == '.' and S[i][j] == '#':
				n2 = L[i][j - 1] + 1
			else:
				n2 = L[i][j - 1]
		L[i][j] = min(L[i][j], n1, n2)
print(L[-1][-1])


def main():
	import sys
	buf = sys.stdin.buffer
	(h, w) = map(int, buf.readline().split())
	s = buf.readline()
	a = b = x = y = s[0] == 35
	(d, e) = ([b], [a])
	(d_add, e_add) = (d.append, e.append)
	for i in range(1, w):
		f = s[i] == 35
		b += a ^ f
		a = f
		d_add(b)
		e_add(a)
	for s in buf.read().split():
		f = s[0] == 35
		y += x ^ f
		b = y
		a = x = f
		(p, q) = ([b], [a])
		(p_add, q_add) = (p.append, q.append)
		for i in range(1, w):
			f = s[i] == 35
			b += a ^ f
			c = d[i] + (f ^ e[i])
			if b > c:
				b = c
			a = f
			p_add(b)
			q_add(a)
		(d, e) = (p, q)
	print(b + 1 >> 1)
main()


from collections import deque
(h, w) = map(int, input().split())
map_input = [list(input()) for i in range(h)]
score = [[10 ** 10] * (w + 1) for i in range(h + 1)]
score[0][1] = 0
score[1][0] = 0
for i in range(h):
	for j in range(w):
		tmp1 = score[i][j + 1] + (map_input[i][j] == '#' and (i == 0 or map_input[i - 1][j] == '.'))
		tmp2 = score[i + 1][j] + (map_input[i][j] == '#' and (j == 0 or map_input[i][j - 1] == '.'))
		score[i + 1][j + 1] = min(tmp1, tmp2)
print(score[-1][-1])


(H, W) = map(int, input().split())
dp = [[H * W for __ in range(W)] for _ in range(H)]
dh = [1, 0]
dw = [0, 1]
S = []
for i in range(H):
	s = input()
	S.append(s)
if S[0][0] == '#':
	dp[0][0] = 1
else:
	dp[0][0] = 0
for i in range(H):
	for j in range(W):
		for k in range(2):
			nh = i + dh[k]
			nw = j + dw[k]
			if nh >= H or nw >= W:
				continue
			add = 0
			if S[nh][nw] == '#' and S[i][j] == '.':
				add = 1
			dp[nh][nw] = min(dp[nh][nw], dp[i][j] + add)
print(dp[H - 1][W - 1])


(H, W) = map(int, input().split())
s = [input() for _ in range(H)]
a = [[0] * W for _ in range(H)]
for i in range(H):
	for j in range(W):
		if i == j == 0:
			a[0][0] = 0
		elif i == 0:
			a[0][j] = a[0][j - 1] if s[0][j] == s[0][j - 1] else a[0][j - 1] + 1
		elif j == 0:
			a[i][0] = a[i - 1][0] if s[i][0] == s[i - 1][0] else a[i - 1][0] + 1
		else:
			a[i][j] = min(a[i][j - 1] if s[i][j] == s[i][j - 1] else a[i][j - 1] + 1, a[i - 1][j] if s[i][j] == s[i - 1][j] else a[i - 1][j] + 1)
print((a[H - 1][W - 1] + 1) // 2 if s[0][0] == '.' else a[H - 1][W - 1] // 2 + 1)


def main():
	(h, t, *s) = open(0)
	(h, w) = map(int, h.split())
	a = b = x = y = t[0] == '#'
	d = [(b, a)]
	d_add = d.append
	for i in range(1, w):
		f = t[i] == '#'
		b += a ^ f
		a = f
		d_add((b, a))
	for s in s:
		f = s[0] == '#'
		y += x ^ f
		b = y
		a = x = f
		p = [(b, a)]
		p_add = p.append
		for i in range(1, w):
			f = s[i] == '#'
			b += a ^ f
			(c, g) = d[i]
			c += f ^ g
			if b > c:
				b = c
			a = f
			p_add((b, a))
		d = p
	print(b + 1 >> 1)
main()


from collections import deque
(h, w) = map(int, input().split())
S = [list(input()) for _ in range(h)]
DP = [[10000] * w for _ in range(h)]
DP[0][0] = 0 if S[0][0] == '.' else 1
directs = [[0, 1], [1, 0]]
for hi in range(h):
	for wi in range(w):
		for (dh, dw) in directs:
			if not (0 <= hi + dh < h and 0 <= wi + dw < w):
				continue
			if S[hi][wi] == '.' and S[hi + dh][wi + dw] == '#':
				DP[hi + dh][wi + dw] = min(DP[hi + dh][wi + dw], DP[hi][wi] + 1)
			else:
				DP[hi + dh][wi + dw] = min(DP[hi + dh][wi + dw], DP[hi][wi])
print(DP[-1][-1])


(H, W) = map(int, input().split())
S = [list(input()) for _ in range(H)]
INF = 10001
dp = [[INF] * W for _ in range(H)]
dp[0][0] = 0 if S[0][0] == '.' else 1
for i in range(H):
	for j in range(W):
		(m, n) = (INF, INF)
		if i != 0:
			m = dp[i - 1][j] + (S[i - 1][j] == '.' and S[i][j] == '#')
		if j != 0:
			n = dp[i][j - 1] + (S[i][j - 1] == '.' and S[i][j] == '#')
		dp[i][j] = min(m, n, dp[i][j])
print(dp[H - 1][W - 1])


(H, W) = map(int, input().split())
M = [input() for _ in '_' * H]
D = [[0] * -~W for _ in '_' * -~H]
for i in range(H):
	for j in range(W):
		a = b = 999
		if i > 0:
			a = D[i][j + 1] + (M[i - 1][j] > M[i][j])
		if j > 0:
			b = D[i + 1][j] + (M[i][j - 1] > M[i][j])
		D[i + 1][j + 1] = min(a, b, 999 * (i + j > 0))
print(D[-1][-1] + (M[0][0] < '.'))


(H, W) = map(int, input().split())
field = [list(input()) for _ in range(H)]
dp = [[float('inf')] * 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):
		if i > 0:
			dp[i][j] = min(dp[i][j], dp[i - 1][j] + (field[i - 1][j] == '.' and field[i][j] == '#'))
		if j > 0:
			dp[i][j] = min(dp[i][j], dp[i][j - 1] + (field[i][j - 1] == '.' and field[i][j] == '#'))
print(dp[H - 1][W - 1])


(H, W) = map(int, input().split())
board = []
for h in range(H):
	board.append(input())
dp = [[1000 for i in range(W + 1)] for j in range(H + 1)]
dp[0][1] = 0
dp[1][0] = 0
for h in range(H):
	for w in range(W):
		dp[h + 1][w + 1] = min(dp[h][w + 1] + (board[h][w] == '#' and (h == 0 or board[h - 1][w] == '.')), dp[h + 1][w] + (board[h][w] == '#' and (w == 0 or board[h][w - 1] == '.')))
print(dp[-1][-1])


(h, w) = map(int, input().split())
s = [input() + '.' for i in range(h)] + ['.' * (w + 1)]
INF = 10 ** 18
dp = [[INF] * (w + 1) for i in range(h + 1)]
dp[0][0] = 1 if s[0][0] == '#' else 0
for i in range(h):
	for j in range(w):
		if s[i][j] == '#':
			dp[i + 1][j] = min(dp[i + 1][j], dp[i][j])
			dp[i][j + 1] = min(dp[i][j + 1], dp[i][j])
		else:
			vi = 1 if s[i + 1][j] == '#' else 0
			vj = 1 if s[i][j + 1] == '#' else 0
			dp[i + 1][j] = min(dp[i + 1][j], dp[i][j] + vi)
			dp[i][j + 1] = min(dp[i][j + 1], dp[i][j] + vj)
print(dp[h - 1][w - 1])


(h, w) = map(int, input().split())
x = [[0] * w for _ in range(h)]
s = [input() for _ in range(h)]
if s[0][0] == '#':
	x[0][0] = 1
for j in range(1, w):
	x[0][j] = x[0][j - 1]
	if s[0][j] == '#' and s[0][j - 1] == '.':
		x[0][j] += 1
for i in range(1, h):
	x[i][0] = x[i - 1][0]
	if s[i][0] == '#' and s[i - 1][0] == '.':
		x[i][0] += 1
for i in range(1, h):
	for j in range(1, w):
		if s[i][j] == '.':
			x[i][j] = min(x[i][j - 1], x[i - 1][j])
		else:
			p = x[i][j - 1]
			q = x[i - 1][j]
			if s[i][j - 1] == '.':
				p += 1
			if s[i - 1][j] == '.':
				q += 1
			x[i][j] = min(p, q)
print(x[h - 1][w - 1])


(H, W) = [int(_) for _ in input().split()]
S = [input() for _ in range(H)]
INF = 10 ** 5
dp = [[INF] * (W + 1) for _ in range(H + 1)]
dp[0][0] = int(S[0][0] == '#')
for i in range(H):
	for j in range(W):
		if j == 0:
			v1 = INF
		else:
			v1 = int(S[i][j - 1] == '.' and S[i][j] == '#') + dp[i][j - 1]
		if i == 0:
			v2 = INF
		else:
			v2 = int(S[i - 1][j] == '.' and S[i][j] == '#') + dp[i - 1][j]
		dp[i][j] = min(v1, v2, dp[i][j])
ans = dp[H - 1][W - 1]
print(ans)


def main():
	(h, w) = map(int, input().split())
	field = [list(input()) for _ in range(h)]
	dp = [[float('inf')] * w for _ in [0] * h]
	dp[0][0] = field[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] + (field[i - 1][j] == '.' and field[i][j] == '#'))
			if j > 0:
				dp[i][j] = min(dp[i][j], dp[i][j - 1] + (field[i][j - 1] == '.' and field[i][j] == '#'))
	print(dp[-1][-1])
main()


def main():
	import sys
	buf = sys.stdin.buffer
	(h, w) = map(int, buf.readline().split())
	(c, *s, _) = buf.readline()
	a = b = x = y = c == 35
	d = [(b, a)]
	for c in s:
		f = c == 35
		b += a ^ f
		a = f
		d += ((b, a),)
	for (c, *s) in buf.read().split():
		f = c == 35
		y += x ^ f
		b = y
		a = x = f
		p = [(b, a)]
		for (i, c) in enumerate(s, 1):
			f = c == 35
			b += a ^ f
			(c, g) = d[i]
			c += f ^ g
			if b > c:
				b = c
			a = f
			p += ((b, a),)
		d = p
	print(b + 1 >> 1)
main()


(h, w) = map(int, input().split())
s = [input() for _ in range(h)]
INF = 10 ** 9
dp = [[INF] * w for _ in range(h)]
dp[0][0] = 0 if s[0][0] == '.' else 1
for i in range(h):
	for j in range(w):
		(d, r) = (INF, INF)
		if i != 0:
			d = dp[i - 1][j] + (s[i - 1][j] == '.' and s[i][j] == '#')
		if j != 0:
			r = dp[i][j - 1] + (s[i][j - 1] == '.' and s[i][j] == '#')
		dp[i][j] = min(r, d, dp[i][j])
print(dp[h - 1][w - 1])


(h, w) = map(int, input().split())
a = [[(i == '#') * 1 for i in list(input())] for _ in range(h)]
dp = [[float('inf')] * w for _ in range(h)]
dp[0][0] = a[0][0]

def cnt(i0, j0, i1, j1):
	if a[i0][j0] == 0 and a[i1][j1] == 1:
		return 1
	return 0
for s in range(h + w):
	for i in range(s + 1):
		j = s - i
		if i >= h or j >= w:
			continue
		if i < h - 1:
			dp[i + 1][j] = min(dp[i + 1][j], dp[i][j] + cnt(i, j, i + 1, j))
		if j < w - 1:
			dp[i][j + 1] = min(dp[i][j + 1], dp[i][j] + cnt(i, j, i, j + 1))
print(dp[-1][-1])


(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] & ~s[j - 1][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] & ~s[j][i - j - 1]), dp[j][i - j])
print(dp[h - 1][w - 1])


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

def cnt(i0, j0, i1, j1):
	if S[i0][j0] == '.' and S[i1][j1] == '#':
		return 1
	else:
		return 0
for i in range(H):
	for j in range(W):
		if i == 0 and j == 0:
			dp[0][0] = 0 if S[0][0] == '.' else 1
		elif i == 0:
			dp[i][j] = dp[i][j - 1] + cnt(i, j - 1, i, j)
		elif j == 0:
			dp[i][j] = dp[i - 1][j] + cnt(i - 1, j, i, j)
		else:
			dp[i][j] = min(dp[i][j - 1] + cnt(i, j - 1, i, j), dp[i - 1][j] + cnt(i - 1, j, i, j))
print(dp[H - 1][W - 1])


def main():
	import sys
	input = sys.stdin.buffer.readline
	(h, w) = map(int, input().split())
	s = input()
	a = x = s[0] >> 3
	b = y = 5 - a
	d = [(b, a)]
	for i in range(1, w):
		f = s[i] >> 3
		b += a ^ f
		a = f
		d += ((b, a),)
	for _ in range(1, h):
		s = input()
		f = s[0] >> 3
		y += x ^ f
		b = y
		a = x = f
		p = [(b, a)]
		for i in range(1, w):
			f = s[i] >> 3
			b += a ^ f
			(c, g) = d[i]
			c += f ^ g
			if b > c:
				b = c
			a = f
			p += ((b, a),)
		d = p
	print(b + 1 >> 1)
main()


(H, W) = map(int, input().split())
s = [list(input()) for _ in range(H)]
dp = [[10000] * 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 and j == 0:
			continue
		if i != 0:
			if s[i - 1][j] == '.' and s[i][j] == '#':
				dp[i][j] = min(dp[i - 1][j] + 1, dp[i][j])
			else:
				dp[i][j] = min(dp[i - 1][j], dp[i][j])
		if j != 0:
			if s[i][j - 1] == '.' and s[i][j] == '#':
				dp[i][j] = min(dp[i][j - 1] + 1, dp[i][j])
			else:
				dp[i][j] = min(dp[i][j - 1], dp[i][j])
print(dp[-1][-1])


import math
(H, W) = map(int, input().split())
M = [input() for _ in range(H)]
INF = float('inf')
D = [[INF] * W for _ in range(H)]
D[0][0] = 0 if M[0][0] == '.' else 1
q = set([(0, 0)])
while q:
	nq = set()
	for (y, x) in q:
		d = D[y][x]
		m = M[y][x]
		if x < W - 1:
			t = d if M[y][x + 1] == m else d + 1
			D[y][x + 1] = min(D[y][x + 1], t)
			nq.add((y, x + 1))
		if y < H - 1:
			t = d if M[y + 1][x] == m else d + 1
			D[y + 1][x] = min(D[y + 1][x], t)
			nq.add((y + 1, x))
	q = nq
print(math.ceil(D[H - 1][W - 1] / 2))


(H, W) = map(int, input().split(' '))
s = []
for _ in range(H):
	s.append(input())
dp = [[10 ** 9 for i in range(W)] for j in range(H)]
dp[0][0] = 0 if s[0][0] == '.' else 1
for i in range(H):
	for j in range(W):
		if i + 1 < H:
			cost = int(s[i][j] == '.' and s[i + 1][j] == '#')
			dp[i + 1][j] = min(dp[i + 1][j], dp[i][j] + cost)
		if j + 1 < W:
			cost = int(s[i][j] == '.' and s[i][j + 1] == '#')
			dp[i][j + 1] = min(dp[i][j + 1], dp[i][j] + cost)
print(dp[H - 1][W - 1])


def main():
	import sys
	input = sys.stdin.buffer.readline
	(h, w) = map(int, input().split())
	s = [c // 8 for _ in range(h) for c in input()[:w]]
	dp = [10 ** 9] * h * w
	dp[0] = 5 - s[0]
	for i in range(h):
		for j in range(w):
			k = i * w + j
			if j + 1 < w:
				t = dp[k] + (s[k] ^ s[k + 1])
				if dp[k + 1] > t:
					dp[k + 1] = t
			if i + 1 < h:
				t = dp[k] + (s[k] ^ s[k + w])
				if dp[k + w] > t:
					dp[k + w] = t
	print(dp[-1] + 1 >> 1)
main()


(h, w) = map(int, input().split())
a = lambda x: 1 if x == '#' else 0
S = [list(map(a, list(input()))) for _ in range(h)]
inf = 10 * 3
dp = [[inf] * 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] * (S[0][i] != S[0][i - 1])
for i in range(1, h):
	dp[i][0] = dp[i - 1][0] + S[i][0] * (S[i][0] != S[i - 1][0])
for i in range(1, h):
	for j in range(1, w):
		dp[i][j] = min(dp[i - 1][j] + S[i][j] * (S[i - 1][j] != S[i][j]), dp[i][j - 1] + S[i][j] * (S[i][j] != S[i][j - 1]))
print(dp[-1][-1])


(h, w) = map(int, input().split())
s = [list(map(str, input().rstrip())) for _ in range(h)]
dp = [[10001] * w for _ in range(h)]
if s[0][0] == '#':
	dp[0][0] = 1
else:
	dp[0][0] = 0
moves = [[1, 0], [0, 1]]
for y in range(h):
	for x in range(w):
		for m in moves:
			(ny, nx) = (y + m[0], x + m[1])
			if ny >= h or nx >= w:
				continue
			add = 0
			if s[y][x] == '.' and s[ny][nx] == '#':
				add = 1
			dp[ny][nx] = min(dp[ny][nx], dp[y][x] + add)
print(dp[-1][-1])


(h, w) = map(int, input().split())
maze = []
for i in range(h):
	t = list(input())
	maze.append(t)
dx = [1, 0]
dy = [0, 1]
dp = [[10000] * w for i in range(h)]
if maze[0][0] == '#':
	dp[0][0] = 1
else:
	dp[0][0] = 0
for x in range(w):
	for y in range(h):
		for (dxi, dyi) in zip(dx, dy):
			if not (0 <= x + dxi < w and 0 <= y + dyi < h):
				continue
			dp[y + dyi][x + dxi] = min(dp[y + dyi][x + dxi], dp[y][x] + (maze[y][x] == '.' and maze[y + dyi][x + dxi] == '#'))
print(dp[h - 1][w - 1])


import sys
readline = sys.stdin.readline
sys.setrecursionlimit(10 ** 8)
mod = 10 ** 9 + 7
INF = 10 ** 18
eps = 10 ** (-7)
(H, W) = map(int, readline().split())
s = [readline().rstrip() for i in range(H)]
dp = [[INF] * W for i in range(H)]
dp[0][0] = 0 if s[0][0] == '.' else 1
for i in range(H):
	ii = max(0, i - 1)
	for j in range(W):
		jj = max(0, j - 1)
		dp[i][j] = min(dp[ii][j] + (s[i][j] != s[ii][j]), dp[i][jj] + (s[i][j] != s[i][jj]))
print((dp[H - 1][W - 1] + 1) // 2)


(h, w) = map(int, input().split())
s = [input() for _ in range(h)]
domain = [[10000] * w for _ in range(h)]
domain[0][0] = int(s[0][0] == '#')
for x in range(1, h):
	domain[x][0] = domain[x - 1][0] + (int(s[x][0] == '#') if s[x - 1][0] == '.' else 0)
for y in range(1, w):
	domain[0][y] = domain[0][y - 1] + int(s[0][y] == '#' if s[0][y - 1] == '.' else 0)
	for x in range(1, h):
		domain[x][y] = min(domain[x - 1][y] + int(s[x][y] == '#' if s[x - 1][y] == '.' else 0), domain[x][y - 1] + int(s[x][y] == '#' if s[x][y - 1] == '.' else 0))
print(domain[-1][-1])


(H, W) = map(int, input().split())
s = [list(input()) for _ in range(H)]
dp = [[0] * W for _ in range(H)]
dp[0][0] = int(s[0][0] == '#')
for i in range(1, W):
	dp[0][i] = dp[0][i - 1] + (int(s[0][i] == '#') if s[0][i - 1] == '.' else 0)
for h in range(1, H):
	dp[h][0] = dp[h - 1][0] + (int(s[h][0] == '#') if s[h - 1][0] == '.' else 0)
	for w in range(1, W):
		dp[h][w] = min(dp[h - 1][w] + (int(s[h][w] == '#') if s[h - 1][w] == '.' else 0), dp[h][w - 1] + (int(s[h][w] == '#') if s[h][w - 1] == '.' else 0))
print(dp[-1][-1])


(h, w) = map(int, input().split())
s = [input() for _ in range(h)]
dp = [[10 ** 9] * w for _ in range(h)]
dp[0][0] = (s[0][0] == '#') + 0
for i in range(h):
	for j in range(w):
		a = dp[i - 1][j]
		b = dp[i][j - 1]
		if s[i - 1][j] == '.' and s[i][j] == '#':
			a += 1
		if s[i][j - 1] == '.' and s[i][j] == '#':
			b += 1
		dp[i][j] = min(a, b, dp[i][j])
print(dp[-1][-1])


(h, w) = map(int, input().split())
sw = [list(input()) for _ in range(h)]
result = [[10 ** 5 for i in range(w)] for j in range(h)]
result[0][0] = 0
for i in range(h):
	for j in range(w):
		if j > 0:
			result[i][j] = result[i][j - 1] + (sw[i][j - 1] != sw[i][j])
		if i > 0:
			result[i][j] = min(result[i][j], result[i - 1][j] + (sw[i - 1][j] != sw[i][j]))
if sw[0][0] == '#':
	print(1 + result[h - 1][w - 1] // 2)
else:
	print(result[h - 1][w - 1] // 2 + (sw[0][0] != sw[h - 1][w - 1]))


(h, w) = map(int, input().split())
s = []
for i in range(h):
	s.append(list(input()))
dp = [[99999999 for i in range(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 s[i][j - 1] != s[i][j]:
			left = dp[i][j - 1] + 1
		else:
			left = dp[i][j - 1]
		if s[i - 1][j] != s[i][j]:
			top = dp[i - 1][j] + 1
		else:
			top = dp[i - 1][j]
		dp[i][j] = min(dp[i][j], left, top)
print((dp[h - 1][w - 1] + 1) // 2)


from collections import deque
(h, w) = map(int, input().split())
l = ['@' * (w + 2)]
for i in range(h):
	l.append('@' + input() + '@')
l.append('@' * (w + 2))
s = [[-1 for i in j] for j in l]
s[1][1] = l[1][1] == '#'
q = deque([[1, 1]])
while len(q) > 0:
	(x, y) = q.popleft()
	for (i, j) in [[1, 0], [0, 1]]:
		if l[i + x][j + y] != '@' and s[i + x][j + y] == -1:
			if l[x][y] == l[i + x][j + y]:
				q.appendleft([i + x, j + y])
				s[i + x][j + y] = s[x][y]
			else:
				q.append([i + x, j + y])
				s[i + x][j + y] = s[x][y] + 1
print(-s[h][w] // 2 * -1)


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 - s[0][0] - s[-1][-1]) // 2)


(H, W) = map(int, input().split())
M = [input() for _ in '_' * H]
D = [[0] * -~W for _ in '_' * -~H]
m = 999
for i in range(H):
	for j in range(W):
		D[i + 1][j + 1] = min([m, D[i][j + 1] + (M[i - 1][j] > M[i][j])][i > 0], [m, D[i + 1][j] + (M[i][j - 1] > M[i][j])][j > 0], m * (i + j > 0))
print(D[-1][-1] + (M[0][0] < '.'))


def main():
	import sys
	b = sys.stdin.buffer
	(h, w) = map(int, b.readline().split())
	x = w + 1
	s = [c >> 3 for c in b.read()]
	dp = [10000] * h * x
	a = p = s[0]
	dp[0] = b = q = 5 - a
	r = range(1, w)
	for i in r:
		t = s[i]
		b += a ^ t
		dp[i] = b
		a = t
	for i in range(x, h * x, x):
		t = s[i]
		q += p ^ t
		dp[i] = b = q
		a = p = t
		for _ in r:
			i += 1
			si = s[i]
			b += a ^ si
			j = i - x
			t = dp[j] + (s[j] ^ si)
			if b > t:
				b = t
			dp[i] = b
			a = si
	print(b + 1 >> 1)
main()


(H, W) = map(int, input().split())
field = [['.'] * (W + 1)]
for _ in range(H):
	tmp = ['.']
	tmp.extend(list(input()))
	field.append(tmp)
dp = [[10 ** 9] * (W + 1) for _ in range(H + 1)]
dp[1][0] = 0
dp[0][1] = 0
for h in range(1, H + 1):
	for w in range(1, W + 1):
		if field[h][w] == '.':
			dp[h][w] = min(dp[h - 1][w], dp[h][w - 1])
		else:
			u = dp[h - 1][w] if field[h - 1][w] == '#' else dp[h - 1][w] + 1
			l = dp[h][w - 1] if field[h][w - 1] == '#' else dp[h][w - 1] + 1
			dp[h][w] = min(u, l)
print(dp[-1][-1])


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

def ch(x1, y1, x2, y2):
	if B[x1][y1] == '.' and B[x2][y2] == '#':
		return 1
	else:
		return 0
dp = [[0 for j in range(w)] for i in range(h)]
for i in range(h):
	for j in range(w):
		if i == 0 and j == 0 and (B[i][j] == '#'):
			dp[i][j] += 1
		elif i == 0:
			dp[i][j] = dp[i][j - 1] + ch(i, j - 1, i, j)
		elif j == 0:
			dp[i][j] = dp[i - 1][j] + ch(i - 1, j, i, j)
		else:
			dp[i][j] = min(dp[i][j - 1] + ch(i, j - 1, i, j), dp[i - 1][j] + ch(i - 1, j, i, j))
print(dp[h - 1][w - 1])


def main():
	(h, w) = map(int, input().split())
	s = [[i == '.' for i in input()] for _ in range(h)]
	dp = [[10000] * w for _ in range(h)]
	dp[0][0] = 1 - s[0][0]
	for r in range(1, h):
		dp[r][0] = dp[r - 1][0] + (s[r - 1][0] and (not s[r][0]))
	for c in range(1, w):
		dp[0][c] = dp[0][c - 1] + (s[0][c - 1] and (not s[0][c]))
	for r in range(1, h):
		for c in range(1, w):
			dp[r][c] = min(dp[r - 1][c] + (s[r - 1][c] and (not s[r][c])), dp[r][c - 1] + (s[r][c - 1] and (not s[r][c])))
	print(dp[-1][-1])
main()


(H, W) = map(int, input().split())
S = [[c for c in input()] for _ in range(H)]
dp = [[0] * W for _ in range(H)]
for y in range(H):
	for x in range(W):
		if y - 1 < 0 and x - 1 < 0:
			dp[y][x] = int(S[y][x] != '.')
		elif y - 1 < 0:
			dp[y][x] = dp[y][x - 1] + (S[y][x] != S[y][x - 1])
		elif x - 1 < 0:
			dp[y][x] = dp[y - 1][x] + (S[y][x] != S[y - 1][x])
		else:
			dp[y][x] = min(dp[y - 1][x] + (S[y][x] != S[y - 1][x]), dp[y][x - 1] + (S[y][x] != S[y][x - 1]))
print((dp[H - 1][W - 1] + 1) // 2)


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


(h, w) = map(int, input().split())
mat = [[] for _ in range(h)]
for i in range(h):
	mat[i] = input()
dp = [[float('inf')] * w for _ in range(h)]
if mat[0][0] == '#':
	dp[0][0] = 1
else:
	dp[0][0] = 0
for i in range(h):
	for j in range(w):
		if mat[i][j - 1] != mat[i][j]:
			left = dp[i][j - 1] + 1
		else:
			left = dp[i][j - 1]
		if mat[i - 1][j] != mat[i][j]:
			top = dp[i - 1][j] + 1
		else:
			top = dp[i - 1][j]
		dp[i][j] = min(dp[i][j], left, top)
print((dp[h - 1][w - 1] + 1) // 2)


(h, w) = map(int, input().split())
s = [list(input()) for _ in range(h)]
cnt = [[float('inf')] * w for _ in range(h)]
if s[0][0] == '.':
	cnt[0][0] = 0
else:
	cnt[0][0] = 1
for i in range(h):
	for j in range(w):
		for (dy, dx) in [[1, 0], [0, 1]]:
			x = j + dx
			y = i + dy
			if x >= w or y >= h:
				continue
			if s[i][j] == s[y][x]:
				cnt[y][x] = min(cnt[y][x], cnt[i][j])
			else:
				cnt[y][x] = min(cnt[y][x], cnt[i][j] + 1)
if s[-1][-1] == '#':
	cnt[-1][-1] += 1
print(cnt[-1][-1] // 2)


(H, W) = map(int, input().split())
S = [input() for _ in range(H)]
INF = 10 ** 18
dp = [[INF 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] == '.':
			dp[i][j] = min(dp[i][j], dp[i - 1][j], dp[i][j - 1])
		else:
			dp[i][j] = min(dp[i][j], dp[i - 1][j] if S[i - 1][j] == '#' else dp[i - 1][j] + 1, dp[i][j - 1] if S[i][j - 1] == '#' else dp[i][j - 1] + 1)
print(dp[-1][-1])


from collections import deque
INF = float('inf')
(H, W) = map(int, input().split())
S = [input() for _ in range(H)]
dp = [[INF] * W for _ in range(H)]
dp[0][0] = int(S[0][0] == '#')
Q = deque([(dp[0][0], 0, 0)])
while Q:
	(cur, i, j) = Q.popleft()
	for (ni, nj) in [(i + 1, j), (i, j + 1)]:
		if H <= ni or W <= nj:
			continue
		c = int(S[i][j] != S[ni][nj])
		if dp[ni][nj] > cur + c:
			dp[ni][nj] = cur + c
			Q.append((cur + c, ni, nj))
print((dp[H - 1][W - 1] + 1) // 2)


(h, *s) = open(0)
(h, w) = map(int, h.split())
dp = [[9000000000.0] * w for _ in s]
dp[0][0] = s[0][0] < '.'
for i in range(h * w):
	(i, j) = (i // w, i % w)
	for (y, x) in ((i + 1, j), (i, j + 1)):
		if y < h and x < w:
			dp[y][x] = min(dp[y][x], dp[i][j] + (s[i][j] == '.' > s[y][x]))
print(dp[-1][-1])


(H, W) = map(int, input().split())
S = tuple((tuple(input()) for _ in range(H)))
dp = [[10 ** 9 for _ in range(W)] for __ in range(H)]
dp[0][0] = int(S[0][0] != '.')
for i in range(H):
	for j in range(W):
		for (di, dj) in [[0, 1], [1, 0]]:
			ni = i + di
			nj = j + dj
			if 0 <= ni < H and 0 <= nj < W:
				WB = S[i][j] == '.' and S[ni][nj] == '#'
				dp[ni][nj] = min(dp[ni][nj], dp[i][j] + int(WB))
print(dp[-1][-1])


INF = int(1000000000.0) + 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
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(dp[h - 1][w - 1])


(h, w) = map(int, input().split())
s = [input() for _ in range(h)]
dp = [[float('inf')] * w for i in range(h)]
dp[0][0] = 1 if s[0][0] == '#' else 0
for x in range(h):
	for y in range(w):
		if x + 1 < h:
			a = 1 if s[x][y] == '.' and s[x + 1][y] == '#' else 0
			dp[x + 1][y] = min(dp[x][y] + a, dp[x + 1][y])
		if y + 1 < w:
			a = 1 if s[x][y] == '.' and s[x][y + 1] == '#' else 0
			dp[x][y + 1] = min(dp[x][y] + a, dp[x][y + 1])
print(dp[h - 1][w - 1])


import sys
input = sys.stdin.readline
(H, W) = map(int, input().split())
s = [input() for _ in range(H)]
dp = [[float('inf')] * W for _ in range(H)]
dp[0][0] = 1 if s[0][0] == '#' else 0
for i in range(H):
	for j in range(W):
		if i > 0:
			if s[i - 1][j] == '.' and s[i][j] == '#':
				dp[i][j] = dp[i - 1][j] + 1
			else:
				dp[i][j] = dp[i - 1][j]
		if j > 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[-1][-1])


MAX = 1000000
(H, W) = map(int, input().split())
S0 = '.' + '#' * (W - 1)
X0 = [MAX] * W
X0[0] = 0
for _ in range(H):
	S = input()
	X = [None] * W
	for i in range(W):
		sc1 = MAX
		sc2 = MAX
		if i > 0:
			sc1 = X[i - 1] + (1 if S[i - 1] == '.' and S[i] == '#' else 0)
		sc2 = X0[i] + (1 if S0[i] == '.' and S[i] == '#' else 0)
		X[i] = min(sc1, sc2)
	X0 = X
	S0 = S
print(X0[-1])


(_, *s) = open(0)
t = '.'
b = t * 101
r = range(101)
i = 0
for s in s:
	a = [i]
	i += 1
	for (x, y, z, c) in zip(b, t + s, s, r):
		a += (min(c + (t > z < x), a[-1] + (t > z < y)),)
	(b, r) = (s, a[1:])
print(a[-2])


(H, W) = map(int, input().split())
s = [list(input()) for _ in range(H)]
inf = 10 ** 9
dp = [[inf] * W for _ in range(H)]
dp[0][0] = 0 if s[0][0] == '.' else 1
for y in range(H):
	for x in range(W):
		if y < H - 1:
			dp[y + 1][x] = min(dp[y + 1][x], dp[y][x] + (1 if s[y][x] == '.' and s[y + 1][x] == '#' else 0))
		if x < W - 1:
			dp[y][x + 1] = min(dp[y][x + 1], dp[y][x] + (1 if s[y][x] == '.' and s[y][x + 1] == '#' else 0))
print(dp[-1][-1])


from heapq import *

def main():
	(h, w) = map(int, input().split())
	s = [input() for _ in range(h)]
	g = h * w + 1
	e = [[] for _ in range(g)]
	for i in range(h):
		for j in range(w):
			for (y, x) in ((i + 1, j), (i, j + 1)):
				if y < h and x < w:
					if s[i][j] == '.' and s[y][x] != '.':
						e[i * w + j] += ((1, y * w + x),)
					else:
						e[i * w + j] += ((0, y * w + x),)
	e[g - 1] += ((s[0][0] != '.', 0),)
	q = [g - 1]
	d = [10 ** 12] * g
	while q:
		c = heappop(q)
		(c, v) = (c // g, c % g)
		if c > d[v]:
			continue
		d[v] = c
		for (x, w) in e[v]:
			x += c
			if d[w] > x:
				d[w] = x
				heappush(q, x * g + w)
	print(d[g - 2])
main()


(H, W) = map(int, input().split())
L = [input() for _ in range(H)]
inf = 10 ** 9 + 7
dp = [[inf] * W for _ in range(H)]
if L[0][0] == '.':
	dp[0][0] = 0
else:
	dp[0][0] = 1
for i in range(H):
	for j in range(W):
		if i == 0 and j == 0:
			continue
		a = dp[i][j - 1]
		b = dp[i - 1][j]
		if L[i - 1][j] == '.' and L[i][j] == '#':
			b += 1
		if L[i][j - 1] == '.' and L[i][j] == '#':
			a += 1
		dp[i][j] = min(dp[i][j], a, b)
print(dp[-1][-1])


(H, W) = map(int, input().split())
S = [list(input()) for i in range(H)]
N = [[10 ** 9] * W] * H
l = 0
u = 0
if S[0][0] == '#':
	N[0][0] = 1
else:
	N[0][0] = 0
for i in range(H):
	for j in range(W):
		if i == 0 and j == 0:
			continue
		l = N[i][j - 1]
		u = N[i - 1][j]
		if S[i][j - 1] == '.' and S[i][j] == '#':
			l += 1
		if S[i - 1][j] == '.' and S[i][j] == '#':
			u += 1
		N[i][j] = min(l, u)
print(N[-1][-1])


import sys
(H, W) = map(int, input().split())
G = [list(sys.stdin.readline().strip()) for _ in range(H)]
DP = [[0] * W for _ in range(H)]
DP[0][0] = int(G[0][0] == '#')
for i in range(1, H):
	DP[i][0] = DP[i - 1][0] + int(G[i][0] == '#' and G[i - 1][0] == '.')
for j in range(1, W):
	DP[0][j] = DP[0][j - 1] + int(G[0][j] == '#' and G[0][j - 1] == '.')
for i in range(1, H):
	for j in range(1, W):
		t = int(G[i][j] == '#')
		DP[i][j] = min(DP[i - 1][j] + int(t and G[i - 1][j] == '.'), DP[i][j - 1] + int(t and G[i][j - 1] == '.'))
print(DP[H - 1][W - 1])


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


INF = 10 ** 18
(H, W) = map(int, input().split())
G = [list(input()) for i in range(H)]
dp = [[INF] * W for i in range(H)]
dp[0][0] = 0
dx = [0, 1]
dy = [1, 0]
for i in range(H):
	for j in range(W):
		for (x, y) in zip(dx, dy):
			if i + x >= H or j + y >= W:
				continue
			if G[i][j] == '.' and G[i + x][j + y] == '#':
				dp[i + x][j + y] = min(dp[i][j] + 1, dp[i + x][j + y])
			else:
				dp[i + x][j + y] = min(dp[i][j], dp[i + x][j + y])
ans = dp[H - 1][W - 1]
print(ans if G[0][0] != '#' else ans + 1)


(h, w) = map(int, input().split())
tb = [input() for _ in range(h)]
st = [[0 for _ in range(w)] for _ in range(h)]
for i in range(h):
	for j in range(w):
		if i == 0 and j == 0:
			st[i][j] = 1 if tb[i][j] == '#' else 0
		else:
			tr = td = 999999999
			if i != 0:
				td = st[i - 1][j] + (1 if tb[i - 1][j] == '.' and tb[i][j] == '#' else 0)
			if j != 0:
				tr = st[i][j - 1] + (1 if tb[i][j - 1] == '.' and tb[i][j] == '#' else 0)
			st[i][j] = min(td, tr)
print(st[h - 1][w - 1])


(h, w) = map(int, input().split())
s = [input() for _i in range(h)]
visit = [[float('inf') for _ in range(w)] for _j in range(h)]
visit[0][0] = 0
for i in range(h):
	for j in range(w):
		if i - 1 >= 0:
			visit[i][j] = visit[i - 1][j] + (s[i][j] != s[i - 1][j])
		if j - 1 >= 0:
			visit[i][j] = min(visit[i][j], visit[i][j - 1] + (s[i][j] != s[i][j - 1]))
if s[0][0] == s[h - 1][w - 1] == '.':
	print(visit[h - 1][w - 1] // 2)
elif s[0][0] == s[h - 1][w - 1] == '#':
	print(visit[h - 1][w - 1] // 2 + 1)
else:
	print(visit[h - 1][w - 1] // 2 + 1)


(h, w) = map(int, input().split())
m = []
for i in range(h):
	m.append(list(map(lambda x: int(x == '#'), list(input()))) + [0])
m.append([0 for i in range(w + 1)])
s = [[100000 for i in range(w + 1)] for j in range(h + 1)]
s[-1][0] = 0
for i in range(h):
	for j in range(w):
		s[i][j] = min(s[i - 1][j] + (not m[i - 1][j] and m[i][j]), s[i][j - 1] + (not m[i][j - 1] and m[i][j]))
print(s[-2][-2])


(h, w) = map(int, input().split())
s = ['*' + '.' + '*' * w] + ['*' + input() + '*' for i in range(h)] + ['*' * (w + 2)]
b = 10 ** 9
d = [[b] * (w + 2)] + [[b] + [0] * w + [b] for _ in range(h)] + [[b] * (w + 2)]
d[0][1] = 0
for i in range(1, h + 1):
	for j in range(1, w + 1):
		d[i][j] = min(d[i - 1][j] + (s[i][j] == '#') * (s[i - 1][j] == '.'), d[i][j - 1] + (s[i][j] == '#') * (s[i][j - 1] == '.'))
print(d[h][w])


def main():
	import sys
	input = sys.stdin.buffer.readline
	(h, w) = map(int, input().split())
	s = [c < 46 and 1 or 0 for _ in range(h) for c in input()[:w]]
	dp = [10 ** 9] * h * w
	dp[0] = s[0]
	for i in range(h * w):
		(j, k) = (i // w, i % w)
		for (y, x) in ((j + 1, k), (j, k + 1)):
			if y < h and x < w:
				z = y * w + x
				t = dp[i] + (s[i] ^ s[z])
				if dp[z] > t:
					dp[z] = t
	print(dp[-1] + 1 >> 1)
main()


(h, w) = map(int, input().split())
s = [input() for i in range(h)]
inf = 10 ** 18
dp = [[inf] * (w + 1) for i in range(h + 1)]
if s[0][0] == '#':
	dp[0][0] = 1
else:
	dp[0][0] = 0
for i in range(h):
	for j in range(w):
		for (y, x) in ([1, 0], [0, 1]):
			(ni, nj) = (i + y, j + x)
			if ni >= h or nj >= w:
				continue
			c = 0
			if s[ni][nj] == '#' and s[i][j] == '.':
				c = 1
			dp[ni][nj] = min(dp[ni][nj], dp[i][j] + c)
print(dp[h - 1][w - 1])


(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] == '#' and meizu[h][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] == '#' and meizu[h][w] == '.' else dp[h][w])
print(dp[-1][-1])


(H, W) = map(int, input().split())
grid = tuple((tuple(map(lambda x: x == '.', input())) for _ in range(H)))
dp = [float('inf')] * W
dp[0] = 0
prow = [True] * W
for row in grid:
	ndp = [None] * W
	ndp[0] = dp[0] + int(prow[0] and (not row[0]))
	for i in range(1, W):
		ndp[i] = min(ndp[i - 1] + int(row[i - 1] and (not row[i])), dp[i] + int(prow[i] and (not row[i])))
	prow = row
	dp = ndp
print(dp[-1])


(h, w) = map(int, input().split())
S = [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:
			if S[0][0] == '#':
				dp[0][0] = 1
			continue
		if i:
			u = dp[i - 1][j]
			if S[i - 1][j] == '.' and S[i][j] == '#':
				u += 1
		else:
			u = float('inf')
		if j:
			v = dp[i][j - 1]
			if S[i][j - 1] == '.' and S[i][j] == '#':
				v += 1
		else:
			v = float('inf')
		dp[i][j] = min(u, v)
print(dp[-1][-1])


from collections import deque
(t, *g) = open(0)
(h, w) = map(int, t.split())
vis = [[1000000000.0] * w for _ in range(h)]
vis[0][0] = int(g[0][0] == '#')
q = deque([(0, 0, vis[0][0])])
while q:
	(cy, cx, c) = q.popleft()
	for (ny, nx) in ((cy + 1, cx), (cy, cx + 1)):
		cc = c
		if not (0 <= ny < h and 0 <= nx < w):
			continue
		if g[cy][cx] == '.' and g[ny][nx] == '#':
			cc += 1
		if cc < vis[ny][nx]:
			vis[ny][nx] = cc
			q.append((ny, nx, cc))
print(vis[-1][-1])


(H, W) = map(int, input().split())
S = [input() for _ in range(H)]
dp = [[100000] * W for _ in range(H)]
dp[0][0] = int(S[0][0] == '#')
for x in range(1, W):
	dp[0][x] = dp[0][x - 1] + (int(S[0][x] == '#') if S[0][x - 1] == '.' else 0)
for y in range(1, H):
	dp[y][0] = dp[y - 1][0] + (int(S[y][0] == '#') if S[y - 1][0] == '.' else 0)
	for x in range(1, W):
		dp[y][x] = min(dp[y][x - 1] + (int(S[y][x] == '#') if S[y][x - 1] == '.' else 0), dp[y - 1][x] + (int(S[y][x] == '#') if S[y - 1][x] == '.' else 0))
print(dp[-1][-1])


(H, W) = list(map(int, input().split()))
l = [list(input()) for i in range(H)]
inf = 10 ** 9
DP = [[inf] * W for i in range(H)]
DP[0][0] = 0 if l[0][0] == '.' else 1
for i in range(H):
	for j in range(W):
		if i > 0:
			DP[i][j] = min(DP[i][j], DP[i - 1][j] + 1) if l[i - 1][j] == '.' and l[i][j] == '#' else min(DP[i][j], DP[i - 1][j])
		if j > 0:
			DP[i][j] = min(DP[i][j], DP[i][j - 1] + 1) if l[i][j - 1] == '.' and l[i][j] == '#' else min(DP[i][j], DP[i][j - 1])
print(DP[H - 1][W - 1])


(h, w) = map(int, input().split())
g = [input() for i in range(h)]
d = [[200] * w for i in range(h)]
d[0][0] = g[0][0] == '#'
for i in range(h):
	for j in range(w):
		if i + 1 < h:
			d[i + 1][j] = min(d[i + 1][j], d[i][j] + (g[i + 1][j] == '#' and g[i][j] == '.'))
		if j + 1 < w:
			d[i][j + 1] = min(d[i][j + 1], d[i][j] + (g[i][j + 1] == '#' and g[i][j] == '.'))
print(d[-1][-1])


inf = float('inf')
(h, w) = map(int, input().split())
D = [[inf] * w for _ in range(h)]
D[0][0] = 0
S = [list(input()) for _ in range(h)]
for i in range(h):
	for j in range(w):
		for (x, y) in ((1, 0), (0, 1)):
			(X, Y) = (i + x, j + y)
			if 0 <= X < h and 0 <= Y < w:
				if S[i][j] == '.' and S[X][Y] == '#':
					D[X][Y] = min(D[i][j] + 1, D[X][Y])
				else:
					D[X][Y] = min(D[i][j], D[X][Y])
ans = D[h - 1][w - 1]
print(ans if S[0][0] != '#' else ans + 1)


(H, W) = map(int, input().split())
field = list((list(input()) for _ in range(H)))
dp = list((list((float('INF') for _ in range(W))) for _ in range(H)))
dp[0][0] = 1 if field[0][0] == '#' else 0
for x in range(W):
	for y in range(H):
		if y < H - 1:
			dp[y + 1][x] = min(dp[y + 1][x], dp[y][x] + 1 if field[y + 1][x] == '#' and field[y][x] == '.' else dp[y][x])
		if x < W - 1:
			dp[y][x + 1] = min(dp[y][x + 1], dp[y][x] + 1 if field[y][x + 1] == '#' and field[y][x] == '.' else dp[y][x])
print(dp[H - 1][W - 1])


(H, W) = [int(s) for s in input().split()]
map = []
for i in range(H):
	map.append(input())
op = [[0 for i in range(W)] for j in range(H)]
op[0][0] = int(map[0][0] == '#')
for i in range(1, W):
	op[0][i] = op[0][i - 1] + int(map[0][i] == '#' and map[0][i - 1] == '.')
for i in range(1, H):
	op[i][0] = op[i - 1][0] + int(map[i][0] == '#' and map[i - 1][0] == '.')
for i in range(1, H):
	for j in range(1, W):
		op[i][j] = min(op[i - 1][j] + int(map[i][j] == '#' and map[i - 1][j] == '.'), op[i][j - 1] + int(map[i][j] == '#' and map[i][j - 1] == '.'))
print(op[H - 1][W - 1])


(h, w) = map(int, input().split())
d = [0] + [300] * w
for i in range(h):
	s = input()
	if i == 0:
		a = s[0]
	for j in range(w):
		t = s[j] == a
		d[j] += t ^ (d[j] % 2 == 0)
		if j > 0:
			d[j] = min(d[j], d[j - 1] + t ^ (d[j - 1] % 2 == 0))
print((d[-2] + (a == '#') + 1) // 2)