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
from collections import deque
H,W=map(int,input().split())
s=[[c for c in l.strip()] for l in sys.stdin]
maze=[[-1]*W for i in range(H)]
dy=[1,0,-1,0]
dx=[0,1,0,-1]
q=deque([])
q.append((0,0))
maze[0][0]=0
kabe=0
while(q):
  c=q.popleft()
  for i in range(4):
    if(c[0]+dy[i]>=0 and c[0]+dy[i]<H and c[1]+dx[i]>=0 and c[1]+dx[i]<W):
      if(s[c[0]+dy[i]][c[1]+dx[i]]=="." and maze[c[0]+dy[i]][c[1]+dx[i]]==-1):
        q.append((c[0]+dy[i],c[1]+dx[i]))
        maze[c[0]+dy[i]][c[1]+dx[i]]=maze[c[0]][c[1]]+1
        
for i in range(H):
  kabe+=s[i].count("
if(maze[H-1][W-1]==-1):
  print(-1)
else:
  print(H*W-kabe-1-maze[H-1][W-1])

Solution (Python):
import sys
input = lambda: sys.stdin.readline().rstrip() 
from collections import deque

def resolve():
    H, W = map(int, input().split())
    s = []
    white_num = 0
    for i in range(H):
        s.append(input())
        white_num += s[i].count('.')

    dir = ((0, 1), (1, 0), (0, -1), (-1, 0))
    dist = [[-1]*W for _ in range(H)]
    que = deque()
    que.append((0, 0))
    dist[0][0] = 0

    while len(que)>0:
        now_y, now_x = que.popleft()
        if now_y==H-1 and now_x==W-1:
            break
        for dy, dx in dir:
            next_y = now_y+dy
            next_x = now_x+dx
            if 0<=next_y<H and 0<=next_x<W and s[next_y][next_x]=='.' and dist[next_y][next_x]==-1:
                que.append((next_y, next_x))
                dist[next_y][next_x] = dist[now_y][now_x] + 1

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

if __name__ == '__main__':
    resolve()

Solution (Python):
import sys
IS = lambda: sys.stdin.readline().rstrip()
II = lambda: int(IS())
MII = lambda: list(map(int, IS().split()))
MIIZ = lambda: list(map(lambda x: x-1, MII()))
from collections import deque, Counter

def main():

    h, w = MII()
    h += 2; w += 2
    grid = '
    for _ in range(h-2):
        grid += '
    grid += '

    if grid[1+w] == '

    c = Counter(grid)
    dot = c['.']

    def bfs(start, goal):
        INF = 10**9
        dist = [INF] * (h*w)
        dist[start] = 1
        q = deque([start])
        while q:
            v = q.popleft()
            if v == goal: return dist[v]
            dv = dist[v]
            for mv in (-1,1,w,-w):
                x = v + mv
                if grid[x] == '
                dw = dv + 1
                if dw >= dist[x]: continue
                dist[x] = dw
                q.append(x)
        return -1
    res = bfs(1+w, (h-1)*w-2)
    if res == -1: print(-1); exit(0)
    print(dot-res)


if __name__ == '__main__':
    main()

Solution (Python):
from collections import deque

h,w = map(int,input().split())
s = ["

shortest_path = [[float('inf')] * (w+1) for _ in range(h+1)]

shortest_path[1][1] = 1
q = deque([(1,1)])

while q:
    x,y = q.popleft()
    cost = shortest_path[y][x]
    for j,i in [(x-1,y),(x+1,y),(x,y-1),(x,y+1)]:
        if s[i][j] == "
            continue
        else:
            if shortest_path[i][j] > cost+1:
                q.append((j,i))
                shortest_path[i][j] = cost+1

if shortest_path[h][w] == float('inf'):
    print(-1)
else:
    print(sum( st.count(".") for st in s) - shortest_path[h][w])

Solution (Python):







def main():
    H, W = map(int, input().split())

    INF = 10**10
    n_white = 0
    s = [[-1] * (W+2) for _ in range(H+2)]
    for i in range(H):
        for j, x in enumerate(input()):
            
            s[i+1][j+1] = INF if x == "." else -1
            n_white += 1 if x == "." else 0
    s[1][1] = 0

    queue = [(1, 1)]
    queue_size = 1
    queue_idx = 0
    while True:
        
        if queue_idx == queue_size:
            
            return -1
        
        x, y = queue[queue_idx]
        queue_idx += 1
        
        if x == H and y == W:
            shortest = s[x][y]
            break

        if s[x][y-1] != -1 and s[x][y-1] > s[x][y]+1:
            s[x][y-1] = s[x][y]+1
            queue.append((x, y-1))
            queue_size += 1
        if s[x][y+1] != -1 and s[x][y+1] > s[x][y]+1:
            s[x][y+1] = s[x][y]+1
            queue.append((x, y+1))
            queue_size += 1
        if s[x-1][y] != -1 and s[x-1][y] > s[x][y]+1:
            s[x-1][y] = s[x][y]+1
            queue.append((x-1, y))
            queue_size += 1
        if s[x+1][y] != -1 and s[x+1][y] > s[x][y]+1:
            s[x+1][y] = s[x][y]+1
            queue.append((x+1, y))
            queue_size += 1
    
    return n_white - (shortest + 1)


print(main())

Solution (Python):
from collections import deque
import itertools

h,w=map(int, input().split())
d=[list(input()) for i in range(h)]
inf=10**7

def bfs():
    for i, j in itertools.product([i for i in range(h)], [j for j in range(w)]):
        if d[i][j]=='.':
            d[i][j]=inf
    que=deque([[0,0]])
    d[0][0]=0

    while que:
        y,x=que.popleft()
        for i,j in [(1,0),(0,1),(-1,0),(0,-1)]:
            ny,nx=y+i,x+j
            if nx>=0 and nx<w and ny>=0 and ny<h:
                dist=d[ny][nx]
                if dist!='
                    if dist>d[y][x]+1:
                        d[ny][nx]=d[y][x]+1
                        que.append([ny,nx])

bfs()
ans=h*w-d[h-1][w-1]-1
for i, j in itertools.product([i for i in range(h)], [j for j in range(w)]):
    if d[i][j]=='
        ans-=1
if ans>=0:
    print(ans)
else:
    print('-1')

Solution (Python):
import queue
INF = 10**8

def bfs():
    q = queue.Queue()
    q.put((sx, sy))
    d[sx][sy] = 0

    while q.empty() == False:
        now = q.get()
        if now[0] == gx and now[1] == gy:
            break

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

            if 0 <= nx < h and 0 <= ny < w and s[nx][ny] == "." and d[nx][ny] == INF:
                q.put((nx, ny))
                d[nx][ny] = d[now[0]][now[1]] + 1

h, w = map(int, input().split())
count = 0
s = [[] for i in range(h)]
for i in range(h):
    s[i] = list(input())
    for j in range(w):
        if s[i][j] == "
            count += 1

sx, sy = 0, 0
gx, gy = h - 1, w - 1
dx = [1, 0, -1, 0]
dy = [0, 1, 0, -1]
d = [[INF]*w for i in range(h)]

bfs()
if d[gx][gy] == INF:
    print(-1)
else:
    ans = h * w - (d[gx][gy] + 1 + count)
    print(ans)

Solution (Python):
from collections import deque
h, w = map(int, input().split())

grid = []
for _ in range(h):
    row = list(input())
    grid.append(row)

def bfs(grid, sy, sx, gy, gx, h, w):
    visited = [[float('inf')] * w for _ in range(h)]
    visited[sy][sx] = 1
    que = deque([(sy, sx)])
    
    dy = [-1, 0, 1, 0]
    dx = [0, 1, 0, -1]
    while que:
        y, x = que.popleft()
        for i in range(4):
            next_y = y + dy[i]
            next_x = x + dx[i]
            if 0 <= next_y < h and 0 <= next_x < w and grid[next_y][next_x] == '.' and visited[next_y][next_x] == float('inf'):
                visited[next_y][next_x] = visited[y][x] + 1
                que.append([next_y, next_x])
                if next_y == gy and next_x == gx:
                    return visited[gy][gx]
    return -1

r = bfs(grid, 0, 0, h - 1, w - 1, h, w)
if r == -1:
    print(r)
else:
    white = 0
    for i in range(h):
        for j in range(w):
            if grid[i][j] == '.':
                white += 1
    print(white - r)

Solution (Python):
from collections import deque
h, w = map(int, input().split())

grid = []
for _ in range(h):
    row = list(input())
    grid.append(row)

def bfs(grid, sy, sx, gy, gx, h, w):
    visited = [[float('inf')] * w for _ in range(h)]
    visited[sy][sx] = 1
    que = deque([(sy, sx)])
    
    dy = [-1, 0, 1, 0]
    dx = [0, 1, 0, -1]
    while que:
        y, x = que.popleft()
        for i in range(4):
            next_y = y + dy[i]
            next_x = x + dx[i]
            if 0 <= next_y < h and 0 <= next_x < w and grid[next_y][next_x] == '.' and visited[next_y][next_x] == float('inf'):
                visited[next_y][next_x] = visited[y][x] + 1
                que.append([next_y, next_x])
                if next_y == gy and next_x == gx:
                    return visited[gy][gx]
    return -1

r = bfs(grid, 0, 0, h - 1, w - 1, h, w)
if r == -1:
    print(r)
else:
    white = 0
    for i in range(h):
        for j in range(w):
            if grid[i][j] == '.':
                white += 1
    print(white - r)

Solution (Python):
from collections import deque

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

T = [[None] * W for _ in range(H)]
T[0][0] = 1
D = deque([(0, 0)])
while D:
    h, w = D.popleft()
    for dh, dw in ((1, 0), (0, 1), (-1, 0), (0, -1)):
        if 0 <= h + dh < H and 0 <= w + dw < W and S[h + dh][w + dw] == '.' and T[h + dh][w + dw] is None:
            T[h + dh][w + dw] = T[h][w] + 1
            D.append((h + dh, w + dw))

if T[H - 1][W - 1] is None:
    print(-1)
else:
    print(sum(s.count('.') for s in S) - T[H - 1][W - 1])

Solution (Python):


from collections import deque
try:
    from typing import Deque, Tuple
except ImportError:
    pass


def main():
    H, W = [int(x) for x in input().split()]
    s = [input() for _ in range(H)]
    q = deque()  
    dist = {
        (0, 0): 1,
    }
    q.append((0, 0))
    while q:
        sy, sx = q.popleft()
        for dy, dx in ((0, 1), (1, 0), (0, -1), (-1, 0)):
            ty = sy + dy
            tx = sx + dx
            if not (0 <= ty < H and 0 <= tx < W):
                continue
            if s[ty][tx] == "
                continue
            if (ty, tx) in dist:
                continue
            dist[ty, tx] = dist[sy, sx] + 1
            q.append((ty, tx))
    if (H - 1, W - 1) not in dist:
        print(-1)
        return
    print(sum(si.count(".") for si in s) - dist[H - 1, W - 1])


if __name__ == '__main__':
    main()

Solution (Python):
from collections import deque
h,w = map(int,input().split())
s = []
s.append(["
for i in range(h):
    s.append(["
s.append(["
dx = [1,0,-1,0]
dy = [0,-1,0,1]
q = deque([(1,1)])
dis = [[-1]*(w+2) for _ in range(h+2)]
dis[1][1] = 0
while q:
    x,y = q.popleft()
    for i in range(4):
        if s[x+dx[i]][y+dy[i]] == "." and dis[x+dx[i]][y+dy[i]] == -1:
                dis[x+dx[i]][y+dy[i]] = dis[x][y] +1
                q.append((x+dx[i],y+dy[i]))
count = 0
if dis[h][w] == -1:
    print(-1)
else:
    for i in range(h+2):
        for j in range(w+2):
            if s[i][j] == ".":
                count += 1
    print(count-dis[h][w]-1)

Solution (Python):
import sys
input = sys.stdin.readline




def RD(): return sys.stdin.read()
def II(): return int(input())
def MI(): return map(int,input().split())
def LI(): return list(map(int,input().split()))
def TI(): return tuple(map(int,input().split()))



from collections import deque

def main():
	h,w=MI()
	G=["
	for i in range(h):
		G+=["
	G+=["
	ans=0
	
	for i in range((h+2)*(w+2)):
		if G[i]==".":
			ans+=1

	Q=deque()
	Q.append((w+3,1))
	G[w+3]="
	f=0
	while Q:
		
		x,d=Q.popleft()
		if x==(w+2)*(h+2)-(w+2)-2:
			f=1
			break
		for dx in [-1,1,-w-2,w+2]:
			if G[x+dx]==".":
				Q.append((x+dx,d+1))
				G[x+dx]="

	if f==1:
		print(ans-d)
	else:
		print(-1)


























































if __name__ == "__main__":
	main()

Solution (Python):
import sys
input = sys.stdin.readline




def RD(): return sys.stdin.read()
def II(): return int(input())
def MI(): return map(int,input().split())
def LI(): return list(map(int,input().split()))
def TI(): return tuple(map(int,input().split()))



from collections import deque

def main():
	h,w=MI()
	G=["
	for i in range(h):
		G+=["
	G+=["
	ans=0
	
	for i in range((h+2)*(w+2)):
		if G[i]==".":
			ans+=1

	Q=deque()
	Q.append((w+3,1))
	G[w+3]="
	f=0
	while Q:
		
		x,d=Q.popleft()
		if x==(w+2)*(h+2)-(w+2)-2:
			f=1
			break
		for dx in [-1,1,-w-2,w+2]:
			if G[x+dx]==".":
				Q.append((x+dx,d+1))
				G[x+dx]="

	if f==1:
		print(ans-d)
	else:
		print(-1)


























































if __name__ == "__main__":
	main()

Solution (Python):

import sys
input = sys.stdin.readline




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

def BFS(dq):
    while dq:
        e = dq.popleft()
        y,x = e
        for i in range(4):
            yi = y+dy[i]
            xi = x+dx[i]
            if 0<=yi<Y and 0<=xi<X:
                if A[yi][xi] != "
                    A[yi][xi] = A[y][x] + 1 
                    dq.append((yi,xi))





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

Y,X = H,W
A = S

A[0][0] = 1
from collections import deque
dq = deque([(0,0)])
BFS(dq)

if A[Y-1][X-1] == ".":
    print(-1)
else:
    cnt = 0
    for a in A:
        cnt += a.count("
    print(X*Y - cnt - A[Y-1][X-1])

Solution (Python):
from sys import stdin
import collections
from sys import  setrecursionlimit
setrecursionlimit(30000)

[H, W] = [int(x) for x in stdin.readline().rstrip().split()]
data = []
for line in range(H):
    temp = stdin.readline().rstrip()
    temp_arr = []
    for j in range(len(temp)):
        temp_arr.append(temp[j])
    data.append(temp_arr)




visited = []
candidates = collections.deque()

def wfs(data, start_pos, visited, candidates):
    index = start_pos[2]
    visited.append([start_pos[0],start_pos[1]])

    
    if start_pos[0] == H-1 and start_pos[1] == W-1:
        return start_pos[2]
    
    
    for i in range(-1,2):
        for j in range(-1,2):
            if abs(i)+ abs(j)!=1:
                continue
            new_pos = [start_pos[0]+i, start_pos[1]+j,index+1]
            if new_pos[0]<0 or new_pos[0]>=H or new_pos[1]<0 or new_pos[1]>=W:
                continue
            if new_pos[:2] in visited:
                continue
            if data[new_pos[0]][new_pos[1]]==".":

                candidates.append(new_pos)
    
    while(True):
        if len(candidates)==0:
            return -1
        next_pos = candidates.popleft()
        if next_pos[:2] not in visited:
            break
        
    result = wfs(data, next_pos, visited,candidates)

    return result

def check_number(data):
    count = 0
    for i in range(H):
        for j in range(W):
            if data[i][j]==".":
                count+=1
    return count


result = wfs(data,[0,0,0],visited, candidates)
if result==-1:
    print(-1)
else:
    print(check_number(data)-result-1)

Solution (Python):
import scipy.sparse
H,W = (int(x) for x in input().split())
lines = [input() for i in range(H)]
lil = scipy.sparse.lil_matrix((H*W, H*W), dtype = int)
for i in range(H):
    for j in range(W):
        if i == j == 0: continue
        elif i == 0 and j > 0:
            if lines[0][j] == lines[0][j-1] == ".":
                lil[i*W+j, i*W+j-1] = 1
                lil[i*W+j-1, i*W+j] = 1
        elif i > 0 and j == 0:
            if lines[i][0] == lines[i-1][0] == ".":
                lil[i*W+j, (i-1)*W+j] = 1
                lil[(i-1)*W+j, i*W+j] = 1
        else:
            if lines[i][j] == lines[i][j-1] == ".":
                lil[i*W+j, i*W+j-1] = 1
                lil[i*W+j-1, i*W+j] = 1
            if lines[i][j] == lines[i-1][j] == ".":
                lil[i*W+j, (i-1)*W+j] = 1
                lil[(i-1)*W+j, i*W+j] = 1
lil2 = scipy.sparse.csgraph.dijkstra(lil, directed = False, indices=[0,H*W-1]).astype(int)
a = lil2[0][H*W-1]
if a <= 0:
    print("-1")
else:
    b = "".join(lines).count(".")
    print(b-a-1)

Solution (Python):
from collections import deque
H,W=map(int,input().split())
s=[list('X'+input()+'X') for i in range(H)]
s.append('X'*(W+2))
s.insert(0,'X'*(W+2))

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

sd=[[-1 for i in range(W+2)] for j in range(H+2)]
d=[[0,1],[0,-1],[1,0],[-1,0]]
que=deque([[1,1]])
sd[1][1]=1
while len(que)>0:
    p=que.popleft()
    if p==[H,W]:
        break
    for v in d:
        ny=p[0]+v[0]
        nx=p[1]+v[1]
        if s[ny][nx]=='.' and sd[ny][nx]==-1:
            sd[ny][nx]=sd[p[0]][p[1]]+1
            que.append([ny,nx])

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

print(wnum-sd[H][W])

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

numdot = 0
for i in s:
    numdot += i.count('.')

from collections import deque


seen = [[0 for _ in range(w)] for __ in range(h)]
seen[0][0] = 1
todo = deque([(0, 0)])
d = [(1,0,0,h-1), (0,1,1,w-1), (-1,0,0,0), (0,-1,1,0)]

while todo != deque([]):
    a = todo.popleft()
    for i in d:
        if a[i[2]] != i[3]:
            x = a[0] + i[0]
            y = a[1] + i[1]
            if s[x][y] == '.' and seen[x][y] == 0:
                todo.append((x, y))
                seen[x][y] = seen[a[0]][a[1]] + 1

    if seen[h-1][w-1] != 0:
        print(numdot - seen[h-1][w-1])
        exit()

print(-1)

Solution (Python):
from collections import deque

Height, Width = map(int, input().split())
Map = [input() for _ in range(Height)]

y_start, x_start = 0, 0
y_goal, x_goal = Height-1, Width-1

min_step_map = [[-1]*Width for _ in range(Height)]
min_step_map[y_start][x_start] = 0
reserch_point = deque()
reserch_point.append([y_start, x_start])
while len(reserch_point) > 0:
    y_now, x_now = reserch_point.popleft()

    for dy, dx in [(-1,0), (0,-1), (1,0), (0,1)]:
        y_next, x_next = y_now+dy, x_now+dx
        if (y_next <= -1 or Height <= y_next) or \
                                              (x_next <= -1 or Width <= x_next):
            continue

        if y_next == y_goal and x_next == x_goal:
            min_step_map[y_goal][x_goal] = min_step_map[y_now][x_now] + 1
            break

        if Map[y_next][x_next] == '.' and min_step_map[y_next][x_next] == -1:
            min_step_map[y_next][x_next] = min_step_map[y_now][x_now] + 1
            reserch_point.append([y_next, x_next])
        
    else:
        continue
    break

else:
    print(-1)
    exit()

min_step = min_step_map[y_goal][x_goal]
count_black = 0
for y in range(Height):
    for x in range(Width):
        if Map[y][x] == '
            count_black += 1



total_point = Height * Width - 1

score = total_point - count_black - min_step
print(score)

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

gh = h-1
gw = w-1
def bfs():
  que = deque([])
  ch = 0
  cw = 0
  d[ch][cw] = 0

  dh = [1,0,-1,0]
  dw = [0,1,0,-1]
  
  que.append([ch,cw])
  while que:
    p = que.popleft()
    if p[0] == gh and p[1] == gw:
      return
    for i in range(4):
      nh = p[0] + dh[i]
      nw = p[1] + dw[i]
      
      if nh >= 0 and nh < h and nw >=0 and nw < w and \
          d[nh][nw] == float('inf') and s[nh][nw] != '
        d[nh][nw] = d[p[0]][p[1]] + 1
        que.append([nh, nw])

d = [[float('inf') for _ in range(w)] for _ in range(h)]
bfs()
if d[gh][gw] == float('inf'):
  print(-1)
  exit()

white = 0
root = d[gh][gw]

for i in range(h):
  for j in range(w):
    if s[i][j] == '.':
      white += 1
print(white-root-1)

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

Solution (Python):
import numpy as np
H, W=map(int, input().split())
F=[]
for i in range(H):
  F.append(list(input()))
count=0
for i in range(H):
  count+=F[i].count("
INF=100000000  
F=np.array(F)
def bfs():
    
    dx=[1,0,-1,0]
    dy=[0,1,0,-1]
    
    P=[]
    
    d=np.ones((H, W))*INF
    
    sx,sy=0,0
    gx,gy=H-1,W-1
    P.append([sx, sy])
    d[sx,sy]=0
    
    
    while len(P)>0:
        
        p=P.pop(0)
        
        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 and nx<H and 0<=ny and ny<W and F[nx, ny]!="
                
                P.append([nx, ny])
                d[nx, ny]=d[p[0], p[1]]+1
    
    return d[gx, gy]
ans=bfs()
if ans==INF:
  print(-1)
else:
  print(int((H*W-count)-ans-1))

Solution (Python):
from collections import deque

def make_wall(maze,h,w):
    maze=deque(maze)
    for i in range(h):
        maze[i]="
    maze.appendleft("
    maze.append("
    return list(maze)

def bfs(maze, visited, sy, sx, gy, gx):
    queue = deque([[sy, sx]])
    visited[sy][sx] = 0
    while queue:
        y, x = queue.popleft()
        if [y, x] == [gy, gx]:
            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 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])
    return -1

h,w=map(int,input().split())
maze=[input() for _ in range(h)]
kabe=0
for i in range(h):
    kabe+=maze[i].count("
maze=make_wall(maze,h,w)
visited=[[-1]*(w+2) for _ in range(h+2)]
sy,sx=1,1
gy,gx=h,w
d=1+bfs(maze, visited, sy, sx, gy, gx)
if d==0:
    print(-1)
else:
    print(h*w-kabe-d)

Solution (Python):
from collections import deque

H, W = map(int, input().split())
s = [None] * H
count = 0

for i in range(H):
  s[i] = input()
  count += s[i].count('

adj = [[] for _ in range(W*H)]
  
dx = [-1,1,0,0]
dy = [0,0,-1,1]
  
for i in range(H):
  for j in range(W):
    if s[i][j] == '.':
      for k in range(4):
        y = i + dy[k]
        x = j + dx[k]
        if 0<=x<W and 0<=y<H:
          if s[y][x] == '.':
            adj[W*i+j].append(W*y+x)
  
queue = deque([0])
visit = [-1] * (W*H)
visit[0] = 1
  
while queue:
  now = queue.popleft()
  for u in adj[now]:
    if visit[u] < 0:
      queue.append(u)
      visit[u] = visit[now] + 1

if visit[W*H-1] == -1:
  print(-1)
else:
  print(W*H - visit[W*H-1] - count)

Solution (Python):
mod = 10 ** 9 + 7
mod2 = 2 ** 61 + 1
from collections import deque
import heapq
import time
from bisect import bisect_left, insort_left, bisect_right
import sys
import random
import itertools

input = sys.stdin.readline
_NUMINT_ALL = list(range(10))
_START_TIME = time.time()
INDEX_KETA = 10**12

def main():
    ans = solve()

    if ans is True or ans is False:
        YesNo(ans)
    elif ans is None:
        return

    if isinstance(ans, tuple):
        split_print_space(ans)
    else:
        print(ans)


def solve():

    H, W = iip()
    maze = []
    for y in range(H):
        maze.append([0 if i == "." else 1 for i in input().strip()])

    num_white = W*H - sum(flatten(maze))

    que = deque()
    que.append((0, 0, 1))

    while que:
        x, y, depth = que.popleft()
        

        for xx, yy in [(x+1, y), (x-1, y), (x, y+1), (x, y-1)]:
            if xx == -1 or xx == W or yy == -1 or yy == H:
                continue
            if maze[yy][xx] == 1:
                continue
            
            if (xx, yy) == (W-1, H-1):
                
                
                
                return num_white - depth - 1

            maze[yy][xx] = 1
            que.append((xx, yy, depth+1))

    return -1











def kiriage_warizan(a, b):
    return -(-a//b)


def iip(listed=False):  
    d = input().rstrip("\n").split()
    try:
        ret = [int(i) for i in d]
    except:
        ret = [int(i) if i in _NUMINT_ALL else i for i in d]
        if len(ret) == 1 and listed is False:
            return ret[0]

    if len(ret) == 1 and not listed:
        return ret[0]
    return ret

def iipt(l, listed=True, num_only=True):  
    if isinstance(l, list):
        l = l[0] 
    ret = []
    for i in range(l):
        ret.append(iip(listed=listed))
    return ret


def saidai_kouyakusuu(A):  
    l = len(A)
    while True:
        m = min(A)
        mx = max(A)
        if m == mx:
            return m

        for i in range(l):
            if A[i] % m == 0:
                A[i] = m
            else:
                A[i] %= m


def flatten(l):
    return list(itertools.chain.from_iterable(l))


def index_sorted(sorted_list, target):
    idx = bisect_left(sorted_list, target)
    if idx != len(sorted_list) and sorted_list[idx] == target:
        return idx
    else:
        return False


def time_debug_10percent():
    a = random.randint(0, 9)
    if a == 9:
        sys.exit()

def time_debug(t):
    time.sleep(_START_TIME + t - time.time())
    sys.exit()


def make_graph_edge_flat(N):  
    ret = []
    for i in range(N-1):
        a, b, c = iip()
        a -= 1
        b -= 1
        ret[a].append((b, c))
        ret[b].append((a, c))
    return ret


def sort_tuples(l, index):  
    if isinstance(l, list):
        l.sort(key=lambda x: x[index])
        return l
    else:
        l = list(l)
        return sorted(l, key=lambda x: x[index])


def count_elements(l):  
    d = {}
    for i in l:
        if i in d:
            d[i] += 1
        else:
            d[i] = 1
    return d


def safeget(l, index, default="exception"):  
    if index >= len(l):                      
        if default == "exception":
            raise Exception("".join(["safegetに不正な値 ", index, "が渡されました。配列の長さは", len(l), "です"]))
        else:
            return default
    elif index < 0:
        if default == "exception":
            raise Exception("".join(["safegetに不正な値 ", index, "が渡されました。負の値は許可されていません"]))
        else:
            return default
    else:
        return l[index]


def sortstr(s):  
    return "".join(sorted(s))


def iip_ord(startcode="a"):  
    if isinstance(startcode, str):
        startcode = ord(startcode)
    return [ord(i) - startcode for i in input()]


def YesNo(s):  
    if s:
        print("Yes")
    else:
        print("No")


def fprint(s):  
    for i in s:
        print(i)


def bitall(N):  
    ret = []
    for i in range(2 ** N):
        a = []
        for j in range(N):
            a.append(i % 2)
            i //= 2
        ret.append(a)
    return ret

def split_print_space(s):  
    print(" ".join([str(i) for i in s]))


def split_print_enter(s):  
    print("\n".join([str(i) for i in s]))


def soinsuu_bunkai(n):  
    ret = []
    for i in range(2, int(n ** 0.5) + 1):
        while n % i == 0:
            n //= i
            ret.append(i)
        if i > n:
            break
    if n != 1:
        ret.append(n)
    return ret


def conbination(n, r, mod, test=False):  
    if n <= 0:
        return 0
    if r == 0:
        return 1
    if r < 0:
        return 0
    if r == 1:
        return n
    ret = 1
    for i in range(n - r + 1, n + 1):
        ret *= i
        ret = ret % mod

    bunbo = 1
    for i in range(1, r + 1):
        bunbo *= i
        bunbo = bunbo % mod

    ret = (ret * inv(bunbo, mod)) % mod
    if test:
        
        pass
    return ret


def inv(n, mod):  
    return power(n, mod - 2)


def power(n, p, mod_=mod):  
    if p == 0:
        return 1
    if p % 2 == 0:
        return (power(n, p // 2, mod_) ** 2) % mod_
    if p % 2 == 1:
        return (n * power(n, p - 1, mod_)) % mod_


def nibutan_func(func, target, left, right, side="left", seido = 1): 
    l = left
    r = right
    if seido == 1:
        x = (l + r) // 2
    else:
        x = (l + r) / 2
    while r-l > seido:
        
        if seido == 1:
            x = (l + r) // 2
        else:
            x = (l + r) / 2
        if func(x) == target:
            if side == "left":
                r=x
            else:
                l=x


        elif func(x) > target:
            r = x
        else:
            
            l = x

    
    if side == "left" and func(r) == target:
        return r
    elif side != "left" and func(l) == target:
        return l
    elif side == "left":
        return l
    else:
        return r


def nibutan_list(list_, target, side="left"):  
    if not isinstance(list_, list):
        list_ = list(list_)

    l = 0
    r = len(list_)
    x = (l + r) // 2
    while r-l > 1:
        x = (l+r)//2
        if list_[x] == target:
            return x
        elif list_[x] > target:
            r = x
        else:
            l = x

    if side == "left" or list_[x] == target:
        return l
    else:
        return r


class UfTree():
    def __init__(self, maxnum):
        self.parent = list(range(maxnum))
        self._size = [1] * maxnum
        self.rank = [0] * maxnum

    def size(self, a):
        return self._size[self.root(a)]

    def root(self, a):
        rank = 0
        cur = a
        while True:
            if self.parent[cur] == cur:
                
                
                return cur
            else:
                self.parent[cur] = self.parent[self.parent[cur]]
                cur = self.parent[cur]
                rank += 1

    def unite(self, a, b):
        ra = self.root(a)
        rb = self.root(b)
        if ra == rb:
            return self

        self._size[ra] += self._size[rb]
        self.parent[rb] = ra
        return self

if __name__ == "__main__":
    main()