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())
L=[]
for i in range(H):
    l=list(input())
    L.append(l)
T=[[0 for i in range(W)] for l in range(H)]
T[0][0]=1
S=[[0,0]]
SS=[[0,0]]
v=0
count=0
while 1:
    count+=1
    S=SS
    SS=[]
    while 1:
        x=S[0][1]
        y=S[0][0]
        if 0<=y and y<H-1:
            if L[y+1][x]=="." and T[y+1][x]==0:
                s=[y+1,x]
                T[y+1][x]=1
                SS.append(s)
                if y+1==H-1 and x==W-1:
                    v=1
                    break
        if 0<y and y<=H-1:
            if L[y-1][x]=="." and T[y-1][x]==0:
                s=[y-1,x]
                T[y-1][x]=1
                SS.append(s)
                if y-1==H-1 and x==W-1:
                    v=1
                    break
        if 0<=x and x<W-1:
            if L[y][x+1]=='.' and T[y][x+1]==0:
                s=[y,x+1]
                T[y][x+1]=1
                SS.append(s)
                if y==H-1 and x+1==W-1:
                    v=1
                    break
        if 0<x and x<=W-1:
            if L[y][x-1]=='.' and T[y][x-1]==0:
                s=[y,x-1]
                T[y][x-1]=1
                SS.append(s)
                if y==H-1 and x-1==W-1:
                    v=1
                    break
        S.pop(0)
        if len(S)==0:
            break
    if v==1:
        break
    if len(SS)==0:
        v=0
        break
x=0
if v==0:
    print(-1)
else:
    for i in range(H):
        for l in range(W):
            if L[i][l]=='
                x+=1
    print(W*H-x-count-1)

Solution (Python):
from collections import deque
h,w = map(int,input().split())
G = []
G.append(['']*(w+2))
for i in range(h):
    G.append([''] + list(input()) + [''])
G.append(['']*(w+2))

dist = [[-1]*(w+2) for i in range(h+2)]

dist[1][1] = 1
que = deque([(1,1)])

while que:
    v = que.popleft()
    compass = [(v[0],v[1]-1),(v[0]+1,v[1]),(v[0],v[1]+1),(v[0]-1,v[1])]
    for i in compass:
        if G[i[0]][i[1]] == '.' and dist[i[0]][i[1]] == -1:
            dist[i[0]][i[1]] = dist[v[0]][v[1]] + 1
            que.append(i)

if dist[h][w] == -1:
    print(-1)
    exit()

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

print(h*w-cnt-dist[h][w])

Solution (Python):



from collections import deque

INF = -1
H, W = map(int,input().split())
stpt = [1,1]
stpt[0]-=1
stpt[1]-=1
glpt = [H,W]
glpt[0]-=1
glpt[1]-=1
Gmap = [list(input()) for _ in range(H)]
Dist = [[INF]*W for _ in range(H)]
direc = [[1,0], [-1,0], [0,1], [0,-1]]

def dfs(start):
    Dist[start[0]][start[1]] = 1
    q = deque([])
    q.append(start)
    r = 0
    while len(q)!=0:
        
        h,w = q.popleft()
        for d in direc:
            hs, ws = h + d[0], w + d[1]
            if not (0<=hs<H and 0<=ws<W):
                continue
            if Gmap[hs][ws]=='.' and Dist[hs][ws]==INF:
                q.append([hs,ws])
                Dist[hs][ws] = Dist[h][w] + 1

def main():
    dfs(stpt)
    white = Dist[glpt[0]][glpt[1]]
    if white == INF:
        print(-1)
    else:
        black = sum([Gmap[h].count('
        print(H*W-white-black)

if __name__ == '__main__':
    main()

Solution (Python):
from collections import deque

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

start_black_cnt = 0
for i in s:
    for j in i:
        if j == '
            start_black_cnt += 1

que = deque([[0, 0]])
y, x = 0, 0
s[0][0] = 1
flg = True
while not (y == h-1 and x == w-1):
    if len(que) == 0:
        flg = False
        break

    now = que.popleft()
    y, x = now[0], now[1]
    
    if y != 0 and s[y-1][x] == '.':
        que.append([y-1, x])
        s[y-1][x] = s[y][x] + 1
    
    if y != h-1 and s[y+1][x] == '.':
        que.append([y+1, x])
        s[y+1][x] = s[y][x] + 1
    
    if x != 0 and s[y][x-1] == '.':
        que.append([y, x-1])
        s[y][x-1] = s[y][x] + 1
    
    if x != w-1 and s[y][x+1] == '.':
        que.append([y, x+1])
        s[y][x+1] = s[y][x] + 1

if flg:
    print(h*w - start_black_cnt - int(s[h-1][w-1]))
else:
    print(-1)

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

H, W = map(int, input().split())
s = [list(input().rstrip()) for h in range(H)]

bc = 0
for h in range(H):
  n = Counter(s[h])
  bc += n['


def dfs():
  que = deque()
  que.append((0,0))
  di = [1, 0, -1, 0]
  dj = [0, 1, 0, -1]
  d = [[float('inf')]*W for h in range(H)]
  d[0][0] = 0
  while que:
    point = que.popleft()
    if point[0] == H-1 and point[1] == W-1:
      break
    for i in range(4):
      ni = point[0] + di[i]
      nj = point[1] + dj[i]
      if 0 <= ni < H and 0 <= nj < W and d[ni][nj] == float('inf') and s[ni][nj] != '
        que.append((ni, nj))
        d[ni][nj] = d[point[0]][point[1]] + 1
  return d[H-1][W-1]

    
score = H*W - bc - dfs() -1 
if dfs() == float('inf'):
  score = -1
print(score)

Solution (Python):
from collections import deque

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

s = []
cnt = 0
for _ in range(h):
    tmp = list(input())
    cnt += tmp.count("
    s.append(tmp)

pos = [0, 0]
ans = 1
direction = [[0, 1], [0, -1], [1, 0], [-1, 0]]
queue = deque()
queue.append(pos)
queue.append(ans)
check = [[False for _ in range(w)] for _ in range(h)]
check[0][0] = True
while queue:
    pos = queue.popleft()
    ans = queue.popleft()
    ans += 1
    for dy, dx in direction:
        y = pos[0] + dy
        x = pos[1] + dx
        if x == -1 or x == w or y == -1 or y == h:
            continue
        if check[y][x]:
            continue
        if s[y][x] == "
            check[y][x] = True
            continue
        if y == h - 1 and x == w - 1:
            print(h * w - cnt - ans)
            exit()
        check[y][x] = True
        queue.append([y, x])
        queue.append(ans)
    
else:
    print(-1)
    exit()

Solution (Python):
import collections
import time
def bfs(G,l):
    l.append([1,1])
    visited = [[0] * len(G[0]) for i in range(len(G))]
    chk = 0
    G[1][1] = 0
    while(len(l)):
        [n0,n1] = l.popleft()
        if visited[n0][n1] == 1:
            continue
        else:
            visited[n0][n1] = 1
        if [n0,n1] == [len(G)-2,len(G[0])-2]:
            chk = 1
            break
        if G[n0][n1+1] != "
            l.append([n0,n1+1])
            G[n0][n1+1] = min(G[n0][n1] + 1,G[n0][n1+1])

        if G[n0][n1-1] != "
            l.append([n0,n1-1])
            G[n0][n1-1] = min(G[n0][n1] + 1,G[n0][n1-1])

        if G[n0+1][n1] != "
            l.append([n0+1,n1])
            G[n0+1][n1] = min(G[n0][n1]+1,G[n0+1][n1])

        if G[n0-1][n1] != "
            l.append([n0-1,n1])
            G[n0-1][n1] = min(G[n0][n1]+1,G[n0-1][n1])
        
    return chk

[h,w] = [int(i) for i in input().split()]
st = time.time()
s = [["
whites = 0
for i in range(h):
    ls = ["
    tmp = input()
    for j in range(len(tmp)):
        if tmp[j] == ".":
            ls.append(200)
        else:
            ls.append(tmp[j])
    ls.append("
    whites += tmp.count(".")
    s.append(ls)
s.append(["
l = collections.deque()

if bfs(s,l):
    print(whites - s[h][w]-1)

else:
    print(-1)

Solution (Python):
import queue

h, w = map(int, input().split())
s = []
total = h * w
num_b = 0
for i in range(h):
    tmp = input()
    num_b += tmp.count('
    s.append(tmp)

visited = set()
q = queue.Queue()


q.put((0, 0, 1))
visited.add((0, 0))

while not q.empty():
    y, x, depth = q.get()
    if y == h - 1 and x == w - 1:
        print(total - num_b - depth)
        exit()
    if x < w - 1:
        if (y, x+1) not in visited and s[y][x+1] == '.':
            visited.add((y, x+1))
            q.put((y, x+1, depth+1))
    if x > 0:
        if (y, x-1) not in visited and s[y][x-1] == '.':
            visited.add((y, x-1))
            q.put((y, x-1, depth+1))
    if y < h - 1:
        if (y+1, x) not in visited and s[y+1][x] == '.':
            visited.add((y+1, x))
            q.put((y+1, x, depth+1))
    if y > 0:
        if (y-1, x) not in visited and s[y-1][x] == '.':
            visited.add((y-1, x))
            q.put((y-1, x, depth+1))

print(-1)

Solution (Python):

from collections import deque

def main():
    h, w = map(int, input().split())
    maze = [[] for _ in range(h+2)]
    maze[0] = ['
    maze[h+1] = ['
    score = h * w
    for i in range(1, h+1):
        maze[i] = list('
        for j in range(1, w+1):
            if maze[i][j] == '
                score -= 1

    direct = [(-1,0), (0,-1), (1,0), (0,1)]
    que1 = deque([(1, 1)])
    que2 = deque([])
    score -= 1
    maze[1][1] = '
    while que1:
        x, y = que1.popleft()
        if (x, y) == (h, w):
            print(score)
            break
        for d in direct:
            dx, dy = d
            if maze[x+dx][y+dy] == '.':
                maze[x+dx][y+dy] = '
                que2.append((x+dx, y+dy))
        if len(que1) == 0:
            score -= 1
            que1.extend(que2)
            que2.clear()
    else:
        print(-1)

if __name__ == '__main__':
    main()

Solution (Python):
from collections import deque

def bfs(sx, sy, gx, gy):
  dist = [[0]*w for i in range(h)] 
  que = deque([(sy,sx)])   
  dist[sy][sx] = 1 
  directions = [(1, 0), (0, 1), (-1, 0), (0, -1)]
  while que:
    y,x = que.popleft()
    for dirs in directions:
      ny = y + dirs[0] 
      nx = x + dirs[1]
      if not(0<=ny<h and 0<=nx<w):
        continue
      if G[ny][nx] == "
        continue
      if dist[ny][nx] == 0:
        dist[ny][nx] = dist[y][x] + 1
        que.append((ny, nx))
      if nx == w-1 and ny == h-1:
        return dist[gy][gx]   
  return -1

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

cnt = 0
for i in range(h):
    cnt += G[i].count('
    
ans = bfs(0,0,w-1,h-1)
if ans == -1:
  print(-1)
else:
  score = h * w - cnt - ans
  print(score)

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

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

black = 0

for i in grid :
    black += i.count('
                     
queue = deque([[0,0]])

while queue:
    x,y = queue.popleft()
    if x == h -1  and y == w - 1:
        break
    for i,j in ([-1,0],[1,0],[0,-1],[0,1]):
        nx,ny = x+i,y+j
        if nx < 0 or ny <0 or nx >= h or ny >= w:
            continue
        if grid[nx][ny] == '.' and visited[nx][ny] == -1:
            visited[nx][ny] = visited[x][y] + 1
            queue.append([nx,ny])
            
ans = h*w - visited[h-1][w-1] - black if visited[h-1][w-1] != -1 else -1


print(ans)

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

s = list([list(input()) for i in range(H)])
dist = list([[-1 for j in range(W)] for i in range(H)])

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

while q.empty() != True:
  x, y = map(int, q.get())
  for i in range(-1,2):
    for j in range(-1,2):
      if (i == 0 and (j == 1 or j == -1)) or (j == 0 and (i == 1 or i == -1)):
        nx = x + i
        ny = y + j
        if 0 <= nx < H and 0 <= ny < W and s[nx][ny] == '.' and dist[nx][ny] == -1:
          dist[nx][ny] = dist[x][y] + 1
          s[nx][ny] = str(dist[x][y] + 1)
          q.put([nx,ny])

dCount = set()
wallCount = 0
notShortest = 0
goal = dist[H-1][W-1]
for i in s:
  for j in range(len(i)):
    if i[j] =='
      wallCount += 1
    elif i[j] == '.':
      pass
    elif goal < int(i[j]):
      pass
    else:
      dCount.add(i[j])

if dist[H-1][W-1] != -1:
  print( H*W - wallCount - goal - 1)
else:
  print(-1)

Solution (Python):
from collections import deque, namedtuple

P = namedtuple('p', 'y x')

moves = [P(-1, 0), P(0, 1), P(1, 0), P(0, -1)]
h, w = map(int, input().split())
S = [list(input()) for _ in range(h)]
s = P(0, 0)
g = P(h - 1, w - 1)
S[s.y][s.x] = 0
d = deque()
d.append(s)
reach_goal = False
while len(d) != 0:
    cur = d.popleft()
    if cur == g:
        reach_goal = True
        break
    for move in moves:
        nxt = P(cur.y + move.y, cur.x + move.x)
        can_move = 0 <= nxt.y < h and 0 <= nxt.x < w and S[nxt.y][nxt.x] == '.'
        if can_move:
            S[nxt.y][nxt.x] = S[cur.y][cur.x] + 1
            d.append(nxt)
if reach_goal:
    sharp_cnt = 0
    for S_ in S:
        for S__ in S_:
            if S__ == '
                sharp_cnt += 1
    ans = h * w - (sharp_cnt + S[g.y][g.x] + 1)
    print(ans)
else:
    print(-1)

Solution (Python):
'''


'''

from collections import deque 
import itertools


import sys


input = sys.stdin.readline 
sys.setrecursionlimit(10**7) 
inf = float('inf')

is_debug = False



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

M = [list(input().rstrip()) for _ in range(h)]



M_color = [['WHITE']*w for _ in range(h)]



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

route_str = '.'

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

def breadth_first_search():
    """

    """
    
    M_color[sy][sx] = 'GRAY'
    M_distance[sy][sx] = 0
    
    q = deque()
    q.append([sy,sx])

    
    deltas = [[-1,0], [0,1], [1,0], [0,-1]]

    
    while len(q) > 0:
        
        y, x = q.popleft()

        
        if x == gx and y == gy:
            return M_distance[y][x]

        
        for delta in deltas:
            
            after_y = y+delta[0]
            after_x = x+delta[1]
            
            if after_x < 0 or after_x > w-1 or after_y < 0 or after_y > h-1:
                continue
            
            
            if M[after_y][after_x] == route_str and M_color[after_y][after_x] == 'WHITE':
                M_color[after_y][after_x] = 'GRAY'
                
                M_distance[after_y][after_x] = M_distance[y][x] + 1
                
                q.append([after_y,after_x]) 
                            
            M_color[y][x] = 'BLACK'
    
    
    return -1


def main():
    '''メイン処理'''
    g_distance = breadth_first_search()
    
    if is_debug:
        print(g_distance)
    
    if g_distance == -1:
        print(-1)
    else:
        
        all_dot = len([s for s in list(itertools.chain.from_iterable(M)) if '.' in s])
        ans = all_dot - g_distance -1
        print(ans)
    
    
if __name__ == "__main__":
    
    main()

Solution (Python):
from collections import deque

H,W = map(int,input().split())
maze = [[] for i in range(H)]
con = 0
inf = 10 ** 6
distance = [[inf] * W for i in range(H)]

for i in range(H):
  m = list(input())
  maze[i] = m
  con += m.count("

def bfs(maze, distance, sh, sw):
  queue = deque([[sh, sw]])
  distance[sh][sw] = 0
  while queue:
    h,w = queue.popleft()
    if h == H - 1 and w == W - 1:
      return distance[H - 1][W - 1]
    for j, k in ([1, 0], [-1, 0], [0, 1], [0, -1]):
      new_h, new_w = h + j, w + k
      if new_h < 0 or new_h >= H or \
        new_w < 0 or new_w >= W:
          continue
      elif maze[new_h][new_w] != "
        distance[new_h][new_w] > distance[h][w] + 1:
        distance[new_h][new_w] = distance[h][w] + 1

        queue.append([new_h, new_w])
  
minpath = bfs(maze,distance,0,0)

if minpath == None:
  print(-1)
else:
  print(H * W - minpath - con - 1)

Solution (Python):
from collections import deque

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


def move(h, w):
    if (0 <= h and h <= H - 1) and (0 <= w and w <= W - 1):
        if s[h][w] == '.':
            return True

    return False


start = (0, 0)
goal = (H - 1, W - 1)

dist = l = [[-1 for _ in range(W)] for _ in range(H)]
dist[0][0] = 0
q = deque()
q.append(start)

flag = False

while q:
    now = q.popleft()
    h, w = now

    next_h, next_w = h, w - 1
    if move(next_h, next_w) and dist[next_h][next_w] == -1:
        dist[next_h][next_w] = dist[h][w] + 1
        q.append((next_h, next_w))

    next_h, next_w = h, w + 1
    if move(next_h, next_w) and dist[next_h][next_w] == -1:
        dist[next_h][next_w] = dist[h][w] + 1
        q.append((next_h, next_w))

    next_h, next_w = h - 1, w
    if move(next_h, next_w) and dist[next_h][next_w] == -1:
        dist[next_h][next_w] = dist[h][w] + 1
        q.append((next_h, next_w))

    next_h, next_w = h + 1, w
    if move(next_h, next_w) and dist[next_h][next_w] == -1:
        dist[next_h][next_w] = dist[h][w] + 1
        q.append((next_h, next_w))

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

ans = white - 2 - (dist[H - 1][W - 1] - 1)

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

Solution (Python):
from collections import deque

h, w = map(int,input().split())
field = [list(input()) for i in range(h)]
seen = [[False]*w for i in range(h)]
dis = [[0]*w for i in range(h)]

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

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

while len(que) != 0:
    x, y = que.popleft()
    for i, j in ([1,0], [0,1], [-1,0], [0,-1]):
        px, py = x+i, y+j
        
        if px < 0 or px > h-1 or py < 0 or py > w-1:
            continue
        
        if field[px][py] == '
            continue
        
        if seen[px][py]:
            continue
        
        else:
            dis[px][py] = dis[x][y] + 1
            seen[px][py] = True
            que.append([px, py])

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

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

print(c_dot-dis[gx][gy]-1)

Solution (Python):

from collections import deque

def bfs(sx, sy, gx, gy):
    directions = [(1, 0), (0, 1), (-1, 0), (0, -1)]
    queue = deque([(sx, sy)])
    dist = [[0] * W for _ in range(H)]
    dist[sy][sx] = 1
    while queue:
        x, y = queue.popleft()
        for dirs in directions:
            nx = x + dirs[0]
            ny = y + dirs[1]

            if nx < 0 or nx >= W or ny < 0 or ny >= H:
                continue

            if maze[ny][nx] == '
                continue

            if dist[ny][nx] == 0:
                dist[ny][nx] = dist[y][x] + 1
                queue.append((nx, ny))
            if nx == gx and ny == gy:
                return dist[gy][gx]
    return -1

H, W = map(int, input().split())
maze = [input() for _ in range(H)]
cnt = 0
for i in range(H):
    cnt += maze[i].count('
ans = bfs(0, 0, W-1, H-1)
if ans == -1:
    print(ans)
else:
    score = H * W - cnt - ans
    print(score)

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

def bfs():
    visited = [[-1]*w for _ in range(h)]
    queue = deque([[sx, sy]])
    visited[sy][sx] = 0
    while queue:
        y, x = queue.popleft()
        if [y, x] == [h-1,w-1]:
            return visited[y][x]
        
        for dy, dx in ([0,1], [1,0], [0, -1], [-1, 0]):
            ny, nx = y+dy, x+dx
            if 0<=ny<h and 0<=nx<w:
                if maze[ny][nx] == '.' and visited[ny][nx] == -1:
                    visited[ny][nx] = visited[y][x] + 1
                    queue.append([ny, nx])
                    
black_num = 0
for i in maze:
    black_num += i.count("
bfs = bfs()
if bfs is None:
    print(-1)
else:
    print(h*w - bfs -1 -black_num)

Solution (Python):
from collections import deque
h, w = map(int, input().split())
s = []
for _ in range(h):
    s.append(input())
dist = [[-1 for i in range(w)] for j in range(h)]
dist[0][0] = 0
queue = deque([[0, 0]])
while len(queue) != 0:
    now = queue.popleft()
    if now[1] != w-1:
        if dist[now[0]][now[1]+1] == -1 and s[now[0]][now[1]+1] == ".":
            dist[now[0]][now[1]+1] = dist[now[0]][now[1]] + 1
            queue.append([now[0],now[1] + 1])
    if now[0] != h-1:
        if dist[now[0] + 1][now[1]] == -1 and s[now[0]+1][now[1]] == ".":
            dist[now[0]+1][now[1]] = dist[now[0]][now[1]] + 1
            queue.append([now[0] + 1,now[1]])
    if now[1] != 0:
        if dist[now[0]][now[1]-1] == -1 and s[now[0]][now[1]-1] == ".":
            dist[now[0]][now[1]-1] = dist[now[0]][now[1]] + 1
            queue.append([now[0],now[1] - 1])
    if now[0] != 0:
        if dist[now[0]-1][now[1]] == -1 and s[now[0]-1][now[1]] == ".":
            dist[now[0]-1][now[1]] = dist[now[0]][now[1]] + 1
            queue.append([now[0] -1 ,now[1]])


if dist[h-1][w-1] == -1:
    print(-1)
else:
    length = dist[h-1][w-1] + 1
    ans = 0
    for i in range(h):
        for j in range(w):
            if s[i][j] == ".":
                ans += 1
    ans -= length
    print(ans)

Solution (Python):
H, W = map(int, input().split())
H_list = [list(input()) for i in range(H)]
import numpy as np

H_list = np.array(H_list)

w_cnt = 0
b_cnt = 0
for i in H_list:
    for j in i:
        if j == '.':
            w_cnt += 1
        if j == '
            b_cnt += 1
    
dis_mat = np.zeros((H, W))
dis_mat[0, 0] = 1
queue = []
queue.append([0,0])

while queue != []:
    v = queue.pop(0)

    v_new = [[v[0], v[1]+1],
             [v[0], v[1]-1],
             [v[0]+1, v[1]],
             [v[0]-1, v[1]]]

    for i in v_new:
        if 0 <= i[0] < H and 0 <= i[1] < W:
            if dis_mat[i[0], i[1]] == 0 and H_list[i[0], i[1]] == '.':
                dis_mat[i[0], i[1]] = dis_mat[v[0], v[1]] + 1
                queue.append(i)
        
dis = dis_mat[H-1][W-1]
if dis == 0:
    print(-1)
else:
    print(int(w_cnt - dis))

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

H, W = map(int, input().split())
field = ["
for i in range(1, H+1):
    field[i] = "
    
idxs = []
dxdy = [(1,0), (-1,0), (0,1), (0,-1)]
for row in range(1, H+1):
    for col in range(1, W+1):
        if field[row][col] == ".":
            idxs.append((row, col))
graph = {idx: deque() for idx in idxs}
for idx in idxs:
    x = idx[0]
    y = idx[1]
    for dx, dy in dxdy:
        if field[x+dx][y+dy] == ".":
            graph[idx].append((x+dx, y+dy))

dist = [[-1] * (W+1) for _ in range(H+1)] 
seen = [[0] * (W+1) for _ in range(H+1)] 
queue = deque()
def bfs(u,v):
    seen[u][v] = 1
    dist[u][v] = 0
    queue.append((u,v))
    while queue:
        p, q = queue[0]
        if not graph[(p,q)]:
            queue.popleft()
            continue
        g,h = graph[(p,q)].popleft()
        if seen[g][h]:
            continue
        seen[g][h] = 1
        dist[g][h] = dist[p][q] + 1
        queue.append((g,h))

bfs(1, 1)
total_pattern = 0
goal = dist[H][W]
if goal == -1:
    print(-1)
else:
    empty_count = 0
    for row in range(1, H+1):
        empty_count += field[row].count(".")
    total_pattern = empty_count - goal - 1
    print(total_pattern)

Solution (Python):
import sys
import math
import numpy as np
from collections import Counter, defaultdict, deque

input = sys.stdin.readline
sys.setrecursionlimit(10 ** 6)


def S():
    return input().rstrip()


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


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


inf = float("inf")
mod = 10 ** 9 + 7

h, w = MI()

white = 0
s = [["
for i in range(h):
    line = S()
    white += line.count(".")
    s.append(["
s.append(["
s[1][1] = "


dxy = ((0, 1), (0, -1), (1, 0), (-1, 0))

step = 1
q = [(1, 1)]
while q:
    qq = []
    for x, y in q:
        for dx, dy in dxy:
            nx, ny = x + dx, y + dy
            if s[nx][ny] == "
                continue
            if nx == h and ny == w:
                print(white - (step + 1))
                exit()
            qq.append((nx, ny))
            s[nx][ny] = "
    q = qq
    step += 1

print(-1)

Solution (Python):
from collections import deque

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

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

d = [[1, 0], [-1, 0], [0, 1], [0, -1]]

flag = False
while q:
  y, x = q.popleft()
  if [y, x] == [gy, gx]:
    flag = True
    break
  for dy, dx in d:
    ny, nx = y+dy, x+dx
    if ny < 0 or ny > H-1 or nx < 0 or nx > W-1:
      continue
    if maze[ny][nx] == "." and visited[ny][nx] == -1:
      visited[ny][nx] = visited[y][x] + 1
      q.append([ny, nx])

black = 0
for i in range(H):
  black += maze[i].count("

if flag:
  print(H*W - black - visited[gy][gx] - 1)
else:
  print(-1)

Solution (Python):
from collections import deque

h, w = map(int, input().split())
total_block = h * w
h += 2
w += 2
area = []
explored = []

wall_num = 0

for i in range(h):
    if i == 0 or i == h-1:
        a = '
    else:
        a = input()
        for j in a:
            if j == '
                wall_num += 1
        a = '
    area.append(a)

distance = [[float('inf') for _ in range(w)] for _ in range(h)]
distance[1][1] = 0

q = deque()
if area[1][2] == '.':
    q.append([1, 2])
    distance[1][2] = 1
    explored.append([1, 2])
if area[2][1] == '.':
    q.append([2, 1])
    distance[2][1] = 1
    explored.append([2, 1])

explored.append([1, 1])

while len(q) != 0:
    now = q.popleft()
    a = now[0]
    b = now[1]
    d = distance[a][b]
    l = [[a+1, b], [a-1, b], [a, b+1], [a, b-1]]
    for x, y in l:
        if area[x][y] == '.' and [x, y] not in explored:
            q.append([x, y])
            distance[x][y] = d + 1
            explored.append([x, y])

if distance[h-2][w-2] == float('inf'):
    print(-1)
else:
    print(total_block - wall_num - distance[h-2][w-2] - 1)

Solution (Python):
from collections import deque

def n_bfs(S,W,H):
    dx=(-1,0,1,0)
    dy=(0,1,0,-1)
    queue=deque([[0,0]])
    d=[[0]*W for _ in range(H)]
    d[0][0]=1
    while queue:
        x,y=queue.popleft()
        for n in range(4):
            nx,ny=x+dx[n],y+dy[n]
            if 0<=nx<=W-1 and 0<=ny<=H-1 and S[ny][nx]=="." and d[ny][nx]==0:
                queue.append([nx,ny])
                d[ny][nx]=d[y][x]+1
    return d[-1][-1]

def n_main():
    H,W=map(int,input().strip().split())
    S=[list(input()) for _ in range(H)]
    ans=n_bfs(S,W,H)
    num_dot=sum(s.count(".") for s in S)
    
    return num_dot-ans if ans!=0 else -1

if __name__=="__main__":
    print(n_main())

Solution (Python):
from collections import deque

def bfs(S,W,H):
    dx=(-1,0,1,0)
    dy=(0,1,0,-1)
    queue=deque([[0,0]])
    visited=[]
    goal=False
    cnt=deque([0])
    while queue and goal==False:
        exe=queue.popleft()
        C=cnt.popleft()
        for i in range(len(dx)):
            x=exe[0]+dx[i]
            y=exe[1]+dy[i]
            if [x,y]==[W-1,H-1]:
                goal=True
            elif 0<=x<=W-1 and 0<=y<=H-1 and S[y][x]==".":
                if [x,y] not in visited:
                    queue.append([x,y])
                    visited.append([x,y])
                    cnt.append(C+1) 
    return goal,C+1

def main():
    H,W=map(int,input().strip().split())
    S=[list(input()) for _ in range(H)]
    
    num_sharp=0
    for i in range(H):
        for j in range(W):
            if S[i][j]=="
                num_sharp+=1
    goal,num=bfs(S,W,H)
    if goal:
        return W*H-num_sharp-(num+1)
    else:
        return -1

if __name__=="__main__":
    print(main())

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

_S = [input() for _ in range(H)]
S = [[0] * W for _ in range(H)]
for i in range(H):
    for j in range(W):
        S[i][j] = _S[i][j]

from collections import deque
queue = deque()

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

def bfs():
    dx = [0, 1, 0, -1]
    dy = [1, 0, -1, 0]

    queue.append([0, 0])
    cost[0][0] = 0

    while len(queue) > 0:
        x, y = queue.popleft()
        if x == W - 1 and y == H - 1:
            return cost[y][x]

        for i in range(4):
            nx = x + dx[i]
            ny = y + dy[i]

            if nx < 0 or ny < 0 or nx >= W or ny >= H:
                continue
            if S[ny][nx] == "
                continue
            if cost[ny][nx] != -1:
                continue
            cost[ny][nx] = cost[y][x] + 1
            queue.append([nx, ny])
    return -1

min_cost = bfs()

import numpy as np
num_white = (np.array(S) == ".").sum(axis=1).sum() - 2

print(-1 if min_cost == -1 else num_white - (min_cost - 1))

Solution (Python):
import collections
import sys
INF = 10**18
h,w = map(int,input().split())
li = [list(input()) for i in range(h)]
sx,sy,gx,gy = 0,0,h-1,w-1

def bfs(sy,sx):
    
    d = [[INF]*w for i in range(h)]
    
    dx = [1,0,-1,0]
    dy = [0,1,0,-1]
    
    que = collections.deque([])
    que.append((sy,sx))
    d[sy][sx] = 0
    
    while que:
        
        p = que.popleft()
        
        
        for i in range(4):
            nx = p[1] + dx[i]
            ny = p[0] + dy[i]

            
            if 0<=nx and nx < w and 0 <= ny and ny < h:
                if li[ny][nx] != "
                    
                    que.append((ny,nx))
                    
                    d[ny][nx] = d[p[0]][p[1]] + 1
    return d[-1][-1]
a = bfs(0,0)-1
if a + 1 == INF:
    print(-1)
    sys.exit()
maxgrid = h*w
cnt = 0
for i in range(h):
    for j in range(w):
        if li[i][j] == "
            cnt+=1
ans = maxgrid - cnt - a -2
print(ans)