AtCoder Beginner Contest 088 - Grid Repainting

We have an H \times W grid whose squares are painted black or white. The square at the i-th row from the top and the j-th column from the left is denoted as (i, j).
Snuke would like to play the following game on this grid. At the beginning of the game, there is a character called Kenus at square (1, 1). The player repeatedly moves Kenus up, down, left or right by one square. The game is completed when Kenus reaches square (H, W) passing only white squares.
Before Snuke starts the game, he can change the color of some of the white squares to black. However, he cannot change the color of square (1, 1) and (H, W). Also, changes of color must all be carried out before the beginning of the game.
When the game is completed, Snuke's score will be the number of times he changed the color of a square before the beginning of the game. Find the maximum possible score that Snuke can achieve, or print -1 if the game cannot be completed, that is, Kenus can never reach square (H, W) regardless of how Snuke changes the color of the squares.  
The color of the squares are given to you as characters s_{i, j}. If square (i, j) is initially painted by white, s_{i, j} is .; if square (i, j) is initially painted by black, s_{i, j} is #.

Source: atcoder | Difficulty: MEDIUM


Solutions:
from queue import Queue
(h, w) = map(int, input().split(' '))
s = [list(input()) for _ in range(h)]
num_w = 0
for i in range(h):
	num_w += s[i].count('#')
for i in range(h):
	s[i] = ['#'] + s[i] + ['#']
s.insert(0, ['#' for i in range(w + 2)])
s.append(['#' for i in range(w + 2)])
q = Queue()
cnt = 0
q.put([1, 1, 0])
s[1][1] = '#'
Z = -1
while not q.empty():
	(x, y, cnt) = q.get()
	if (x, y) == (h, w):
		Z = cnt
		break
	for (i, j) in [(x + 1, y), (x - 1, y), (x, y + 1), (x, y - 1)]:
		if s[i][j] != '#':
			s[i][j] = '#'
			q.put([i, j, cnt + 1])
if Z == -1:
	print(-1)
else:
	print(h * w - Z - 1 - num_w)


(H, W) = map(int, input().split())
s = []
black = 0
for i in range(H):
	l = list(input())
	for j in range(W):
		if l[j] == '#':
			black += 1
	s.append(l)
white = H * W - black
from collections import deque
q = deque([(0, 0, 0)])
s[0][0] = '#'
while q:
	(x, y, cnt) = q.popleft()
	for (dx, dy) in [(0, 1), (0, -1), (1, 0), (-1, 0)]:
		(nx, ny) = (x + dx, y + dy)
		if 0 <= nx < H and 0 <= ny < W and (s[nx][ny] != '#'):
			if nx == H - 1 and ny == W - 1:
				print(white - cnt - 2)
				exit(0)
			s[nx][ny] = '#'
			q.append((nx, ny, cnt + 1))
print(-1)


from collections import deque
(h, w) = map(int, input().split())
m = [input() for _ in [0] * h]
v = [[-1] * w for _ in [0] * h]
q = deque([[0, 0]])
v[0][0] = 0
c = sum((t.count('#') for t in m))
while q:
	(y, x) = q.popleft()
	for (i, j) in ([1, 0], [-1, 0], [0, 1], [0, -1]):
		(t, u) = (y + i, x + j)
		if t + 1 and t < h and u + 1 and (u < w) and (m[t][u] == '.') and (v[t][u] < 0):
			v[t][u] = v[y][x] + 1
			q.append([t, u])
print(-(v[h - 1][w - 1] < 0) or h * w - c - v[h - 1][w - 1] - 1)


(H, W) = map(int, input().split())
s = [list(input()) for _ in range(H)]
total_white = 0
for i in s:
	total_white += i.count('.')
sh = 0
sw = 0
gh = H - 1
gw = W - 1
s[sh][sw] = 0
q = [[sh, sw]]
min_path = 0
while len(q) > 0:
	(h, w) = q.pop(0)
	if h == gh and w == gw:
		min_path = s[h][w]
		print(total_white - min_path - 1)
		exit()
	for (dh, dw) in ([0, 1], [0, -1], [1, 0], [-1, 0]):
		if 0 <= h + dh < H and 0 <= w + dw < W:
			if s[h + dh][w + dw] == '.':
				s[h + dh][w + dw] = s[h][w] + 1
				q.append([h + dh, w + dw])
print(-1)


from collections import deque
(h, w) = map(int, input().split())
s = [input() for _ in range(h)]
vi = [[-1 for _ in range(w)] for _ in range(h)]
st = deque()
st.append([0, 0, 0])
d = [[0, 1], [-1, 0], [1, 0], [0, -1]]
while st:
	(h1, w1, i) = st.popleft()
	if 0 <= h1 < h and 0 <= w1 < w and (vi[h1][w1] == -1) and (s[h1][w1] == '.'):
		vi[h1][w1] = i + 1
		for m in d:
			st.append([h1 + m[0], w1 + m[1], i + 1])
print(''.join(s).count('.') - vi[h - 1][w - 1] if vi[h - 1][w - 1] != -1 else -1)


(h, w) = map(int, input().split())
b = [['#'] * (w + 2)]
a = 0
for i in range(h):
	c = ['#']
	for j in input():
		a += j == '#'
		c.append(j)
	b.append(c + ['#'])
b += [['#'] * (w + 2)]
b[h][w] = 0
Q = [(1, 1)]
x = 0
y = -1
while Q:
	x += 1
	p = []
	for (i, j) in Q:
		for (dx, dy) in [(1, 0), (-1, 0), (0, 1), (0, -1)]:
			if b[i + dx][j + dy] == '.':
				p += [(i + dx, j + dy)]
				b[i + dx][j + dy] = '#'
			elif b[i + dx][j + dy] == 0:
				y = x
	if y > 0:
		break
	Q = p
if y > 0:
	print(h * w - a - y - 1)
else:
	print(-1)


(t, *g) = open(0)
(h, w) = map(int, t.split())
v = [[0] * w for _ in range(h)]
v[0][0] = 1
q = [(0, 0)]
while q:
	(a, b) = q.pop(0)
	for (c, d) in ((-1, 0), (0, -1), (1, 0), (0, 1)):
		x = a + c
		y = b + d
		if w > x >= 0 <= y < h and v[y][x] < 1 and (g[y][x] == '.'):
			q += [(x, y)]
			v[y][x] = v[b][a] + 1
t = v[-1][-1]
print((-1, sum((c.count('.') for c in g)) - t)[t > 0])


(h, w) = map(int, input().split())
l = [[1] * (w + 2)] + [[1] + [1 if i == '#' else 0 for i in input()] + [1] for i in range(h)] + [[1] * (w + 2)]
c = [[0] * (w + 2) for i in range(h + 2)]
q = [(1, 1)]
e = [(0, 1), (0, -1), (1, 0), (-1, 0)]
kyori = 1
while len(q) > 0 and c[h][w] == 0:
	tl = q
	q = []
	for (x, y) in tl:
		for (X, Y) in e:
			if l[y + Y][x + X] == 0 and c[y + Y][x + X] == 0:
				q.append((x + X, y + Y))
				c[y + Y][x + X] = 1
	kyori += 1
if c[h][w] == 0:
	print(-1)
else:
	print(sum([i.count(0) for i in l]) - kyori)


(h, w) = map(int, input().split())
g = [input() for _ in range(h)]
from collections import *

def bfs(x, y):
	d = [[-1] * w for _ in range(h)]
	d[x][y] = 0
	q = deque([(x, y)])
	while q:
		(tx, ty) = q.popleft()
		for (dx, dy) in [(1, 0), (0, 1), (-1, 0), (0, -1)]:
			(nx, ny) = (tx + dx, ty + dy)
			if 0 <= nx < h and 0 <= ny < w and (g[nx][ny] == '.') and (d[nx][ny] < 0):
				d[nx][ny] = d[tx][ty] + 1
				q.append((nx, ny))
	return d
d = bfs(0, 0)[-1][-1]
print((h * w - sum((s.count('#') for s in g)) - d) * (d > 0) - 1)


from collections import deque
(H, W) = map(int, input().split())
S = [input() for i in range(H)]
C = sum((i.count('.') for i in S))
dd = ((-1, 0), (0, -1), (1, 0), (0, 1))
que = deque([(0, 0, 0)])
used = {(0, 0)}
res = []
while que:
	(s, t, cost) = que.popleft()
	if s == H - 1 and t == W - 1:
		res = cost
		break
	for (di, dj) in dd:
		xi = s + di
		yj = t + dj
		if not 0 <= xi < H or not 0 <= yj < W or S[xi][yj] == '#' or ((xi, yj) in used):
			continue
		used.add((xi, yj))
		que.append((xi, yj, cost + 1))
if res:
	print(C - 1 - res)
else:
	print(-1)


from collections import deque
(H, W) = map(int, input().split())
S = []
count = 0
for _ in range(H):
	A = list(input())
	for a in A:
		if a == '.':
			count += 1
	S.append(A)
mas = deque([(0, 0, 0)])
while mas:
	(y, x, n) = mas.popleft()
	if 0 <= y <= H - 1 and 0 <= x <= W - 1:
		if S[y][x] == '.':
			S[y][x] = n
			mas.append((y + 1, x, n + 1))
			mas.append((y, x + 1, n + 1))
			mas.append((y - 1, x, n + 1))
			mas.append((y, x - 1, n + 1))
short = S[H - 1][W - 1]
if short == '.':
	print(-1)
else:
	print(count - (short + 1))


import sys
input = sys.stdin.readline
from collections import deque
(H, W) = map(int, input().split())
X = [1, 0, -1, 0]
Y = [0, -1, 0, 1]
num = 0
D = []
for i in range(H):
	s = list(input())
	num += s.count('.')
	D.append(s)
Q = deque()
Q.append((0, 0))
dist = [[-1] * W for i in range(H)]
dist[0][0] = 0
while Q:
	(y, x) = Q.popleft()
	for i in range(4):
		nx = x + X[i]
		ny = y + Y[i]
		if 0 <= nx < W and 0 <= ny < H and (dist[ny][nx] == -1) and (D[ny][nx] == '.'):
			dist[ny][nx] = dist[y][x] + 1
			Q.append((ny, nx))
if dist[H - 1][W - 1] == -1:
	print(-1)
else:
	print(num - dist[H - 1][W - 1] - 1)


from collections import deque
(H, W) = [int(i) for i in input().split()]
S = []
white = 0
for _ in range(H):
	s = input()
	white += s.count('.')
	S.append(list(s))
S[0][0] = ''
Q = deque([(0, 0, 1)])
while Q:
	(h, w, count) = Q.popleft()
	if (h, w) == (H - 1, W - 1):
		print(white - count)
		quit()
	for (nh, nw) in [(h, w + 1), (h, w - 1), (h + 1, w), (h - 1, w)]:
		if 0 <= nh < H and 0 <= nw < W and (S[nh][nw] == '.'):
			S[nh][nw] = ''
			Q.append((nh, nw, count + 1))
print(-1)


from collections import deque
(H, W) = map(int, input().split())
p = {}
for i in range(H):
	for (j, c) in enumerate(input()):
		p[i, j] = c == '.'
d = {(i, j): -1 for i in range(H) for j in range(W)}
white = sum(p.values())
q = deque()
s = (0, 0)
q.append(s)
d[s] = 1
while q:
	u = q.popleft()
	(ui, uj) = u
	for v in [(ui - 1, uj), (ui + 1, uj), (ui, uj - 1), (ui, uj + 1)]:
		(vi, vj) = v
		if 0 <= vi <= H - 1 and 0 <= vj <= W - 1 and p[v] and (d[v] == -1):
			d[v] = d[u] + 1
			q.append(v)
if d[H - 1, W - 1] == -1:
	ans = -1
else:
	ans = white - d[H - 1, W - 1]
print(ans)


from collections import deque
LOAD = '.'
(H, W) = map(int, input().split())
field = [['' for _ in range(W)] for _ in range(H)]
dist = [[-1 for _ in range(W)] for _ in range(H)]
for h in range(H):
	field[h] = list(input())
total_laod = 0
for f in field:
	total_laod += f.count(LOAD)
dx = [1, 0, -1, 0]
dy = [0, 1, 0, -1]
(sh, sw) = (0, 0)
(gh, gw) = (H - 1, W - 1)
dist[sh][sw] = 0
q = deque()
q.append((sh, sw))
while q:
	(h, w) = q.popleft()
	for i in range(4):
		nh = h + dy[i]
		nw = w + dx[i]
		if nh < 0 or H <= nh or nw < 0 or (W <= nw):
			continue
		if field[nh][nw] != LOAD:
			continue
		if dist[nh][nw] != -1:
			continue
		dist[nh][nw] = dist[h][w] + 1
		q.append((nh, nw))
if dist[gh][gw] == -1:
	print(-1)
else:
	print(total_laod - (dist[gh][gw] + 1))


from collections import deque
import sys
(H, W) = [int(x) for x in input().split()]
s = [list(input()) for _ in range(H)]
white = sum([s[i].count('.') for i in range(H)])
que = deque([(0, 0, 0)])
s[0][0] = '#'
while que:
	(y, x, d) = que.popleft()
	if (y, x) == (H - 1, W - 1):
		break
	for (dy, dx) in [(-1, 0), (1, 0), (0, -1), (0, 1)]:
		ny = y + dy
		nx = x + dx
		if ny < 0 or ny > H - 1 or nx < 0 or (nx > W - 1):
			continue
		if s[ny][nx] == '#':
			continue
		s[ny][nx] = '#'
		que.append((ny, nx, d + 1))
else:
	print(-1)
	sys.exit()
print(white - d - 1)


import queue
(h, w) = map(int, input().split())
d = [(0, 1), (1, 0), (0, -1), (-1, 0)]
s = [list(input()) for i in range(h)]
m = [[-1] * w for i in range(h)]
m[0][0] = 1
q = queue.Queue()
q.put((0, 0))
while not q.empty():
	p = q.get()
	for i in range(4):
		x = p[0] + d[i][0]
		y = p[1] + d[i][1]
		if 0 <= x < h and 0 <= y < w and (m[x][y] < 0) and (s[x][y] == '.'):
			q.put((x, y))
			m[x][y] = m[p[0]][p[1]] + 1
dis = m[h - 1][w - 1]
c = sum((si.count('.') for si in s))
print(c - dis if dis > 0 else -1)


import sys
(H, W) = list(map(int, input().split()))
sx = 0
sy = 0
gx = W - 1
gy = H - 1
ans = 0
A = [list((i for i in input())) for _ in range(H)]
for j in A:
	ans += j.count('.')
inf = -1
distance = [[inf] * W for _ in range(H)]
queue = []
queue.insert(0, (sy, sx))
distance[sy][sx] = 0
X = 0
while True:
	try:
		(y, x) = queue.pop()
	except:
		break
	for i in range(4):
		nx = x + (-1, 0, 1, 0)[i]
		ny = y + (0, -1, 0, 1)[i]
		if 0 <= nx and nx <= W - 1 and (0 <= ny) and (ny <= H - 1) and (A[ny][nx] != '#') and (distance[ny][nx] == inf):
			queue.insert(0, (ny, nx))
			distance[ny][nx] = distance[y][x] + 1
			A[ny][nx] = '!'
if distance[H - 1][W - 1] != inf:
	ans -= distance[gy][gx] + 1
	print(ans)
else:
	print(-1)


from collections import deque
(h, w) = list(map(int, input().split()))
queue = deque()
s = [list(input()) for _ in range(h)]
seen = [[False] * w for _ in range(h)]
queue.append([0, 0])
ans = [[1000000000] * w for _ in range(h)]
seen[0][0] = True
ans[0][0] = 1
for i in range(h * w * 10):
	if len(queue) == 0:
		break
	cnt = queue.popleft()
	if cnt[0] != 0:
		if seen[cnt[0] - 1][cnt[1]] == False and s[cnt[0] - 1][cnt[1]] == '.':
			queue.append([cnt[0] - 1, cnt[1]])
			ans[cnt[0] - 1][cnt[1]] = ans[cnt[0]][cnt[1]] + 1
			seen[cnt[0] - 1][cnt[1]] = True
	if cnt[1] != 0:
		if seen[cnt[0]][cnt[1] - 1] == False and s[cnt[0]][cnt[1] - 1] == '.':
			queue.append([cnt[0], cnt[1] - 1])
			ans[cnt[0]][cnt[1] - 1] = ans[cnt[0]][cnt[1]] + 1
			seen[cnt[0]][cnt[1] - 1] = True
	if cnt[0] != h - 1:
		if seen[cnt[0] + 1][cnt[1]] == False and s[cnt[0] + 1][cnt[1]] == '.':
			queue.append([cnt[0] + 1, cnt[1]])
			ans[cnt[0] + 1][cnt[1]] = ans[cnt[0]][cnt[1]] + 1
			seen[cnt[0] + 1][cnt[1]] = True
	if cnt[1] != w - 1:
		if seen[cnt[0]][cnt[1] + 1] == False and s[cnt[0]][cnt[1] + 1] == '.':
			queue.append([cnt[0], cnt[1] + 1])
			ans[cnt[0]][cnt[1] + 1] = ans[cnt[0]][cnt[1]] + 1
			seen[cnt[0]][cnt[1] + 1] = True
cnt2 = 0
for i in range(h):
	for j in range(w):
		if s[i][j] == '.':
			cnt2 += 1
if seen[-1][-1] == False:
	print(-1)
else:
	print(cnt2 - ans[-1][-1])


from collections import deque
(h, w) = map(int, input().split())
field = [input() for _ in range(h)]
d = [(1, 0), (-1, 0), (0, 1), (0, -1)]
white = 0
for i in range(h):
	white += field[i].count('.')
cnt = [[-1] * w for _ in range(h)]
cnt[0][0] = 0
q = deque([[0, 0]])
while q:
	(y, x) = q.pop()
	for (dy, dx) in d:
		ny = y + dy
		nx = x + dx
		if 0 <= ny < h and 0 <= nx < w and (field[ny][nx] == '.') and (cnt[ny][nx] < 0):
			cnt[ny][nx] = cnt[y][x] + 1
			q.appendleft([ny, nx])
		if ny == h - 1 and nx == w - 1:
			print(white - cnt[h - 1][w - 1] - 1)
			exit()
print(-1)


from collections import *
(h, w) = map(int, input().split())
s = [input() for _ in range(h)]
p = [[-1] * w for _ in range(h)]
p[0][0] = 1
d = ((1, 0), (-1, 0), (0, 1), (0, -1))
white = sum((row.count('.') for row in s))
queue = deque([(0, 0)])
clearable = False
while queue:
	(x, y) = queue.popleft()
	if x == w - 1 and y == h - 1:
		clearable = True
		break
	for (dx, dy) in d:
		(nx, ny) = (x + dx, y + dy)
		if not (0 <= nx < w and 0 <= ny < h):
			continue
		if s[ny][nx] == '#' or p[ny][nx] > 0:
			continue
		p[ny][nx] = p[y][x] + 1
		queue.append((nx, ny))
if clearable:
	print(white - p[h - 1][w - 1])
else:
	print(-1)


(h, w) = map(int, input().split())
g = [['#'] * (w + 2) for i in range(h + 2)]
c = 0
for i in range(h):
	g[i + 1][1:-1] = list(input())
	c += g[i + 1][1:-1].count('#')
d = {}
d[0] = [(1, 1)]
vi = set()
vi.add((1, 1))
i = 0
while d[i]:
	l = d[i]
	d[i + 1] = []
	for cur in l:
		for (a, b) in [[1, 0], [0, 1], [-1, 0], [0, -1]]:
			to = (cur[0] + a, cur[1] + b)
			if to == (h, w):
				print(h * w - c - i - 2)
				exit()
			if g[to[0]][to[1]] == '.' and to not in vi:
				vi.add(to)
				d[i + 1].append(to)
	i += 1
print(-1)


from collections import *
(H, W) = map(int, input().split())
S = [(W + 2) * ['#']] + list((['#'] + list(input()) + ['#'] for h in range(H))) + [(W + 2) * ['#']]
S[1][1] = 1
Q = deque([[1, 1]])
D = [[1, 0], [-1, 0], [0, 1], [0, -1]]
while Q:
	(x, y) = Q.popleft()
	for (dx, dy) in D:
		if S[x + dx][y + dy] == '.':
			S[x + dx][y + dy] = S[x][y] + 1
			Q.append([x + dx, y + dy])
if S[H][W] == '.':
	print(-1)
else:
	print((H + 2) * (W + 2) - sum((s.count('#') for s in S)) - S[H][W])


import queue
(H, W) = list(map(int, input().split()))
s = [list(input()) + ['#'] for i in range(H)] + [['#' for i in range(W + 1)]]
white = sum([s[i].count('.') for i in range(H)])
q = queue.Queue()
s[0][0] = 1
q.put((0, 0))
while not q.empty():
	(i, j) = q.get()
	for (x, y) in [(i + 1, j), (i - 1, j), (i, j + 1), (i, j - 1)]:
		if s[x][y] == '.':
			s[x][y] = s[i][j] + 1
			q.put((x, y))
if s[H - 1][W - 1] in ['.', '#']:
	print(-1)
else:
	print(white - s[H - 1][W - 1])


(h, w) = map(int, input().split())
s = [list(input()) for _ in range(h)]
q = [(0, 0)]
s[0][0] = 0
dxy = [(1, 0), (-1, 0), (0, 1), (0, -1)]
while q:
	(x, y) = q.pop(0)
	for (dx, dy) in dxy:
		(nx, ny) = (x + dx, y + dy)
		if not 0 <= nx < w:
			continue
		if not 0 <= ny < h:
			continue
		if s[ny][nx] == '#':
			continue
		if s[ny][nx] == '.':
			s[ny][nx] = s[y][x] + 1
			q.append((nx, ny))
		else:
			continue
if s[h - 1][w - 1] == '.' or s[h - 1][w - 1] == '#':
	print(-1)
else:
	kuro = 0
	for i in range(h):
		kuro += s[i].count('#')
	print(h * w - s[h - 1][w - 1] - 1 - kuro)


import queue
(h, w) = map(int, input().split())
s = [input() for i in range(h)]
white = 0
for i in range(h):
	white += s[i].count('.')
q = queue.Queue()
q.put([0, 0])
goal = [h - 1, w - 1]
visited = [[float('inf') for i in range(w)] for j in range(h)]
visited[0][0] = 0
move = [[0, 1], [0, -1], [1, 0], [-1, 0]]
while not q.empty():
	(a, b) = q.get()
	for (y, x) in move:
		if 0 <= a + y < h and 0 <= x + b < w:
			if s[a + y][x + b] == '.' and visited[a + y][x + b] == float('inf'):
				q.put([a + y, x + b])
				visited[a + y][x + b] = visited[a][b] + 1
print(white - visited[-1][-1] - 1 if visited[-1][-1] != float('inf') else -1)


from collections import deque
(H, W) = map(int, input().split())
S = [input() for _ in range(H)]
T = [[None] * W for _ in range(H)]
T[0][0] = 1
D = deque([(0, 0)])
while D:
	(h, w) = D.popleft()
	for (dh, dw) in ((1, 0), (0, 1), (-1, 0), (0, -1)):
		if 0 <= h + dh < H and 0 <= w + dw < W and (S[h + dh][w + dw] == '.') and (T[h + dh][w + dw] is None):
			T[h + dh][w + dw] = T[h][w] + 1
			D.append((h + dh, w + dw))
if T[H - 1][W - 1] is None:
	print(-1)
else:
	print(sum((s.count('.') for s in S)) - T[H - 1][W - 1])


from collections import deque, Counter

def main():
	with open(0) as f:
		(H, W) = map(int, f.readline().split())
		maze = [list(line) for line in f.readlines()]
	rank = [[None] * W for _ in range(H)]
	rank[0][0] = 0
	reserved = deque([(0, 0)])
	while len(reserved) > 0:
		(x, y) = reserved.popleft()
		for (u, v) in [(s, t) for (s, t) in [(x - 1, y), (x + 1, y), (x, y - 1), (x, y + 1)] if 0 <= s < H and 0 <= t < W]:
			if rank[u][v] is not None:
				continue
			if maze[u][v] == '.':
				rank[u][v] = rank[x][y] + 1
				reserved.append((u, v))
	if rank[H - 1][W - 1] is None:
		print(-1)
	else:
		counter = Counter()
		for line in maze:
			counter.update(line)
		print(counter['.'] - rank[H - 1][W - 1] - 1)
main()


from collections import deque
(H, W) = map(int, input().split())
graph = [input() for i in range(H)]
q = deque([(0, 0)])
dist = [[-1] * W for i in range(H)]
dist[0][0] = 1
while q:
	(y, x) = q.popleft()
	L = [(1, 0), (-1, 0), (0, 1), (0, -1)]
	for (i, j) in L:
		if (0 <= y + i <= H - 1 and 0 <= x + j <= W - 1) and dist[y + i][x + j] == -1 and (graph[y + i][x + j] == '.'):
			dist[y + i][x + j] = dist[y][x] + 1
			q.append((y + i, x + j))
white = 0
for i in range(H):
	white += graph[i].count('.')
if dist[H - 1][W - 1] == -1:
	print('-1')
else:
	ans = white - dist[H - 1][W - 1]
	print(ans)


from collections import deque

def bfs(start):
	q = deque([[start]])
	visited = set()
	while q:
		path = q.popleft()
		(i, j) = path[-1]
		if (i, j) == (H - 1, W - 1):
			return path
		for (di, dj) in [(1, 0), (-1, 0), (0, 1), (0, -1)]:
			(ni, nj) = (i + di, j + dj)
			if 0 <= ni < H and 0 <= nj < W and (field[ni][nj] != '#') and ((ni, nj) not in visited):
				q.append(path + [(ni, nj)])
				visited.add((ni, nj))
(H, W) = list(map(int, input().split()))
field = [input() for _ in range(H)]
shortest_path = bfs((0, 0))
if shortest_path is None:
	print(-1)
	return
ans = 0
for i in range(H):
	for j in range(W):
		if field[i][j] == '.' and (i, j) not in shortest_path:
			ans += 1
print(ans)


import sys
read = sys.stdin.read
from collections import deque

def main():
	(h, w) = map(int, input().split())
	wall_cnt = 0
	gg = list()
	gg.append([1] * (w + 2))
	for _ in range(h):
		row = tuple(input())
		wall_cnt += row.count('#')
		gg.append([1] + [c == '#' for c in row] + [1])
	gg.append([1] * (w + 2))
	g2 = [[0] * (w + 2) for _ in range(h + 2)]
	g2[1][1] = 1
	vs = deque()
	vs.append((1, 1))
	move_y = (0, 1, 0, -1)
	move_x = (1, 0, -1, 0)
	while vs:
		(y, x) = vs.popleft()
		ys = [y + i for i in move_y]
		xs = [x + i for i in move_x]
		for (yse, xse) in zip(ys, xs):
			if not gg[yse][xse]:
				vs.append((yse, xse))
				gg[yse][xse] = 1
				g2[yse][xse] = g2[y][x] + 1
	if g2[h][w] == 0:
		print(-1)
	else:
		ans = h * w - g2[h][w] - wall_cnt
		print(ans)

def __starting_point():
	main()
__starting_point()


from collections import deque
(H, W) = map(int, input().split())
src = [input() for i in range(H)]
walls = 0
for row in src:
	walls += row.count('#')
visited = [[0 for j in range(W)] for i in range(H)]
q = deque([(0, 0, 0)])
dxs = [1, 0, -1, 0]
dys = [0, 1, 0, -1]
while q:
	(d, x, y) = q.popleft()
	if (x, y) == (W - 1, H - 1):
		print(H * W - walls - d - 1)
		exit()
	for (dx, dy) in zip(dxs, dys):
		(nx, ny) = (x + dx, y + dy)
		if not 0 <= nx < W or not 0 <= ny < H:
			continue
		if src[ny][nx] == '#' or visited[ny][nx]:
			continue
		q.append((d + 1, nx, ny))
		visited[ny][nx] = 1
print(-1)


(H, W) = map(int, input().split())
grid = [None] * H
white = 0
for i in range(H):
	grid[i] = input()
	white += grid[i].count('.')
from collections import deque
q = deque()
q.append([0, 0, 0])
seen = [[False for i in range(W)] for j in range(H)]
while q:
	v = q.popleft()
	y = v[0]
	x = v[1]
	p = v[2]
	if grid[y][x] == '#' or seen[y][x]:
		continue
	if y == H - 1 and x == W - 1:
		print(white - (p + 1))
		break
	seen[y][x] = True
	if y - 1 >= 0:
		q.append([y - 1, x, p + 1])
	if y + 1 < H:
		q.append([y + 1, x, p + 1])
	if x - 1 >= 0:
		q.append([y, x - 1, p + 1])
	if x + 1 < W:
		q.append([y, x + 1, p + 1])
else:
	print(-1)


import sys
from collections import deque

def IN_I():
	return int(sys.stdin.readline().rstrip())

def IN_LI():
	return list(map(int, sys.stdin.readline().rstrip().split()))

def IN_S():
	return sys.stdin.readline().rstrip()

def IN_LS():
	return list(sys.stdin.readline().rstrip().split())
(H, W) = IN_LI()
s = [IN_S() for _ in range(H)]
dh = [-1, 0, 1, 0]
dw = [0, -1, 0, 1]
dist = [[-1] * W for j in range(H)]
dist[0][0] = 0
q = deque()
q.append([0, 0])
while q:
	now = q.popleft()
	now_h = now[0]
	now_w = now[1]
	for i in range(4):
		next_h = now_h + dh[i]
		next_w = now_w + dw[i]
		if not (0 <= next_h < H and 0 <= next_w < W):
			continue
		if s[next_h][next_w] == '#':
			continue
		if dist[next_h][next_w] == -1:
			q.append([next_h, next_w])
			dist[next_h][next_w] = dist[now_h][now_w] + 1
if dist[-1][-1] == -1:
	print(-1)
	return
white = sum([i.count('.') for i in s])
ans = white - (dist[-1][-1] + 1)
print(ans)


from collections import deque
(h, w) = list(map(int, input().split()))
num = [list(input()) for _ in range(h)]
seen = [[False] * w for _ in range(h)]
queue = deque()
queue.append([0, 0])
ans = [[0] * w for _ in range(h)]
seen[0][0] = True
for i in range(h * w * 100):
	if len(queue) == 0:
		break
	cnt = queue.popleft()
	if num[max(0, cnt[0] - 1)][cnt[1]] == '.' and seen[max(0, cnt[0] - 1)][cnt[1]] == False:
		queue.append([cnt[0] - 1, cnt[1]])
		seen[max(0, cnt[0] - 1)][cnt[1]] = True
		ans[max(0, cnt[0] - 1)][cnt[1]] = ans[cnt[0]][cnt[1]] + 1
	if num[min(h - 1, cnt[0] + 1)][cnt[1]] == '.' and seen[min(h - 1, cnt[0] + 1)][cnt[1]] == False:
		queue.append([cnt[0] + 1, cnt[1]])
		seen[min(h - 1, cnt[0] + 1)][cnt[1]] = True
		ans[min(h - 1, cnt[0] + 1)][cnt[1]] = ans[cnt[0]][cnt[1]] + 1
	if num[cnt[0]][max(cnt[1] - 1, 0)] == '.' and seen[cnt[0]][max(cnt[1] - 1, 0)] == False:
		queue.append([cnt[0], cnt[1] - 1])
		seen[cnt[0]][max(cnt[1] - 1, 0)] = True
		ans[cnt[0]][max(cnt[1] - 1, 0)] = ans[cnt[0]][cnt[1]] + 1
	if num[cnt[0]][min(w - 1, cnt[1] + 1)] == '.' and seen[cnt[0]][min(w - 1, cnt[1] + 1)] == False:
		queue.append([cnt[0], cnt[1] + 1])
		seen[cnt[0]][min(w - 1, cnt[1] + 1)] = True
		ans[cnt[0]][min(w - 1, cnt[1] + 1)] = ans[cnt[0]][cnt[1]] + 1
if seen[-1][-1] == False:
	print(-1)
else:
	cnt3 = 0
	for i in range(h):
		cnt3 += num[i].count('.')
	print(cnt3 - ans[-1][-1] - 1)


from collections import deque
(H, W) = map(int, input().split())
stack = deque()
c = [input() for i in range(H)]
ans = 0
for ci in c:
	for j in ci:
		if j == '.':
			ans += 1
reached = [[0] * W for i in range(H)]
stack.append((0, 0))
dydx = [(1, 0), (-1, 0), (0, 1), (0, -1)]
while stack:
	(Y, X) = stack.popleft()
	for (dy, dx) in dydx:
		y = Y + dy
		x = X + dx
		if y < 0 or y >= H or x < 0 or (x >= W) or (c[y][x] == '#'):
			continue
		if reached[y][x] != 0:
			continue
		stack.append((y, x))
		reached[y][x] = reached[Y][X] + 1
if reached[H - 1][W - 1] == 0:
	print(-1)
else:
	print(ans - (reached[H - 1][W - 1] + 1))


import sys
from collections import deque
sys.setrecursionlimit(10000)
(a, b) = map(int, input().split())
List = []
sumup = 0
for i in range(a):
	l = list(input())
	p = l.count('.')
	sumup += p
	List.append(l)
List[0][0] = 1
q = deque([[0, 0]])
while q:
	(h, w) = q.popleft()
	aaa = [[0, 1], [0, -1], [1, 0], [-1, 0]]
	for (x, y) in aaa:
		if 0 <= h + x < a and 0 <= w + y < b:
			if List[h + x][w + y] == '.':
				List[h + x][w + y] = List[h][w] + 1
				q.append([h + x, w + y])
if List[a - 1][b - 1] == '.':
	print(-1)
else:
	print(sumup - List[a - 1][b - 1])


import sys
(H, W) = map(int, input().split())
num_w = -1
srch = []
for i in range(H):
	h = list(str(sys.stdin.readline().rstrip()))
	for j in range(W):
		if h[j] == '.':
			srch.append([i + 1, j + 1])
			num_w += 1
Cn = [[sys.maxsize for j in range(W + 2)] for i in range(H + 2)]
Cn[1][1] = 0
for _ in range(num_w):
	for (i, j) in srch[1:]:
		Cn[i][j] = min(Cn[i - 1][j], Cn[i][j - 1], Cn[i + 1][j], Cn[i][j + 1]) + 1
if Cn[H][W] < sys.maxsize:
	print(num_w - Cn[H][W])
else:
	print(-1)


from collections import deque
inf = 10 ** 10
(h, w) = map(int, input().split())
field = [input() for _ in range(h)]
length = [[inf for j in range(w)] for i in range(h)]
visited = [[0 for j in range(w)] for i in range(h)]
move = [[-1, 0], [1, 0], [0, -1], [0, 1]]
que = deque([])
que.append([0, 0])
length[0][0] = 1
visited[0][0] = 1
white = 0
for i in range(h):
	white += field[i].count('.')
while que:
	(y, x) = que.popleft()
	for (i, j) in move:
		(ny, nx) = (y + i, x + j)
		if ny < 0 or ny >= h or nx < 0 or (nx >= w):
			continue
		elif field[ny][nx] == '#':
			continue
		elif visited[ny][nx] == 1:
			continue
		visited[ny][nx] = 1
		que.append([ny, nx])
		length[ny][nx] = length[y][x] + 1
if length[h - 1][w - 1] == inf:
	print(-1)
else:
	print(white - length[h - 1][w - 1])


import sys
from collections import deque
readline = sys.stdin.readline
read = sys.stdin.read
(h, w) = map(int, readline().split())
wb = {'#': 0, '.': 1}
s = [wb[g] for g in read() if g != '\n']
dist = [0] * (h * w)
dist[0] = 1
stack = deque([(0, 0)])
while stack:
	cg = stack.popleft()
	for i in range(4):
		ng = (cg[0] + (1 - 2 * (i & 1)) * (i >> 1), cg[1] + (1 - 2 * (i & 1)) * (1 - (i >> 1)))
		fcg = w * cg[0] + cg[1]
		fng = w * ng[0] + ng[1]
		if 0 <= ng[0] <= h - 1 and 0 <= ng[1] <= w - 1 and s[fng] and (dist[fng] == 0):
			stack.append(ng)
			dist[fng] = dist[fcg] + 1
if dist[-1]:
	print(sum(s) - dist[-1])
else:
	print(-1)


from collections import deque
(H, W) = map(int, input().split())
white = 0
s = []
for y in range(H):
	line = input()
	white += line.count('.')
	s.append(list(line))
q = deque([(0, 0, 1)])
q_append = q.append
q_popleft = q.popleft
while q:
	(x, y, l) = q_popleft()
	if s[y][x] != '.':
		continue
	if x == W - 1 and y == H - 1:
		print(white - l)
		break
	s[y][x] = '*'
	for d in [(1, 0), (0, 1), (-1, 0), (0, -1)]:
		(nx, ny) = (x + d[0], y + d[1])
		if 0 <= nx < W and 0 <= ny < H:
			q_append((nx, ny, l + 1))
else:
	print(-1)


import queue
(H, W) = map(int, input().split())
c = ['#' * (W + 2)] + ['#' + input() + '#' for _ in range(H)] + ['#' * (W + 2)]
ans = 0
for i in range(H + 2):
	for g in range(W + 2):
		if c[i][g] == '.':
			ans += 1
dist = [[-1] * (W + 2) for _ in range(H + 2)]
que = queue.Queue()
que.put((1, 1))
dist[1][1] = 0
while not que.empty():
	(h, w) = que.get()
	direction = [(0, -1), (0, 1), (1, 0), (-1, 0)]
	for (y, x) in direction:
		if c[h + y][w + x] == '.' and dist[h + y][w + x] == -1:
			que.put((h + y, w + x))
			dist[h + y][w + x] = dist[h][w] + 1
if dist[H][W] == -1:
	print(-1)
else:
	print(ans - dist[H][W] - 1)


(h, w) = map(int, input().split())
A = []
for i in range(h):
	A.append(list(input()))
kabe = 0
for i in range(h):
	for j in range(w):
		if A[i][j] == '#':
			kabe += 1

def bfs():
	while queue:
		(x, y, d) = queue.pop()
		for i in range(4):
			xx = x + dx[i]
			yy = y + dy[i]
			if xx == h - 1 and yy == w - 1:
				print(h * w - d - 2 - kabe)
				exit()
			if 0 <= xx < h and 0 <= yy < w and (A[xx][yy] == '.'):
				A[xx][yy] = '#'
				queue.appendleft([xx, yy, d + 1])
from collections import deque
dx = [-1, 0, 1, 0]
dy = [0, 1, 0, -1]
queue = deque([[0, 0, 0]])
bfs()
print(-1)


(h, w) = map(int, input().split())
s = [input() for i in range(h)]
ex = [[0] * w for i in range(h)]
ex[0][0] = 1
do = [[0, 0]]
check = [[1, 0], [-1, 0], [0, 1], [0, -1]]
white = 0
for i in s:
	white += i.count('.')
while len(do) != 0:
	(x, y) = do.pop(0)
	for (i, j) in check:
		a = x + i
		b = y + j
		if -1 < a < h and -1 < b < w:
			if a == h - 1 and b == w - 1:
				print(white - ex[x][y] - 1)
				exit()
			elif ex[a][b] == 0 and s[a][b] == '.':
				ex[a][b] = ex[x][y] + 1
				do.append([a, b])
print(-1)


from collections import deque
(H, W) = map(int, input().split())
s = [list(input()) for i in range(H)]
q = deque([(0, 0, 1)])
while q:
	(h, w, c) = q.popleft()
	if s[h][w] != '.':
		continue
	s[h][w] = c
	if h + 1 == H and w + 1 == W:
		break
	if 0 <= h - 1:
		q.append((h - 1, w, c + 1))
	if h + 1 < H:
		q.append((h + 1, w, c + 1))
	if 0 <= w - 1:
		q.append((h, w - 1, c + 1))
	if w + 1 < W:
		q.append((h, w + 1, c + 1))
else:
	print(-1)
	exit()
print(H * W - sum([sum([x == '#' for x in sh]) for sh in s]) - s[-1][-1])


from collections import deque
(H, W) = map(int, input().split())
S = [input() for _ in range(H)]
c = [[-1 for _ in range(W)] for _ in range(H)]
d = [(1, 0), (-1, 0), (0, 1), (0, -1)]
q = deque()
q.append((0, 0))
c[0][0] = 1
while q:
	(x, y) = q.popleft()
	for (dx, dy) in d:
		nx = x + dx
		ny = y + dy
		if nx < 0 or nx >= W or ny < 0 or (ny >= H):
			continue
		if S[ny][nx] == '.' and c[ny][nx] is -1:
			c[ny][nx] = c[y][x] + 1
			q.append((nx, ny))
c_min = c[H - 1][W - 1]
if c_min == -1:
	ans = -1
else:
	ans = sum([s.count('.') for s in S]) - c_min
print(ans)


from collections import deque
(h, w) = map(int, input().split())
Map = [['#'] * (w + 2)]
Map += [['#'] + list(input()) + ['#'] for _ in range(h)]
Map += [['#'] * (w + 2)]
cnt = 0
for i in range(h + 2):
	for j in range(w + 2):
		if Map[i][j] == '.':
			cnt += 1
stack = deque([(1, 1)])
Map[1][1] = 1
moved = [[0, 1], [0, -1], [1, 0], [-1, 0]]
while stack:
	(x, y) = stack.popleft()
	for (s, t) in moved:
		if Map[x + s][y + t] == '.':
			stack.append((x + s, y + t))
			Map[x + s][y + t] = Map[x][y] + 1
goal = Map[-2][-2]
if goal == '.':
	print(-1)
else:
	print(cnt - goal)


from collections import deque
(h, w) = map(int, input().split())
maze = [['#' for i in range(w + 2)]] + [['#'] + [x == '#' for x in input()] + ['#'] for i in range(h)] + [['#' for i in range(w + 2)]]
f = 0
for i in range(1, h + 1):
	for j in range(1, w + 1):
		if maze[i][j]:
			f += 1
z = 0
pos = deque([(1, 1, 0)])
while pos:
	(x, y, c) = pos.popleft()
	if (x, y) == (h, w):
		print(h * w - f - c - 1)
		z = 1
		break
	elif maze[x][y]:
		continue
	pos.append((x - 1, y, c + 1))
	pos.append((x + 1, y, c + 1))
	pos.append((x, y - 1, c + 1))
	pos.append((x, y + 1, c + 1))
	maze[x][y] = True
if z == 0:
	print(-1)


import sys
from collections import deque
input = sys.stdin.readline
(H, W) = map(int, input().split())
(sy, sx) = (0, 0)
(gy, gx) = (H - 1, W - 1)
D = [list(input()) for i in range(H)]
Bs = 0
for i in range(H):
	Bs += D[i].count('#')
Q = deque()
Q.append((sy, sx))
dist = [[-1] * W for i in range(H)]
dist[sy][sx] = 0
dx = [1, 0, -1, 0]
dy = [0, -1, 0, 1]
while Q:
	(x, y) = Q.popleft()
	for i in range(4):
		nx = x + dx[i]
		ny = y + dy[i]
		if 0 <= nx <= W - 1 and 0 <= ny <= H - 1 and (D[ny][nx] != '#') and (dist[ny][nx] == -1):
			Q.append((nx, ny))
			dist[ny][nx] = dist[y][x] + 1
print(H * W - Bs - 1 - dist[gy][gx] if dist[gy][gx] != -1 else -1)


(h, w) = map(int, input().split())
a = ['*' * (w + 2)] + ['*' + input() + '*' for _ in range(h)] + ['*' * (w + 2)]
s = 0
for i in range(1, h + 1):
	s += a[i].count('.')
from collections import deque
d = deque()
d.append([1, 1])
c = [[10000] * w for _ in range(h)]
c[0][0] = 1
di = [[0, 1], [1, 0], [-1, 0], [0, -1]]
while d:
	g = d.popleft()
	for i in di:
		x = g[0] + i[0]
		y = g[1] + i[1]
		if a[x][y] == '.':
			if c[x - 1][y - 1] == 10000:
				d.append([x, y])
				c[x - 1][y - 1] = c[g[0] - 1][g[1] - 1] + 1
if c[h - 1][w - 1] == 10000:
	print(-1)
else:
	print(s - c[h - 1][w - 1])


from collections import deque
(h, w) = map(int, input().split())
s = [list(input()) for i in range(h)]
cnt = 0
for i in s:
	cnt += i.count('.')
(sy, sx) = (0, 0)
(gy, gx) = (h - 1, w - 1)
dist = [[-1] * w for i in range(h)]
dist[sy][sx] = 0
que = deque()
que.append((sy, sx))
while que:
	(y, x) = que.popleft()
	if y == gy and x == gx:
		print(cnt - (dist[y][x] + 1))
		exit()
	for (dy, dx) in [[1, 0], [-1, 0], [0, 1], [0, -1]]:
		ny = y + dy
		nx = x + dx
		if 0 <= ny <= h - 1 and 0 <= nx <= w - 1 and (s[ny][nx] == '.') and (dist[ny][nx] == -1):
			que.append((ny, nx))
			dist[ny][nx] = dist[y][x] + 1
print(-1)


xy = [(1, 0), (-1, 0), (0, 1), (0, -1)]
ans = chk = 0
(h, w) = map(int, input().split())
d = [[0] * w for i in range(h)]
l = []
for i in range(h):
	a = input()
	chk += a.count('#')
	l.append(a)
p = set([(0, 0)])
while len(p):
	(a, b) = p.pop()
	for (y, x) in xy:
		y += a
		x += b
		if 0 <= y < h and 0 <= x < w and (l[y][x] != '#'):
			if d[y][x] == 0 or d[y][x] > d[a][b] + 1:
				d[y][x] = d[a][b] + 1
				p.add((y, x))
print(-1 if d[h - 1][w - 1] == 0 else h * w - 1 - chk - d[h - 1][w - 1])


from collections import deque
(H, W) = map(int, input().split())
G = [input() for _ in range(H)]
num = 0
for i in range(H):
	for j in range(W):
		if G[i][j] == '.':
			num += 1
q = deque([(0, 0)])
done = [[-1] * W for _ in range(H)]
done[0][0] = 1
while q:
	(w, h) = q.popleft()
	for (dw, dh) in [[0, 1], [0, -1], [1, 0], [-1, 0]]:
		(nw, nh) = (w + dw, h + dh)
		if not (0 <= nw < W and 0 <= nh < H and (G[nh][nw] == '.') and (done[nh][nw] == -1)):
			continue
		done[nh][nw] = done[h][w] + 1
		q.append((nw, nh))
if done[H - 1][W - 1] != -1:
	print(num - done[H - 1][W - 1])
else:
	print(-1)


from collections import deque
(h, w) = map(int, input().split())
s = [input() for _ in range(h)]
d = [[1, 0], [-1, 0], [0, 1], [0, -1]]
bcnt = 0
for i in range(h):
	bcnt += s[i].count('#')
dist = [[-1] * w for _ in range(h)]
r = deque()
r.append([0, 0])
dist[0][0] = 0
while r:
	(x, y) = r.popleft()
	for (dx, dy) in d:
		nx = x + dx
		ny = y + dy
		nd = dist[y][x]
		if nx >= 0 and nx <= w - 1 and (ny >= 0) and (ny <= h - 1):
			if dist[ny][nx] > -1 or s[ny][nx] == '#':
				continue
			dist[ny][nx] = nd + 1
			r.append([nx, ny])
if dist[h - 1][w - 1] == -1:
	print(-1)
else:
	print(h * w - dist[h - 1][w - 1] - 1 - bcnt)


from collections import deque
(h, w) = map(int, input().split())
s = [input() for _ in range(h)]

def bfs():
	dist = {(0, 0): 0}
	que = deque([(0, 0)])
	while que:
		(i, j) = que.popleft()
		for (k, l) in ((0, 1), (1, 0), (0, -1), (-1, 0)):
			k += i
			l += j
			if 0 <= k < h and 0 <= l < w and (s[k][l] == '.') and ((k, l) not in dist):
				dist[k, l] = dist[i, j] + 1
				que.append((k, l))
	return dist
dist = bfs()
if (h - 1, w - 1) in dist:
	black = sum((line.count('#') for line in s))
	print(h * w - black - (dist[h - 1, w - 1] + 1))
else:
	print(-1)


from collections import deque, defaultdict
(H, W) = map(int, input().split())
s = [['#'] * (W + 2)] + [list('#' + input() + '#') for _ in range(H)] + [['#'] * (W + 2)]
Q = deque([(1, 1, 1)])
cnt = 0
for S in s[1:-1]:
	cnt += S.count('.')
while Q:
	(x, y, d) = Q.popleft()
	s[x][y] = '#'
	if x == H and y == W:
		route = d
		break
	for (dx, dy) in [(1, 0), (-1, 0), (0, 1), (0, -1)]:
		if s[x + dx][y + dy] == '.':
			Q.append((x + dx, y + dy, d + 1))
			s[x + dx][y + dy] = '#'
else:
	print(-1)
	exit()
print(cnt - route)


dx = (0, 1, 0, -1)
dy = (1, 0, -1, 0)
(H, W) = list(map(int, input().split()))
S = [input() for i in range(H)]
S_check = [[False] * W for _ in range(H)]
start = (0, 0, 1)
goal = (H - 1, W - 1)
Q = []
Q.append(start)
step = 0
is_reached = False
while Q:
	current = Q.pop(0)
	step = current[2]
	for i in range(4):
		next_pos = (current[0] + dx[i], current[1] + dy[i])
		if next_pos[0] < 0 or next_pos[0] > H - 1 or next_pos[1] < 0 or (next_pos[1] > W - 1):
			continue
		elif S_check[next_pos[0]][next_pos[1]]:
			continue
		elif next_pos == goal:
			is_reached = True
			break
		elif S[next_pos[0]][next_pos[1]] == '#':
			continue
		else:
			S_check[next_pos[0]][next_pos[1]] = True
			Q.append((next_pos[0], next_pos[1], step + 1))
	if is_reached:
		break
cnt = 0
for i in range(H):
	for j in range(W):
		if S[i][j] == '#':
			cnt += 1
ans = -1
if is_reached:
	ans = H * W - step - 1 - cnt
print(ans)


(a, b) = map(int, input().split())
G = []
white_num = 0
for i in range(a):
	s = list(input())
	white_num += s.count('.')
	G.append(s)
from collections import deque

def mazesearch(G, initial_h, initial_w, target_h, target_w):
	steps = 0
	(BLOCKED, ALLOWED) = ('#', '.')
	(UNVISITED, VISITED) = (0, 1)
	directions = [(0, -1), (0, 1), (-1, 0), (1, 0)]
	if G[initial_h][initial_w] == BLOCKED:
		return -1
	(height, width) = (len(G), len(G[0]))
	is_visited = [[UNVISITED for w in range(width)] for h in range(height)]
	is_visited[initial_h][initial_w] = VISITED
	queue = deque([(initial_h, initial_w, steps)])
	while queue:
		(h, w, steps) = queue.popleft()
		if h == target_h and w == target_w:
			return steps
		for (dh, dw) in directions:
			new_h = h + dh
			new_w = w + dw
			if not (0 <= new_h < height and 0 <= new_w < width):
				continue
			if G[new_h][new_w] == ALLOWED and is_visited[new_h][new_w] == UNVISITED:
				queue.append((new_h, new_w, steps + 1))
				is_visited[new_h][new_w] = VISITED
	return -1
steps = mazesearch(G, 0, 0, a - 1, b - 1)
if steps == -1:
	print(-1, flush=True)
else:
	print(white_num - steps - 1, flush=True)


from collections import deque
(H, W) = map(int, input().split())
S = [['#'] * (W + 2) for _ in range(H + 2)]
c = 0
for i in range(1, H + 1):
	s = list(input())
	S[i] = ['#'] + s + ['#']
	c += s.count('.')
step = [(1, 0), (-1, 0), (0, 1), (0, -1)]
que = deque([(1, 1)])
S[1][1] = 1
while que:
	(h, w) = que.popleft()
	if (h, w) == (H, W):
		break
	for (dh, dw) in step:
		nh = h + dh
		nw = w + dw
		if S[nh][nw] != '.':
			continue
		que.append((nh, nw))
		S[nh][nw] = S[h][w] + 1
print(-1 if S[H][W] == '.' else c - S[H][W])


from collections import deque
(H, W) = map(int, input().split())
mp = ['#' * (W + 1)]
memo = [[-1] * (W + 1) for _ in range(H + 1)]
cnt = 0
for _ in range(H):
	s = '#' + input()
	cnt += s.count('.')
	mp.append(s)
ds = [[1, 0], [-1, 0], [0, 1], [0, -1]]
h = deque([[1, 1, 1]])
while h:
	l = h.popleft()
	for d in ds:
		if l[0] + d[0] <= W and l[1] + d[1] <= H:
			if mp[l[1] + d[1]][l[0] + d[0]] == '.' and memo[l[1] + d[1]][l[0] + d[0]] == -1:
				memo[l[1] + d[1]][l[0] + d[0]] = l[2] + 1
				h.append([l[0] + d[0], l[1] + d[1], l[2] + 1])
	if memo[H][W] > -1:
		print(cnt - memo[H][W])
		exit()
print(memo[H][W])


from collections import deque
(h, w) = map(int, input().split())
s = [list('#' + input() + '#') for i in range(h)]
s = [['#'] * (w + 2)] + s + [['#'] * (w + 2)]
z = 0
for i in s:
	z += i.count('.')
ans = [[-1] * (w + 2) for i in range(h + 2)]
m = [[0, 1], [0, -1], [1, 0], [-1, 0]]
ans[1][1] = 1
d = deque([[1, 1]])
while len(d):
	(x, y) = d.popleft()
	for (i, j) in m:
		(a, b) = (x + i, y + j)
		if s[a][b] == '.' and ans[a][b] == -1:
			d.append([a, b])
			ans[a][b] = ans[x][y] + 1
if ans[h][w] == -1:
	print(-1)
else:
	print(z - ans[h][w])


(H, W) = map(int, input().split())
que = [(0, 0)]
S = [input() for i in range(H)]
flag = [[1 << 30 for i in range(W)] for j in range(H)]
flag[0][0] = 1
cnt = sum((row.count('.') for row in S))
while que:
	(y, x) = que.pop(0)
	for (ny, nx) in ([1, 0], [-1, 0], [0, 1], [0, -1]):
		nx += x
		ny += y
		if ny >= 0 and nx >= 0 and (ny < H) and (nx < W) and (S[ny][nx] != '#') and (flag[ny][nx] > flag[y][x] + 1):
			que.append((ny, nx))
			flag[ny][nx] = flag[y][x] + 1
			if (ny, nx) == (H - 1, W - 1):
				print(cnt - flag[ny][nx])
				exit()
print(-1)


from collections import deque
(h, w) = map(int, input().split())
s = [list(input()) for i in range(h)]
ans = sum([i.count('#') for i in s])
s = [['#'] * (w + 2)] + [['#'] + i + ['#'] for i in s] + [['#'] * (w + 2)]
d = deque([[1, 1, 1]])
while len(d) > 0:
	(x, y, cnt) = d.popleft()
	if x == h and y == w:
		print(h * w - cnt - ans)
		return
	s[x][y] = '#'
	if s[x - 1][y] == '.':
		d.append([x - 1, y, cnt + 1])
		s[x - 1][y] = '#'
	if s[x + 1][y] == '.':
		d.append([x + 1, y, cnt + 1])
		s[x + 1][y] = '#'
	if s[x][y - 1] == '.':
		d.append([x, y - 1, cnt + 1])
		s[x][y - 1] = '#'
	if s[x][y + 1] == '.':
		d.append([x, y + 1, cnt + 1])
		s[x][y + 1] = '#'
print(-1)


(H, W) = map(int, input().split())
S = [list(input()) for _ in range(H)]
from collections import deque

def bfs(h, w, sy, sx, gy, gx, S):
	maze = [[10 ** 9] * W for _ in range(H)]
	maze[sy - 1][sx - 1] = 0
	que = deque([[sy - 1, sx - 1]])
	while que:
		(y, x) = que.popleft()
		for (i, j) in [(1, 0), (0, 1), (-1, 0), (0, -1)]:
			(nexty, nextx) = (y + i, x + j)
			if 0 <= nexty < h and 0 <= nextx < w:
				dist1 = S[nexty][nextx]
				dist2 = maze[nexty][nextx]
			else:
				continue
			if dist1 != '#':
				if dist2 > maze[y][x] + 1:
					maze[nexty][nextx] = maze[y][x] + 1
					que.append([nexty, nextx])
	return maze[gy - 1][gx - 1] + 1
A = 0
for s in S:
	A += s.count('.')
B = bfs(H, W, 1, 1, H, W, S)
if B > 10 ** 9:
	ans = -1
else:
	ans = A - B
print(ans)


from collections import deque
(H, W) = map(int, input().split())
M = []
M = ['#' * (W + 2)]
num_blk = 0
for h in range(H):
	inp = input()
	M.append('#' + inp + '#')
	num_blk += inp.count('#')
M.append('#' * (W + 2))
(sy, sx) = (1, 1)
(gy, gx) = (H, W)
T = [[float('inf')] * (W + 2) for _ in range(H + 2)]
T[sy][sx] = 0
que = deque([(sy, sx)])
while len(que) > 0:
	(y, x) = que.popleft()
	for (a, b) in [(0, 1), (0, -1), (1, 0), (-1, 0)]:
		if M[y + b][x + a] != '#' and T[y + b][x + a] == float('inf'):
			T[y + b][x + a] = T[y][x] + 1
			que.append((y + b, x + a))
	if y == gy and x == gx:
		break
if T[gy][gx] == float('inf'):
	print(-1)
else:
	print(H * W - num_blk - T[gy][gx] - 1)


from collections import deque
import copy
(H, W) = map(int, input().split())
s = [list(input()) for i in range(H)]
ss = copy.deepcopy(s)
q = deque([[0, 0]])
ss[0][0] = 0
move = [[1, 0], [0, 1], [0, -1], [-1, 0]]
num = 0
t = False
while q:
	num += 1
	for i in range(len(q)):
		b = q.popleft()
		if b == [H - 1, W - 1]:
			t = True
			num -= 1
			break
		for m in move:
			if 0 <= b[0] + m[0] <= H - 1 and 0 <= b[1] + m[1] <= W - 1 and (ss[b[0] + m[0]][b[1] + m[1]] == '.'):
				ss[b[0] + m[0]][b[1] + m[1]] = num
				q.append([b[0] + m[0], b[1] + m[1]])
	else:
		continue
	break
if not t:
	print('-1')
else:
	x = num
	b = (H - 1, W - 1)
	ss[b[0]][b[1]] = '#'
	while x != 0:
		for m in move:
			if 0 <= b[0] + m[0] <= H - 1 and 0 <= b[1] + m[1] <= W - 1 and (ss[b[0] + m[0]][b[1] + m[1]] == x - 1):
				x = x - 1
				ss[b[0] + m[0]][b[1] + m[1]] = '#'
				b = (b[0] + m[0], b[1] + m[1])
				break
	ans = 0
	for h in range(H):
		for w in range(W):
			if ss[h][w] != '#':
				ans += 1
	print(ans)


(H, W) = map(int, input().split())
s = [['#'] * (W + 2)] + [['#'] + [c for c in input()] + ['#'] for _ in [0] * H] + [['#'] * (W + 2)]
ans = sum([sum([int(c == '.') for c in row]) for row in s])
s[1][1] = 1
ij = [[1, 1]]
d = [[0, 1], [0, -1], [1, 0], [-1, 0]]
cnt = 0
while ij[cnt:]:
	(i, j) = ij[cnt]
	for (di, dj) in d:
		if s[i + di][j + dj] == '.':
			s[i + di][j + dj] = s[i][j] + 1
			ij.append([i + di, j + dj])
			if i + di == H and j + dj == W:
				break
	cnt += 1
if s[H][W] == '.':
	ans = -1
else:
	ans -= s[H][W]
print(ans)


(h, w) = map(int, input().split())
grid = [['#'] * (w + 2)] + [list('#' + input() + '#') for x in range(h)] + [['#'] * (w + 2)]
(sx, sy) = (1, 1)
(gx, gy) = (w, h)
loc = [[sy, sx]]
ans = sum((i.count('.') for i in grid))
for c in range(h * w):
	next_loc = []
	for (y, x) in loc:
		for (i, j) in ([0, 1], [1, 0], [0, -1], [-1, 0]):
			if grid[y + i][x + j] == '.':
				grid[y][x] = c + 1
				grid[y + i][x + j] = c + 2
				next_loc.append([y + i, x + j])
	loc = next_loc
	if [gy, gx] in loc:
		ans -= grid[gy][gx]
		print(ans)
		exit()
print(-1)


def cal():
	import queue
	(h, w) = list(map(int, input().split()))
	s = [list(input()) for _ in range(h)]
	cost = [[-1] * w for _ in range(h)]
	INF = float('inf')
	(count, ans) = (0, INF)
	for i in range(h):
		for j in range(w):
			if s[i][j] != '#':
				cost[i][j] = INF
			else:
				count += 1
	q = queue.Queue()
	q.put((0, 0, 1))
	while not q.empty():
		(c0, c1, c2) = q.get()
		s[c0][c1] = '#'
		if c0 == h - 1 and c1 == w - 1:
			return h * w - count - c2
		for (i, j) in ((1, 0), (-1, 0), (0, 1), (0, -1)):
			(x, y) = (c0 + i, c1 + j)
			if 0 <= x < h and 0 <= y < w:
				if s[x][y] != '#' and cost[x][y] == INF:
					cost[x][y] = c2 + 1
					q.put((x, y, c2 + 1))
	return ans
ans = cal()
if ans == float('inf'):
	print(-1)
else:
	print(ans)


from collections import deque
(h, w) = [int(i) - 1 for i in input().split()]
ans = 0
maze = []
for i in range(h + 1):
	s = list(input())
	maze.append(s)
	ans += s.count('.')
pos = deque([[0, 0, 0]])
while pos:
	(y, x, b) = pos.popleft()
	if y == h and x == w:
		print(ans - b - 1)
		exit()
	for (ny, nx) in [[1, 0], [-1, 0], [0, 1], [0, -1]]:
		if 0 <= y + ny <= h and 0 <= x + nx <= w and (maze[y + ny][x + nx] == '.'):
			pos.append([y + ny, x + nx, b + 1])
			maze[y + ny][x + nx] = '#'
print(-1)


from collections import deque
(h, w) = map(int, input().split())
m = [['#'] * (w + 2)] + [['#'] + list(input()) + ['#'] for _ in range(h)] + [['#'] * (w + 2)]
d = [(1, 0), (0, 1), (-1, 0), (0, -1)]
q = deque([(1, 1, 1)])
m[1][1] = '@'
ans = -1
while q:
	(x, y, c) = q.popleft()
	if x == h and y == w:
		ans = c
		break
	for (dx, dy) in d:
		(nx, ny) = (x + dx, y + dy)
		if m[nx][ny] == '.':
			q.append((nx, ny, c + 1))
			m[nx][ny] = '@'
if ans != -1:
	for i in range(1, h + 1):
		for j in range(1, w + 1):
			if m[i][j] == '#':
				ans += 1
	ans = h * w - ans
print(ans)


from collections import deque
(H, W) = map(int, input().split())
maze = []
white = 0
for i in range(H):
	s = input()
	c = s.count('.')
	white += c
	maze.append(s)
path = [[None] * W for _ in range(H)]
path[0][0] = 1
q = deque([[0, 0]])
while q:
	(h, w) = q.popleft()
	for (nh, nw) in ([h + 1, w], [h - 1, w], [h, w + 1], [h, w - 1]):
		if nh < 0 or nh > H - 1 or nw < 0 or (nw > W - 1):
			continue
		if maze[nh][nw] == '#' or path[nh][nw] != None:
			continue
		q.append([nh, nw])
		path[nh][nw] = path[h][w] + 1
		if nh == H - 1 and nw == W - 1:
			print(white - path[nh][nw])
			exit()
print(-1)


(H, W) = map(int, input().split())
S = tuple((input().rstrip() for _ in range(H)))
a = 0
d = [(1, 0), (-1, 0), (0, 1), (0, -1)]
lity = [[0 for i in range(W)] for j in range(H)]
lity[0][0] = 1

def roop() -> None:
	p = [(0, 0)]
	while p:
		(x, y) = p.pop(0)
		for (dx, dy) in d:
			if 0 <= x + dx < H and 0 <= y + dy < W and (S[x + dx][y + dy] == '.') and (lity[x + dx][y + dy] == 0):
				p.append((x + dx, y + dy))
				lity[x + dx][y + dy] = lity[x][y] + 1
roop()
white = sum((t.count('.') for t in S))
x = lity[-1][-1]
ans = white - x if x else -1
print(ans)


from collections import deque
(h, w) = map(int, input().split())
s = [list(input()) for i in range(h)]
cntW = 0
for i in range(h):
	for j in range(w):
		if s[i][j] == '.':
			cntW += 1
dist = [[-1] * w for i in range(h)]
dist[0][0] = 0
q = [(0, 0)]
q = deque(q)
dx = [1, 0, -1, 0]
dy = [0, 1, 0, -1]
while q:
	(y, x) = q.pop()
	for i in range(4):
		(ny, nx) = (y + dy[i], x + dx[i])
		if 0 <= ny < h and 0 <= nx < w and (dist[ny][nx] == -1) and (s[ny][nx] == '.'):
			dist[ny][nx] = dist[y][x] + 1
			q.appendleft((ny, nx))
if dist[-1][-1] == -1:
	print(-1)
else:
	print(cntW - dist[-1][-1] - 1)


from collections import deque
(H, W) = list(map(int, input().split()))
grid = [list(input()) for _ in range(H)]
visited = [[-1] * W for _ in range(H)]
moves = [(1, 0), (0, 1), (-1, 0), (0, -1)]
q = deque()
q.append((0, 0))
visited[0][0] = 0
while q:
	(y, x) = q.popleft()
	for (dy, dx) in moves:
		moved_y = y + dy
		moved_x = x + dx
		if moved_y < 0 or H - 1 < moved_y or moved_x < 0 or (W - 1 < moved_x):
			continue
		if grid[moved_y][moved_x] == '#':
			continue
		if visited[moved_y][moved_x] != -1:
			continue
		visited[moved_y][moved_x] = visited[y][x] + 1
		q.append((moved_y, moved_x))
min_route = visited[H - 1][W - 1]
if min_route == -1:
	answer = -1
else:
	total_white = 0
	for row in grid:
		total_white += row.count('.')
	answer = total_white - min_route - 1
print(answer)


(H, W) = map(int, input().split())
S = []
for _ in range(H):
	a = input()
	S.append(a)
count = 0
for i in range(H):
	for j in range(W):
		if S[i][j] == '.':
			count += 1
from collections import deque
seen = [[False] * W for _ in range(H)]
seen[0][0] = True
dq = deque([(0, 0, 1)])
d = [(1, 0), (0, 1), (0, -1), (-1, 0)]
while dq:
	(x, y, cnt) = dq.popleft()
	if x == H - 1 and y == W - 1:
		print(count - cnt)
		exit()
	for (dx, dy) in d:
		if 0 <= x + dx < H and 0 <= y + dy < W and (seen[x + dx][y + dy] == False) and (S[x + dx][y + dy] == '.'):
			seen[x + dx][y + dy] = True
			dq.append((x + dx, y + dy, cnt + 1))
print(-1)


from collections import deque

def bfs():
	d = [[float('inf')] * w for i in range(h)]
	dx = [1, 0, -1, 0]
	dy = [0, 1, 0, -1]
	que = deque([])
	que.append((sx, sy))
	d[sx][sy] = 0
	while que:
		p = que.popleft()
		if p[0] == gy and p[1] == gx:
			break
		for i in range(4):
			nx = p[0] + dx[i]
			ny = p[1] + dy[i]
			if 0 <= nx < h and 0 <= ny < w and (maze[nx][ny] != '#') and (d[nx][ny] == float('inf')):
				que.append((nx, ny))
				d[nx][ny] = d[p[0]][p[1]] + 1
	return d[gx][gy]
(h, w) = list(map(int, input().split()))
maze = [list(input()) for i in range(h)]
(sx, sy) = (0, 0)
(gx, gy) = (h - 1, w - 1)
white = 0
for i in range(h):
	for j in range(w):
		if maze[i][j] == '.':
			white += 1
res = bfs()
if 0 < res < float('inf'):
	print(white - res - 1)
else:
	print(-1)


from collections import deque
(h, w) = map(int, input().split())
maze = []
visited = [[0] * w for _ in range(h)]
mx = 0
for _ in range(h):
	s = input()
	mx += s.count('.')
	maze.append(list(s))
(sy, sx) = (0, 0)
(gy, gx) = (h - 1, w - 1)
que = deque([(sy, sx, 1)])
while que:
	(y, x, c) = que.popleft()
	if visited[y][x] != 0:
		continue
	visited[y][x] = c
	for (dy, dx) in zip((1, -1, 0, 0), (0, 0, 1, -1)):
		(ny, nx) = (y + dy, x + dx)
		if 0 <= ny < h and 0 <= nx < w:
			if maze[ny][nx] == '.':
				que.append((ny, nx, c + 1))
print(mx - visited[gy][gx] if visited[gy][gx] != 0 else -1)


(h, w) = [int(s) for s in input().split(' ')]
s = []
for i in range(h):
	s.append([s == '.' for s in input()])
inf = 10000
dx = [1, 0, -1, 0]
dy = [0, 1, 0, -1]
queue = [(0, 0)]
p = []
for i in range(h):
	p.append([inf] * w)
p[0][0] = 1
while len(queue) > 0:
	(x, y) = queue.pop()
	for i in range(4):
		xx = x + dx[i]
		yy = y + dy[i]
		if 0 <= xx and xx < w and (0 <= yy) and (yy < h) and s[yy][xx] and (p[yy][xx] > p[y][x] + 1):
			p[yy][xx] = p[y][x] + 1
			queue.insert(0, (xx, yy))
if p[h - 1][w - 1] == inf:
	print('-1')
else:
	print(sum((sum(x) for x in s)) - p[h - 1][w - 1])


(h, w) = map(int, input().split())
s = [[0 if c == '#' else 1 for c in input()] for _ in range(h)]
directions = [(0, -1), (-1, 0), (0, 1), (1, 0)]
dist = [[-1 for _ in range(w)] for _ in range(h)]
dist[0][0] = 0
q = [(0, 0)]
for (y, x) in q:
	for (dy, dx) in directions:
		(ny, nx) = (y + dy, x + dx)
		if (ny < 0 or h <= ny) or (nx < 0 or w <= nx):
			continue
		if not s[ny][nx]:
			continue
		if dist[ny][nx] >= 0:
			continue
		dist[ny][nx] = dist[y][x] + 1
		q.append((ny, nx))
if dist[-1][-1] < 0:
	print(-1)
else:
	print(sum((sum(si) for si in s)) - dist[-1][-1] - 1)


from collections import deque
(h, w) = map(int, input().split())
maplis = [input() for i in range(h)]
que = deque([(0, 0, 1)])
used = {(0, 0)}
bcount = sum((s.count('#') for s in maplis))

def check(x, y, c):
	if x < 0 or x > w - 1 or y < 0 or (y > h - 1):
		return
	if maplis[y][x] == '#':
		return
	if (x, y) in used:
		return
	que.append((x, y, c + 1))
	used.add((x, y))
f = -1
while que:
	(x, y, c) = que.popleft()
	if x == w - 1 and y == h - 1:
		f = c
		break
	check(x - 1, y, c)
	check(x + 1, y, c)
	check(x, y - 1, c)
	check(x, y + 1, c)
print(f if f == -1 else h * w - f - bcount)


from collections import deque
INF = 10 ** 18
(h, w) = map(int, input().split())
e = [input() for _ in range(h)]
cnt = 0
for i in range(h):
	for j in range(w):
		if e[i][j] == '.':
			cnt += 1
dx = [-1, 0, 1, 0]
dy = [0, -1, 0, 1]
(sx, sy) = (0, 0)
(gx, gy) = (h - 1, w - 1)
q = deque([(sx, sy)])
d = [[INF] * w for _ in range(h)]
d[sx][sy] = 1
while q:
	(x, y) = q.popleft()
	for i in range(4):
		nx = x + dx[i]
		ny = y + dy[i]
		if 0 <= nx < h and 0 <= ny < w and (e[nx][ny] == '.') and (d[nx][ny] == INF):
			q.append((nx, ny))
			d[nx][ny] = d[x][y] + 1
if d[gx][gy] == INF:
	print(-1)
else:
	print(cnt - d[gx][gy])


from collections import deque
(H, W) = map(int, input().split())
s = [input() for _ in range(H)]
q = deque([[0, 0]])
f = [[-1 for j in range(W)] for i in range(H)]
f[0][0] = 0
dxy = [[1, 0], [-1, 0], [0, 1], [0, -1]]
while q:
	(x, y) = q.popleft()
	for (dx, dy) in dxy:
		dx += x
		dy += y
		if dx >= 0 and dy >= 0 and (dx < H) and (dy < W):
			if s[dx][dy] == '.' and f[dx][dy] == -1:
				f[dx][dy] = f[x][y] + 1
				q.append([dx, dy])
res = 0
for i in range(H):
	res += s[i].count('.')
if f[H - 1][W - 1] == -1:
	print(-1)
else:
	print(res - f[H - 1][W - 1] - 1)


(H, W) = list(map(int, input().split()))
sq = [list(input()) for i in range(H)]
ans = False
c = H * W
pos = [[0, 0, 0]]
while pos != []:
	(y, x, depth) = pos.pop(0)
	if x == W - 1 and y == H - 1:
		ans = True
		break
	if 0 <= x + 1 <= W - 1:
		if sq[y][x + 1] == '.':
			pos.append([y, x + 1, depth + 1])
			sq[y][x + 1] = '!'
	if 0 <= x - 1 <= W - 1:
		if sq[y][x - 1] == '.':
			pos.append([y, x - 1, depth + 1])
			sq[y][x - 1] = '!'
	if 0 <= y + 1 <= H - 1:
		if sq[y + 1][x] == '.':
			pos.append([y + 1, x, depth + 1])
			sq[y + 1][x] = '!'
	if 0 <= y - 1 <= H - 1:
		if sq[y - 1][x] == '.':
			pos.append([y - 1, x, depth + 1])
			sq[y - 1][x] = '!'
for j in range(H):
	for k in range(W):
		if sq[j][k] == '#':
			c -= 1
if ans == True:
	print(c - depth - 1)
else:
	print(-1)


from collections import deque
(h, w) = map(int, input().split())
s = [list(input()) for _ in range(h)]
dots = sum([v.count('.') for v in s])
visited = [[-1] * w for _ in range(h)]
q = deque([[0, 0]])
visited[0][0] = 1
while q:
	(y, x) = q.popleft()
	if y == h - 1 and x == w - 1:
		break
	for (i, j) in [(1, 0), (0, 1), (-1, 0), (0, -1)]:
		(ny, nx) = (y + i, x + j)
		if not 0 <= ny < h or not 0 <= nx < w or s[ny][nx] == '#':
			continue
		elif visited[ny][nx] == -1:
			visited[ny][nx] = visited[y][x] + 1
			q.append([ny, nx])
if visited[h - 1][w - 1] != -1:
	print(dots - visited[h - 1][w - 1])
else:
	print(-1)


from collections import deque
(H, W) = map(int, input().split())
m = [list(input()) for _ in range(H)]
numdot = sum([line.count('.') for line in m])
q = deque([[0, 0, 1]])
m[0][0] = '#'
goal = False
while q:
	(i, j, score) = q.popleft()
	if i == H - 1 and j == W - 1:
		goal = True
		break
	for (movei, movej) in [[1, 0], [-1, 0], [0, 1], [0, -1]]:
		ni = i + movei
		nj = j + movej
		if ni < 0 or H <= ni or nj < 0 or (W <= nj) or (m[ni][nj] == '#'):
			continue
		m[ni][nj] = '#'
		q.append([ni, nj, score + 1])
if goal:
	print(numdot - score)
else:
	print(-1)


from collections import deque
(h, w) = map(int, input().split())
s = []
for _ in range(h):
	s.append(input())
q = deque([(0, 0)])
INF = 10 ** 5
dist = [[INF] * w for _ in range(h)]
dist[0][0] = 0
dxdy = [(-1, 0), (0, -1), (0, 1), (1, 0)]
while q:
	(x, y) = q.popleft()
	for (dx, dy) in dxdy:
		if not (0 <= x + dx < w and 0 <= y + dy < h):
			continue
		if s[y + dy][x + dx] == '#' or dist[y + dy][x + dx] < INF:
			continue
		dist[y + dy][x + dx] = dist[y][x] + 1
		q.append((x + dx, y + dy))
if dist[h - 1][w - 1] == INF:
	print(-1)
else:
	white = 0
	for r in s:
		white += r.count('.')
	print(white - dist[h - 1][w - 1] - 1)


from collections import deque
(h, w) = map(int, input().split())
c = []
for _ in range(h):
	c.append(input())
ans = 0
for i in range(h):
	for j in range(w):
		if c[i][j] == '.':
			ans += 1
d = [[-1] * w for _ in range(h)]
d[0][0] = 1
que = deque([[0, 0]])
while que:
	(x, y) = que.popleft()
	for (i, j) in [[1, 0], [0, 1], [-1, 0], [0, -1]]:
		(nx, ny) = (x + i, y + j)
		if 0 <= nx < w and 0 <= ny < h and (c[ny][nx] == '.') and (d[ny][nx] == -1):
			d[ny][nx] = d[y][x] + 1
			que.append([nx, ny])
if d[h - 1][w - 1] == -1:
	print(-1)
else:
	print(ans - d[h - 1][w - 1])


import sys
sys.setrecursionlimit(10 ** 7)
from collections import deque
(H, W) = list(map(int, input().split()))
dots = H * W
field = []
for _ in range(H):
	tmp = input()
	dots -= tmp.count('#')
	field.append(tmp)
DX = [1, 0, -1, 0]
DY = [0, 1, 0, -1]
dist = [[-1] * W for _ in range(H)]
dist[0][0] = 0
que = deque()
que.append([0, 0])
while que:
	(y, x) = que.popleft()
	for (dx, dy) in zip(DX, DY):
		nx = x + dx
		ny = y + dy
		if nx < 0 or nx >= W or ny < 0 or (ny >= H):
			continue
		if field[ny][nx] == '#':
			continue
		if dist[ny][nx] == -1:
			dist[ny][nx] = dist[y][x] + 1
			que.append([ny, nx])
score = -1
goal = dist[H - 1][W - 1]
if goal != -1:
	score = dots - goal - 1
print(score)


from collections import deque
(H, W) = map(int, input().split())
S = [input() for _ in range(H)]
s = 0
for c in S:
	s += c.count('.')
que = deque()
dist = [[-1 for j in range(W)] for i in range(H)]
dist[0][0] = 0
st = (0, 0)
que.append(st)
dydx = [(1, 0), (0, 1), (-1, 0), (0, -1)]
while que:
	(p, q) = que.popleft()
	for (dy, dx) in dydx:
		if 0 <= p + dy and p + dy < H and (0 <= q + dx) and (q + dx < W):
			if dist[p + dy][q + dx] != -1 or S[p + dy][q + dx] != '.':
				continue
			dist[p + dy][q + dx] = dist[p][q] + 1
			que.append((p + dy, q + dx))
if dist[H - 1][W - 1] == -1:
	print(-1)
else:
	print(s - dist[H - 1][W - 1] - 1)


from collections import deque
(H, W) = list(map(int, input().split()))
C = list((list(input()) for _ in range(H)))

def bfs():
	(sx, sy) = (0, 0)
	(gx, gy) = (H - 1, W - 1)
	dx = [1, 0, -1, 0]
	dy = [0, 1, 0, -1]
	work_queue = deque([])
	work_queue.append((sx, sy))
	visited = [[float('inf')] * W for _ in range(H)]
	visited[sx][sy] = 1
	while work_queue:
		(x, y) = work_queue.popleft()
		for i in range(4):
			(nx, ny) = (x + dx[i], y + dy[i])
			if 0 <= nx < H and 0 <= ny < W and (visited[nx][ny] == float('inf')) and (C[nx][ny] != '#'):
				work_queue.append((nx, ny))
				visited[nx][ny] = visited[x][y] + 1
	return visited[gx][gy]
temp = bfs()
black = 0
white = 0
for i in range(H):
	for j in range(W):
		if C[i][j] == '.':
			white += 1
		else:
			black += 1
if temp == float('inf'):
	print(-1)
else:
	print(white - temp)


from collections import deque
(H, W) = map(int, input().split())
S = [input() for _ in range(H)]
Q = deque([[0, 0]])
dist = [[-1] * W for _ in range(H)]
dist[0][0] = 0
while Q:
	(h, w) = Q.popleft()
	for (nh, nw) in [[h + 1, w], [h - 1, w], [h, w - 1], [h, w + 1]]:
		if 0 <= nh < H and 0 <= nw < W and (S[nh][nw] == '.') and (dist[nh][nw] == -1):
			dist[nh][nw] = dist[h][w] + 1
			Q.append([nh, nw])
if dist[H - 1][W - 1] == -1:
	print(-1)
else:
	ans = 0
	for s in S:
		ans += s.count('.')
	print(ans - dist[H - 1][W - 1] - 1)


from collections import deque
(H, W) = list(map(int, input().split()))
route = []
n_black = 0
for _ in range(H):
	tmp_ls = input()
	n_black += tmp_ls.count('#')
	route.append(tmp_ls)
visited = [[False] * W for _ in range(H)]
dist = [[-1] * W for _ in range(H)]
dist[0][0] = 0
tmp = [0, 0]
goal = [H - 1, W - 1]
kouho = deque()

def rinsetsu(ls):
	(x, y) = (ls[0], ls[1])
	ans = []
	if x - 1 >= 0:
		ans.append([x - 1, y])
	if x + 1 <= H - 1:
		ans.append([x + 1, y])
	if y - 1 >= 0:
		ans.append([x, y - 1])
	if y + 1 <= W - 1:
		ans.append([x, y + 1])
	return ans
for ls in rinsetsu([0, 0]):
	if route[ls[0]][ls[1]] == '.':
		kouho.append([ls[0], ls[1], 0, 0])

def bfs():
	while True:
		while True:
			if len(kouho) == 0:
				return
			tmp = kouho.popleft()
			if not visited[tmp[0]][tmp[1]]:
				break
		(x, y) = (tmp[0], tmp[1])
		visited[x][y] = True
		dist[x][y] = dist[tmp[2]][tmp[3]] + 1
		if [x, y] == goal:
			return
		for ls in rinsetsu([x, y]):
			if not visited[ls[0]][ls[1]] and route[ls[0]][ls[1]] == '.':
				kouho.append(ls + [x, y])
bfs()
if dist[H - 1][W - 1] == -1:
	print(-1)
else:
	white = dist[H - 1][W - 1] + 1
	print(H * W - white - n_black)


import sys
from collections import deque

def main():

	def input():
		return sys.stdin.readline()[:-1]
	(H, W) = map(int, input().split())
	graph = [input() for _ in range(H)]
	dist = [[-1] * W for _ in range(H)]
	queue = deque()
	H -= 1
	W -= 1
	queue.append((0, 0))
	dist[0][0] = 0
	cnt = 0
	for g in graph:
		cnt += g.count('.')
	while queue:
		(vx, vy) = queue.popleft()
		if (vx, vy) == (W, H):
			break
		dxdy = [(1, 0), (0, 1), (-1, 0), (0, -1)]
		for (dx, dy) in dxdy:
			if vx + dx > W or vy + dy > H:
				continue
			elif vx + dx < 0 or vy + dy < 0:
				continue
			elif graph[vy + dy][vx + dx] == '.':
				if dist[vy + dy][vx + dx] == -1:
					queue.append((vx + dx, vy + dy))
					dist[vy + dy][vx + dx] = dist[vy][vx] + 1
			elif graph[vy + dy][vx + dx] == '#':
				continue
			else:
				continue
	if dist[H][W] == -1:
		print(-1)
	else:
		print(cnt - dist[H][W] - 1)

def __starting_point():
	main()
__starting_point()


(H, W) = map(int, input().split())
List = []
queue = [(0, 0, 1)]
shape = 0
used = {(0, 0)}
for i in range(H):
	x = input()
	shape += x.count('#')
	List.append(x)

def check(x, y, c):
	if x > W - 1 or y > H - 1 or x < 0 or (y < 0):
		return
	if List[y][x] == '#':
		return
	if (x, y) in used:
		return
	queue.append((x, y, c + 1))
	used.add((x, y))
flag = -1
while len(queue) != 0:
	(x, y, c) = queue[0]
	if x == W - 1 and y == H - 1:
		flag = 1
		break
	queue.pop(0)
	check(x + 1, y, c)
	check(x, y + 1, c)
	check(x - 1, y, c)
	check(x, y - 1, c)
if flag == 1:
	print(H * W - c - shape)
else:
	print(-1)


def main():
	from collections import deque
	(H, W) = list(map(int, input().split()))
	S = []
	num_path = 0
	for _ in range(H):
		s = input()
		num_path += s.count('.')
		S.append(s)
	move = ((0, 1), (0, -1), (1, 0), (-1, 0))
	distance = [[1] * W for _ in range(H)]
	queue = deque([(0, 0)])
	while queue:
		(y, x) = queue.popleft()
		if y == H - 1 and x == W - 1:
			break
		for (dy, dx) in move:
			ny = y + dy
			nx = x + dx
			if 1 and 0 <= ny < H and (0 <= nx < W) and (distance[ny][nx] == 1) and (S[ny][nx] == '.'):
				queue.append((ny, nx))
				distance[ny][nx] = distance[y][x] + 1
	if distance[H - 1][W - 1] == 1:
		print(-1)
	else:
		print(num_path - distance[H - 1][W - 1])

def __starting_point():
	main()
__starting_point()


from collections import deque
(R, C) = map(int, input().split())
masu = [list(input()) for _ in range(R)]
(sr, sc) = (0, 0)
(gr, gc) = (R - 1, C - 1)

def bfs():
	d = [[float('inf')] * C for _ in range(R)]
	dr = [0, -1, 0, 1]
	dc = [1, 0, -1, 0]
	que = deque([])
	que.append((sr, sc))
	d[sr][sc] = 0
	while que:
		p = que.popleft()
		if p[0] == gr and p[1] == gc:
			break
		for i in range(4):
			nr = p[0] + dr[i]
			nc = p[1] + dc[i]
			if 0 <= nr < R and 0 <= nc < C and (masu[nr][nc] != '#') and (d[nr][nc] == float('inf')):
				que.append((nr, nc))
				d[nr][nc] = d[p[0]][p[1]] + 1
	return d[gr][gc]
white = 0
for i in range(R):
	for j in range(C):
		if masu[i][j] == '.':
			white += 1
res = bfs()
if 0 < res < float('inf'):
	print(white - res - 1)
else:
	print(-1)


from collections import deque
(H, W) = map(int, input().split())
Map = [list(input()) for i in range(H)]
for h in range(H):
	Map[h].insert(0, '#')
	Map[h].append('#')
Map.insert(0, ['#'] * (W + 2))
Map.append(['#'] * (W + 2))
white = sum((Map[i].count('.') for i in range(H + 2)))
Que = deque([(1, 1, 1)])
visited = [[10 ** 10] * (W + 2) for i in range(H + 2)]
while Que:
	(x, y, stage) = Que.popleft()
	if x == W and y == H:
		print(white - stage)
		exit()
	stage += 1
	for (i, j) in ((x + 1, y), (x - 1, y), (x, y + 1), (x, y - 1)):
		if Map[j][i] == '.' and stage < visited[j][i]:
			visited[j][i] = stage
			Que.append((i, j, stage))
print(-1)


(h, w) = map(int, input().split())
a = [input() for _ in range(h)]
b = [[h * w] * w for _ in range(h)]
b[0][0] = 1
d = [(0, 0)]
while d:
	(y, x) = d.pop(0)
	for (i, j) in ([1, 0], [-1, 0], [0, 1], [0, -1]):
		(t, u) = (y + i, x + j)
		if h > t >= 0 <= u < w and a[t][u] == '.' and (b[t][u] > b[y][x] + 1):
			d += [(t, u)]
			b[t][u] = b[y][x] + 1
print(max(-1, sum([i.count('.') for i in a]) - b[-1][-1]))


from collections import deque
import sys
(H, W) = map(int, input().split())
S = [[x for x in input()] for _ in range(H)]
count = 0
for i in range(len(S)):
	count += S[i].count('.')
d = deque([(0, 0)])
distance = [[-1] * W for _ in range(H)]
distance[0][0] = 0
goal_distance = 0
while d:
	(h, w) = d.popleft()
	if h == H - 1 and w == W - 1:
		goal_distance = distance[h][w]
		break
	if h - 1 >= 0 and S[h - 1][w] == '.':
		d.append((h - 1, w))
		distance[h - 1][w] = distance[h][w] + 1
		S[h - 1][w] = '#'
	if h + 1 <= H - 1 and S[h + 1][w] == '.':
		d.append((h + 1, w))
		distance[h + 1][w] = distance[h][w] + 1
		S[h + 1][w] = '#'
	if w - 1 >= 0 and S[h][w - 1] == '.':
		d.append((h, w - 1))
		distance[h][w - 1] = distance[h][w] + 1
		S[h][w - 1] = '#'
	if w + 1 <= W - 1 and S[h][w + 1] == '.':
		d.append((h, w + 1))
		distance[h][w + 1] = distance[h][w] + 1
		S[h][w + 1] = '#'
else:
	if distance[H - 1][W - 1] == -1:
		print(-1)
		return
print(count - (goal_distance + 1))


from collections import deque
(H, W) = map(int, input().split())
s = [list(input()) for _ in range(H)]
d = deque()
d.append([0, 0, 0])
s[0][0] = '0'
mx = [1, 0, -1, 0]
my = [0, 1, 0, -1]
ans = 0
white = 0
for i in range(H):
	for j in range(W):
		if s[i][j] == '.':
			white += 1
while len(d) > 0:
	(t, y, x) = d.popleft()
	if [y, x] == [H - 1, W - 1]:
		break
	for m in range(4):
		if 0 <= y + my[m] < H and 0 <= x + mx[m] < W and (s[y + my[m]][x + mx[m]] == '.'):
			d.append([t + 1, y + my[m], x + mx[m]])
			s[y + my[m]][x + mx[m]] = str(t + 1)
if s[-1][-1] == '.':
	print(-1)
else:
	print(white - int(s[-1][-1]))


(H, W) = map(int, input().split())
s = [input() for i in range(H)]
from collections import deque
m = [[-1] * W for i in range(H)]
m[0][0] = 0
d = deque()
d.append([0, 0])
dx = [1, -1, 0, 0]
dy = [0, 0, 1, -1]
while len(d) > 0:
	(y, x) = d.popleft()
	for i in range(4):
		ny = y + dy[i]
		nx = x + dx[i]
		if 0 <= ny <= H - 1 and 0 <= nx <= W - 1 and (s[ny][nx] == '.') and (m[ny][nx] == -1):
			m[ny][nx] = m[y][x] + 1
			d.append([ny, nx])
ans = m[H - 1][W - 1]
whites = -1
for i in s:
	whites += i.count('.')
if ans != -1:
	ans = whites - ans
print(ans)


from collections import deque
(h, w) = map(int, input().split())
ans = 0
c = []
for i in range(h):
	ci = list(input())
	ans += ci.count('.')
	c.append(ci)
sy = 0
sx = 0
gy = h - 1
gx = w - 1
dx = [1, 0, -1, 0]
dy = [0, 1, 0, -1]
que = deque([(sy, sx)])
c[sy][sx] = 1
while bool(que):
	(y, x) = que.popleft()
	if y == gy and x == gx:
		break
	for i in range(4):
		yi = y + dy[i]
		xi = x + dx[i]
		if 0 <= yi < h and 0 <= xi < w and (c[yi][xi] == '.'):
			que.append((yi, xi))
			c[yi][xi] = c[y][x] + 1
if c[gy][gx] == '.':
	print(-1)
else:
	print(ans - c[gy][gx])


from collections import deque
(H, W) = map(int, input().split())
mp = [['#'] * (W + 2)]
count = 0
for _ in range(H):
	l = list(input())
	mp.append(['#'] + l + ['#'])
	count += l.count('.')
mp.append(['#'] * (W + 2))
dist = [[-1] * (W + 2) for _ in range(H + 2)]
Q = deque()
Q.append((1, 1))
dist[1][1] = 1
f = False
while Q:
	(y, x) = Q.popleft()
	if (y, x) == (H, W):
		f = True
		break
	for (dy, dx) in [(1, 0), (-1, 0), (0, 1), (0, -1)]:
		ny = y + dy
		nx = x + dx
		if 0 <= ny < H + 2 and 0 <= nx < W + 2:
			if mp[ny][nx] == '.' and dist[ny][nx] == -1:
				Q.append((ny, nx))
				dist[ny][nx] = dist[y][x] + 1
if f:
	print(count - dist[H][W])
else:
	print(-1)


from collections import deque
(H, W, *S) = open(0).read().split()
(H, W, S) = (int(H), int(W), [list(s) for s in S])
white = sum((s.count('.') for s in S))
Q = deque([(0, 0, 1)])
while Q:
	(h, w, count) = Q.popleft()
	if (h, w) == (H - 1, W - 1):
		print(white - count)
		quit()
	for (nh, nw) in [(h, w + 1), (h, w - 1), (h + 1, w), (h - 1, w)]:
		if 0 <= nh < H and 0 <= nw < W and (S[nh][nw] == '.'):
			S[nh][nw] = 'visited'
			Q.append((nh, nw, count + 1))
print(-1)


(h, w) = map(int, input().split())
s = ['#' * (w + 2)]
s += ['#' + input() + '#' for _ in range(h)]
s.append('#' * (w + 2))
h += 2
w += 2
p = [[1, 0], [0, 1], [-1, 0], [0, -1]]
st = []
cnt = 0
for i in range(h):
	for j in range(w):
		if s[i][j] == '.':
			cnt += 1
ans = 0
n = [(1, 1)]
route = {n[0]: 0}
count = 0
while n:
	count += 1
	n2 = []
	for i in n:
		for j in p:
			np = (i[0] + j[0], i[1] + j[1])
			if s[np[0]][np[1]] == '.' and route.get(np, -1) == -1:
				n2.append(np)
				route[np] = count
	n = n2
if route.get((h - 2, w - 2), -1) >= 0:
	print(cnt - route.get((h - 2, w - 2), -1) - 1)
else:
	print(-1)


(H, W) = tuple(map(int, input().split()))
s = [input() for _ in range(H)]
q = [(0, 0, 0)]
h = {(0, 0)}
opt = float('inf')
while q:
	(i, j, k) = q.pop(0)
	if i == H - 1 and j == W - 1:
		opt = k
		break
	a = [(u, v) for (u, v) in ((i + 1, j), (i, j + 1), (i - 1, j), (i, j - 1)) if 0 <= u < H and 0 <= v < W and (s[u][v] == '.') and ((u, v) not in h)]
	q += [(u, v, k + 1) for (u, v) in a]
	h |= set(a)
print(max(-1, sum((t.count('.') for t in s)) - opt - 1))


import queue
(h, w) = list(map(int, input().split()))
s = []
black_num = 0
for i in range(h):
	s_ij = input()
	s.append(s_ij)
	for j in range(w):
		if s_ij[j] == '#':
			black_num += 1
already_pass = set()
already_pass.add((1, 1))
q = queue.Queue()
q.put([(1, 1), 1])
while not q.empty():
	(x_y, l) = q.get()
	x = x_y[0]
	y = x_y[1]
	if x == h and y == w:
		print(h * w - black_num - l)
		break
	next_xy = [(max(1, x - 1), y), (min(h, x + 1), y), (x, max(1, y - 1)), (x, min(w, y + 1))]
	for i in next_xy:
		if i not in already_pass and s[i[0] - 1][i[1] - 1] != '#':
			q.put([i, l + 1])
			already_pass.add(i)
else:
	print(-1)


from collections import deque
(H, W) = map(int, input().split())
G = [input() for _ in range(H)]
white = 0
dist = [(-1, 0), (1, 0), (0, -1), (0, 1)]
visited = set()
for line in G:
	white += line.count('.')
D = deque()
D.append((0, 0, 1))
rout = -1
while D:
	(h, w, c) = D.popleft()
	if h == H - 1 and w == W - 1:
		rout = c
		break
	if (h, w) in visited or G[h][w] == '#':
		continue
	else:
		visited.add((h, w))
	for (dh, dw) in dist:
		if 0 <= h + dh < H and 0 <= w + dw < W:
			if (h + dh, w + dw) not in visited and G[h + dh][w + dw] != '#':
				D.append((h + dh, w + dw, c + 1))
if rout == -1:
	print(rout)
else:
	print(white - rout)


(h, w) = map(int, input().split())
s = [list(input()) for i in range(h)]
blackCnt = 0
for i in s:
	for j in i:
		if j == '#':
			blackCnt += 1
q = [[0, 0]]
route = [[1, 0], [0, 1], [-1, 0], [0, -1]]
visited = [[0 for i in range(w)] for j in range(h)]
visited[0][0] = 1
cnt = 0
while q:
	for _ in range(len(q)):
		(x, y) = q.pop(0)
		for i in range(4):
			(nx, ny) = (x + route[i][0], y + route[i][1])
			if 0 <= nx < h and 0 <= ny < w and (visited[nx][ny] == 0) and (s[nx][ny] != '#'):
				q.append([nx, ny])
				visited[nx][ny] = 1
	cnt += 1
	if visited[h - 1][w - 1] == 1:
		print(w * h - cnt - 1 - blackCnt)
		exit()
print(-1)


from collections import deque
(H, W) = map(int, input().split())
X = [input() for _ in range(H)]
dist = [[0] * W for _ in range(H)]
dist[0][0] = 1
q = deque([(0, 0)])
while q:
	(u, v) = q.popleft()
	for (i, j) in [(-1, 0), (1, 0), (0, -1), (0, 1)]:
		if not (0 <= u + i < H and 0 <= v + j < W) or X[u + i][v + j] == '#' or dist[u + i][v + j] > 0:
			continue
		dist[u + i][v + j] = dist[u][v] + 1
		q.append((u + i, v + j))
if dist[-1][-1] > 0:
	print(W * H - dist[-1][-1] - sum((s.count('#') for s in X)))
else:
	print(-1)


(H, W) = list(map(int, input().split()))
M = [[-1] * (W + 2)]
ans = 0
for _ in range(H):
	s = input()
	ans += s.count('.')
	M.append([-1] + [0 if c == '.' else -1 for c in s] + [-1])
M += [[-1] * (W + 2)]
queue = [(1, 1)]
M[1][1] = 1
dr = [(+1, 0), (-1, 0), (0, +1), (0, -1)]
turn = 1
while len(queue) > 0:
	turn += 1
	queue_new = []
	for (qx, qy) in queue:
		for (dx, dy) in dr:
			(x, y) = (qx + dx, qy + dy)
			if M[y][x] == 0:
				M[y][x] = turn
				queue_new.append((x, y))
	queue = queue_new
print(ans - M[H][W] if M[H][W] > 0 else -1)


from collections import deque
(h, w) = map(int, input().split())
l = []
v = 0
for _ in range(h):
	b = [0 if i == '.' else 1 for i in input()]
	v += b.count(1)
	l.extend([b])
dq = deque([])
dq.append((0, 0, 1))
while dq:
	(x, y, d) = dq.popleft()
	if x == w - 1 and y == h - 1:
		break
	for (dx, dy) in zip([-1, 1, 0, 0], [0, 0, -1, 1]):
		nx = x + dx
		ny = y + dy
		if 0 <= nx < w and 0 <= ny < h and (not l[ny][nx]):
			l[ny][nx] = 2
			dq.append((nx, ny, d + 1))
if x == w - 1 and y == h - 1:
	print(h * w - v - d)
else:
	print(-1)


(H, W) = map(int, input().split())
F = [list(input()) for _ in range(H)]
cnt = 0
for i in range(H):
	for j in range(W):
		if F[i][j] == '.':
			cnt += 1
que = [[0, 0, 0]]
flag = True
while len(que) > 0 and flag:
	sp = que.pop(0)
	(y, x, c) = (sp[0], sp[1], sp[2])
	for (dy, dx) in [[1, 0], [-1, 0], [0, 1], [0, -1]]:
		if 0 <= y + dy < H and 0 <= x + dx < W and (F[y + dy][x + dx] == '.'):
			F[y + dy][x + dx] = c + 1
			que.append([y + dy, x + dx, c + 1])
			if y + dy == H - 1 and x + dx == W - 1:
				flag = False
if flag:
	print(-1)
else:
	print(cnt - F[H - 1][W - 1] - 1)


from collections import deque
import sys
(h, w) = map(int, input().split())
mp = [list(input()) for _ in range(h)]
visited = [[0] * w for _ in range(h)]
dxdy = [[1, 0], [0, 1], [-1, 0], [0, -1]]
queue = deque()
queue.append([0, 0, 1])
visited[0][0] = 1
while queue:
	(x, y, d) = queue.popleft()
	for (dx, dy) in dxdy:
		(nx, ny) = (x + dx, y + dy)
		if -1 < nx < h and -1 < ny < w and (visited[nx][ny] == 0) and (mp[nx][ny] != '#'):
			visited[nx][ny] = d + 1
			queue.append([nx, ny, d + 1])
if visited[-1][-1] == 0:
	print(-1)
	return
cnt = 0
for i in range(h):
	for j in range(w):
		if mp[i][j] != '#':
			cnt += 1
print(cnt - visited[-1][-1])


from collections import deque
(h, w) = map(int, input().split())
p = [list('#' * (w + 2))] + [list('#' + input() + '#') for i in range(h)] + [list('#' * (w + 2))]
(s0, s1) = (1, 1)
(g0, g1) = (h, w)
p[s0][s1] = 0
d = [(1, 0), (-1, 0), (0, 1), (0, -1)]
q = deque([[s0, s1]])
while q:
	(x, y) = q.popleft()
	for (dx, dy) in d:
		if p[x + dx][y + dy] == '.':
			p[x + dx][y + dy] = p[x][y] + 1
			q.append([x + dx, y + dy])
if p[g0][g1] == '.':
	print(-1)
else:
	yy = 0
	for i in range(1, h + 1):
		for j in range(1, w + 1):
			if p[i][j] == '#':
				yy += 1
	print(h * w - p[g0][g1] - yy - 1)


from collections import deque
(h, w) = list(map(int, input().split()))
grid = [input() for _ in range(h)]
q = deque([(0, 0)])
dists = [[10000] * w for _ in range(h)]
dists[0][0] = 0
prev = [[-1] * w for _ in range(h)]
while q:
	(x, y) = q.popleft()
	nei = [(0, 1), (0, -1), (1, 0), (-1, 0)]
	for (xo, yo) in nei:
		(nextx, nexty) = (x + xo, y + yo)
		if nextx < 0 or nextx >= w or nexty < 0 or (nexty >= h):
			continue
		if grid[nexty][nextx] == '#':
			continue
		dist = dists[y][x] + 1
		if dist < dists[nexty][nextx]:
			dists[nexty][nextx] = dist
			prev[nexty][nextx] = (x, y)
			q.append((nextx, nexty))
if prev[h - 1][w - 1] != -1:
	path = []
	cur = (w - 1, h - 1)
	while cur != -1:
		path.append(cur)
		cur = prev[cur[1]][cur[0]]
	cnt = 0
	for i in range(w):
		for j in range(h):
			if grid[j][i] == '.' and (i, j) not in path:
				cnt += 1
	print(cnt)
else:
	print(-1)


from collections import deque
move = ((-1, 0), (1, 0), (0, -1), (0, 1))
(H, W) = map(int, input().split())
M = []
visited = [[0] * W for _ in range(H)]
D = [[0] * W for _ in range(H)]
black = 0
for _ in range(H):
	s = input()
	M.append(s)
	for c in s:
		if c == '#':
			black += 1
q = deque()
q.append((0, 0))
cost = -1
while q:
	(y, x) = q.popleft()
	d = D[y][x]
	if x == W - 1 and y == H - 1:
		cost = d
		break
	if visited[y][x] == 1:
		continue
	else:
		visited[y][x] = 1
		for (dx, dy) in move:
			(nx, ny) = (x + dx, y + dy)
			if 0 <= nx < W and 0 <= ny < H:
				if visited[ny][nx] == 0 and M[ny][nx] == '.':
					D[ny][nx] = d + 1
					q.append((ny, nx))
if cost == -1:
	print(-1)
else:
	print(H * W - cost - 1 - black)


(H, W) = map(int, input().split())
import numpy as np
Grid = np.array([[0 if x == '.' else -1 for x in input()] for _ in range(H)], dtype='int64')

def solveMase(Grid, start, goal):
	seen = {start}
	V = [start]
	while len(V) != 0:
		v = V.pop(0)
		if v == goal:
			return Grid[goal]
		(y, x) = v
		nV = []
		if x > 0:
			nV.append((y, x - 1))
		if y > 0:
			nV.append((y - 1, x))
		if x < W - 1:
			nV.append((y, x + 1))
		if y < H - 1:
			nV.append((y + 1, x))
		for nv in nV:
			if Grid[nv] == -1 or nv in seen:
				continue
			Grid[nv] = Grid[v] + 1
			V.append(nv)
			seen.add(nv)
	return 0
white = len(Grid[Grid == 0]) - 1
nes_white = solveMase(Grid, (0, 0), (H - 1, W - 1))
if nes_white > 0:
	ans = white - nes_white
else:
	ans = -1
print(ans)


from collections import deque
(H, W) = map(int, input().split(' '))
S = [list(input()) for i in range(H)]
S[0][0] = 1
next = deque([[0, 0]])
ans = H * W
while next:
	(x, y) = next.popleft()
	s = S[x][y]
	for (i, j) in [[1, 0], [0, 1], [-1, 0], [0, -1]]:
		if 0 <= x + i < H and 0 <= y + j < W and (S[x + i][y + j] == '.'):
			S[x + i][y + j] = s + 1
			next.append([x + i, y + j])
for i in S:
	ans -= i.count('#')
if type(S[H - 1][W - 1]) == str:
	print(-1)
else:
	print(ans - S[H - 1][W - 1])


from collections import deque
(h, w) = map(int, input().split())
s = [list(input()) for _ in range(h)]
q = deque()
q.append((0, 0, 0))
check = [[0] * w for _ in range(h)]
flag = False
while q:
	(y, x, d) = q.popleft()
	if y == h - 1 and x == w - 1:
		g = d
		flag = True
		break
	if check[y][x] == 0:
		check[y][x] = 1
		for (xdx, ydy) in zip((x, x, x + 1, x - 1), (y + 1, y - 1, y, y)):
			if 0 <= xdx < w and 0 <= ydy < h:
				if check[ydy][xdx] == 0 and s[ydy][xdx] == '.':
					q.append((ydy, xdx, d + 1))
ss = 0
for i in s:
	ss += i.count('#')
print(h * w - ss - d - 1 if flag else -1)


(H, W) = map(int, input().split())
MAP = [list(input()) for i in range(H)]
ANS = 0
for i in range(H):
	ANS += MAP[i].count('.')
from collections import deque
QUE = deque()
QUE.append((0, 0))
MAP[0][0] = 0
while QUE:
	(x, y) = QUE.pop()
	for (i, j) in [(x + 1, y), (x - 1, y), (x, y + 1), (x, y - 1)]:
		if i < 0 or j < 0 or i >= H or (j >= W):
			continue
		if MAP[i][j] == '.':
			MAP[i][j] = MAP[x][y] + 1
			QUE.appendleft((i, j))
if MAP[H - 1][W - 1] == '.':
	print(-1)
else:
	print(ANS - MAP[H - 1][W - 1] - 1)


from collections import deque
(H, W) = map(int, input().split())
s = [input() for i in range(H)]
Map = [[0] * W for i in range(H)]
num_b = 0
for i in range(H):
	for j in range(W):
		if s[i][j] == '#':
			num_b += 1
			Map[i][j] = -1
dxy = [(1, 0), (0, 1), (-1, 0), (0, -1)]
que = deque([[0, 0]])
Map[0][0] = 1
while que:
	(x, y) = que.popleft()
	for (dx, dy) in dxy:
		(xx, yy) = (x + dx, y + dy)
		if 0 <= xx < H and 0 <= yy < W and (Map[xx][yy] == 0):
			Map[xx][yy] = Map[x][y] + 1
			if (xx, yy) == (H - 1, W - 1):
				print(H * W - Map[xx][yy] - num_b)
				quit()
			que.append([xx, yy])
print(-1)


(h, w) = map(int, input().split())
G = []
white = 0
for _ in range(h):
	s = input()
	white += s.count('.')
	G.append(s)
vis = [[0] * w for _ in range(h)]
vis[0][0] = 1
from collections import deque
que = deque([(0, 0, 1)])
move = [(1, 0), (-1, 0), (0, 1), (0, -1)]
while len(que) > 0:
	(ni, nj, c) = que.popleft()
	for (di, dj) in move:
		(mi, mj) = (ni + di, nj + dj)
		if 0 <= mi < h and 0 <= mj < w and (G[mi][mj] == '.') and (vis[mi][mj] == 0):
			vis[mi][mj] = c + 1
			que.append((mi, mj, c + 1))
print(white - vis[-1][-1]) if vis[-1][-1] != 0 else print(-1)


import sys
(H, W) = map(int, input().split())
C = [list(input()) for i in range(H)]
cost = [[-1 for i in range(W)] for i in range(H)]
queue = []
black = 0
for i in range(H):
	black += C[i].count('#')
queue.append([0, 0])
cost[0][0] = 0
dy_dx = [[1, 0], [0, 1], [-1, 0], [0, -1]]
while len(queue) > 0:
	now = queue.pop(0)
	if now[0] == H - 1 and now[1] == W - 1:
		ans = H * W - cost[H - 1][W - 1] - black - 1
		print(ans)
		return
	for i in range(4):
		y = now[0] + dy_dx[i][0]
		x = now[1] + dy_dx[i][1]
		if 0 <= y < H and 0 <= x < W:
			if C[y][x] != '#' and cost[y][x] == -1:
				cost[y][x] = cost[now[0]][now[1]] + 1
				queue.append([y, x])
print(-1)


from collections import deque

def bfs(start, goal):
	q = deque([[start]])
	visited = set()
	while q:
		path = q.popleft()
		(i, j) = path[-1]
		if (i, j) == goal:
			return path
		for (di, dj) in [(1, 0), (-1, 0), (0, 1), (0, -1)]:
			(ni, nj) = (i + di, j + dj)
			if not (0 <= ni < H and 0 <= nj < W and (field[ni][nj] == '.')):
				continue
			if (ni, nj) not in visited:
				q.append(path + [(ni, nj)])
				visited.add((ni, nj))
	return []
(H, W) = list(map(int, input().split()))
field = [input() for _ in range(H)]
shortest_path = bfs((0, 0), (H - 1, W - 1))
if shortest_path:
	print(sum((v == '.' for row in field for v in row)) - len(shortest_path))
else:
	print(-1)


from fractions import gcd
from itertools import combinations, permutations, accumulate, product
from collections import deque, defaultdict, Counter
import decimal
import re
import math
import bisect
import sys
sys.setrecursionlimit(10000000)
mod = 10 ** 9 + 7
from sys import stdin
readline = stdin.readline

def readInts():
	return list(map(int, readline().split()))

def readTuples():
	return tuple(map(int, readline().split()))

def I():
	return int(readline())
(h, w) = readInts()
block = [input() for _ in range(h)]
allcnt = 0
for i in range(w):
	for j in range(h):
		if block[j][i] == '.':
			allcnt += 1
INF = float('inf')
AR = [[INF] * w for _ in range(h)]
dy = [1, 0, 0, -1]
dx = [0, -1, 1, 0]

def bfs():
	d = deque()
	d.append([0, 0])
	while d:
		(y, x) = d.popleft()
		if y == 0 and x == 0:
			AR[y][x] = 0
		for i in range(4):
			ny = y + dy[i]
			nx = x + dx[i]
			if not 0 <= ny < h or not 0 <= nx < w:
				continue
			if AR[ny][nx] == INF and block[ny][nx] != '#':
				AR[ny][nx] = AR[y][x] + 1
				d.append([ny, nx])
bfs()
if AR[h - 1][w - 1] == INF:
	print(-1)
else:
	print(allcnt - (AR[h - 1][w - 1] + 1))


from collections import deque
dis = [[1, 0], [-1, 0], [0, 1], [0, -1]]
(H, W) = map(int, input().split())
A = []
count = 0
for i in range(H):
	a = input()
	A.append(a)
	count += a.count('.')
B = [[0 for j in range(W)] for i in range(H)]
D = deque([[0, 0]])
B[0][0] = 1
while len(D) > 0:
	d = D.popleft()
	for k in range(4):
		p = d[0] + dis[k][0]
		q = d[1] + dis[k][1]
		if 0 <= p < H and 0 <= q < W and (A[p][q] == '.') and (B[p][q] == 0):
			B[p][q] = B[d[0]][d[1]] + 1
			D.append([p, q])
if B[H - 1][W - 1] == 0:
	print(-1)
else:
	print(count - B[H - 1][W - 1])


from collections import deque
(Y, X) = map(int, input().split())
Map = list((input() for _ in range(Y)))

def bfs(sy, sx, gy, gx):
	seen = list(([-1] * X for _ in range(Y)))
	queue = deque()
	queue.append((sy, sx))
	seen[sy][sx] = 0
	while queue:
		(y, x) = queue.popleft()
		search_around(y, x, seen, queue)
		if seen[gy][gx] > 0:
			return seen[gy][gx]

def search_around(y, x, seen, queue):
	count = seen[y][x]
	for (u, t) in [(y - 1, x), (y + 1, x), (y, x - 1), (y, x + 1)]:
		if u < 0 or t < 0 or u >= Y or (t >= X):
			continue
		elif Map[u][t] == '#' or seen[u][t] != -1:
			continue
		queue.append((u, t))
		seen[u][t] = count + 1
cnt = 0
for M in Map:
	for m in M:
		if m == '#':
			cnt += 1
b = bfs(0, 0, Y - 1, X - 1)
if b == None:
	print(-1)
else:
	print(Y * X - cnt - b - 1)


(H, W) = map(int, input().split())
m = []
m.append('#' * (W + 2))
white = 0
for i in range(H):
	s = input()
	m.append(list('#' + s + '#'))
	white += s.count('.')
m.append('#' * (W + 2))
op = set([(1, 1)])
dist = 0
while len(op) > 0:
	dist += 1
	next_op = set()
	for (y, x) in op:
		m[y][x] = dist
		if (y, x) == (H, W):
			print(white - dist)
			exit()
		for (dx, dy) in ([0, 1], [0, -1], [1, 0], [-1, 0]):
			if m[y - dy][x - dx] == '.':
				next_op.add((y - dy, x - dx))
	op = next_op
print('-1')


from collections import deque
(H, W) = list(map(int, input().split()))
grid = [list('#' * (W + 2))]
b_cnt = 0
for _ in range(H):
	tmp = list(input())
	grid.append(['#'] + tmp + ['#'])
grid.append(list('#' * (W + 2)))
grid[1][1] = 1
q = deque([[1, 1]])
move = [[1, 0], [-1, 0], [0, 1], [0, -1]]
while q:
	(x, y) = q.popleft()
	for (dx, dy) in move:
		if grid[x + dx][y + dy] == '.':
			grid[x + dx][y + dy] = grid[x][y] + 1
			q.append([x + dx, y + dy])
if grid[H][W] == '.':
	print(-1)
else:
	print((H + 2) * (W + 2) - sum((g.count('#') for g in grid)) - grid[H][W])


(R, C) = map(int, input().split())
c = [list(input()) for _ in range(R)]
d = {}
q = [(0, 0, 0)]
d[0, 0] = 0
while q != []:
	(y, x, z) = q.pop(0)
	for (v, w) in [(-1, 0), (1, 0), (0, -1), (0, 1)]:
		t = x + v
		u = y + w
		if t < 0 or t >= C or u < 0 or (u >= R):
			continue
		if c[u][t] == '.' and (u, t) not in d:
			q.append((u, t, z + 1))
			d[u, t] = z + 1
if (R - 1, C - 1) not in d:
	ans = -1
else:
	ans = R * C - d[R - 1, C - 1] - 1
	for i in c:
		for j in i:
			if j == '#':
				ans -= 1
print(ans)


import sys
import operator
from collections import deque, Counter
input = sys.stdin.readline
(h, w) = map(int, input().split())
(sx, sy) = (0, 0)
(gx, gy) = (h - 1, w - 1)
s = [list(input()) for _ in range(h)]
c = []
for a in s:
	c += a
c = Counter(c)
white = c['.']
dx = [1, 0, -1, 0]
dy = [0, 1, 0, -1]
visited = [[-1] * w for _ in range(h)]

def bfs(x, y):
	queue = deque([[x, y]])
	visited[x][y] = 0
	while queue:
		(x, y) = queue.popleft()
		if [x, y] == [gx, gy]:
			return visited[x][y]
		for i in range(4):
			(nx, ny) = (x + dx[i], y + dy[i])
			if nx >= 0 and nx < h and (ny >= 0) and (ny < w) and (s[nx][ny] == '.') and (visited[nx][ny] == -1):
				visited[nx][ny] = visited[x][y] + 1
				queue.append([nx, ny])
bfs(sx, sy)
print(white - visited[gx][gy] - 1 if visited[gx][gy] != -1 else -1)


import queue
(h, w) = map(int, input().split())
INF = 10 ** 9
s = [[-1] * w for _ in range(h)]
b = 0
for i in range(h):
	x = input()
	for j in range(w):
		if x[j] == '.':
			s[i][j] = INF
		else:
			b += 1
q = queue.Queue()
s[0][0] = 0
q.put((0, 0))

def test(x, y, t):
	if 0 <= x < h and 0 <= y < w:
		u = s[x][y]
		if t < u:
			s[x][y] = t
			q.put((x, y))
while not q.empty():
	(x, y) = q.get()
	t = s[x][y]
	test(x + 1, y, t + 1)
	test(x - 1, y, t + 1)
	test(x, y + 1, t + 1)
	test(x, y - 1, t + 1)
x = s[h - 1][w - 1]
print(-1 if x == INF else h * w - b - x - 1)


from collections import deque
(h, w) = map(int, input().split())
G = [['#'] * (w + 2)]
white = 0
for i in range(h):
	G.append(['#'] + list(input()) + ['#'])
	white += G[i + 1].count('.')
G.append(['#'] * (w + 2))
G[1][1] = 1
que = deque([[1, 1]])
while que:
	(y, x) = que.popleft()
	d = G[y][x]
	for (dy, dx) in ((1, 0), (-1, 0), (0, 1), (0, -1)):
		ny = y + dy
		nx = x + dx
		if G[ny][nx] == '.':
			G[ny][nx] = d + 1
			que.append((ny, nx))
if G[h][w] == '.':
	print('-1')
else:
	ans = white - G[h][w]
	print(ans)


from collections import deque
(h, w) = list(map(int, input().split()))
s = [input() for _ in range(h)]
c = 0
for i in range(h):
	for j in range(w):
		if s[i][j] == '#':
			c += 1
q = deque([[0, 0]])
dist = [[10000] * w for _ in range(h)]
dist[0][0] = 0
flag = False
while len(q) > 0:
	(i, j) = q.popleft()
	if i == h - 1 and j == w - 1:
		break
	else:
		if i < h - 1 and s[i + 1][j] == '.' and (not dist[i + 1][j] < 10000):
			q.append([i + 1, j])
			dist[i + 1][j] = dist[i][j] + 1
		if j < w - 1 and s[i][j + 1] == '.' and (not dist[i][j + 1] < 10000):
			q.append([i, j + 1])
			dist[i][j + 1] = dist[i][j] + 1
		if i > 0 and s[i - 1][j] == '.' and (not dist[i - 1][j] < 10000):
			q.append([i - 1, j])
			dist[i - 1][j] = dist[i][j] + 1
		if j > 0 and s[i][j - 1] == '.' and (not dist[i][j - 1] < 10000):
			q.append([i, j - 1])
			dist[i][j - 1] = dist[i][j] + 1
if dist[h - 1][w - 1] < 10000:
	print(h * w - dist[h - 1][w - 1] - 1 - c)
else:
	print(-1)


from collections import deque
move = ((-1, 0), (1, 0), (0, -1), (0, 1))
(H, W) = map(int, input().split())
M = ['#' * (W + 2)]
black = 0
for _ in range(H):
	row = input()
	M.append('#' + row + '#')
	black += row.count('#')
M.append('#' * (W + 2))
(sy, sx) = (1, 1)
(gy, gx) = (H, W)
D = [[-1] * (W + 2) for _ in range(H + 2)]
D[sy][sx] = 0
visited = set()
q = deque()
q.append((sy, sx))
visited.add((sy, sx))
while q:
	(y, x) = q.popleft()
	for (dy, dx) in move:
		(ny, nx) = (y + dy, x + dx)
		if M[ny][nx] == '#' or D[ny][nx] != -1:
			continue
		D[ny][nx] = D[y][x] + 1
		q.append((ny, nx))
print(W * H - (D[gy][gx] + 1) - black if D[gy][gx] != -1 else -1)


(H, W) = map(int, input().split())
S = [list(input()) for _ in range(H)]
white = 0
for i in range(H):
	white += S[i].count('.')
q = [(0, 0)]
S[0][0] = 0
while q:
	qq = []
	for xy in q:
		(x, y) = xy
		for (dx, dy) in ((1, 0), (-1, 0), (0, 1), (0, -1)):
			if not 0 <= x + dx < W or not 0 <= y + dy < H:
				continue
			elif S[y + dy][x + dx] != '.':
				continue
			S[y + dy][x + dx] = S[y][x] + 1
			qq.append((x + dx, y + dy))
	if S[-1][-1] != '.':
		break
	q = qq
print(white - S[-1][-1] - 1 if S[-1][-1] != '.' else -1)


from collections import deque
(h, w) = map(int, input().split())
map = [list(input()) for _ in range(h)]
ans = 0
for i in range(h):
	l = map[i]
	ans += l.count('.')

def bfs(x, y):
	for (next_x, next_y) in [(x + 1, y), (x - 1, y), (x, y + 1), (x, y - 1)]:
		if 0 <= next_x < h and 0 <= next_y < w and (map[next_x][next_y] == '.'):
			map[next_x][next_y] = 1 + map[x][y]
			q.append([next_x, next_y])
map[0][0] = 1
q = deque([[0, 0]])
while True:
	if len(q) == 0:
		break
	(x, y) = q.popleft()
	bfs(x, y)
if map[h - 1][w - 1] == '.':
	ans = -1
else:
	ans -= map[h - 1][w - 1]
print(ans)


from collections import deque
(h, w) = map(int, input().split())
bord = [list(input()) for _ in range(h)]
visit = [[-1 for _ in range(w)] for _ in range(h)]
visit[0][0] = 1
q = deque([[0, 0]])
visit[0][0] = 1
while q:
	(px, py) = q.popleft()
	for (i, j) in ([1, 0], [-1, 0], [0, 1], [0, -1]):
		if px + i >= 0 and px + i < h and (py + j >= 0) and (py + j < w):
			if bord[px + i][py + j] == '.' and visit[px + i][py + j] < 0:
				visit[px + i][py + j] = visit[px][py] + 1
				q.append([px + i, py + j])
if visit[h - 1][w - 1] < 0:
	print(-1)
else:
	c = [i.count('.') for i in bord]
	print(sum(c) - visit[h - 1][w - 1])


import math
import sys
from collections import deque
import copy

def mi():
	return map(int, input().split())
(a, b) = mi()
l = [list(input()) for _ in range(a)]
count = 0
for i in range(a):
	for _ in range(b):
		if l[i][_] == '.':
			count += 1
l[0][0] = 1
q = deque([[0, 0]])
while q:
	(x, y) = q.popleft()
	if x == a - 1 and y == b - 1:
		print(count - l[x][y])
		sys.exit()
	for (e, f) in [[0, 1], [0, -1], [1, 0], [-1, 0]]:
		if 0 <= x + e < a and 0 <= y + f < b and (l[x + e][f + y] == '.'):
			l[x + e][f + y] = l[x][y] + 1
			q.append([x + e, y + f])
print(-1)


(H, W) = map(int, input().split())
S = [input() for _ in range(H)]
G = [[-1] * W for _ in range(H)]
G[0][0] = 1
q = [(0, 0)]
while q:
	(i, j) = q[0]
	q = q[1:]
	for (x, y) in [(1, 0), (0, 1), (-1, 0), (0, -1)]:
		(t, u) = (i + x, j + y)
		if 0 <= t < H and 0 <= u < W and (G[t][u] < 0) and (S[t][u] == '.'):
			G[t][u] = 1 + G[i][j]
			q += [(t, u)]
print(-1 * (G[-1][-1] < 0) or sum((s.count('.') for s in S)) - G[-1][-1])


from collections import deque

def bfs(sy, sx):
	queue = deque([[sy, sx]])
	d[sy][sx] = 0
	while queue:
		(y, x) = queue.popleft()
		for (i, j) in [(-1, 0), (1, 0), (0, -1), (0, 1)]:
			(dy, dx) = (y + i, x + j)
			if dy < 0 or h <= dy:
				continue
			elif dx < 0 or w <= dx:
				continue
			elif s[dy][dx] == '#':
				continue
			elif d[dy][dx] != -1:
				continue
			d[dy][dx] = d[y][x] + 1
			queue.append([dy, dx])
(h, w) = map(int, input().split())
s = [input() for _ in range(h)]
if s[0][0] == '#' or s[h - 1][w - 1] == '#':
	print(-1)
	return
d = [[-1] * w for _ in range(h)]
bfs(0, 0)
if d[h - 1][w - 1] == -1:
	print(-1)
else:
	t = 0
	for i in s:
		t += i.count('#')
	print(h * w - t - d[h - 1][w - 1] - 1)


import numpy as np
(h, w, *s) = open(0).read().split()
h = int(h)
w = int(w)
all = sum((t.count('#') for t in s))
inf = 1 << 30
d = np.full((h + 1, w + 1), inf, dtype=np.int)
d[0][0] = 0
q = [(0, 0)]
for v in q:
	for nv in [(0, 1), (1, 0), (-1, 0), (0, -1)]:
		ny = v[0] + nv[0]
		nx = v[1] + nv[1]
		if 0 <= nx < w and 0 <= ny < h and (d[ny][nx] == inf) and (s[ny][nx] == '.'):
			d[ny][nx] = d[v[0]][v[1]] + 1
			q.append((ny, nx))
if d[h - 1][w - 1] == inf:
	print(-1)
else:
	print(h * w - (d[h - 1][w - 1] + 1) - all)


from collections import *
(H, W) = map(int, input().split())
M = [input() for _ in '_' * H]
C = [[1] * W for _ in '_' * H]
q = deque([[0, 0]])
while q:
	(x, y) = q.popleft()
	for (i, j) in [[1, 0], [-1, 0], [0, 1], [0, -1]]:
		(h, w) = (x + i, y + j)
		if H > h > -1 and W > w > -1 and (M[h][w] > '#') and (C[h][w] < 2):
			C[h][w] = C[x][y] + 1
			q.append([h, w])
c = C[H - 1][W - 1]
print(-1 * (c < 2) or sum((m.count('.') for m in M)) - c)


from collections import deque
(H, W) = map(int, input().split())
maze = '#' * (W + 2)
for _ in range(H):
	maze += '#' + input() + '#'
maze += '#' * (W + 2)
dist = [-1] * (W + 2) * (H + 2)
q = deque()
dist[(W + 2) * 1 + 1] = 0
q.append((W + 2) * 1 + 1)
while len(q) != 0:
	v = q.popleft()
	udlr = (-W - 2, W + 2, -1, 1)
	for move in udlr:
		nv = v + move
		if maze[nv] == '#':
			continue
		if dist[nv] != -1:
			continue
		dist[nv] = dist[v] + 1
		q.append(nv)
if dist[(W + 2) * H + W] == -1:
	print(-1)
else:
	print(W * H - maze.count('#') + 2 * (W + H + 2) - dist[(W + 2) * H + W] - 1)


(H, W) = map(int, input().split())
s = []
black = 0
for i in range(H):
	tmp = list(input())
	s.append(tmp)
	for j in range(W):
		if tmp[j] == '#':
			black += 1
white = H * W - black
q = [(0, 0, 0)]
s[0][0] = '#'
while q:
	(i, j, cnt) = q.pop(0)
	for (di, dj) in [(1, 0), (0, 1), (-1, 0), (0, -1)]:
		(ni, nj) = (i + di, j + dj)
		if ni == H - 1 and nj == W - 1:
			print(white - cnt - 2)
			exit(0)
		elif 0 <= ni < H and 0 <= nj < W and (s[ni][nj] == '.'):
			s[ni][nj] = '#'
			q.append((ni, nj, cnt + 1))
print(-1)


from collections import deque
(H, W) = map(int, input().split())
S = [[c for c in input()] for _ in range(H)]
a = sum([S[y][x] == '.' for x in range(W) for y in range(H)])
dx = [1, -1, 0, 0]
dy = [0, 0, 1, -1]
B = [[-1] * W for _ in range(H)]
q = deque([(0, 0, 1)])
while len(q) > 0:
	(y, x, step) = q.popleft()
	if y < 0 or H <= y or x < 0 or (W <= x):
		continue
	if S[y][x] == '#' or B[y][x] >= 0:
		continue
	B[y][x] = step
	for i in range(4):
		q.append((y + dy[i], x + dx[i], step + 1))
print(a - B[H - 1][W - 1] if B[H - 1][W - 1] >= 0 else -1)


from collections import deque
(H, W) = map(int, input().split())
edges = ['#'] * (W + 2)
field = [edges]
dyx = [(0, 1), (0, -1), (1, 0), (-1, 0)]
bk = 0
for _ in range(H):
	line = list(input())
	bk += line.count('#')
	field.append(['#'] + line + ['#'])
field.append(edges)
steps = 1
q = deque()
field[1][1] = 1
q.append((1, 1, 1))
while q:
	(cy, cx, lv) = q.popleft()
	for (dy, dx) in dyx:
		(ny, nx) = (dy + cy, dx + cx)
		if field[ny][nx] == '.':
			field[ny][nx] = lv + 1
			q.append((ny, nx, lv + 1))
steps = str(field[H][W])
if steps.isnumeric():
	print(W * H - bk - int(steps))
else:
	print(-1)


(h, w) = map(int, input().split())
grid = [list(input()) for i in range(h)]
sum = 0
for i in range(h):
	for j in range(w):
		if grid[i][j] == '.':
			sum += 1
grid[0][0] = 0
loc = [[0, 0]]
ans = 0
for k in range(1, h * w):
	next_loc = []
	for [y, x] in loc:
		for [i, j] in ([1, 0], [-1, 0], [0, 1], [0, -1]):
			if 0 <= y + i <= h - 1 and 0 <= x + j <= w - 1:
				if grid[y + i][x + j] == '.':
					grid[y + i][x + j] = k
					next_loc.append([y + i, x + j])
		loc = next_loc
	if [h - 1, w - 1] in loc:
		ans = k
		break
if ans == 0:
	print(-1)
else:
	print(sum - k - 1)


from collections import deque
(h, w) = map(int, input().split())
s = [list(input()) for i in range(h)]
dist = [[0 for i in range(w)] for j in range(h)]
que = deque([])
que.append([0, 0])
dyx = [[1, 0], [0, -1], [-1, 0], [0, 1]]
ndot = 0
for i in range(h):
	for j in range(w):
		if s[i][j] == '.':
			ndot += 1
s[0][0] = '#'
while que:
	(y, x) = que.popleft()
	for (dy, dx) in dyx:
		nx = x + dx
		ny = y + dy
		if nx < 0 or nx > w - 1 or ny < 0 or (ny > h - 1):
			continue
		if s[ny][nx] == '.':
			dist[ny][nx] = dist[y][x] + 1
			que.append([ny, nx])
			s[ny][nx] = '#'
ans = ndot - dist[h - 1][w - 1] - 1
if dist[h - 1][w - 1] == 0:
	ans = -1
print(ans)


import copy
(h, w) = (int(i) for i in input().split())
x = [input() for i in range(h)]
(cf, list1, num) = ([[0, 0]], [[0, 0]], 1)
while [h - 1, w - 1] not in cf and len(list1) != 0:
	list2 = []
	for j in list1:
		list3 = [[j[0] + 1, j[1]], [j[0] - 1, j[1]], [j[0], j[1] + 1], [j[0], j[1] - 1]]
		for j2 in list3:
			if -1 < j2[0] < h and -1 < j2[1] < w and (j2 not in cf) and (x[j2[0]][j2[1]] == '.'):
				cf.append(j2)
				list2.append(j2)
	num += 1
	list1 = copy.deepcopy(list2)
num2 = 0
for k in x:
	num2 += k.count('.')
if [h - 1, w - 1] not in cf:
	answer = -1
else:
	answer = num2 - num
print(answer)


(H, W) = map(int, input().split())
MAP = [['#'] * (W + 2)] + [['#'] + list(input()) + ['#'] for i in range(H)] + [['#'] * (W + 2)]
white = 0
for line in MAP:
	white += line.count('.')
from collections import deque
check = deque([(1, 1, 1)])
dist = float('inf')
while len(check) > 0:
	(d, x, y) = check.popleft()
	for (i, j) in [(-1, 0), (1, 0), (0, 1), (0, -1)]:
		if MAP[x + i][y + j] == '.':
			if x + i == H and y + j == W:
				dist = d + 1
				check = []
				break
			check.append((d + 1, x + i, y + j))
			MAP[x + i][y + j] = '#'
if dist > 10 ** 10:
	print(-1)
else:
	print(white - dist)


from collections import deque
(h, w) = map(int, input().split())
maze = [list(input()) for _ in range(h)]

def repaint(maze, sx, sy):
	maze[sy][sx] = 1
	que = deque([(sx, sy)])
	dxdy = [(1, 0), (0, 1), (-1, 0), (0, -1)]
	while que:
		(x, y) = que.popleft()
		for (dx, dy) in dxdy:
			if 0 <= x + dx < w and 0 <= y + dy < h and (maze[y + dy][x + dx] == '.'):
				maze[y + dy][x + dx] = maze[y][x] + 1
				que.append((x + dx, y + dy))
	return True
white = 0
for x in maze:
	white += x.count('.')
repaint(maze, 0, 0)
if maze[h - 1][w - 1] == '.':
	print(-1)
else:
	print(white - maze[h - 1][w - 1])


import collections
import math
(H, W) = map(int, input().split())
c = [list(str(input())) for i in range(H)]
d = [[0 for j in range(W)] for i in range(H)]
inf = 10 ** 6
ans = 0
for i in range(H):
	for j in range(W):
		if c[i][j] == '#':
			d[i][j] = -1
		else:
			d[i][j] = inf
			ans += 1
d[0][0] = 0
queue = collections.deque([[0, 0]])
(gy, gx) = (H - 1, W - 1)
moves = [[1, 0], [-1, 0], [0, 1], [0, -1]]
flag = False
while len(queue) > 0:
	now = queue.popleft()
	for i in range(4):
		ny = now[0] + moves[i][0]
		nx = now[1] + moves[i][1]
		if 0 <= ny and ny < H and (0 <= nx) and (nx < W) and (c[ny][nx] == '.') and (d[ny][nx] == inf):
			d[ny][nx] = d[now[0]][now[1]] + 1
			queue.append([ny, nx])
			if ny == gy and nx == gx:
				print(ans - d[ny][nx] - 1)
				return
print(-1)


import sys
(h, w) = list(map(int, input().split()))
ss = [list(input()) for i in range(h)]
num = 0
for i in range(h):
	num += ss[i].count('.')
visited = [[0 for i in range(w)] for j in range(h)]
queue = []
queue.append([0, 0])
ss[0][0] = 'fin'
dy = [1, 0, -1, 0]
dx = [0, 1, 0, -1]
while len(queue) > 0:
	now = queue.pop(0)
	for i in range(4):
		x = now[1] + dx[i]
		y = now[0] + dy[i]
		if 0 <= x < w and 0 <= y < h:
			if ss[y][x] == '.' and visited[y][x] == 0:
				visited[y][x] = visited[now[0]][now[1]] + 1
				queue.append([y, x])
			if x == w - 1 and y == h - 1:
				print(num - visited[y][x] - 1)
				return
print(-1)


(H, W) = map(int, input().split())
S = [input() for i in range(H)]
T = [[False] * W for i in range(H)]
Q = [(1, 0, 0)]
cnt = 0
while Q:
	q = Q.pop(0)
	if min(q) < 0 or q[1] >= H or q[2] >= W:
		continue
	if S[q[1]][q[2]] == '#' or T[q[1]][q[2]]:
		continue
	if q[1] == H - 1 and q[2] == W - 1:
		cnt = q[0]
		break
	T[q[1]][q[2]] = True
	Q.append((q[0] + 1, q[1] + 1, q[2]))
	Q.append((q[0] + 1, q[1] - 1, q[2]))
	Q.append((q[0] + 1, q[1], q[2] + 1))
	Q.append((q[0] + 1, q[1], q[2] - 1))
ans = 0
for s in S:
	ans += s.count('.')
print(ans - cnt if cnt else -1)


(n, m) = map(int, input().split())
cnt = 0
grid = [list(input()) for i in range(n)]
grid2 = [[]] * n
for i in range(n):
	cnt += ''.join(grid[i]).count('#')
	grid2[i] = ['#'] + grid[i] + ['#']
grid2.insert(0, ['#'] * (m + 2))
grid2.append(['#'] * (m + 2))
grid2[1][1] = 0
loc = [[1, 1]]
for k in range(1, n * m):
	next_loc = []
	for (y, x) in loc:
		for (i, j) in ([-1, 0], [1, 0], [0, -1], [0, 1]):
			if grid2[y + i][x + j] == '.':
				grid2[y + i][x + j] = k
				next_loc.append([y + i, x + j])
	loc = next_loc
	if [n, m] in loc:
		break
ans = n * m - (k + 1 + cnt)
print(ans if ans >= 0 else -1)


(H, W) = list(map(int, input().split()))
grid = [input() for _ in range(H)]
checked = [[False] * W for _ in range(H)]

def solve(arr, count):
	next_arr = set()
	count += 1
	for a in arr:
		(y, x) = (a[0], a[1])
		checked[y][x] = True
		if y == H - 1 and x == W - 1:
			return count
		if y < H - 1:
			if not checked[y + 1][x] and grid[y + 1][x] == '.':
				next_arr.add((y + 1, x))
		if 0 < y:
			if not checked[y - 1][x] and grid[y - 1][x] == '.':
				next_arr.add((y - 1, x))
		if x < W - 1:
			if not checked[y][x + 1] and grid[y][x + 1] == '.':
				next_arr.add((y, x + 1))
		if 0 < x:
			if not checked[y][x - 1] and grid[y][x - 1] == '.':
				next_arr.add((y, x - 1))
	if len(next_arr) == 0:
		return -1
	return solve(next_arr, count)
min_steps = solve([(0, 0)], 0)
if min_steps == -1:
	print(-1)
else:
	w_c = 0
	for i in grid:
		w_c += i.count('.')
	print(w_c - min_steps)


from collections import deque
(H, W) = map(int, input().split())
s = list((input() for i in range(H)))
board = [[1] * (W + 2) for i in range(H + 2)]
white = 0
for i in range(H):
	for j in range(W):
		if s[i][j] == '.':
			white += 1
			board[i + 1][j + 1] = 0
queue = deque([[1, 1]])
v = [[1, 0], [-1, 0], [0, -1], [0, 1]]
while queue != deque([]):
	(x, y) = queue.popleft()
	for (a, b) in v:
		if board[x + a][y + b] == 0:
			board[x + a][y + b] = board[x][y] + 1
			queue.append([x + a, y + b])
if board[H][W] != 0:
	print(white - board[H][W] - 1)
else:
	print(-1)


from collections import deque
(H, W) = list(map(int, input().split()))
L = [list(input()) for _ in range(H)]
s = sum((l.count('.') for l in L))
dd = [(0, 1), (0, -1), (1, 0), (-1, 0)]
res = None
que = deque([(0, 0, 0)])
used = {(0, 0)}
while que:
	(i, j, cost) = que.popleft()
	if i == H - 1 and j == W - 1:
		res = cost
		break
	for (di, dj) in dd:
		ni = i + di
		nj = j + dj
		if not 0 <= ni < H or not 0 <= nj < W or L[ni][nj] == '#' or ((ni, nj) in used):
			continue
		que.append((ni, nj, cost + 1))
		used.add((ni, nj))
if res:
	print(s - res - 1)
else:
	print(-1)


(h, w) = map(int, input().split())
field = [list(input()) for i in range(h)]
cnt = 0
for i in field:
	for j in i:
		if j == '#':
			cnt += 1
dp = [[0 for i in range(w)] for i in range(h)]
dydx = [[-1, 0], [1, 0], [0, -1], [0, 1]]
queue = []
queue.append([0, 0])
while queue:
	(ny, nx) = queue.pop(0)
	for (dy, dx) in dydx:
		(nny, nnx) = (ny + dy, nx + dx)
		if 0 <= nny <= h - 1 and 0 <= nnx <= w - 1 and (field[nny][nnx] != '#') and (dp[nny][nnx] == 0):
			dp[nny][nnx] = dp[ny][nx] + 1
			queue.append([nny, nnx])
			if nny == h - 1 and nnx == w - 1:
				print(h * w - cnt - dp[h - 1][w - 1] - 1)
				exit()
print(-1)


import sys
from collections import deque

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

def LSH(h):
	return [list(input()) for _ in range(h)]
(H, W) = LI()
MAP = LSH(H)
d = deque()
d.append([0, 0])
looked = [[0 for i in range(W)] for j in range(H)]
looked[0][0] = 1
move = [[1, 0], [0, 1], [-1, 0], [0, -1]]
while d:
	x = d.popleft()
	h = x[0]
	w = x[1]
	for i in move:
		a = h + i[0]
		b = w + i[1]
		if not 0 <= a < H or not 0 <= b < W or looked[a][b] != 0 or (MAP[a][b] == '#'):
			continue
		d.append([a, b])
		looked[a][b] = looked[h][w] + 1
if looked[H - 1][W - 1] == 0:
	print(-1)
	return
white = 0
for i in range(H):
	for j in range(W):
		if MAP[i][j] == '.':
			white += 1
print(white - looked[H - 1][W - 1])


from collections import deque
(h, w) = map(int, input().split())
chiz = [[] for _ in range(w)]
cnt = 0
for _ in range(h):
	tmp_list = input()
	for i in range(w):
		if tmp_list[i] == '.':
			cnt += 1
		chiz[i].append(tmp_list[i])
dq = deque([(0, 0)])
chiz[0][0] = 0
while dq:
	(i, j) = dq.popleft()
	for e in [(1, 0), (-1, 0), (0, -1), (0, 1)]:
		if i + e[0] >= 0 and i + e[0] < w and (j + e[1] >= 0) and (j + e[1] < h):
			if chiz[i + e[0]][j + e[1]] == '.':
				chiz[i + e[0]][j + e[1]] = chiz[i][j] + 1
				dq.append((i + e[0], j + e[1]))
try:
	print(cnt - chiz[w - 1][h - 1] - 1)
except:
	print(-1)


(H, W) = map(int, input().split())
inf = 101
s = [''] * H
cnt = 0
for i in range(H):
	s[i] = input()
	cnt += s[i].count('.')
d = [[inf] * W for i in range(H)]
from collections import deque
queue = deque([[0, 0]])
d[0][0] = 0
while queue:
	(x, y) = queue.popleft()
	if x + 1 == H and y + 1 == W:
		break
	(dx, dy) = ([-1, 0, 1, 0], [0, -1, 0, 1])
	for i in range(4):
		(nx, ny) = (x + dx[i], y + dy[i])
		if 0 <= nx and nx < H and (0 <= ny) and (ny < W) and (s[nx][ny] != '#') and (d[nx][ny] == inf):
			queue.append([nx, ny])
			d[nx][ny] = d[x][y] + 1
if d[H - 1][W - 1] == inf:
	print(-1)
else:
	print(cnt - d[H - 1][W - 1] - 1)


class Queue:

	def __init__(self, data=[]):
		self.data = data

	def enqueue(self, x):
		self.data.append(x)
		return self.data

	def dequeue(self):
		if len(self.data) == 0:
			return 'Queue is Empty!'
		else:
			cell = self.data[0]
			del self.data[0]
			return self.data
(H, W) = list(map(int, input().split()))
s = [list(input()) for i in range(H)]
dy = [-1, 0, 1, 0]
dx = [0, 1, 0, -1]
min_dis = [[False for i in range(W)] for j in range(H)]
min_dis[0][0] = 1
Q = Queue()
Q.enqueue([0, 0])
while Q.data:
	y = Q.data[0][0]
	x = Q.data[0][1]
	for (i, j) in zip(dy, dx):
		if 0 <= y + i < H and 0 <= x + j < W and (s[y + i][x + j] == '.'):
			if min_dis[y + i][x + j] == False:
				min_dis[y + i][x + j] = min_dis[y][x] + 1
				Q.enqueue([y + i, x + j])
	Q.dequeue()
if not min_dis[H - 1][W - 1]:
	print(-1)
	return
num_shap = 0
for i in range(H):
	for j in range(W):
		if s[i][j] == '#':
			num_shap += 1
score = H * W - num_shap - min_dis[H - 1][W - 1]
print(score)


from collections import deque
from collections import Counter
(H, W) = map(int, input().split())
s = [list(input()) for _ in range(H)]
t = [[-1] * W for _ in range(H)]
q = deque([[0, 0]])
t[0][0] = 0
while len(q) > 0:
	qq = q.popleft()
	dh = [-1, 0, 1, 0]
	dw = [0, 1, 0, -1]
	for i in range(4):
		h = qq[0] + dh[i]
		w = qq[1] + dw[i]
		if 0 <= h < H and 0 <= w < W:
			if s[h][w] == '#' or t[h][w] != -1:
				continue
			t[h][w] = t[qq[0]][qq[1]] + 1
			q.append([h, w])
X = 0
for i in range(H):
	c = Counter(s[i])
	X += c['.']
if t[H - 1][W - 1] == -1:
	print(-1)
else:
	print(X - 1 - t[H - 1][W - 1])


from collections import deque
(h, w) = map(int, input().split())
maze = [['#'] * (w + 2) for i in range(h + 2)]
wall = 0
for i in range(1, h + 1):
	s = input()
	for j in range(1, w + 1):
		if s[j - 1] == '#':
			wall += 1
		maze[i][j] = s[j - 1]
queue = deque([[1, 1]])
maze[1][1] = 0
while queue:
	(x, y) = queue.popleft()
	if [x, y] != [h, w]:
		for (n, m) in ([0, -1], [0, 1], [-1, 0], [1, 0]):
			(new_h, new_w) = (x + n, y + m)
			if maze[new_h][new_w] == '.':
				maze[new_h][new_w] = maze[x][y] + 1
				queue.append([new_h, new_w])
			elif maze[new_h][new_w] != '#':
				maze[new_h][new_w] = min(maze[new_h][new_w], maze[x][y] + 1)
			else:
				pass
if maze[h][w] == '.' or maze[h][w] == '#':
	print(-1)
else:
	print(h * w - (maze[h][w] + 1) - wall)


(H, W) = map(int, input().split())
G = [input() for _ in range(H)]
(sy, sx, gy, gx) = (0, 0, H - 1, W - 1)
seen = [[-1] * W for _ in range(H)]
if G[sy][sx] == '#' or G[gy][gx] == '#':
	print(-1)
	return
from collections import deque
que = deque()
que.append([sy, sx])
seen[sy][sx] = 0
while que:
	(y, x) = que.popleft()
	for d in ([-1, 0], [1, 0], [0, -1], [0, 1]):
		dy = y + d[0]
		dx = x + d[1]
		if dy < 0 or H <= dy or dx < 0 or (W <= dx):
			continue
		if G[dy][dx] == '#':
			continue
		if seen[dy][dx] > -1:
			continue
		que.append([dy, dx])
		seen[dy][dx] = seen[y][x] + 1
count = 0
bunpu = [0] * (H * W + 1)
if seen[gy][gx] == -1:
	print(-1)
	return
else:
	all = H * W
	black = 0
	for i in range(H):
		for j in range(W):
			if G[i][j] == '#':
				black += 1
	ans = all - black - seen[gy][gx] - 1
print(ans)


from collections import deque
from typing import List

def main():
	(h, w) = list(map(int, input().split()))
	g = []
	for _ in range(h):
		gg = list(input())
		g.append(gg)
	print(gr(h, w, g))

def gr(h: int, w: int, g: List[List[str]]) -> int:
	m = [[-1] * w for _ in range(h)]
	q = deque([(0, 0)])
	m[0][0] = 0
	while q:
		(x, y) = q.popleft()
		for (nx, ny) in [(x + 1, y), (x, y + 1), (x - 1, y), (x, y - 1)]:
			if (0 <= nx <= w - 1 and 0 <= ny <= h - 1) and g[ny][nx] == '.' and (m[ny][nx] < 0):
				m[ny][nx] = m[y][x] + 1
				if nx == w - 1 and ny == h - 1:
					break
				q.append((nx, ny))
	if m[h - 1][w - 1] < 0:
		return -1
	return sum((gg.count('.') for gg in g)) - m[h - 1][w - 1] - 1

def __starting_point():
	main()
__starting_point()


from collections import deque
(h, w) = [int(x) for x in input().split()]
c = []
b = 0
for i in range(h):
	C = input()
	b += C.count('#')
	c.append(C)
dist = [[0] * w for i in range(h)]
dist[0][0] = 1
d = deque()
d.append([0, 0])
dydx = [[1, 0], [0, 1], [-1, 0], [0, -1]]
while d:
	(y, x) = d.popleft()
	if y == h - 1 and x == w - 1:
		break
	for i in range(4):
		(ny, nx) = (y + dydx[i][0], x + dydx[i][1])
		if not 0 <= ny < h or not 0 <= nx < w or dist[ny][nx] != 0 or (c[ny][nx] == '#'):
			continue
		dist[ny][nx] = dist[y][x] + 1
		d.append([ny, nx])
if dist[h - 1][w - 1] == 0:
	print(-1)
else:
	ans = h * w - b - dist[h - 1][w - 1]
	print(ans)


(h, w) = map(int, input().split())
s = [input() for _ in range(h)]
dist = [[-1] * w for _ in range(h)]
dist[0][0] = 0
que = [(0, 0)]
move = [(0, 1), (0, -1), (1, 0), (-1, 0)]
n_white = 0
for i in range(h):
	n_white += s[i].count('.')
while que != []:
	(x, y) = que.pop(0)
	for m in move:
		nx = x + m[0]
		ny = y + m[1]
		if 0 <= nx < h and 0 <= ny < w:
			if dist[nx][ny] != -1:
				continue
			if s[nx][ny] == '.':
				dist[nx][ny] = dist[x][y] + 1
				que.append((nx, ny))
distance = dist[-1][-1]
if distance == -1:
	print(-1)
else:
	print(n_white - distance - 1)


from queue import Queue
(H, W) = map(int, input().split())
s = [list(input()) for _ in range(H)]
white = sum([1 if s[y][x] == '.' else 0 for x in range(W) for y in range(H)])
used = [[False for x in range(W)] for y in range(H)]
q = Queue()
q.put((0, 0, 1))
while True:
	if q.empty():
		print(-1)
		break
	(x, y, l) = q.get()
	if used[y][x]:
		continue
	if x == W - 1 and y == H - 1:
		print(white - l)
		break
	used[y][x] = True
	for d in [(1, 0), (0, 1), (-1, 0), (0, -1)]:
		nx = x + d[0]
		ny = y + d[1]
		if ny >= 0 and ny < H and (nx >= 0) and (nx < W):
			if s[ny][nx] == '.':
				q.put((nx, ny, l + 1))


from queue import deque
(H, W) = map(int, input().split())
matrix = []
count = 0
for i in range(H):
	matrix.append(list(input()))
	count += matrix[-1].count('.')
que = deque([(0, 0, 1)])
visited = set()
while que:
	(row, col, depth) = que.popleft()
	if not (0 <= row < H and 0 <= col < W) or matrix[row][col] == '#':
		continue
	if (row, col) in visited:
		continue
	visited.add((row, col))
	if (row, col) == (H - 1, W - 1):
		print(count - depth)
		exit()
	for (ud, lr) in ((-1, 0), (1, 0), (0, -1), (0, 1)):
		que.append((row + ud, col + lr, depth + 1))
print(-1)


(H, W) = map(int, input().split())
G = [list(input()) for _ in range(H)]
que = [[0, 0]]
dist = [[-1] * W for _ in range(H)]
direction = [[0, 1], [0, -1], [1, 0], [-1, 0]]
dist[0][0] = 0
while que:
	(h, w) = que.pop(0)
	for (dh, dw) in direction:
		if h + dh < 0 or h + dh >= H or w + dw < 0 or (w + dw >= W):
			continue
		if G[h + dh][w + dw] == '#':
			continue
		if dist[h + dh][w + dw] != -1:
			continue
		dist[h + dh][w + dw] = dist[h][w] + 1
		que.append([h + dh, w + dw])
if dist[H - 1][W - 1] == -1:
	print(-1)
else:
	num = 0
	for i in range(H):
		num += G[i].count('#')
	print(H * W - num - dist[H - 1][W - 1] - 1)


import sys
readline = sys.stdin.readline
(H, W) = map(int, readline().split())
G = [None] * H
white = 0
for i in range(H):
	G[i] = readline().rstrip()
	white += G[i].count('.')
from collections import deque
q = deque([])
q.append([0, 0, 0])
seen = set()
cases = ((0, 1), (0, -1), (1, 0), (-1, 0))
while q:
	(y, x, d) = q.popleft()
	if G[y][x] == '#':
		continue
	if (y, x) in seen:
		continue
	seen.add((y, x))
	if y == H - 1 and x == W - 1:
		print(white - d - 1)
		break
	for c in cases:
		if 0 <= y + c[0] < H and 0 <= x + c[1] < W:
			q.append([y + c[0], x + c[1], d + 1])
else:
	print(-1)


(h, w) = map(int, input().split())
g = [input() for _ in range(h)]
d = [[-1] * w for _ in range(h)]
d[0][0] = 0
q = [(0, 0)]
while q:
	(tx, ty) = q.pop(0)
	for (dx, dy) in [(1, 0), (0, 1), (-1, 0), (0, -1)]:
		(nx, ny) = (tx + dx, ty + dy)
		if 0 <= nx < h and 0 <= ny < w and (g[nx][ny] == '.') and (d[nx][ny] < 0):
			d[nx][ny] = d[tx][ty] + 1
			q += [(nx, ny)]
print((sum((s.count('.') for s in g)) - d[-1][-1]) * (d[-1][-1] > 0) - 1)


from collections import deque
(H, W) = map(int, input().split())
l = [str(input()) for _ in range(H)]
white_count = 0
for s in l:
	white_count += s.count('.')
sy = 0
sx = 0
gy = H - 1
gx = W - 1
visited = [[-1] * W for _ in range(H)]
visited[sy][sx] = 0
Q = deque([[sy, sx]])
while Q:
	(y, x) = Q.popleft()
	if [y, x] == [gy, gx]:
		print(white_count - visited[y][x] - 1)
		exit()
	for (i, j) in [(1, 0), (0, 1), (-1, 0), (0, -1)]:
		if 0 <= x + j < W and 0 <= y + i < H and (visited[y + i][x + j] == -1) and (l[y + i][x + j] == '.'):
			visited[y + i][x + j] = visited[y][x] + 1
			Q.append([y + i, x + j])
		else:
			continue
print(-1)


DIR = [(1, 0), (-1, 0), (0, 1), (0, -1)]
(H, W) = [int(x) for x in input().split()]
G = []
B = 0
G.append('#' * (W + 2))
for i in range(H):
	s = input()
	B += s.count('.')
	G.append(['#'] + list(s) + ['#'])
G.append('#' * (W + 2))
que = [(1, 1, 1)]
ans = -1
while que:
	(y, x, c) = que.pop(0)
	if (y, x) == (H, W):
		ans = c
		break
	for dir in DIR:
		ny = y + dir[0]
		nx = x + dir[1]
		if G[ny][nx] == '.':
			G[ny][nx] = '#'
			que.append((ny, nx, c + 1))
print(B - ans if ans != -1 else -1)


import queue
(H, W) = map(int, input().split())
(c, b) = ([], 0)
for i in [0] * H:
	c.append(input())
	b += c[-1].count('#')
vis = [[0] * W for _ in [0] * H]
q = queue.Queue()
q.put((0, 0, 1))
res = -1
while not q.empty():
	(x, y, d) = q.get()
	for (dx, dy) in [(1, 0), (0, 1), (-1, 0), (0, -1)]:
		(nx, ny) = (x + dx, y + dy)
		if (nx, ny) == (W - 1, H - 1):
			res = H * W - (d + 1) - b
		if 0 <= nx <= W - 1 and 0 <= ny <= H - 1:
			if not vis[ny][nx] and c[ny][nx] == '.':
				q.put((nx, ny, d + 1))
				vis[ny][nx] = 1
		if res > -1:
			break
	if res > -1:
		break
print(res)


def main():
	(H, W) = [int(n) for n in input().split(' ')]
	iniBlack = 0
	S = []
	S.append(['X'] * (W + 2))
	for i in range(H):
		row = list(input())
		iniBlack += row.count('#')
		S.append(['X'] + row + ['X'])
	S.append(['X'] * (W + 2))
	to_visit = [{'row': 1, 'col': 1, 'step': 1}]
	checked = [[0] * (W + 2) for i in range(H + 2)]
	checked[1][1] = 1
	while len(to_visit) > 0:
		visiting = to_visit.pop(0)
		r0 = visiting['row']
		c0 = visiting['col']
		s0 = visiting['step']
		for d in [[0, 1], [0, -1], [1, 0], [-1, 0]]:
			r = r0 + d[0]
			c = c0 + d[1]
			if S[r][c] == '.' and checked[r][c] == 0:
				to_visit.append({'row': r, 'col': c, 'step': s0 + 1})
				checked[r][c] = s0 + 1
	if checked[H][W] == 0:
		print(-1)
		return 0
	print(H * W - iniBlack - checked[H][W])
main()


(h, w) = map(int, input().split())
s = [list(input()) for _ in range(h)]
black = 0
for i in range(h):
	black += s[i].count('#')
from collections import deque
que = deque()
que.append([0, 0])
s[0][0] = '#'
count = [[0] * w for _ in range(h)]
while que:
	x = que.pop()
	dx_dy = [[0, 1], [1, 0], [0, -1], [-1, 0]]
	for k in range(4):
		nx = x[0] + dx_dy[k][0]
		ny = x[1] + dx_dy[k][1]
		if 0 <= nx <= h - 1 and 0 <= ny <= w - 1 and (s[nx][ny] == '.'):
			s[nx][ny] = '#'
			count[nx][ny] = count[x[0]][x[1]] + 1
			que.appendleft([nx, ny])
if s[-1][-1] == '#':
	print(h * w - count[-1][-1] - black - 1)
else:
	print(-1)


(h, w) = map(int, input().split())
g = [input() for _ in range(h)]
from collections import *
d = [[-1] * w for _ in range(h)]
d[0][0] = 0
q = deque([(0, 0)])
while q:
	(tx, ty) = q.popleft()
	for (dx, dy) in [(-1, 0), (1, 0), (0, -1), (0, 1)]:
		(nx, ny) = (tx + dx, ty + dy)
		if 0 <= nx < h and 0 <= ny < w and (g[nx][ny] == '.') and (d[nx][ny] < 0):
			d[nx][ny] = d[tx][ty] + 1
			q.append((nx, ny))
if d[-1][-1] < 0:
	print(-1)
	exit()
else:
	print(sum([s.count('.') for s in g]) - d[-1][-1] - 1)


(H, W) = map(int, input().split())
S = []
S.append(list(['X'] * (W + 2)))
for h in range(H):
	S.append(['X'] + list(input()) + ['X'])
S.append(list(['X'] * (W + 2)))
from collections import deque
q = deque([[1, 1]])
d = [(1, 0), (-1, 0), (0, 1), (0, -1)]
S[1][1] = 0
cnt_nm = 0
for h in range(H + 2):
	for w in range(W + 2):
		if S[h][w] == '#':
			cnt_nm += 1
while q:
	(y, x) = q.popleft()
	for (dy, dx) in d:
		if S[y + dy][x + dx] == '.':
			q.append([y + dy, x + dx])
			S[y + dy][x + dx] = S[y][x] + 1
if S[H][W] == '.':
	print('-1')
else:
	print(H * W - cnt_nm - S[H][W] - 1)


import sys
sys.setrecursionlimit(10 ** 6)
(H, W) = map(int, input().split())
S = []
initB = 0
for i in range(H):
	s = [0 if j == '.' else 1 if j == '#' else None for j in input()]
	initB += sum(s)
	S.append(s)
from collections import deque
que = deque([(0, 0)])
di = [-1, 1, 0, 0]
dj = [0, 0, -1, 1]
S[0][0] = 1
while que:
	(h, w) = que.popleft()
	for (i, j) in zip(di, dj):
		if 0 <= h + i < H and 0 <= w + j < W and (S[h + i][w + j] == 0):
			S[h + i][w + j] = S[h][w] + 1
			que.append((h + i, w + j))
if S[H - 1][W - 1] < 2:
	print(-1)
else:
	print(H * W - S[H - 1][W - 1] - initB)


(h, w) = map(int, input().split())
s = [list('#' * (w + 2))]
queue = [[1, 1, 1]]
dot = 0
for i in range(h):
	s.append(['#'] + list(input()) + ['#'])
	dot += s[-1].count('.')
s.append(list('#' * (w + 2)))

def move(yxc):
	(y, x, cost) = (yxc[0], yxc[1], yxc[2])
	global queue
	for (dy, dx) in ([1, 0], [-1, 0], [0, 1], [0, -1]):
		(ny, nx) = (y + dy, x + dx)
		if s[ny][nx] == '.':
			s[ny][nx] = cost + 1
			queue.append([ny, nx, cost + 1])
while len(queue) > 0:
	move(queue.pop(0))
s[1][1] = 1
move([1, 1, 1])
if s[h][w] == '.':
	print(-1)
else:
	print(dot - s[h][w])


from collections import deque
(h, w) = map(int, input().split())
m = ['#' * (w + 2)] + ['#' + input() + '#' for i in range(h)] + ['#' * (w + 2)]
temp = [[-1] * (w + 2) for i in range(h + 2)]
(sy, sx) = (1, 1)
temp[sy][sx] = 0
opt = [(1, 0), (0, 1), (-1, 0), (0, -1)]
dq = deque([(sy, sx)])
while dq:
	(y, x) = dq.popleft()
	for i in opt:
		y1 = y + i[0]
		x1 = x + i[1]
		if m[y1][x1] == '.' and temp[y1][x1] == -1:
			temp[y1][x1] = temp[y][x] + 1
			dq.append((y1, x1))
cnt = 0
for i in m:
	cnt += i.count('#')
if temp[h][w] == -1:
	print(-1)
else:
	print((h + 2) * (w + 2) - cnt - temp[h][w] - 1)


from collections import deque

def main():
	(H, W) = list(map(int, input().split()))
	field = [list(input().rstrip()) for _ in range(H)]
	black = 0
	for f in field:
		for s in f:
			if s == '#':
				black += 1
	dir_h = [0, 0, 1, -1]
	dir_w = [1, -1, 0, 0]
	print(H * W - black - bfs(H, W, field, dir_h, dir_w))

def bfs(H, W, field, dir_h, dir_w):
	q = deque([])
	seen = [[-1 for _ in range(W)] for _ in range(H)]
	q.append([0, 0])
	seen[0][0] = 1
	while q:
		(h, w) = q.popleft()
		for (dh, dw) in zip(dir_h, dir_w):
			(nh, nw) = (h + dh, w + dw)
			if nh < 0 or nh >= H or nw < 0 or (nw >= W):
				continue
			elif field[nh][nw] == '#':
				continue
			elif seen[nh][nw] != -1:
				continue
			seen[nh][nw] = seen[h][w] + 1
			q.append([nh, nw])
	if seen[H - 1][W - 1] == -1:
		print(-1)
		return
	return seen[H - 1][W - 1]

def __starting_point():
	main()
__starting_point()


from collections import deque
(h, w) = map(int, input().split())
m = ['#' * (w + 2)] + ['#' + input() + '#' for _ in range(h)] + ['#' * (w + 2)]
cnt = 0
for hi in range(1, h + 1):
	for wi in range(1, w + 1):
		if m[hi][wi] == '.':
			cnt += 1
inf = 10 ** 9
d = [[inf] * (w + 2) for _ in range(h + 2)]
q = deque([(1, 1, 1)])
d[1][1] = 1
while len(q):
	(ch, cw, r) = q.popleft()
	for (hi, wi) in [[ch + 1, cw], [ch, cw + 1], [ch - 1, cw], [ch, cw - 1]]:
		if m[hi][wi] == '.' and d[hi][wi] > r + 1:
			d[hi][wi] = r + 1
			q.append((hi, wi, r + 1))
if d[h][w] == inf:
	print(-1)
else:
	print(cnt - d[h][w])


from collections import deque
(H, W) = map(int, input().split())
S = []
wall = 0
for i in range(H):
	s = list(input())
	wall += s.count('#')
	S.append(s)
q = deque()
q.append([0, 0, 0])
S[0][0] = '#'
while q:
	(y, x, cnt) = q.popleft()
	if y == H - 1 and x == W - 1:
		break
	for (dy, dx) in [[1, 0], [-1, 0], [0, 1], [0, -1]]:
		if 0 <= y + dy < H and 0 <= x + dx < W and (S[y + dy][x + dx] == '.'):
			q.append([y + dy, x + dx, cnt + 1])
			S[y + dy][x + dx] = '#'
if S[H - 1][W - 1] == '.':
	print(-1)
else:
	score = H * W - (cnt + 1) - wall
	print(score)


(h, w) = map(int, input().split())
maze = [list(input()) for _ in range(h)]
dx = [1, 0, -1, 0]
dy = [0, 1, 0, -1]
queue = []
ans = 0
cn = 0
for i in maze:
	cn += i.count('#')
queue.append([0, 0, 0])
while len(queue) > 0:
	(x, y, cnt) = queue.pop(0)
	ans = cnt
	if x == h - 1 and y == w - 1:
		print(h * w - ans - cn - 1)
		exit()
	for i in range(4):
		X = x + dx[i]
		Y = y + dy[i]
		if not (0 <= X < h and 0 <= Y < w):
			continue
		if maze[X][Y] == '#':
			continue
		if maze[X][Y] == '.':
			queue.append([X, Y, cnt + 1])
			maze[X][Y] = '#'
print(-1)


import sys
sys.setrecursionlimit(1000000)
from collections import deque
(H, W) = list(map(int, input().split()))
s = [list(input()) for _ in range(H)]
dist = [[-1 for _ in range(W)] for _ in range(H)]

def bfs():
	que = deque()
	que.append((0, 0))
	dist[0][0] = 0
	offset = ((1, 0), (-1, 0), (0, 1), (0, -1))
	while que:
		(now_h, now_w) = que.popleft()
		if now_h < 0 or H - 1 < now_h or now_w < 0 or (W - 1 < now_w):
			continue
		if s[now_h][now_w] == '#':
			continue
		for (oh, ow) in offset:
			if now_h + oh < 0 or H - 1 < now_h + oh or now_w + ow < 0 or (W - 1 < now_w + ow):
				continue
			if dist[now_h + oh][now_w + ow] != -1:
				continue
			else:
				dist[now_h + oh][now_w + ow] = dist[now_h][now_w] + 1
				que.append((now_h + oh, now_w + ow))
bfs()
m = dist[H - 1][W - 1]
if m == -1:
	print(-1)
else:
	count = 0
	for t in s:
		count += t.count('.')
	print(count - m - 1)


from collections import deque
(H, W) = map(int, input().split())
con = [[1, 0], [0, 1], [-1, 0], [0, -1]]
m = []
c = 0
d = [[0] * (W + 2) for _ in range(H + 2)]
d[1][1] = 1
m.append('#' * (W + 2))
for i in range(H):
	b = input()
	c += b.count('.')
	a = '#' + b + '#'
	m.append(a)
q = deque()
m.append('#' * (W + 2))
q.append((1, 1))
while len(q) > 0:
	(y, x) = q.popleft()
	if y == H and x == W:
		print(c - d[H][W])
		exit()
	for (dx, dy) in con:
		if d[y + dy][x + dx] == 0 and m[y + dy][x + dx] == '.':
			q.append((y + dy, x + dx))
			d[y + dy][x + dx] += d[y][x] + 1
print(-1)


import sys
import queue
(H, W) = map(int, input().split())
white = 0
maze = [['#'] * (W + 2)]
for y in range(H):
	li = list(input())
	white += li.count('.')
	maze.append(['#'] + li + ['#'])
maze.append(['#'] * (W + 2))

def check(x, y, n):
	if 1 <= x < W + 1 and 1 <= y < H + 1:
		if x == W and y == H:
			print(white - n - 1)
			sys.exit()
		elif maze[y][x] == '.':
			maze[y][x] = n
			q.put([x - 1, y, n + 1])
			q.put([x + 1, y, n + 1])
			q.put([x, y - 1, n + 1])
			q.put([x, y + 1, n + 1])
		else:
			return
	else:
		return
q = queue.Queue()
q.put([1, 1, 0])
while not q.empty():
	(x, y, n) = q.get()
	check(x, y, n)
print(-1)


(h, w) = list(map(int, input().split()))
matrix = [list('#' * (w + 2))]
count_sharp = 0
for _ in range(h):
	C = list(input())
	count_sharp += C.count('#')
	matrix.append(['#'] + C + ['#'])
matrix.append(list('#') * (w + 2))
B = [[] for _ in range(10000)]
for i in range(h + 2):
	for j in range(w + 2):
		if matrix[i][j] == '.':
			if matrix[i - 1][j] == '.':
				B[100 * i + j].append(100 * (i - 1) + j)
			if matrix[i][j - 1] == '.':
				B[100 * i + j].append(100 * i + j - 1)
			if matrix[i][j + 1] == '.':
				B[100 * i + j].append(100 * i + j + 1)
			if matrix[i + 1][j] == '.':
				B[100 * i + j].append(100 * (i + 1) + j)

def solver(matrix, h, w, count_):
	path = [10000000] * 10000
	depth = 0
	path[101] = 0
	reached = [101]
	stack = []
	stack.append(101)
	while len(stack) > 0:
		depth += 1
		for _ in range(len(stack)):
			val = stack.pop(0)
			for j in matrix[val]:
				if j not in set(reached):
					path[j] = min(depth, path[j])
					reached.append(j)
					stack.append(j)
	if path[h * 100 + w] == 10000000:
		print(-1)
	else:
		print(h * w - path[h * 100 + w] - 1 - count_)
solver(B, h, w, count_sharp)


(H, W) = list(map(int, input().split()))
maze = []
s_init_cnt = 0
for i in range(H):
	gyo = list(input())
	s_init_cnt += gyo.count('.')
	maze.append(gyo)
direction = [(-1, 0), (0, -1), (1, 0), (0, 1)]
reached = [[-1] * W for i in range(H)]
reached[0][0] = 1
from collections import deque

def bfs():
	d = deque([[0, 0]])
	while len(d) > 0:
		(px, py) = d.popleft()
		for (dx, dy) in direction:
			tx = px + dx
			ty = py + dy
			if tx >= H or ty >= W or tx < 0 or (ty < 0):
				continue
			if reached[tx][ty] != -1 or maze[tx][ty] == '#':
				continue
			else:
				reached[tx][ty] = reached[px][py] + 1
				d.append([tx, ty])
bfs()
ans = reached[H - 1][W - 1]
if ans == -1:
	print(ans)
else:
	ans = s_init_cnt - ans
	print(ans)


from collections import *
(h, w) = map(int, input().split())
a = [input() for _ in range(h)]
b = [[h * w] * w for _ in range(h)]
b[0][0] = 1
d = deque([[0, 0]])
while d:
	(y, x) = d.popleft()
	for (i, j) in ([1, 0], [-1, 0], [0, 1], [0, -1]):
		(t, u) = (y + i, x + j)
		if h > t >= 0 <= u < w:
			if a[t][u] == '.' and b[t][u] > b[y][x] + 1:
				d.append([t, u])
				b[t][u] = b[y][x] + 1
print(max(-1, sum([i.count('.') for i in a]) - b[-1][-1]))


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


def getval():
	(h, w) = map(int, input().split())
	s = [input() for i in range(h)]
	return (h, w, s)

def main(h, w, s):
	whites = 0
	for i in s:
		for j in range(w):
			if i[j] == '.':
				whites += 1
	d = [[-1 for i in range(w)] for j in range(h)]
	q = [[0, 0, 0]]
	d[0][0] = 0
	while q:
		idx = q.pop(0)
		adj = [[idx[0] + 1, idx[1], idx[2] + 1], [idx[0] - 1, idx[1], idx[2] + 1], [idx[0], idx[1] + 1, idx[2] + 1], [idx[0], idx[1] - 1, idx[2] + 1]]
		for i in adj:
			if i[0] < 0 or i[1] < 0 or i[0] >= h or (i[1] >= w):
				continue
			if d[i[0]][i[1]] != -1:
				continue
			if s[i[0]][i[1]] == '#':
				continue
			q.append(i)
			d[i[0]][i[1]] = i[2]
	dist = d[h - 1][w - 1]
	if dist == -1:
		print(-1)
	else:
		print(whites - dist - 1)

def __starting_point():
	(h, w, s) = getval()
	main(h, w, s)
__starting_point()


from queue import Queue
(h, w) = map(int, input().split())
S = [list(input()) for _ in range(h)]
memo = [[-1] * w for _ in range(h)]

def bfs(q):
	(x, y, cnt) = q.get()
	if x < 0 or x >= w or y < 0 or (y >= h):
		return
	elif S[y][x] == '#':
		return
	elif memo[y][x] < 0:
		memo[y][x] = cnt
		q.put([x - 1, y, cnt + 1])
		q.put([x + 1, y, cnt + 1])
		q.put([x, y - 1, cnt + 1])
		q.put([x, y + 1, cnt + 1])
q = Queue()
q.put([0, 0, 0])
while not q.empty():
	bfs(q)
if memo[h - 1][w - 1] == -1:
	print(-1)
	exit()
cnt = 0
for i in range(h):
	cnt += S[i].count('.')
print(cnt - memo[h - 1][w - 1] - 1)


(h, w) = map(int, input().split())
a = []
for i in range(h):
	a.append(list(input()))
white = [flatten for inner in a for flatten in inner].count('.')
turn = 1
a[-1][-1] = 1
while turn in [flatten for inner in a for flatten in inner]:
	for i in range(h):
		for j in range(w):
			if a[i][j] == turn:
				if i > 0 and a[i - 1][j] == '.':
					a[i - 1][j] = turn + 1
				if i < h - 1 and a[i + 1][j] == '.':
					a[i + 1][j] = turn + 1
				if j > 0 and a[i][j - 1] == '.':
					a[i][j - 1] = turn + 1
				if j < w - 1 and a[i][j + 1] == '.':
					a[i][j + 1] = turn + 1
	turn += 1
	if a[0][0] != '.':
		break
print(-1 if a[0][0] == '.' else white - a[0][0])


from collections import deque
(H, W) = map(int, input().split())
s = [['#'] * (W + 2) for _ in range(H + 2)]
count = 0
for i in range(1, H + 1):
	S = list(input())
	s[i] = ['#'] + S + ['#']
	count += S.count('.')
move = [(1, 0), (-1, 0), (0, 1), (0, -1)]
que = deque([(1, 1)])
s[1][1] = 1
while que:
	(a, b) = que.popleft()
	if (a, b) == (H, W):
		break
	for (my, mx) in move:
		ny = my + a
		nx = mx + b
		if s[ny][nx] == '#':
			continue
		elif s[ny][nx] == '.':
			que.append((ny, nx))
			s[ny][nx] = s[a][b] + 1
ans = -1
if s[H][W] != '.':
	ans = count - s[H][W]
print(ans)


from collections import deque
(H, W) = map(int, input().split())
S = [input() for _ in range(H)]
white = sum((s.count('.') for s in S))
visited = [[-1] * W for _ in range(H)]
deq = deque([(0, 0)])
visited[0][0] = 1
dia = [1, 0, -1, 0, 1]
while deq:
	(i, j) = deq.popleft()
	if i == H - 1 and j == W - 1:
		break
	d = visited[i][j]
	for (x, y) in zip(dia, dia[1:]):
		(ii, jj) = (i + x, j + y)
		if 0 <= ii < H and 0 <= jj < W and (S[ii][jj] == '.') and (visited[ii][jj] < 0):
			visited[ii][jj] = d + 1
			deq.append((ii, jj))
print(white - visited[H - 1][W - 1] if visited[H - 1][W - 1] > 0 else -1)


from collections import deque
(H, W) = map(int, input().split())
M = [input() for _ in range(H)]
dist = 0
visited = [[False] * W for _ in range(H)]
q = deque([(0, 0, 0)])
visited[0][0] = True
while q:
	(x, y, dist) = q.popleft()
	for i in range(4):
		(nx, ny) = (x + [-1, 0, 1, 0][i], y + [0, -1, 0, 1][i])
		if 0 <= nx and nx < W and (0 <= ny) and (ny < H) and (M[ny][nx] == '.') and (not visited[ny][nx]):
			q.append((nx, ny, dist + 1))
			visited[ny][nx] = True
	if x == W - 1 and y == H - 1:
		c = 0
		for m in M:
			c += m.count('.')
		print(c - dist - 1)
		exit()
print(-1)


from collections import deque
(h, w) = map(int, input().split())
maze = {(i, j): c for i in range(h) for (j, c) in enumerate(input())}
blacks = sum((c == '#' for c in maze.values()))

def bfs(i, j):
	dq = deque()
	dq.appendleft((1, (i, j)))
	while dq:
		(steps, (i, j)) = dq.pop()
		if (i, j) == (h - 1, w - 1):
			return steps
		if maze.get((i, j), '#') == '#':
			continue
		maze[i, j] = '#'
		dirs = ((-1, 0), (1, 0), (0, 1), (0, -1))
		dq.extendleft(((steps + 1, (i + di, j + dj)) for (di, dj) in dirs))
res = bfs(0, 0)
print(-1 if res is None else h * w - res - blacks)


from collections import deque
(H, W) = map(int, input().split())
S = []
w = 0
for i in range(H):
	s = input()
	w += s.count('.')
	S.append(list(s))
Q = deque([(0, 0, 0)])
ans = float('inf')
flag = False
while Q:
	(i, j, n) = Q.popleft()
	if i == H - 1 and j == W - 1:
		flag = True
		ans = min(ans, n)
	if S[i][j] == '.':
		S[i][j] = '#'
		for (dx, dy) in [(1, 0), (0, 1), (-1, 0), (0, -1)]:
			if 0 <= i + dx < H and 0 <= j + dy < W:
				Q.append((i + dx, j + dy, n + 1))
if flag:
	print(w - 2 - (ans - 1))
else:
	print(-1)


(h, w) = map(int, input().split())
maze = [list(input()) for i in range(h)]
distance = [[-1] * w for i in range(h)]
cnt = 0
for i in maze:
	cnt += i.count('#')
Q = [[0, 0]]
distance[0][0] = 1
ans = -1
while Q:
	p = Q.pop(0)
	if p[0] == h - 1 and p[1] == w - 1:
		ans = h * w - cnt - distance[h - 1][w - 1]
		break
	dx = [1, -1, 0, 0]
	dy = [0, 0, 1, -1]
	for i in range(4):
		nx = p[0] + dx[i]
		ny = p[1] + dy[i]
		if 0 <= nx < h and 0 <= ny < w and (distance[nx][ny] == -1) and (maze[nx][ny] != '#'):
			Q.append([nx, ny])
			distance[nx][ny] = distance[p[0]][p[1]] + 1
print(ans)


(h, w) = map(int, input().split())
cnt = 0
s = [input() for _ in range(h)]
for x in s:
	cnt += x.count('.')
ans = 0
inf = 10 ** 8
dp = [[inf] * w for _ in range(h)]
dp[0][0] = 0
from collections import deque
queue = deque([(0, 0)])
d = ((0, 1), (0, -1), (1, 0), (-1, 0))
while queue:
	r = queue.popleft()
	for x in d:
		xx = r[0] + x[0]
		yy = r[1] + x[1]
		if 0 <= xx < h and 0 <= yy < w:
			if s[xx][yy] == '.' and dp[xx][yy] == inf:
				dp[xx][yy] = dp[r[0]][r[1]] + 1
				queue.append((xx, yy))
if dp[-1][-1] == inf:
	print(-1)
	exit()
print(cnt - dp[-1][-1] - 1)


from collections import deque
(H, W) = map(int, input().split())
M = []
white = 0
for _ in range(H):
	M.append(input())
	white += M[-1].count('.')
q = deque()
q.append((0, 0))
visit = [0] * (H * W)
visit[0] = 1

def bfs():
	while q:
		(x, y) = q.popleft()
		for (dx, dy) in [(-1, 0), (0, -1), (1, 0), (0, 1)]:
			x2 = x + dx
			y2 = y + dy
			if x2 < 0 or x2 > W - 1:
				continue
			if y2 < 0 or y2 > H - 1:
				continue
			if visit[y2 * W + x2]:
				continue
			if M[y2][x2] == '#':
				continue
			visit[y2 * W + x2] = visit[y * W + x] + 1
			if y2 == H - 1 and x2 == W - 1:
				return visit[y2 * W + x2]
			q.append((x2, y2))
steps = bfs()
ans = -1
if steps:
	ans = white - steps
print(ans)


from collections import deque
(H, W) = list(map(int, input().split()))
S = [list(input()) for _ in range(H)]

def get_next(x, y, costs, S, cost):
	ans = list()
	if x != 0 and costs[x - 1][y] == -1 and (S[x - 1][y] == '.'):
		ans.append([x - 1, y])
		costs[x - 1][y] = cost + 1
	if x != H - 1 and costs[x + 1][y] == -1 and (S[x + 1][y] == '.'):
		ans.append([x + 1, y])
		costs[x + 1][y] = cost + 1
	if y != 0 and costs[x][y - 1] == -1 and (S[x][y - 1] == '.'):
		ans.append([x, y - 1])
		costs[x][y - 1] = cost + 1
	if y != W - 1 and costs[x][y + 1] == -1 and (S[x][y + 1] == '.'):
		ans.append([x, y + 1])
		costs[x][y + 1] = cost + 1
	return ans
costs = [[-1 for _ in range(W)] for _ in range(H)]
costs[0][0] = 0
q = deque()
q.append([0, 0])
while len(q) and costs[H - 1][W - 1] == -1:
	now = q.popleft()
	nxt = get_next(now[0], now[1], costs, S, costs[now[0]][now[1]])
	for dot in nxt:
		q.append([dot[0], dot[1]])
fin_cost = costs[H - 1][W - 1]
if fin_cost == -1:
	print(-1)
else:
	w_cnt = 0
	for i in range(H):
		for j in range(W):
			if S[i][j] == '.':
				w_cnt += 1
	print(w_cnt - fin_cost - 1)


from collections import deque
(H, W) = map(int, input().split())
w = '#' * (W + 2)
white = 0
S = [w]
for _ in range(H):
	wwww = input()
	white += wwww.count('.')
	S.append('#' + wwww + '#')
S.append(w)
m = [[10 ** 10] * (W + 2) for _ in range(H + 2)]
q = deque([[1, 1]])
d = ((-1, 0), (0, -1), (0, 1), (1, 0))
m[1][1] = 0
while q:
	(y, x) = q.popleft()
	p = m[y][x]
	for (dx, dy) in d:
		xx = x + dx
		yy = y + dy
		if S[yy][xx] == '#':
			continue
		if m[yy][xx] > p + 1:
			m[yy][xx] = p + 1
			q.append([yy, xx])
if m[H][W] == 10 ** 10:
	print(-1)
else:
	print(white - m[H][W] - 1)


(H, W) = (int(i) for i in input().split())
grid = ['#' * (W + 2)] + ['#' + input() + '#' for i in range(H)] + ['#' * (W + 2)]
smap = [[-1 for i in range(W + 2)] for i in range(H + 2)]
q = []
dot = 0
angle = [[1, 0], [-1, 0], [0, 1], [0, -1]]
for i in grid:
	dot += i.count('.')
smap[1][1] = 1
q.append([1, 1])
while len(q) > 0:
	pos = q.pop(0)
	cnt = smap[pos[0]][pos[1]] + 1
	for a in angle:
		if grid[pos[0] + a[0]][pos[1] + a[1]] == '.' and smap[pos[0] + a[0]][pos[1] + a[1]] == -1:
			q.append([pos[0] + a[0], pos[1] + a[1]])
			smap[pos[0] + a[0]][pos[1] + a[1]] = cnt
print(-1) if smap[H][W] == -1 else print(dot - smap[H][W])


(H, W) = map(int, input().strip().split(' '))
maze = ['#' * (W + 2)]
maze += ['#' + input().strip() + '#' for _ in range(H)]
maze.append('#' * (W + 2))
maze_map = [[float('inf')] * (W + 2) for _ in range(H + 2)]
maze_map[1][1] = 1
mem = [(1, 1)]
while True:
	if len(mem) == 0:
		break
	(x, y) = mem.pop()
	for (dx, dy) in [(1, 0), (-1, 0), (0, 1), (0, -1)]:
		if maze[y + dy][x + dx] == '.':
			if maze_map[y + dy][x + dx] > maze_map[y][x] + 1:
				maze_map[y + dy][x + dx] = maze_map[y][x] + 1
				mem.append((x + dx, y + dy))
if maze_map[H][W] == float('inf'):
	print(-1)
else:
	w = sum((m.count('.') for m in maze))
	print(w - maze_map[H][W])


(H, W) = map(int, input().split())
S = [input() for i in range(H)]
queue = [(0, 0, 1)]
done = {(0, 0)}
count = sum((row.count('#') for row in S))

def bfs(x, y, c):
	if x < 0 or y < 0 or x >= W or (y >= H) or (S[y][x] == '#'):
		return
	if (x, y) in done:
		return
	queue.append((x, y, c + 1))
	done.add((x, y))
dx = [1, -1, 0, 0]
dy = [0, 0, 1, -1]
flag = -1
while queue:
	(x, y, c) = queue.pop(0)
	if x == W - 1 and y == H - 1:
		flag = 1
		break
	for i in range(4):
		bfs(x + dx[i], y + dy[i], c)
print(flag if flag == -1 else H * W - count - c)


(h, w) = map(int, input().split())
l = []
l.append(['#' for i in range(w + 2)])
for i in range(h):
	l.append(list('#' + input() + '#'))
l.append(['#' for i in range(w + 2)])
ctw = 0
for i in range(1, h + 1):
	for j in range(1, w + 1):
		if l[i][j] == '.':
			ctw += 1
L = [[1, 1]]
ct = 0
x = 0
for i in range(h * w):
	L2 = []
	for j in range(len(L)):
		L3 = [[L[j][0] - 1, L[j][1]], [L[j][0] + 1, L[j][1]], [L[j][0], L[j][1] - 1], [L[j][0], L[j][1] + 1]]
		for k in range(4):
			if l[L3[k][0]][L3[k][1]] == '.':
				L2.append(L3[k])
				l[L3[k][0]][L3[k][1]] = '#'
	ct += 1
	L = L2
	if [h, w] in L:
		x = ct
		break
if x == 0:
	print(-1)
else:
	print(ctw - ct - 1)


def __starting_point():
	from collections import deque
	(H, W) = map(int, input().split())
	s = []
	black = 0
	for _ in range(H):
		t = list(input())
		for c in t:
			if c == '#':
				black += 1
		s.append(t)
	q = deque([(0, 0, 1)])
	s[0][0] = '#'
	while q:
		(x, y, d) = q.popleft()
		if x == H - 1 and y == W - 1:
			print(H * W - d - black)
			return
		for (nx, ny) in [(x + 1, y), (x, y + 1), (x - 1, y), (x, y - 1)]:
			if 0 <= nx < H and 0 <= ny < W and (s[nx][ny] == '.'):
				s[nx][ny] = '#'
				q.append((nx, ny, d + 1))
	print(-1)
__starting_point()


def abc088d_grid_repainting():
	import heapq
	(h, w) = map(int, input().split())
	maze = []
	cnt = h * w
	for _ in range(h):
		s = input()
		maze.append(s)
		cnt -= s.count('#')
	q = [(1, 0, 0)]
	heapq.heapify(q)
	check = [[False] * w for _ in range(h)]
	while len(q) != 0:
		(dis, x, y) = heapq.heappop(q)
		if (x, y) == (h - 1, w - 1):
			print(cnt - dis)
			return
		for (dx, dy) in zip([0, 0, 1, -1], [1, -1, 0, 0]):
			if 0 <= x + dx < h and 0 <= y + dy < w and (maze[x + dx][y + dy] != '#') and (not check[x + dx][y + dy]):
				check[x + dx][y + dy] = True
				heapq.heappush(q, (dis + 1, x + dx, y + dy))
	print('-1')
abc088d_grid_repainting()


from collections import deque
(h, w) = map(int, input().split())
w_sum = 0
maze = []
inf = 10000000
for _ in range(h):
	s = list(input())
	for i in range(w):
		if s[i] == '.':
			s[i] = inf
			w_sum += 1
	maze.append(s)

def solve(maze, h, w):
	qu = deque([[0, 0]])
	maze[0][0] = 0
	while qu:
		(y, x) = qu.popleft()
		t = maze[y][x]
		for i in ([1, 0], [-1, 0], [0, 1], [0, -1]):
			ny = y + i[0]
			nx = x + i[1]
			if 0 <= ny <= h - 1 and 0 <= nx <= w - 1 and (maze[ny][nx] != '#'):
				if maze[ny][nx] > t + 1:
					maze[ny][nx] = t + 1
					qu.append([ny, nx])
	return maze[h - 1][w - 1]
if solve(maze, h, w) == inf:
	print(-1)
else:
	print(w_sum - solve(maze, h, w) - 1)


(h, w) = map(int, input().split())
w_cnt = 0
L = []
for i in range(h):
	s = input()
	w_cnt += s.count('.')
	L.append(s)
from collections import deque
visited = [[0] * w for _ in range(h)]
q = deque([[0, 0]])
li = [[1, 0], [0, 1], [-1, 0], [0, -1]]
while q:
	(y, x) = q.popleft()
	for (dy, dx) in li:
		(ny, nx) = (y + dy, x + dx)
		if ny < 0 or ny >= h or nx < 0 or (nx >= w) or (visited[ny][nx] > 0) or (L[ny][nx] == '#'):
			continue
		visited[ny][nx] = visited[y][x] + 1
		if [ny, nx] == [h - 1, w - 1]:
			print(w_cnt - visited[ny][nx] - 1)
			return
		q.append([ny, nx])
print(-1)


(H, W) = list(map(int, input().split()))
sq = [list(input()) for i in range(H)]
pos = [[0, 0, 0]]
g = True
while pos != []:
	(y, x, depth) = pos.pop(0)
	if y == H - 1 and x == W - 1:
		g = False
		break
	if x - 1 >= 0:
		if sq[y][x - 1] == '.':
			pos.append([y, x - 1, depth + 1])
			sq[y][x - 1] = '!'
	if x + 1 <= W - 1:
		if sq[y][x + 1] == '.':
			pos.append([y, x + 1, depth + 1])
			sq[y][x + 1] = '!'
	if y - 1 >= 0:
		if sq[y - 1][x] == '.':
			pos.append([y - 1, x, depth + 1])
			sq[y - 1][x] = '!'
	if y + 1 <= H - 1:
		if sq[y + 1][x] == '.':
			pos.append([y + 1, x, depth + 1])
if g == True:
	print(-1)
else:
	temp = 0
	for k in range(H):
		for m in range(W):
			if sq[k][m] == '#':
				temp += 1
	print(H * W - temp - depth - 1)


(H, W) = map(int, input().split())
maze = ['#' * (W + 2)]
for _ in range(H):
	maze.append('#' + input() + '#')
maze.append('#' * (W + 2))
cost = [[-1] * (W + 2) for _ in range(H + 2)]
cost[1][1] = 0
que = [(1, 1)]
while que:
	(i, j) = que.pop(0)
	if (i, j) == (H, W):
		break
	for (k, l) in ((i - 1, j), (i + 1, j), (i, j - 1), (i, j + 1)):
		if maze[k][l] == '.' and cost[k][l] == -1:
			cost[k][l] = cost[i][j] + 1
			que.append((k, l))
if cost[H][W] == -1:
	print(-1)
else:
	n = -2
	for i in range(1, H + 1):
		for j in range(1, W + 1):
			if maze[i][j] == '.':
				n += 1
	print(n - cost[H][W] + 1)


import re
import copy
import numpy as np
import queue

def accept_input():
	(H, W) = list(map(int, input().split()))
	S = []
	for _ in range(H):
		S.append(input())
	return (H, W, S)

def widthsearch(q):
	movelist = [(0, 1), (0, -1), (1, 0), (-1, 0)]
	while not q.empty():
		pack = q.get()
		y = pack[0][0]
		x = pack[0][1]
		num = pack[1]
		if S[y][x] == 'g':
			return num
		for move in movelist:
			if y + move[0] == -1 or y + move[0] == H or x + move[1] == -1 or (x + move[1] == W):
				continue
			elif visitedlist[y + move[0]][x + move[1]] == 1:
				continue
			elif S[y + move[0]][x + move[1]] == '#':
				continue
			else:
				visitedlist[y + move[0]][x + move[1]] = 1
				q.put(((y + move[0], x + move[1]), num + 1))
	return -1
(H, W, S) = accept_input()
for i in range(len(S)):
	if i == 0:
		S[i] = 's' + S[i][1:]
	if i == H - 1:
		S[i] = S[i][:W - 1] + 'g'
siro = H * W
for i in range(H):
	for j in range(W):
		if S[i][j] == '#':
			siro -= 1
q = queue.Queue()
q.put(((0, 0), 0))
visitedlist = np.zeros((H, W))
visitedlist[0][0] = 1
result = widthsearch(q)
if result == -1:
	print(-1)
else:
	print(siro - result - 1)


from collections import deque
(h, w) = map(int, input().split())
s = []
sharp = 0
for i in range(h):
	t = input()
	sharp += t.count('#')
	s.append(t)
queue = deque([[0, 0]])
visited = [[-1 for i in range(w)] for j in range(h)]
visited[0][0] = 0
d = [(1, 0), (0, 1), (-1, 0), (0, -1)]
while queue:
	(i, j) = queue.popleft()
	for (n, m) in d:
		x = i + n
		y = j + m
		if x < 0 or x >= h or y < 0 or (y >= w) or (s[x][y] == '#') or (visited[x][y] != -1):
			continue
		visited[x][y] = visited[i][j] + 1
		queue.append([x, y])
if visited[h - 1][w - 1] == -1:
	print(-1)
else:
	ans = h * w - visited[h - 1][w - 1] - 1 - sharp
	print(ans)


from _collections import deque

def bfs():
	que = deque([])
	que.append((0, 0))
	dh = [-1, 0, 1, 0]
	dw = [0, -1, 0, 1]
	d = [[float('inf')] * w for _ in range(h)]
	d[0][0] = 0
	while que:
		p = que.popleft()
		if p[0] == h - 1 and p[1] == w - 1:
			break
		for i in range(4):
			nh = p[0] + dh[i]
			nw = p[1] + dw[i]
			if 0 <= nh < h and 0 <= nw < w and (d[nh][nw] == float('inf')) and (c[nh][nw] == '.'):
				que.append((nh, nw))
				d[nh][nw] = 1 + d[p[0]][p[1]]
	return d[h - 1][w - 1]
(h, w) = list(map(int, input().split()))
c = [list(input()) for _ in range(h)]
count = 0
for i in range(h):
	for j in range(w):
		if c[i][j] == '.':
			count += 1
mi = bfs()
if 0 < mi < float('inf'):
	print(count - mi - 1)
else:
	print(-1)


from collections import deque
(H, W) = [int(x) for x in input().split()]
board = []
for _ in range(H):
	board.append(input())
white = sum([board[h].count('.') for h in range(H)])
dist = {(x, y): white + 1 for x in range(W) for y in range(H)}
q = deque([(0, 0)])
dist[0, 0] = 1
while q:
	(x, y) = q.popleft()
	for d in range(4):
		(nx, ny) = (x + int((1j ** d).real), y + int((1j ** d).imag))
		if nx < 0 or W <= nx or ny < 0 or (H <= ny):
			continue
		if board[ny][nx] == '#':
			continue
		if dist[nx, ny] <= white:
			continue
		dist[nx, ny] = dist[x, y] + 1
		q.append((nx, ny))
lenofpath = dist[W - 1, H - 1]
ans = white - lenofpath
print(ans)


from collections import deque
(h, w) = map(int, input().split())
maze = [input() for _ in range(h)]
(gx, gy) = (w - 1, h - 1)
q = deque()
q.appendleft([0, 0])
INF = 10 ** 5
dist = [[INF] * w for _ in range(h)]
dist[0][0] = 0
while q:
	(x, y) = q.pop()
	for (dx, dy) in [[1, 0], [0, 1], [-1, 0], [0, -1]]:
		nx = x + dx
		ny = y + dy
		if 0 <= nx < w and 0 <= ny < h:
			if dist[ny][nx] == INF and maze[ny][nx] != '#':
				dist[ny][nx] = dist[y][x] + 1
				q.appendleft([nx, ny])
black_num = sum([maze[i].count('#') for i in range(h)])
if dist[gy][gx] == INF:
	print(-1)
else:
	print(h * w - dist[gy][gx] - black_num - 1)


from collections import deque
import sys
sys.setrecursionlimit(10 ** 6)
(H, W) = map(int, input().split())
maze = []
for _ in range(H):
	maze.append(input())
(si, sj) = (0, 0)
(gi, gj) = (H - 1, W - 1)
didj = [(1, 0), (0, 1), (-1, 0), (0, -1)]

def bfs(H, W, blocker='X'):
	while que != deque():
		(i, j) = que.popleft()
		for (di, dj) in didj:
			ni = i + di
			nj = j + dj
			if 0 <= ni and ni < H and (0 <= nj) and (nj < W) and (maze[ni][nj] != blocker) and (d[ni][nj] == INF):
				d[ni][nj] = d[i][j] + 1
				que.append((ni, nj))
	return
INF = H * W * 10
d = [[INF for x in range(W)] for x in range(H)]
d[si][sj] = 0
que = deque()
que.append((si, sj))
bfs(H, W, blocker='#')
if d[gi][gj] == INF:
	print(-1)
else:
	blc = 0
	for h in maze:
		for l in h:
			if l == '#':
				blc += 1
	score = H * W - blc - d[gi][gj] - 1
	print(score)


(H, W) = map(int, input().split())
walls = 0
S = [0] * H
for i in range(H):
	L = input()
	walls += L.count('#')
	S[i] = '#' + L + '#'
S = ['#' * (W + 2)] + S + ['#' * (W + 2)]
V = [[0] * (W + 2) for _ in range(H + 2)]
q = [(1, 1, 1)]
while q:
	(x, y, c) = q.pop(0)
	if (x, y) == (H, W):
		print(H * W - walls - c)
		break
	for (m, n) in {(0, 1), (0, -1), (1, 0), (-1, 0)}:
		(i, j) = (x + m, y + n)
		if S[i][j] == '#' or V[i][j]:
			continue
		q.append((i, j, c + 1))
		V[i][j] = 1
else:
	print(-1)


from collections import deque
(H, W) = map(int, input().split())
M = [input() for _ in range(H)]
D = [[10 ** 5] * W for _ in range(H)]
cnt = 0
for i in range(H):
	cnt += M[i].count('#')
visited = [[0] * W for _ in range(H)]
q = deque([[0, 0, 0]])
while q:
	(x, y, dist) = q.popleft()
	if visited[x][y] == 1:
		continue
	visited[x][y] = 1
	D[x][y] = dist
	for (i, j) in [(1, 0), (-1, 0), (0, 1), (0, -1)]:
		if x + i >= H or y + j >= W or x + i < 0 or (y + j < 0):
			continue
		if M[x + i][y + j] == '#':
			continue
		q.append([x + i, y + j, dist + 1])
if D[H - 1][W - 1] == 10 ** 5:
	print(-1)
else:
	print(H * W - 1 - D[H - 1][W - 1] - cnt)


from collections import deque
(h, w) = map(int, input().split())
s = [list(input()) for i in range(h)]
ans = 0
for i in range(h):
	for j in range(w):
		if s[i][j] == '.':
			ans += 1
q = deque([[0, 0]])
dx = [1, 0, -1, 0]
dy = [0, 1, 0, -1]
s[0][0] = 0
while q:
	p = q.popleft()
	if p[0] == h - 1 and p[1] == w - 1:
		break
	for i in range(4):
		x = p[0] + dx[i]
		y = p[1] + dy[i]
		if 0 <= x < h and 0 <= y < w and (s[x][y] == '.'):
			s[x][y] = s[p[0]][p[1]] + 1
			q.append([x, y])
print(-1 if s[-1][-1] == '.' else ans - s[-1][-1] - 1)


import sys
sys.setrecursionlimit(3000)
import queue
(h, w) = map(int, input().split())
s = ['#' * (w + 2)] + ['#' + input() + '#' for _ in [0] * h] + ['#' * (w + 2)]
l = [[0] * (w + 2) for _ in [0] * (h + 2)]
for i in range(h + 2):
	for j in range(w + 2):
		if s[i][j] == '#':
			l[i][j] = -1
L = queue.Queue()
L.put([1, 1])
while not L.empty():
	n = L.get()
	for (dx, dy) in [(1, 0), (-1, 0), (0, 1), (0, -1)]:
		if l[n[0] + dx][n[1] + dy] == 0 and [n[0] + dx, n[1] + dy] != [1, 1]:
			l[n[0] + dx][n[1] + dy] = l[n[0]][n[1]] + 1
			L.put([n[0] + dx, n[1] + dy])
if l[h][w] == 0:
	print(-1)
else:
	print(h * w - l[h][w] - (sum((x.count('#') for x in s)) - 2 * h - 2 * w - 4) - 1)


INF = 10 * 10
(H, W) = map(int, input().split())
s = [list(input()) for _ in range(H)]
wall = sum(map(lambda x: x.count('#'), s))
d = [[INF for _ in range(W)] for _ in range(H)]

def bfs(h, w, c):
	if d[h][w] <= c:
		return
	d[h][w] = c
	for (dh, dw) in [(0, -1), (-1, 0), (0, 1), (1, 0)]:
		if h + dh >= 0 and w + dw >= 0 and (h + dh < H) and (w + dw < W) and (s[h + dh][w + dw] == '.'):
			bfs(h + dh, w + dw, c + 1)
bfs(0, 0, 1)
print(-1 if d[H - 1][W - 1] == INF else H * W - d[H - 1][W - 1] - wall)


from collections import deque
(H, W) = map(int, input().split())
s = []
cnt = 0
for i in range(H):
	temp = list(input())
	cnt += temp.count('.')
	s.append(temp)
d = deque([[0, 0]])
c = [[10000] * W for i in range(H)]
step = [[-1, 0], [0, -1], [1, 0], [0, 1]]
c[0][0] = 1
while d:
	(h0, w0) = d.popleft()
	for (h1, w1) in step:
		h = h0 + h1
		w = w0 + w1
		if h < 0 or h >= H or w < 0 or (w >= W) or (s[h][w] == '#') or (c[h][w] != 10000):
			continue
		if h == H - 1 and w == W - 1:
			ans = cnt - c[h0][w0] - 1
			print(ans)
			exit()
		c[h][w] = c[h0][w0] + 1
		d.append([h, w])
print(-1)


(H, W) = map(int, input().split())
MAP = [list(input()) for _ in range(H)]
cnt = 0
for l in MAP:
	cnt += l.count('#')
FLAG = [[-1] * W for _ in range(H)]
FLAG[0][0] = 1
q = [(0, 0)]
d = [(1, 0), (0, 1), (-1, 0), (0, -1)]
while q:
	(y, x) = q.pop(0)
	for (dy, dx) in d:
		if 0 <= y + dy < H and 0 <= x + dx < W and (FLAG[y + dy][x + dx] == -1) and (MAP[y + dy][x + dx] == '.'):
			FLAG[y + dy][x + dx] = FLAG[y][x] + 1
			q.append((y + dy, x + dx))
if FLAG[H - 1][W - 1] == -1:
	print(-1)
else:
	print(H * W - FLAG[H - 1][W - 1] - cnt)


import collections
(h, w) = map(int, input().split())
s = [list(input()) for _ in range(h)]
deq = collections.deque([[0, 0, 0]])
while deq:
	(i, j, k) = deq.popleft()
	if not (i in range(h) and j in range(w)):
		continue
	if s[i][j] != '.':
		continue
	s[i][j] = k
	if i == h - 1 and j == w - 1:
		break
	deq.append([i + 1, j, k + 1])
	deq.append([i - 1, j, k + 1])
	deq.append([i, j + 1, k + 1])
	deq.append([i, j - 1, k + 1])
if s[h - 1][w - 1] == '#' or s[h - 1][w - 1] == '.':
	print(-1)
else:
	black = sum([y.count('#') for y in s])
	print(h * w - black - s[h - 1][w - 1] - 1)


(H, W) = map(int, input().split())
s = ['' for i in range(H)]
white = H * W
black = 0
for i in range(H):
	s[i] = input()
	black += s[i].count('#')
white -= black
direction = [[1, 0], [0, 1], [-1, 0], [0, -1]]
q = [[0, 0, 0]]
mass = [[-1 for i in range(W)] for j in range(H)]
while len(q) > 0:
	tmp = [y, x, d] = q.pop(0)
	if mass[y][x] >= 0:
		continue
	mass[y][x] = d
	for [dy, dx] in direction:
		ny = y + dy
		nx = x + dx
		if 0 <= ny and ny < H and (0 <= nx) and (nx < W):
			if s[ny][nx] == '#' or mass[ny][nx] >= 0:
				continue
			q.append([ny, nx, d + 1])
if mass[H - 1][W - 1] < 0:
	print(-1)
else:
	print(white - mass[H - 1][W - 1] - 1)


from collections import deque
(h, w) = map(int, input().split())
grid = [input() for _ in range(h)]
vis = [[0] * w for _ in range(h)]
vis[0][0] = 1
que = deque([(0, 0)])
while que:
	(p, q) = que.popleft()
	for (x, y) in ((-1, 0), (0, -1), (1, 0), (0, 1)):
		if 0 <= p + x < w and 0 <= q + y < h and (vis[q + y][p + x] < 1) and (grid[q + y][p + x] == '.'):
			vis[q + y][p + x] = vis[q][p] + 1
			que.append((p + x, q + y))
if not vis[h - 1][w - 1]:
	print(-1)
else:
	print(h * w - sum((c.count('#') for c in grid)) - vis[h - 1][w - 1])


from queue import Queue
dx = [1, 0, -1, 0]
dy = [0, 1, 0, -1]
(H, W) = list(map(int, input().split()))
S = [input() for _ in range(H)]
dist = [[-1] * W for _ in range(H)]
que = Queue()
dist[0][0] = 0
que.put((0, 0))
while not que.empty():
	(x, y) = que.get()
	for dir in range(4):
		(x2, y2) = (x + dx[dir], y + dy[dir])
		if x2 < 0 or x2 >= H or y2 < 0 or (y2 >= W) or (S[x2][y2] == '#'):
			continue
		if dist[x2][y2] != -1:
			continue
		dist[x2][y2] = dist[x][y] + 1
		que.put((x2, y2))
white = sum((sum((1 if S[x][y] == '.' else 0 for y in range(W))) for x in range(H)))
print(white - dist[H - 1][W - 1] - 1 if dist[H - 1][W - 1] != -1 else -1)


from collections import deque
(h, w) = [int(item) for item in input().split()]
s = [input() for _ in range(h)]
dist = [[-1] * w for _ in range(h)]
black = 0
for line in s:
	black += line.count('#')
que = deque()
que.append([0, 0])
dist[0][0] = 1
while que:
	(x, y) = que.popleft()
	for (i, j) in [(1, 0), (-1, 0), (0, 1), (0, -1)]:
		nx = x + i
		ny = y + j
		if nx < 0 or nx >= h or ny < 0 or (ny >= w):
			continue
		if s[nx][ny] == '#':
			continue
		if dist[nx][ny] == -1:
			dist[nx][ny] = dist[x][y] + 1
			que.append([nx, ny])
if dist[h - 1][w - 1] == -1:
	print(-1)
else:
	print(h * w - dist[h - 1][w - 1] - black)


(H, W) = map(int, input().split())
l = [list(input()) for _ in range(H)]
from collections import deque
q = deque([(0, 0)])
d = [(1, 0), (-1, 0), (0, 1), (0, -1)]
l[0][0] = 0
while q:
	(y, x) = q.popleft()
	for (dy, dx) in d:
		if 0 <= y + dy < H and 0 <= x + dx < W and (l[y + dy][x + dx] == '.'):
			l[y + dy][x + dx] = l[y][x] + 1
			q.append((y + dy, x + dx))
try:
	g = l[H - 1][W - 1]
	total = 0
	for _l in l:
		for i in _l:
			if i != '#':
				total += 1
	print(total - g - 1)
except:
	print(-1)


from collections import deque
(H, W) = map(int, input().split())
edges = [0] * (W + 2)
field = [edges]
WH = 0
for _ in range(H):
	row = [c == '.' for c in input()]
	field.append([0] + row + [0])
	WH += sum(row)
field.append(edges)
que = deque([(1, 1, 1)])
(enq, deq) = (que.append, que.popleft)
while que:
	(x, y, cnt) = deq()
	if (x, y) == (W, H):
		print(WH - cnt)
		exit()
	for (dx, dy) in [(0, 1), (0, -1), (1, 0), (-1, 0)]:
		(nx, ny) = (x + dx, y + dy)
		if field[ny][nx]:
			enq((nx, ny, cnt + 1))
			field[ny][nx] = 0
print(-1)


(H, W) = map(int, input().split())
T = [[] for i in range(H)]
b = 0
for i in range(H):
	T[i] = list(input())
	for j in range(W):
		if T[i][j] == '#':
			b += 1
que = [(0, 0, 1)]
while que:
	(x, y, k) = que.pop(0)
	if x == H - 1 and y == W - 1:
		print(H * W - b - k)
		exit()
	for (dx, dy) in [(0, 1), (1, 0), (-1, 0), (0, -1)]:
		(nx, ny) = (x + dx, y + dy)
		if 0 <= nx < H and 0 <= ny < W and (T[nx][ny] == '.'):
			T[nx][ny] = '#'
			que.append((nx, ny, k + 1))
print(-1)


from collections import deque

def main():

	def _bfs():
		while q:
			now = q.popleft()
			(height, width) = (now[0], now[1])
			if height == h - 1 and width == w - 1:
				return board[height][width]
			for i in range(4):
				ny = height + dy[i]
				nx = width + dx[i]
				if 0 <= ny < h and 0 <= nx < w and (board[ny][nx] == '.'):
					q.append((ny, nx))
					board[ny][nx] = 1 + board[height][width]
		return -1
	(h, w) = list(map(int, input().split()))
	board = []
	totalPoints = 0
	for _ in range(h):
		row = list(input())
		totalPoints += row.count('.')
		board.append(row)
	board[0][0] = 1
	q = deque([(0, 0)])
	dy = [0, -1, 0, 1]
	dx = [1, 0, -1, 0]
	step = _bfs()
	if step == -1:
		return -1
	ans = totalPoints - step
	return ans

def __starting_point():
	print(main())
__starting_point()


(H, W) = map(int, input().split())
L = ['#' * (W + 2)]
n = 0
for i in range(H):
	S = input()
	n += S.count('.')
	L.append('#' + S + '#')
L.append('#' * (W + 2))
r = [(1, 1)]
dic = {(1, 1): 1}
m = [(1, 1)]
i = 1
mm = []
nyan = [(0, 1), (0, -1), (1, 0), (-1, 0)]
while m:
	i += 1
	for (a, b) in m:
		for (c, d) in nyan:
			(x, y) = (a + c, b + d)
			if L[x][y] == '.' and (x, y) not in r:
				r.append((x, y))
				mm.append((x, y))
				dic[x, y] = i
	m = mm[:]
	mm = []
if (H, W) in r:
	print(n - dic[H, W])
else:
	print(-1)


from collections import deque
(H, W) = list(map(int, input().split()))
mazo = [list(input()) for _ in range(H)]
cnt = 0
for i in range(H):
	for j in range(W):
		if mazo[i][j] == '#':
			cnt += 1
d = deque()
d.append((0, 0))
move = [(-1, 0), (1, 0), (0, -1), (0, 1)]
visited = [[0] * W for _ in range(H)]
flg = False
while d:
	(y, x) = d.popleft()
	if y == H - 1 and x == W - 1:
		flg = True
		break
	for (u, v) in move:
		t = y + u
		s = x + v
		if 0 <= t and t < H and (0 <= s) and (s < W) and (mazo[t][s] == '.') and (visited[t][s] == 0):
			visited[t][s] = visited[y][x] + 1
			d.append((t, s))
if flg:
	print(H * W - cnt - visited[H - 1][W - 1] - 1)
else:
	print(-1)


import sys
from io import StringIO
import unittest
from collections import deque

class TestClass(unittest.TestCase):

	def assertIO(self, input, output):
		(stdout, stdin) = (sys.stdout, sys.stdin)
		(sys.stdout, sys.stdin) = (StringIO(), StringIO(input))
		resolve()
		sys.stdout.seek(0)
		out = sys.stdout.read()[:-1]
		(sys.stdout, sys.stdin) = (stdout, stdin)
		self.assertEqual(out, output)

	def test_入力例_1(self):
		input = '3 3\n..#\n# ..\n...'
		output = '2'
		self.assertIO(input, output)

	def test_入力例_2(self):
		input = '10 37\n.....................................\n...#...####...####..###...###...###..\n..#.#..#...#.##....#...#.#...#.#...#.\n..#.#..#...#.#.....#...#.#...#.#...#.\n.#...#.#..##.#.....#...#.#.###.#.###.\n.#####.####..#.....#...#..##....##...\n.#...#.#...#.#.....#...#.#...#.#...#.\n.#...#.#...#.##....#...#.#...#.#...#.\n.#...#.####...####..###...###...###..\n.....................................'
		output = '209'
		self.assertIO(input, output)

def resolve():
	(H, W) = list(map(int, input().split()))
	S = [list(input()) for _ in range(H)]
	F = [[-1] * W for _ in range(H)]
	dx = [1, 0, -1, 0]
	dy = [0, 1, 0, -1]
	Q = deque()
	Q.append([0, 0])
	F[0][0] = 1
	while Q:
		p = Q.popleft()
		(x, y) = p
		if x == W - 1 and y == H - 1:
			break
		for i in range(4):
			nx = x + dx[i]
			ny = y + dy[i]
			if nx < 0 or nx >= W or ny < 0 or (ny >= H) or (S[ny][nx] == '#') or (F[ny][nx] != -1):
				continue
			Q.append([nx, ny])
			F[ny][nx] = F[y][x] + 1
	if F[H - 1][W - 1] == -1:
		print(-1)
	else:
		NS = 0
		for s in S:
			NS += s.count('#')
		print(W * H - F[H - 1][W - 1] - NS)

def __starting_point():
	resolve()
__starting_point()


import sys
from collections import Counter
from collections import deque
input = sys.stdin.readline

def main():
	(H, W) = list(map(int, input().split()))
	grid = []
	wh = 0
	for _ in range(H):
		tmp = list(input()[:-1])
		wh += Counter(tmp)['.']
		grid.append(tmp)
	check = [[0] * W for _ in range(H)]
	digtmp = [(0, 1), (1, 0), (0, -1), (-1, 0)]
	que = deque([(0, 0)])
	check[0][0] = 1
	while True:
		(a, b) = que.popleft()
		for (dx, dy) in digtmp:
			x = a + dx
			y = b + dy
			if not (0 <= x < H and 0 <= y < W):
				continue
			if check[x][y] != 0 or grid[x][y] == '#':
				continue
			check[x][y] = check[a][b] + 1
			que.append((x, y))
		if len(que) == 0:
			break
	if check[H - 1][W - 1] == 0:
		print(-1)
	else:
		print(wh - check[H - 1][W - 1])

def __starting_point():
	main()
__starting_point()


import copy
(h, w) = list(map(int, input().split()))
s = [[] * w for _ in range(h)]
white = 0
for i in range(h):
	t = input()
	for j in range(w):
		if t[j] == '.':
			white += 1
			s[i].append(10 ** 5)
		elif t[j] == '#':
			s[i].append(t[j])
now = [0, 0]
steps = []
steps.append(now)
direction = []
s[0][0] = 0
a = [2]
while len(steps) > 0:
	now = copy.copy(steps[0])
	if s[now[0]][now[1]] == '#':
		continue
	for k in [[0, 1], [1, 0], [-1, 0], [0, -1]]:
		now = copy.copy(steps[0])
		if now[0] + k[0] >= 0 and now[0] + k[0] < h:
			now[0] += k[0]
			if now[1] + k[1] >= 0 and now[1] + k[1] < w:
				now[1] += k[1]
				if s[now[0]][now[1]] == 10 ** 5:
					if not [now[0], now[1]] in steps:
						steps.append([now[0], now[1]])
			else:
				continue
		else:
			continue
	if s[steps[0][0]][steps[0][1]] > 10 ** 4:
		direction = []
		for l in [[0, 1], [1, 0], [-1, 0], [0, -1]]:
			if steps[0][0] + l[0] >= 0 and steps[0][0] + l[0] < h and (steps[0][1] + l[1] < w) and (steps[0][1] + l[1] >= 0) and (s[steps[0][0] + l[0]][steps[0][1] + l[1]] != '#'):
				s[steps[0][0]][steps[0][1]] = min(s[steps[0][0] + l[0]][steps[0][1] + l[1]] + 1, s[steps[0][0]][steps[0][1]])
	steps.pop(0)
if s[h - 1][w - 1] == '#' or s[h - 1][w - 1] == 10 ** 5:
	print(-1)
else:
	print(white - 1 - s[h - 1][w - 1])