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):
import sys
readline = sys.stdin.readline
from collections import deque
INF = 10 ** 4
directions = [(-1, 0), (1, 0), (0, -1), (0, 1)]

def main():
    H, W = map(int, readline().rstrip().split())
    mat = [readline().rstrip() for _ in range(H)]
    maze = [[INF] * W for _ in range(H)]
    maze[0][0] = 0
    que = deque([(0, 0)])
    flg = True
    while que and flg:
        h, w = que.popleft()
        for dh, dw in directions:
            if 0 <= h+dh < H and 0 <= w+dw < W:
                if mat[h+dh][w+dw] == '.' and maze[h+dh][w+dw] > maze[h][w] + 1:
                    maze[h+dh][w+dw] = maze[h][w] + 1
                    que.append((h+dh, w+dw))
                if h+dh == H-1 and w+dw == W-1:
                    flg = False

    if maze[H-1][W-1] == INF:
        print(-1)
    else:
        cnt_b = sum([l.count('
        print(H * W - cnt_b - (maze[H-1][W-1] + 1))

if __name__ == '__main__':
    main()

Solution (Python):
from collections import deque

row, col = map(int, input().split())
graph = [input() for i in range(row)]

count = 0
for i in range(row):
  for j in range(col):
    if graph[i][j] == ".":
      count += 1
      
dx = [1, 0, -1, 0]
dy = [0, 1, 0, -1]


distance = [[-1]*col for _ in range(row)]
queue = deque([])
distance[0][0] = 0
queue.appendleft([0, 0])

while len(queue) > 0:
  v = queue.popleft() 

  for j in range(4):
    next_y, next_x = v[0]+dy[j], v[1]+dx[j]
    if not 0 <= next_y < row or not 0 <= next_x < col:
      continue
    if distance[next_y][next_x] != -1 or graph[next_y][next_x] == '
      continue 

    distance[next_y][next_x] = distance[v[0]][v[1]] + 1
    queue.append([next_y, next_x])
      
if distance[row-1][col-1] == -1:
  print(-1)
else:
  ans = count - distance[row-1][col-1] - 1
  print(ans)

Solution (Python):
import queue
h, w = map(int,input().split())
s = ["
for i in range(1,h+1):
    s[i] = "

d = [[-1 for i in range(w+2)] for j in range(h+2)]
d[1][1] = 1
q = queue.Queue()
q.put([1,1])

while not q.empty():
    i = q.get()
    r = d[i[0]][i[1]]
    if d[i[0]+1][i[1]] == -1 and s[i[0]+1][i[1]] == ".":
        d[i[0]+1][i[1]] = r+1
        q.put([i[0]+1,i[1]])
    if d[i[0]-1][i[1]] == -1 and s[i[0]-1][i[1]] == ".":
        d[i[0]-1][i[1]] = r+1
        q.put([i[0]-1,i[1]])
    if d[i[0]][i[1]+1] == -1 and s[i[0]][i[1]+1] == ".":
        d[i[0]][i[1]+1] = r+1
        q.put([i[0],i[1]+1])
    if d[i[0]][i[1]-1] == -1 and s[i[0]][i[1]-1] == ".":
        d[i[0]][i[1]-1] = r+1
        q.put([i[0],i[1]-1])

if d[h][w] == -1:
    print(-1)
else:
    num = 0
    for i in range(h+2):
        for j in range(w+2):
            if s[i][j] == ".":
                num += 1
    print(num-d[h][w])

Solution (Python):
from collections import deque

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

block_count = 0
for i in range(H):
    for j in range(W):
        if s[i][j] == '
            block_count += 1

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

dxdy = [(1, 0), (-1, 0), (0, 1), (0, -1)]

que = deque([])
que.append((0, 0))
d[0][0] = 1
while que:
    x, y = que.popleft()
    
    for dx, dy in dxdy:
        nx = x + dx
        ny = y + dy
        if 0 <= nx < W and 0 <= ny < H and d[ny][nx] == 0 and s[ny][nx] == '.':
            que.append((nx, ny))
            d[ny][nx] = d[y][x] + 1

if d[H-1][W-1]:
    print(H * W - d[H-1][W-1] - block_count)
else:
    print(-1)

Solution (Python):
import sys
import heapq
import re
from itertools import permutations
from bisect import bisect_left, bisect_right
from collections import Counter, deque
from fractions import gcd
from math import factorial, sqrt, ceil
from functools import lru_cache, reduce
INF = 1 << 60
MOD = 1000000007
sys.setrecursionlimit(10 ** 7)


class UnionFind():
    def __init__(self, n):
        self.n = n
        self.parents = [-1] * n

    def find(self, x):
        if self.parents[x] < 0:
            return x
        else:
            self.parents[x] = self.find(self.parents[x])
            return self.parents[x]

    def union(self, x, y):
        x = self.find(x)
        y = self.find(y)

        if x == y:
            return

        if self.parents[x] > self.parents[y]:
            x, y = y, x

        self.parents[x] += self.parents[y]
        self.parents[y] = x

    def size(self, x):
        return -self.parents[self.find(x)]

    def same(self, x, y):
        return self.find(x) == self.find(y)

    def members(self, x):
        root = self.find(x)
        return [i for i in range(self.n) if self.find(i) == root]

    def roots(self):
        return [i for i, x in enumerate(self.parents) if x < 0]

    def group_count(self):
        return len(self.roots())

    def all_group_members(self):
        return {r: self.members(r) for r in self.roots()}

    def __str__(self):
        return '\n'.join('{}: {}'.format(r, self.members(r)) for r in self.roots())

def is_prime(n):
    if n == 1:
        return False
    for i in range(2,int(n**0.5)+1):
        if n % i == 0:
            return False
    return True




def warshall_floyd(d, n):
    
    for k in range(n):
        for i in range(n):
            for j in range(n):
                d[i][j] = min(d[i][j],d[i][k] + d[k][j])
    return d



def dijkstra_heap(s, edge, n):
    
    d = [10**20] * n
    used = [True] * n 
    d[s] = 0
    used[s] = False
    edgelist = []
    for a,b in edge[s]:
        heapq.heappush(edgelist,a*(10**6)+b)
    while len(edgelist):
        minedge = heapq.heappop(edgelist)
        
        if not used[minedge%(10**6)]:
            continue
        v = minedge%(10**6)
        d[v] = minedge//(10**6)
        used[v] = False
        for e in edge[v]:
            if used[e[1]]:
                heapq.heappush(edgelist,(e[0]+d[v])*(10**6)+e[1])
    return d


def factorization(n):
    arr = []
    temp = n
    for i in range(2, int(-(-n**0.5//1))+1):
        if temp%i==0:
            cnt=0
            while temp%i==0:
                cnt+=1
                temp //= i
            arr.append([i, cnt])

    if temp!=1:
        arr.append([temp, 1])

    if arr==[]:
        arr.append([n, 1])

    return arr


def lcm(x, y):
    return (x * y) // gcd(x, y)


def lcm_list(numbers):
    return reduce(lcm, numbers, 1)


def gcd_list(numbers):
    return reduce(gcd, numbers)






def eratosthenes(limit):
    A = [i for i in range(2, limit+1)]
    P = []

    while True:
        prime = min(A)
        
        if prime > sqrt(limit):
            break
            
        P.append(prime)
            
        i = 0
        while i < len(A):
            if A[i] % prime == 0:
                A.pop(i)
                continue
            i += 1
            
    for a in A:
        P.append(a)
            
    return P


def permutation_with_duplicates(L):

    if L == []:
        return [[]]

    else:
        ret = []

        
        S = sorted(set(L))

        for i in S:

            data = L[:]
            data.remove(i)

            for j in permutation_with_duplicates(data):
                ret.append([i] + j)

        return ret



h, w = map(int, input().split())
s = [[j for j in input()] for i in range(h)]


queue = deque([])
queue.append([0, 0, 0])
visited = [[0 for j in range(w)] for i in range(h)]
saitan = -1
while queue:
    y, x, cnt = queue.popleft()
    if visited[y][x] == 1 or s[y][x] == "
        continue
    visited[y][x] = 1
    if y == h - 1 and x == w - 1:
        saitan = cnt
        break
    for i in [[1, 0], [-1, 0], [0, 1], [0, -1]]:
        y2 = y + i[0]
        x2 = x + i[1]
        if 0 <= y2 < h and 0 <= x2 < w:
            queue.append([y2, x2, cnt + 1])
if saitan == -1:
    print(-1)
else:
    cnt2 = 0
    for i in range(h):
        for j in range(w):
            if s[i][j] == ".":
                cnt2 += 1
    
    print(cnt2 - saitan - 1)

Solution (Python):
from collections import deque
H,W=map(int,input().split())
G=[input() for i in range(H)]

b_n= [G[i].count("

root_min=float("inf")
root=deque([[0,0,1]])
F=[[0]*W for i in range(H)]
while len(root)!=0:
  p=root.popleft()
  if p[:2]==[H-1,W-1]:
    print(H*W-p[2]-sum(b_n))
    exit()
  F[p[0]][p[1]]=1
  for i in range(4):
    if i==0:
      n=[max(0,p[0]-1),p[1],p[2]+1]
    elif i==1:
      n=[min(H-1,p[0]+1),p[1],p[2]+1]
    elif i==2:
      n=[p[0],max(0,p[1]-1),p[2]+1]
    else:
      n=[p[0],min(W-1,p[1]+1),p[2]+1]
      
    if G[n[0]][n[1]]=="
      continue
    if F[n[0]][n[1]]==1:
      continue
    if n in root:
      continue
    root.append(n)
print(-1)

Solution (Python):
import collections,itertools,sys
def S(): return sys.stdin.readline().rstrip()
def LI(): return list(map(int,sys.stdin.readline().rstrip().split()))
H,W = LI()
s = [S() for _ in range(H)]
black_count = 0
for i,j in itertools.product(range(H),range(W)):
    if s[i][j]=='
        black_count += 1
dhdw = [[-1,0],[1,0],[0,-1],[0,1]]
min_dist = [[-1]*W for _ in range(H)]
seen = [[0]*W for _ in range(H)]
queue = collections.deque() 
def bfs():
    seen[0][0] = 1
    queue.append([0,0])
    min_dist[0][0] = 1
    while queue:
        qh,qw = queue.popleft()
        for dh,dw in dhdw:
            nh,nw = qh+dh,qw+dw
            if not(0<=nh<=H-1) or not(0<=nw<=W-1) or seen[nh][nw] or s[nh][nw]=='
                continue
            if [nh,nw]==[H-1,W-1]:
                return min_dist[qh][qw]+1
            seen[nh][nw] = 1
            queue.append([nh,nw])
            min_dist[nh][nw] = min_dist[qh][qw]+1
    else:
        return -1
min_dist = bfs()
print(H*W-black_count-min_dist if min_dist!=-1 else -1)

Solution (Python):
import collections,itertools,sys
def S(): return sys.stdin.readline().rstrip()
def LI(): return list(map(int,sys.stdin.readline().rstrip().split()))
H,W = LI()
s = [S() for _ in range(H)]
black_count = 0
for i,j in itertools.product(range(H),range(W)):
    if s[i][j]=='
        black_count += 1
dhdw = [[-1,0],[1,0],[0,-1],[0,1]]
min_dist = [[-1]*W for _ in range(H)]
seen = [[0]*W for _ in range(H)]
queue = collections.deque() 
def bfs():
    seen[0][0] = 1
    queue.append([0,0])
    min_dist[0][0] = 1
    while queue:
        qh,qw = queue.popleft()
        for dh,dw in dhdw:
            nh,nw = qh+dh,qw+dw
            if not(0<=nh<=H-1) or not(0<=nw<=W-1) or seen[nh][nw] or s[nh][nw]=='
                continue
            seen[nh][nw] = 1
            queue.append([nh,nw])
            min_dist[nh][nw] = min_dist[qh][qw]+1
bfs()
if min_dist[H-1][W-1]!=-1:
    print(H*W-black_count-min_dist[H-1][W-1])
else:
    print(-1)

Solution (Python):
from collections import deque
H, W = map(int, input().split())
area = [['
space = 0
for i in range(H):
    temp = ['
    for t in temp:
        if t=='.': space+=1 
    area.append(temp)
area.append(['
move = ((1, 0), (-1, 0), (0, 1), (0, -1))

dq = deque([(1,1)])
dist = [[-1]*(W+2) for _ in range(H+2)]
dist[1][1] = 1

while dq:
    nowx, nowy = dq.popleft()
    
    for dx, dy in move:
        nxtx, nxty = nowx+dx, nowy+dy
        if not 0<=nxtx<W+2 and 0<=nxty<H+2: continue
        if dist[nxty][nxtx]>=0 or area[nxty][nxtx]=='
        dist[nxty][nxtx] = dist[nowy][nowx]+1
        dq.append((nxtx, nxty))
if dist[H][W]==-1: print(-1)
else: print(space-dist[H][W])

Solution (Python):
import queue
h,w = map(int,input().split())

city = [list(input()) for i in range(h)]
count = [[-1]*w for i in range(h)]
dx = [0,1,0,-1]
dy = [1,0,-1,0]
que = queue.Queue()

white = 0
for i in range(h):
  for j in range(w):
    if city[i][j] == ".":
      white += 1

def short():
  que.put([0,0])
  count[0][0] = 0
  while not que.empty():
    p = que.get()
    if p[0] == h-1 and p[1] == w-1:
      exit
    for i in range(4):
      ny = p[0] + dy[i]
      nx = p[1] + dx[i]
      if 0 <= nx < w and 0 <= ny < h and city[ny][nx] != "
        que.put([ny,nx])
        count[ny][nx] = count[p[0]][p[1]] + 1    
  return count[h-1][w-1]

if short() >= 0:
  print(white - short() - 1)
else:
  print(short())

Solution (Python):
h,w = map(int,input().split())
mapl = [list(input()) for i in range(h)]
searched = [[0 for i in range(w)] for j in range(h)]
s_queue = []
move = ((0,1),(1,0),(-1,0),(0,-1))
def bfs():
    cnt=1
    s_queue.append([0,0,cnt])
    searched[0][0] = 1
    while(len(s_queue)>0):
        y,x,cnt=s_queue.pop(0)
        for a,b in move:
            ny = y+a
            nx = x+b
            if(ny<0 or ny>=h or nx<0 or nx>=w or mapl[ny][nx]=='
                continue
            if(searched[ny][nx]==1):
                continue
            s_queue.append([ny,nx,cnt+1])
            searched[ny][nx]=1
            if(ny==(h-1) and nx==(w-1)):
                return cnt+1
    return -1

cnt = bfs()
if(cnt==(-1)):
    print(cnt)
else:
    dot_c = sum(map(lambda x:x.count('.'),mapl))
    print(dot_c-cnt)

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

Solution (Python):
import queue

h, w = map(int, input().split())
s = '
for _ in range(h):
    s += '
s += '

def bfs():
    step = [0]*(w+2)*(h+2)
    step[w+2+1] = 1
    q = queue.Queue()
    q.put(w+3)
    while not q.empty():
        x = q.get()
        for i in (1, -1, w+2, -w-2):
            if s[x+i] == '
                continue
            if x+i == (w+2)*(h+1) - 2:
                step[x+i] = step[x] + 1
                return step[x+i]
            if step[x+i] == 0:
                step[x+i] = step[x] + 1
                q.put(x+i)
    print(-1)
    exit()

count = 0
for j in range((w+2)*(h+2)):
    if s[j] == '.':
        count += 1

print(count - bfs())

Solution (Python):
from sys import stdin, setrecursionlimit
from collections import deque

setrecursionlimit(10 ** 9)


def input():
    return stdin.readline().strip()


def main():
    H, W = map(int, input().split())
    s = [input() for _ in range(H)]

    gx, gy = H - 1, W - 1
    q = deque([(0, 0)])
    dist = [[-1] * W for _ in range(H)]
    dist[0][0] = 1

    while q:
        x, y = q.popleft()
        if x == gx and y == gy:
            break

        for dx, dy in ((-1, 0), (1, 0), (0, -1), (0, 1)):
            nx, ny = x + dx, y + dy
            if 0 <= nx < H and 0 <= ny < W and dist[nx][ny] == -1 and s[nx][ny] == '.':
                q.append((nx, ny))
                dist[nx][ny] = dist[x][y] + 1

    if dist[gx][gy] == -1:
        print(-1)
    else:
        ans = sum(row.count('.') for row in s) - dist[gx][gy]
        print(ans)

if __name__ == '__main__':
    main()

Solution (Python):
from sys import stdin, setrecursionlimit
from collections import deque

setrecursionlimit(10 ** 9)


def input():
    return stdin.readline().strip()


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

gx, gy = H - 1, W - 1
q = deque([(0, 0)])
dist = [[-1] * W for _ in range(H)]
dist[0][0] = 1

while q:
    x, y = q.popleft()
    if x == gx and y == gy:
        break

    for dx, dy in ((-1, 0), (1, 0), (0, -1), (0, 1)):
        nx, ny = x + dx, y + dy
        if 0 <= nx < H and 0 <= ny < W and dist[nx][ny] == -1 and s[nx][ny] == '.':
            q.append((nx, ny))
            dist[nx][ny] = dist[x][y] + 1

if dist[gx][gy] == -1:
    print(-1)
else:
    ans = sum(row.count('.') for row in s) - dist[gx][gy]
    print(ans)

Solution (Python):
m,n=map(int,input().split())
l=[]
ans=[]
for i in range(m):
  l.append(input())
  ans.append([-1]*n)
ans[0][0]=0
memo=[[-1,0],[1,0],[0,1],[0,-1]]
from collections import deque
d = deque([[0,0]])
while d:
  no=d.popleft()
  for me in memo:
    now=[0,0]
    for i in range(2):
      now[i]=no[i]+me[i]
    if min(now)<0 or now[0]>m-1 or now[1]>n-1 or l[now[0]][now[1]]=='
      pass
    else:
      d.append(now)
      ans[now[0]][now[1]]=ans[no[0]][no[1]]+1
if ans[-1][-1]<0:
  print(-1)
else:
  a=n*m-ans[-1][-1]-1
  for i in range(m):
    for j in range(n):
      if l[i][j]=='
        a-=1
  print(a)

Solution (Python):
from collections import deque

INF = float("inf")


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

maze = [input() for i in range(H)]


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




def bfs():
    que = deque([])
    
    d = [[INF]*W for i in range(H)]

    
    que.append([0,0])
    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):
            nx = p[0] + dx[i]
            ny = p[1] + dy[i]

            
            if 0<=nx and nx<H and 0<=ny and ny<W and maze[nx][ny] != '
                
                que.append([nx,ny])
                d[nx][ny] = d[p[0]][p[1]] + 1
    
    return d[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 < INF:
    print(white - bfs() - 1)
else:
    print(-1)

Solution (Python):
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] == gx and p[1] == gy:
            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] != "
                que.append((nx, ny))
                d[nx][ny] = d[p[0]][p[1]] + 1

    return d[gx][gy]


h, w = 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)

Solution (Python):
h, w = map(int, input().split())
s = [list(input()) for _ in range(h)]
ans = 0
dist = [[0] * w for _ in range(h)]
dist[0][0] = 1
queue = [(0, 0)]
cnt = 0
while len(queue) > 0:
    n_h, n_w = queue.pop(0)
    for i, j in ([0, 1], [1, 0], [0, -1], [-1, 0]):
        y, x = n_h + i, n_w + j
        if 0 <= x < w and 0 <= y < h:
            if s[y][x] == "." and dist[y][x] == 0:
                dist[y][x] = dist[n_h][n_w] + 1
                queue.append([y, x])

if dist[-1][-1] == 0:
    print(-1)
    exit()
for i in range(h):
    for j in range(w):
        if s[i][j] == ".":
            ans += 1
    
print(ans - dist[h - 1][w - 1])

Solution (Python):

from collections import deque


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


def bfs():
    moves = ((1, 0), (0, 1), (-1, 0), (0, -1))
    dists = [[-1] * W for _ in range(H)]
    dists[0][0] = 0
    que = deque()
    que.append((0, 0))
    while len(que):
        ch, cw = que.popleft()
        for dh, dw in moves:
            nh, nw = ch + dh, cw + dw
            if (    0 <= nh < H 
                and 0 <= nw < W 
                and S[nh][nw] == '.' 
                and dists[nh][nw] == -1):
                dists[nh][nw] = dists[ch][cw] + 1
                que.append((nh, nw))

    return dists[-1][-1]


def solve():
    dist = bfs()
    if dist == -1:
        print(-1)
        exit()
    white = sum([1 for row in S for i in row if i == '.'])
    print(white - dist - 1)


solve()

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

allcnt = 0
for i in range(w):
    for j in range(h):
        if block[j][i] == '.':
            allcnt += 1
import sys
sys.setrecursionlimit(10**6)

INF = float('inf')
AR = [[INF] * w for _ in range(h)]
from collections import deque

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

Solution (Python):
from collections import deque 

def main():
    H, W = map(int, input().split())
    s = []
    num = 0
    for i in range(H):
        s.append(list(input()))
        num += s[i].count("
    ans = -1    
    cnt = [[0 for _ in range(W)] for _ in range(H)]
    queue = deque()
    queue.append((0, 0))
    while queue:
        x, y = queue.popleft()
        if(s[x][y] == "
            continue
        if(x == H-1 and y == W-1):
            ans = cnt[x][y]
        s[x][y] = "
        
        d = [(-1, 0), (1, 0), (0, 1), (0, -1)]
        for dx, dy in d:
            nx = x + dx
            ny = y + dy
            if(nx < 0 or nx >= H or ny < 0 or ny >= W):
                continue
            queue.append((nx, ny))
            if(s[nx][ny] != "
                cnt[nx][ny] = cnt[x][y]+1
    if(ans == -1):
        print(-1)
    else:
        print(H*W-ans-num-1)
    
main()

Solution (Python):
from collections import deque
INF = 10**10
h, w = map(int, input().split())
s = [[s for s in input()] for _ in range(h)]
sx, sy = 0, 0
gx, gy = w-1, h-1

d = [[INF for _ in range(w)] for _ in range(h)]
d[0][0] = 0
que = deque([])
que.append([sx, sy])

x_ = [1, 0, -1, 0]
y_ = [0, 1, 0, -1]

while que:
    x, y = que.popleft()
    if x == gx and y == gy: break
    for dx, dy in zip(x_, y_):
        cx, cy = x + dx, y + dy
        if cx != -1 and cy != -1 and cx != w and cy != h and s[cy][cx] != "
            que.append([cx, cy])
            d[cy][cx] = d[y][x] + 1
if d[h-1][w-1] == INF:
    print(-1)
    exit()
cnt = 0
for hi in range(h):
    for wi in range(w):
        if s[hi][wi] == "
            cnt += 1
print(h*w - d[h-1][w-1] - 1 - cnt)

Solution (Python):
from collections import deque

H,W = map(int,input().split())
s = [list(input()) for _ in range(H)]
c = [[-1 for _ in range(W)] for _ in range(H)]

black=0
for tate in s:
  for yoko in tate:
    if yoko=="
      black += 1

def search(y,x,H,W,c,i):
  child=[]      
  if y<H-1:
    if s[y+1][x]=="." and c[y+1][x]==-1:
      c[y+1][x]=i
      child.append([y+1,x])
  if 0<y:
    if s[y-1][x]=="." and c[y-1][x]==-1:
      c[y-1][x]=i
      child.append([y-1,x])
  if 0<x:
    if s[y][x-1]=="." and c[y][x-1]==-1:
      c[y][x-1]=i
      child.append([y,x-1])
  if x<W-1:
    if s[y][x+1]=="." and c[y][x+1]==-1:
      c[y][x+1]=i
      child.append([y,x+1])
  return child

def dfs(y,x,c):
  visited=[[y,x]]
  c[y][x]=0
  i=1
  
  while visited:
    tmp=[]
    for a in visited:
      p=search(a[0],a[1],H,W,c,i)  
      tmp += p
    visited=tmp
    i += 1

dfs(0,0,c)
a=c[-1][-1]
if a==-1:
  print(-1)
else:
  print(H*W-black-a-1)

Solution (Python):
from collections import deque
h,w=map(int,input().split())
s=[input() for _ in range(h)]
def bfs(i,j):
  seen=[[-1]*w for _ in range(h)]
  todo=deque([(i,j)])
  seen[i][j]=0
  while len(todo)>0:
    (i,j)=todo.popleft()
    if i>0 and seen[i-1][j]==-1 and s[i-1][j]=='.':
      seen[i-1][j]=seen[i][j]+1
      todo.append((i-1,j))
    if i>0 and seen[i-1][j]==-1 and s[i-1][j]=='
      seen[i-1][j]=0
    if i<h-1 and seen[i+1][j]==-1 and s[i+1][j]=='.':
      seen[i+1][j]=seen[i][j]+1
      todo.append((i+1,j))
    if i<h-1 and seen[i+1][j]==-1 and s[i+1][j]=='
      seen[i+1][j]=0
    if j>0 and seen[i][j-1]==-1 and s[i][j-1]=='.':
      seen[i][j-1]=seen[i][j]+1
      todo.append((i,j-1))
    if j>0 and seen[i][j-1]==-1 and s[i][j-1]=='
      seen[i][j-1]=0
    if j<w-1 and seen[i][j+1]==-1 and s[i][j+1]=='.':
      seen[i][j+1]=seen[i][j]+1
      todo.append((i,j+1))
    if j<w-1 and seen[i][j+1]==-1 and s[i][j+1]=='
      seen[i][j+1]=0
  return seen[-1][-1]
b=bfs(0,0)
if b==-1:
  print(-1)
  exit()
c=0
for si in s:
  c+=si.count('.')
print(c-b-1)

Solution (Python):
from collections import deque
H, W=map(int, input().split(" "))
field=[list(input()) for _ in range(H)]
dist=[[-1]*W for _ in range(H)]
que=deque([[0,0]])
dist[0][0]=0
dx=[1,0,-1,0]
dy=[0,1,0,-1]
cnt=0

while que:
    y, x=que.popleft()
    if [y, x]==[H-1, W-1]:
        break
    for i in range(4):
        nx = x + dx[i]
        ny = y + dy[i]
        if (0<=nx<W and 0<=ny<H and field[ny][nx]=="." and dist[ny][nx]==-1):
            dist[ny][nx]=dist[y][x]+1
            que.append([ny, nx])

if dist[H-1][W-1]!=-1:
    for j in range(H):
        for k in range(W):
            if field[j][k]=="
                cnt+=1
    print(H*W-dist[H-1][W-1]-cnt-2+1)
else:
    print("-1")

Solution (Python):
from collections import deque

def bfs():
  queue = deque([[0, 0]])
  visited[0][0] = 0
  while queue:
    y, x = queue.popleft()
    if [y, x] == [h-1, w-1]:
      return visited[y][x]

    for j, k in ([1, 0], [-1, 0], [0, 1], [0, -1]):
      new_y, new_x = y+j, x+k
      if not (0 <= new_y < h) or not (0 <= new_x < w):
        continue

      if maze[new_y][new_x] == "." and visited[new_y][new_x] == -1:
        visited[new_y][new_x] = visited[y][x] + 1
        queue.append([new_y, new_x])

h,w = map(int, input().split())

maze=[]
w_space=0
for _ in range(h):
  t=input()
  maze.append(t)
  w_space += t.count(".")
visited = [[-1]*w for _ in range(h)]

ans = bfs()
if ans and ans != -1:
  print(w_space - ans - 1)
else:
  print(-1)

Solution (Python):

from collections import deque
def bfs(i):
    q=deque()
    q.append((0, 0))

    d = ((1, 0), (0, 1), (-1, 0), (0, -1))
    log = [[0] * w for i in range(h)]
    log[0][0] = 1

    while q:
        
        x, y=q.popleft()
        for dx, dy in d:
            nx = x + dx
            ny = y + dy
            if not(0 <= nx < h and 0 <= ny <w):continue
            if s[nx][ny] == '
            if log[nx][ny] != 0:continue
            log[nx][ny] = log[x][y] + 1
            if (nx + 1, ny + 1) == (h, w):
                return h * w - i - log[nx][ny]

            q.append((nx, ny))

    return -1

h, w = map(int,input().split())
s = [list(input()) for i in range(h)]

cnt = 0
for i in range(h):
    for j in range(w):
        if s[i][j] == '
ans = bfs(cnt)
print(ans)

Solution (Python):
from collections import deque, Counter

h, w = map(int, input().split())
s = []
c = Counter()
for i in range(h):
    s_ = input().rstrip()
    s.append(s_)
    c.update(list(s_))

searched = [[False] * w for i in range(h)]

d = deque([(0, 0, 1)])
clear_step = -1

while d:
    i, j, step = d.popleft()

    if searched[i][j]:
        continue
    else:
        searched[i][j] = True

    if i == h-1 and j == w-1:
        clear_step = step
        break

    if i > 0 and s[i-1][j] == '.':
        d.append((i-1, j, step+1))
    if i < h-1 and s[i+1][j] == '.':
        d.append((i+1, j, step+1))
    if j > 0 and s[i][j-1] == '.':
        d.append((i, j-1, step+1))
    if j < w-1 and s[i][j+1] == '.':
        d.append((i, j+1, step+1))

if clear_step >= 0:
    print(c['.']-clear_step)
else:
    print(-1)

Solution (Python):
"""
最高得点＝初期状態の白タイルの数 - ゴールまでの最短経路上の白タイルの数

まず、白タイルの数を全部数える。
次に、BFSで探索を行い、最短経路を求める。
"""
from collections import deque
H,W = map(int,input().split())
maze = [list(input()) for _ in range(H)]
default = 0
for i in range(H):
    for j in range(W):
        if maze[i][j] == ".":
            default += 1

que = deque()
que.append((0,0,1))
patterns = [(1,0),(-1,0),(0,1),(0,-1)]
count = 0
while que:
    y,x,cost = que.popleft()
    if y == H-1 and x == W-1:
        count = cost
        break
    for a,b in patterns:
        if 0<=y+a<H and 0<=x+b<W and maze[y+a][x+b]==".":
            maze[y+a][x+b] = "o"
            que.append((y+a,x+b,cost+1))


if count == 0:
    print(-1)
else:
    print(default-count)

Solution (Python):
from collections import deque 
H, W = map(int, input().split())
graph = [list(input()) for _ in range(H)]
dist = [[-1] * W for _ in range(H)]
q = deque([(0,0)])
dist[0][0] = 1
while q:
  x, y = q.popleft()
  if(x >= 1):
    if(dist[x-1][y] < 0 and graph[x-1][y] == '.'):
      dist[x-1][y] = dist[x][y] + 1
      q.append((x-1, y))
  if(x <= H-2):
    if(dist[x+1][y] < 0 and graph[x+1][y] == '.'):
      dist[x+1][y] = dist[x][y] + 1
      q.append((x+1, y))
  if(y >= 1):
    if(dist[x][y-1] < 0 and graph[x][y-1] == '.'):
      dist[x][y-1] = dist[x][y] + 1
      q.append((x, y-1))
  if(y <= W-2):
    if(dist[x][y+1] < 0 and graph[x][y+1] == '.'):
      dist[x][y+1] = dist[x][y] + 1
      q.append((x, y+1))
      
cnt = 0
if(dist[H-1][W-1] == -1):
  print(-1)
else:
  for i in range(H):
    for j in range(W):
      if(graph[i][j] == '
        cnt += 1
  print(H*W-cnt-dist[H-1][W-1])

Solution (Python):
from collections import deque
h,w = map(int, input().split())
G = [['
white = 0
for i in range(h):
    G.append(['
    white += G[i+1].count('.')
G.append(['

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)