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 numpy as np
from collections import deque
H, W = map(int, input().split())
S = [input() for i in range(H)]

L = [[-1] * W for i in range(H)]
L[0][0] = 0
Open = deque([np.array([0,0])])
D = np.array([[0,1], [1,0], [-1,0], [0,-1]])
white = 0
for s in S:
    for s2 in s:
        if s2 == ".":
            white += 1
while True:
    if len(Open) == 0:
        print(-1)
        exit()
    n = Open.popleft()
    for d in D:
        nNew = n+d
        if not(0 <= nNew[0] < H and 0 <= nNew[1] < W):
            continue
        if S[nNew[0]][nNew[1]] == "
            continue
        if L[nNew[0]][nNew[1]] == -1:
            L[nNew[0]][nNew[1]] = L[n[0]][n[1]] + 1
            Open.append(nNew)
        if (nNew == np.array([H-1,W-1])).all():
            print(white - L[H-1][W-1] - 1)
            exit()

Solution (Python):
from collections import deque
import sys
H,W=map(int,input().split())
S =[]
kuro=0
for i in range(H):
    s = list(input())
    for j in s:
        if j=='
            kuro +=1
    S.append(s)

visit=[[False]*W for i in range(H)]
dist=[[]]
kei=deque()
kei.append((0,0,1))
visit[0][0]=True
X =[-1,0,1,0]
Y=[0,-1,0,1]
while kei:
    y,x,d=kei.popleft()
    if y==H-1 and x==W-1:
        print(H*W-d-kuro)
        sys.exit()
    for i in range(4):
        nx = x +X[i]
        ny = y +Y[i]
        if (0<=nx< W) and (0<=ny<H) and S[ny][nx]=='.':
            if not visit[ny][nx]:
                kei.append((ny,nx,d+1))
                visit[ny][nx]=True
print(-1)

Solution (Python):
from collections import deque
import sys
H,W=map(int,input().split())
S =[]
kuro=0
for i in range(H):
    s = list(input())
    for j in s:
        if j=='
            kuro +=1
    S.append(s)

visit=[[False]*W for i in range(H)]
dist=[[]]
kei=deque()
kei.append((0,0,1))
visit[0][0]=True
X =[-1,0,1,0]
Y=[0,-1,0,1]
while kei:
    y,x,d=kei.popleft()
    if y==H-1 and x==W-1:
        print(H*W-d-kuro)
        sys.exit()
    for i in range(4):
        nx = x +X[i]
        ny = y +Y[i]
        if (0<=nx< W) and (0<=ny<H) and S[ny][nx]=='.':
            if not visit[ny][nx]:
                kei.append((ny,nx,d+1))
                visit[ny][nx]=True
print(-1)

Solution (Python):
from collections import deque

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

ans = 0
c = []

for i in range(h):
    ci = list(input())
    ans += ci.count(".")
    c.append(ci)

sy = 0
sx = 0
gy = h-1
gx = w-1

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

que = deque([(sy,sx)])
c[sy][sx] = 1
while bool(que):
    y, x = que.popleft()
    if y == gy and x == gx:
        break
    for i in range(4):
        yi = y + dy[i]
        xi = x + dx[i]
        if 0 <= yi < h and 0 <= xi < w and c[yi][xi] == ".":
            que.append((yi,xi))
            c[yi][xi] = c[y][x] + 1

if c[gy][gx] == ".":
    print(-1)
else:
    print(ans - c[gy][gx])

Solution (Python):
from collections import deque
H, W = map(int, input().split())
inf = float("inf")
s = [["
D = [[inf] * (W + 2)]
white_num = 0
for i in range(H):
    main = list(input())
    white_num += len([e for e in main if e == "."])
    s.append(["
    D.append([inf] * (W + 2))
s.append(["
D.append([inf] * (W + 2))


def BFS():  
    global D
    D[1][1] = 1
    q = deque()
    q.append((1, 1))
    while len(q) != 0:
        p = q.popleft()
        for e in [(p[0] + 1, p[1]), (p[0], p[1] + 1), (p[0] - 1, p[1]), (p[0], p[1] - 1)]:
            if s[e[0]][e[1]] == "." and D[e[0]][e[1]] == inf:
                D[e[0]][e[1]] = D[p[0]][p[1]] + 1
                q.append(e)
                if e == (H, W):
                    return white_num - D[H][W]
    return -1


print(BFS())

Solution (Python):
from collections import deque
h, w =map(int, input().split())
s = [input() for i in range(h)]
s_x, s_y = 0, 0



max = 0
c = [[0] * w for i in range(h)]



def BFS():
    q = deque()
    q.append((s_x, s_y))

    while len(q) > 0:
        y, x = q.popleft()
        if y == h - 1 and x == w - 1:
            return c[y][x]
        if x < w - 1:
            if s[y][x+1] == '.' and c[y][x+1] == 0:
                q.append((y, x+1))
                c[y][x+1] = c[y][x] + 1
        if x > 0:
            if s[y][x-1] == '.' and c[y][x-1] == 0:
                q.append((y, x-1))
                c[y][x-1] = c[y][x] + 1
        if y < h - 1:
            if s[y+1][x] == '.' and c[y+1][x] == 0:
                q.append((y+1, x))
                c[y+1][x] = c[y][x] + 1
        if y > 0:
            if s[y-1][x] == '.' and c[y-1][x] == 0:
                q.append((y-1, x))
                c[y-1][x] = c[y][x] + 1

    return(-1)

area = h*w
blunk_num_origin = 0
for ch1 in s:
    for ch2 in ch1:
        if ch2 == '
            blunk_num_origin += 1

min_grid = BFS()
if min_grid == -1:
    print(min_grid)
else:
    sol = area-blunk_num_origin-2-(min_grid-1)
    
    print(sol)

Solution (Python):
import numpy as np
H,W = map(int,input().split())
H += -1
W += -1
import sys
ma = [[c for c in l.strip()] for l in sys.stdin]
ya = []
for s in ma:
  ya.extend(s)
count = ya.count(".")
ma = np.array(ma,"U10")
ma[0][0] = 1
que = []
que.append([0,0])
while len(que) > 0:
  y,x = que.pop(0)
  if y == H and x == W:
    break
  score = ma[y][x]
  try:
    if y != 0:
      y1 = ma[y-1][x] 
  except:
    pass
  try:
    y2 = ma[y+1][x]
  except:
    pass
  try:
    if x != 0:
      x1 = ma[y][x-1]
  except:
    pass
  try:
    x2 = ma[y][x+1] 
  except:
    pass
  try:
    if y1 == ".":
      ma[y-1][x] = str(int(score) + 1)
      que.append([y-1, x])
  except:
    pass
  try:
    if y2 == ".":
      ma[y+1][x] = str(int(score) + 1)
      que.append([y+1, x])
  except:
    pass
  try:
    if x1 == ".":
      ma[y][x-1] = str(int(score) + 1)
      que.append([y, x-1])
  except:
    pass
  try:
    if x2 == ".":
      ma[y][x+1] = str(int(score) + 1)
      que.append([y, x+1])
  except:
    pass
  x1 = 999
  x2 = 999
  y1 = 999
  y2 = 999
if ma[H][W] == ".":
  print(-1)
else:
  ten = int(ma[H][W])
  print(count - ten)

Solution (Python):
from collections import deque
h, w = map(int, input().split())
maze = []
white = 0
que = deque([])
visited = []
dirs = [[-1, 0], [1, 0], [0, -1], [0, 1]]
ans = -1

for i in range(h):
  temp = list(input())
  white += temp.count('.')
  maze.append(temp)

for i in range(h):
  visited.append([0]*w)

visited[0][0] = 1
que.append([0, 0, 1])

while len(que):
  y, x, count = que.popleft()
  
  if x == w-1 and y == h-1:
    ans = white - count
    break
  
  for dir in dirs:
    if y+dir[0] < 0 or y+dir[0] >= h or x+dir[1] < 0 or x+dir[1] >= w:
      continue

    if maze[y+dir[0]][x+dir[1]] == '.' and visited[y+dir[0]][x+dir[1]] == 0:
      visited[y+dir[0]][x+dir[1]] = 1
      que.append([y+dir[0], x+dir[1], count+1])

print(ans)

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

memo = [[0]*w for i in range(h)]

from collections import deque
q = deque()
q.append((0, 0))

while len(q) > 0:
    y, x = q.popleft()
    if y == h-1 and x == w-1:
        break
    if x > 0:
        if s[y][x-1] == "." and memo[y][x-1] == 0:
            q.append((y, x-1))
            memo[y][x-1] = memo[y][x] + 1
    if x < w-1:
        if s[y][x+1] == "." and memo[y][x+1] == 0:
            q.append((y, x+1))
            memo[y][x+1] = memo[y][x] + 1
    if y > 0:
        if s[y-1][x] == "." and memo[y-1][x] == 0:
            q.append((y-1, x))
            memo[y-1][x] = memo[y][x] + 1
    if y < h-1:
        if s[y+1][x] == "." and memo[y+1][x] == 0:
            q.append((y+1, x))
            memo[y+1][x] = memo[y][x] + 1

count = 0

for H in range(h):
    for W in range(w):
        if s[H][W] == "
            count += 1

if memo[h-1][w-1] == 0:
    print(-1)
else:
    print(w*h - memo[h-1][w-1]-1 - count)

Solution (Python):
from collections import deque
from itertools import chain
H, W = map(int, input().split(' '))
Maze = [list(input()) for _ in range(H)]
White = list(chain.from_iterable(Maze)).count('.')
Maze[0][0] = 1
q = deque([])
current = [0, 0]
q.append(current)

dir_x = [1, -1, 0, 0]
dir_y = [0, 0, 1, -1]
while len(q) > 0:
    now_y, now_x = q.popleft()
    if now_y == H-1 and now_x == W-1 : break
    for (dx, dy) in zip(dir_x, dir_y):
        if 0 <= now_y + dy <= H-1 and 0 <= now_x + dx <= W-1 and Maze[now_y + dy][now_x + dx] == '.':
            Maze[now_y + dy][now_x + dx] = Maze[now_y][now_x] + 1
            q.append([now_y + dy, now_x + dx])


if Maze[H-1][W-1] == '.': print(-1)
else: print(White - Maze[H-1][W-1])

Solution (Python):
import queue
h, w = map(int, input().split())
masu = [input() for _ in range(h)]
dx = [1, 0, -1, 0]
dy = [0, -1, 0, 1]
INF = 100000
cood = (0, 0)
d = [[INF for _ in range(w)] for _ in range(h)]
d[0][0] = 0

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

que = queue.Queue()
que.put((0, 0))
while not que.empty():
    cood = que.get()
    if cood[0] == h-1 and cood[1] == w-1:
        break
    for i in range(4):
        ncood = (cood[0] + dy[i], cood[1] + dx[i])
        if 0 <= ncood[0] and ncood[0] < h and 0 <= ncood[1] and ncood[1] < w and masu[ncood[0]][ncood[1]] != '
            que.put(ncood)
            d[ncood[0]][ncood[1]] = d[cood[0]][cood[1]] + 1


if d[h-1][w-1] == INF:
    print(-1)
else:
    print(h*w - d[h-1][w-1] - 1 - black_num)

Solution (Python):
h,w=map(int,input().split())
s=[[] for j in range(h)]
t=[[0]*w for k in range(h)]
t[0][0]=1
q=0
u=[]
for i in range(h):
    s[i]+=list(input())
    q+=s[i].count("
u.append((0,0))
while u!=[]:
    (x,y)=u[0]
    if x!=h-1:
        if t[x+1][y]==0 and s[x+1][y]==".":
            t[x+1][y]=t[x][y]+1
            u.append((x+1,y))
    if y!=w-1:        
        if t[x][y+1]==0 and s[x][y+1]==".":
            t[x][y+1]=t[x][y]+1
            u.append((x,y+1))
    if x!=0:        
        if t[x-1][y]==0 and s[x-1][y]==".":
            t[x-1][y]=t[x][y]+1
            u.append((x-1,y))
    if y!=0:        
        if t[x][y-1]==0 and s[x][y-1]==".":
            t[x][y-1]=t[x][y]+1
            u.append((x,y-1))
    u.pop(0)
if t[h-1][w-1]==0:
    print(-1)
else:    
    print((h*w-t[h-1][w-1])-q)

Solution (Python):
H,W = map(int,input().split())
s=[]
for i in range(H):
    s.append(input().strip())
dist=[[float("inf")]*W for i in range(H)]
Q=[]
for i in range(H):
    for j in range(W):
        if s[i][j] == ".":
            Q.append((i,j))
dist[0][0]=0
while len(Q) > 0:
    Q=sorted(Q,key=lambda x: dist[x[0]][x[1]])
    pt=Q.pop(0)
    if pt==(H-1,W-1):
        break
    dpt = dist[pt[0]][pt[1]]
    for nbr in [(pt[0]-1,pt[1]),(pt[0],pt[1]-1),(pt[0]+1,pt[1]),(pt[0],pt[1]+1)]:
        if nbr in Q:
            dist[nbr[0]][nbr[1]] = min(dist[nbr[0]][nbr[1]],dpt+1)
    

print(max(H*W-sum(i.count("

Solution (Python):
import sys
from collections import deque
sys.setrecursionlimit(10**8)

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

Kuro = 0
Shiro = 0
for j in range(H):
    for i in range(W):
        if S[j][i]=='.':
            Shiro += 1
Dis =[[-1]*W for i in range(H)]
X =[-1, 0, 1, 0]
Y =[0, -1, 0, 1]
q = deque()
q.append((0,0))
Dis[0][0] = 0
a=deque()
while (q != a):
    y,x = q.popleft()
    if (y==H-1) and (x==W-1):
        break
    for i in range(4):
        nx = x + X[i]
        ny = y + Y[i]
        if (0<= nx < W) and(0 <= ny < H) and (S[ny][nx]=='.') and (Dis[ny][nx] ==-1):
            q.append((ny,nx))
            Dis[ny][nx] = Dis[y][x] +1

if (Dis[H-1][W-1]==-1):
    print(-1)
else:
    print(Shiro-Dis[H-1][W-1]-1)

Solution (Python):
h, w = map(int, raw_input().split())
grid = [raw_input() for y in range(h)]
dist = [[-1]*w for y in range(h)]
que = [(0,0)]
dist[0][0] = 0
while que != []:
    cx, cy = que.pop(0)
    for dx, dy in [(1,0), (0,1), (-1,0), (0,-1)]:
        nx, ny = cx+dx, cy+dy
        if (0 <= nx < w) and (0 <= ny < h) and (grid[ny][nx] == '.') and (dist[ny][nx] == -1):
            que.append((nx, ny))
            dist[ny][nx] = dist[cy][cx] + 1
d = dist[h-1][w-1]
if d == -1:
    print -1
else:
    print (h*w - d - 1 - sum([len(filter(lambda c: c=="

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

dist = [[float('inf') for _ in range(w)] for _ in range(h)]
dist[0][0] = 0
next_move = [[0, 0]]
x = [1, 0, -1, 0]
y = [0, 1, 0, -1]

while len(next_move):
    if next_move[0] == [h-1, w-1]:
        break
    
    for i in range(4):
        nx = next_move[0][1] + x[i]
        ny = next_move[0][0] + y[i]
        if (nx >= 0 and nx < w and ny >= 0 and ny < h and 
            cell[ny][nx] != '
            dist[ny][nx] = dist[next_move[0][0]][next_move[0][1]] + 1
            next_move.append([ny, nx])
    next_move.pop(0)

cnt = 0
for i in range(h):
    for t in range(w):
        
        if cell[i][t] == '
            cnt += 1
            
if dist[h-1][w-1] == float('inf'):
    print(-1)
else:
    print((h*w) - (dist[h-1][w-1] + 1) - cnt)

Solution (Python):
class Queue:
    class Node:
        def __init__(self, item):
            self.item=item
            self.next=None
    def __init__(self):
        self.head=None
        self.tail=None
    def enqueue(self, item):
        node=Queue.Node(item)
        if self.head:
            assert self.tail is not None
            self.tail.next=node
            self.tail=node
        else:
            assert self.tail is None
            self.head=node
            self.tail=node
    def dequeue(self):
        assert self.head is not None
        node=self.head
        if self.head==self.tail:
            self.head=None
            self.tail=None
        else:
            self.head=node.next
        return node.item
    def empty(self):
        if self.head: return False
        else: return True

h, w=[int(word) for word in input().split()]
map=[["
visited=[[False for hi in range(h+2)] for wi in range(w+2)]
num_white=0
for hi in range(1, h+1):
    l=input()
    for wi in range(1, w+1):
        map[wi][hi]=l[wi-1]
        if l[wi-1]==".": num_white+=1
queue=Queue()
queue.enqueue((1, 1, 0))
length=None
while not queue.empty():
    wi, hi, l=queue.dequeue()
    if wi==w and hi==h:
        length=l
        break
    if visited[wi][hi]: continue
    if map[wi][hi]==".":
        visited[wi][hi]=True
        queue.enqueue((wi-1, hi, l+1))
        queue.enqueue((wi+1, hi, l+1))
        queue.enqueue((wi, hi-1, l+1))
        queue.enqueue((wi, hi+1, l+1))
if length is not None:
    print(num_white-length-1)
else:
    print(-1)

Solution (Python):
h,w=map(int,input().split())
maze=['
white=0
for i in range(h):
    r=input()
    maze.append('
    white+=r.count('.')
maze.append('
dxy=((1,0),(-1,0),(0,1),(0,-1))
dist=[[-1] *(w+2) for i in range(h+2)]
def bfs():
    queue=[]
    queue.insert(0,(1,1))
    dist[1][1]=0
    while len(queue):
        x,y=queue.pop()
        if x==w and y==h:
            break
        for (dx,dy) in dxy:
            nx, ny= x+dx, y+dy
            if maze[ny][nx]=='.' and dist[ny][nx]==-1:
                queue.insert(0,(nx,ny))
                dist[ny][nx]=dist[y][x]+1
    return dist

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

Solution (Python):
h,w = map(int,input().split())
counter = 0
space = [[-1 for i in range(w+2)]]
for i in range(1,h+1):
    r = input()
    s = list("
    counter += r.count("
    space.append([])
    for j,moji in enumerate(s):
        if moji == ".":
            space[i].append(0)
        elif moji =="
            space[i].append(-1)
space.append([-1 for i in range(w+2)])

sx,sy = 1,1
ex,ey = h,w

watch_space = [[sx,sy]]
decided_space = [[sx,sy]]
flag = 0
while(True):
    tmp = list()
    for [i,j] in watch_space:
        if [i-1,j] not in decided_space and space[i-1][j] == 0:
            space[i-1][j] = space[i][j]+ 1
            decided_space.append([i-1,j])
            tmp.append([i-1,j])
        if [i+1,j] not in decided_space and space[i+1][j] == 0:
            space[i+1][j] = space[i][j]+ 1
            decided_space.append([i+1,j])
            tmp.append([i+1,j])
        if [i,j+1] not in decided_space and space[i][j+1] == 0:
            space[i][j+1] = space[i][j]+ 1
            decided_space.append([i,j+1])
            tmp.append([i,j+1])
        if [i,j-1] not in decided_space and space[i][j-1] == 0:
            space[i][j-1] = space[i][j]+ 1
            decided_space.append([i,j-1])
            tmp.append([i,j-1])
    watch_space = tmp
    if [ex,ey] in decided_space:
        break
    elif len(watch_space) < 1:
        flag = -1
        break
if flag == 0:
    ans = (w*h)-(space[ex][ey]+1) - counter
    print(ans)
else:
    print(-1)

Solution (Python):
h, w = [int(x) for x in input().split()]
maze = []
whitesum = 0
for i in range(h):
  m = input()
  whitesum += m.count('.') 
  maze.append(m)
dist = [[-1]*w for i in range(h)]
dxy = ((1,0),(-1,0),(0,1),(0,-1))

def bfs():
  queue = []
  queue.insert(0,(1,1))
  dist[0][0] = 0
  while(len(queue)):
    x, y = queue.pop()
    if x == w and y == h:
      break
    for (dx, dy) in dxy:
      nx, ny = x+dx, y+dy
      
      if(nx>0 and nx<=w and ny>0 and ny<=h and maze[ny-1][nx-1] == '.' and dist[ny-1][nx-1] == -1):
        queue.insert(0, (nx, ny))
        dist[ny-1][nx-1] = dist[y-1][x-1] + 1
        
bfs()
if dist[h-1][w-1] == -1:
  print(-1)
else:
  print(whitesum-dist[h-1][w-1]-1)

Solution (Python):
H, W = map(int,input().split())
s = [list(input()) for i in range(H)]
num_of_point = 0
for i in range(H):
    for j in range(W):
        if s[i][j] == '.':
            num_of_point += 1
 
counter = 0
position = [[0,0]]
while True:
    counter += 1
    new_position =[]
    for i,j in position:
        for i_,j_ in [[-1,0],[1,0],[0,1],[0,-1]]:
            i_new = i+i_
            j_new = j+j_
            if i_new >=0 and i_new <= H-1 and j_new >= 0 and j_new <= W-1:
                if s[i_new][j_new] == '.':
                    new_position.append([i_new,j_new])
                    s[i_new][j_new] = counter
    if [H-1,W-1] in new_position:
        print(num_of_point-counter-1)
        break
    if counter >= H*W:
      	print(-1)
      	break
    position = new_position

Solution (Python):
tmp = list(map(int,input().split()))
h, w = tmp[0],tmp[1]
maze = []
for i in range(h):
    maze.append([i for i in input()])
maze[0][0] = 0
i = 0
def change(data,p,q,i):
    if data[p][q] == ".":
        data[p][q] = i+1

def makechange(data,j,k,i):
    if j != h-1:
        change(data,j+1,k,i)
    if k != w-1:
        change(data,j,k+1,i)
    if j != 0:
        change(data,j-1,k,i)
    if k != 0:
        change(data,j,k-1,i)

while(True):
    ifhenka = False
    newmaze = [i for i in maze]
    for j in range(h):
        for k in range(w):
            if maze[j][k] == i:
                makechange(maze,j,k,i)
    if maze[h-1][w-1] != ".":
        break
    if i == 2500:
        print(-1)
        quit()
    i += 1

ans = 0
for i in maze:
    ans += i.count("
print(h*w - ans - maze[h-1][w-1] - 1)

Solution (Python):
from collections import deque

h,w=[int(i) for i in input().split() ]

graph=[[None for i in range(w+2)] for j in range(h+2)]
wnum=0
for i in range(w+2):
    graph[0][i]=['
    graph[h+1][i]=['
for j in range(h+2):
    graph[j][0]=['
    graph[j][w+1]=['
for i in range(h):
    a=input()
    for j in range(w):
        if a[j]=='.':
            wnum+=1
        graph[i+1][j+1]=[a[j],None]

q=deque([])
q.append((1,1))
graph[1][1][1]=0
d_min=None
while len(q)!=0:
    x,y=q.popleft()
    for cx,cy in ((x-1,y),(x+1,y),(x,y-1),(x,y+1)):
        if graph[cx][cy][0]=='.':
            if graph[cx][cy][1]==None:
                graph[cx][cy][1]=graph[x][y][1]+1
                if (cx,cy)==(h,w):
                    d_min=graph[cx][cy][1]
                    break
                q.append((cx,cy))
if d_min!=None:
   print(wnum-d_min-1)
else:
   print(-1)

Solution (Python):
from collections import defaultdict, Counter
from itertools import product, groupby, count, permutations, combinations
from math import pi, sqrt
from collections import deque
from bisect import bisect, bisect_left, bisect_right
from string import ascii_lowercase
from functools import lru_cache
import sys
sys.setrecursionlimit(10000)
INF = float("inf")
YES, Yes, yes, NO, No, no = "YES", "Yes", "yes", "NO", "No", "no"
dy4, dx4 = [0, 1, 0, -1], [1, 0, -1, 0]


def inside(y, x, H, W):
    return 0 <= y < H and 0 <= x < W


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

    num_white = 0
    field = []
    for _ in range(H):
        field.append(list(input()))
        num_white += field[-1].count(".")

    memo = [[INF] * W for _ in range(H)]
    memo[0][0] = 1

    que = deque()
    que.append((0, 0))
    while que:
        y, x = que.popleft()
        c = memo[y][x]

        for i in range(len(dy4)):
            ny, nx = y + dy4[i], x + dx4[i]

            if inside(ny, nx, H, W) and memo[ny][nx] > c + 1 and field[ny][nx] == '.':
                memo[ny][nx] = c + 1
                que.append((ny, nx))

    if memo[-1][-1] == INF:
        return -1
    else:
        return num_white - memo[H - 1][W - 1]


def main():
    print(solve())


if __name__ == '__main__':
    main()

Solution (Python):
h,w = map(int,input().split())
grid = [[0 for j in range(0,w)] for i in range(0,h)]
black = 0
for i in range(0,h):
    c = list(input())
    grid[i] = c
for j in range(0,h):
    for i in range(0,w):
        if grid[j][i] == "
            black += 1

point = [[0 for j in range(0,w)] for i in range(0,h)]
q = [(0,0)]
def haba(y,x):
    nextPoint = [[y+1,x],[y,x+1],[y-1,x],[y,x-1]]
    for ny,nx in nextPoint:
        if ny >= 0 and ny < h and nx >= 0 and nx < w:
            if grid[ny][nx] == "." and point[ny][nx] == 0:
                point[ny][nx] = point[y][x] + 1
                q.append((ny,nx))
while len(q)>0:
    (y,x) = q.pop(0)
    haba(y,x)
if point[h-1][w-1] == 0:
    print("-1")
else:
    print((h*w) - point[h-1][w-1] - 1 - black)

Solution (Python):
h, w =map(int, input().split())

a=['
for i in range(h):
    b='
    a.append(b)
a.append('


from collections import Counter

n=[(1,1)]
route={(1,1):0}
p=[[1,0],[0,1],[-1,0],[0,-1]]
count=1
while route.get((h,w),0)==0 and count != 10000:
    n2=[]
    
    for i in n:
        for j in p:
            np=(i[0]+j[0],i[1]+j[1])
            if a[np[0]][np[1]]=='.' and route.get(np,-1)==-1:
                n2.append(np)
                if route.get(np,1000)>count:
                    route[np]=count
    n=n2
    
    count+=1

    
a2=[]
for i in a:
    for j in range(len(i)):
        a2.append(i[j])
con=Counter(a2)


if count==10000:
    print('-1')
else:
    print(con['.']-route[(h,w)]-1)

Solution (Python):
H, W = list(map(int, input().split()))

import heapq

f = []
count = 0
for _ in range(H):
    line = list(input())
    f.append(line)
    count += sum([1 if x == '.' else 0 for x in line])

v = [[2501 for i in range(W)] for j in range(H)]
v[0][0] = 0

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

heap = [(0,0,0)]
while len(heap) > 0:
    w, x, y = heapq.heappop(heap)
    for i in range(4):
        nx = x+dx[i]
        ny = y+dy[i]
        if (nx >= 0 and nx < W and ny >= 0 and ny < H):
            if nx == W-1 and ny == H-1:
                print(count - w -2)
                exit()
            elif f[ny][nx] == '
                pass
            else:
                if v[ny][nx] > w+1:
                    v[ny][nx] = w+1
                    heapq.heappush(heap, (w+1, nx, ny))

print(-1)

Solution (Python):
H, W = map(int, input().split())
walls = 0
S = [0] * H
for i in range(H):
    L = input()
    walls += L.count('
    S[i] = '
S = ['
V = [[0] * (W+2) for _ in range(H+2)]

q = [(1, 1, 1)]
while q:
    x, y, c = q.pop(0)

    if (x, y) == (H, W):
        
        print(H * W - walls - c)
        break

    for m, n in {(0, 1), (0, -1), (1, 0), (-1, 0)}:
        i, j = x+m, y+n
        if S[i][j] == '
            continue
        q.append((i, j, c+1))
        V[i][j] = 1

else:
    print(-1)

Solution (Python):


from collections import deque

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



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

d=[[float("inf") for i in range(w)] for j in range(h)] 
d[0][0]=0 
queue=deque([]) 
queue.append([0,0]) 


while len(queue): 
    p=queue.popleft() 
    if p==[h-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 s[ny][nx]=="." and d[ny][nx]==float("inf")):
            queue.append([ny,nx]) 
            d[ny][nx]=d[p[0]][p[1]]+1 


if d[h-1][w-1]==float("inf"): 
    print(-1)
else: 
    tot=0
    for i in range(h): 
        for j in range(w):
            if s[i][j]=="
    print(h*w-((d[h-1][w-1]+1)+tot))

Solution (Python):
h, w = map(int, input().split())

field = []
visited = {(1, 1)}

white_count = 0

field.append("


for i in range(h):
    row = input()
    field.append("
    white_count += row.count(".")

field.append("


def is_movable(x, y):
    state = (x, y)

    
    if state in visited:
        return False

    if field[y][x] == "
        return False
    else:
        return True


def breadth_search(field):
    
    queue = [(1, 1, 1)]

    while queue:
        x, y, count = queue.pop(0)

        if(x == w and y == h):
            return count

        if(is_movable(x+1, y)):
            visited.add((x+1, y))
            queue.append((x+1, y, count+1))

        if(is_movable(x, y+1)):
            visited.add((x, y+1))
            queue.append((x, y+1, count+1))

        if(is_movable(x-1, y)):
            visited.add((x-1, y))
            queue.append((x-1, y, count+1))

        if(is_movable(x, y-1)):
            visited.add((x, y-1))
            queue.append((x, y-1, count+1))

    return 0


count = breadth_search(field)

if count == 0:
    print(-1)
else:
    print(white_count-count)

Solution (Python):
from collections import deque
import sys
INF = 500000000000
sys.setrecursionlimit(2147483647)

def bfs(posit):
    y,x = posit
    n = [(y - 1, x), (y  + 1, x), (y, x - 1), (y, x + 1)]
    for ny, nx in n:
        if 0 <= ny < H and 0 <= nx < W and s[ny][nx] != "
            temp = dist[ny][nx]
            dist[ny][nx] = min(temp, dist[y][x] + 1)
            if temp != dist[ny][nx]:
                route.append((ny, nx))
            if (ny, nx) == (H - 1, W - 1):
                return
    if len(route) > 0:
        bfs(route.popleft())

H,W = [int(i) for i in input().split()]
s = []
route = deque()
black = 0
for i in range(H):
    po = list(input())
    black += po.count("
    s.append(po)
dist = [[INF for _ in range(W)] for _ in range(H)]
dist[0][0] = 0
bfs((0, 0))
if 0 < dist[H - 1][W - 1] < INF:
    print(H * W - black - dist[H - 1][W - 1] - 1)
else:
    print(-1)

Solution (Python):
import sys

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

board = [0 for i in range(H)]
for i in range(H):
    board[i] = list(input())
INF = 100000
dis = [[INF for i in range(H)] for j in range(W)]
queue = []
queue.insert(0, (0, 0))
dis[0][0] = 0
while len(queue):
    x, y = queue.pop()

    if x == W - 1 and y == H - 1:
        count = 0
        for i in range(W):
            for j in range(H):
                if board[j][i] == "
                    count += 1
        print(H*W - count - dis[W-1][H-1] -1)
        sys.exit()
        break

    for i in range(0, 4):
        nx, ny = x + [1, 0, -1, 0][i], y + [0, 1, 0, -1][i]
        if 0 <= nx < W and 0 <= ny < H and board[ny][nx] != "
            if dis[nx][ny] == INF:
                queue.insert(0, (nx, ny))
                dis[nx][ny] = dis[x][y] + 1

print(-1)

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

M = [input() for i in range(h)]
N = [[False]*w for i in range(h)]

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


que = deque([[0,0,1]])
while que:
    x,y,c = que.popleft()

    if M[y][x] == "
        continue
    elif N[y][x]:
        continue
    elif x == w-1 and y == h-1:
        
        print(h*w-(c+cnt))
        quit()

    else:
        N[y][x]=True
        A = [[x+1,y,c+1],[x-1,y,c+1],[x,y+1,c+1],[x,y-1,c+1]]
        for a in A:
            if 0<=a[0]<=w-1 and 0<=a[1]<=h-1:
                que.append(a)
                
print(-1)

Solution (Python):


H,W=map(int,raw_input().split())
maze=[]
for i in xrange(H):
 maze.append(list(raw_input()))
d=[[-1 for i in xrange(W+1)] for j in xrange(H+1)]
dx=[1,0,-1,0]
dy=[0,1,0,-1]

def bfs():
 q=[]
 q.insert(0,(0,0))
 d[sx][sy]=0
 while len(q):
  x,y=q.pop()
  if x==gx and y==gy:
   break
  for i in xrange(4):
   nx,ny=x+dx[i],y+dy[i]
   if 0<=nx<H and 0<=ny<W and maze[nx][ny]!='
    q.insert(0,(nx,ny))
    d[nx][ny]=d[x][y]+1
 return d[gx][gy]
sx,sy=0,0
gx,gy=H-1,W-1

def cntsharp():
 cnt=0
 for i in xrange(H):
  cnt+=maze[i].count('
 return cnt
if bfs()==-1:
 print -1
else:
 print H*W-(bfs()+cntsharp())-1

Solution (Python):
H, W = map(int, input().split())
table = []
for _ in range(H):
    table.append(input())
w = sum(v.count(".") for v in table)    
dist = [[-1 for _ in range(W)] for _ in range(H)]
dist[0][0] = 0
import queue
qu = queue.Queue()
qu.put((0,0))
while not qu.empty():
    x,y = qu.get()
    for dx,dy in ((1,0), (0,1), (-1,0), (0,-1)):
        nx,ny = dx + x , dy + y
        if nx >= 0 and nx < H and ny >= 0 and ny < W:            
            if table[nx][ny] == "." and dist[nx][ny] == -1:
                dist[nx][ny] = dist[x][y] + 1
                qu.put((nx,ny))
if dist[-1][-1] == -1:
    print(-1)
else :
    print(w - (dist[-1][-1] + 1))