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

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

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

    cnt = 0
    for i in range(H):
        cnt += field[i].count('.')
    
    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((0,0))
        d[0][0] = 1

        while que:
            y,x = que.popleft()
            if y == H - 1 and x == W - 1:
                return d[y][x]

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

                if 0 <= nx < W and 0 <= ny < H and field[ny][nx] != '
                    que.append((ny,nx))
                    d[ny][nx] = d[y][x] + 1

        return -1

    num = bfs()

    if num == -1:
        print(num)
    else:
        print(cnt - num)

main()

Solution (Python):
import sys
input = sys.stdin.readline
sys.setrecursionlimit(1000000)
from collections import deque
def getN():
    return int(input())
def getList():
    return list(map(int, input().split()))
import math

h, w = getList()
INF = 1000000000

dist = [[INF for i in range(w)] for j in range(h)]
grid = []
udlr = [(0, 1), (0, -1), (-1, 0), (1, 0)]

white = 0
for i in range(h):
    state = input().strip()
    grid.append(state)
    white += state.count(".")

dist[0][0] = 1
def bfs(grid, dist):
    q = deque([])
    q.append((0, 0))
    while(q):
        a, b = q.popleft()
        
        cur = dist[a][b]
        for mv in udlr:
            c, d = mv
            e, f = a + c, b + d
            if e >= 0 and e < h and f >= 0 and f < w:
                if grid[e][f] == ".":
                    if dist[e][f] > cur + 1:
                        dist[e][f] = cur + 1
                        q.append((e, f))

bfs(grid, dist)





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

else:
    print(white - dist[h-1][w-1])

Solution (Python):
from collections import deque

def dfs(stage , visited , start_x,start_y,goal_x,goal_y):
    queue = deque([[start_x,start_y]])
    visited[start_x][start_y] = 1
    while queue:
        x , y = queue.popleft()
        if [x , y] == [goal_x,goal_y]:
            return visited[x][y]

        for dx , dy in ([1,0],[-1,0],[0,1],[0,-1]):
            new_x , new_y = x + dx , dy + y
            
            if 0 <= new_x <= goal_x and 0 <= new_y <= goal_y  and stage[new_x][new_y] == "." and visited[new_x][new_y] == -1:
                
                visited[new_x][new_y] = visited[x][y] + 1
                queue.append([new_x,new_y])
    print("-1")
    exit(0)
if __name__ == "__main__":
    H , W = map(int , input().split())
    stage = []
    for _ in range(H):
        stage.append(list(input()))
    start_x,start_y ,goal_x,goal_y = 0,0,H-1,W-1
    visited = [[-1] * W for _ in range(H)]
    
    
    
    sum = 0
    for value in stage:
        sum += value.count('.')
    
    print(sum - dfs(stage,visited,start_x,start_y,goal_x,goal_y))

Solution (Python):
from collections import deque
h,w = map(int, input().split())
map = [list(input()) for _ in range(h)]
dis = [[float("inf")]*w for _ in range(h)]
dy = [1,0,-1,0]
dx = [0,1,0,-1]
que = deque([])
que.append((0,0))
dis[0][0]=1
count = 0
for i in range(h):
    for j in range(w):
        if map[i][j]=="
            count+=1

while que:
    p = que.popleft()
    if p[0]==h-1 and p[1]==w-1:
        break
    for i in range(4):
        ny = p[0] + dy[i]
        nx = p[1] + dx[i]
        if 0<=ny<h and 0<=nx<w and map[ny][nx]!="
           and dis[ny][nx]==float("inf"):
            que.append((ny,nx))
            dis[ny][nx]=dis[p[0]][p[1]]+1

print(h*w-dis[h-1][w-1]-count if dis[h-1][w-1]!=float("inf") else -1)

Solution (Python):
from queue import Queue
import sys

def check(fl, y, x):
  mark = fl[y][x]
  if mark == '.': return True
  else: return False

def run():
  q = Queue()
  H, W = map(int, input().split())
  fl_list = [['
  num_white = 0
  for h in range(H):
    fl = list('
    num_white += fl.count('.')
    fl_list.append(fl)
  fl_list.append(['
  q.put([1,1,0])
  n_list = [0, 0, 1, -1]
  i_list = [1, -1, 0, 0]
  while True:
    if q.empty(): print(-1); sys.exit()
    y, x, t = q.get()
    if (y == H) and (x == W): break
    for n, i in zip(n_list, i_list):
      if check(fl_list, y+n, x+i):
        fl_list[y+n][x+i] = '
        q.put([y+n, x+i, t+1])
      
  print(num_white - (t+1))

run()

Solution (Python):
from collections import deque
from itertools import chain


class Solver:
    def __init__(self, m):
        self.m = m
        self.label = [[-1 for _ in range(len(m[0]))] for _ in range(len(m))]

    def bfs(self, s, g):
        queue = deque()
        start = [a - 1 for a in s]
        goal = [a - 1 for a in g]
        queue.append(start)
        self.label[start[0]][start[1]] = 0
        while len(queue) > 0:
            node = queue.popleft()
            y, x = node
            dist = self.label[y][x] + 1
            if y > 0:
                if self.m[y - 1][x] != "
                    if y-1 == goal[0] and x == goal[1]:
                        return dist
                    else:
                        queue.append([y - 1, x])
                        self.label[y - 1][x] = dist
            if y < len(self.m)-1:
                if self.m[y + 1][x] != "
                    if y+1 == goal[0] and x == goal[1]:
                        return dist
                    else:
                        queue.append([y + 1, x])
                        self.label[y + 1][x] = dist
            if x > 0:
                if self.m[y][x - 1] != "
                    if y == goal[0] and x-1 == goal[1]:
                        return dist
                    else:
                        queue.append([y, x-1])
                        self.label[y][x-1] = dist
            if x < len(self.m[0])-1:
                if self.m[y][x + 1] != "
                    if y == goal[0] and x+1 == goal[1]:
                        return dist
                    else:
                        queue.append([y, x+1])
                        self.label[y][x + 1] = dist
        return -1


def main():
    H, W = list(map(int, input().split()))
    m = [list(input()) for _ in range(H)]
    sum = list(chain.from_iterable(m)).count(".")

    solver = Solver(m)
    ans = solver.bfs([1, 1], [H, W])
    if ans == -1:
      print(-1)
      quit()
    print(sum - ans -1)


if __name__ == "__main__":
    main()

Solution (Python):
r,c=map(int,input().split())
grid=[input() for _ in [0]*r]
ans=sum([grid[i].count(".") for i in range(r)])
visit=[[grid[i][j]=="
d=[(1,0),(-1,0),(0,1),(0,-1)]
cnt=0
q=[[0,0]]
flag=False
while q:
    qq=[]
    while q:
        i,j=q.pop()
        for dx,dy in d:
            if 0<=i+dx<r and 0<=j+dy<c:
                if i+dx==r-1 and j+dy==c-1:
                    flag=True
                if visit[i+dx][j+dy]==False:
                    visit[i+dx][j+dy]=True
                    qq.append([i+dx,j+dy])
    q=qq
    cnt+=1
    if flag==True:
        break
if flag==False:
    print(-1)
else:
    print(ans-cnt-1)

Solution (Python):
from collections import deque
H,W=map(int,input().split())
s=[list(input()) for _ in range(H)]
dflt_cnt=0
for i in range(H):
    dflt_cnt+=s[i].count(".")
que=deque([(0,0)])
step=[[-1]*W for _ in range(H)]
step[0][0]=0
move_h=[1,0,-1,0]
move_w=[0,1,0,-1]
cnt=1
while que:
    v=que.popleft()
    if v[0]==H-1 and v[1]==W-1:
        cnt+=step[H-1][W-1]
        break
    for i in range(4):
        next_h=v[0]+move_h[i]
        next_w=v[1]+move_w[i]
        if 0<=next_h<H and 0<=next_w<W and s[next_h][next_w]=="." and step[next_h][next_w]==-1:
            que.append((next_h,next_w))
            step[next_h][next_w]=step[v[0]][v[1]]+1
print(dflt_cnt-cnt if cnt!=1 else -1)

Solution (Python):
from collections import deque

h,w = map(int, input().split())
w = w + 2
maze = [list('
for i in range(h):
    maze.append(list('
maze.append(list('
h = h + 2
                
distance = [[float('inf')] * w for i in range(h)] 

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

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

while que:
    i,j,k = que.popleft() 
    for di,dj in move:
        if maze[i+di][j+dj] == '.' and distance[i+di][j+dj] > k+1:
            
            distance[i+di][j+dj] = k+1 
            que.append((i+di,j+dj,k+1)) 


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

if distance[h-2][w-2] != float('inf'):
    minimum_distance = distance[h-2][w-2]
else:
    minimum_distance = road

print(road - minimum_distance - 1)

Solution (Python):
import sys
import copy
import  math
import bisect
from statistics import *
from collections import *
from operator import itemgetter
"""
from fractions import gcd
def lcm(x, y):
    return (x * y) // gcd(x, y)
"""
stdin = sys.stdin
ni = lambda: int(ns())
na = lambda: list(map(int, stdin.readline().split()))
ns = lambda: stdin.readline()

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

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

    while que:
        x, y = que.popleft()
        if x == h - 1 and y == w - 1:
            break
        for dx, dy in ([1, 0], [0, 1], [-1, 0], [0, -1]):
            nx = x + dx
            ny = y + dy
            if 0 <= nx < h and 0 <= ny < w and maze[nx][ny] != "
                que.append((nx, ny))
                d[nx][ny] = d[x][y] + 1

    return d[h - 1][w - 1]

h, w = na()
maze = [list(input()) for _ in range(h)]
ct = 0
for i in range(h):
    ct += maze[i].count("
res = bfs()
if bfs() == -1:
    print(-1)
else:
    print(h * w - bfs() - 1 - ct)

Solution (Python):
H, W = map(int, input().split())
board = [0]*(H+2)
board[0] = [1]*(W+2)
total = 0
for i in range(1,H+1):
    board[i] = [1]+list(1 if c == '
    total += sum(1 for c in board[i] if c == 0)
board[H+1] = [1]*(W+2)

D = [[10e10] * (W+2) for _ in range(H+2)]
D[1][1] = 0
from heapq import heappush, heappop

q = [(0, (1, 1))]

while q:
    d, (i, j) = heappop(q)
    alt = d + 1

    for x, y in [(i+1,j), (i-1,j), (i,j+1), (i,j-1)]:
        if board[x][y] == 0:
            if D[x][y] > alt:
                D[x][y] = alt
                heappush(q, (alt, (x, y)))



if D[H][W] == 10e10:
    print(-1)
else:
    print(total - D[H][W] - 1)

Solution (Python):
import sys
import copy

h, w = map(int, sys.stdin.readline().split())

maps = [list(sys.stdin.readline().rstrip()) for _ in range(h)]

def calcdist(maps, start, end, h, w):
    nextlist = []
    nextlist.append(start)
    count = 1
    while True:
        nexnex = []
        for i in nextlist:
            if i[0] == end[0] and i[1] == end[1]:
                return count
            if i[0] > 0 and maps[i[0] -1][i[1]] == '.':
                maps[i[0] -1][i[1]] = '
                nexnex.append([i[0] -1, i[1]])
            if i[0] < h-1 and maps[i[0] +1][i[1]] == '.':
                maps[i[0] +1][i[1]] = '
                nexnex.append([i[0] +1, i[1]])
            if i[1] > 0 and maps[i[0]][i[1]-1] == '.':
                maps[i[0]][i[1]-1] = '
                nexnex.append([i[0], i[1]-1])
            if i[1] < w-1 and maps[i[0]][i[1]+1] == '.':
                maps[i[0]][i[1]+1] = '
                nexnex.append([i[0], i[1]+1])
        nextlist = nexnex
        count += 1
        if len(nexnex) == 0:
            return -1
    return count

kabe = 0

for i in range(h):
    for j in range(w):
        if maps[i][j] == '
            kabe += 1

total = 0
dist = calcdist(maps,[0, 0], [h-1, w-1], h, w)
if dist == -1:
    print(-1)
else:
    print(h*w - dist - kabe)

Solution (Python):
import sys
sys.setrecursionlimit(10**6)

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

tmp = 0
for i in range(H):
	tmp += S[i].count("

w_count = (H*W) - tmp

def bfs(field, dp, q):
	cp = q.pop(0)
	np = [[cp[0]+1,cp[1]], [cp[0]-1,cp[1]], [cp[0],cp[1]+1], [cp[0],cp[1]-1]]

	for n in np:
		if 0 <= n[0] <= H-1 and 0 <= n[1] <= W-1:
			if field[n[0]][n[1]] == "." and dp[n[0]][n[1]] == inf:
				q.append(n)
				dp[n[0]][n[1]] = dp[cp[0]][cp[1]] + 1
			if n == [H-1,W-1]:
				return dp[n[0]][n[1]]

	if len(q) == 0:
		return -1

	return bfs(field, dp, q)

inf = float("inf")
dp = [[inf for _ in range(W)] for _ in range(H)]
dp[0][0] = 0
nes = bfs(S, dp, [[0,0]])
if nes == -1:
	print(-1)
else:
	print(w_count-nes-1)

Solution (Python):
import sys
sys.setrecursionlimit(10**6)

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

tmp = 0
for i in range(H):
	tmp += S[i].count("

w_count = (H*W) - tmp

def bfs(field, dp, q):
	cp = q.pop(0)
	np = [[cp[0]+1,cp[1]], [cp[0]-1,cp[1]], [cp[0],cp[1]+1], [cp[0],cp[1]-1]]

	for n in np:
		if 0 <= n[0] <= H-1 and 0 <= n[1] <= W-1:
			if field[n[0]][n[1]] == "." and dp[n[0]][n[1]] == inf:
				q.append(n)
				dp[n[0]][n[1]] = dp[cp[0]][cp[1]] + 1
			if n == [H-1,W-1]:
				return dp[n[0]][n[1]]

	if len(q) == 0:
		return -1

	return bfs(field, dp, q)

inf = float("inf")
dp = [[inf for _ in range(W)] for _ in range(H)]
dp[0][0] = 0
nes = bfs(S, dp, [[0,0]])
if nes == -1:
	print(-1)
else:
	print(w_count-nes-1)

Solution (Python):
R, C = map(int, input().split())
 
c = []
black = 0

for _ in range(R):
    tmp = input()
    c.append(tmp)
    black += list(tmp).count("

INF = R * C
 
def steppable(h, w):
    if not (h in range(R) and w in range(C)):
        return False
    if c[h][w] == '
        return False
    else:
        return True
 
num_step = [[INF for w in range(C)] for h in range(R)]
num_step[0][0] = 1
 
queue = [(0, 0)]
counter = 0

while not queue == []:

    if counter >= 10000:
        print(-1)
        exit()

    h = queue.pop(0) 
    next_  = [
        (h[0] + 1, h[1]),
        (h[0] - 1, h[1]),
        (h[0], h[1] + 1),
        (h[0], h[1] - 1),]
        
    for n in next_:
        if steppable(n[0], n[1]) and num_step[n[0]][n[1]] == INF:
            queue.append(n)
            num_step[n[0]][n[1]] = num_step[h[0]][h[1]] + 1
 
if num_step[R-1][C-1] != INF:
    ans = R*C - black - num_step[R-1][C-1]
    print(ans)
else:
    print(-1)

Solution (Python):

adjust_list = ((0,1),(0,-1),(1,0),(-1,0))
h, w = [ int(v) for v in input().split() ]
total_block = 0
field = [ list(input()) for i in range(h) ]
for i in field:
    total_block += i.count("

start = (0,0)
def bfs(p,t):
    field[p[0]][p[1]] = t
    search_list = [p]
    while search_list != []:
        t += 1
        new_search_list = []
        for i in search_list:
            for j in adjust_list:
                if 0 <= i[0]+j[0] < h and 0 <= i[1]+j[1] < w:
                    if field[i[0]+j[0]][i[1]+j[1]] == ".":
                        field[i[0]+j[0]][i[1]+j[1]] = t
                        new_search_list.append((i[0]+j[0],i[1]+j[1]))
        search_list = new_search_list
    return

bfs(start,1)


if field[-1][-1] == ".":
    print(-1)
else:
    print(h*w - total_block - field[-1][-1])

Solution (Python):
h,w=map(int,input().split())
grid=[list(input()) for _ in range(h)]
dist=[[-1]*w for _ in range(h)]
dist[0][0]=0
Q=[(0,0)]
tile=h*w
cnt=0

white=0
for i in range(h):
    white+=grid[i].count(".")

while Q:
    Q_alt=[]
    for q in Q:
        if grid[q[1]][q[0]]!="
            if q[0]!=0:
                if grid[q[1]][q[0]-1]!="
                    dist[q[1]][q[0]-1]=cnt+1
                    Q_alt.append((q[0]-1,q[1]))
            if q[0]!=w-1:
                if grid[q[1]][q[0]+1]!="
                    dist[q[1]][q[0]+1]=cnt+1
                    Q_alt.append((q[0]+1,q[1]))
            if q[1]!=0:
                if grid[q[1]-1][q[0]]!="
                    dist[q[1]-1][q[0]]=cnt+1
                    Q_alt.append((q[0],q[1]-1))
            if q[1]!=h-1:
                if grid[q[1]+1][q[0]]!="
                    dist[q[1]+1][q[0]]=cnt+1
                    Q_alt.append((q[0],q[1]+1))
    cnt+=1
    Q=Q_alt

if dist[h-1][w-1]==-1:
    print(-1)
else:
    print(white-dist[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)

Q = [[0,0]]
shnum = 0



for i in range(H):

    for j in range(W):

        if s[i][j] == "

            shnum += 1


while len(Q) > 0:

    
    

    now = Q.pop(0)

    if now[0] == 0 and now[1] == 0:
        s[0][0] = 1
        Q.append([0,1])
        Q.append([1,0])

    elif s[now[0]][now[1]] == "
        continue;

    else:

        if s[now[0]][now[1]] == ".":

            far = 10000

        else:

            far = s[now[0]][now[1]]

        flag = 0

        if now[0]-1 >= 0 and s[now[0]-1][now[1]] not in [-1,"

            if far > s[now[0]-1][now[1]]+1:
                far = s[now[0]-1][now[1]]+1
                flag = 1

        if now[1]-1 >= 0 and s[now[0]][now[1]-1] not in [-1,"

            if far > s[now[0]][now[1]-1]+1:
                far = s[now[0]][now[1]-1]+1
                flag = 2

        if now[0]+1 < H and s[now[0]+1][now[1]] not in [-1,"

            if far > s[now[0]+1][now[1]]+1:
                far = s[now[0]+1][now[1]]+1
                flag = 3

        if now[1]+1 < W and s[now[0]][now[1]+1] not in [-1,"

            if far > s[now[0]][now[1]+1]+1:
                far = s[now[0]][now[1]+1]+1
                flag = 4

        if flag != 0:
            
            s[now[0]][now[1]] = far

            if now[0]-1 >= 0 and flag != 1:

                Q.append([now[0]-1,now[1]])

            if now[1]-1 >= 0 and flag != 2:

                Q.append([now[0],now[1]-1])

            if now[0]+1 < H and flag != 3:

                Q.append([now[0]+1,now[1]])

            if now[1]+1 < W and flag != 4:

                Q.append([now[0],now[1]+1])


if s[-1][-1] == -1:
    print (-1)

else:

    if s[-1][-1] == ".":
        print (-1)
    else:
        print (H*W - s[-1][-1] - shnum)

Solution (Python):
H,W=map(int,input().split());S=[input() for _ in range(H)];G=[[-1]*W for _ in range(H)];G[0][0]=1;q=[(0,0)]
while q:
 i,j=q[0];q=q[1:]
 for x,y in[(1,0),(0,1),(-1,0),(0,-1)]:
  t,u=i+x,j+y
  if 0<=t<H and 0<=u<W and G[t][u]<0 and S[t][u]==".":
   G[t][u]=1+G[i][j];q+=[(t,u)]
print(-1*(G[-1][-1]<0)or sum(s.count(".")for s in S)-G[-1][-1])

Solution (Python):
from collections import deque

H, W = [int(i) for i in input().split()]

S = []
white = 0
for _ in range(H):
    s = input()
    white += s.count(".")
    S.append(list(s))

S[0][0] = ""
Q = deque([(0, 0, 1)])
while Q:
    h, w, count = Q.popleft()
    if (h, w) == (H - 1, W - 1):
        print(white - count)
        quit()

    for nh, nw in [(h, w + 1), (h, w - 1), (h + 1, w), (h - 1, w)]:
        if 0 <= nh < H and 0 <= nw < W and S[nh][nw] == ".":
            S[nh][nw] = ""
            Q.append((nh, nw, count + 1))
print(-1)

Solution (Python):
from collections import deque

H, W, *S = open(0).read().split()
H, W, S = int(H), int(W), [list(s) for s in S]

white = sum(s.count(".") for s in S)

S[0][0] = ""
Q = deque([(0, 0, 1)])
while Q:
    h, w, count = Q.popleft()
    if (h, w) == (H - 1, W - 1):
        print(white - count)
        quit()

    for nh, nw in [(h, w + 1), (h, w - 1), (h + 1, w), (h - 1, w)]:
        if 0 <= nh < H and 0 <= nw < W and S[nh][nw] == ".":
            S[nh][nw] = ""
            Q.append((nh, nw, count + 1))
print(-1)

Solution (Python):
from collections import deque

H, W, *S = open(0).read().split()
H, W, S = int(H), int(W), [list(s) for s in S]

white = sum(s.count(".") for s in S)

Q = deque([(0, 0, 1)])
while Q:
    h, w, count = Q.popleft()
    if (h, w) == (H - 1, W - 1):
        print(white - count)
        quit()

    for nh, nw in [(h, w + 1), (h, w - 1), (h + 1, w), (h - 1, w)]:
        if 0 <= nh < H and 0 <= nw < W and S[nh][nw] == ".":
            S[nh][nw] = "visited"
            Q.append((nh, nw, count + 1))
print(-1)

Solution (Python):
from collections import deque

H, W, *S = open(0).read().split()
H, W, S = int(H), int(W), [list(s) for s in S]

white = sum(s.count(".") for s in S)

Q = deque([(0, 0, 1)])
while Q:
    h, w, count = Q.popleft()
    if (h, w) == (H - 1, W - 1):
        print(white - count)
        quit()

    for nh, nw in [(h, w + 1), (h, w - 1), (h + 1, w), (h - 1, w)]:
        if 0 <= nh < H and 0 <= nw < W and S[nh][nw] == ".":
            S[nh][nw] = "" 
            Q.append((nh, nw, count + 1))
print(-1)

Solution (Python):
from collections import deque

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

white = sum(s.count(".") for s in S)

Q = deque([(0, 0, 1)])
while Q:
    h, w, count = Q.popleft()
    if (h, w) == (H - 1, W - 1):
        print(white - count)
        quit()

    for nh, nw in [(h, w + 1), (h, w - 1), (h + 1, w), (h - 1, w)]:
        if not (0 <= nh < H and 0 <= nw < W):
            continue
        if S[nh][nw] == ".":
            S[nh][nw] = "" 
            Q.append((nh, nw, count + 1))
print(-1)

Solution (Python):
from collections import deque

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

white = sum(s.count(".") for s in S)

S[0][0] = "_"
Q = deque([(0, 0, 1)])
while Q:
    h, w, count = Q.popleft()
    if (h, w) == (H - 1, W - 1):
        print(white - count)
        quit()

    for nh, nw in [(h, w + 1), (h, w - 1), (h + 1, w), (h - 1, w)]:
        if 0 <= nh < H and 0 <= nw < W and S[nh][nw] == ".":
            S[nh][nw] = "_"
            Q.append((nh, nw, count + 1))
print(-1)

Solution (Python):
from collections import deque

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

white = sum(s.count(".") for s in S)

S[0][0] = "_"
Q = deque([(0, 0, 1)])
while Q:
    h, w, count = Q.popleft()
    if (h, w) == (H - 1, W - 1):
        print(white - count)
        quit()

    for nh, nw in [(h, w + 1), (h, w - 1), (h + 1, w), (h - 1, w)]:
        if 0 <= nh < H and 0 <= nw < W and S[nh][nw] == ".":
            S[nh][nw] = "_"
            Q.append((nh, nw, count + 1))
print(-1)

Solution (Python):
from collections import deque
h, w = map(int, input().split())
s = [list(input()) for _ in range(h)]
moves = ((1, 0), (-1, 0), (0, 1), (0, -1))
cnt = [[float('inf') for _ in range(w)] for _ in range(h)]
cnt[0][0] = 0

def bfs():
    q = deque([(0, 0)])
    while q:
        y, x = q.popleft()
        for dy, dx in moves:
            if 0 <= y+dy < h and 0 <= x+dx < w and s[y+dy][x+dx] != '
                q.append([y+dy, x+dx])
                cnt[y+dy][x+dx] = cnt[y][x] + 1
    
bfs()
if cnt[h-1][w-1] != float('inf'):
    short_path = cnt[h-1][w-1]
    ans = 0
    ans += short_path + 1
    for i in range(h):
        for j in range(w):
            if s[i][j] == '
                ans += 1

    ans = h*w - ans 
    print(ans)
else:
    print(-1)

Solution (Python):

from collections import defaultdict
from collections import deque
from heapq import heappush, heappop
import sys
import math
import bisect
import random
import itertools
sys.setrecursionlimit(10**5)
stdin = sys.stdin
bisect_left = bisect.bisect_left
bisect_right = bisect.bisect_right
def LI(): return list(map(int, stdin.readline().split()))
def LF(): return list(map(float, stdin.readline().split()))
def LI_(): return list(map(lambda x: int(x)-1, stdin.readline().split()))
def II(): return int(stdin.readline())
def IF(): return float(stdin.readline())
def LS(): return list(map(str, stdin.readline().split()))
def S(): return list(stdin.readline().rstrip())
def IR(n): return [II() for _ in range(n)]
def LIR(n): return [LI() for _ in range(n)]
def FR(n): return [IF() for _ in range(n)]
def LFR(n): return [LI() for _ in range(n)]
def LIR_(n): return [LI_() for _ in range(n)]
def SR(n): return [S() for _ in range(n)]
def LSR(n): return [LS() for _ in range(n)]
mod = 1000000007
inf = float('INF')


def A():
    n, a = IR(2)
    n %= 500
    if a >= n:
        print("Yes")
    else:
        print("No")
    return


def B():
    _ = II()
    a = LI()
    a.sort(reverse=True)
    op = 0
    ans = 0
    for ai in a:
        ans += -ai * op or ai
        op ^= 1
    print(ans)
    return


def C():
    c = LIR(3)
    for x in range(c[0][0] + 1):
        b = (c[0][0] - x, c[0][1] - x, c[0][2] - x)
        if (c[1][0] - b[0]) == (c[1][1] - b[1]) == (c[1][2] - b[2]):
            if (c[2][0] - b[0]) == (c[2][1] - b[1]) == (c[2][2] - b[2]):
                print("Yes")
                return
    print("No")
    return

def D():
    move = [[0, 1], [0, -1], [-1, 0], [1, 0]]
    h, w = LI()
    s = SR(h)
    q = deque([(0, 0, 1)])
    ans = h * w
    for y in range(h):
        for x in range(w):
            if s[y][x] == "
                ans -= 1
    check = [[True] * w for _ in range(h)]
    while q:
        x, y, tern = q.pop()
        for mx, my in move:
            mx += x
            my += y
            if 0 <= mx < w and 0 <= my < h:
                if s[my][mx] == "." and check[my][mx]:
                    check[my][mx] = False
                    if my == h - 1 and mx == w - 1:
                        print(ans - tern - 1)
                        return
                    q.appendleft((mx, my, tern + 1))
    print(-1)


    return


if __name__ == '__main__':
    D()

Solution (Python):

import sys
input = sys.stdin.readline

def bfs() -> None:
    q = [(0, 0)]
    while q:
        x, y = q.pop(0)
        for dx, dy in dxy:
            nx, ny = x + dx, y + dy  
            if 0 <= nx < H and 0 <= ny < W and S[nx][ny] == "." and dist[nx][ny] == 0:
                q.append((nx, ny))
                dist[nx][ny] = dist[x][y] + 1


def main():
    global H, W, S, dist, dxy
    H, W = tuple(map(int, input().split()))
    S = tuple(input().rstrip() for _ in range(H))
    dist = [[0] * W for _ in range(H)]  
    dist[0][0] = 1
    dxy = [(1, 0), (-1, 0), (0, 1), (0, -1)]
    bfs()
    white, x = sum(s.count(".") for s in S), dist[-1][-1]
    ans = white - x if x else -1
    print(ans)


if __name__ == "__main__":
    main()

Solution (Python):

import sys
input = sys.stdin.readline

from collections import deque

def bfs() -> None:
    q = [(0, 0)]
    while q:
        x, y = q.pop(0)
        for dx, dy in dxy:
            nx, ny = x + dx, y + dy  
            if 0 <= nx < H and 0 <= ny < W and S[nx][ny] == "." and dist[nx][ny] == 0:
                q.append((nx, ny))
                dist[nx][ny] = dist[x][y] + 1


def main():
    global H, W, S, dist, dxy
    H, W = tuple(map(int, input().split()))
    S = tuple(input().rstrip() for _ in range(H))
    dist = [[0] * W for _ in range(H)]  
    dist[0][0] = 1
    dxy = [(1, 0), (-1, 0), (0, 1), (0, -1)]
    bfs()
    white, x = sum(s.count(".") for s in S), dist[-1][-1]
    ans = white - x if x else -1
    print(ans)


if __name__ == "__main__":
    main()

Solution (Python):

import sys
input = sys.stdin.readline

from collections import deque

def bfs() -> None:
    q = [(0, 0)]
    while q:
        x, y = q.pop(0)
        for dx, dy in dxy:
            nx, ny = x + dx, y + dy  
            if 0 <= nx < H and 0 <= ny < W and S[nx][ny] == "." and dist[nx][ny] == 0:
                q += [(nx, ny)]
                dist[nx][ny] = dist[x][y] + 1


def main():
    global H, W, S, dist, dxy
    H, W = tuple(map(int, input().split()))
    S = tuple(input().rstrip() for _ in range(H))
    dist = [[0] * W for _ in range(H)]  
    dist[0][0] = 1
    dxy = [(1, 0), (-1, 0), (0, 1), (0, -1)]
    bfs()
    white, x = sum(s.count(".") for s in S), dist[-1][-1]
    ans = white - x if x else -1
    print(ans)


if __name__ == "__main__":
    main()

Solution (Python):

import sys
input = sys.stdin.readline

from collections import deque

def bfs() -> None:
    q = deque([(0, 0)])
    while q:
        x, y = q.popleft()
        for dx, dy in dxy:
            nx, ny = x + dx, y + dy  
            if 0 <= nx < H and 0 <= ny < W and S[nx][ny] == "." and dist[nx][ny] == 0:
                q += [(nx, ny)]
                dist[nx][ny] = dist[x][y] + 1


def main():
    global H, W, S, dist, dxy
    H, W = tuple(map(int, input().split()))
    S = tuple(input().rstrip() for _ in range(H))
    dist = [[0] * W for _ in range(H)]  
    dist[0][0] = 1
    dxy = [(1, 0), (-1, 0), (0, 1), (0, -1)]
    bfs()
    white, x = sum(s.count(".") for s in S), dist[-1][-1]
    ans = white - x if x else -1
    print(ans)


if __name__ == "__main__":
    main()

Solution (Python):

import sys
input = sys.stdin.readline

from collections import deque

def bfs() -> None:
    q = deque([(0, 0)])
    while q:
        x, y = q.popleft()
        for dx, dy in dxy:
            nx, ny = x + dx, y + dy  
            if 0 <= nx < H and 0 <= ny < W and S[nx][ny] == "." and dist[nx][ny] == 0:
                q.append((nx, ny))
                dist[nx][ny] = dist[x][y] + 1


def main():
    global H, W, S, dist, dxy
    H, W = tuple(map(int, input().split()))
    S = tuple(input().rstrip() for _ in range(H))
    dist = [[0] * W for _ in range(H)]  
    dist[0][0] = 1
    dxy = [(1, 0), (-1, 0), (0, 1), (0, -1)]
    bfs()
    white, x = sum(s.count(".") for s in S), dist[-1][-1]
    ans = white - x if x else -1
    print(ans)


if __name__ == "__main__":
    main()