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):
H,W = map(int,input().split())
s = []
black = 0
for i in range(H):
    l = list(input())
    for j in range(W):
        if l[j] == "
            black += 1
    s.append(l)
white = H*W-black
from collections import deque
q = deque([(0,0,0)])
s[0][0] = "
while q:
    x,y,cnt = q.popleft()
    for dx,dy in [(0,1),(0,-1),(1,0),(-1,0)]:
        nx,ny = x+dx,y+dy
        if 0<=nx<H and 0<=ny<W and s[nx][ny] != "
            if nx == H-1 and ny == W-1:
                print(white-cnt-2)
                exit(0)
            s[nx][ny] = "
            q.append((nx,ny,cnt+1))
print(-1)

Solution (Python):
from collections import deque

def bfs():
    
    d = [[float("inf")] * C for _ in range(R)]

    dx = [1, 0, -1, 0]
    dy = [0, 1, 0, -1]
    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):
            nx = p[1] + dx[i]
            ny = p[0] + dy[i]

            if 0<=nx<C and 0<=ny<R and maze[ny][nx] != "
                
                que.append((ny, nx))
                d[ny][nx] = d[p[0]][p[1]] + 1

    return d[gy][gx]

R, C = map(int,input().split())
sy, sx = 0, 0
gy, gx = R-1, C-1

maze = [list(input()) for _ in range(R)]

cnt = 0
for m in maze:
    cnt += m.count(".")

if cnt-bfs()-1 >= 0:
    print(cnt-bfs()-1)
else:
    print(-1)

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

INF = 1<<30
dist = [[INF]*W for _ in range(H)]
dist[0][0] = 0

import queue

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

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

keiro = [[[] for _ in range(W)] for _ in range(H)]

while not (q.empty()):
    cur = q.get()
    y,x = cur[0],cur[1]
    
    for i in range(4):
        nx = x+dx[i]
        ny = y+dy[i]
        d = dist[y][x] + 1
        if nx<0 or nx>=W or ny<0 or ny>=H:
            continue
        elif S[ny][nx] == '
            continue
        
        elif dist[ny][nx]>d:
            q.put([ny,nx])
            dist[ny][nx] = d
            keiro[ny][nx] = [y,x]


if dist[H-1][W-1]==INF:
    print(-1)
else:
    white = 0
    for s in S:
        for t in s:
            if t=='.':
                white += 1
    
    ans = white - dist[H-1][W-1] - 1
    print(ans)

Solution (Python):
from collections import deque

def bfs():
    flag = False
    d = [[float('inf')] * W for i in range(H)]
    dx = [1, 0, -1, 0]
    dy = [0, 1, 0, -1]

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

    while que:
        p = que.popleft()
        if p[0]==H-1 and p[1]==W-1:
            flag = True
            break

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

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

    if flag==False:
        return False

    return d[H-1][W-1]

def notcount(H, W, maze):
    cnt = 0

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

    return cnt

H, W = map(int, input().split())
maze = [list(input()) for i in range(H)]
if bfs()==False:
    print(-1)
else:
    s = (H * W - notcount(H, W, maze)) - (bfs() + 1)
    
    print(s)

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

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

q = [(0,0)]

while q:
    h1,w1 = q.pop(-1)
    if h1 > 0:
        if s[h1-1][w1] == '.':
            if dis[h1][w1] + 1 < dis[h1-1][w1]:
                dis[h1-1][w1] = dis[h1][w1] + 1
                q.append((h1-1,w1))
    if w1 > 0:
        if s[h1][w1-1] == '.':
            if dis[h1][w1] + 1 < dis[h1][w1-1]:
                dis[h1][w1-1] = dis[h1][w1] + 1
                q.append((h1,w1-1))
    if h1 < h - 1:
        if s[h1+1][w1] == '.':
            if dis[h1][w1] + 1 < dis[h1+1][w1]:
                dis[h1+1][w1] = dis[h1][w1] + 1
                q.append((h1+1,w1))
    if w1 < w - 1:
        if s[h1][w1+1] == '.':
            if dis[h1][w1] + 1 < dis[h1][w1+1]:
                dis[h1][w1+1] = dis[h1][w1] + 1
                q.append((h1,w1+1))

if dis[-1][-1] == 10 ** 10:
    print(-1)
    exit()

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

print(count - dis[-1][-1] - 1)

Solution (Python):
H,W=map(int,input().split())
A=[list(input()) for i in range(H)]
from collections import deque
INF=10**6
m=[[10**6]*W for _ in range(H)]
dx=[1,-1,0,0]
dy=[0,0,1,-1]

def bfs(y,x):
  q=deque()
  q.append((y,x))  
  
  while len(q)>0:
    y,x=q.popleft()
    dx=[1,-1,0,0]
    dy=[0,0,1,-1]
    for i in range(4):
      nx=x+dx[i]
      ny=y+dy[i]
      if  0<=nx<W and 0<=ny<H and A[ny][nx]=="." and m[ny][nx]==INF:
        q.append((ny,nx))
        m[ny][nx]=m[y][x]+1

m[0][0]=0
bfs(0,0)
cnt=(m[-1][-1])
if cnt>2500:
  print(-1)
else:
  cntd=0
  for i in range(H):
    for j in range(W):
      if A[i][j]=='
        cntd+=1
  print(H*W-cnt-cntd-1)

Solution (Python):
import math,itertools,fractions,heapq,bisect,sys,queue,copy

sys.setrecursionlimit(10**7)
inf=10**20
mod=10**9+7
dd=[(-1,0),(0,1),(1,0),(0,-1)]
ddn=[(-1,0),(-1,1),(0,1),(1,1),(1,0),(1,-1),(0,-1),(-1,-1)]

def LI(): return [int(x) for x in sys.stdin.readline().split()]
def I(): return int(sys.stdin.readline())
def LS(): return sys.stdin.readline().split()
def S(): return input()

def main():
  h,w=LI()
  q=[]

  field=[S() for _ in range(h)]
  counter=[[inf]*w for _ in range(h)]

  sharp_cnt=0
  for x in field:
    sharp_cnt+=x.count('

  q.append((0,0,1))

  while len(q)>0:
    y,x,cnt=q.pop()
    if counter[y][x]<cnt:
      continue
    counter[y][x]=cnt

    for dy,dx in dd:
      ny=y+dy
      nx=x+dx

      if 0<=ny and 0<=nx and ny<h and nx<w:
        if field[ny][nx]!='

          if counter[ny][nx]>cnt+1:
            q.append((ny,nx,cnt+1))

  step_cnt=counter[h-1][w-1]

  if step_cnt==inf:
    return -1

  return h*w-sharp_cnt-step_cnt


print(main())

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



road_count = 0
lis = [list('
for _ in range(h):
    li = input()
    for i in li:
        if i == '.':
            road_count += 1
    li = '
    lis.append(list(li))
lis.append(list('


dp = [[0]*(w+2) for _ in range(h+2)]


step = [[1,1]]
while len(step)>0:
    x,y = step.pop(0)

    if x == h and y == w:
        print(road_count-dp[x][y]-1)
        exit()

    
    lis[x][y] = '


    if lis[x-1][y] != '
        step.append([x-1,y])
        dp[x-1][y] = dp[x][y]+1
    if lis[x+1][y] != '
        step.append([x+1,y])
        dp[x+1][y] = dp[x][y]+1
    if lis[x][y-1] != '
        step.append([x,y-1])
        dp[x][y-1] = dp[x][y]+1
    if lis[x][y+1] != '
        step.append([x,y+1])
        dp[x][y+1] = dp[x][y]+1
print(-1)

Solution (Python):
h,w = (int(x) for x in input().split())
ab = []
count = 0
for _ in range(h):
    a = input()
    a = a+'
    ab.append(list(a))
    for i in a:
        if i == '.':
            count += 1
ab.append(list('
dp = [[0 for i in range(w)] for j in range(h)]
 
step = [[0, 0]]
dp[0][0] = 1
 
while len(step) > 0:
    y, x = step.pop(0)
    if y == h-1 and x == w-1:
        print(count-dp[y][x])
        exit()
    if ab[y+1][x] == '.' and dp[y+1][x] == 0 :
        step.append([y+1, x])
        dp[y+1][x] = dp[y][x] + 1
    if ab[y][x+1] == '.' and dp[y][x+1] == 0 :
        step.append([y, x+1])
        dp[y][x+1] = dp[y][x] + 1
    if ab[y-1][x] == '.' and dp[y-1][x] == 0 :
        step.append([y-1, x])
        dp[y-1][x] = dp[y][x] + 1
    if ab[y][x-1] == '.' and dp[y][x-1] == 0 :
        step.append([y, x-1])
        dp[y][x-1] = dp[y][x] + 1
 
 
print(-1)

Solution (Python):
from collections import deque


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

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

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

    while que:
        p = que.popleft()
        if p[0] == gx and p[1] == gy:
            break
        for i in range(4):
            nx = p[0] + dx[i]
            ny = p[1] + dy[i]

            if 0 <= nx < h and 0 <= ny < w and maze[nx][ny] != "
                que.append((nx, ny))
                d[nx][ny] = d[p[0]][p[1]] + 1

    return d[gx][gy]


h, w = map(int, input().split())
maze = [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 maze[i][j] == ".":
            white += 1

res = bfs()
if 0 < res < float("inf"):
    
    
    print(white - res - 1)
else:
    print(-1)

Solution (Python):
h,w = (int(x) for x in input().split())
ab = []
count = 0
for _ in range(h):
    a = input()
    a = a+'
    ab.append(list(a))
    for i in a:
        if i == '.':
            count += 1
ab.append(list('
dp = [[0 for i in range(w)] for j in range(h)]
 
step = [[0, 0]]
dp[0][0] = 1

while len(step) > 0:
    y, x = step.pop(0)
    if y == h-1 and x == w-1:
        print(count-dp[y][x])
        exit()
    if ab[y+1][x] == '.' and dp[y+1][x] == 0 :
        step.append([y+1, x])
        dp[y+1][x] = dp[y][x] + 1
    if ab[y][x+1] == '.' and dp[y][x+1] == 0 :
        step.append([y, x+1])
        dp[y][x+1] = dp[y][x] + 1
    if ab[y-1][x] == '.' and dp[y-1][x] == 0 :
        step.append([y-1, x])
        dp[y-1][x] = dp[y][x] + 1
    if ab[y][x-1] == '.' and dp[y][x-1] == 0 :
        step.append([y, x-1])
        dp[y][x-1] = dp[y][x] + 1


print(-1)

Solution (Python):
H, W = map(int, input().split())
m = []
m.append('
white = 0
for i in range(H):
  s = input()
  m.append(list('
  white += s.count('.')
m.append('
 
op = set([(1, 1)])
dist = 0
while len(op) > 0:
  dist += 1
  next_op = set()
  for y, x in op:
    m[y][x] = dist
    if (y, x) == (H, W):
      print(white - dist)
      exit()
 
    for dx,dy in [0,1],[0,-1],[1,0],[-1,0]:
      if m[y-dy][x-dx] == '.':
        next_op.add((y-dy,x-dx))
  op = next_op
 
print('-1')

Solution (Python):
import sys
import queue

h, w = list(map(int, input().split()))
l = [input() for _ in range(h)]
checked = [[False for _ in range(w)] for __ in range(h)]

q = queue.Queue()
q.put((0, 0, 1))
while not q.empty():
    x, y, count = q.get()
    if checked[y][x]:
        continue
    checked[y][x] = True
    if x == w-1 and y == h-1:
        ans = 0
        for i in range(h):
            for j in range(w):
                if l[i][j] == ".":
                    ans += 1
        print(ans-count)
        sys.exit(0)
    if x > 0 and l[y][x-1] == "." and not checked[y][x-1]:
        q.put((x-1, y, count+1))
    if y > 0 and l[y-1][x] == "." and not checked[y-1][x]:
        q.put((x, y-1, count+1))
    if x < w-1 and l[y][x+1] == "." and not checked[y][x+1]:
        q.put((x+1, y, count+1))
    if y < h-1 and l[y+1][x] == "." and not checked[y+1][x]:
        q.put((x, y+1, count+1))
print(-1)

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

from collections import deque

def solve(x,y,gx,gy):
    dx = [1, 0, -1, 0]
    dy = [0, 1, 0, -1]

    start = [x, y]
    dist = [[10**3]*w for i in range(h)]
    dist[y][x] = 0
    Q = deque()
    Q.append(start)

    while Q:
        p = Q.popleft()
        for i in range(4):
            nx = p[0] + dx[i]
            ny = p[1] + dy[i]

            if 0 <= nx < w and 0 <= ny < h:
                if l[ny][nx]=="." and dist[ny][nx]==10**3:
                    Q.append([nx, ny])
                    dist[ny][nx] = dist[p[1]][p[0]] + 1
                    if nx==gx and ny==gy:
                        return dist[ny][nx]
    return -1

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

res=solve(0,0,w-1,h-1)

if res==-1:
    print(res)
else:
    print(cnt-solve(0,0,w-1,h-1)-1)

Solution (Python):
from collections import deque


def bfs(sx, sy, gx, gy):
    que = deque()
    que.append([sx, sy])
    d[sx][sy] = 0
    while que:
        p = que.popleft()
        if p[0] == gx and p[1] == gy:
            return d[gx][gy]
        for i in range(4):
            nx = p[0] + dx[i]
            ny = p[1] + dy[i]
            if (0 <= nx and nx < H and 0 <= ny and ny < W and s[nx][ny] != "
                que.append([nx, ny])
                d[nx][ny] = d[p[0]][p[1]] + 1
    return -1


H, W = map(int, input().split())
s = [list(input()) for _ in range(H)]
d = [[-1] * W for _ in range(H)]
b = 0

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

for i in range(H):
    for j in range(W):
        if s[i][j] == "
            b += 1
l = bfs(0, 0, H - 1, W - 1)
if l < 0:
    print(l)
else:
    print(H*W - b-l-1)

Solution (Python):
import math
import fractions
import bisect
import collections
import itertools
import heapq
import string
import sys
import copy
from collections import deque
sys.setrecursionlimit(10**7)
MOD = 10**9+7
def gcd(a,b):return fractions.gcd(a,b) 
def lcm(a,b):return (a*b) // fractions.gcd(a,b) 
def iin(): return int(input()) 
def ifn(): return float(input()) 
def isn(): return input().split() 
def imn(): return map(int, input().split()) 
def fmn(): return map(float, input().split()) 
def iln(): return list(map(int, input().split())) 
def iln_s(): return sorted(iln()) 
def iln_r(): return sorted(iln(), reverse=True) 
def fln(): return list(map(float, input().split())) 
def join(l, s=''): return s.join(l) 
def perm(l, n): return itertools.permutations(l, n) 
def perm_count(n, r): return math.factorial(n) // math.factorial(n-r) 
def comb(l, n): return itertools.combinations(l, n) 
def comb_count(n, r): return math.factorial(n) // (math.factorial(n-r) * math.factorial(r)) 
def two_distance(a, b, c, d): return ((c-a)**2 + (d-b)**2)**.5 
def m_add(a,b): return (a+b) % MOD

H,W = map(lambda x: int(x)-1, input().split())
s = [input() for _ in range(H+1)]

d = [[-1 for _ in range(W+1)] for _ in range(H+1)]
d[0][0] = 0

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

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

while len(queue) > 0:
    point = queue.popleft()

    if point[1] == H and point[0] == W: break 
    for i in range(4):
        x = point[0] + dx[i]
        y = point[1] + dy[i]

        if x < 0 or y < 0 or x > W or y > H or s[y][x] == '
        if d[y][x] != -1: continue
        d[y][x] = d[point[1]][point[0]] + 1
        queue.append((x,y))

if d[H][W] == -1:
    print(-1)
else:
    white_count = 0
    for i in range(H+1):
        for j in range(W+1):
            if s[i][j] == '.':
                white_count += 1
    print(white_count - (d[H][W]+1))

Solution (Python):
from collections import deque
import sys

h, w = map(int, input().split())
map_size = h * w
maze = [list(input()) for _ in range(h)]
goal = (h - 1, w - 1)


def shortest_path(start, goal):
    que = deque()
    que.append(start)
    visited = [[-1] * w for _ in range(h)]
    visited[start[0]][start[1]] = 0
    while que:
        now = que.popleft()
        for iy, ix in [(0, 1), (0, -1), (1, 0), (-1, 0)]:
            ny = now[0] + iy
            nx = now[1] + ix
            if (0 <= ny < h) and (0 <= nx < w):
                if ny == goal[0] and nx == goal[1]:
                    visited[ny][nx] = visited[now[0]][now[1]] + 1
                    return visited[ny][nx]
                
                
                if maze[ny][nx] != '
                    visited[ny][nx] = visited[now[0]][now[1]] + 1
                    que.append((ny, nx))
    return -1






















move_cnt = shortest_path((0, 0), goal)
if move_cnt == -1:
    print(-1)
    sys.exit()

cnt = 0
for y in range(h):
    for x in range(w):
        if maze[y][x] == '
            cnt += 1

print(map_size - cnt - move_cnt - 1)

Solution (Python):
import sys
sys.setrecursionlimit(10**9)
H,W = map(int,input().split())
move_x = [1,-1,0,0]
move_y = [0,0,1,-1]
Field = [[c for c in input()] for _ in range(H)]
seen = [[False for _ in range(W)] for _ in range(H)]
queue = []
black = 0
for i in range(H):
    for j in range(W):
        if Field[i][j] == '
            black += 1
dist = [[0 for _ in range(W)] for _ in range(H)]
res = -1 
def bfs(start_x,start_y,Field,seen,queue,dist):
    global res
    seen[start_x][start_y] = True
    for i in range(0,4):
        x = start_x + move_x[i]
        y = start_y + move_y[i]
        if x < 0 or y < 0 or x >= H or y >= W:
            continue 
        if Field[x][y] == '
            continue 
        if seen[x][y]:
            continue 
        if Field[x][y] in queue:
            continue 
        dist[x][y] = dist[start_x][start_y] + 1
        if x == (H-1) and y == (W-1):
            res = H*W - dist[x][y] - black 
        queue.append((x,y))
    for element in queue:
        x,y = element
        if seen[x][y]:
            continue
        seen[x][y] = True
        queue.remove(element)
        bfs(x,y,Field,seen,queue,dist)    
bfs(0,0,Field,seen,queue,dist)
if res != -1:
	print(res-1)
else:
  print(-1)

Solution (Python):
from sys import stdin
from collections import deque
inf = 10**10
h,w = [int(x) for x in stdin.readline().rstrip().split()]
li = [["" for i in range(w)]for j in range(h)]
point = 0
for i in range(h):
    s = stdin.readline().rstrip()
    point += s.count(".")
    for j in range(w):
        li[i][j] = s[j]
dx = [1,0,-1,0]
dy = [0,1,0,-1]
que = deque()
lin = [[inf for i in range(w)]for j in range(h)]
lin[0][0] = 0
que.append([0,0])
while que:
    k = que.popleft()
    x = k[0]
    y = k[1]
    for i,j in zip(dx,dy):
        nx = x + i
        ny = y + j
        if nx < 0 or nx >= h or ny < 0 or ny >= w:
            continue
        elif li[nx][ny] == "
            continue
        elif lin[nx][ny] == inf:
            que.append([nx,ny])
            lin[nx][ny] = lin[x][y]+1
kotae = lin[h-1][w-1]
if kotae == inf:
    print(-1)
    exit()
print(point-kotae-1)

Solution (Python):
H,W = [int(i) for i in input().split()]
maze = ['0'] * H
for i in range(H):
    maze[i] = list(input())
dx = [1,0,-1,0]
dy = [0,1,0,-1]
import collections
from collections import deque
que = deque()
dic = [[-1] * (W) for _ in range(H)]
dic[0][0] = 0
que.append([0,0])
while (len(que) != 0):
    k = que.popleft()
    x = k[0]
    y = k[1]
    for i in range(4):
        nx = x + dx[i]
        ny = y + dy[i]
        if nx < 0 or nx >= H or ny < 0 or ny >= W:
            continue
        if maze[nx][ny] == "
            continue
        if dic[nx][ny] == -1:
            que.append([nx,ny])
            dic[nx][ny] = dic[x][y] +1
ml = dic[H-1][W-1]
count = 0
for i in range(H):
    for j in range(W):
        if maze[i][j] == '.':
            count+=1
if ml == -1:
    print(-1)
else :
    print(count - ml - 1)

Solution (Python):
from collections import deque, defaultdict
H, W = map(int, input().split())
sheet = [[0]*(W+2) for i in range(H+2)]
dist = defaultdict(int)
cnt = 0
for i in range(1,H+1):
  inf = input()
  for j in range(1, W+1):
    if inf[j-1]=='.':
      sheet[i][j]=1
      cnt += 1
deq = deque([(1,1,1)])
dist[(1,1)] = 1
while deq:
  x,y,d = deq.popleft()
  flag = False
  for dx,dy in [(-1,0),(1,0),(0,-1),(0,1)]:
    nx = x+dx
    ny = y+dy
    if sheet[ny][nx]==1 and dist[(nx,ny)]==0:
      deq += [(nx,ny,d+1)]
      dist[(nx,ny)]=d+1
      if nx==W and ny==H:
        flag= True
        break
  if flag:
    print(cnt-dist[(W,H)])
    break
else:
  print(-1)

Solution (Python):
import sys
import collections

input = sys.stdin.readline


def main():
    H, W = [int(x) for x in input().split()]
    S = [input().strip() for _ in range(H)]

    dj = [1, 0, -1, 0]
    di = [0, 1, 0, -1]

    d = [[-1 for i in range(W)] for j in range(H)]
    q = collections.deque([])
    q.append((0, 0))
    d[0][0] = 0

    while q:
        p = q.popleft()
        for i in range(4):
            nj = p[0] + dj[i]
            ni = p[1] + di[i]

            if 0 <= nj < H and 0 <= ni < W and S[nj][ni] != "
                q.append((nj, ni))
                d[nj][ni] = d[p[0]][p[1]] + 1

    if d[H - 1][W - 1] == -1:
        print(-1)
    else:
        bnum = 0
        for s in S:
            bnum += s.count(".")
        print(bnum - 1 - d[H - 1][W - 1])


if __name__ == '__main__':
    main()

Solution (Python):
INF = 1e10

H, W = list(map(int, input().split()))
c = []
cnt = 0
for y in range(H):
    c.append(input())
    for s in c[-1]:
        if s=='.':
            cnt+=1
    
def search(syx, gyx):
    sy,sx = syx
    gy,gx = gyx
    visited = [[INF]*W for _ in range(H)]
    q = [[sy,sx]]
    visited[sy][sx]=0
    while len(q)>0:
        tmp_q = []
        for one in q:
            cy,cx = one
            for dy, dx in ((1, 0), (-1, 0), (0, 1), (0, -1)):
                ny, nx = cy+dy, cx+dx
                if 0 <= nx < W and 0 <= ny < H and c[ny][nx] == '.' and visited[ny][nx]> visited[cy][cx]+1:
                    visited[ny][nx] = visited[cy][cx]+1
                    tmp_q.append([ny,nx])
        q = tmp_q
        if visited[gy][gx]!=INF:
            break
    return visited[gy][gx]

ans = search([0,0],[H-1,W-1])
if ans==INF:
    print(-1)
else:
    print(cnt-ans-1)

Solution (Python):
def main():
    H, W = (int(i) for i in input().split())
    c = [input() for j in range(H)]
    from collections import deque
    dist = [[-1]*W for i in range(H)]

    def bfs(sy, sx):
        que = deque()
        dist[sy][sx] = 0
        que.append((sy, sx))
        d = ((1, 0), (0, 1), (-1, 0), (0, -1))
        while que:
            uy, ux = que.popleft()
            for dy, dx in d:
                next_y = uy + dy
                next_x = ux + dx
                if not(0 <= next_y < H and 0 <= next_x < W):
                    continue
                if dist[next_y][next_x] != -1:
                    continue
                if c[next_y][next_x] == '
                    continue
                dist[next_y][next_x] = dist[uy][ux] + 1
                que.append((next_y, next_x))

    bfs(0, 0)
    if dist[H-1][W-1] == -1:
        return print(-1)
    ans = H*W - (dist[H-1][W-1] + 1)
    for h in range(H):
        for w in range(W):
            if c[h][w] == "
                ans -= 1
    print(ans)


if __name__ == '__main__':
    main()

Solution (Python):
import queue

h, w = list(map(int, input().split()))
s = [input() for _ in range(h)]
white = 0
for i in range(h):
    white += s[i].count('.')
q = queue.Queue()
q.put(0)
kyori = [0] * (h*w)
kyori[0] = 1
while not q.empty():
    p = q.get()
    kyo = kyori[p]
    x = p%w
    y = p//w
    if x >= 1 and s[y][x-1] == '.' and kyori[p-1] == 0:
        q.put(p-1)
        kyori[p-1] = kyo+1
    if x < w-1 and s[y][x+1] == '.' and kyori[p+1] == 0:
        q.put(p+1)
        kyori[p+1] = kyo+1
    if y >= 1 and s[y-1][x] == '.' and kyori[p-w] == 0:
        q.put(p-w)
        kyori[p-w] = kyo+1
    if y < h-1 and s[y+1][x] == '.' and kyori[p+w] == 0:
        q.put(p+w)
        kyori[p+w] = kyo+1
if kyori[-1] == 0:
    print(-1)
else:
    print(white - kyori[-1])

Solution (Python):
from _collections import deque


def bfs(field, field_info, starting_y, starting_x, goal_y, goal_x):
    queue = deque([[starting_y, starting_x]])
    field_info[starting_y][starting_x] = 1

    while queue:
        y, x = queue.popleft()
        for dy, dx in ([1, 0], [-1, 0], [0, 1], [0, -1]):
            new_y, new_x = y + dy, x + dx
            if 0 <= new_y <= goal_y and 0 <= new_x <= goal_x and field[new_y][new_x] == "." and field_info[new_y][new_x] == -1:
                field_info[new_y][new_x] = field_info[y][x] + 1
                queue.append([new_y, new_x])


def solve():
    number_of_rows, number_of_columns = list(map(int, input().split()))  
    field = [input() for _ in range(number_of_rows)]
    field_info = [[-1] * number_of_columns for _ in range(number_of_rows)]
    starting_y, starting_x = 0, 0
    goal_y, goal_x = number_of_rows - 1, number_of_columns - 1
    bfs(field, field_info, starting_y, starting_x, goal_y, goal_x)

    
    
    

    if field_info[goal_y][goal_x] == -1:
        print(-1)
        return
    else:   
        number_of_black_cell = 0
        for row_i in range(number_of_rows):
            for column_i in range(number_of_columns):
                if field[row_i][column_i] == "
                    number_of_black_cell += 1
        point = number_of_columns * number_of_rows - field_info[goal_y][goal_x] - number_of_black_cell
        print(point)

solve()

Solution (Python):
from _collections import deque


def bfs(field, field_info, starting_y, starting_x, goal_y, goal_x):
    queue = deque([[starting_y, starting_x]])
    field_info[starting_y][starting_x] = 1

    while queue:
        y, x = queue.popleft()
        if [y, x] == [goal_y, goal_x]:
            return field_info[y][x]
        for dy, dx in ([1, 0], [-1, 0], [0, 1], [0, -1]):
            new_y, new_x = y + dy, x + dx
            if 0 <= new_y <= goal_y and 0 <= new_x <= goal_x and field[new_y][new_x] == "." and field_info[new_y][new_x] == -1:
                field_info[new_y][new_x] = field_info[y][x] + 1
                queue.append([new_y, new_x])


def solve():
    number_of_rows, number_of_columns = list(map(int, input().split()))  
    field = [input() for _ in range(number_of_rows)]
    field_info = [[-1] * number_of_columns for _ in range(number_of_rows)]
    starting_y, starting_x = 0, 0
    goal_y, goal_x = number_of_rows - 1, number_of_columns - 1
    bfs(field, field_info, starting_y, starting_x, goal_y, goal_x)

    
    
    

    if field_info[goal_y][goal_x] == -1:
        print(-1)
        return
    else:   
        number_of_black_cell = 0
        for row_i in range(number_of_rows):
            for column_i in range(number_of_columns):
                if field[row_i][column_i] == "
                    number_of_black_cell += 1
        point = number_of_columns * number_of_rows - field_info[goal_y][goal_x] - number_of_black_cell
        print(point)


solve()

Solution (Python):
from collections import deque


H, W = map(int, input().split())
M = []
black_before = 0
for i in range(H):
    s = list(input().strip())
    black_before += s.count('
    M.append(s)


def bfs(sx, sy):
    dist = [[-1 for _ in range(W)] for _ in range(H)]
    q = deque()
    q.append((sx, sy))
    dist[sy][sx] = 0

    while q:
        x, y = q.popleft()
        for dx, dy in [(-1, 0), (1, 0), (0, 1), (0, -1)]:
            newx, newy = x+dx, y+dy
            if not (0 <= newx < W):
                continue
            if not (0 <= newy < H):
                continue
            if M[newy][newx] == '
                continue
            if dist[newy][newx] != -1:
                continue
            q.append((newx, newy))
            dist[newy][newx] = dist[y][x] + 1
    return dist[H-1][W-1]


step = bfs(0, 0)

if step == -1:
    print(-1)
    exit()

black_after = H * W - step - 1
print(black_after - black_before)

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

ans = 0
for i in range(h): ans += s[i].count(".")
dist = [[-1 for _ in range(w)] for _ in range(h)]
dist[0][0] = 1
queue = deque()
queue.append((0,0))
while len(queue) != 0:
    cx,cy = queue.popleft()
    if cx == h-1 and cy == w-1: 
        ans -= dist[cx][cy]
        break
    for dx,dy in ((1,0),(-1,0),(0,1),(0,-1)):
        nx,ny = cx+dx,cy+dy
        if 0 <= nx < h and 0 <= ny < w and s[nx][ny] == "." and dist[nx][ny] == -1:
            queue.append((nx,ny))
            dist[nx][ny] = dist[cx][cy] + 1
else:
    ans = -1

print(ans)

Solution (Python):
H, W = map(int, input().split())
ans = 0
S = []
for _ in range(H):
    s = list(input())
    ans += s.count('.')
    S.append(s)

inf = float('inf')
G = [[inf] * H * W for _ in range(H * W)]

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

for h in range(H):
    for w in range(W):
        for x, y in zip(dx, dy):
            nx = w + x
            ny = h + y
            if 0 <= nx < W and 0 <= ny < H and S[ny][nx] != '
                G[W * h + w][W * ny + nx] = 1

from scipy.sparse.csgraph import dijkstra

d = dijkstra(G, indices=0)
if d[-1] == inf:
    print(-1)
else:
    print(int(ans - d[-1] - 1))

Solution (Python):
from collections import deque


H,W = map(int, input().split())
S = [""] * H
b = 0

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

cost = [[0 for _ in range(W)] for _ in range(H)]
cost[0][0] = 1




q = deque()
q.append((0,0))
while q:
    y,x = q.popleft()

    if 0 <= x - 1 <= W - 1 and cost[y][x-1] == 0 and S[y][x-1] == ".":
        cost[y][x-1] = cost[y][x] + 1
        q.append((y, x-1))
    if 0 <= x + 1 <= W - 1 and cost[y][x+1] == 0 and S[y][x+1] == ".":
        cost[y][x+1] = cost[y][x] + 1
        q.append((y, x+1))

    if 0 <= y - 1 <= H - 1 and cost[y-1][x] == 0 and S[y-1][x] == ".":
        cost[y-1][x] = cost[y][x] + 1
        q.append((y-1, x))

    if 0 <= y + 1 <= H - 1 and cost[y+1][x] == 0 and S[y+1][x] == ".":
        cost[y+1][x] = cost[y][x] + 1
        q.append((y+1, x))

if cost[H-1][W-1] == 0:
    print(-1)
else:
    print(H*W - b - cost[H-1][W-1])