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):
from collections import deque

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

cnt = 0
maze = []
for i in range(h):
    t = list(input())
    cnt += t.count('.')
    maze.append(t)
    
dx = [0,0,1,-1]
dy = [1,-1,0,0]

queue = deque([(0, 0)])

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

while queue:
    y, x = queue.popleft()
    for dxi, dyi in zip(dx, dy):
        if (0<=x+dxi<w and 0<=y+dyi<h) and maze[y+dyi][x+dxi] == "." and distance[y+dyi][x+dxi] == -1:
            distance[y+dyi][x+dxi] = distance[y][x]+1
            queue.append((y+dyi, x+dxi))

if distance[h-1][w-1] != -1:
    print(cnt-(distance[h-1][w-1]+1))
else:
    print(-1)

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

Solution (Python):
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>-1and W>w>-1and M[h][w]>'
c=C[H-1][W-1];print(-1*(c<2)or sum(m.count(".") for m in M)-c)

Solution (Python):
from collections import deque
from typing import List


def main():
    h, w = 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


if __name__ == "__main__":
    main()

Solution (Python):
import heapq
H, W = map(int, input().split())
S = [list(input()) for i in range(H)]
count_black = 0
for i in range(H):
    for j in range(W):
        if S[i][j] == '
            count_black += 1
is_visited = [[False for j in range(W)] for i in range(H)]
q = []
heapq.heappush(q, (1, (0, 0)))
is_visited[0][0] = True
lrud = [[0, -1], [0, 1], [-1, 0], [1, 0]]
while q:
    cost, (x, y) = heapq.heappop(q)
    if x == H-1 and y == W-1:
        break
    for dx, dy in lrud:
        if 0 <= x + dx < H and 0 <= y + dy < W and \
            S[x+dx][y+dy] == '.' and not is_visited[x+dx][y+dy]:
            heapq.heappush(q, (cost+1, (x+dx, y+dy)))
            is_visited[x+dx][y+dy] = True
if x == H-1 and y == W-1:
    print(H*W-count_black-cost)
else:
    print(-1)

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

Solution (Python):
from collections import deque
H, W = map(int, input().split())
K = []
for i in range(H):
    A = list(input())
    K.append(A)
P = deque([[0, 0, 1]])
used = [[0]*W for _ in range(H)]
used[0][0] = 1
while(True):
    if len(P) == 0:
        break
    h, w, c = P.popleft()
    if h == H-1 and w == W-1:
        break
    for i, j in [(1, 0), (-1, 0), (0, 1), (0, -1)]:
        if 0 <= h+i <= H-1:
            if 0 <= w+j <= W-1:
                if K[h+i][w+j] == ".":
                    if used[h+i][w+j] == 0:
                        used[h+i][w+j] = 1
                        P.append([h+i, w+j, c+1])

ans = 0
for i in range(H):
    for j in range(W):
        if K[i][j] == ".":
            ans += 1
if h == H-1 and w == W-1:
    print(ans - c)
else:
    print(-1)

Solution (Python):
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] == '
    print(-1)
    exit()

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

Solution (Python):
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] == '
    print(-1)
    exit()

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

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] == 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] != "
                
                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):
from collections import deque
h,w = map(int,input().split())
maze = [['
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)

Solution (Python):
import re
import copy
import numpy as np
import queue

def accept_input():
    H,W = 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)

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

Solution (Python):

from collections import deque

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

map_ = [[10**9]*w for i in range(h)]


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


dq = deque([[0, 0, 1]])


ans = 0
while(len(dq) > 0):
    y, x, dis = dq.popleft()

    if map_[y][x] > dis:
        map_[y][x] = dis
    else:
        continue

    for i, j in [(-1, 0), (1, 0), (0, -1), (0, 1)]:
        if y+i < 0 or y+i >= h:
            continue
        if x+j < 0 or x+j >= w:
            continue
        if map_[y+i][x+j] <= dis:
            continue
        if s[y+i][x+j] == "
            continue
        else:
            dq.appendleft([y+i, x+j, dis+1])

ans = map_[-1][-1]


if ans == 10**9:
    print(-1)
else:
    print(w*h-ans-num_black)

Solution (Python):
import sys

H, W = 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] != '
            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)

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

Solution (Python):
import sys
INF = 10**18
sys.setrecursionlimit(10**6)
from collections import deque

def li():
    return [int(x) for x in input().split()]


H, W = li()

maze = []
wall_cnt = 0
for i in range(H):
    row = input()
    wall_cnt += row.count("
    maze.append(list(row))

seen = [[INF] * W for _ in range(H)]

sx, sy = 0, 0
gx, gy = W - 1, H - 1

todo = deque()

todo.append((sx, sy))
seen[sy][sx] = 0

dist = INF
while len(todo) > 0:
    x, y = todo.popleft()
    if x == gx and y == gy:
        dist = seen[y][x]
        break
    children = [(x + 1, y), (x - 1, y), (x, y + 1), (x, y - 1)]
    for child in children:
        cx, cy = child
        
        if 0 <= cx < W and 0 <= cy < H and maze[cy][cx] == '.' and seen[cy][cx] == INF:
            seen[cy][cx] = seen[y][x] + 1
            todo.append((cx, cy))

ans = H * W - wall_cnt - (dist + 1)
print(ans if dist != INF else '-1')

Solution (Python):
from collections import deque

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

sx,sy=0,0
gx,gy=H-1,W-1

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]

ans=0
cnt=0
res=bfs()
for i in range(H):
    for j in range(W):
        if maze[i][j]=='.':
            cnt+=1
if res==float('inf'):
    ans=-1
else:
    ans=cnt-res-1
print(ans)

Solution (Python):
import sys
from sys import exit
from collections import deque
from bisect import bisect_left, bisect_right, insort_left, insort_right
from heapq import heapify, heappop, heappush
from itertools import product, permutations, combinations, combinations_with_replacement
from functools import reduce
from math import gcd, sin, cos, tan, asin, acos, atan, degrees, radians

sys.setrecursionlimit(10**6)
INF = 10**20
eps = 1.0e-20
MOD = 10**9+7

def lcm(x,y):
    return x*y//gcd(x,y)
def lgcd(l):
    return reduce(gcd,l)
def llcm(l):
    return reduce(lcm,l)
def powmod(n,i,mod):
    return pow(n,mod-1+i,mod) if i<0 else pow(n,i,mod)
def div2(x):
    return x.bit_length()
def div10(x):
    return len(str(x))-(x==0)
def intput():
    return int(input())
def mint():
    return map(int,input().split())
def lint():
    return list(map(int,input().split()))
def ilint():
    return int(input()), list(map(int,input().split()))
def judge(x, l=['Yes', 'No']):
    print(l[0] if x else l[1])
def lprint(l, sep='\n'):
    for x in l:
        print(x, end=sep)
def ston(c, c0='a'):
    return ord(c)-ord(c0)
def ntos(x, c0='a'):
    return chr(x+ord(c0))
class counter(dict):
    def __init__(self, *args):
        super().__init__(args)
    def add(self,x,d=1):
        self.setdefault(x,0)
        self[x] += d
    def list(self):
        l = []
        for k in self:
            l.extend([k]*self[k])
        return l
class comb():
    def __init__(self, n, mod=None):
        self.l = [1]
        self.n = n
        self.mod = mod
    def get(self,k):
        l,n,mod = self.l, self.n, self.mod
        k = n-k if k>n//2 else k
        while len(l)<=k:
            i = len(l)
            l.append(l[i-1]*(n+1-i)//i if mod==None else (l[i-1]*(n+1-i)*powmod(i,-1,mod))%mod)
        return l[k]
def pf(x):
    C = counter()
    p = 2
    while x>1:
        k = 0
        while x%p==0:
            x //= p
            k += 1
        if k>0:
            C.add(p,k)
        p = p+2-(p==2) if p*p<x else x
    return C

H,W=mint()
s=[input() for _ in range(H)]
c=[[-1]*W for _ in range(H)]
c[0][0]=1
q=deque([(0,0)])
while q:
    x,y=q.popleft()
    for i,j in [(x-1,y),(x+1,y),(x,y-1),(x,y+1)]:
        if 0<=i<H and 0<=j<W and s[i][j]=='.' and c[i][j]<0:
            c[i][j] = c[x][y]+1
            q.append((i,j))
if c[H-1][W-1]<0:
    print(-1)
else:
    w=0
    for ss in s:
        w+=ss.count('.')
    print(w-c[H-1][W-1])

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

if __name__=="__main__":
    h,w,s = getval()
    main(h,w,s)

Solution (Python):

import sys
sys.setrecursionlimit(1000000)
from collections import deque


H, W = 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)

Solution (Python):
from collections import deque
inf = 1000000000
h, w = map(int, input().split())
root = [[-1]*w for i in range(h)]
root[0][0] = 1
s = [[] for i in range(h)]

cnt = 0
for i in range(h):
    s[i] = input()
    for j in range(w):
        if s[i][j] == '
dw = [-1, 0, 1, 0]
dh = [0, 1, 0, -1]
que = deque()
que.append([0, 0])
while len(que)>0:
    x, y = que.popleft()
    for dx, dy in zip(dw, dh):
        nx, ny = x+dx, y+dy
        if 0<=nx<w and 0<=ny<h and root[ny][nx]==-1 and s[ny][nx]=='.':
                que.append([nx, ny])
                root[ny][nx] = root[y][x] + 1
if root[h-1][w-1]<0:
    print(-1)
else:
    print(h*w - cnt - root[h-1][w-1])

Solution (Python):
from collections import deque


def main():
    h, w = map(int, input().split())
    maze = [list(input()) for _ in range(h)]

    white_count = 0
    for r in range(h):
        for c in range(w):
            if maze[r][c] == ".":
                white_count += 1

    q = deque()
    q.append((0, 0))
    dist = [[-1 for _ in range(w)] for _ in range(h)]
    dist[0][0] = 0

    while q:
        r, c = q.popleft()
        for dr, dc in ((-1, 0), (1, 0), (0, -1), (0, 1)):
            nr = r + dr
            nc = c + dc

            if not (0 <= nr < h and 0 <= nc < w):
                continue

            if maze[nr][nc] == "
                continue

            if dist[nr][nc] == -1:
                dist[nr][nc] = dist[r][c] + 1
                q.append((nr, nc))

    if dist[h - 1][w - 1] == -1:
        print(-1)
    else:
        print(white_count - dist[h - 1][w - 1] - 1)


if __name__ == "__main__":
    main()

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

cnt0 = -2
for ma in m:
  for n in ma:
    if n == ".":
      cnt0 += 1
q = deque([(0,0)])
v = [[float("inf")]*W for i in range(H)]
v[0][0] = 0
g = (H-1, W-1)
move = ((0,1), (1,0), (0,-1), (-1,0))  

cnt1 = -1

while q:
  s = q.popleft()
  for mo in move:
    ns = (s[0]+mo[0], s[1]+mo[1])
    if 0<=ns[0]<=H-1 and 0<=ns[1]<=W-1 and v[ns[0]][ns[1]]==float("inf") and m[ns[0]][ns[1]]==".":
      q.append(ns)
      if v[ns[0]][ns[1]]>v[s[0]][s[1]]+1:
        v[ns[0]][ns[1]] = v[s[0]][s[1]]+1
    if ns == g:
      cnt1 += v[g[0]][g[1]]
      break
  if ns == g:
    break

if v[g[0]][g[1]]==float("inf"):
  print(-1)
else:
  print(cnt0-cnt1)

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

Solution (Python):
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] = 0
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]+1))

Solution (Python):

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

from collections import deque
q=deque([(0,0)])
X=((-1,0),(1,0),(0,1),(0,-1))
used=[[-1]*w for i in range(h)]
used[0][0]=0
while len(q)>0:
  y,x=q.popleft()
  if y==h-1 and x==w-1:
    break
  for dy,dx in X:
    nx=x+dx
    ny=y+dy
    if nx>=0 and nx<w and ny>=0 and ny<h and s[ny][nx]=="." and used[ny][nx]==-1:
      used[ny][nx]=used[y][x]+1
      q.append((ny,nx))
      
      
cnt=0
for i in range(h):
  for j in range(w):
    if s[i][j]=="
      cnt+=1

if used[h-1][w-1]==-1:
  print(-1)
else:
  print(w*h-cnt-(used[h-1][w-1]+1))

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

Solution (Python):
from collections import deque

H, W = map(int, input().split())
w = "
white = 0
S = [w]
for _ in range(H):
    wwww = input()
    white += wwww.count(".")
    S.append("
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)

Solution (Python):





dx = (0,1,0,-1)
dy = (1,0,-1,0)


H, W = 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)

Solution (Python):

from math import floor, ceil, sqrt, factorial, log, gcd
from itertools import accumulate, permutations, combinations, product, combinations_with_replacement, chain
from bisect import bisect_left, bisect_right
from collections import Counter, defaultdict, deque
from heapq import heappop, heappush, heappushpop, heapify
import copy
import sys
INF = float('inf')
mod = 10**9+7
sys.setrecursionlimit(10 ** 6)


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





def LI(): return list(map(int, sys.stdin.buffer.readline().split()))




def I(): return int(sys.stdin.buffer.readline())





def LS(): return sys.stdin.buffer.readline().rstrip().decode('utf-8').split()




def S(): return sys.stdin.buffer.readline().rstrip().decode('utf-8')







def IR(n): return [I() for i in range(n)]







def LIR(n): return [LI() for i in range(n)]







def SR(n): return [S() for i in range(n)]







def LSR(n): return [LS() for i in range(n)]







def SRL(n): return [list(S()) for i in range(n)]


def main():
    h, w = LI()
    grid = SRL(h)
    v = [[-1] * w for i in range(h)]
    v[0][0] = 1
    q = deque()
    q.append((1, 1))

    while q:
        i, j = q.popleft()
        grid[i - 1][j - 1] = "*"
        for x, y in ((0, 1), (0, -1), (1, 0), (-1, 0)):
            if i + x < 1 or i + x > h or j + y < 1 or j + y > w or grid[i + x - 1][j + y - 1] != "." or v[i + x - 1][j + y - 1] > 0:
                continue
            v[i + x - 1][j + y -
                         1] = v[i - 1][j - 1] + 1
            q.append((i + x, j + y))

    if v[h-1][w-1] < 0:
        print(-1)
        return
    print(h*w-v[h-1][w-1]-list(chain.from_iterable(grid)).count("


if __name__ == "__main__":
    main()

Solution (Python):
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] == "
            else: continue

    
    if dist[H][W] == -1:
        print(-1)
    else:
        
        print(cnt - dist[H][W] - 1)

if __name__ == '__main__':
    main()