Problem:
 Score: 400 points    Problem statement  We have an H \times W grid whose squares are painted black or white. The square at the i -th row from the top and the j -th column from the left is denoted as (i, j) . Snuke would like to play the following game on this grid. At the beginning of the game, there is a character called Kenus at square (1, 1) . The player repeatedly moves Kenus up, down, left or right by one square. The game is completed when Kenus reaches square (H, W) passing only white squares. Before Snuke starts the game, he can change the color of some of the white squares to black. However, he cannot change the color of square (1, 1) and (H, W) . Also, changes of color must all be carried out before the beginning of the game. When the game is completed, Snuke's score will be the number of times he changed the color of a square before the beginning of the game. Find the maximum possible score that Snuke can achieve, or print -1 if the game cannot be completed, that is, Kenus can never reach square (H, W) regardless of how Snuke changes the color of the squares.  The color of the squares are given to you as characters s_{i, j} . If square (i, j) is initially painted by white, s_{i, j} is . ; if square (i, j) is initially painted by black, s_{i, j} is # .      Constraints   H is an integer between 2 and 50 (inclusive).  W is an integer between 2 and 50 (inclusive).  s_{i, j} is . or #  (1 \leq i \leq H, 1 \leq j \leq W) .  s_{1, 1} and s_{H, W} are . .         Input  Input is given from Standard Input in the following format:  H  W  s_{1, 1}s_{1, 2}s_{1, 3} ... s_{1, W}  s_{2, 1}s_{2, 2}s_{2, 3} ... s_{2, W}  :  :  s_{H, 1}s_{H, 2}s_{H, 3} ... s_{H, W}       Output  Print the maximum possible score that Snuke can achieve, or print -1 if the game cannot be completed.        Sample Input 1 3 3
..#
#..
...      Sample Output 1 2  The score 2 can be achieved by changing the color of squares as follows:        Sample Input 2 10 37
.....................................
...#...####...####..###...###...###..
..#.#..#...#.##....#...#.#...#.#...#.
..#.#..#...#.#.....#...#.#...#.#...#.
.#...#.#..##.#.....#...#.#.###.#.###.
.#####.####..#.....#...#..##....##...
.#...#.#...#.#.....#...#.#...#.#...#.
.#...#.#...#.##....#...#.#...#.#...#.
.#...#.####...####..###...###...###..
.....................................      Sample Output 2 209

Solution (Python):
from collections import deque
h,w=map(int,input().split())
s=[input() for _ in range(h)]
vi=[ [-1 for _ in range(w)] for _ in range(h)]
st=deque()
st.append([0,0,1])
vi[0][0]=1
while st:
  h1,w1,i=st.popleft()
  d=[[0,1],[-1,0],[1,0],[0,-1]]
  for m in d:
    if h1+m[0]==h-1 and w1+m[1]==w-1:
      vi[h-1][w-1]=i+1
      st.clear()
    if 0<=h1+m[0]<h and 0<=w1+m[1]<w:
      if vi[h1+m[0]][w1+m[1]]==-1 and s[h1+m[0]][w1+m[1]]==".":
        st.append([h1+m[0],w1+m[1],i+1])
        vi[h1+m[0]][w1+m[1]]=i+1

print("".join(s).count(".")-vi[h-1][w-1] if vi[h-1][w-1]!=-1 else -1)

Solution (Python):
from collections import deque

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



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


def sur(v):
    vx=v[0]
    vy=v[1]
    preE=[(vx-1,vy),(vx+1,vy),(vx,vy+1),(vx,vy-1)]
    E=[]
    for nv in preE:
        if 0<=nv[0]<=h-1 and 0<=nv[1]<=w-1:
            if G[nv[0]][nv[1]]=='.':
                E.append(nv)
    return E


dist=[[0]*w for i in range(h)]
q=deque()

dist[0][0]=1
q.append((0,0))
while q:
    now=q.popleft()
    for next in sur(now):
        if dist[next[0]][next[1]]>0:
            continue
        q.append(next)
        dist[next[0]][next[1]]=dist[now[0]][now[1]]+1

        if next==(h-1,w-1):
            print(white-dist[h-1][w-1])
            break
    else:
        continue
    break
else:
    print(-1)

Solution (Python):
import copy
h,w = map(int,input().split())
g = [[False]*(w+2) for _ in range(h+2)]
d = [[-1]*(w+2) for _ in range(h+2)]
ans = 0
for i in range(h):
    l = list(input())
    for j in range(w):
        if l[j] == ".":
            ans += 1
            g[i+1][j+1] = True
def f(i,j):
    return [(i+1,j),(i,j+1),(i-1,j),(i,j-1)]
now = f(1,1)
d[1][1] = 0
nxt = []
cnt = 1
while now:
    for l in now:
        i,j = l[0],l[1]
        if d[i][j] == -1 and g[i][j]:
            d[i][j] = cnt
            for l2 in f(i,j):
                nxt.append(l2)
    cnt += 1
    now = copy.copy(nxt)
    nxt = []
if d[h][w] == -1:
    print(-1)
else:
    print(ans-d[h][w]-1)

Solution (Python):
def main():
    h,w=map(int,input().split())
    maze=["
    total_white=sum([row.count(".") for row in maze])

    seen=[[-1]*(w+2) for _ in range(h+2)]
    if maze[1][1]=="
    seen[1][1]=1
    token=1
    bfs_new=[(1,1)]

    while bfs_new:
        token+=1
        bfs_old=bfs_new[:]
        bfs_new=[]
        for x in bfs_old:
            for move in [(1,0),(-1,0),(0,1),(0,-1)]:
                ywork=x[0]+move[0]
                xwork=x[1]+move[1]
                if maze[ywork][xwork]=="
                if seen[ywork][xwork]>=0 : continue
                seen[ywork][xwork]=token
                bfs_new.append((ywork,xwork))
    
    if seen[h][w]==-1 : print(-1)
    else : print(total_white-seen[h][w])

main()

Solution (Python):
from collections import deque

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

d = [[float("inf")] * w for _ in range(h)]

que = deque()
que.append((0, 0))
d[0][0] = 1
while que:
    x, y = que.popleft()
    for dx, dy in [(1, 0), (-1, 0), (0, 1), (0, -1)]:
        nx = x + dx
        ny = y + dy
        if 0 <= nx < w and 0 <= ny < h and s[ny][nx] == '.' and d[ny][nx] == float("inf"):
            que.append((nx, ny))
            d[ny][nx] = d[y][x] + 1

res = d[h-1][w-1]
if res == float("inf"):
    print(-1)
else:
    print(white_count - res)

Solution (Python):
from math import ceil,floor,factorial,gcd,sqrt,log2,cos,sin,tan,acos,asin,atan,degrees,radians,pi,inf
from itertools import accumulate,groupby,permutations,combinations,product,combinations_with_replacement
from collections import deque,defaultdict,Counter
from bisect import bisect_left,bisect_right
from operator import itemgetter
from heapq import heapify,heappop,heappush
from queue import Queue,LifoQueue,PriorityQueue
from copy import deepcopy
from time import time
import string
import sys
sys.setrecursionlimit(10 ** 7)
def input() : return sys.stdin.readline().strip()
def INT()   : return int(input())
def MAP()   : return map(int,input().split())
def LIST()  : return list(MAP())

def bfs():
    d = [[inf]*w for i in range(h)]

    dy = [0, 1, 0, -1] 
    dx = [1, 0, -1, 0]
 
    que = deque([])
    que.append((sy, sx))
    d[sy][sx] = 0
 
    while que:
        p = que.popleft()
        if p[0] == gy and p[1] == gx:
            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 s[ny][nx] != '
                que.append((ny,nx))
                d[ny][nx] = d[p[0]][p[1]] + 1
 
    return d[gy][gx]

h, w = MAP()
s = [input() for i in range(h)]
sy = sx = 0
gy, gx = h-1, w-1

if bfs() == inf:
    ans = -1
else:
    count = 0
    for i in range(h):
        count += s[i].count('
    ans = h*w - bfs() - 1 - count

print(ans)

Solution (Python):
def conv(S,index,c):
	lstS = list(S)
	lstS[index] = c
	S = ''.join(lstS)

	return S


def DFS(stack,MAP,size,count,goal):
	ret = -1
	newstack = []
	for p in stack:
		if p == goal:
			ret = count
		elif ret == -1:
			y = p[0]
			x = p[1]
			Y = size[0]-1
			X = size[1]-1
			if y != 0:
				if MAP[y-1][x] == '.':
					MAP[y-1] = conv(MAP[y-1],x,'*')
					newstack.append([y-1,x])
			if y != Y:
				if MAP[y+1][x] == '.':
					MAP[y+1] = conv(MAP[y+1],x,'*')
					newstack.append([y+1,x])
			if x != 0:
				if MAP[y][x-1] == '.':
					MAP[y] = conv(MAP[y],x-1,'*')
					newstack.append([y,x-1])
			if x != X:
				if MAP[y][x+1] == '.':
					MAP[y] = conv(MAP[y],x+1,'*')
					newstack.append([y,x+1])
	
	if ret == -1:
		if len(newstack) == 0:
			ret = -1
		else:
			ret = DFS(newstack,MAP,size,count+1,goal)

	return ret


if __name__ == '__main__':
	H, W = map(int, input().split())

	MAP = []
	black = 0

	for y in range(H):
		IN = input() 
		MAP.append(IN)
		black += IN.count('

	step = DFS([[0,0]],MAP,[H,W],0,[H-1,W-1])

	if step == -1:
		ans = -1
	else:
		ans = H*W - step - 1 - black

	print(ans)

Solution (Python):
from collections import deque

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



def bfs(maze,maze_s,sy,sx):
  maze_s[sy][sx] = 0
  queue = deque([[sy,sx]])
  while queue:
    y,x = queue.popleft()
    if maze[y][x] == "g":
      return maze_s[y][x]
    else:
      for j,k in [(0,1),(0,-1),(1,0),(-1,0)]:
        new_y,new_x = y+j, x+k
        if 0 <= new_y <= H-1 and 0 <= new_x <= W-1:
          if maze[new_y][new_x] != "
            maze_s[new_y][new_x] = maze_s[y][x] + 1
            queue.append([new_y,new_x])
  else:
    print(-1)
    exit()

maze_s = list([-1] * W for i in range(H))
count = 0
for row in maze:
  count += row.count(".")

maze[H-1][W-1] = "g"

ans = count - bfs(maze,maze_s,0,0) -1
print(ans)

Solution (Python):
from collections import deque
def main():
    h,w = map(int,input().split())
    Map = []
    Visited = [[False for j in range(w)]for i in range(h)]
    DYDX = [[0,1],[1,0],[0,-1],[-1,0]]
    white = 0
    black = 0
    for i in range(h):
        tmp = [i for i in input()]
        white += tmp.count('.')
        black += tmp.count('
        
        Map.append(tmp)
    q = deque()
    q.append((0,0,0))
    ans = 0
    while q:
        y,x,cnt = q.popleft()
        if y<0 or y>=h or x<0 or x>=w:
            continue
        if Visited[y][x]:
            continue
        if Map[y][x]=='
            continue
        if y==h-1 and x==w-1:
            ans = cnt
            break
        Visited[y][x] = True
        cnt += 1
        for dy,dx in DYDX:
            q.append((y+dy,x+dx,cnt))
    if ans == 0:
        print('-1')
    else:
        print(white-ans-1) 

if __name__ == '__main__':
    main()

Solution (Python):
H,W = map(int,input().split())
s = [None]*H
for i in range(H):
    s[i] = input()

from collections import deque
def cango(x,y):
    cand =[]
    if x+1<=H-1:
        cand.append((x+1,y))
    if x-1>=0:
        cand.append((x-1,y))
    if y+1<=W-1:
        cand.append((x,y+1))
    if y-1>=0:
        cand.append((x,y-1))
    return cand
    
q = deque([(-1,-1,0,0,0)]) 
been = [[False]*W for _ in range(H)]

reach=False
while q:
    x_old,y_old,x_now,y_now,time = q.popleft()
    
    cand = cango(x_now,y_now)
    
    if x_now==H-1 and y_now==W-1:
        reach=True
        break
    
    for x_new,y_new in cand:
        if not been[x_new][y_new] and s[x_new][y_new]==".":
            q.append((x_now,y_now,x_new,y_new,time+1))
            been[x_new][y_new]=True
if reach:
    print( sum(ss.count(".") for ss in s)-time-1 )
else:
    print(-1)

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

vist=[[0]*W  for i in range(H)]
dxdy=[[-1,0],[1,0],[0,-1],[0,1]]

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


ans=0

while len(d)>0:
    a=d.popleft()
    x,y,z=a[0],a[1],a[2]

    if x==H-1 and y==W-1:
        ans=z
        break
    
    elif arr[x][y]=="." and vist[x][y]==0:
        vist[x][y]=1
        for dx,dy in dxdy:
            if (0<=x+dx<H) and (0<=y+dy<W):
                if arr[x+dx][y+dy]==".":
                    d.append([x+dx,y+dy,z+1])

count=0
for i in range(H):
    for j in range(W):
        if arr[i][j]=="
            count+=1
if ans==0:
    print(-1)
else:
    print(H*W-count-ans)

Solution (Python):
from collections import deque
h,w = map(int,input().split())
mapa=[]
mapa.append(''.join(['
dotn = 0
for i in range(h):
    temp = input()
    dotn+=temp.count('.')
    mapa.append('
mapa.append(''.join(['
passed = [[False for _ in range(w+2)] for _ in range(h+2)]

def dircheck(cy,cx):
    if mapa[cy][cx]=='.' and not passed[cy][cx]:
        passed[cy][cx]=True
        return True
    else:
        return False    

q=deque()
q.append((1,1))
step=0
goaled=False
while True:
    newq=deque()
    while len(q)!=0:
        (y,x) = q.pop()
        if (y,x)==(h,w):
            goaled=True
            break
        else:
            for dy,dx in zip((y-1,y+1,y,y),(x,x,x-1,x+1)):
                if dircheck(dy,dx):newq.append((dy,dx))
    q = newq
    step+=1
    if goaled:
        print(dotn-step)        
        break
    if len(newq)==0:
        print(-1)
        break

Solution (Python):
from collections import deque
H,W=map(int,input().split())
S=[]
count=0
for _ in range (H):
    A=list(input())
    for a in A:
        if a=='.':
            count+=1
    S.append(A)
 
mas=deque([(0,0,0)])
while mas:
    y,x,n=mas.popleft()
    if 0<=y<=H-1 and 0<=x<=W-1:
        if S[y][x]=='.':
            S[y][x]=n
            mas.append((y+1,x,n+1))
            mas.append((y,x+1,n+1))
            mas.append((y-1,x,n+1))
            mas.append((y,x-1,n+1))
short=S[H-1][W-1]
if short=='.':
    print(-1)
else:
    print(count-(short+1))

Solution (Python):
from collections import deque

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

S = [[] for _ in range(h)]

ans = 0
for i in range(h):
    S[i] = input()
    ans += S[i].count('.')

direct = [[0, 1], [0, -1], [1, 0], [-1, 0]]



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


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


while que:
    
    chi, cwi = que.pop()

    for (dh, dw) in direct:
        
        if not (0 <= chi + dh <= h - 1 and 0 <= cwi + dw <= w - 1):
            continue
        
        if D[chi + dh][cwi + dw] != -1 or S[chi + dh][cwi + dw] == '
            continue
        
        D[chi + dh][cwi + dw] = D[chi][cwi] + 1
        
        que.appendleft([chi + dh, cwi + dw])

dist = D[-1][-1]

if dist != -1:
    print(ans - (dist + 1))
else:
    print(-1)

Solution (Python):
from collections import deque

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

def get_adj(pos):
    ans = []
    for v in [(-1, 0), (1, 0), (0, -1), (0, 1)]:
        adj = (pos[0] + v[0], pos[1] + v[1])
        if adj[0] >= 0 and adj[0] < H and adj[1] >= 0 and adj[1] < W:
            ans.append(adj)
    return ans

start = (0, 0)
goal = (H-1, W-1)

q = deque()
q.append((start, 1))
visited = {}

while q:
    pos, dist = q.popleft()
    if field[pos[0]][pos[1]] == '
        continue
    if pos in visited:
        continue
    visited[pos] = dist
    if pos == goal:
        break
    for adj in get_adj(pos):
        q.append((adj, dist+1))

count_walls = sum([row.count('

if goal in visited:
    print(H*W-visited[goal]-count_walls)
else:
    print(-1)

Solution (Python):
import sys
input = lambda : sys.stdin.readline().rstrip()
sys.setrecursionlimit(max(1000, 10**9))
write = lambda x: sys.stdout.write(x+"\n")

h,w = list(map(int, input().split()))
s = [None]*h
for i in range(h):
    s[i] = input()
start = (0,0)

from queue import deque
vals = [None] * (w*h)
q = deque([(0, start)]) 
vals[start[0]*w+start[1]] = 0
dx = [0,1,0,-1]
dy = [1,0,-1,0]
while q:
    val, (x,y) = q.popleft()
    for i, j in zip(dx,dy):
        xx, yy = x+i, y+j
        if xx<0 or xx>=h or yy<0 or yy>=w or s[xx][yy]=="
            continue
        if vals[xx*w+yy] is None:
            vals[xx*w+yy] = val+1
            q.append((vals[xx*w+yy], (xx,yy)))

dist = vals[-1]
if dist is None:
    ans = -1
else:
    ans = (h*w) - (dist+1) - sum(sum(item=="
print(ans)

Solution (Python):
from collections import deque
h,w = map(int,input().split())
l = [list(input()) for i in range(h)]
h1,w1= 0,0

cou = 0
for i in l:
  for j in i:
    if j=='.':
      cou += 1
k = [[-1]*w for i in range(h)]
def bfs(a,b):
  d = deque()
  d.append([a,b])
  k[a][b]=0
  while d:
    c,e = d.popleft()
    m = [1,0,-1,0]
    n = [0,1,0,-1]
    for i in range(4):
      c1 = c+m[i]
      e1 = e+n[i]
      if 0<=c1 and 0<=e1 and c1<h and e1<w:
        if l[c1][e1]=="." and k[c1][e1]==-1:
          k[c1][e1]  =k[c][e] +1
          d.append([c1,e1])
  return k
bfs(h1,w1)        
if k[-1][-1]!=-1:
  print(cou-k[-1][-1]-1)
else:
  print(-1)

Solution (Python):
import sys
input = sys.stdin.readline
INF = 1001001001
from collections import deque

def linput(ty=int, cvt=list):
	return cvt(map(ty,input().split()))

def pad(mxy, w="
	gp = w*(len(mxy[0])+2)
	return [gp,]+[w+vx+w for vx in mxy]+[gp,]

vD = [(0,1),(1,0),(0,-1),(-1,0)]
vQ = deque([])
vQ_app, vQ_popl = vQ.append, vQ.popleft

def main():
	H,W = linput()
	sr,sc = 1,1
	gr,gc = H,W
	mM = [input().rstrip() for _ in "*"*H]
	walls = sum(s.count("
	mM = pad(mM,"
	
	
	res = 0
	cnt = 0
	
	mV = [[INF,]*(W+2) for _ in "*"*(H+2)]
	
	
	
	
	mV[sr][sc] = 0
	vQ_app((sr,sc))
	
	while vQ:
		r,c = vQ_popl()
		now_cost = mV[r][c]
		for dr,dc in vD:
			nr,nc = r+dr, c+dc
			if mM[nr][nc]!=".":
				continue
			if now_cost + 1 < mV[nr][nc]:
				vQ_app((nr,nc))
				mV[nr][nc] = now_cost + 1
				
		
		cnt += 1
		
		if cnt>4999999: break
	
	res = mV[gr][gc]
	if res == INF:
		res = -1
	else:
		res = H*W - res - walls - 1
	print(res)

if __name__ == "__main__":
	main()

Solution (Python):
from collections import deque
H,W=map(int,input().split())
maze=[]
white=0
for i in range(H):
    s=input()
    c=s.count(".")
    white+=c
    maze.append(s)
path=[[None]*W for _ in range(H)]
path[0][0]=1
q=deque([[0,0]])
while q:
    h,w=q.popleft()
    for nh,nw in ([h+1,w],[h-1,w],[h,w+1],[h,w-1]):
        if nh<0 or nh>H-1 or nw<0 or nw>W-1:
            continue
        if maze[nh][nw]=="
            continue
        q.append([nh,nw])
        path[nh][nw]=path[h][w]+1
        if nh==H-1 and nw==W-1:
            print(white-path[nh][nw])
            exit()
print(-1)

Solution (Python):
from collections import deque
h, w = map(int, input().split())
S = [[] for _ in range(h)]
ans = 0
for i in range(h):
    S[i] = list(input())
    ans += S[i].count('.')

direct = [[0,1],[0,-1],[1,0],[-1,0]]


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

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

while que:
    
    chi, cwi = que.pop()
    for (dh,dw) in direct:
        
        if not (0<=chi+dh<=h-1 and 0<=cwi+dw<=w-1): continue
        
        if D[chi+dh][cwi+dw]!=-1 or S[chi+dh][cwi+dw]=='
        
        D[chi+dh][cwi+dw] = D[chi][cwi]+1
        
        que.appendleft([chi+dh, cwi+dw])
dist = D[-1][-1]
print(ans-(dist+1) if dist!=-1 else -1)

Solution (Python):
import sys
from collections import deque
def input(): return sys.stdin.readline().strip()


def main():
    H, W = map(int, input().split())
    S = [input() for _ in range(H)]
    black = 0
    for i in range(H):
        for j in range(W):
            if S[i][j] == '

    q = deque([(0, 0, 0)]) 
    dist = -1
    visited = {(0, 0)}
    while q:
        i, j, c = q.popleft()
        if i == H - 1 and j == W - 1:
            dist = c
            break
        for di, dj in [(1, 0), (0, 1), (-1, 0), (0, -1)]:
            ni, nj = i + di, j + dj
            if (ni, nj) in visited: continue
            if 0 <= ni < H and 0 <= nj < W and S[ni][nj] == '.':
                q.append((ni, nj, c + 1))
                visited.add((ni, nj))

    if dist == -1:
        print(-1)
    else:
        print(H * W - black - dist - 1)


if __name__ == "__main__":
    main()

Solution (Python):
def read():
    H, W = map(int, input().split(' '))
    Ss = []
    for _ in range(H):
        Ss.append(input())
    return H, W, Ss
 
DIRS = [(-1, 0), (1, 0), (0, -1), (0, 1)]
 
def add(p1, p2):
    return (p1[0] + p2[0], p1[1] + p2[1])
 
def ans(H, W, Ss):
    if Ss[0][0] == '
        print('0,0 
        return -1
    ds =[ [-1 for _ in range(W)] for _ in range(H)]
    ds[0][0] = 1
    q = [(0, 0)]
    while q:
        p = q.pop()
        d = ds[p[1]][p[0]]
        for dr in DIRS:
            x, y = add(p, dr)
            if x < 0 or x >= W or y < 0 or y >= H:
                continue 
            if Ss[y][x] == '
                continue 
            if ds[y][x] >= 0 and ds[y][x] <= d + 1: 
                continue
            ds[y][x] = d + 1
            q.append((x, y))
    if ds[H-1][W-1] < 0:
        return -1
    
    ws = sum([l.count('.') for l in Ss])
    return ws - ds[H-1][W-1]
 
if __name__ == '__main__':
    H, W, Ss = read()
    print(ans(H, W, Ss))

Solution (Python):
from collections import deque
H,W=map(int, input().split())
S = ["
MAP=[]
MAP.append(S)
cnt = 0
for _ in range(H):
    tmp = ["
    cnt += tmp.count(".")
    MAP.append(tmp)
MAP.append(S)

move=[[1,0],[-1,0],[0,1],[0,-1]]
start=[1,1]

cheak = [[-1]*(W+2) for _ in range(H+2)]
cheak[1][1] = 0

que = deque()
que.append(start)
while que:
    tmp = que.popleft()
    x = tmp[0]
    y = tmp[1]
    for dx,dy in move:
        nx = x + dx
        ny = y + dy
        if MAP[nx][ny] == "." and cheak[nx][ny] == -1:
            que.append([nx,ny])
            cheak[nx][ny]=cheak[x][y]+1
if cheak[H][W] == -1:
    print(-1)
else:
    print(cnt-cheak[H][W]-1)

Solution (Python):






from collections import deque

import sys
sys.setrecursionlimit(10**6)
input = sys.stdin.readline

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


White = 0
White += Map[0].count('.', 1)
for i in range(1, H - 1):
    White += Map[i].count('.')
White += Map[-1].count('.', 0, -1)

s = (0, 0)
e = (H-1, W-1)

dis = [[-1]*W for _ in range(H)]

q = deque()
q.append(s)
dis[q[0][0]][q[0][1]] = 0
while q:
    for delta in [(-1, 0), (1, 0), (0, -1), (0, 1)]:
        y, x = [o + d for o, d in zip(q[0], delta)]
        if y < 0 or H - 1 < y or x < 0 or W - 1 < x:
            pass
        elif Map[y][x] == '
            pass
        elif dis[y][x] != -1:
            pass
        else:
            dis[y][x] = dis[q[0][0]][q[0][1]] + 1
            q.append((y, x))
            if (y, x) == e:
                break
    else:
        q.popleft()
        continue
    break

if dis[e[0]][e[1]] == -1:
    print(-1)
else:
    print(White-(dis[e[0]][e[1]]-1))

Solution (Python):
from collections import deque

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

mp = ['
memo = [[-1]*(W+1) for _ in range(H+1)]

cnt = 0
for _ in range(H):
  s = '
  cnt += s.count('.')
  mp.append(s)
  
ds = [[1,0], [-1,0], [0,1], [0,-1]]
h = deque([[1,1,1]])
while h:
  l = h.popleft()
  for d in ds:
    if l[0]+d[0] <= W and l[1]+d[1] <= H:
      if mp[l[1]+d[1]][l[0]+d[0]] == '.' and memo[l[1]+d[1]][l[0]+d[0]] == -1:
        memo[l[1]+d[1]][l[0]+d[0]] = l[2] + 1
        h.append([l[0]+d[0], l[1]+d[1], l[2] + 1])
  if memo[H][W] > -1:
    print(cnt-memo[H][W])
    exit()
    
print(memo[H][W])

Solution (Python):
h,w = map(int,input().split())
s = [0]*h
white = 0
for i in range(h):
	s[i] =  input()
	s[i] = list(s[i])
	for j in range(w):
		if s[i][j] == '.':
			white += 1

def clear_maze(sx, sy, gx, gy, maze):

	INF = 100000000

	field_x_length = len(maze)
	field_y_length = len(maze[0])
	distance = [[INF for i in range(field_y_length)] for j in range(field_x_length)]


	def bfs():
		queue = []

		queue.insert(0, (sx, sy))

		distance[sx][sy] = 0

		while len(queue):
			x, y = queue.pop()

			if x == gx and y == gy:
				break

			for i in range(0, 4):
				nx, ny = x + [1, 0, -1, 0][i], y + [0, 1, 0, -1][i]

				if (0 <= nx and nx < field_x_length and 0 <= ny and ny < field_y_length and maze[nx][ny] != '
					queue.insert(0, (nx, ny))
					distance[nx][ny] = distance[x][y] + 1

		return distance[gx][gy]
	return bfs()
if clear_maze(0, 0, h-1, w-1, s) == 100000000:
	print(-1)
else:
	print(white - clear_maze(0, 0, h-1, w-1, s) - 1)

Solution (Python):
from collections import deque

H, W = map(int, input().split())
H += 2
W += 2
grid = '
for _ in range(H-2):
    grid += '
grid += '

def bfs(start):
    INF = 10 ** 9
    dist = [INF] * (H*W)
    dist[start] = 0
    q = deque([start])
    move_list = [-1, 1, W, -W]
    while q:
        v = q.popleft()
        dv = dist[v]
        for move in move_list:
            w = v + move
            if grid[w] == '
                continue
            dw = dv + 1
            if dw >= dist[w]:
                continue
            dist[w] = dw
            q.append(w)
    return dist[-(W+2)]

d = bfs(W+1)
T = grid.count("

if d == 10 ** 9:
  print("-1")
else:
  print(H*W - T - (d+1))

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




def search() :
    flag=[[0]*W for i in range(H)]
    count=[[-1]*W for i in range(H)]
    flag[0][0]=1                               
    count[0][0]=0                              
    pos=deque([])
    pos.append([0,0])

    while len(pos)>0 :
        y,x=pos.popleft()
        if y==H-1 and x==W-1 :
            return count[H-1][W-1]
            break

        for p,q in [[1,0],[-1,0],[0,1],[0,-1]] :
            if 0<=y+p<H and 0<=x+q<W and maze[y+p][x+q]=="." and flag[y+p][x+q]==0 :
                flag[y+p][x+q]=1     
                pos.append([y+p,x+q])
                count[y+p][x+q]=count[y][x]+1    

    if y!=H-1 and x!=W-1 :
        print(-1)
        exit()         




for i in range(H) :
    for j in range(W) :
        if maze[i][j]=="." :    
            count+=1

ans=count-search()

print(ans)

Solution (Python):
from collections import deque
def MI(): return map(int, input().split())
INF=float('inf')
def bfs():
  que=deque()
  que.append((sx,sy))
  dist=[[INF] *W for _ in range(H)]
  dist[sx][sy]=0
  dx=[1,0,-1,0]
  dy=[0,1,0,-1]
  while que:
    x,y=que.popleft()
    if x==gx and y==gy:
      break
    for i in range(4):
      nx=x+dx[i]
      ny=y+dy[i]
      if 0<=nx<H and 0<=ny<W:
        if Map[nx][ny]!='
          if dist[nx][ny]==INF:
            dist[nx][ny]=dist[x][y]+1
            que.append((nx,ny))
  return dist[gx][gy]
H,W=MI()
Map=[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 Map[i][j]=='.':
      white+=1
res=bfs()
if 0<res<INF:
  print(white-res-1)
else:
  print(-1)

Solution (Python):
from collections import deque
INF=10**18
h,w=map(int,input().split())
a=[input() for _ in range(h)]
d=[[INF for _ in range(w)]for _ in range(h)]
dx=[0,1,0,-1]
dy=[1,0,-1,0]
sx,sy=0,0
gx,gy=h-1,w-1
d[sx][sy]=1
q=deque([(sx,sy)])
while q:
  x,y=q.popleft()
  if (x,y)==(gx,gy):break
  for i in range(4):
    nx,ny=x+dx[i],y+dy[i]
    if 0<=nx<h and 0<=ny<w:
      if a[nx][ny]=='.' and d[nx][ny]==INF:
        d[nx][ny]=d[x][y]+1
        q.append((nx,ny))
if d[gx][gy]==INF:print(-1)
else:
  cnt=0
  for i in a:
    cnt+=i.count('.')
  print(cnt-d[gx][gy])

Solution (Python):
from collections import deque
def MI(): return map(int, input().split())
def bfs():
  dist=[[INF] * (W+1) for _ in range(H+1)]
  dist[sx][sy]=0
  que=deque([])
  que.append((sx,sy))
  di=(-1,0,1,0)
  dj=(0,-1,0,1)
  while que:
    (x,y)=que.popleft()
    if x==gx and y==gy:
      break
    for k in range(4):
      ni=x+di[k]
      nj=y+dj[k]
      if 0<=ni<H and 0<=nj<W:
        if Map[ni][nj]!='
          if dist[ni][nj]==INF:
            dist[ni][nj]=dist[x][y]+1
            que.append((ni,nj))
  return dist[gx][gy]
H,W=MI()
Map=[list(input()) for _ in range(H)]

INF=float('inf')
(sx,sy)=(0,0)
(gx,gy)=(H-1,W-1)
res=bfs()
white=0
for i in range(H):
  for j in range(W):
    if Map[i][j]=='.':
      white+=1
if 0<res<INF:
  ans=white-res-1
  print(ans)
else:
  print(-1)

Solution (Python):
from collections import deque
h,w = map(int, input().split())
s = [list('
s = [['
z=0
for i in s:
  z += i.count('.')
ans = [[-1]*(w+2) for i in range(h+2)]
m = [[0,1],[0,-1],[1,0],[-1,0]]
ans[1][1] = 1
d = deque([[1,1]])
while len(d):
  x,y = d.popleft()
  for i,j in m:
    a,b = x+i,y+j
    if s[a][b] == '.' and ans[a][b] == -1:
      d.append([a,b])
      ans[a][b] = ans[x][y]+1
if ans[h][w] == -1:
  print(-1)
else:
  print(z-ans[h][w])

Solution (Python):
import queue
h,w=map(int,input().split())
INF=10**9
s=[[-1]* w for _ in range(h)]
b=0
for i in range(h):
	x=input()
	for j in range(w):
		if x[j]==".":
			s[i][j] = INF
		else:
			b+=1

q=queue.Queue()
s[0][0]=0
q.put((0,0))

def test(x,y,t):
	if 0<=x<h and 0<=y<w:
		u=s[x][y]
		if t<u:
			s[x][y]=t
			q.put((x,y))

while not q.empty():
	x,y=q.get()
	t=s[x][y]
	test(x+1,y,t+1)
	test(x-1,y,t+1)
	test(x,y+1,t+1)
	test(x,y-1,t+1)

x=s[h-1][w-1]
print(-1 if x==INF else h*w-b-x-1)

Solution (Python):
from collections import deque
n,m = map(int,input().split())
white = 0
maze = []
for _ in range(n):
  row = list(input())
  white += row.count(".")
  maze.append(row)
steps = [ [-1]*m for _ in range(n) ]
steps[0][0] = 0

q = deque([(0,0)])
while q:
  r,c = q.popleft()

  for x,y in [(1,0), (0,1), (-1,0), (0,-1)]:
    nr,nc = r+x,c+y
    if nr<0 or nc<0 or nr>=n or nc>=m: continue
    if maze[nr][nc] == "
    if steps[nr][nc] != -1: continue
    steps[nr][nc] = steps[r][c] + 1
    if nr==n-1 and nc==m-1:
      break
    else:
      q.append((nr,nc))

if steps[n-1][m-1] == -1:
  print(-1)
else:
  print( white - steps[n-1][m-1] - 1)

Solution (Python):
import collections
 
H,W = list(map(int,input().split()))
S = [list(input()) for _ in range(H)]
copyS = [S[i][:] for i in range(H)]
que = collections.deque()
que.append([0,0])
 
d = [[float('inf') for _ in range(W)] for _ in range(H)]
d[0][0] = 0
S[0][0] = '
 
while len(que) != 0:
    y,x = que.popleft()
    if y == H-1 and x == W-1:
        break
    for direct in [[1,0],[-1,0],[0,1],[0,-1]]:
        if 0 <= y+direct[0] <= H-1 and 0 <= x+direct[1] <= W-1:
            if S[y+direct[0]][x+direct[1]] != '
                d[y+direct[0]][x+direct[1]] = d[y][x]+1
                S[y+direct[0]][x+direct[1]] = '
                que.append([y+direct[0], x+direct[1]])

if y != H-1 or x != W-1:
    print(-1)
    exit()

count = 0
for i in range(H):
    for j in range(W):
        if copyS[i][j] == '.':
            count += 1
print(count - (d[y][x]+1))

Solution (Python):
from collections import deque

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

cnt_white = 0
for row in s:
    cnt_white += row.count('.')

d = deque([[0, 0]])
dist = [[-1] * w for _ in range(h)]
dist[0][0] = 0
dx = [-1, 0, 1, 0]
dy = [0, -1, 0, 1]
goal_flag = False
while d:
    x, y = d.popleft()
    if x == h - 1 and y == w - 1:
        goal_flag = True
        break
    for i in range(4):
        pos_x, pos_y = x + dx[i], y + dy[i]
        if 0 <= pos_x < h and 0 <= pos_y < w and s[pos_x][pos_y] == '.' and dist[pos_x][pos_y] == -1:
            d.append([pos_x, pos_y])
            dist[pos_x][pos_y] = dist[x][y] + 1

if goal_flag:
    print(cnt_white - dist[h-1][w-1] - 1)
else:
    print(-1)

Solution (Python):


from collections import deque
H, W = map(int,input().split())
S = []
count = 0
for h in range(H):
    A = list(input())
    for a in A:
        if a == ".":
            count += 1
    S.append(A)


mas = deque([(0, 0, 0)])
while mas: 
    y, x, n = mas.popleft()
    if (0 <= y <= H -1) and (0 <= x <= W -1):
        if S[y][x] == ".":
            S[y][x] = n
            mas.append((y + 1, x, n + 1))
            mas.append((y, x + 1, n + 1))
            mas.append((y - 1, x, n + 1))
            mas.append((y, x - 1, n + 1))


short = S[H -1][W -1]
if short == ".": 
    print("-1")
else:
    print(count - (short + 1))

Solution (Python):
h,w=map(int,input().split())
maze=[list(input()) for _ in range(h)]
dx=[1,0,-1,0]
dy=[0,1,0,-1]
queue=[]
ans = 0
cn = 0
for i in maze:
     cn += i.count("
queue.append([0,0,0])
while len(queue)>0:
    x,y,cnt=queue.pop(0)
    ans=cnt
    if x == h - 1 and y == w - 1:
        print(h*w-ans-cn-1)
        exit()
    for i in range(4):
        X=x+dx[i]
        Y = y + dy[i]
        if not (0 <= X < h and 0 <= Y < w):
             continue
        if maze[X][Y]=="
            continue
        if maze[X][Y]==".":
            queue.append([X,Y,cnt+1])
            maze[X][Y]="
print(-1)