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):
def main():
    from collections import deque

    h, w = map(int, input().split())
    grid = [input() for _ in range(h)]
    f_inf = float('inf')
    maze = [[f_inf] * w for _ in range(h)]
    maze[0][0] = 0
    que = deque([[0, 0]])
    while que:
        y, x = que.popleft()
        for i, j in ((1, 0), (-1, 0), (0, 1), (0, -1)):
            next_y, next_x = y + i, x + j
            if -1 < next_y < h and -1 < next_x < w:
                if grid[next_y][next_x] != "
                    if maze[next_y][next_x] > maze[y][x] + 1:
                        maze[next_y][next_x] = maze[y][x] + 1
                        que.append([next_y, next_x])

    if maze[h - 1][w - 1] != f_inf:
        res = h * w - (maze[h - 1][w - 1] + 1)
        for i in range(h):
            for j in range(w):
                if grid[i][j] == "
                    res -= 1
        print(res)
    else:
        print(-1)


if __name__ == '__main__':
    main()

Solution (Python):
from collections import deque
def bfs():
    
    d = [[float("inf")]*m for _ in range(n)]
    dx = [1,0,-1,0]
    dy = [0,1,0,-1]
    
    sx,sy = 0,0
    gx,gy = n-1,m-1
    
    q = deque([])
    q.append((sx,sy))
    d[sx][sy] = 0
    
    
    while q:
        p = q.popleft()
        
        if p[0] == gx and p[1] == gy:
            break
        
        for k in range(4):
            xi,yi = p[0]+dx[k],p[1]+dy[k]
            
            if 0 <= xi < n and 0 <= yi < m and maze[xi][yi] != "
                q.append((xi,yi))
                d[xi][yi] = d[p[0]][p[1]] + 1

    
    return d[gx][gy]

n,m = map(int, input().split())
maze = [list(input()) for _ in range(n)]
c = 0
for i in range(n):
    for j in range(m):
        if maze[i][j] == ".":
            c += 1
res = bfs()

if 0 < res < float("inf"):
    print(c - res -1)
else:
    print(-1)

Solution (Python):
import sys
from collections import deque
sys.setrecursionlimit(10**7)
inf=float("inf")

def BFS(x,y):
    color=[["white" for _ in range(w+2)] for _ in range(h+2)]
    D=[[inf for _ in range(w+2)] for _ in range(h+2)]

    color[x][y]="gray"
    D[x][y]=1
    queue=deque([[x,y]])
    while len(queue)!=0:
        a,b=queue.popleft()
        for c,d in ((1,0),(0,1),(-1,0),(0,-1)):
            X,Y=a+c,b+d
            if S[X][Y]=="." and color[X][Y]=="white":
                color[X][Y]="gray"
                D[X][Y]=D[a][b]+1
                queue.append([X,Y])
        color[a][b]="black"

    return D


h,w=map(int,input().split())
S=[["
S.insert(0,["
S.append(["
D=BFS(1,1)

black=0
for i in range(1,h+1):
    black +=S[i][1:w+1].count("
print(h*w-black-D[h][w] if D[h][w]!=inf else -1)

Solution (Python):
import sys
from collections import deque
sys.setrecursionlimit(10**7)
inf=float("inf")

def BFS(x,y):
    color=[["white" for _ in range(w+2)] for _ in range(h+2)]
    D=[[inf for _ in range(w+2)] for _ in range(h+2)]

    color[x][y]="gray"
    D[x][y]=0
    queue=deque([[x,y]])
    while len(queue)!=0:
        a,b=queue.popleft()
        for c,d in ((1,0),(0,1),(-1,0),(0,-1)):
            X,Y=a+c,b+d
            if S[X][Y]=="." and color[X][Y]=="white":
                color[X][Y]="gray"
                D[X][Y]=D[a][b]+1
                queue.append([X,Y])
        color[a][b]="black"

    return D


h,w=map(int,input().split())
S=[["
S.insert(0,["
S.append(["
D=BFS(1,1)

black=0
for i in range(1,h+1):
    black +=S[i][1:w+1].count("
print(h*w-(black+D[h][w]+1) if D[h][w]!=inf else -1)

Solution (Python):
import sys
from collections import deque
sys.setrecursionlimit(10**7)
inf=float("inf")

def BFS(x,y):
    color=[["white" for _ in range(w+2)] for _ in range(h+2)]
    D=[[inf for _ in range(w+2)] for _ in range(h+2)]

    color[x][y]="gray"
    D[x][y]=0
    queue=deque([[x,y]])
    while len(queue)!=0:
        a,b=queue.popleft()
        for c,d in ((1,0),(0,1),(-1,0),(0,-1)):
            X,Y=a+c,b+d
            if S[X][Y]=="." and color[X][Y]=="white":
                color[X][Y]="gray"
                D[X][Y]=D[a][b]+1
                queue.append([X,Y])
        color[a][b]="black"

    return D


h,w=map(int,input().split())
S=[["
S.insert(0,["
S.append(["
D=BFS(1,1)

black=0
for i in range(1,h+1):
    black +=S[i][1:w+1].count("
print(h*w-black-D[h][w]-1 if D[h][w]!=inf else -1)

Solution (Python):

def bfs(s,sx,sy,gx,gy):
    from collections import deque
    inf = float("inf")
    dx = [1,0,-1,0]
    dy = [0,1,0,-1]
    d = [[inf for _ in  range(w)] for _ in  range(h)]
    que = deque()
    que.append([sx,sy])
    d[sx][sy] = 1
    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 s[nx][ny] == '.' and d[nx][ny] == inf:
                que.append([nx,ny])
                d[nx][ny] = d[p[0]][p[1]] + 1
    return d[gx][gy]

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

cnt = 0
for i in s:
    for j in i:
        if j == ".":
            cnt+=1

ans = bfs(s,0,0,h - 1,w - 1)
if ans==float("inf"):
    print(-1)
else:
    print(cnt - ans)

Solution (Python):
ii = lambda : int(input())
mi = lambda : map(int,input().split())
li = lambda : list(map(int,input().split()))
h,w = mi()
a = [list(input()) for _ in range(h)]
b = [[-1]*w for i in range(h)]
from collections import deque
l=deque()
l.append((0,0))
b[0][0]=1
y_drct = [-1,0,1,0]
x_drct = [0,1,0,-1]
default_white = 0
for i in range(h):
    for j in range(w):
        if a[i][j] == '.':
            default_white +=1
while len(l)>0:
    cy,cx = l.popleft()
    if cy==h-1 and cx==w-1:
        break
    for i in range(4):
        ny=cy+y_drct[i]
        nx=cx+x_drct[i]
        if 0<=ny<h and 0<=nx<w:
            if a[ny][nx] == '.' and b[ny][nx]==-1:
                l.append((ny,nx))
                b[ny][nx]=b[cy][cx]+1

if b[h-1][w-1] == -1:
    print(-1)
else:
    print(default_white-b[h-1][w-1])

Solution (Python):
from collections import deque
r, c = list(map(int, input().split()))
sy, sx = [0, 0]
gy, gx = [r-1, c-1]

s = [list(map(str, list(input()))) for i in range(r)]

N = r*c
G = [[] for _ in range(N)]
w_c = 0
for i in range(r):
    for j in range(c):
        if s[i][j] == '.':
            w_c += 1
            for x, y in ([0, 1], [0, -1], [1, 0], [-1, 0]):
                if 0 <= i+y <= r-1 and 0 <= j+x <= c-1:
                    if s[i+y][j+x] == '.':
                        G[i*c+j].append((i+y)*c+j+x)





dist = [-1]*N
que = deque([sy*c+sx])
dist[sy*c+sx] = 0
while que:
    v = que.popleft()
    d = dist[v]
    for w in G[v]:
        if dist[w] > -1:
            continue
        dist[w] = d + 1
        que.append(w)
if dist[gy*c+gx] == -1:
    print(-1)
else:
    print(w_c-dist[gy*c+gx]-1)

Solution (Python):
from collections import deque
H,W=map(int,input().split())
M=[input() for _ in range(H)]
D=[[10**5]*W for _ in range(H)]

cnt=0
for i in range(H):
    cnt+=M[i].count('

visited=[[0]*W for _ in range(H)]
q=deque([[0,0,0]])

while q:
    x,y,dist=q.popleft()
    if visited[x][y]==1:
        continue
    visited[x][y]=1
    D[x][y]=dist
    
    for i,j in [(1,0),(-1,0),(0,1),(0,-1)]:
        if x+i>=H or y+j>=W or x+i<0 or y+j<0:
            continue
        if M[x+i][y+j]=='
            continue
        q.append([x+i,y+j,dist+1])
if D[H-1][W-1]==10**5:
    print(-1)
else:
    print((H*W-1-D[H-1][W-1])-cnt)

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

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

ex[0][0] = 1
do = [[0,0]]
check = [[1,0],[-1,0],[0,1],[0,-1]]

white = 0
for i in s:
  white += i.count('.')




while(len(do)!=0):
  x,y = do.pop(0)

  
  for i,j in check:
    a = x + i
    b = y + j
    if(-1<a<h and -1<b<w):
      if(a == h-1 and b == w-1):
        print(white-(ex[x][y])-1)
        exit()
      elif(ex[a][b] == 0 and s[a][b] =='.'):
        ex[a][b] = ex[x][y] +1
        do.append([a,b])
print(-1)

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

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

def bfs():
    log=[[0 for _ in range(W)] for _ in range(H)]
    queue=deque([[0,0]])
    while queue:
        y,x = queue.popleft()
        for j,k in ([1,0],[-1,0],[0,1],[0,-1]):
            next_y,next_x = y+j, x+k

            if 0 > next_y or next_y >= H or 0 > next_x or next_x >= W:
                continue
            elif log[next_y][next_x] == 0 and \
                maze[next_y][next_x] != '
                log[next_y][next_x] = log[y][x] + 1
                queue.append([next_y,next_x])
    
    return log[H-1][W-1]

min_wh = bfs()

if min_wh == 0:
    print('-1')
    sys.exit()

ans = (W*H - min_wh - 1) - bl_cnt

print(ans)

Solution (Python):
h, w = map(int, input().split())
maze = [['
cou = 0
for i in range(h):
    a = ['
    maze.append(a)
x = ['
maze.append(x)

for i in range(1, h+1):
    for j in range(1, w+1):
        if maze[i][j] == '
            cou += 1

ng = True
pos = [[1, 1, 0]]
checklist = [[0] * (w+2) for _ in range(h+2)]
while len(pos) > 0:
    x, y, depth = pos.pop(0)
    if ([x, y] == [h, w]) & (maze[x][y] != '
        ans = h * w - cou - depth - 1
        
        
        print(ans)
        ng = False
        break
    maze[x][y] = 'f'

    if (maze[x+1][y] == '.') & (checklist[x+1][y] == 0):
        pos.append([x+1, y, depth+1])
        checklist[x+1][y] = 1
    if (maze[x][y+1] == '.') & (checklist[x][y+1] == 0):
        pos.append([x, y+1, depth+1])
        checklist[x][y+1] = 1
    if (maze[x-1][y] == '.') & (checklist[x-1][y] == 0):
        pos.append([x-1, y, depth+1])
        checklist[x-1][y] = 1
    if (maze[x][y-1] == '.') & (checklist[x][y-1] == 0):
        pos.append([x, y-1, depth+1])
        checklist[x][y-1] = 1
    
    


if (len(pos) == 0) & ng:
    print(-1)

Solution (Python):
from sys import stdin
from collections import deque
H, W = [int(x) for x in stdin.readline().rstrip().split()]
grid = ["
for i in range(H):
    grid.append("
grid.append("

ans = 0
for h in range(1, H+1):
    for w in range(1, W+1):
        if grid[h][w] == ".":
            ans += 1

visited = [[False for i in range(W+2)] for i in range(H+2)]

visit_p = deque()
visit_p.append((1, 1, 0))
cnt = 0

f = False

while visit_p:
    nh, nw, num = visit_p.popleft()

    for dh, dw in [(0, 1), (1, 0), (-1, 0), (0, -1)]:

        if not (0 < nh+dh < H+2) or not (0 < nw+dw < W+2):
            
            continue

        if visited[nh+dh][nw+dw] or grid[nh+dh][nw+dw] == '
            
            continue

        visit_p.append((nh+dh, nw+dw, num+1))
        visited[nh+dh][nw+dw] = True

        if nh+dh == H and nw+dw == W:
            cnt = num + 2
            f = True
            break
    else:
        continue
    break

if f:
    ans -= cnt
    print(ans)

else:
    print(-1)

Solution (Python):
import sys, re, os
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, radians, acos, atan, asin
from itertools import permutations, combinations, product, accumulate
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
from fractions import gcd
def input(): return sys.stdin.readline().strip()
def STR(): return input()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def S_MAP(): return map(str, input().split())
def LIST(): return list(map(int, input().split()))
def S_LIST(): return list(map(str, input().split()))
sys.setrecursionlimit(10 ** 9)
inf = sys.maxsize
mod = 10 ** 9 + 7

h, w = MAP()
s = [STR() for _ in range(h)]
arr = [[inf for _ in range(w)] for _ in range(h)]
arr[0][0] = 0
que = deque([[0, 0]])
dy = [1, -1, 0, 0]
dx = [0, 0, 1, -1]
while len(que):
    y, x = map(int, que.popleft())
    for i in range(4):
        ny = y + dy[i]
        nx = x + dx[i]
        if 0 <= ny < h and 0 <= nx < w:
            tmp = arr[y][x]
            arr[y][x] = min(arr[y][x], arr[ny][nx] + 1)
            if arr[ny][nx] >= inf and s[ny][nx] == '.' and not [ny, nx] in que:
                que.append([ny, nx])
    if y == h - 1 and x == w - 1:
        break
if arr[h - 1][w - 1] >= inf:
    print(-1)
    exit()
ss = 0
for i in range(h):
    ss += s[i].count('.')
print(ss - arr[h - 1][w - 1] - 1)

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

dp = [[2501] * W for _ in range(H)]
dp[0][0] = 1

q = [(0, 0)]
while q:
    nq = []
    while q:
        y, x = q.pop()
        t = dp[y][x] + 1
        if y < H - 1:
            if s[y + 1][x] == '.' and dp[y + 1][x] > t:
                dp[y + 1][x] = t
                nq.append((y + 1, x))
        if y > 0:
            if s[y - 1][x] == '.' and dp[y - 1][x] > t:
                dp[y - 1][x] = t
                nq.append((y - 1, x))
        if x < W - 1:
            if s[y][x + 1] == '.' and dp[y][x + 1] > t:
                dp[y][x + 1] = t
                nq.append((y, x + 1))
        if x > 0:
            if s[y][x - 1] == '.' and dp[y][x - 1] > t:
                dp[y][x - 1] = t
                nq.append((y, x - 1))
    q = nq

if dp[H - 1][W - 1] == 2501:
    print(-1)
else:
    print(sum(s[y].count('.') for y in range(H)) - dp[H - 1][W - 1])

Solution (Python):
from collections import deque
H, W = map(int, input().split())
S = [[c for c in input()] for _ in range(H)]
a = sum([S[y][x] == "." for x in range(W) for y in range(H)])
dx = [1, -1, 0, 0]
dy = [0, 0, 1, -1]
B = [[-1]*W for _ in range(H)]
q = deque([(0, 0, 1)])  
while len(q) > 0:
    y, x, step = q.popleft()
    if y < 0 or H <= y or x < 0 or W <= x:
        continue
    if S[y][x] == '
        continue

    B[y][x] = step

    for i in range(4):
        q.append((y+dy[i], x+dx[i], step+1))

print(a - B[H-1][W-1] if B[H-1][W-1] >= 0 else -1)

Solution (Python):
from collections import deque

H,W = map(int,input().split())
maze = [list(input()) for i in range(H)]
gy, gx = H-1, W-1
maze[0][0]=1

blackTiles = 0
for i in range(H):
  for j in range(W):
    if maze[i][j]=="
      blackTiles += 1
      
que = deque([[0,0]])
patterns = [[1,0],[-1,0],[0,1],[0,-1]]
flag = False
while que:
  now = que.popleft()
  nowY = now[0]
  nowX = now[1]
  nowStep = maze[nowY][nowX]
  if nowY == gy and nowX == gx:
    ret = nowStep
    flag = True
    break
  for pattern in patterns:
    nextY = nowY + pattern[0]
    nextX = nowX + pattern[1]
    nextStep = nowStep + 1
    if 0 <= nextY < H and 0<= nextX < W and maze[nextY][nextX]==".":
      maze[nextY][nextX] = nextStep
      que.append([nextY,nextX])
if flag:
  print(H*W-ret-blackTiles)
else:
  print(-1)

Solution (Python):

import queue
h, w = map(int, input().split())
inf = 10 ** 5
s = [input() for _ in range(h)]
d = [[inf]*w for _ in range(h)]

que = queue.Queue()
que.put((0, 0))
d[0][0] = 0
while not que.empty():
    qx, qy = que.get()
    if qx == h-1 and qy == w-1:
        break
        
    for dx, dy in [(0, 1), (0, -1), (1, 0), (-1, 0)]:
        px, py = qx+dx, qy+dy
        if 0 <= px < h and 0<= py < w:
            if s[px][py] == '
                continue
            elif d[px][py] != inf:
                continue
            d[px][py] = d[qx][qy] + 1
            que.put((px, py))
            
if d[h-1][w-1] == inf:
    print(-1)
else:
    print(h * w - (d[h-1][w-1]+1) - sum(s[i].count('

Solution (Python):
from collections import deque


h, w = map(int, input().split())
field = [list(input()) for _ in range(h)]
directions = [(-1, 0), (1, 0), (0, -1), (0, 1)]
nokoshi = 1
que = deque([(0, 0)])
done = [[False] * w for _ in range(h)]

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

while que:
    for i in range(len(que)):
        y, x = que.popleft()

        if y == h - 1 and x == w - 1:
            print(white_num - nokoshi)
            exit()

        if y < 0 or y >= h or x < 0 or x >= w or field[y][x] == "
            continue
        done[y][x] = True

        for dy, dx in directions:
            que.append((y+dy, x+dx))

    nokoshi += 1
print(-1)

Solution (Python):
from collections import deque

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

INF = float('inf')
path = [[INF] * W for _ in range(H)]
q = deque()

q.append((0, 0, 1))
path[0][0] = 1
isGoal = False
while q:
    x, y, s = q.popleft()
    for dx, dy in [(1, 0), (-1, 0), (0, 1), (0, -1)]:
        nx = x + dx
        ny = y + dy
        if (nx, ny) == (H - 1, W - 1):
            path[nx][ny] = s + 1
            isGoal = True
            break
        if 0 <= nx < H and 0 <= ny < W and grid[nx][ny] == '.' and path[nx][ny] > s + 1:
            q.append((nx, ny, s + 1))
            path[nx][ny] = s + 1
    else:
        continue
    break

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

if isGoal:
    print(cnt - path[H - 1][W - 1])
else:
    print(-1)

Solution (Python):
import sys
input = sys.stdin.readline
sys.setrecursionlimit(10000000)
from collections import deque
H, W = map(int, input().split())
areas = []

black_count = 0
for _ in range(H):
    text = list(input().rstrip())
    for char in text:
        if char == '
            black_count += 1
    areas.append(text)





def bfs(areas, start_point, goal_point):
    scores = [[10**9 + 7 for _ in range(W)] for _ in range(H)]
    scores[0][0] = 1
    mv = [[-1, 0], [0, -1], [1, 0], [0, 1]]
    queue = deque([start_point])
    while queue:
        now_point = queue.popleft()
        for next_postion in mv:
            next_point = [now_point[0] + next_postion[0],
                          now_point[1] + next_postion[1]]
            if 0 <= next_point[0] < H and 0 <= next_point[1] < W:
                if areas[next_point[0]][next_point[1]] == '
                    continue
                if scores[next_point[0]][next_point[1]] > scores[now_point[0]][now_point[1]] + 1:
                    queue.append(next_point)
                    scores[next_point[0]][next_point[1]
                                          ] = scores[now_point[0]][now_point[1]] + 1
    if scores[goal_point[0]][goal_point[1]] == 10**9 + 7:
        return -1
    return scores[goal_point[0]][goal_point[1]]


cost = bfs(areas, [0, 0], [H - 1, W - 1])
if cost == -1:
    print(cost)
else:
    print(H * W - black_count - cost)

Solution (Python):
from collections import deque


def bfs(maze, visited, sh, sw, gh, gw, H, W):
    queue = deque([(sh, sw)])
    visited[sh][sw] = 1

    while queue:
        h, w = queue.popleft()
        if (h, w) == (gh, gw):
            return visited[h][w]

        for i, j in ((0, 1), (0, -1), (1, 0), (-1, 0)):
            nh = h + i
            nw = w + j
            if 0 <= nh < H and 0 <= nw < W:
                if maze[nh][nw] == "." and visited[nh][nw] == -1:
                    visited[nh][nw] = visited[h][w] + 1
                    queue.append((nh, nw))

    return -1


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

    cnt = 0
    for i in range(H):
        for j in range(W):
            if s[i][j] == ".":
                cnt += 1

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

    ans = bfs(s, visited, 0, 0, H - 1, W - 1, H, W)
    if ans == -1:
        print(ans)
    else:
        print(cnt - ans)


main()

Solution (Python):
import numpy as np
from collections import deque

H, W = list(map(int, input().split()))
s_y, s_x = 0, 0
g_y, g_x = H - 1, W - 1

visited = np.full((H, W), False)
board = np.zeros((H, W))
for i in range(H):
    row = input()
    for j, r in enumerate(row):
        if r == '.':
            board[i][j] = 1

direction = [[0, 1], [0, -1], [1, 0], [-1, 0]]
queue = deque()
queue.append(((s_y, s_x), 0))  

found = False
while len(queue) > 0:
    (y, x), dist = queue.popleft()
    if x == g_x and y == g_y:
        found = True
        break

    for dx, dy in direction:
        new_y, new_x = y + dy, x + dx
        if new_y < 0 or new_y >= H or new_x < 0 or new_x >= W:
            continue
        if board[new_y][new_x] == 0:
            continue
        if visited[new_y][new_x]:
            continue
        queue.append(((new_y, new_x), dist + 1))
        visited[new_y][new_x] = True
if found:
    print(int(np.sum(board)) - (dist + 1))
else:
    print(-1)

Solution (Python):
h, w = map(int, input().split())
M = [list(input()) for _ in range(h)]
M = [[1 if M[i][j]=='.' else 0 for j in range(w)] for i in range(h)]

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

from collections import deque

d = deque()
d.append((sy, sx))

goal = 0
V = [[0]*w for i in range(h)]
V[sy][sx] = 1
D = [[-1]*w for i in range(h)]
D[sy][sx] = 1
while len(d):
  y_cur, x_cur = d.popleft()
  
  if y_cur == gy and x_cur == gx:
    goal = 1
    break
  for dy, dx in [(-1, 0), (1, 0), (0, -1), (0, 1)]:
    y_nxt = y_cur + dy
    x_nxt = x_cur + dx
    if y_nxt>=0 and y_nxt<h and x_nxt>=0 and x_nxt<w:
      if M[y_nxt][x_nxt] == 1 and V[y_nxt][x_nxt]==0:
        V[y_nxt][x_nxt] = 1
        D[y_nxt][x_nxt] = D[y_cur][x_cur] + 1
        d.append((y_nxt, x_nxt))

if goal:
  black = h*w - sum([sum(M[i]) for i in range(h)])
  white = h*w - black
  ans = white - D[gy][gx]
  
  print(ans)
else:
  print(-1)

Solution (Python):
from collections import deque
H,W = map(int,input().split())
S = [input().strip() for _ in range(H)]
cnt = 0
for i in range(H):
    for j in range(W):
        if S[i][j]==".":
            cnt += 1
dist = [[-1 for _ in range(W)] for _ in range(H)]
que = deque([(0,0,0)])
dist[0][0] = 0
while que:
    i,j,d = que.popleft()
    if j+1<W and dist[i][j+1]<0 and S[i][j+1]==".":
        que.append((i,j+1,d+1))
        dist[i][j+1]=d+1
    if i-1>=0 and dist[i-1][j]<0 and S[i-1][j]==".":
        que.append((i-1,j,d+1))
        dist[i-1][j]=d+1
    if j-1>=0 and dist[i][j-1]<0 and S[i][j-1]==".":
        que.append((i,j-1,d+1))
        dist[i][j-1]=d+1
    if i+1<H and dist[i+1][j]<0 and S[i+1][j]==".":
        que.append((i+1,j,d+1))
        dist[i+1][j]=d+1
x = dist[H-1][W-1]
if x<0:
    print(-1)
else:
    print(cnt-1-x)

Solution (Python):
from collections import deque
MAX_VAL = 10 ** 9
H, W = map(int, input().split())
 
 
 
border_row = "
field = [border_row]
num_blacks = 0
for i in range(H):
    line = input()
    num_blacks += line.count(".")
    field.append("
field.append(border_row)
 
cost = [[MAX_VAL]*(W+2) for _ in range(H+2)]
 
if field[1][1] == ".":
    cost[1][1] = 1
else:
    cost[1][1] = MAX_VAL
 
visited = [[False]*(W+2) for _ in range(H+2)]
dxdy = [(-1, 0), (1, 0), (0, -1), (0, 1)]
def bfs():
    q = deque()
    q.append((1, 1))
    visited[1][1] = True
    while len(q):
        x, y = q.popleft()
        for dx, dy in dxdy:
            nx = x + dx
            ny = y + dy
            if field[ny][nx] == "." and not visited[ny][nx]:
                cost[ny][nx] = cost[y][x]+1
                visited[ny][nx] = True
                q.append((nx, ny))
    return 
bfs()
print(num_blacks - cost[H][W]) if cost[H][W] < MAX_VAL else print(-1)

Solution (Python):
from collections import deque
H, W = map(int, input().split())


field = []
num_blacks = 0
for i in range(H):
    line = input()
    line2 = "
    num_blacks += line.count(".")
    field.append(line)

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

cost[0][0] = 1
dxdy = [(-1, 0), (1, 0), (0, -1), (0, 1)]
def bfs():
    q = deque()
    q.append((0, 0))
    while len(q):
        x, y = q.popleft()
        for dx, dy in dxdy:
            nx = x + dx
            ny = y + dy
            if nx < 0 or nx >= W or ny < 0 or ny >= H:
                continue

            if field[ny][nx] == "." and cost[ny][nx] < 0:
                cost[ny][nx] = cost[y][x]+1
                q.append((nx, ny))

bfs()
print(num_blacks - cost[H-1][W-1]) if cost[H-1][W-1] > 0 else print(-1)

Solution (Python):
from collections import deque
H, W = map(int, input().split())


field = []
num_blacks = 0
for i in range(H):
    line = input()
    num_blacks += line.count(".")
    field.append(line)

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

cost[0][0] = 1
dxdy = [(-1, 0), (1, 0), (0, -1), (0, 1)]
def bfs():
    q = deque()
    q.append((0, 0))
    while len(q):
        x, y = q.popleft()
        for dx, dy in dxdy:
            nx = x + dx
            ny = y + dy
            if nx < 0 or nx >= W or ny < 0 or ny >= H:
                continue

            if field[ny][nx] == "." and cost[ny][nx] < 0:
                cost[ny][nx] = cost[y][x]+1
                q.append((nx, ny))

bfs()
print(num_blacks - cost[H-1][W-1]) if cost[H-1][W-1] > 0 else print(-1)

Solution (Python):
H,W=map(int,input().split())
S=[input() for _ in range(H)]
visited_place=[[-1]*W for _ in range(H)]
visited_place[0][0]=1
stack=[[0,0]]
kazu=0
for a in S:
    kazu+=a.count('.')
def bfs(S,visited_place,stack):
    while len(stack)>0:
        h,w=stack.pop()
        for x,y,in ([1,0],[-1,0],[0,1],[0,-1]):
            new_h=h+x
            new_w=w+y
            if new_w<0 or new_w>=W or new_h<0 or new_h>=H:
                continue
            if S[new_h][new_w]=='.' and visited_place[new_h][new_w]==-1:
                visited_place[new_h][new_w]=visited_place[h][w]+1
                stack.insert(0,[new_h,new_w])
    return visited_place[H-1][W-1]
if bfs(S,visited_place,stack)==-1:
    print(-1)
else:
    answer=kazu-bfs(S,visited_place,stack)
    print(answer)

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

def f(sx, sy, gx, gy):
    q = collections.deque()
    q.append((sx, sy))
    dist = [[float("inf") for w in range(W)] for h in range(H)]
    dist[sx][sy] = 0
    dx = [(-1, 0), (1, 0), (0, -1), (0, 1)]
    while len(q) != 0:
        h, w = q.popleft()
        d = dist[h][w]
        for x, y in dx:
            h2 = h + y
            w2 = w + x
            if h2 >= 0 and h2 < H and w2 >= 0 and w2 < W:
                if S[h2][w2] == "." and dist[h2][w2] == float("inf"):
                    dist[h2][w2] = d+1
                    q.append((h2, w2))
    return dist[gy][gx]
count = 0
for h in range(H):
    for w in range(W):
        if S[h][w] == '
            count += 1
ans = f(0, 0, W-1, H-1)
if ans == float('inf'):
    print(-1)
else:
    print(H*W-ans-1-count)

Solution (Python):
import sys
from collections import deque
input = sys.stdin.readline
H, W = map(int, input().split())
G = [[0]*(H*W) for _ in range(H*W)]
S = [list(input()) for i in range(H)]
dot = 0
for i in range(H*W) :
    h = i//W
    w = i%W
    if S[h][w] != "
        dot += 1
        if h > 1 and S[h-1][w] == "." :
            j = (h-1)*W + w
            G[i][j] = G[j][i] = 1
        if h < H-1 and S[h+1][w] == "." :
            j = (h+1)*W + w
            G[i][j] = G[j][i] = 1
        if w > 1 and S[h][w-1] == "." :
            j = h*W + w-1
            G[i][j] = G[j][i] = 1
        if w < W-1 and S[h][w+1] == "." :
            j = h*W + w+1
            G[i][j] = G[j][i] = 1

def bfs(s) :
    q = deque([s])
    dist[s] = 0
    while q :
        now = q.popleft()
        for i in range(H*W) :
            if G[now][i] == 1 :
                if dist[i] != -1 :
                    continue
                else :
                    dist[i] = dist[now] + 1
                    q.append(i)
    return dist[H*W-1]

dist = [-1 for _ in range(H*W)]
ans = bfs(0)
if ans == -1 :
    print(-1)
else :
    print(dot - ans - 1)

Solution (Python):
import heapq

h,w = (int(x) for x in input().split())
seq = []
white = 0
for i in range(h):
    seq.append(input())
    white += seq[-1].count('.')

MOVES = ((-1, 0), (1, 0), (0, 1), (0, -1))
visited = set()

final = (w-1, h-1)
stack = []
heapq.heappush(stack, ((0,0), 1))
ans = -1
while stack:
    state, cost = heapq.heappop(stack)
    if state == final:
        ans = white - cost
        break
    
    if state not in visited:
        x,y = state
        visited.add(state)
        for dx,dy in MOVES:
            xnew = x + dx
            ynew = y + dy
            
            if xnew >= 0 and ynew >=0 and xnew < w and ynew < h and seq[ynew][xnew] == '.':
                heapq.heappush(stack, ((xnew, ynew),cost+1))

print(ans)

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 can_go(y, x, explored):
    return not (out(y, x) or wall(y, x) or (y, x) in explored)

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

def bfs(frontier, explored, count):
    if not frontier:
        return -1
    elif any(map(lambda point: point == (H-1, W-1), frontier)):
        return count
    else:
        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()