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


dh = [-1, 0, 1, 0]
dw = [0, 1, 0, -1]


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


def count_black():
    res = 0
    for i in range(H):
        for j in range(W):
            if G[i][j] == '
                res += 1
    return res


def minimum_step():
    dist = [[0] * W for _ in range(H)]
    dist[0][0] = 1
    que = deque([[0, 0]])

    while que:
        h, w = que.popleft()
        for i in range(4):
            nh = h + dh[i]
            nw = w + dw[i]
            if nh < 0 or nw < 0 or nh >= H or nw >= W:
                continue
            if G[nh][nw] == '
                continue
            if dist[nh][nw]:
                continue
            dist[nh][nw] = dist[h][w] + 1
            que.append([nh, nw])
    return dist[H - 1][W - 1]


def main():
    step = minimum_step()
    print(H * W - step - count_black() if step else -1)

if __name__ == "__main__":
    main()

Solution (Python):
from collections import deque


def bfs(start, goal):
    q = deque([[start]])
    visited = set()
    while q:
        path = q.popleft()
        i, j = path[-1]
        if (i, j) == goal:
            return path
        for di, dj in [(1, 0), (-1, 0), (0, 1), (0, -1)]:
            ni, nj = i + di, j + dj
            if not (0 <= ni < H and 0 <= nj < W and field[ni][nj] == "."):
                continue
            if (ni, nj) not in visited:
                q.append(path + [(ni, nj)])
                visited.add((ni, nj))
    return []


H, W = map(int, input().split())
field = [input() for _ in range(H)]
shortest_path = bfs((0, 0), (H - 1, W - 1))
if shortest_path:
    print(sum(v == "." for row in field for v in row) - len(shortest_path))
else:
    print(-1)

Solution (Python):
import sys
from collections import deque


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


def LSH(h):
    return [list(input()) for _ in range(h)]


H, W = LI()
MAP = LSH(H)
d = deque()
d.append([0, 0])
looked = [[0 for i in range(W)]for j in range(H)]
looked[0][0] = 1
move = [[1, 0], [0, 1], [-1, 0], [0, -1]]
while d:
    x = d.popleft()
    h = x[0]
    w = x[1]
    for i in move:
        a = h+i[0]
        b = w+i[1]
        if not(0 <= a < H) or not(0 <= b < W) or looked[a][b] != 0 or MAP[a][b] == "
            continue
        d.append([a, b])
        looked[a][b] = looked[h][w]+1
if looked[H-1][W-1] == 0:
    print(-1)
    sys.exit()

white = 0
for i in range(H):
    for j in range(W):
        if MAP[i][j] == ".":
            white += 1

print(white-looked[H-1][W-1])

Solution (Python):



from fractions import gcd
from itertools import combinations,permutations,accumulate, product 

from collections import deque,defaultdict,Counter
import decimal
import re
import math
import bisect














import sys
sys.setrecursionlimit(10000000)
mod = 10**9 + 7


from sys import stdin
readline = stdin.readline
def readInts():
  return list(map(int,readline().split()))
def readTuples():
    return tuple(map(int,readline().split()))
def I():
  return int(readline())
h,w = readInts()
block = [input() for _ in range(h)]

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

Solution (Python):
from collections import deque
from collections import Counter
H, W = map(int, input().split())
s = [list(input()) for _ in range(H)]
t = [[-1]*W for _ in range(H)]
q = deque([[0,0]])
t[0][0] = 0
while len(q) > 0:
  qq = q.popleft()
  dh = [-1,0,1,0]
  dw = [0,1,0,-1]
  for i in range(4):
    h = qq[0] + dh[i]
    w = qq[1] + dw[i]
    if 0 <= h < H and 0 <= w < W:
      if s[h][w] == "
      t[h][w] = t[qq[0]][qq[1]] + 1
      q.append([h,w])

X = 0
for i in range(H):
  c = Counter(s[i])
  X += c["."]
if t[H-1][W-1] == -1:
  print(-1)
else:
  print(X-1-t[H-1][W-1])

Solution (Python):
from collections import deque


def bfs(start):
    q = deque([[start]])
    visited = set()
    while q:
        path = q.popleft()
        i, j = path[-1]
        if (i, j) == (H - 1, W - 1):
            return path
        for di, dj in [(1, 0), (-1, 0), (0, 1), (0, -1)]:
            ni, nj = i + di, j + dj
            if (
                0 <= ni < H
                and 0 <= nj < W
                and field[ni][nj] != "
                and (ni, nj) not in visited
            ):
                q.append(path + [(ni, nj)])
                visited.add((ni, nj))


H, W = map(int, input().split())
field = [input() for _ in range(H)]
shortest_path = bfs((0, 0))
if shortest_path is None:
    print(-1)
    exit()
ans = 0
for i in range(H):
    for j in range(W):
        if field[i][j] == "." and (i, j) not in shortest_path:
            ans += 1
print(ans)

Solution (Python):
from collections import deque
from heapq import heapify,heappop,heappush,heappushpop
from copy import copy,deepcopy
from itertools import product,permutations,combinations,combinations_with_replacement
from collections import defaultdict,Counter
from bisect import bisect_left,bisect_right
from math import gcd,ceil,floor,factorial

from functools import reduce
from pprint import pprint
from statistics import mean,median,mode

INF = float("inf")

def mycol(data,col):
    return [ row[col] for row in data ]

def mysort(data,col,reverse_flag):
    data.sort(key=lambda x:x[col],reverse=reverse_flag)
    return data

def mymax(data):
    M = -1*float("inf")
    for i in range(len(data)):
        m = max(data[i])
        M = max(M,m)
    return M

def mymin(data):
    m = float("inf")
    for i in range(len(data)):
        M = min(data[i])
        m = min(m,M)
    return m

def mycount(ls,x):
    
    l = bisect_left(ls,x)
    r = bisect_right(ls,x)
    return (r-l)

def myoutput(ls,space=True):
    if space:
        if len(ls)==0:
            print(" ")
        elif type(ls[0])==str:
            print(" ".join(ls))
        elif type(ls[0])==int:
            print(" ".join(map(str,ls)))
        else:
            print("Output Error")
    else:
        if len(ls)==0:
            print("")
        elif type(ls[0])==str:
            print("".join(ls))
        elif type(ls[0])==int:
            print("".join(map(str,ls)))
        else:
            print("Output Error")

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

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

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

def CI(n):
    return [ int(input()) for _ in range(n) ]

def LI(n):
    return [ list(map(int,input().split())) for _ in range(n) ]

def S():
    return input()

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

def RS():
    return list(input())

def CS(n):
    return [ input() for _ in range(n) ]

def LS(n):
    return [ list(input()) for _ in range(n) ]







h,w = MI()
maze = LS(h)
sy = 1
sx = 1
gy = h
gx = w
sy -= 1
sx -= 1
gy -= 1
gx -= 1

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

def bfs(sy,sx,gy,gx):
    q = deque()
    q.append([sy,sx])
    d[sy][sx] = 0
    while q:
        y,x = q.popleft()
        if y==gy and x==gx:
            break
        else:
            for j,i in ([1,0],[0,-1],[-1,0],[0,1]):
                ny = y + j
                nx = x + i
                if nx==-1 or ny==-1 or nx==w or ny==h:
                    pass
                elif maze[ny][nx]=="
                    pass
                elif d[ny][nx]!=INF:
                    pass
                else:
                    q.append([ny,nx])
                    d[ny][nx] = d[y][x] + 1
    return d[gy][gx]

count = 0
for i in range(h):
    c = maze[i].count('.')
    count += c

d = bfs(sy,sx,gy,gx) 

if d==INF:
    print('-1')
else:
    print(count-2-(d-1))

Solution (Python):
from collections import deque
H,W = map(int,input().split())
S = [input().strip() for _ in range(H)]
dist = [[-1 for _ in range(W)] for _ in range(H)]
que = deque([(0,0,0)])
dist[0][0] = 0
while que:
    i,j,d = que.popleft()
    if j+1<W and S[i][j+1]=="." and dist[i][j+1]<0:
        dist[i][j+1] = d+1
        que.append((i,j+1,d+1))
    if i-1>=0 and S[i-1][j]=="." and dist[i-1][j]<0:
        dist[i-1][j]=d+1
        que.append((i-1,j,d+1))
    if j-1>=0 and S[i][j-1]=="." and dist[i][j-1]<0:
        dist[i][j-1]=d+1
        que.append((i,j-1,d+1))
    if i+1<H and S[i+1][j]=="." and dist[i+1][j]<0:
        dist[i+1][j]=d+1
        que.append((i+1,j,d+1))
dmin = dist[H-1][W-1]
if dmin<0:
    print(-1)
else:
    B = H*W-dmin-1
    cnt = 0
    for i in range(H):
        for j in range(W):
            if S[i][j]=="
                cnt += 1
    print(B-cnt)

Solution (Python):
import numpy as np

h, w, *s = open(0).read().split()
h = int(h)
w = int(w)
all = sum(t.count('

inf = 1 << 30
d = np.full((h + 1, w + 1), inf, dtype=np.int)

d[0][0] = 0
q = [(0, 0)]
for v in q:
    for nv in [(0, 1), (1, 0), (-1, 0), (0, -1)]:
        ny = v[0] + nv[0]
        nx = v[1] + nv[1]
        if 0 <= nx < w and 0 <= ny < h and d[ny][nx] == inf and s[ny][nx] == '.':
            d[ny][nx] = d[v[0]][v[1]] + 1
            q.append((ny, nx))

if d[h - 1][w - 1] == inf:
    print(-1)
else:
    print(h * w - (d[h - 1][w - 1] + 1) - all)

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

cnt = 0
for i in range(h):
    cnt += M[i].count('.')

M = ['
M = ['

sy, sx = 1, 1

from collections import deque
stack = deque()
stack.append((sy, sx))
visit = [[-1]*(w+2) for _ in range(h+2)]
visit[sy][sx] = 0

while stack:
    y, x = stack.popleft()
    if y == h and x == w:
        break
    for dy, dx in (-1, 0), (1, 0), (0, -1), (0, 1):
        new_y, new_x = y+dy, x+dx
        if visit[new_y][new_x] == -1 and M[new_y][new_x] != '
            visit[new_y][new_x] = visit[y][x]+1
            stack.append((new_y, new_x))
else:
    print(-1)
    exit()

print(cnt-(visit[h][w]+1))

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

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

white = len(Grid[Grid == 0])-1
nes_white = solveMase(Grid, (0,0), (H-1,W-1))
print(white-nes_white if nes_white > 0 else -1)

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

def solveMase(Grid, start, goal):
    seen = {start}
    V = [start]
    while len(V) != 0:
        v = V.pop(0)
        if v == goal:
            return Grid[goal]

        y,x = v
        nV = []
        if x > 0: nV.append((y,x-1))
        if y > 0: nV.append((y-1,x))
        if x < W-1: nV.append((y,x+1))
        if y < H-1: nV.append((y+1,x))

        for nv in nV:
            if Grid[nv] == -1 or nv in seen:
                continue
            Grid[nv] = Grid[v] + 1
            V.append(nv)
            seen.add(nv)
    return 0

white = len(Grid[Grid == 0])-1
nes_white = solveMase(Grid, (0,0), (H-1,W-1))
if nes_white > 0:
    ans = white - nes_white
else:
    ans = -1
print(ans)

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

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

already_pass = set()
already_pass.add((1, 1))
q = queue.Queue()
q.put([(1, 1), 1])

while not q.empty():
    x_y, l = q.get()
    x = x_y[0]
    y = x_y[1]
    if x == h and y == w:
        print(h * w - black_num - l)
        break
    next_xy = [(max(1, x - 1), y), (min(h, x + 1), y),
               (x, max(1, y - 1)), (x, min(w, y + 1))]
    for i in next_xy:
        if i not in already_pass and s[i[0] - 1][i[1] - 1] != "
            q.put([i, l + 1])
            already_pass.add(i)
else:
    print(-1)

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

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

s = [input() for _ in range(h)]

c = 0

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


q = deque([[0, 0]])
dist = [[10000] * w for _ in range(h)]
dist[0][0] = 0

flag = False

while len(q) > 0:
    i, j = q.popleft()
    if i == h-1 and j == w-1:
        break
    else:
        if i < h-1 and s[i+1][j] == "." and not dist[i+1][j] < 10000:
            q.append([i+1, j])
            dist[i+1][j] = dist[i][j] + 1
        if j < w-1 and s[i][j+1] == "." and not dist[i][j+1] < 10000:
            q.append([i, j+1])
            dist[i][j+1] = dist[i][j] + 1
        if i > 0 and s[i-1][j] == "." and not dist[i-1][j] < 10000:
            q.append([i-1, j])
            dist[i-1][j] = dist[i][j] + 1
        if j > 0 and s[i][j-1] == "." and not dist[i][j-1] < 10000:
            q.append([i, j-1])
            dist[i][j-1] = dist[i][j] + 1

if dist[h-1][w-1] < 10000:
    print(h * w - dist[h-1][w-1] - 1 - c)
else:
    print(-1)

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

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

A=0
for s in S:
    A+=s.count('.')

B=bfs(H,W,1,1,H,W,S)
if B>10**9:
    ans=-1
else:
    ans=A-B
print(ans)

Solution (Python):
from collections import deque

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

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

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

b = bfs(0,0,Y-1,X-1)
if b == None:
    print(-1)
else:
    print(Y*X - cnt - b - 1)

Solution (Python):
from collections import deque
H,W=map(int,input().split())
mp=[['
count=0
for _ in range(H):
    l=list(input())
    mp.append(['
    count+=l.count('.')
mp.append(['

dist=[[-1]*(W+2)for _ in range(H+2)]
Q=deque()
Q.append((1,1))
dist[1][1]=1
f=False

while Q:
    y,x=Q.popleft()
    if (y,x)==(H,W):
        f=True
        break
    for dy,dx in [(1,0),(-1,0),(0,1),(0,-1)]:
        ny=y+dy
        nx=x+dx
        if 0<=ny<H+2 and 0<=nx<W+2:
            if mp[ny][nx]=='.' and dist[ny][nx]==-1:
                Q.append((ny,nx))
                dist[ny][nx]=dist[y][x]+1

if f:
    print(count-dist[H][W])
else:
    print(-1)

Solution (Python):
from collections import deque
H,W=map(int,input().split())
mp=[['
count=0
for _ in range(H):
    l=list(input())
    mp.append(['
    count+=l.count('.')
mp.append(['

dist=[[-1]*(W+2)for _ in range(H+2)]
Q=deque()
Q.append((1,1))
dist[1][1]=1
f=False

while Q:
    y,x=Q.popleft()
    if (y,x)==(H,W):
        f=True
        break
    for dy,dx in [(1,0),(-1,0),(0,1),(0,-1)]:
        ny=y+dy
        nx=x+dx
        if 0<=ny<H+2 and 0<=nx<W+2:
            if mp[ny][nx]=='.' and dist[ny][nx]==-1:
                Q.append((ny,nx))
                dist[ny][nx]=dist[y][x]+1

if f:
    print(count-dist[H][W])
else:
    print(-1)

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

mv=[(0,-1),(0,1),(-1,0),(1,0)]
INF = H*W
depth = [[INF]*(W+2) for _ in range(H+2)]
depth[1][1] = 0
stk = deque([[1, 1]])
while len(stk)>0:
    l = stk.pop()
    
    x = l[0]
    y = l[1]
    ct = depth[x][y]
    for i, j in mv:
        nx=x+i
        ny=y+j
        if 1<=nx<=H and 1<=ny<=W and S[nx][ny]=='.' and depth[nx][ny]==INF:
            stk.appendleft([nx,ny])
            depth[nx][ny]=ct+1

if depth[H][W]==INF:
    print(-1)
else:
    dots=0
    for i in range(1,H+1):
        dots+=S[i].count('.')
    
    print(dots-depth[H][W]-1)

Solution (Python):
from collections import deque

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

q = deque()
q.append((0, 0, 0))
check = [[0]*w for _ in range(h)]

flag = False
while q:
    y, x, d = q.popleft()
    if y == h-1 and x == w-1:
        g = d
        flag = True
        break
    if check[y][x] == 0:
        check[y][x] = 1
        for xdx, ydy in zip((x, x, x+1, x-1), (y+1, y-1, y, y)):
            if (0 <= xdx < w) and (0 <= ydy < h):
                if check[ydy][xdx] == 0 and s[ydy][xdx] == '.':
                    q.append((ydy, xdx, d+1))
ss = 0
for i in s:
    ss += i.count('
print(h*w-ss-d-1 if flag else -1)

Solution (Python):
from collections import deque

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

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

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

d = deque()
d.append((0,0))

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

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

flg = False
while d:
    y, x = d.popleft()
    if (y==H-1) and (x==W-1):
        flg = True
        break

    for u, v in move:
        t = y + u
        s = x + v
        if 0 <= t and t<H and 0<=s and s<W and mazo[t][s]=="." and visited[t][s]==0:
            visited[t][s] = visited[y][x] + 1
            d.append((t, s))

if flg:
    print(H*W - cnt - visited[H-1][W-1] -1)
else:
    print(-1)

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

def get_next(x, y, costs, S, cost):
    ans = list()
    if x != 0 and costs[x-1][y] == -1 and S[x-1][y] == ".":
        ans.append([x-1, y])
        costs[x-1][y] = cost + 1

    if x != H-1 and costs[x+1][y] == -1 and S[x+1][y] == ".":
        ans.append([x+1, y])
        costs[x+1][y] = cost + 1

    if y != 0 and costs[x][y-1] == -1 and S[x][y-1] == ".":
        ans.append([x, y-1])
        costs[x][y-1] = cost + 1

    if y != W-1 and costs[x][y+1] == -1 and S[x][y+1] == ".":
        ans.append([x, y+1])
        costs[x][y+1] = cost + 1

    return ans

costs = [[-1 for _ in range(W)] for _ in range(H)]
costs[0][0] = 0
q = deque()
q.append([0, 0])
while len(q) and costs[H-1][W-1] == -1:
    now = q.popleft()
    nxt = get_next(now[0], now[1], costs, S, costs[now[0]][now[1]])
    for dot in nxt:
        q.append([dot[0], dot[1]])
    
fin_cost = costs[H-1][W-1]
if fin_cost == -1:
    print(-1)
else:
    w_cnt = 0
    for i in range(H):
        for j in range(W):
            if S[i][j] == ".":
                w_cnt += 1
    print(w_cnt - fin_cost - 1)

Solution (Python):
from collections import deque

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

def bfs():
	sx, sy= 0, 0
	gx, gy= H-1, W-1
	dx = [1, 0, -1, 0]
	dy = [0, 1, 0, -1]

	work_queue=deque([])
	work_queue.append((sx, sy))
	visited=[[float("inf")]*W for _ in range(H)]
	visited[sx][sy]=1

	while work_queue:
		x, y = work_queue.popleft()

		for i in range(4):
			nx, ny = x+dx[i], y+dy[i]

			if 0<=nx<H and 0<=ny<W and visited[nx][ny]==float("inf") and C[nx][ny]!="
				work_queue.append((nx, ny))
				visited[nx][ny]= visited[x][y]+1
	return visited[gx][gy]


temp=bfs()

black=0
white=0
for i in range(H):
	for j in range(W):
		if C[i][j]==".":
			white+=1
		else:
			black+=1

if temp==float("inf"):
	print(-1)
else:
	print(white-temp)

Solution (Python):
from collections import deque

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

def bfs():
    d = [[float("inf")] * C for _ in range(R)]
    dr = [0, -1, 0, 1]
    dc = [1, 0, -1, 0]
    que = deque([])

    que.append((sr, sc))
    d[sr][sc] = 0
    while que:
        p = que.popleft()
        if p[0] == gr and p[1] == gc:
            break
        for i in range(4):
            nr = p[0] + dr[i]
            nc = p[1] + dc[i]
            if (0 <= nr < R) and (0 <= nc < C) and masu[nr][nc] != "
                que.append((nr, nc))
                d[nr][nc] = d[p[0]][p[1]] + 1
    
    return d[gr][gc]

white = 0
for i in range(R):
    for j in range(C):
        if masu[i][j] == ".":
            white += 1

res = bfs()
if 0 < res < float("inf"):
    print(white - res - 1)
else:
    print(-1)

Solution (Python):
"""
Maze class.

cf. WarpableMaze class.
"""
import sys
from collections import deque
from typing import List, Tuple


class Maze:
    __slots__ = ["height", "width", "wall", "sentinel", "unsearched", "dist"]

    def __init__(
        self, height: int, width: int, grid: List[bytes], wall: str = "
    ) -> None:
        self.height = height + 2
        self.width = width + 2
        self.wall = -1
        self.sentinel = -2
        self.unsearched = 1 << 30
        self.dist = self._convert_grid_to_dist(grid, wall)

    def _convert_grid_to_dist(self, grid: List[bytes], wall) -> List[int]:
        """Convert a 2D grid to a 1D dist."""
        dist = [self.sentinel] * self.height * self.width
        i = self.width
        for row in grid:
            for c in row.decode():
                i += 1
                dist[i] = self.wall if c == wall else self.unsearched
            i += 2
        return dist

    def _flatten_coordinate(self, x: int, y: int) -> int:
        """Flatten 2D coordinate values.
        Values of a coordinate must be 1-origin.
        """
        return self.width * x + y

    def bfs(
        self,
        start_2d: Tuple[int, int],
        goal_2d: Tuple[int, int],
        updates_dist: bool = False,
    ) -> int:
        """BFS to compute the distance from start to goal.
        Values of start_2d and goal_2d must be 1-origin.
        """
        start = self._flatten_coordinate(*start_2d)
        goal = self._flatten_coordinate(*goal_2d)

        moves = (-self.width, self.width, -1, 1)
        dist = self.dist[:]
        dist[start] = 0
        queue = deque([start])

        while queue:
            x = queue.popleft()
            cur_dist = dist[x]
            if x == goal:
                break

            for dx in moves:
                nx = x + dx
                if dist[nx] == self.unsearched:
                    dist[nx] = cur_dist + 1
                    queue.append(nx)

        if updates_dist:
            self.dist = dist
        return dist[goal] if dist[goal] != self.unsearched else self.wall

    def debug(self) -> None:
        """Show debugging information."""

        def convert(n: int) -> str:
            if n == self.sentinel:
                return "†"
            elif n == self.wall:
                return "
            return "."

        print(f"<DEBUG>\nheight={self.height}, width={self.width}\n", file=sys.stderr)
        for row in zip(*[iter(self.dist)] * self.width):
            print(*map(convert, row), file=sys.stderr)


class BreakableMaze(Maze):
    def __init__(self, height: int, width: int, grid: List[bytes], wall: str = "
        self.start = -1
        self.goal = -1
        super().__init__(height, width, grid, wall)

    def _convert_grid_to_dist(self, grid: List[bytes], wall) -> List[int]:
        """Convert a 2D grid to a 1D dist."""
        dist = [self.sentinel] * self.height * self.width
        i = self.width
        for row in grid:
            for c in row.decode():
                i += 1
                dist[i] = self.wall if c == wall else self.unsearched
                if c == "s":
                    self.start = i
                elif c == "g":
                    self.goal = i
            i += 2
        return dist

    def breakable_bfs(self, updates_dist: bool = False) -> int:
        """BFS to compute the distance from start to goal.
        """
        moves = (-self.width, self.width, -1, 1)
        dist = self.dist[:]
        dist[self.start] = 0
        queue = deque([self.start])

        while queue:
            x = queue.popleft()
            cur_dist = dist[x]
            if x == self.goal or cur_dist > 2:
                break

            for dx in moves:
                nx = x + dx
                if dist[nx] == self.unsearched:
                    dist[nx] = cur_dist
                    queue.appendleft(nx)
                elif dist[nx] == self.wall:
                    dist[nx] = cur_dist + 1
                    queue.append(nx)

        if updates_dist:
            self.dist = dist
        return dist[self.goal]


def abc007_c():
    
    read = sys.stdin.buffer.read
    readline = sys.stdin.buffer.readline

    R, C = map(int, readline().split())
    (*start,) = map(int, readline().split())
    (*goal,) = map(int, readline().split())
    (*S,) = read().split()

    maze = Maze(R, C, S)
    print(maze.bfs(start, goal))


def abc088_d():
    
    read = sys.stdin.buffer.read
    readline = sys.stdin.buffer.readline

    H, W = map(int, readline().split())
    (*S,) = read().split()
    maze = Maze(H, W, S)

    dist = maze.bfs((1, 1), (H, W))
    if dist != -1:
        res = H * W - sum((row.decode()).count("
        print(res)
    else:
        print(-1)


def arc005_c():
    
    read = sys.stdin.buffer.read
    readline = sys.stdin.buffer.readline

    H, W = map(int, readline().split())
    (*C,) = read().split()
    maze = BreakableMaze(H, W, C)
    print("YES" if maze.breakable_bfs() <= 2 else "NO")


if __name__ == "__main__":
    
    abc088_d()

Solution (Python):
from collections import deque

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