All of us love treasures, right? That's why young Vasya is heading for a Treasure Island.

Treasure Island may be represented as a rectangular table $n \times m$ which is surrounded by the ocean. Let us number rows of the field with consecutive integers from $1$ to $n$ from top to bottom and columns with consecutive integers from $1$ to $m$ from left to right. Denote the cell in $r$-th row and $c$-th column as $(r, c)$. Some of the island cells contain impassable forests, and some cells are free and passable. Treasure is hidden in cell $(n, m)$.

Vasya got off the ship in cell $(1, 1)$. Now he wants to reach the treasure. He is hurrying up, so he can move only from cell to the cell in next row (downwards) or next column (rightwards), i.e. from cell $(x, y)$ he can move only to cells $(x+1, y)$ and $(x, y+1)$. Of course Vasya can't move through cells with impassable forests.

Evil Witch is aware of Vasya's journey and she is going to prevent him from reaching the treasure. Before Vasya's first move she is able to grow using her evil magic impassable forests in previously free cells. Witch is able to grow a forest in any number of any free cells except cells $(1, 1)$ where Vasya got off his ship and $(n, m)$ where the treasure is hidden.

Help Evil Witch by finding out the minimum number of cells she has to turn into impassable forests so that Vasya is no longer able to reach the treasure.


-----Input-----

First line of input contains two positive integers $n$, $m$ ($3 \le n \cdot m \le 1\,000\,000$), sizes of the island.

Following $n$ lines contains strings $s_i$ of length $m$ describing the island, $j$-th character of string $s_i$ equals "#" if cell $(i, j)$ contains an impassable forest and "." if the cell is free and passable. Let us remind you that Vasya gets of his ship at the cell $(1, 1)$, i.e. the first cell of the first row, and he wants to reach cell $(n, m)$, i.e. the last cell of the last row.

It's guaranteed, that cells $(1, 1)$ and $(n, m)$ are empty.


-----Output-----

Print the only integer $k$, which is the minimum number of cells Evil Witch has to turn into impassable forest in order to prevent Vasya from reaching the treasure.


-----Examples-----
Input
2 2
..
..

Output
2

Input
4 4
....
#.#.
....
.#..

Output
1

Input
3 4
....
.##.
....

Output
2



-----Note-----

The following picture illustrates the island in the third example. Blue arrows show possible paths Vasya may use to go from $(1, 1)$ to $(n, m)$. Red illustrates one possible set of cells for the Witch to turn into impassable forest to make Vasya's trip from $(1, 1)$ to $(n, m)$ impossible. [Image]

Source: codeforces | Difficulty: HARD
Tags: String algorithms

Dynamic programming

Graph traversal

Flows and cuts


Solutions:
import sys
input = sys.stdin.readline
(n, m) = list(map(int, input().split()))
MAP = [list(input().strip()) for i in range(n)]
from collections import deque
Q = deque()
Q.append([0, 0])
while Q:
	(x, y) = Q.pop()
	if x + 1 < n and MAP[x + 1][y] == '.':
		MAP[x + 1][y] = 1
		Q.append([x + 1, y])
	if y + 1 < m and MAP[x][y + 1] == '.':
		MAP[x][y + 1] = 1
		Q.append([x, y + 1])
Q.append([n - 1, m - 1])
while Q:
	(x, y) = Q.pop()
	if x - 1 >= 0 and MAP[x - 1][y] == 1:
		MAP[x - 1][y] = 0
		Q.append([x - 1, y])
	if y - 1 >= 0 and MAP[x][y - 1] == 1:
		MAP[x][y - 1] = 0
		Q.append([x, y - 1])
if MAP[n - 1][m - 1] != 1:
	print(0)
	return
SCORE = [0] * (n + m + 5)
for i in range(n):
	for j in range(m):
		if MAP[i][j] == 0:
			SCORE[i + j] += 1
if 1 in SCORE:
	print(1)
else:
	print(2)


from sys import stdin
from collections import defaultdict
(n, m) = list(map(int, input().split()))
if n == 1 or m == 1:
	if '#' in stdin.read():
		print(0)
	else:
		print(1)
	return
graph = []
for i in range(n):
	graph.append(input())

def dfs(visited):
	reachable = []
	stack = []
	stack.append((0, 0))
	while stack:
		(node_r, node_c) = stack.pop()
		if not visited[node_r][node_c]:
			visited[node_r][node_c] = True
			reachable.append((node_r, node_c))
			if node_r + 1 < n and (not visited[node_r + 1][node_c]) and (graph[node_r + 1][node_c] != '#'):
				stack.append((node_r + 1, node_c))
			if node_c + 1 < m and (not visited[node_r][node_c + 1]) and (graph[node_r][node_c + 1] != '#'):
				stack.append((node_r, node_c + 1))
			if node_r == n - 1 and node_c == m - 1:
				break
	return reachable
visited = [[False for j in range(m)] for i in range(n)]
dfs(visited)
if not visited[n - 1][m - 1]:
	print(0)
else:
	visited[0][0] = False
	visited[n - 1][m - 1] = False
	dfs(visited)
	if visited[n - 1][m - 1]:
		print(2)
	else:
		print(1)


import sys
import collections as cc
input = sys.stdin.readline
(n, m) = map(int, input().split())
ar = [list(input().strip()) for i in range(n)]
q = cc.deque()
q.append([0, 0])
while q:
	(x, y) = q.pop()
	if x + 1 < n and ar[x + 1][y] == '.':
		ar[x + 1][y] = 1
		q.append([x + 1, y])
	if y + 1 < m and ar[x][y + 1] == '.':
		ar[x][y + 1] = 1
		q.append([x, y + 1])
q = cc.deque()
q.append([n - 1, m - 1])
while q:
	(x, y) = q.pop()
	if x - 1 >= 0 and ar[x - 1][y] == 1:
		ar[x - 1][y] = 0
		q.append([x - 1, y])
	if y - 1 >= 0 and ar[x][y - 1] == 1:
		ar[x][y - 1] = 0
		q.append([x, y - 1])
if ar[n - 1][m - 1] != 1:
	print(0)
else:
	ans = [0] * (n + m + 10)
	for i in range(n):
		for j in range(m):
			if ar[i][j] == 0:
				ans[i + j] += 1
	if 1 in ans:
		print(1)
	else:
		print(2)


import sys
input = sys.stdin.readline
(n, m) = [int(item) for item in input().split()]
field = []
field.append('#' * (m + 2))
for i in range(n):
	field.append('#' + input().rstrip() + '#')
field.append('#' * (m + 2))
visited = [[False] * (m + 2) for _ in range(n + 2)]
for i in range(2):
	q = [(1, 1)]
	while q:
		(x, y) = q.pop()
		if visited[x][y]:
			continue
		visited[x][y] = True
		if field[x + 1][y] != '#' and (not visited[x + 1][y]):
			q.append((x + 1, y))
		if field[x][y + 1] != '#' and (not visited[x][y + 1]):
			q.append((x, y + 1))
		if x == n and y == m:
			break
	if x != n or y != m:
		print(i)
		exit()
	visited[1][1] = False
	visited[n][m] = False
print(2)


import sys
(n, m) = map(int, input().split())
o_map = ['.' * (m + 2)]
o_map.extend(['.' + sys.stdin.readline() + '.' for i in range(n)])
o_map.append(['.' * (m + 2)])
f_method = [[0] * (m + 2) for i in range(n + 2)]
r_method = [[0] * (m + 2) for i in range(n + 2)]
MOD = 10 ** 9 + 93
f_method[1][1] = 1
for i in range(1, n + 1):
	for j in range(1, m + 1):
		if o_map[i][j] == '.' and i + j != 2:
			f_method[i][j] = (f_method[i - 1][j] + f_method[i][j - 1]) % MOD
r_method[n][m] = 1
for i in range(n, 0, -1):
	for j in range(m, 0, -1):
		if o_map[i][j] == '.' and i + j != m + n:
			r_method[i][j] = (r_method[i + 1][j] + r_method[i][j + 1]) % MOD
if f_method[n][m] == 0:
	print(0)
else:
	for i in range(1, n + 1):
		for j in range(1, m + 1):
			if i + j in [2, m + n]:
				continue
			if f_method[i][j] * r_method[i][j] % MOD == f_method[n][m]:
				print(1)
				exit()
	print(2)


from collections import defaultdict
from sys import stdin
(n, m) = map(int, input().split())
g = ['.' * (m + 1)]
for _ in range(n):
	g.append('.' + stdin.readline())

def solve(n, m, g):
	t = [[0] * (m + 2) for j in range(n + 2)]
	t[0][1] = 1
	t[n + 1][m] = 1
	for i in range(1, n + 1):
		for j in range(1, m + 1):
			if g[i][j] == '#':
				t[i][j] = 0
			else:
				t[i][j] = max(t[i - 1][j], t[i][j - 1])
	if t[n][m] == 0:
		return 0
	d = defaultdict(int)
	for i in range(n, 0, -1):
		for j in range(m, 0, -1):
			if t[i][j] == 0:
				continue
			else:
				t[i][j] = max(t[i + 1][j], t[i][j + 1])
			if t[i][j] == 1:
				v = i - 1 + j - 1
				d[v] += 1
	return min((d[x] for x in range(1, n + m - 2)))
r = solve(n, m, g)
print(r)


import sys
from io import BytesIO, IOBase
from collections import defaultdict, deque

class FastIO(IOBase):
	newlines = 0

	def __init__(self, file):
		import os
		self.os = os
		self._fd = file.fileno()
		self.buffer = BytesIO()
		self.writable = 'x' in file.mode or 'r' not in file.mode
		self.write = self.buffer.write if self.writable else None
		self.BUFSIZE = 8192

	def read(self):
		while True:
			b = self.os.read(self._fd, max(self.os.fstat(self._fd).st_size, self.BUFSIZE))
			if not b:
				break
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines = 0
		return self.buffer.read()

	def readline(self):
		while self.newlines == 0:
			b = self.os.read(self._fd, max(self.os.fstat(self._fd).st_size, self.BUFSIZE))
			self.newlines = b.count(b'\n') + (not b)
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines -= 1
		return self.buffer.readline()

	def flush(self):
		if self.writable:
			self.os.write(self._fd, self.buffer.getvalue())
			(self.buffer.truncate(0), self.buffer.seek(0))

class IOWrapper(IOBase):

	def __init__(self, file):
		self.buffer = FastIO(file)
		self.flush = self.buffer.flush
		self.writable = self.buffer.writable
		self.write = lambda s: self.buffer.write(s.encode('ascii'))
		self.read = lambda : self.buffer.read().decode('ascii')
		self.readline = lambda : self.buffer.readline().decode('ascii')
(sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))
input = lambda : sys.stdin.readline().rstrip('\r\n')

def get_int():
	return int(input())

def get_ints():
	return list(map(int, input().split(' ')))

def get_int_grid(n):
	return [get_ints() for _ in range(n)]

def get_str():
	return input().strip()

def get_strs():
	return get_str().split(' ')

def flat_list(arr):
	return [item for subarr in arr for item in subarr]

def yes_no(b):
	if b:
		return 'YES'
	else:
		return 'NO'

def binary_search(good, left, right, delta=1, right_true=False):
	limits = [left, right]
	while limits[1] - limits[0] > delta:
		if delta == 1:
			mid = sum(limits) // 2
		else:
			mid = sum(limits) / 2
		if good(mid):
			limits[int(right_true)] = mid
		else:
			limits[int(~right_true)] = mid
	if good(limits[int(right_true)]):
		return limits[int(right_true)]
	else:
		return False

def prefix_sums(a):
	p = [0]
	for x in a:
		p.append(p[-1] + x)
	return p

def solve_a():
	n = get_int()
	d = get_int()
	e = get_int()
	best = float('inf')
	while n >= 0:
		best = min(best, n % d)
		n -= 5 * e
	return best

def solve_b():
	b = get_int()
	g = get_int()
	n = get_int()
	return min(b, n) - max(0, n - g) + 1

def solve_c():
	n = get_int()
	s = get_str()
	open = 0
	for (idx, char) in enumerate(s):
		if char == '(':
			open += 1
		else:
			open -= 1
		if open < -1:
			return False
	return open == 0

def solve_d():
	(n, m) = get_ints()
	grid = [['#'] * (m + 2)]
	for row in range(n):
		grid.append(['#'] + list(get_str()) + ['#'])
	grid.append(['#'] * (m + 2))
	if n > 5 * 10 ** 5:
		for i in range(n):
			if grid[i + 1][1] == '#':
				return 0
		return 1
	if m > 5 * 10 ** 5:
		for j in range(m):
			if grid[1][j + 1] == '#':
				return 0
		return 1
	queue = deque([(1, 1)])
	vis_forward = [[0] * (m + 2) for _ in range(n + 2)]
	while queue:
		(x, y) = queue.popleft()
		if not vis_forward[x][y]:
			vis_forward[x][y] = 1
			if grid[x + 1][y] == '.':
				queue.append((x + 1, y))
			if grid[x][y + 1] == '.':
				queue.append((x, y + 1))
	back_queue = deque([(n, m)])
	vis_backward = [[0] * (m + 2) for _ in range(n + 2)]
	while back_queue:
		(x, y) = back_queue.popleft()
		if not vis_backward[x][y]:
			vis_backward[x][y] = 1
			if grid[x - 1][y] == '.':
				back_queue.append((x - 1, y))
			if grid[x][y - 1] == '.':
				back_queue.append((x, y - 1))
	score = [0] * (n + m - 1)
	if not vis_forward[n][m] or not vis_backward[1][1]:
		return 0
	for i in range(n):
		for j in range(m):
			score[i + j] += vis_forward[i + 1][j + 1] * vis_backward[i + 1][j + 1]
	if not max(score[0], score[-1]):
		return 0
	else:
		return min(2, min(score[1:-1]))
print(solve_d())


import os, sys, time
from io import BytesIO, IOBase
from collections import deque as dq
BUFSIZE = 8192

class FastIO(IOBase):
	newlines = 0

	def __init__(self, file):
		import os
		self.os = os
		self._fd = file.fileno()
		self.buffer = BytesIO()
		self.writable = 'x' in file.mode or 'r' not in file.mode
		self.write = self.buffer.write if self.writable else None

	def read(self):
		while True:
			b = self.os.read(self._fd, max(self.os.fstat(self._fd).st_size, BUFSIZE))
			if not b:
				break
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines = 0
		return self.buffer.read()

	def readline(self):
		while self.newlines == 0:
			b = self.os.read(self._fd, max(self.os.fstat(self._fd).st_size, BUFSIZE))
			self.newlines = b.count(b'\n') + (not b)
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines -= 1
		return self.buffer.readline()

	def flush(self):
		if self.writable:
			self.os.write(self._fd, self.buffer.getvalue())
			(self.buffer.truncate(0), self.buffer.seek(0))

class IOWrapper(IOBase):

	def __init__(self, file):
		self.buffer = FastIO(file)
		self.flush = self.buffer.flush
		self.writable = self.buffer.writable
		self.write = lambda s: self.buffer.write(s.encode('ascii'))
		self.read = lambda : self.buffer.read().decode('ascii')
		self.readline = lambda : self.buffer.readline().decode('ascii')
(sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))
input = lambda : sys.stdin.readline().rstrip('\r\n')
(N, M) = list(map(int, input().split()))
if N > 500000:
	flag = False
	for i in range(N):
		x = input()
		if x == '#':
			flag = True
	if flag:
		print(0)
	else:
		print(1)
	sys.exit(0)
if M > 500000:
	x = list(input())
	if '#' in x:
		print(0)
	else:
		print(1)
	sys.exit(0)
tmp = ['#'] * (M + 2)
S = tmp[:]
for _ in range(N):
	S += ['#'] + list(input()) + ['#']
S += tmp
N += 2
M += 2
size = N * M
dist = [0] * size
Q = dq([M + 1])
used1 = [0] * size
used1[M + 1] = 1
dist[M + 1] = 0
while Q:
	i = Q.popleft()
	tmp = []
	if S[i + 1] == '.':
		tmp.append(i + 1)
	if S[i + M] == '.':
		tmp.append(i + M)
	for j in tmp:
		if not used1[j]:
			dist[j] = dist[i] + 1
			used1[j] = 1
			Q.append(j)
Q = dq([size - M - 2])
used2 = [0] * size
used2[size - M - 2] = 1
while Q:
	i = Q.popleft()
	tmp = []
	if S[i - 1] == '.':
		tmp.append(i - 1)
	if S[i - M] == '.':
		tmp.append(i - M)
	for j in tmp:
		if not used2[j]:
			used2[j] = 1
			Q.append(j)
dist[size - M - 2] = 0
D = [0] * size
flag = False
for j in range(size):
	if used1[j] and used2[j]:
		D[dist[j]] += 1
		flag = True
if not flag:
	print(0)
elif 1 in D:
	print(1)
else:
	print(2)


from collections import *
import sys

def main():
	(r, c) = map(int, sys.stdin.readline().strip().split())
	grid = [list(sys.stdin.readline().strip()) for _ in range(r)]
	n = sum((u.count('#') for u in grid))
	if n == 0:
		if r == 1:
			print(1)
		elif c == 1:
			print(1)
		else:
			print(2)
		return
	if r == c == 2:
		print(2 - n)
		return
	grid[0][0] = '0'
	for i in range(r):
		for j in range(c):
			if grid[i][j] == '#':
				continue
			f = False
			if i != 0:
				f = f or grid[i - 1][j] == '0'
			if j != 0:
				f = f or grid[i][j - 1] == '0'
			if f:
				grid[i][j] = '0'
	grid[-1][-1] = '1'
	for i in range(r - 1, -1, -1):
		for j in range(c - 1, -1, -1):
			if grid[i][j] != '0':
				continue
			if i != r - 1 and grid[i + 1][j] == '1':
				grid[i][j] = '1'
			elif j != c - 1 and grid[i][j + 1] == '1':
				grid[i][j] = '1'
	if grid[0][0] != '1':
		print(0)
		return
	dictionary = Counter()
	for i in range(r):
		for j in range(c):
			if grid[i][j] == '1':
				dictionary[i + j] += 1
	for key in dictionary:
		if 0 < key < r + c - 2 and dictionary[key] == 1:
			print(1)
			return
	print(2)
main()


import sys
readLn = sys.stdin.readline

def __starting_point():
	(n, m) = list(map(int, readLn().split()))
	ds = [[-1 if c == '#' else 0 for c in readLn()] for _ in range(n)]
	ds[0][0] = 1
	for i in range(0, n):
		for j in range(0, m):
			if ds[i][j] == 0:
				if i > 0 and ds[i - 1][j] > 0:
					ds[i][j] = ds[i - 1][j] + 1
				if j > 0 and ds[i][j - 1] > 0:
					ds[i][j] = ds[i][j - 1] + 1
	if ds[n - 1][m - 1] == 0:
		print(0)
	else:
		ds[n - 1][m - 1] = -2
		sm = [0 for _ in range(n + m + 1)]
		for i in range(n - 1, -1, -1):
			for j in range(m - 1, -1, -1):
				if ds[i][j] > 1 and (i + 1 < n and ds[i + 1][j] == -2 or (j + 1 < m and ds[i][j + 1] == -2)):
					sm[ds[i][j]] += 1
					ds[i][j] = -2
		ans = 2
		for i in range(2, n + m):
			if sm[i] == 1:
				ans = 1
				break
		print(ans)
__starting_point()


import sys
input = sys.stdin.readline
t = 1
for _ in range(t):
	(n, m) = (int(x) for x in input().split())
	mat = [input() for x in range(n)]
	dp = [[0 for x in range(m + 1)] for y in range(n + 1)]
	for i in range(n - 1, -1, -1):
		for j in range(m - 1, -1, -1):
			if mat[i][j] == '#':
				dp[i][j] = 0
			elif i == n - 1 and j == m - 1:
				dp[i][j] = 1
			elif i == n - 1:
				dp[i][j] = dp[i][j + 1]
			elif j == m - 1:
				dp[i][j] = dp[i + 1][j]
			else:
				dp[i][j] = dp[i + 1][j] + dp[i][j + 1]
	if dp[0][0] == 0:
		print(0)
		break
	ans = 2
	(r1, c1, r2, c2) = (0, 0, 0, 0)
	for i in range(n + m - 2 - 1):
		if dp[r1 + 1][c1] != 0:
			r1 += 1
		else:
			c1 += 1
		if dp[r2][c2 + 1] != 0:
			c2 += 1
		else:
			r2 += 1
		if r1 == r2 and c1 == c2:
			ans = 1
			break
	print(ans)


from heapq import heappush, heappop
from collections import deque, defaultdict, Counter
import itertools
from itertools import permutations
import sys
import bisect
import string
import math
import time
ts = time.time()
sys.setrecursionlimit(10 ** 6)

def SI():
	return input().split()

def MI():
	return map(int, input().split())

def I():
	return int(input())

def LI():
	return [int(i) for i in input().split()]
YN = ['Yes', 'No']
mo = 10 ** 9 + 7
from math import log
input = sys.stdin.readline
pr = False

def tprint(*a):
	if pr:
		print(*a)
	return
(n, m) = MI()
mp = [[1] * (m + 2)]
if m == 1:
	for i in range(n):
		for j in list(input()):
			if j == '#':
				print(0)
				exit()
	print(1)
	exit()
for i in range(n):
	a = [1]
	for j in list(input()):
		if j == '#':
			a.append(1)
		else:
			a.append(0)
	mp.append(a + [1])
mp.append([1] * (m + 2))

def search():
	go = [[0] * (m + 2) for _ in range(n + 2)]
	go[0][1] = 1
	for i in range(1, n + 1):
		for j in range(1, m + 1):
			if mp[i][j] != 1:
				if go[i - 1][j] + go[i][j - 1] > 0:
					go[i][j] = 1
	go[0][1] = 0
	return go

def bc_search(go):
	bc = [[0] * (m + 2) for _ in range(n + 2)]
	bc[n + 1][m] = 1
	for i in range(n, 0, -1):
		for j in range(m, 0, -1):
			if go[i][j] != 0:
				if bc[i + 1][j] + bc[i][j + 1] > 0:
					bc[i][j] = 1
	bc[n + 1][m] = 0
	return bc
go = search()
bc = bc_search(go)
G = [[0] * (m + 3)]
G += [[0] + [bc[i][j] for j in range(m + 2)] for i in range(n + 2)]
for i in range(n + 2):
	for j in range(m + 2):
		G[i + 1][j + 1] += G[i + 1][j] + G[i][j + 1] - G[i][j]
if go[n][m] == 0:
	ans = 0
else:
	ans = 2
	for i in range(1, n + 1):
		for j in range(1, m + 1):
			if i * j == 1 or i * j == n * m:
				continue
			s = 0
			if j + 1 < m + 3 + 10:
				s += G[i][m + 2] - G[i][j + 1]
			if i + 1 < n + 3 + 10:
				s += G[n + 2][j] - G[i + 1][j]
			if s == 0:
				ans = 1
				tprint(i, j, G[i + 1][j + 1])
print(ans)


import sys
input = sys.stdin.readline
(n, m) = map(int, input().split())
if n == 1:
	f = input().strip()
	if '#' in f:
		print(0)
	else:
		print(1)
	sys.exit()
if m == 1:
	f = input().strip()
	for i in range(n):
		if '#' == f:
			print(0)
			break
		f = input().strip()
	else:
		print(1)
	sys.exit()
a = []
for i in range(n):
	b = input().strip()
	d = []
	for j in range(m):
		if b[j] == '.':
			d.append(1)
		else:
			d.append(0)
	a.append(d)
gr = [[] for i in range(n * m + 5)]
for i in range(2, n + 1):
	for j in range(2, m + 1):
		if a[i - 2][j - 1] == 1:
			gr[(i - 1) * m + j].append((i - 2) * m + j)
		if a[i - 1][j - 2] == 1:
			gr[(i - 1) * m + j].append((i - 1) * m + j - 1)
for i in range(2, n + 1):
	if a[i - 2][0] == 1:
		gr[(i - 1) * m + 1].append((i - 2) * m + 1)
for j in range(2, m + 1):
	if a[0][j - 2] == 1:
		gr[j].append(j - 1)
if a[n - 1][m - 2] == 1:
	gr[n * m].append(n * m - 1)
if a[n - 2][m - 1] == 1:
	gr[n * m].append(n * m - m)
v = [False for i in range(n * m + 6)]
if a[n - 1][m - 2] == 1:
	s = [n * m - 1]
	t = True
	while s and t:
		x = s.pop()
		if x == 1:
			t = False
		v[x] = True
		for j in gr[x]:
			if v[j]:
				continue
			s.append(j)
ans = 0
if v[1]:
	ans += 1
v[1] = False
if a[n - 2][m - 1] == 1:
	s = [n * m - m]
	while s:
		x = s.pop()
		v[x] = True
		for j in gr[x]:
			if v[j]:
				continue
			s.append(j)
if v[1]:
	ans += 1
print(ans)


import sys
(n, m) = list(map(int, input().split()))
fields = ['#' * (2 + m)] + ['#' + sys.stdin.readline().rstrip() + '#' for i in range(n)] + ['#' * (2 + m)]
visited = [[False] * (m + 2) for i in range(n + 2)]
for i in range(2):
	q = [(1, 1)]
	while q:
		(x, y) = q.pop()
		if visited[x][y]:
			continue
		visited[x][y] = True
		if fields[x + 1][y] != '#' and (not visited[x + 1][y]):
			q.append((x + 1, y))
		if fields[x][y + 1] != '#' and (not visited[x][y + 1]):
			q.append((x, y + 1))
		if x == n and y == m:
			break
	if x != n or y != m:
		print(i)
		return
	visited[1][1] = False
	visited[n][m] = False
print(2)


import os
import sys
from io import BytesIO, IOBase
BUFSIZE = 8192

class FastIO(IOBase):
	newlines = 0

	def __init__(self, file):
		self._fd = file.fileno()
		self.buffer = BytesIO()
		self.writable = 'x' in file.mode or 'r' not in file.mode
		self.write = self.buffer.write if self.writable else None

	def read(self):
		while True:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			if not b:
				break
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines = 0
		return self.buffer.read()

	def readline(self):
		while self.newlines == 0:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			self.newlines = b.count(b'\n') + (not b)
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines -= 1
		return self.buffer.readline()

	def flush(self):
		if self.writable:
			os.write(self._fd, self.buffer.getvalue())
			(self.buffer.truncate(0), self.buffer.seek(0))

class IOWrapper(IOBase):

	def __init__(self, file):
		self.buffer = FastIO(file)
		self.flush = self.buffer.flush
		self.writable = self.buffer.writable
		self.write = lambda s: self.buffer.write(s.encode('ascii'))
		self.read = lambda : self.buffer.read().decode('ascii')
		self.readline = lambda : self.buffer.readline().decode('ascii')
(sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))
input = lambda : sys.stdin.readline().rstrip('\r\n')
from math import gcd, ceil

def pre(s):
	n = len(s)
	pi = [0] * n
	for i in range(1, n):
		j = pi[i - 1]
		while j and s[i] != s[j]:
			j = pi[j - 1]
		if s[i] == s[j]:
			j += 1
		pi[i] = j
	return pi

def prod(a):
	ans = 1
	for each in a:
		ans = ans * each
	return ans

def lcm(a, b):
	return a * b // gcd(a, b)

def binary(x, length=16):
	y = bin(x)[2:]
	return y if len(y) >= length else '0' * (length - len(y)) + y

def dfs(graph, start=0):
	n = len(graph)
	dp = [0] * n
	(visited, finished) = ([False] * n, [False] * n)
	stack = [start]
	while stack:
		start = stack[-1]
		if not visited[start]:
			visited[start] = True
			for child in graph[start]:
				if not visited[child]:
					stack.append(child)
		else:
			stack.pop()
			dp[start] += 1
			for child in graph[start]:
				if finished[child]:
					dp[start] += dp[child]
			finished[start] = True
	return visited
for _ in range(int(input()) if not True else 1):
	(n, m) = map(int, input().split())
	a = ['' for __ in range(n)]
	for __ in range(n):
		a[__] = input()
	vis = [[0] * m for __ in range(n)]
	vis[0][0] = 1
	for i in range(n):
		for j in range(m):
			if a[i][j] == '#' or not vis[i][j]:
				continue
			if j != m - 1 and a[i][j + 1] != '#':
				vis[i][j + 1] = True
			if i != n - 1 and a[i + 1][j] != '#':
				vis[i + 1][j] = True
	if not vis[n - 1][m - 1]:
		print(0)
		quit()
	vis2 = [[0] * m for __ in range(n)]
	vis2[n - 1][m - 1] = 1
	for i in range(n - 1, -1, -1):
		for j in range(m - 1, -1, -1):
			if a[i][j] == '#' or not vis2[i][j]:
				continue
			if j != 0 and a[i][j - 1] != '#':
				vis2[i][j - 1] = 1
			if i != 0 and a[i - 1][j] != '#':
				vis2[i - 1][j] = 1
	di = [0] * (n + m + 10)
	cc = 0
	for i in range(2, n * m):
		(x, y) = ((i - 1) // m, (i - 1) % m)
		if vis[x][y] and vis2[x][y]:
			dist = n - 1 - x + m - 1 - y
			di[dist] += 1
			if di[dist] == 1:
				cc += 1
			elif di[dist] == 2:
				cc -= 1
	print(1 if cc else 2)


from sys import stdin

def main():
	(n, m) = map(int, input().split())
	field = stdin.read()
	if n == 1 or m == 1:
		return print('10'['#' in field])
	field = [c == '.' for c in field]
	field += (False,) * (m + 2)
	(visited1, visited2) = ([False] * len(field) for _ in '12')
	cnt = [0] * (n + m)
	m += 1
	visited1[0] = visited2[n * m - 2] = True
	for i in range(n * m - 2, 0, -1):
		if field[i] and (visited2[i + 1] or visited2[i + m]):
			visited2[i] = True
	for i in range(n * m):
		if field[i] and (visited1[i - 1] or visited1[i - m]):
			visited1[i] = True
			if visited2[i]:
				cnt[i // m + i % m] += 1
	print(min(cnt[1:-2]))
main()