Problem:
 Score: 400 points    Problem statement  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 # .      Constraints   H is an integer between 2 and 50 (inclusive).  W is an integer between 2 and 50 (inclusive).  s_{i, j} is . or #  (1 \leq i \leq H, 1 \leq j \leq W) .  s_{1, 1} and s_{H, W} are . .         Input  Input is given from Standard Input in the following format:  H  W  s_{1, 1}s_{1, 2}s_{1, 3} ... s_{1, W}  s_{2, 1}s_{2, 2}s_{2, 3} ... s_{2, W}  :  :  s_{H, 1}s_{H, 2}s_{H, 3} ... s_{H, W}       Output  Print the maximum possible score that Snuke can achieve, or print -1 if the game cannot be completed.        Sample Input 1 3 3
..#
#..
...      Sample Output 1 2  The score 2 can be achieved by changing the color of squares as follows:        Sample Input 2 10 37
.....................................
...#...####...####..###...###...###..
..#.#..#...#.##....#...#.#...#.#...#.
..#.#..#...#.#.....#...#.#...#.#...#.
.#...#.#..##.#.....#...#.#.###.#.###.
.#####.####..#.....#...#..##....##...
.#...#.#...#.#.....#...#.#...#.#...#.
.#...#.#...#.##....#...#.#...#.#...#.
.#...#.####...####..###...###...###..
.....................................      Sample Output 2 209

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

d = [[-1]*w for _ in range(h)]

directions = [[1, 0], [-1, 0], [0, 1], [0, -1]]

from collections import deque
que = deque([])

que.append((0, 0))
d[0][0] = 0

while que:
    x, y = que.popleft()
    if x == h-1 and y == w-1:
        break
    for i in range(4):
        dx, dy = directions[i]
        nx = x + dx
        ny = y + dy
        if 0 <= nx < h and 0 <= ny < w and field[nx][ny] =='.' and d[nx][ny] == -1:
            que.append((nx, ny))
            d[nx][ny] = d[x][y] + 1   
            

if d[h-1][w-1] == -1:
    print(-1)
else:
    white = sum(field, []).count('.')
    print(white - (d[h-1][w-1] + 1))

Solution (Python):
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)

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

def calcDist(startIdx, area):
     que = [startIdx]
     dist = [[-1 for i in range(W)] for i in range(H)]
     dist[startIdx[0]][startIdx[1]] = 0
     
     while len(que) != 0:
         idx = que.pop(0)
         
         if idx[0]-1 >= 0 and area[idx[0]-1][idx[1]] != '
             que.append([idx[0]-1, idx[1]])
             dist[idx[0]-1][idx[1]] = dist[idx[0]][idx[1]] + 1
         
         if idx[0]+1 < H and area[idx[0]+1][idx[1]] != '
             que.append([idx[0]+1, idx[1]])
             dist[idx[0]+1][idx[1]] = dist[idx[0]][idx[1]] + 1
             
         if idx[1]-1 >= 0 and area[idx[0]][idx[1]-1] != '
             que.append([idx[0], idx[1]-1])
             dist[idx[0]][idx[1]-1] = dist[idx[0]][idx[1]] + 1
             
         if idx[1]+1 < W and area[idx[0]][idx[1]+1] != '
             que.append([idx[0], idx[1]+1])
             dist[idx[0]][idx[1]+1] = dist[idx[0]][idx[1]] + 1
     
     return dist
     
def searchWhiteNum(area):
    ans = 0
    for i in range(H):
        for j in range(W):
            if area[i][j] == '.':
                ans += 1
    
    return ans

dist = calcDist([0,0], area)
neededWhiteNum = dist[H-1][W-1] + 1
ans = searchWhiteNum(area)
if neededWhiteNum == 0:
    print(-1)
else:
    print(ans-neededWhiteNum)

Solution (Python):
from collections import deque

H, W = map(int, input().split())

count = 0
g = []
g.append(['
for _ in range(H):
    lst = ['
    count += lst.count('.')
    g.append(lst)

g.append(['
check = [[-1] * (W + 2) for _ in range(H + 2)]

move = [[1, 0], [-1, 0], [0, 1], [0, -1]]




x = 1
y = 1
que = deque()
que.append([x, y])

flag = True
check[1][1] = 1
while que:
    tmp = que.popleft()
    x = tmp[0]
    y = tmp[1]
    
    for dx, dy in move:
        nx = x + dx
        ny = y + dy
        
        if g[nx][ny] == '.' and check[nx][ny] == -1:
            check[nx][ny] = check[x][y] + 1
            que.append([nx, ny])
            




if check[H][W] == -1:
    print (-1)
    exit()

print (count - check[H][W])

Solution (Python):
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]-1if visited[-1][-1]!=float('inf')else -1)

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

from collections import deque
dxy = [(0,1),(1,0),(0,-1),(-1,0)]
dist = [[0]*W for i in range(H)]
visited = [[0]*W for i in range(H)]
visited[0][0] = 1
q = deque([(0,0)])
while q:
    x,y = q.popleft()
    for dx,dy in dxy:
        nx,ny = x+dx,y+dy
        if not 0 <= nx < W: continue
        if not 0 <= ny < H: continue
        if visited[ny][nx]: continue
        if S[ny][nx] == '
        visited[ny][nx] = 1
        dist[ny][nx] = dist[y][x] + 1
        q.append((nx,ny))

dots = sum(row.count('.') for row in S)
print(dots - dist[-1][-1] - 1 if dist[-1][-1] else -1)

Solution (Python):
from collections import deque
import sys
sys.setrecursionlimit(1000000)
h, w = map(int, input().split())
start_y = 0
start_x = 0
goal_y = h - 1
goal_x = w - 1
field = []
for _ in range(h):
    field.append(list(input()))


black_count = 0
for i in range(h):
    for j in range(w):
        if field[i][j] == '.':
            black_count += 1

dy = [1, -1, 0, 0]
dx = [0, 0, 1, -1]
distance = [[-1] * w for i in range(h)]
que = deque([])
que.append([start_y, start_x])
distance[start_y][start_x] = 0

while que:
    q = que.popleft()
    if q[0] == goal_y and q[1] == goal_x:
        break
    for i in range(4):
        now_y = q[0] + dy[i]
        now_x = q[1] + dx[i]
        if now_y < 0 or now_y >= h or now_x < 0 or now_x >= w or field[now_y][now_x] == '
            continue
        if distance[now_y][now_x] != -1:
            continue
        que.append([now_y, now_x])
        distance[now_y][now_x] = distance[q[0]][q[1]] + 1

if distance[goal_y][goal_x] == -1:
    result = -1
else:
    result = black_count - (distance[goal_y][goal_x] + 1)
print(result)

Solution (Python):
from collections import deque

def solve(h, w, S):
    cands = ((0, 1), (0, -1), (1, 0), (-1, 0))
    q = deque(maxlen = h * w)
    q.append((1, 1, 1))
    s = {(1, 1)}
    min_len = -1
    while len(q) > 0:
        x, y, d = q.popleft()
        for dx, dy in cands:
            if x + dx == w and y + dy == h:
                min_len = d + 1
                q.clear()
                break
            if  1 <= x + dx <= w \
                and 1 <= y + dy <= h \
                and S[y + dy - 1][x + dx - 1] == '.' \
                and (x + dx, y + dy) not in s:
                q.append((x + dx, y + dy, d + 1))
                s.add((x + dx, y + dy))
    return (sum(l == '.' for s in S for l in s) - min_len) if min_len >= 0 else -1

_h, _w = map(int, input().split())
_S = [input() for _ in range(_h)]
print(solve(_h, _w, _S))

Solution (Python):
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)

Solution (Python):
from collections import deque

h, w = map(int, input().split())
maze = [list(input()) for a in range(h)]
visited = [[0]*w for a in range(h)]

dy = [0,1,0,-1]
dx = [1,0,-1,0]
def bfs():
    que = deque([])
    que.append((0,0))
    visited[0][0]=0

    while que:
        p = que.popleft()

        if p[0]==h-1 and p[1]==w-1:
            break

        for i in range(4):
            ny = p[0]+dy[i]
            nx = p[1]+dx[i]

            if 0<=ny<h and 0 <=nx<w and maze[ny][nx]=='.' and visited[ny][nx]==0:
                visited[ny][nx]=visited[p[0]][p[1]]+1
                que.append((ny,nx))

    return visited[h-1][w-1]

ans = bfs()
if ans == 0:
    print(-1)
else:
    cnt = 0
    for i in range(h):
        for j in range(w):
            if maze[i][j]=='
                cnt +=1

    print(h*w-cnt-ans-1)

Solution (Python):
import sys
import numpy as np
H, W = map(int, input().split())
grid = np.array([list(map(str, input())) for _ in range(H)])

X = np.where(grid == '
A = np.zeros([H,W])
A[X] = 1
orig_black = np.count_nonzero(grid=='

q = [[0,0,0]]
while q:
	cx,cy,cd = q.pop(0)
	if cx == H-1 and cy == W-1:
		shortest = cd
		break
	elif A[cx,cy] == -1:
		continue

	A[cx,cy] = -1

	for nx,ny in [[cx+1,cy],[cx-1,cy],[cx,cy+1],[cx,cy-1]]:
		if 0 <= nx < H and 0 <= ny < W:
			if A[nx][ny] == 0:
				q.append([nx,ny,cd+1])

	if q == []:
		print(-1)
		sys.exit()

print((H*W)-shortest-orig_black-1)

Solution (Python):
from collections import deque
H, W = list(map(int, input().split()))
A = []
for _ in range(H):
  A.append(input())
  

bcount = 0
for i in range(H):
  for j in range(W):
    if A[i][j] == ".":
      bcount += 1
      
d = deque()
dist = [[-1 for j in range(W)] for i in range(H)]
visited = [[False for j in range(W)] for i in range(H)]
willsearch = [[False for j in range(W)] for i in range(H)]

d.append([0,0])
dist[0][0] = 0

while len(d) > 0:
  x,y = d.popleft()
  visited[x][y] = True
  for a,b in [[x+1,y], [x-1,y], [x,y+1], [x,y-1]]:
    if not (0 <= a and a < H and 0 <= b and b < W) :
      continue
    if A[a][b] == '
      continue
    if visited[a][b] or willsearch[a][b]:
      continue
    willsearch[a][b] = True
    d.append([a,b])
    dist[a][b] = dist[x][y] + 1
    
if not visited[H-1][W-1]:
  print(-1)
else:
  print(bcount - dist[H-1][W-1]-1)

Solution (Python):

import sys
import math
import os
import itertools
import string
import heapq
import _collections
from collections import Counter
from collections import defaultdict
from functools import lru_cache
import bisect


class Scanner():
    @staticmethod
    def int():
        return int(sys.stdin.readline().rstrip())

    @staticmethod
    def string():
        return sys.stdin.readline().rstrip()

    @staticmethod
    def map_int():
        return [int(x) for x in Scanner.string().split()]

    @staticmethod
    def string_list(n):
        return [input() for i in range(n)]

    @staticmethod
    def int_list_list(n):
        return [Scanner.map_int() for i in range(n)]

    @staticmethod
    def int_cols_list(n):
        return [int(input()) for i in range(n)]


class Math():
    @staticmethod
    def gcd(a, b):
        if b == 0:
            return a
        return Math.gcd(b, a % b)

    @staticmethod
    def lcm(a, b):
        return (a * b) // Math.gcd(a, b)

    @staticmethod
    def roundUp(a, b):
        return -(-a // b)

    @staticmethod
    def toUpperMultiple(a, x):
        return Math.roundUp(a, x) * x

    @staticmethod
    def toLowerMultiple(a, x):
        return (a // x) * x

    @staticmethod
    def nearPow2(n):
        if n <= 0:
            return 0
        if n & (n - 1) == 0:
            return n
        ret = 1
        while(n > 0):
            ret <<= 1
            n >>= 1
        return ret

    @staticmethod
    def sign(n):
        if n == 0:
            return 0
        if n < 0:
            return -1
        return 1

    @staticmethod
    def isPrime(n):
        if n < 2:
            return False
        if n == 2:
            return True
        if n % 2 == 0:
            return False
        d = int(n ** 0.5) + 1
        for i in range(3, d + 1, 2):
            if n % i == 0:
                return False
        return True


MOD = int(1e09) + 7
INF = int(1e15)


def main():
    
    H, W = Scanner.map_int()
    S = Scanner.string_list(H)
    white = 0
    for s in S:
        white += s.count(".")
    q = []
    q.append((0, 0))
    memo = [[-1 for _ in range(W)] for _ in range(H)]
    memo[0][0] = 0
    while q != []:
        cur = q.pop(0)
        DIR = [(-1, 0), (1, 0), (0, 1), (0, -1)]
        for i in range(4):
            next = (cur[0] + DIR[i][0], cur[1] + DIR[i][1])
            if not 0 <= next[1] < H:
                continue
            if not 0 <= next[0] < W:
                continue
            if S[next[1]][next[0]] == "
                continue
            if memo[next[1]][next[0]] != -1:
                continue
            memo[next[1]][next[0]] = memo[cur[1]][cur[0]] + 1
            q.append(next)
    if memo[H-1][W-1] == -1:
        print("-1")
    else:
        print(white - memo[H-1][W-1] - 1)


if __name__ == "__main__":
    main()

Solution (Python):
import collections

h, w = map(int, input().split())
s = [[""]*(w+2)]
for _ in range(h):
    _s = list(input())
    _s.append("")
    _s.insert(0, "")
    s.append(_s)
s.append([""]*(w+2))

blacks = 0
for i in range(h+2):
    for j in range(w+2):
        if s[i][j] == "
            blacks += 1

dx = [1, -1, 0, 0]
dy = [0, 0, 1, -1]

visited = [[float("inf")]*(w+2) for _ in range(h+2)]
visited[1][1] = 1

q = collections.deque([[1, 1]])
while 0 < len(q):
    cy, cx = q.pop()
    for _dx, _dy in zip(dx, dy):
        x = cx + _dx
        y = cy + _dy
        if s[y][x] == "." and visited[y][x] == float("inf"):
            visited[y][x] = visited[cy][cx] + 1
            q.appendleft([y, x])

if visited[h][w] == float("inf"):
    print(-1)
else:
    print(h*w - visited[h][w] - blacks)

Solution (Python):
from collections import deque,defaultdict
H,W = map(int,input().split())
s = [["
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)

Solution (Python):
h,w = map(int, input().split())
maze = [input() for i in range(h)]
route = [[0] * w for i in range(h)]
white = 0
for i in range(h):
    for j in range(w):
        if maze[i][j] == '.':
            white += 1
 
 
class MyStack:
    def __init__(self):
        self.stack = []
    def push(self, item_1, item_2):
        self.stack.append([item_1,item_2])
    def pop(self):
        result = self.stack.pop(0)
        return result[0],result[1]
 
 
def min_route():
    global h,w
    stack = MyStack()
    stack.push(1,1)
    route[0][0] = 0
    while len(stack.stack) >= 1:
        y,x = stack.pop()
        route_num = route[y-1][x-1] + 1
        if y != h:
            if maze[y][x-1] == '.' and route[y][x-1] == 0:
                stack.push(y+1,x)
                route[y][x-1] += route_num
        if y != 1:
            if maze[y-2][x-1] == '.' and route[y-2][x-1] == 0:
                stack.push(y-1,x)
                route[y-2][x-1] += route_num
        if x != w:
            if maze[y-1][x] == '.' and route[y-1][x] == 0:
                stack.push(y,x+1)
                route[y-1][x] += route_num
        if x != 1:
            if maze[y-1][x-2] == '.' and route[y-1][x-2] == 0:
                stack.push(y,x-1)
                route[y-1][x-2] += route_num
        if route[h-1][w-1]  != 0:
            return route[h-1][w-1]
    print(-1)
    exit()
 
ans = white - min_route() - 1
 
if ans < 0:
    print(-1)
else:
    print(ans)

Solution (Python):
h,w = map(int, input().split())
maze = [input() for i in range(h)]
route = [[0] * w for i in range(h)]
white = 0
for i in range(h):
    for j in range(w):
        if maze[i][j] == '.':
            white += 1
 
 
class MyStack:
    def __init__(self):
        self.stack = []
    def push(self, item_1, item_2):
        self.stack.append([item_1,item_2])
    def pop(self):
        result = self.stack.pop(0)
        return result[0],result[1]
 
 
def min_route():
    global h,w
    stack = MyStack()
    stack.push(1,1)
    route[0][0] = 0
    n = 0
    while len(stack.stack) >= 1:
        y,x = stack.pop()
        route_num = route[y-1][x-1] + 1
        if y != h:
            if maze[y][x-1] == '.' and route[y][x-1] == 0:
                stack.push(y+1,x)
                route[y][x-1] += route_num
        if y != 1:
            if maze[y-2][x-1] == '.' and route[y-2][x-1] == 0:
                stack.push(y-1,x)
                route[y-2][x-1] += route_num
        if x != w:
            if maze[y-1][x] == '.' and route[y-1][x] == 0:
                stack.push(y,x+1)
                route[y-1][x] += route_num
        if x != 1:
            if maze[y-1][x-2] == '.' and route[y-1][x-2] == 0:
                stack.push(y,x-1)
                route[y-1][x-2] += route_num
        if route[h-1][w-1]  != 0:
            return route[h-1][w-1]
        n += 1
    print(-1)
    exit()
 
ans = white - min_route() - 1
 
if ans < 0:
    print(-1)
else:
    print(ans)

Solution (Python):
from collections import deque
from copy import deepcopy

H, W = [int(i) for i in input().split()]
raw_grid = [list(input()) for _ in range(H)]
grid = deepcopy(raw_grid)

queue = deque()
queue.append((0, 0, 0))
count = None
while queue:
    ny, nx, steps = queue.popleft()
    if not (0 <= ny < H and 0 <= nx < W):
        continue
    if grid[ny][nx] == "
        continue
    grid[ny][nx] = "
    if ny == H - 1 and nx == W - 1:
        count = steps
    for dy, dx in ((-1, 0), (1, 0), (0, -1), (0, 1)):
        queue.append((ny+dy, nx+dx, steps+1))

if count is None:
    ans = -1
else:
    ans = 0
    for line in raw_grid:
        ans += line.count(".")
    ans -= 2
    ans -= (count - 1)

print(ans)

Solution (Python):
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] == '
      continue
    p[ny][nx] = p[y][x] + 1
    queue.append((nx, ny) )
if clearable:
  print(white - p[h-1][w-1])
else:
  print(-1)

Solution (Python):
from collections import deque
H, W = map(int, input().split())
S = [input() for i in range(H)]
C = sum(s.count('.') for s in S)

dd = ((-1, 0), (0, -1), (1, 0), (0, 1))
que = deque([(0, 0, 0)])
used = {(0, 0)}

res = None
while que:
    s, t, cost = que.popleft()
    if s == H-1 and t == W-1:
        res = cost
        break
    for di, dj in dd:
        ni = s + di; nj = t + dj
        if (not 0 <= ni < H) or (not 0 <= nj < W) or S[ni][nj] == '
            continue
        used.add((ni, nj))
        que.append((ni, nj, cost + 1))
if res:
    print(C - 1 - res)
else:
    print(-1)

Solution (Python):
height, width = map(int, input().split(" "))
target = []
white_num = 0
for h in range(height):
    temp = [n for n in input()]
    white_num += temp.count(".")
    target.append(temp)
queue = [[0, 0]]
goal = -1
turn = 1
visited = [[0 for n in range(width)] for m in range(height)]
visited[0][0] = 1
all_move = [[0, 1], [0, -1], [1, 0], [-1, 0]]

while queue:
    next_queue = []
    for q in queue:
        here_x, here_y = q
        if here_x == width - 1 and here_y == height - 1:
            goal = turn
        for move in all_move:
            next_x, next_y = move[0] + here_x, move[1] + here_y
            if 0 <= next_x < width and 0 <= next_y < height:
                if not visited[next_y][next_x] and target[next_y][next_x] == ".":
                    visited[next_y][next_x] = 1
                    next_queue.append([next_x, next_y])
    queue = next_queue
    turn += 1

if goal >= 0:
    print(white_num - goal)
else:
    print(-1)

Solution (Python):




h,w = map(int,input().split())
board = [["
num_black = 0
for i in range(h):
    s = input()
    for j in range(w):
        board[i+1][j+1] = str(s[j])
        if s[j] == "
            num_black += 1
path = 0 
from collections import deque
mv = ((1,0),(-1,0),(0,1),(0,-1))
visit = deque()
start_pos = (1,1)
visit.append(start_pos)
cnt = [[-1]*(w+2) for _ in range(h+2)] 
cnt[1][1] = 0 
while visit:
    point = visit.popleft()
    
    for k in mv:
        pos = (point[0]+k[0],point[1]+k[1])
        
        if board[pos[0]][pos[1]] == ".":
            if cnt[pos[0]][pos[1]] == -1: 
                
                cnt[pos[0]][pos[1]] = cnt[point[0]][point[1]] + 1
                visit.append((pos[0],pos[1]))
                if pos[0] == h and pos[1] == w:
                    path = cnt[pos[0]][pos[1]]
                    break
if path == 0: print(-1)
else: print(h*w - path - num_black -1)

Solution (Python):
from collections import deque
import numpy as np
H, W = map(int, input().split())
maze = [list(input()) for _ in range(H)]
w = 0
for i in range(H):
    w += maze[i].count(".")
inf = 10**9
d = np.array([[inf]*W for _ in range(H)])
d[0][0] = 0
q = deque([])
q.append([0, 0])
nx, ny = 0, 0
dx = [0, 0, -1, 1]
dy = [1, -1, 0, 0]
while len(q) > 0:
    p = q.popleft()
    if p[0] == H and p[1] == W:
        break
    for i in range(4):
        nx = p[1] + dx[i]
        ny = p[0] + dy[i]
        if nx >= 0 and ny >= 0 and nx < W and ny < H and d[ny][nx] == inf and maze[ny][nx]==".":
            q.append([ny, nx])
            d[ny][nx] = d[p[0]][p[1]] + 1
if d[H-1][W-1] == inf:
	print(-1)
else:
	print(w-(d[H-1][W-1]+1))

Solution (Python):
import collections

H,W = list(map(int,input().split()))
field = [["

white = 0
for i in range(H):
    field.append(list(input()))
    counter = collections.Counter(field[-1])
    white += counter["."]
    field[-1].insert(0,"
    field[-1].append("
field.append(["

queue = collections.deque()
queue.append((1,1))

distances = [[-1]*(W+2) for i in range(H+2)]
distances[1][1] = 0

while queue:
    y,x = queue.popleft()
    for i,j in ([1, 0], [-1, 0], [0, 1], [0, -1]):
        newx,newy = x+i,y+j
        if field[newy][newx] == "." and distances[newy][newx] == -1:
            distances[newy][newx] = distances[y][x]+1
            if (newy,newx) == (H,W):
                break
            else:
                queue.append((newy,newx))

if distances[H][W] == -1:
    print(-1)
else:
    print(white-distances[H][W]-1)

Solution (Python):
from collections import deque
h,w=map(int,input().split())
maze=[input() for i in range(h)]
visited=[[-1]*w for i in range(h)]
aw=0
for i in range(h):
  aw+=maze[i].count('.')
def bfs(maze,visited):
  q=deque([[0,0]])
  visited[0][0]=1
  while q:
    x,y=q.popleft()
    if [x,y]==[h-1,w-1]:
      return True,visited[x][y]
    for i,j in [[0,1],[1,0],[0,-1],[-1,0]]:
      newx,newy=x+i,y+j
      if 0<=newx<h and 0<=newy<w:
        if maze[newx][newy]!='
          visited[newx][newy]=visited[x][y]+1
          q.append([newx,newy])
  return False,-1
ok,path=bfs(maze,visited)
if ok:
  print(aw-path)
else:
  print(path)

Solution (Python):
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] == '
            continue
        used.add((xi, yj))
        que.append((xi, yj, cost + 1))
if res:
    print(C - 1 - res)
else:
    print(-1)

Solution (Python):
from collections import deque
h, w = map(int, input().split())
black = 0
v = [""] * h
for i in range(h):
    v[i] = input()
    for c in v[i]:
        black += c == '

d = [[(10 ** 18)]*w for j in range(h)]
d[0][0] = 0

q = deque()
q.append((0, 0))
dx = [0, 1, 0, -1]
dy = [1, 0, -1, 0]
while len(q):
    y, x = q.popleft()
    for k in range(4):
        ny = y + dy[k]
        nx = x + dx[k]
        if not (0 <= ny and ny < h and 0 <= nx and nx < w):
            continue
        if v[ny][nx] == '
            continue
        if d[ny][nx] < (10 ** 18):
            continue
        d[ny][nx] = d[y][x] + 1
        q.append((ny, nx))

if d[h - 1][w - 1] == 10 ** 18:
    print(-1)
    exit()
print(h*w-black-d[h-1][w-1]-1)

Solution (Python):
from collections import defaultdict,deque
import sys,heapq,bisect,math,itertools,string,queue,copy,time
import numpy as np
sys.setrecursionlimit(10**8)
INF = float('inf')
mod = 10**9+7
eps = 10**-7
def inp(): return int(sys.stdin.readline())
def inpl(): return list(map(int, sys.stdin.readline().split()))
def inpl_str(): return list(sys.stdin.readline().split())

ans = 0
H, W = map(int, input().split())

si, sj = 0, 0
gi, gj = H-1, W-1

field = [list(input()) for _ in range(H)]


di = [1, 0, -1, 0]
dj = [0, 1, 0, -1]

dis = [[INF]*W for _ in range(H)]
dis[si][sj] = 0

dq = deque([])
dq.append([si,sj])

while dq:
    p = dq.popleft()
    if p[0] == gi and p[1] == gj:
        break
    for i in range(4):
        ni = p[0] + di[i]
        nj = p[1] + dj[i]
        if 0 <= ni < H and 0 <= nj < W and field[ni][nj] != '
            dq.append([ni,nj])
            dis[ni][nj] = dis[p[0]][p[1]]+1

path_length = dis[gi][gj]
shiro = 0
for i in range(H):
    for j in range(W):
        if field[i][j] == '.':
            shiro += 1

if path_length != INF:
    ans = shiro - path_length - 1
else:
    ans = -1
print(ans)

Solution (Python):
import collections

def bfs(si, sj, ei, ej):
    q = collections.deque()
    q.append([si, sj, 0])
    used = set()
    used.add((si, sj))
    while len(q) > 0:
        prvi, prvj, cost = q.popleft()
        for i, j in [[prvi + 1, prvj], [prvi - 1, prvj], [prvi, prvj + 1], [prvi, prvj - 1]]:
            if i < 0 or j < 0 or W <= i or H <= j or (i, j) in used:
                continue
            elif grids[j][i] == '.':
                if [i, j] == [ei, ej]:
                    return cost
                else:
                    q.append([i, j, cost + 1])
                    used.add((i, j))
    return -1


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

res = bfs(0, 0, W - 1, H - 1)
if res != -1:
    black_num = sum([row.count('
    print( H * W - black_num - 2 - res)
else:
    print(res)

Solution (Python):
from collections import deque

H,W=map(int,input().split())
H-=1
W-=1
maze=[]
for i in range(H+1):
   S=input()
   S=[c for c in S]
   maze.append(S)

maze[0][0]="S"

count=0
for i in range(H+1):
   for j in range(W+1):
      if maze[i][j]=="
         count+=1

que=deque([[0,0]])
steps=[[-1]*(W+1) for i in range(H+1)]
steps[0][0]=0
flag=True

def bfs():
      global flag
      if len(que)>=1:
         now=que.popleft()
         now_step=steps[now[0]][now[1]]
         for dx,dy in (0,-1),(1,0),(0,1),(-1,0):
               ny=now[0]+dy
               nx=now[1]+dx
               if 0<=ny<=H and 0<=nx<=W:
                     if ny==H and nx==W:
                           print((H+1)*(W+1)-(now_step+1+1)-(count))
                           flag=False
                           break
                     elif maze[ny][nx]==".":
                           maze[ny][nx]="A"
                           que.append([ny,nx])
                           steps[ny][nx]=now_step+1
                     else:
                           pass
      else:
         print(-1)
         flag=False

while(flag):
      bfs()

Solution (Python):
from collections import deque
H, W = map(int, input().split())
f_inf = float('inf')
C = [input() for _ in range(H)]

def bfs():
  dist = [[False]*W for _ in range(H)]
  D = ((1,0), (0,1), (-1,0), (0,-1))
  
  que = deque([])
  que.append((0,0))
  dist[0][0] = 0
  
  while que:
    p = que.popleft()
    for d in D:
      nx = p[0] + d[0]
      ny = p[1] + d[1]
      if H > nx >= 0 and W > ny >= 0 and C[nx][ny] != '
        que.append((nx,ny))
        dist[nx][ny] = dist[p[0]][p[1]]+1
  return dist[H-1][W-1]

cnt = 0
for c in C:
  cnt += c.count('.')
  
ans = bfs()
if ans is False:
  print(-1)
else:
  print(cnt - 1 - ans)

Solution (Python):
def gridbfs(grid,sy,sx):
    INF = 10**18

    gridy = len(grid)
    gridx = len(grid[0])

    dist = [[INF]*gridx for _ in range(gridy)]
    dist[sy][sx] = 0
    q = [(sy,sx)]
    d = 1

    while q:
        qq = []
        for y,x in q:
            for dy,dx in [(-1,0),(1,0),(0,-1),(0,1)]:
                yy,xx = y+dy, x+dx
                if not (0 <= yy < gridy and 0 <= xx < gridx):
                    continue
                if grid[yy][xx] == '
                    continue
                if dist[yy][xx] != INF:
                    continue
                dist[yy][xx] = d
                qq.append((yy,xx))
        q = qq
        d += 1

    return dist

H,W = map(int,input().split())
grid = [input() for i in range(H)]
d = gridbfs(grid,0,0)
b = 0
for h in range(H):
    for w in range(W):
        if grid[h][w] == '
            b += 1

print(max(H*W-b-d[H-1][W-1]-1,-1))