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

Solution (Python):
import sys

from itertools import chain

H, W = map(int, input().split())
grid = [input() for _ in range(H)]
initial = sum(row.count("
dire = [(1,0),(0,1),(-1,0),(0,-1)]

def out(y, x):
    return y < 0 or y >= H or x < 0 or x >= W

def wall(y, x):
    return grid[y][x] == "

def succs(explored):
    def succs_(point):
        y = point[0]
        x = point[1]
        return [(y+h, x+w) for h, w in dire if not (out(y+h, x+w) or wall(y+h, x+w) or (y+h, x+w) in explored)]
    return succs_

def bfs(frontier, explored, count):
    if not frontier:
        return -1

    if any(map(lambda point: point == (H-1, W-1), frontier)):
        return count
    
    frontier_ = set(chain(*map(succs(explored), frontier)))
    return bfs(frontier_, explored | frontier_, count+1)
    
def main():
    path_count = bfs([(0, 0)], set([(0, 0)]), 1)
    if path_count == -1:
        print(-1)
    else:
        print(H*W - path_count - initial)

main()

Solution (Python):
import sys

from collections import deque

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

initial = 0
grid = []
for _ in range(H):
    row = input()
    initial += row.count("
    grid.append(row)

def bfs():
    dire = [(1,0),(0,1),(-1,0),(0,-1)]
    q = deque()
    q.append((0, 0, 1))
    explored = set()
    explored.add((0, 0))
    while q:
        y, x, count = q.popleft()
        for h, w in dire:
            yh = y + h
            xw = x + w
            if yh < 0 or yh >= H or xw < 0 or xw >= W or grid[yh][xw] == "
                continue
            
            if (yh, xw) == (H-1, W-1):
                return count+1

            explored.add((yh, xw))
            q.append((yh, xw, count+1))

    return -1

path_count = bfs()

if path_count == -1:
    print(-1)
else:
    print(H*W - path_count - initial)

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

    sy = 0
    sx = 0
    blk_cnt = 0

    for i in range(H):
        for j in range(W):
            if field[i][j] == '
                blk_cnt += 1

    
    shortest_step = bfs(H,W,field,sy,sx,H-1,W-1)
    if shortest_step == -1:
        print(-1)
    else: 
        print(H*W - blk_cnt - shortest_step)

def bfs(H,W,field,sy,sx,ty,tx):
    n_step = [[-1]*W for i in range(H)]
    n_step[sy][sx] = 1
    deq = deque()
    deq.appendleft((sy,sx))
    
    d_x_y = ((1,0),(-1,0),(0,1),(0,-1))
    while len(deq) > 0:
        cy, cx = deq.pop()
        if cy == ty and cx == tx:
            return n_step[cy][cx]

        for dy, dx in d_x_y:
            ny = cy + dy
            nx = cx + dx
            if 0 <= ny < H and 0 <= nx < W and field[ny][nx] != '
                n_step[ny][nx] = n_step[cy][cx] + 1
                deq.appendleft((ny,nx)) 
    
    return -1

if __name__ == '__main__':
    solve()

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




'''
A=[]
B=[]
for i in range():
    a, b = map(int, input().split())
    A.append(a)
    B.append(b)'''

h,w = map(int, input().split())
s = []
cnt=0
for i in range(h):
    t = list(input().strip())
    cnt+=t.count('.')
    s.append(t)

def sol(h,w,s,start):
    import queue
    
    dx=[1,0,-1,0]
    dy=[0,1,0,-1]
    px=start[0]
    py=start[1]
    
    sco = [[-1 for _ in range(w)] for x in range(h)]
    sco[py][px]=0
    a=queue.Queue()
    a.put([px, py])
    
    while not a.empty():
        px, py = a.get()
        if px==w-1 and py==h-1:
            
            
            return cnt-sco[h-1][w-1]-1
        for i in range(4):
            nx=px+dx[i]
            ny=py+dy[i]
            
            if 0<=nx<w and 0<=ny<h and s[ny][nx]!="
                sco[ny][nx]=sco[py][px]+1
                a.put([nx,ny])
    return -1

print(sol(h,w,s,[0,0]))

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

from collections import deque
e = [i for row in s for i in row]
chk =[]
def f():
  d = [[float('inf')]*w for i in range(h)]
  d[0][0]=1
  n = [0,0,1,-1]
  m = [1,-1,0,0]
  que = deque([])
  que.append((0,0))
  while que:
    p = que.popleft()
    if p[0]==h-1 and p[1]==w-1:
      break
    for i in range(4):
      nh = p[0]+n[i]
      nw = p[1]+m[i]
      if 0<=nh<h and 0<=nw<w and d[nh][nw]==float('inf') and s[nh][nw]!='
        d[nh][nw] = d[p[0]][p[1]]+1
        
        que.append((nh,nw))
  return  d[h-1][w-1]

res = f()

if res != float("inf"):
  print(h*w-res-e.count('
else:
  print('-1')

Solution (Python):
from collections import deque

def bfs():
    d = [[float("INF")] * w for i in range(h)]
    d[0][0] = 0
    dx = [-1, 0, 1, 0]
    dy = [0, -1, 0, 1]
    que = deque([])
    que.append((0, 0))
    
    while que:
        p = que.popleft()
        if p[0] == h - 1 and p[1] == w - 1:
            break
        for i in range(4):
            nx = p[0] + dx[i]
            ny = p[1] + dy[i]
            if 0 <= nx < h and 0 <= ny < w and maze[nx][ny] != "
                que.append((nx, ny))
                d[nx][ny] = d[p[0]][p[1]] + 1
    
    return d[h - 1][w - 1]
    
h, w = map(int, input().split())
maze = [list(input()) for i in range(h)]
cnt = 0
for i in range(h):
    for j in range(w):
        if maze[i][j] == "
            cnt += 1
if bfs() == float("INF"):
    print("-1")
else:
    print(h * w - cnt - bfs() - 1)

Solution (Python):
from collections import deque
white, black = '.', '
H, W = map(int, input().split())
S = [[j for j in input()] for i in range(H)]
mvv, mvh = [0, 0, -1, 1], [-1, 1, 0, 0]
q = deque([(0, 0)])
S[0][0] = 0
while q:
  y, x = q.popleft()
  for i in range(4):
    if 0 <= y + mvv[i] <= H-1 and S[y + mvv[i]][x] == white:
      S[y + mvv[i]][x] = S[y][x] + 1
      q.append((y + mvv[i], x))
    if 0 <= x + mvh[i] <= W-1 and S[y][x + mvh[i]] == white:
      S[y][x + mvh[i]] = S[y][x] + 1
      q.append((y, x + mvh[i]))
if S[H-1][W-1] == white:
  print(-1)
else:
  r = 0
  c = set()
  for y in range(H):
    for x in range(W):
      if S[y][x] == black:
        continue
      if S[y][x] == white or S[y][x] in c or S[y][x] > S[H-1][W-1]:
        r += 1
      else:
        c.add(S[y][x])
  print(r)

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


h, w = map(int, input().split())
maze = [[-1 for i in range(w)] for j in range(h)]

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

INF = h*w
visited = [[0 for i in range(w)] for j in range(h)]
distance = [[INF for i in range(w)] for j in range(h)]

if maze[0][0]=='
    print(-1)
    exit()

sx=0
sy=0
queue = deque()
queue.append((sy,sx))
distance[sy][sx] = 0

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

if distance[h-1][w-1] <INF:
    ans = h*w-count_wall- (distance[h-1][w-1]+1)
else:
    ans = -1
print(ans)

Solution (Python):
import sys
import math
import string
import fractions
import random
from operator import itemgetter
import itertools
from collections import deque
import copy
import heapq
import bisect

MOD = 10 ** 9 + 7
INF = float('inf')
input = lambda: sys.stdin.readline().strip()

sys.setrecursionlimit(10 ** 8)


def judge(y, x, dis):
    if info[y][x] == ".":
        info[y][x] = "
        stack.append([y, x, dis + 1])


H, W = map(int, input().split())
info = [["
for _ in range(H):
    info.append(["
info.append(["
white = 0
for i in range(H + 2):
    for j in range(W + 2):
        if info[i][j] == ".":
            white += 1

stack = deque([[1, 1, 0]])
while len(stack) > 0:
    y, x, dis = stack.popleft()
    if y == H and x == W:
        ans = dis
        break
    judge(y + 1, x, dis)
    judge(y, x + 1, dis)
    judge(y - 1, x, dis)
    judge(y, x - 1, dis)
    if len(stack) == 0:
        print(-1)
        sys.exit()
print(white - dis - 1)

Solution (Python):
H, W = map(int, input().split())
maze = ['
for _ in range(H):
  maze.append('
maze.append('

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

que = [(1,1)]
while que:
  i,j = que.pop(0)
  if (i,j) == (H,W):
    break
  for k,l in ((i-1,j), (i+1,j), (i,j-1), (i,j+1)):
    
    if maze[k][l] == '.' and cost[k][l] == -1:
      cost[k][l] = cost[i][j] + 1
      que.append((k,l))

if cost[H][W] == -1:
  print(-1)
else:
  n = -2 
  for i in range(1,H+1):
    for j in range(1,W+1):
      if maze[i][j] == '.':
        n += 1
  print(n - cost[H][W] + 1)

Solution (Python):
'''
https://atcoder.jp/contests/abc088/tasks/abc088_d
'''
def main():
    import sys
    
    sys.setrecursionlimit(10000000)
    from collections import Counter, deque
    
    from itertools import combinations, permutations
    
    from bisect import bisect_left,bisect_right
    from math import floor, ceil
    

    

    h,w = map(int, input().split())
    a = [list(input().rstrip()) for _ in range(h)]
    kuro = 0
    for i in a:
        kuro += i.count('
    d = deque([[0,0]])
    dxy = [[0,1],[0,-1],[1,0],[-1,0]]
    a[0][0] = 1
    while d:
        x,y = d.popleft()
        for dx, dy in dxy:
            nx = x + dx
            ny = y + dy
            if 0<=nx<=h-1 and 0<=ny<=w-1:
                if a[nx][ny] == '.':
                    a[nx][ny] = a[x][y] + 1
                    d.append([nx, ny])
    if a[h-1][w-1] == '.':
        print(-1)
    else:
        print(h*w - a[h-1][w-1]-kuro)

if __name__ == '__main__':
    main()

Solution (Python):
'''
https://atcoder.jp/contests/abc088/tasks/abc088_d
'''
def main():
    import sys
    
    sys.setrecursionlimit(10000000)
    from collections import Counter, deque
    
    from itertools import combinations, permutations
    
    from bisect import bisect_left,bisect_right
    from math import floor, ceil
    

    

    h,w = map(int, input().split())
    a = [list(input().rstrip()) for _ in range(h)]
    kuro = 0
    for i in a:
        kuro += i.count('
    d = deque([[0,0]])
    dxy = [[0,1],[0,-1],[1,0],[-1,0]]
    a[0][0] = 1
    while d:
        x,y = d.popleft()
        for dx, dy in dxy:
            nx = x + dx
            ny = y + dy
            if 0<=nx<=h-1 and 0<=ny<=w-1:
                if a[nx][ny] == '.':
                    a[nx][ny] = a[x][y] + 1
                    d.append([nx, ny])
    if a[h-1][w-1] == '.':
        print(-1)
    else:
        print(h*w - a[h-1][w-1]-kuro)

if __name__ == '__main__':
    main()

Solution (Python):
"""
参考にさせていただきました.ありがとうございました.(https://atcoder.jp/contests/abc088/submissions/10819295)
"""

from collections import deque

def dfs(H,W,s):
    que = deque()
    que.append([0,0])
    distance = [[-1 for i in range(W)] for j in range(H)]
    dxdy = [[1,0],[0,1],[-1,0],[0,-1]]

    distance[0][0] = 1

    flag = False 

    while que:

        x,y = que.popleft()

        if x == H-1 and y == W-1:
            flag = True
            break

        for i,j in dxdy:
            dx = x + i
            dy = y + j
            if dx >= 0 and dx < H and dy >= 0 and dy < W and distance[dx][dy] == -1 and s[dx][dy] == ".":
                distance[dx][dy] = distance[x][y] + 1 
                que.append([dx,dy])

    if not flag:
        return -1
    else:
        ans = 0
        for i in range(H):
            ans += s[i].count("
        
        
        return H*W - ans - distance[-1][-1]

def main():
    H,W = map(int,input().split())
    s = []
    for i in range(H):
        s.append(input())
    print(dfs(H,W,s))

if __name__ == "__main__":
    main()

Solution (Python):
import queue
import numpy as np

num = list(map(int,input().split()))
field = [list(input()) for i in range(num[0])]
seen = np.zeros((num[0],num[1]))

step_r = [1,0,-1,0]
step_c = [0,1,0,-1]
q_r = queue.Queue()
q_c = queue.Queue()
sign = 0
white = 0
q_r.put(0)
q_c.put(0)

for i in range(num[0]):
  for j in range(num[1]):
    if field[i][j] == ".":
      white = white + 1

while not q_r.empty():
  r = q_r.get()
  c = q_c.get()
  for i in range(4):
    next_r = r + step_r[i]
    next_c = c + step_c[i]
    
    if (next_r<0) or (num[0]<=next_r) or (next_c<0) or (num[1]<=next_c) or (field[next_r][next_c] == "
      continue
      
    if seen[next_r][next_c] == 0:
      q_r.put(next_r)
      q_c.put(next_c)
      seen[next_r][next_c] = seen[r][c] + 1
      if (next_r == num[0]-1) and (next_c == num[1]-1):
        g_r = next_r
        g_c = next_c
        sign = 1
        break
 
  if sign == 1:
    break

if sign == 1:
  ans = white - (seen[g_r][g_c] + 1)
elif sign == 0:
  ans = -1

print(int(ans))

Solution (Python):
from collections import deque
import sys
h,w = map(lambda x: int(x),input().split())
map = []
white_count = 0
map_count = [[float('inf') for i in range(w)] for j in range(h) ]
seen = [[False for i in range(w)] for j in range(h) ]
for _ in range(h) :
    a = list(input())
    white_count += a.count('.')
    map.append(a)

map_count[0][0] = 1

q = deque()
q.append([0,0,0,0])
while q :
    v = q.popleft()
    x = v[0]
    y = v[1]
    pre_x = v[2]
    pre_y = v[3]


    if x < 0 or x >= h or y < 0 or y >= w :
        continue
    if seen[x][y] :
        continue
    if map[x][y] == '
        continue
    if map_count[x][y] > map_count[pre_x][pre_y] + 1 :
        map_count[x][y] = map_count[pre_x][pre_y] + 1

    if x == h-1 and y == w-1 :
        print(white_count - map_count[x][y])
        sys.exit()

    pre_x = x
    pre_y = y
    seen[x][y] = True
    q.append([x+1,y,pre_x,pre_y])
    q.append([x-1,y,pre_x,pre_y])
    q.append([x,y+1,pre_x,pre_y])
    q.append([x,y-1,pre_x,pre_y])




print(-1)

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

visited = [[False]*(W+2) for _ in range(H+2)]
import queue
q = queue.Queue()
q.put((1,1,1))
visited[1][1]=True
dh = [1,0,-1,0]
dw = [0,1,0,-1]
ans = -1
while not q.empty():
  h,w,c = q.get()
  for i in range(4):
    y,x = h+dh[i],w+dw[i]
    
    if y == H and x == W:
      c += 1
      ans = path_c-c
      break
    if S[y][x]=='.' and visited[y][x]==False:
      
      q.put((y,x,c+1))
      visited[y][x]=True
  else:
      continue
  break
print(ans)

Solution (Python):

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


dists = [[float('inf') for _ in range(W)] for _ in range(H)]
dists[0][0] = 0
nexts = [(1,0), (-1,0), (0,1), (0,-1)]

buf = [(0, 0)]
while buf:
    h, w = buf.pop(0)

    for dh, dw in nexts:
        next_h, next_w = h+dh, w+dw
        if 0 <= next_h < H and 0 <= next_w < W:
            if table[next_h][next_w] == '.':
                if dists[next_h][next_w] == float('inf'):
                    dists[next_h][next_w] = dists[h][w] + 1
                    buf.append((next_h, next_w))

num_white = 0
for row in table:
    for r in row:
        if r == '.':
            num_white += 1


if dists[H-1][W-1] == float('inf'):
        print(-1)

else:
    print(num_white - dists[H-1][W-1] - 1)

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

from collections import deque

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

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

direction = [(1, 0), (0, 1), (-1, 0), (0, -1)]
d[0][0] = 1

flag = False
while que:
    x, y = que.popleft()

    if x == h-1 and y == w-1:
        flag = True
        break

    for i, j in direction:
        dx, dy = x + i, y + j
        if 0<=dx<h and 0<=dy<w and d[dx][dy] == 0 and maze[dx][dy] != '
            d[dx][dy] = d[x][y] + 1
            que.append((dx, dy))

if flag == False:
    print(-1)
    exit()

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

res += d[-1][-1]


print(h*w - res)

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

M = [str(input()) for _ in range(h)]

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

M = ['
M = ['

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

while q:
    y, x = q.popleft()
    for dy, dx in (-1, 0), (1, 0), (0, -1), (0, 1):
        ny, nx = y+dy, x+dx
        if visit[ny][nx] == -1 and M[ny][nx] != '
            visit[ny][nx] = visit[y][x]+1
            q.append((ny, nx))

if visit[h][w] == -1:
    print(-1)
else:
    ans = ans -visit[h][w]-1
    print(ans)

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

M = [str(input()) for _ in range(h)]

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

M = ['
M = ['

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

while q:
    y, x = q.popleft()
    for dy, dx in (-1, 0), (1, 0), (0, -1), (0, 1):
        ny, nx = y+dy, x+dx
        if visit[ny][nx] == -1 and M[ny][nx] != '
            visit[ny][nx] = visit[y][x]+1
            q.append((ny, nx))

if visit[h][w] == -1:
    print(-1)
else:
    ans = ans -visit[h][w]-1
    print(ans)

Solution (Python):
import collections
H, W = map(int, input().split())
l = [input() for _ in range(H)]
check = [([0] * (W)) for _ in range(H)]
white = 0
for i in range(H):
    white += l[i].count(".")
q = collections.deque()
check[0][0] = 1
q.append([0, 0])
g = False
while q:
    h, w = q.popleft()
    for i, j in ([0, 1], [0, -1], [1, 0], [-1, 0]):
        new_h = h + i
        new_w = w + j
        if new_w < 0 or new_h < 0 or new_w > W-1 or new_h > H-1 or l[new_h][new_w] == "
            continue
        elif check[new_h][new_w] == 0:
            check[new_h][new_w] = check[h][w] + 1
            q.append([new_h, new_w])
print(white - check[H-1][W-1] if check[H-1][W-1] != 0 else -1)

Solution (Python):

from collections import defaultdict,deque
from heapq import heappush, heappop
from itertools import permutations
import sys
import math
import bisect
def LI(): return [int(x) for x in sys.stdin.readline().split()]
def I(): return int(sys.stdin.readline())
def LS():return [list(x) for x in sys.stdin.readline().split()]
def S():
    res = list(sys.stdin.readline())
    if res[-1] == "\n":
        return res[:-1]
    return res
def IR(n):
    return [I() for i in range(n)]
def LIR(n):
    return [LI() for i in range(n)]
def SR(n):
    return [S() for i in range(n)]
def LSR(n):
    return [LS() for i in range(n)]

sys.setrecursionlimit(1000000)
mod = 1000000007

d = [(1,0),(-1,0),(0,1),(0,-1)]
def solve():
    h,w = LI()
    s = [input() for i in range(h)]
    bfs = [[0]*w for i in range(h)]
    bfs[0][0] = 1
    q = deque([(0,0)])
    gy,gx = h-1,w-1
    while q:
        y,x = q.popleft()
        if (y,x) == (gy,gx):
            break
        nb = bfs[y][x] + 1
        for dy,dx in d:
            ny,nx = y+dy,x+dx
            if 0 <= ny < h and 0 <= nx < w:
                if s[ny][nx] == "
                    continue
                if not bfs[ny][nx]:
                    bfs[ny][nx] = nb
                    q.append((ny,nx))
    ans = bfs[gy][gx]
    if not ans:
        print(-1)
        return
    c = sum([i.count("
    print(h*w-c-ans)
    return


if __name__ == "__main__":
    solve()

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

dist = [[-1]*w for _ in range(h)]
dist[0][0]=0
que = [(0,0)]
move = [(0,1),(0,-1),(1,0),(-1,0)]

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

while que!=[]:
    (x , y) = que.pop(0)
    
    for m in move:
        nx = x + m[0]
        ny = y + m[1]
        if (0<=nx<h and 0<=ny<w):
            if dist[nx][ny] != -1: continue
            
            if s[nx][ny] == ".":
                dist[nx][ny] = dist[x][y]+1
                que.append((nx,ny))
distance = dist[-1][-1]
if distance == -1:
    print(-1)
else:
    print(n_white - distance - 1)

Solution (Python):
from collections import deque

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

dx = [0,1,0,-1]
dy = [1,0,-1,0]
seen = [[0]*W for i in range(H)]
que = deque([[0,0]])
seen[0][0] = 1
while True:
    if len(que) == 0: break 
    h,w = que.popleft()
    if h == H-1 and w == W-1: break 
    for i in range(0,4):
        if (h+dy[i]<0 or h+dy[i]>=H or w+dx[i]<0 or w+dx[i]>=W): continue
        if S[h+dy[i]][w+dx[i]] == "." and seen[h+dy[i]][w+dx[i]] == 0:
            seen[h+dy[i]][w+dx[i]] = seen[h][w]+1
            que.append([h+dy[i],w+dx[i]])

cnt = 0
for a in range(H):
    for b in range(W):
        if S[a][b] == ".": cnt += 1

if seen[H-1][W-1] == 0:
    print(-1)
else:
    print(cnt-seen[H-1][W-1])

Solution (Python):
from collections import deque

def main():
    h, w = map(int, input().split())
    M = [list(input()) for _ in range(h)]
    D = [[10**10] * w for _ in range(h)]
    D[0][0] = 0

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

    que = deque([])
    que.append((0, 0))
    while que:
        p = que.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 M[ny][nx] != "
                D[ny][nx] = D[p[0]][p[1]] + 1
                que.append((ny, nx))

    if D[h-1][w-1] == 10**10:
        print(-1)
        exit()

    n_white = 0
    for r in M:
        n_white += len([s for s in r if s == "."])
    print(n_white - D[h-1][w-1] - 1)


if __name__ == '__main__':
    main()

Solution (Python):
from collections import deque

h, w = map(int, input().split())
black = 0
data = []
for _ in range(h):
    s = input()
    for i in range(w):
        if s[i] == "
            black += 1
    data.append(s)

dist = [[-1]*w for _ in range(h)]
queue = deque()
queue.append((0, 0))
dist[0][0] = 0

while queue:
    x, y = queue.popleft()
    for dx, dy in [(-1, 0), (1, 0), (0, 1), (0, -1)]:
        tox, toy = x + dx, y + dy
        if 0 <= tox < h and 0 <= toy < w and dist[tox][toy] == -1 and data[tox][toy] == '.':
            dist[tox][toy] = dist[x][y] + 1
            queue.append((tox, toy))

print(h * w - black - dist[-1][-1] - 1 if dist[-1][-1] != -1 else -1)

Solution (Python):
from collections import deque


def bfs():
    INF = float('inf')
    check = [[INF] * W for _ in range(H)]
    dx = [1, 0, -1, 0]
    dy = [0, 1, 0, -1]
    que = deque([])
    que.append((sy, sx))
    check[sy][sx] = 1
    while que:
        y, x = que.popleft()
        if y == gy and x == gx:
            break
        for i in range(4):
            ny = y + dy[i]
            nx = x + dx[i]
            if 0 <= ny < H and 0 <= nx < W and maze[ny][nx] != '
                que.append((ny, nx))
                check[ny][nx] = check[y][x] + 1
    return check[gy][gx]


H, W = map(int, input().split())
maze = [list(input()) for _ in range(H)]
black = 0
for i in range(H):
    for j in range(W):
        if maze[i][j] == '
            black += 1

sy = 0
sx = 0
gy = H - 1
gx = W - 1
ret = bfs()
if ret == float('inf'):
    print(-1)
else:
    ans = H * W - black - ret
    print(ans)

Solution (Python):
from collections import deque
def BFS_grid(grid,visited,start,goal):
    y,x = start
    visited[y][x] = 1
    q = deque([start])
    delta = [[-1,0],[0,-1],[1,0],[0,1]]
    h = len(grid)
    w = len(grid[0])
    flag = False
    while q:
        y,x = q.popleft()
        for dy,dx in delta:
            if (0<= x+dx < w) and (0<= y+dy<h) :
                if visited[y+dy][x+dx] == 0 and grid[y+dy][x+dx]==".":
                    visited[y+dy][x+dx] = visited[y][x] +1
                    q.append([y+dy,x+dx])
                    if [y+dy,x+dx] == goal:
                        flag = True
    return flag


h,w = map(int,input().split())
mz = []
white = 0

for i in range(h):
    mz.append(list(input()))
    white += mz[-1].count(".")

visited = [[0]*w for i in range(h)]
if BFS_grid(mz,visited,[0,0],[h-1,w-1]):
    print(white - (visited[h-1][w-1]-visited[0][0]+1))
else:
    print(-1)

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

ll=[[-1 for i in range(w)] for j in range(h)]
ld=deque()

ld.append([0,0])
ll[0][0]=0
while len(ld)!=0:
    k=ld.popleft()
    y=k[0]
    x=k[1]
    p=ll[y][x]
    if 0<=y+1<h and 0<=x<w and ll[y+1][x]==-1 and l[y+1][x]!="
        ld.append([y+1,x])
        ll[y+1][x]=p+1
    if 0<=y-1<h and 0<=x<w and ll[y-1][x]==-1 and l[y-1][x]!="
        ld.append([y-1,x])
        ll[y-1][x]=p+1
    if 0<=y<h and 0<=x+1<w and ll[y][x+1]==-1 and l[y][x+1]!="
        ld.append([y,x+1])
        ll[y][x+1]=p+1
    if 0<=y<h and 0<=x-1<w and ll[y][x-1]==-1 and l[y][x-1]!="
        ld.append([y,x-1])
        ll[y][x-1]=p+1
        
s=0
if ll[h-1][w-1]==-1:
    print(-1)
else:
    for i in range(h):
        s+=l[i].count("
    print(h*w-s-ll[h-1][w-1]-1)

Solution (Python):
import collections


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

grid = []
flat_grid = []
for i in range(H):
  S = input()
  tasu = [S[i] for i in range(W) ]
  grid.append(tasu )
  flat_grid = flat_grid + tasu


sx,sy = 0,0
gx,gy = W-1,H-1


l_seen = [[False for i in range(W)] for j in range(H) ]
l_todo = []
dist = [[0 for i in range(W)] for j in range(H) ]


l_seen[sy][sx] = True 


for i in [[sx+1,sy],[sx,sy+1],[sx-1,sy],[sx,sy-1] ]:
  
  if (i[0]<0 or i[1] <0 or i[1]>=H or i[0] >= W ):
    continue
  
  if grid[i[1]][i[0]] == "
    continue  
  dist[i[1]][i[0]] = 1 
  
  l_seen[i[1]][i[0]] = True 
  
  l_todo = l_todo + [i]



while len(l_todo) != 0:

  
  v = l_todo.pop(0) 

  for i in [ [v[0]+1,v[1]] , [v[0],v[1]+1] , [v[0]-1,v[1]] ,[v[0],v[1]-1] ]:
    
    if (i[0]<0 or i[1] <0 or i[1]>=H or i[0] >= W ):
      continue
    
    if grid[i[1]][i[0]] == "
      continue
    
    if l_seen[i[1]][i[0]] == True:
      continue  

    if l_seen[i[1]][i[0]] == False:
      l_seen[i[1]][i[0]] = True
      l_todo = l_todo + [i]
      dist[i[1]][i[0]]=dist[v[1]][v[0]]+1

d = dist[gy][gx]
w_num = collections.Counter(flat_grid)["."]
if d == False:
  print(-1)
else:
  print(w_num -(d+1))

Solution (Python):
H, W = map(int, input().split())
Map = [input() for _ in range(H)]
black_no1 = 0
A = [[0 for __ in range(W)] for _ in range(H)]
for i in range(H):
  for j in range(W):
    if Map[i][j] == '
      black_no1 += 1
      A[i][j] = 1
pos = [[0, 0]]
dfs = 1
clr = -1
while pos != []:
  dfs += 1
  n = len(pos)
  for i in range(n):
    p = pos[0]
    if p[0] > 0:
      if A[p[0]-1][p[1]] == 0:
        A[p[0]-1][p[1]] = 1
        pos.append([p[0]-1, p[1]])
      if p[0] - 1 == H - 1 and p[1] == W - 1:
        clr = 0
    if p[0] < H - 1:
      if A[p[0]+1][p[1]] == 0:
        A[p[0]+1][p[1]] = 1
        pos.append([p[0]+1, p[1]])
      if p[0] + 1 == H - 1 and p[1] == W - 1:
        clr = 0
    if p[1] > 0:
      if A[p[0]][p[1]-1] == 0:
        A[p[0]][p[1]-1] = 1
        pos.append([p[0], p[1]-1])
      if p[0] == H - 1 and p[1] - 1 == W - 1:
        clr = 0
    if p[1] < W - 1:
      if A[p[0]][p[1]+1] == 0:
        A[p[0]][p[1]+1] = 1
        pos.append([p[0], p[1]+1])
      if p[0] == H - 1 and p[1] + 1 == W - 1:
        clr = 0
    pos = pos[1:]
    if clr == 0:
      break
  if clr == 0:
    break
if clr == 0:
  print(H*W-dfs-black_no1)
else:
  print(clr)

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

dx = [0, 0, 1, -1]
dy = [1, -1, 0, 0]
INF = float("inf")
ss = [[INF] * w for i in range(h)]
def bfs():
    q = queue.Queue()
    ss[0][0] = 1
    q.put([0, 0])
    while not q.empty():
        now = q.get()
        nowx = now[0]
        nowy = now[1]
        for i in range(4):
            nextx = dx[i] + nowx
            nexty = dy[i] + nowy
            if nextx >= 0 and nexty >= 0 and nextx < h and nexty < w:
                if s[nextx][nexty] == "." and ss[nextx][nexty] == INF:
                    ss[nextx][nexty] = ss[nowx][nowy] + 1
                    q.put([nextx, nexty])

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

if ss[h - 1][w - 1] == INF:
    print("-1")
else:  
    print(cnt - ss[h - 1][w - 1])

Solution (Python):
from collections import deque
INF = int(1e9) + 7
h, w = map(int, input().split())
maze = []
for i in range(h):
    maze.append(list(input()))
if maze[0][0] == '
    print(-1)
    exit()


d = [[INF] * w for i in range(h)]
def bfs():
    
    dx = [1, 0, -1, 0]
    dy = [0, 1, 0, -1]
    que = deque([(0, 0)])
    d[0][0] = 0

    while len(que) != 0:
        val = que.popleft()
        if val[0] == h-1 and val[1] == w-1:
            break
        for i in range(4):
            nx = val[0] + dx[i]
            ny = val[1] + dy[i]
            if (0 <= nx < h and 0 <= ny < w and maze[nx][ny] != '
                que.append((nx, ny))
                d[nx][ny] = d[val[0]][val[1]] + 1
    return d[h-1][w-1]
ans = bfs()
if ans == INF:
    print(-1)
else:
    cnt = 0
    for i in range(h):
        for j in range(w):
            if maze[i][j] == '.':
                cnt += 1
    print(cnt - (ans+1))