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

Solution (Python):

from collections import deque

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


cnt = 0
for i in range(h):
    grid[i] = input()
    cnt += grid[i].count('
        
dist = [[float('inf') for _ in range(w)] for _ in range(h)]

dist[0][0] = 0

P = deque([])
P.append((0,0))

while P:
    p = P.popleft()
    x,y = p[0],p[1]
    for dx,dy in ((1,0),(0,1),(-1,0),(0,-1)):
        nx,ny = x + dx, y+dy
        if 0 <= nx and 0 <= ny and nx <= h-1 and ny <= w-1 and grid[nx][ny] == '.' and dist[nx][ny] == float('inf'):
            dist[nx][ny] = dist[x][y] + 1
            P.append((nx,ny))
            
if dist[h-1][w-1] == float('inf'):
    print(-1)
    
else:
    print(h*w - dist[h-1][w-1] - cnt -1)

Solution (Python):

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

maze=[]
maze.append(["

for i in range(h):
    x=list(input())
    x.insert(0,"
    x.append("
    maze.append(x)
    
maze.append(["

visited=[[False for i in range(w+2)] for j in range(h+2)]
for i in range(h+2):
    for j in range(w+2):
        if (i==0 or i==h+1) or (j==0 or j==w+1):
            visited[i][j]=True

from collections import deque
visited[1][1]=True
d=deque()
e=deque()
d.append((1,1))
distance=0

capable=False

while (not capable) and d:
    distance+=1
    while d:
        X=d.popleft()
        x,y=X[0],X[1]
        if visited[x][y+1]==False and maze[x][1+y]==".":
            visited[x][y+1]=True
            e.append((x,1+y))
        if visited[x][y-1]==False and maze[x][y-1]==".":
            visited[x][y-1]=True
            e.append((x,y-1))
        if visited[x-1][y]==False and maze[x-1][y]==".":
            visited[x-1][y]=True
            e.append((x-1,y))
        if visited[x+1][y]==False and maze[x+1][y]==".":
            visited[x+1][y]=True
            e.append((x+1,y))
    if e:
        d=e
        e=deque()
    if visited[h][w]==True:
        capable=True
cnt=0

for i in range(h+2):
    for j in range(w+2):
        if maze[i][j]==".":
            cnt+=1
if capable:
    print(cnt-distance-1)
else:
    print(-1)

Solution (Python):
from collections import deque
h, w = map(int, input().split())
maze = ["
white_cnt = 0
for _ in range(h):
    row = input()
    white_cnt += row.count('.')
    maze.append("
else:
    maze.append("

w += 2
h += 2
INF = 10**9
dist = [[INF]*w for _ in range(h)]
dist[1][1] = 0
next_block = deque([(1, 1)])
dirc = [(-1, 0), (0, 1), (1, 0), (0, -1)]
cnt = 0
while next_block:
    i, j = next_block.popleft()
    for x, y in dirc:
        if maze[i+x][j+y] == '
            continue
        if dist[i+x][j+y] <= dist[i][j]+1:
            continue
        dist[i+x][j+y] = dist[i][j]+1
        next_block.append((i+x, j+y))


if dist[-2][-2] == INF:
    print(-1)
else:
    print(white_cnt-dist[-2][-2]-1)

Solution (Python):
from collections import deque
h, w = map(int, input().split())
maze = ["
white_cnt = 0
for _ in range(h):
    row = input()
    white_cnt += row.count('.')
    maze.append("
else:
    maze.append("

w += 2
h += 2
INF = 10**9
dist = [[INF]*w for _ in range(h)]
dist[1][1] = 0
next_block = deque([(1, 1)])
dirc = [(-1, 0), (0, 1), (1, 0), (0, -1)]
cnt = 0
while next_block:
    i, j = next_block.popleft()
    for x, y in dirc:
        if maze[i+x][j+y] == '
            continue
        if dist[i+x][j+y] != INF:
            continue
        next_block.append((i+x, j+y))
        dist[i+x][j+y] = min(dist[i+x+v][j+y+w] for v, w in dirc)+1

if dist[-2][-2] == INF:
    print(-1)
else:
    print(white_cnt-dist[-2][-2]-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 _ 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):
import math
import copy
import sys
import fractions


import decimal
import heapq
import collections
import itertools
import bisect



sys.setrecursionlimit(100001)







def getInputIntList():
    outputDataList = []
    inputData = input().split()
    outputDataList = [int(n) for n in inputData]

    return outputDataList


def getSomeInputInt(n):
    outputDataList = []
    for i in range(n):
        inputData = int(input())
        outputDataList.append(inputData)

    return outputDataList


def getSomeInputListInt(n):
    inputDataList = []
    outputDataList = []
    for i in range(n):
        inputData = input().split()
        inputDataList = [int(n) for n in inputData]
        outputDataList.append(inputDataList)

    return outputDataList




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

table = [[1 for _ in range(w)] for _ in range(h)]
d_table = [[-1 for _ in range(w)] for _ in range(h)]

for i in range(h):
    s = input()
    tmp = list(s)
    for j, ts in enumerate(tmp):
        if ts == ".":
            table[i][j] = 0

ans = -1
search_table = [[-1, 0], [1, 0], [0, -1], [0, 1]]

q = collections.deque([])
q.append([0,0])
table[0][0]=1
d_table[0][0]=0

gy, gx = [h-1, w-1]

while len(q) > 0:
    qy, qx = q.popleft()

    for y, x in search_table:
        cy = qy + y
        cx = qx + x

        if cy < 0 or cy > h - 1 or cx < 0 or cx > w - 1:
            continue

        if table[cy][cx] == 0 and d_table[cy][cx] == -1:
            table[cy][cx] = 1
            d_table[cy][cx] = d_table[qy][qx] + 1
            q.append([cy, cx])

            if cy == gy and cx == gx:
                ans = d_table[cy][cx]

if ans == -1:
    print(-1)
    exit(0)

cnt = 0

for i in range(h):
    for j in range(w):
        tmp = d_table[i][j]
        if tmp > -1:
            cnt+=1
        elif tmp == -1 and table[i][j]==0:
            cnt+=1

res = cnt -ans -1



print(res)

Solution (Python):
import queue

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

def bfs():
    start=[0,0]
    goal=[W-1,H-1]
    distance=[[-1]*H for j in range(W)]
    li_x=[1,-1,0,0]
    li_y=[0,0,1,-1]
    q = queue.Queue()
    q.put(start)
    distance[start[0]][start[1]]=1

    while not q.empty():
        hoge=q.get()
        x=hoge[0]
        y=hoge[1]
        dis=distance[x][y]

        for i in range(4):
            x1=x+li_x[i]
            y1=y+li_y[i]
            if (0 <=x1 < W and 0 <= y1 < H):
                if distance[x1][y1] == -1:
                    if S[y1][x1]=='.':
                        q.put([x1,y1])
                        distance[x1][y1]=dis+1
    m=''
    for i in range(H):
        m+=S[i]
    
    if distance[W-1][H-1]==-1:
        ans=-1 
    else:
        ans=m.count('.')-distance[W-1][H-1]
    return ans

ans=bfs()
print(ans)

Solution (Python):
from heapq import heappush, heappop, heapify
from collections import deque, defaultdict, Counter
import itertools
from itertools import permutations, combinations, accumulate
import sys
import bisect
import string
import math
import time


def I(): return int(input())


def MI(): return map(int, input().split())


def S(): return input()


def MS(): return map(str, input().split())


def LI(): return [int(i) for i in input().split()]


def LI_(): return [int(i)-1 for i in input().split()]


def StoI(): return [ord(i)-97 for i in input()]


def ItoS(nn): return chr(nn+97)


def input(): return sys.stdin.readline().rstrip()


def show(*inp, end='\n'):
    if show_flg:
        print(*inp, end=end)


def print_matrix(mat):
    for i in range(len(mat)):
        print(*mat[i])


YNL = {False: 'No', True: 'Yes'}
YNU = {False: 'NO', True: 'YES'}
MOD = 10**9+7
inf = float('inf')
IINF = 10**10
l_alp = string.ascii_lowercase
u_alp = string.ascii_uppercase
ts = time.time()

nums = ['1', '2', '3', '4', '5', '6', '7', '8', '9', '10']



show_flg = False

BLOCK = '
ROAD = '.'


def bfs(graph, initial, goal, H, W):
    options = [(-1, 0), (0, 1), (1, 0), (0, -1)]
    q = deque([initial])
    visited = [[False for i in range(W)] for i in range(H)]
    dist = [[-1 for i in range(W)] for i in range(H)]
    visited[initial[0]][initial[1]] = True
    dist[initial[0]][initial[1]] = 0

    while len(q) != 0:
        p = q.popleft()

        for d in options:
            i = p[0] + d[0]
            j = p[1] + d[1]

            if i >= 0 and i < H and j >= 0 and j < W and not visited[i][j] and graph[i][j] != BLOCK:
                visited[i][j] = True
                q.append((i, j))
                dist[i][j] = dist[p[0]][p[1]] + 1

    return dist


def main():
    H, W = MI()
    graph = [None] * H

    for i in range(H):
        graph[i] = list(S())

    dist = bfs(graph, (0, 0), (H-1, W-1), H, W)

    if dist[H-1][W-1] == -1:
        print(-1)
        return

    ans = H * W
    
    for i in range(H):
        for j in range(W):
            if graph[i][j] == '
                ans -= 1

    ans -= dist[H-1][W-1] + 1
    print(ans)


if __name__ == '__main__':
    main()

Solution (Python):
import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
sys.setrecursionlimit(10 ** 7)

h, w = map(int, readline().split())
s = [input() for i in range(h)]
q = [(0, 0)]
g = (h - 1, w - 1)
test = [(0, 1), (0, -1), (1, 0), (-1, 0)]
inf = float('inf')
dist = [[inf] * w for _ in range(h)]
dist[0][0] = 0
cnt = 0
while 1:
    qq = []
    cnt += 1
    for y, x in q:
        for dy, dx in test:
            yy, xx = y + dy, x + dx
            if xx < 0 or yy < 0 or xx > w - 1 or yy > h - 1:
                continue
            if s[yy][xx] == '
                continue
            dist[yy][xx] = cnt
            qq.append((yy, xx))
    q = qq
    if g in q:
        break
    if q:
        continue
    else:
        print(-1)
        exit()
for i in range(h):
    for j in range(w):
        if s[i][j] == '
            cnt += 1
print(h * w - cnt - 1)

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

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

d = [[-1]*w for _ in range(h)]
d[0][0] = 1
que = deque([[0, 0]])
while que:
    x, y = que.popleft()
    for i, j in [[1,0],[0,1],[-1,0],[0,-1]]:
        nx, ny = x+i, y+j
        if 0<=nx<w and 0<=ny<h and c[ny][nx]=="." and d[ny][nx]==-1:
            d[ny][nx] = d[y][x]+1
            que.append([nx, ny])
if d[h-1][w-1] == -1:
    print(-1)
else:
    print(ans-d[h-1][w-1])

Solution (Python):
from heapq import heappop, heappush
H, W = map(int,input().split())
dire = [(1, 0), (0, 1), (-1, 0), (0, -1)]
mp = [[0] * (W + 2)]
cnt = 0
for i in range(H):
    S = [0]
    for ch in input():
        S.append(ch)
        if ch == ".":
            cnt += 1
    S.append(0)
    mp.append(S)
mp.append([0] * (W + 2))
leng = [[float("inf")] * (W + 2) for _ in range(H + 2)]
leng[1][1] = 1
que = [(1, 1, 1)]
while que:
    cost, i, j = heappop(que)
    if cost != leng[i][j]:
        continue
    for di, dj in dire:
        if mp[i + di][j + dj] == ".":
            if leng[i + di][j + dj] > cost + 1:
                leng[i + di][j + dj] = cost + 1
                heappush(que, (leng[i + di][j + dj], i + di, j + dj))
if leng[H][W] == float("inf"):
    print(-1)
else:
    print(cnt - leng[H][W])

Solution (Python):
from collections import deque


def bfs(si, sj, gi, gj):
    q = deque()
    q.append([si, sj, 0])
    used = [[False for _ in range(W)] for _ in range(H)]
    used[si][sj] = True

    while len(q) > 0:
        prvi, prvj, cost = q.popleft()
        for i, j in [[prvi - 1, prvj], [prvi + 1, prvj], [prvi, prvj - 1], [prvi, prvj + 1]]:
            if i == gi and j == gj:
                return cost + 1

            if i < 0 or j < 0 or i >= H or j >= W:
                continue

            if used[i][j] or C[i][j] == '
                continue

            q.append([i, j, cost + 1])
            used[i][j] = True
    return -1


if __name__ == '__main__':
    H, W = map(int, input().split())
    C = [input() for _ in range(H)]
    min_cost = bfs(0, 0, H - 1, W - 1)
    if min_cost == -1:
        print(-1)
    else:
        black_num = sum([row.count('
        print(H * W - black_num - min_cost - 1)

Solution (Python):
from collections import deque

H, W = map(int, input().split())
start = [1, 1]
goal  = [H, W]

maps = [[-1]*(W+2)] + [([-1] + list(input()) + [-1]) for _ in range(H)] + [[-1]*(W+2)]
seen = [[-1]*(W+2) for _ in range(H+2)]
dxy = ((-1, 0), (1, 0), (0, -1), (0, 1))
todo = deque()

blacknum = 0
for i in maps:
    blacknum += i.count('


def bfs(x, y):
    for i in dxy:
        new_x = x+i[0]
        new_y = y+i[1]
        if seen[new_x][new_y] == -1:
            if maps[new_x][new_y] == '.':
                seen[new_x][new_y] = seen[x][y] + 1
                todo.append([new_x, new_y])
            else:
                seen[new_x][new_y] = -2


todo.append([start[0], start[1]])
seen[start[0]][start[1]] = 1

while len(todo) > 0:
    tmp = todo.popleft()
    bfs(tmp[0], tmp[1])

if seen[H][W] < 0:
    print(-1)
else:
    print(H*W-blacknum-seen[H][W])

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

def bfs(x, y):
    for (next_x, next_y) in [(x + 1, y), (x - 1, y), (x, y + 1), (x, y - 1)]:
        if 0 <= next_x < h and 0 <= next_y < w and map[next_x][next_y] == ".":
            map[next_x][next_y] = 1 + map[x][y]
            q.append([next_x, next_y])

map[0][0] = 1
q = deque([[0, 0]])
while True:
    if len(q) == 0:
        break
    x, y = q.popleft()
    bfs(x, y)

if map[h-1][w-1] == ".":
    ans = -1
else:
    ans -= map[h-1][w-1]

print(ans)

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

from collections import deque
cnt_black = 0
for y in range(h):
    for x in range(w):
        if(m[y][x]=='
            cnt_black += 1
cnt_white =h*w-cnt_black

sy,sx = 0,0

q = deque([(sy,sx)])



cnt = [[-1]*w for _ in range(h)]
cnt[sy][sx]=0
while q:
    cy,cx = q.popleft() 
    for dy,dx in ([1,0],[-1,0],[0,1],[0,-1]):
        ny, nx = cy + dy, cx + dx
        if(0<=ny<h and 0<=nx<w and cnt[ny][nx]==-1 and m[ny][nx]!='
            
            cnt[ny][nx] = cnt[cy][cx]+1
            q.append((ny,nx))
            
            
if(cnt[h-1][w-1]==-1):
    ans = -1
else:
    ans = cnt_white-1-cnt[h-1][w-1]
print(ans)

Solution (Python):
from collections import deque
H, W = map(int, input().split())
grid = []
for _ in range(H):
    array = input()
    grid.append(array)


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


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


dist[0][0] = 0
dy = [0,0,1,-1]
dx = [-1,1,0,0]
que = deque()
que.append([0,0])

while que:
    y,x = que.popleft()
    for i in range(4):
        vy = y + dy[i] 
        vx = x + dx[i] 
        if vy < 0 or H <= vy or vx < 0 or W <= vx:
            continue
        if dist[vy][vx] != -1 or grid[vy][vx] == '
            continue
        dist[vy][vx] = dist[y][x] + 1
        que.append([vy,vx])

if dist[-1][-1] == -1:
    print(-1)
else:
    print(H*W-dist[-1][-1]-count-1)

Solution (Python):
from collections import deque

h, w = map(int, input().split())
mapping = [0]*h

for i in range(h):
    mapping[i] = input()


wall = 0
yet = [[False]*w for i in range(h)]
for i in range(h):
    for j in range(w):
        if mapping[i][j] == "
            yet[i][j] = True
            wall += 1

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

not_yet = deque([[0, 0]])
yet[0][0] = True


while len(not_yet) > 0:
    key = not_yet.popleft()
    a, b = key[0], key[1]
        
    if a != 0 and not yet[a-1][b]:
        not_yet.append([a-1, b])
        yet[a-1][b] = True
        depth[a-1][b] = depth[a][b]+1
            
    if a != h-1 and not yet[a+1][b]:
        not_yet.append([a+1, b])
        yet[a+1][b] = True
        depth[a+1][b] = depth[a][b]+1
            
    if b != 0 and not yet[a][b-1]:
        not_yet.append([a, b-1])
        yet[a][b-1] = True
        depth[a][b-1] = depth[a][b]+1
            
    if b != w-1 and not yet[a][b+1]:
        not_yet.append([a, b+1])
        yet[a][b+1] = True
        depth[a][b+1] = depth[a][b]+1
if depth[h-1][w-1]:
  print(h*w-depth[h-1][w-1]-1-wall)
else:
  print(-1)

Solution (Python):
from collections import deque
h,w = list(map(int, input().split()))
s = ['
[s.append('
s.append('
whitecount = 0
for i in s:
    whitecount += i.count('.')

ans = 0
queue = deque([[1,1]])
cost = [[1]*(w+2) for _ in range(h+2)]
visited = [[False]*(w+2) for _ in range(h+2)]
while queue:
    x,y = queue.popleft()
    visited[y][x] = True
    hjkl = [[x-1,y], [x,y-1], [x+1,y], [x,y+1]]
    for dx,dy in hjkl:
        if (s[dy][dx]=='.') and (visited[dy][dx]==False) and ([dx,dy] not in queue):
            queue.append([dx,dy])
            cost[dy][dx] = cost[y][x] + 1

if visited[h][w]:
    print(whitecount - cost[h][w])
else:
    print(-1)

Solution (Python):
from collections import deque

def dfs(sx, sy):
  stack = deque()
  stack.append([sx, sy])
  visited[sy][sx] = 1
  while stack:
    x, y = stack.popleft()
    if x == w - 1 and y == h - 1:
      break
    for dx, dy in [(1, 0), (-1, 0), (0, 1), (0, -1)]:
      if 0 <= x + dx < w and 0 <= y + dy < h:
        if S[y + dy][x + dx] != "
          visited[y + dy][x + dx] = visited[y][x] + 1
          stack.append([x + dx, y + dy])

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

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

dfs(0, 0)

whites = sum([s.count(".") for s in S])

if visited[h - 1][w - 1] != -1:
  ans = whites - visited[h - 1][w - 1]
else:
  ans = -1
  
print(ans)

Solution (Python):
import sys
from collections import deque
MAX_INT = int(10e10)
MIN_INT = -MAX_INT
mod = 1000000007
sys.setrecursionlimit(1000000)
def IL(): return list(map(int,input().split()))
def SL(): return input().split()
def I(): return int(sys.stdin.readline())
def S(): return input()

H,W = IL()
grid = [list(S()) for i in range(H)]

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

data = [[MAX_INT]*W for i in range(H)]

d = deque()
d.append((1, 0, 0)) 
while d:
  cnt, h, w = d.popleft()
  if data[h][w] > cnt:
    data[h][w] = cnt
    for i,j in ((-1,0), (0,-1),(1,0),(0,1)):
      if 0 <= h+i < H and 0 <= w+j < W:
        if grid[h+i][w+j] == ".":
          d.append((cnt+1, h+i, w+j))
if data[-1][-1] == MAX_INT:
  print(-1)
else:
  print(ans - data[-1][-1])

Solution (Python):
from collections import deque

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

count_w = 0
for i in range(H):
    for j in range(W):
        if M[i][j] == ".":
            count_w += 1
            
def bfs():
    que = deque()
    que.append((0,0))
    dx = [0,1,0,-1]
    dy = [-1,0,1,0]
    d = [[float("Inf")]*W for i in range(H)]
    d[0][0] = 0
    while que :
        p = que.popleft()
        for i in range(4):
            nx = p[0] + dx[i]
            ny = p[1] + dy[i]
            if 0 <=nx <H and 0 <= ny <W and M[nx][ny] != "
                que.append((nx,ny))
                d[nx][ny] = d[p[0]][p[1]]+1
    if d[H-1][W-1] != float("Inf"):
        return d[H-1][W-1]
    else:
        return -1

ans = bfs()
if ans != -1:
    print(count_w-ans-1)
else:
    print(-1)

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

sys.setrecursionlimit(10**9)

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



S = np.zeros((H + 2, W + 2), dtype='int')
S[0, :] = 1
S[-1, :] = 1
S[:, 0] = 1
S[:, -1] = 1

cost = np.zeros((H + 2, W + 2), dtype='int')
cost[:, :] = -1

subset = S[1:-1, 1:-1]
for h in range(H):
    s = list(input())
    subset[h:] = np.array([0 if i == '.' else 1 for i in s], dtype='i')

dd = ((-1, 0), (1, 0), (0, -1), (0, 1))
q = deque([(1, 1)])
cost[1, 1] = 0

while q:
    x, y = q.popleft()
    for dx, dy in dd:
        nx = x + dx
        ny = y + dy
        if S[nx, ny] == 0 and cost[nx, ny] == -1:
            cost[nx, ny] = cost[x, y] + 1
            q.append((nx, ny))

if cost[H, W] == -1:
    print(-1)
    exit()

ans = (H + 2) * (W + 2) - (S == 1).sum() - cost[H, W] - 1
print(ans)

Solution (Python):
h, w = map(int, input().split())
maze = [list(input()) for _ in range(h)]
memo = [[0 for _ in range(w)] for _ in range(h)]
step = [[1, 0], [-1, 0], [0, 1], [0, -1]]

memo[0][0] = 1
white = 0
for row in maze:
    white += row.count('.')

q = [[0, 0, 0]]

while q:
    x, y, c = q.pop(0)
    for a, b in step:
        next_x = x + a
        next_y = y + b
        if next_x == h - 1 and next_y == w - 1:
            print(white - (c + 2))
            exit()
        if next_x >= h or next_x < 0:
            continue
        if next_y >= w or next_y < 0:
            continue
        if memo[next_x][next_y] == 1:
            continue
        if maze[next_x][next_y] == '
            continue
        memo[next_x][next_y] = 1
        q.append([next_x, next_y, c + 1])
print(-1)

Solution (Python):
import sys

stdin = sys.stdin
inf = 1 << 60
mod = 1000000007

ni      = lambda: int(ns())
nin     = lambda y: [ni() for _ in range(y)]
na      = lambda: list(map(int, stdin.readline().split()))
nan     = lambda y: [na() for _ in range(y)]
nf      = lambda: float(ns())
nfn     = lambda y: [nf() for _ in range(y)]
nfa     = lambda: list(map(float, stdin.readline().split()))
nfan    = lambda y: [nfa() for _ in range(y)]
ns      = lambda: stdin.readline().rstrip()
nsn     = lambda y: [ns() for _ in range(y)]
ncl     = lambda y: [list(ns()) for _ in range(y)]
nas     = lambda: stdin.readline().split()

from collections import deque

h, w = na()
maze = nsn(h)

def bfs():
    q = deque()
    q.append((0, 0))
    dx, dy = [1, 0, 0, -1], [0, 1, -1, 0]
    dist = [[inf] * w for _ in range(h)]
    dist[0][0] = 0
    while len(q):
        p = q.popleft()
        cx, cy = p
        for i in range(4):
            nx, ny = cx + dx[i], cy + dy[i]
            if nx >= 0 and nx < w and ny >= 0 and ny < h and dist[ny][nx] == inf and maze[ny][nx] != '
                dist[ny][nx] = dist[cy][cx] + 1
                q.append((nx, ny))
    return dist[h - 1][w - 1]

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

d = bfs()
if d == inf:
    print(-1)
else:
    print(h * w - cnt - d - 1)

Solution (Python):
from collections import deque
h,w = map(int,input().split())
grid = []
white = 0
grid.append(["
for i in range(h):
    a = list(input())
    white += a.count(".")
    a.insert(0,"
    a.append("
    grid.append(a)
grid.append(["

grid[1][1] = "1"

def bfs():
    q = deque([(1,1)])
    used = set()
    while q:
        here = q.popleft()
        num = int(grid[here[0]][here[1]])
        x = here[0]
        y = here[1]
        if grid[x-1][y] == "." and (x-1,y) not in used:
            grid[x-1][y] = str(num + 1)
            used.add((x-1,y))
            q.append((x-1,y))
        if grid[x+1][y] == "." and (x+1,y) not in used:
            grid[x+1][y] = str(num + 1)
            used.add((x+1,y))
            q.append((x+1,y))
        if grid[x][y-1] == "." and (x,y-1) not in used:
            grid[x][y-1] = str(num + 1)
            used.add((x,y-1))
            q.append((x,y-1))
        if grid[x][y+1] == "." and (x,y+1) not in used:
            grid[x][y+1] = str(num + 1)
            used.add((x,y+1))
            q.append((x,y+1))

bfs()
if grid[h][w] == ".":
    print(-1)
else:
    print(white-int(grid[h][w]))

Solution (Python):
from collections import deque
h,w = map(int,input().split())
grid = []
white = 0
grid.append(["
for i in range(h):
    a = list(input())
    white += a.count(".")
    a.insert(0,"
    a.append("
    grid.append(a)
grid.append(["

grid[1][1] = "1"

def bfs():
    q = deque([(1,1)])
    used = set()
    while q:
        here = q.popleft()
        num = int(grid[here[0]][here[1]])
        x = here[0]
        y = here[1]
        if grid[x-1][y] == "." and (x-1,y) not in used:
            grid[x-1][y] = str(num + 1)
            used.add((x-1,y))
            q.append((x-1,y))
        if grid[x+1][y] == "." and (x+1,y) not in used:
            grid[x+1][y] = str(num + 1)
            used.add((x+1,y))
            q.append((x+1,y))
        if grid[x][y-1] == "." and (x,y-1) not in used:
            grid[x][y-1] = str(num + 1)
            used.add((x,y-1))
            q.append((x,y-1))
        if grid[x][y+1] == "." and (x,y+1) not in used:
            grid[x][y+1] = str(num + 1)
            used.add((x,y+1))
            q.append((x,y+1))

bfs()
if grid[h][w] == ".":
    print(-1)
else:
    print(white-int(grid[h][w]))

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

H, W = map(int, input().split())
s = [input() for _ in range(H)]
queue = deque()
dist = [[-1] * W for _ in range(H)]
queue.append((0, 0))
dist[0][0] = 0
move = [(1, 0), (0, 1), (-1, 0), (0, -1)]
while queue:
    i, j = queue.popleft()
    for di, dj in move:
        ni, nj = i + di, j + dj
        if 0 <= ni < H and 0 <= nj < W and s[ni][nj] == '.' and dist[ni][nj] == -1:
            dist[ni][nj] = dist[i][j] + 1
            queue.append((ni, nj))
ans = 0
if dist[-1][-1] == -1:
    ans = -1
else:
    ans = sum(row.count('.') for row in s) - (dist[-1][-1] + 1)
print(ans)

Solution (Python):
from collections import deque,defaultdict
def bfs(sy,sx,gy,gx):
    q = deque([[sy,sx]])
    visited[sy][sx]=0
    while q:
        y,x = q.popleft()
        if [y,x]==[gy,gx]:
            return visited[y][x]
        for j,k in ([1,0],[-1,0],[0,1],[0,-1]):
            ny,nx = y+j,x+k
            if ny<0 or ny>h-1 or nx<0 or nx>w-1 or path[ny][nx]=="
                continue
            if path[ny][nx]=="." and visited[ny][nx]==-1:
                visited[ny][nx]=visited[y][x]+1
                q.append([ny,nx])

h,w=map(int,input().split())
path=[input() for i in range(h)]
visited=[[-1]*w for i in range(h)]
sy,sx=0,0
gy,gx=h-1,w-1
bfs(sy,sx,gy,gx)


if visited[gy][gx]==-1:
    print(-1)
    exit()

c=0
for i in range(h):
    for j in range(w):
        if path[i][j]=='
            c+=1
print(h*w-c-(visited[gy][gx]+1))

Solution (Python):
from collections import deque
d=deque()
e=deque()
h,w=map(int,input().split())
field=[0 for i in range(h+2)]
field[0]=[True for i in range(w+2)]
distance=0
white=0
for i in range(h):
    s=input()
    a=[False for i in range(w+2)]
    a[0]=True
    for j in range(w):
        if s[j]=="
            a[j+1]=True
        else:
            white+=1

    a[w+1]=True
    field[i+1]=a
field[h+1]=[True for i in range(w+2)]
d.append((1,1))
ans=-1
while d:
    while d:
        some=d.popleft()
        index1,index2=some[0],some[1]
        if index1==h and index2==w:
            ans=distance
        if field[index1-1][index2]==False:
                field[index1-1][index2]=True
                e.append((index1-1,index2))
        if field[index1+1][index2]==False:
                field[index1+1][index2]=True
                e.append((index1+1,index2))
        if field[index1][index2+1]==False:
                field[index1][index2+1]=True
                e.append((index1,index2+1))
        if  field[index1][index2-1]==False:
                field[index1][index2-1]=True
                e.append((index1,index2-1))
    distance+=1
    d=e
    e=deque()
if ans>=0:
    print(white-ans-1)
else:
    print(-1)

Solution (Python):
from collections import deque
 
h, w = map(int, input().split())
maze = [list(input()) for _ in range(h)]
visited = [[-1] * w for _ in range(h)]
move = [(1,0), (0,1), (-1,0), (0,-1)]
 
sy, sx= 0, 0
gy, gx = h-1, w-1
 
queue = deque([(sy, sx, 0)])
 
while queue:
    y, x, dist = queue.popleft()
    for dy, dx in move:
        if maze[y+dy:y+dy+1] and maze[y+dy][x+dx:x+dx+1]:
            if maze[y+dy][x+dx] == "." and visited[y+dy][x+dx] == -1:
                visited[y+dy][x+dx] = dist + 1
                queue.append((y+dy, x+dx, dist+1))
shortest_distance = visited[gy][gx]
 
if shortest_distance == -1:
    print("-1")
else:
    white_count = 0
    for row in maze:
        for cell in row:
            if cell == ".":
                white_count += 1
 
    score = white_count - 1 - shortest_distance
    print(score)