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

def search_maze(maze, start, goal, size):
    TO_NEXT_CELL = [(1,0), (0,1), (-1,0), (0,-1)]
    h = size[0]
    w = size[1]
    distance = [[float("inf") for _ in range(w)] for _ in range(h)]
    min_step = -1
    queue = deque([start])
    distance[start[0]][start[1]] = 1
    while len(queue) != 0:
        i, j = queue.popleft()
        d = distance[i][j]
        if i == goal[0] and j == goal[1]:
            min_step = d
            break
        for next_cell in TO_NEXT_CELL:
            next = (i + next_cell[0], j + next_cell[1])
            if (0 <= next[0] and next[0] < h and 0 <= next[1] and next[1] < w and distance[next[0]][next[1]] == float('inf')):
                if maze[next[0]][next[1]] == '.':
                    queue.append(next)
                    distance[next[0]][next[1]] = d + 1
    return min_step

if __name__ == '__main__':
    h, w = map(int, input().split())
    maze = []
    for i in range(h):
        maze.append(list(input().strip()))
    white_count = 0
    for i in range(h):
        for j in range(w):
            if maze[i][j] == '.':
                white_count += 1
    min_step = search_maze(maze, (0,0), (h-1,w-1), (h,w))
    if min_step == -1:
        print ('-1')
    else:
        ans = white_count - min_step
        print(ans)

Solution (Python):
from collections import deque

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

check = [[False] * w for i in range(h)]

ans = 0
q = deque()
q.append((0, 0, 0))
while len(q) > 0:
    x, y, step = q.popleft()
    if x == w-1 and y == h-1:
        ans = step
        break
    for n_x, n_y in [(x-1, y), (x+1, y), (x, y-1), (x, y+1)]:
        if 0 <= n_x and n_x < w and 0 <= n_y and n_y < h:
            if board[n_y][n_x] == "." and not check[n_y][n_x]:
                q.append((n_x, n_y, step+1))
                check[n_y][n_x] = True

if ans != 0:
    air = 0
    for y in range(h):
        for x in range(w):
            if board[y][x] == ".":
                air += 1
    print(air - ans - 1)
else:
    print(-1)

Solution (Python):
H, W = map(int, input().split())
field = []
for i in range(0, H):
	field.append(input())
countwhite = 0
for i in range(0, H):
	for j in range(0, W):
		if field[i][j] == '.':
			countwhite += 1
minfield = []
for i in range(0, H):
	lst = []
	for j in range(0, W):
		lst.append(5000000000000000)
	minfield.append(lst)
queue = [[1, [0, 0]]]
while queue != []:
	now = queue.pop(0)
	if now[0] < minfield[now[1][0]][now[1][1]]:
		minfield[now[1][0]][now[1][1]] = now[0]
		for i in range(0, 2):
			nexth = now[1][0] - 1 + 2*i
			if 0 <= nexth and nexth < H:
				if field[nexth][now[1][1]] == '.':
					queue.append([now[0]+1, [nexth, now[1][1]]])
			nextw = now[1][1] - 1 + 2*i
			if 0 <= nextw and nextw < W:
				if field[now[1][0]][nextw] == '.':
					queue.append([now[0]+1, [now[1][0], nextw]])
if minfield[H-1][W-1] == 5000000000000000:
	print(-1)
else:
	print(countwhite-minfield[H-1][W-1])

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

C = 0
for i in range(H):
  for j in range(W):
    if S[i][j] == ".":
      C += 1
    
S[0][0] = 0
for l in range(C-1):
  for i in range(H):
    for j in range(W):
      if S[i][j] == l:     
        for k in [[0,1],[1,0],[-1,0],[0,-1]]:
          if not(0 <= i + k[0] < H):
            continue
          elif not(0 <= j + k[1] < W):
            continue
          elif S[i+k[0]][j+k[1]] != ".":
            continue
          else:
            S[i+k[0]][j+k[1]] = S[i][j]+1
        
if S[H-1][W-1] == ".":
  print(-1)
  exit()
  
ans = C - S[H-1][W-1] -1
print(ans)

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 and nx < h and 0 <= ny and ny < w and\
                    maze[nx][ny] != "
                que.append((nx, ny))
                d[nx][ny] = d[p[0]][p[1]] + 1

    return d[gx][gy]


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


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

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

Solution (Python):
from collections import deque

H, W = map(int, input().split())
maze = [input() for _ in range(H)]
visited = [[0] * W for _ in range(H)]

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

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

flag = False
while len(que):
    px, py = que.popleft()
    dx = [1, 0, -1, 0]
    dy = [0, 1, 0, -1]
    for i, j in zip(dx, dy):
        nx = px + i
        ny = py + j
        if nx < 0 or ny < 0 or nx >= W or ny >= H:
            continue
        if maze[ny][nx] == '
            continue
        if visited[ny][nx]:
            continue
            
        visited[ny][nx] = visited[py][px] + 1
        que.append([nx, ny])
        
        if nx == W-1 and ny == H-1:
            cnt = visited[ny][nx] + 1
            flag = True
            break
    if flag:
        break

if flag:
    print(H*W - black - cnt)
else:
    print(-1)

Solution (Python):
def main():
	H, W = map(int,input().split())
	pos = [""]*H
	for i in range(H):
		pos[i] = input()

	offset = [[-1, 0], [1, 0], [0, -1], [0, 1]]
	def bfs(s, h, w):
		queue = [[0, 0, 0]]
		is_visited = [[False for _ in range(w)] for _ in range(h)]
		is_visited[0][0] = True
		while queue:
			cur = queue.pop(0)
			for o in offset:
				y, x = cur[0]+o[0], cur[1]+o[1]
				if x < 0 or x >= w or y < 0 or y >= h:
					continue
				if x == w-1 and y == h-1:
					return cur[2]+1
				if is_visited[y][x]:
					continue
				if s[y][x] == ".":
					queue.append([y, x, cur[2]+1])
					is_visited[y][x] = True
		return -1

	white_num = 0
	for i in range(H):
		for j in range(W):
			if pos[i][j] == ".":
				white_num += 1
	route = bfs(pos, H, W)
	if route == -1:
		print(-1)
	else:
		print(white_num-route-1)

if __name__ == '__main__':
    main()

Solution (Python):
import bisect
import heapq
import itertools
import math
import os
import re
import string
import sys
from collections import Counter, deque, defaultdict
from copy import deepcopy
from decimal import Decimal
from fractions import gcd
from functools import lru_cache, reduce
from operator import itemgetter

import numpy as np

if os.getenv("LOCAL"):
    sys.stdin = open("_in.txt", "r")

sys.setrecursionlimit(2147483647)
INF = float("inf")
IINF = 10 ** 18
MOD = 10 ** 9 + 7

H, W = list(map(int, sys.stdin.readline().split()))
S = [list(sys.stdin.readline().rstrip()) for _ in range(H)]


def ok(h, w):
    return 0 <= h < H and 0 <= w < W and S[h][w] == '.'


dot_count = 0
for r in S:
    dot_count += r.count('.')


sh = sw = 0
que = deque()
que.append((sh, sw, 0))
delta = list(zip(*[[0, 0, 1, -1], [1, -1, 0, 0]]))
distance = -1
while que:
    h, w, d = que.popleft()
    if h == H - 1 and w == W - 1:
        distance = d
        break
    for dh, dw in delta:
        if ok(h + dh, w + dw):
            S[h + dh][w + dw] = '
            que.append((h + dh, w + dw, d + 1))

if distance > 0:
    print(dot_count - distance - 1)
else:
    print(-1)

Solution (Python):
import sys
input = sys.stdin.readline
from collections import deque
H, W = map(int, input().split())
X = [1,0,-1,0]
Y = [0,-1,0,1]
num = 0
D = []
for i in range(H):
  s = list(input())
  num += s.count(".")
  D.append(s)
Q = deque()
Q.append((0,0))
dist = [[-1]*W for i in range(H)]
dist[0][0] = 0

while Q:
  y,x = Q.popleft()
  for i in range(4):
    nx = x + X[i]
    ny = y + Y[i]
    if 0 <= nx < W and 0 <= ny < H and dist[ny][nx] == -1 and D[ny][nx] == ".":
      dist[ny][nx] = dist[y][x] + 1
      Q.append((ny,nx))

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

Solution (Python):
from collections import deque
H,W = map(int,input().split())
S = [list(input()) for i in range(H)]
went = [[False]*W for i in range(H)]
queue = deque()
queue.append((0,0,0))
went[0][0] = True
dist = -1
while queue:
    curh,curw,curturn = queue.popleft()
    if curh==H-1 and curw == W-1:
        dist = curturn
        break
    for dx,dy in ((1,0),(0,1),(-1,0),(0,-1)):
        newh,neww = curh+dx,curw+dy
        if 0<=newh<H and 0<=neww<W and not went[newh][neww]\
        and S[newh][neww]==".":
            went[newh][neww] = True
            queue.append((newh,neww,curturn+1))

white = sum([s.count(".") for s in S])
if dist == -1:print(-1)
else:print(white - dist - 1)

Solution (Python):
H, W = map(int, input().split())
INF = 10**9
maze = []
for i in range(H):
    maze.append(input())

dist = [[INF for j in range(W)] for i in range(H)]

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

dirc = [[0, 1], [1, 0], [0, -1], [-1, 0]]

togo = []
togo.append([sy, sx])
dist[sy][sx] = 0
def bfs():
    while len(togo) > 0:
        y, x = togo.pop(0)
        if y == gy and x == gx:
            break
        for dy, dx in dirc:
            ny = y + dy
            nx = x + dx
            if 0 <= ny < H and 0 <= nx < W and maze[ny][nx] == '.' and dist[ny][nx] == INF:
                togo.append([ny, nx])
                dist[ny][nx] = dist[y][x] + 1
    
    return dist[gy][gx]

ret = bfs()

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

if ret == INF:
    print(-1)
else:
    res = cnt-ret-1
    print(res)

Solution (Python):
from collections import deque
H, W = map(int, input().split())
S = [input() for i in range(H)]
C = sum(s.count('.') for s in S)

dd = ((-1, 0), (0, -1), (1, 0), (0, 1))
que = deque([(0, 0, 0)])
used = {(0, 0)}

res = None
while que:
    s, t, cost = que.popleft()
    if s == H-1 and t == W-1:
        res = cost
        break
    for di, dj in dd:
        ni = s + di; nj = t + dj
        if (not 0 <= ni < H) or (not 0 <= nj < W) or S[ni][nj] == '
            continue
        used.add((ni, nj))
        que.append((ni, nj, cost + 1))
if res:
    print(C - 1 - res)
else:
    print(-1)

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

sy,sx = 0,0

gy,gx = H-1,W-1

INF = 1000000

nulcnt = -2


for y in range(H):
    for x in range(W):
        if C[y][x] == '.':
            nulcnt += 1
            C[y][x] = INF

def bfs(C,sy,sx,gy,gx):
    
    que = deque([[sy,sx]])
    C[sy][sx] = 0

    while que:
        y,x = que.popleft()
        if [y,x] == [gy,gx]:
            
            return C[gy][gx]
        for dy,dx in [[1,0],[0,1],[-1,0],[0,-1]]:
            ny = y + dy
            nx = x + dx
            if (0 <= ny < H) and (0 <= nx < W):
                if C[ny][nx] != '
                    que.append([ny,nx])
                    C[ny][nx] = C[y][x] + 1
    
    return -1

saitan = bfs(C,sy,sx,gy,gx)

if saitan != -1:
    print(nulcnt - saitan + 1)
else:
    print(-1)

Solution (Python):
from collections import deque

H,W = map(int, input().split())
board = [["
for i in range(H):
    board.append(["
board.append(["
board[H][W] = "g" 


cntsharp = 0
for i in range(1,H+1):
    for j in range(1,W+1):
        if board[i][j] == "
            cntsharp += 1


seen = [[-1] * (W+2) for i in range(H+2)]
seen[1][1] = 0 
q = deque([[1,1,1]]) 
mvs = [(1,0),(-1,0),(0,1),(0,-1)]

while len(q) > 0:
    h,w,p = q.popleft()
    for dh,dw in mvs: 
        next_h = h + dh
        next_w = w + dw
        next_p = p + 1
        if seen[next_h][next_w] == -1 and board[next_h][next_w] != "
            seen[next_h][next_w] = next_p
            q.append([next_h,next_w,next_p])
            
if seen[H][W] == -1:
    print(-1)
else:
    print(H*W-cntsharp-seen[H][W])

Solution (Python):
h,w=map(int,input().split())
s=[]
for i in range(h):
    s.append(input())
from collections import deque
dp=[[-1]*w for i in range(h)]
d=[[1,0],[0,1],[-1,0],[0,-1]]
que=deque([])
que.append((0,0))
dp[0][0]=1
while len(que)>0:
    now=que.popleft()
    for i in d:
        if 0<=now[0]+i[0]<=h-1 and 0<=now[1]+i[1]<=w-1:
            x=now[0]+i[0]
            y=now[1]+i[1]
            if dp[x][y]==-1 and s[x][y]=='.':
                que.append((x,y))
                dp[x][y]=dp[now[0]][now[1]]+1
if dp[h-1][w-1]==-1:
    print(-1)
else:
    count=0
    for i in range(h):
        for j in range(w):
            if s[i][j]=='.':
                    count=count+1
    print(count-dp[h-1][w-1])

Solution (Python):
from collections import deque

h,w=map(int,input().split())
sx,sy=1,1
gx,gy=h,w
w+=2

grh=[list('
res=0
for i in range(h):
    tmp=input()
    res+=tmp.count('.')    
    grh+=[list('
grh+=[list('
h+=2


def bfs():
    que=deque()
    g=[[float('inf')]*w for i in range(h)]
    g[sx][sy]=1
    xy=[(-1,0),(0,-1),(0,1),(1,0)]
    que.append((sx,sy))

    while que:
        x,y=que.popleft()
        if x==gx and y==gy:break
        
        for dx,dy in xy:
            nx=x+dx
            ny=y+dy
            if grh[nx][ny]=='.' and g[nx][ny]==float('inf'):
                que.append((nx,ny))
                g[nx][ny]=g[x][y]+1

    return g[gx][gy]


res-=bfs()
print(-1 if res==float('-inf') else res)

Solution (Python):

from collections import defaultdict
from collections import deque
from heapq import heappush, heappop
import sys
import math
import bisect
import random
def LI(): return list(map(int, sys.stdin.readline().split()))
def I(): return int(sys.stdin.readline())
def LS():return list(map(list, sys.stdin.readline().split()))
def S(): return list(sys.stdin.readline())[:-1]
def IR(n):
    l = [None for i in range(n)]
    for i in range(n):l[i] = I()
    return l
def LIR(n):
    l = [None for i in range(n)]
    for i in range(n):l[i] = LI()
    return l
def SR(n):
    l = [None for i in range(n)]
    for i in range(n):l[i] = S()
    return l
def LSR(n):
    l = [None for i in range(n)]
    for i in range(n):l[i] = LS()
    return l
sys.setrecursionlimit(1000000)
mod = 1000000007

H, W = LI()
c = SR(H)
sy, sx = 0, 0
gy, gx = H-1, W-1

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

def bfs(sy, sx, gy, gx, c, road=".", blocks=["
    H = len(c)
    W = len(c[0])
    dire = [(1,0), (0,1), (-1,0), (0,-1)]
    dist = [[107]*W for i in range(H)]
    dist[sy][sx] = 0

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

    while q:
        y, x = q.popleft()
        for dy, dx in dire:
            if (y+dy<H) and (y+dy>=0) and (x+dx<W) and (x+dx>=0):
                if (c[y+dy][x+dx] in blocks):
                    continue
                else:
                    if (y+dy==gy) and (x+dx==gx):
                        return (dist[y][x]+1)
                    elif (dist[y+dy][x+dx] > dist[y][x]+1):
                        dist[y+dy][x+dx] = dist[y][x]+1
                        q.append((y+dy, x+dx))
    return -1

path = bfs(sy, sx, gy, gx, c)
print(white_counts-path-1 if (path!=-1) else -1)

Solution (Python):
from sys import stdin
input = [int(x) for x in stdin.readline().rstrip().split()]
H=input[0]
W=input[1]
start=[0,0]
goal=[H-1,W-1]
road=[]
wall_len=0
for h in range(H):
    road.append(list(stdin.readline().rstrip().split()[0]))
    wall_len+=len([x for x in road[h] if x == "

def bfs(H,W,start,goal,road):
    road_dist=[[float("inf") for w in range(W)] for h in range(H)]
    queue_list=[start]
    already_list=[]
    road_dist[start[0]][start[1]]=0
    move_list=[[0,1],[0,-1],[1,0],[-1,0]]
    while len(queue_list)>0:
        now_position=queue_list.pop(0)
        already_list.append(now_position)
        now_dist=road_dist[now_position[0]][now_position[1]]
        if now_position == goal:
            break
        next_list=[]
        for dy, dx in move_list:
            next_y=now_position[0]+dy
            next_x=now_position[1]+dx
            if (0<=next_x<W) & (0<=next_y<H):
                if (road[next_y][next_x]!="
                    next_list.append([next_y,next_x])
        for p in next_list:
            if p in queue_list:
                continue
            if p in already_list:
                continue
            queue_list.append(p)
            road_dist[p[0]][p[1]]=now_dist+1

    return road_dist

rd=bfs(H,W,start,goal,road)
if rd[goal[0]][goal[1]] == float("inf"):
    output=-1
else:
    output=H*W-(rd[goal[0]][goal[1]]+1+wall_len)

print(output)

Solution (Python):
from collections import deque

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

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

dist = [[-1 for i in range(W)] for j in range(H)]
dx = [1, 0, -1, 0]
dy = [0, 1, 0, -1]

def bfs():
    q = deque()
    q.append([0, 0])
    dist[0][0] = 1
    while q:
        p = q.popleft()
        if p[0] == H-1 and p[1] == W-1:
            break
        for i in range(4):
            nx = p[0] + dx[i]
            ny = p[1] + dy[i]
            if 0 <= nx and nx < H and 0 <= ny and ny < W:
                if s[nx][ny] != '
                    q.append([nx, ny])
                    dist[nx][ny] = dist[p[0]][p[1]] + 1
    return dist[H-1][W-1]

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

Solution (Python):
from queue import Queue

H, W = map(int, input().split())
N = H * W
field = []

dxy_list = [(-1, 0), (0, 1), (1, 0), (0, -1)]

INF = 10000
cost = [[INF] * W for _ in range(H)]

for _ in range(H):
    field.append(list(input()))

n_black = 0
for r in field:
    for c in r:
        if c == '
            n_black += 1

que = Queue()
que.put((0,0))
cost[0][0] = 1

while not que.empty():
    x, y = que.get()

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

    for dxy in dxy_list:
        nx = x + dxy[0]
        ny = y + dxy[1]

        if 0 <= nx < H and 0 <= ny < W and field[nx][ny] != '
            que.put((nx, ny))
            cost[nx][ny] = cost[x][y] + 1    

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

print(N - n_black - cost[H-1][W-1])

Solution (Python):
h,w=map(int,input().split())
l=[[1]*(w+2)]+[[1]+[1 if i=="
c=[[0]*(w+2) for i in range(h+2)]
q=[(1,1)]
e=[(0,1),(0,-1),(1,0),(-1,0)]
kyori=1
while len(q)>0 and c[h][w]==0:
    tl=q
    q=[]
    for x,y in tl:
        for X,Y in e:
            if(l[y+Y][x+X]==0 and c[y+Y][x+X]==0):
                q.append((x+X,y+Y))
                c[y+Y][x+X]=1
    kyori+=1
if  c[h][w]==0:
    print(-1)
else:
    print(sum([i.count(0) for i in l])-kyori)

Solution (Python):
H,W = map(int,input().split())
Grid = [[1 if g == "." else 0 for g in input()] for _ in range(H)]
dp = [[10**5]*(W) for _ in range(H)]
dp[0][0] = 0
black = 0
flag = Grid[0][0]

for g in Grid:
    for gg in g:
        if not(gg):
            black += 1

a = [-1,1]

import sys
sys.setrecursionlimit(10**4)
def bfs(grid,h,w,Q):
    if h == H - 1 and w == W - 1:
        return dp[h][w]
    for aa in a:
        if 0 <= h + aa <= H -1:
            if grid[h+aa][w]:
                grid[h+aa][w] = 0
                dp[h+aa][w] = dp[h][w] + 1
                Q.append([h+aa,w])
        if 0 <= w + aa <= W - 1:
            if grid[h][w+aa]:
                grid[h][w+aa] = 0
                dp[h][w+aa] = dp[h][w] + 1
                Q.append([h,w + aa])
    if len(Q) == 0:
        return -1
    else:
        nexth,nextw = Q.pop(0)
        return bfs(grid,nexth,nextw,Q)
queue = []
Grid[0][0] = 0
if  flag:
    ans = bfs(Grid,0,0,queue)
    if ans == -1:
        print(-1)
    else:
        print(H*W - ans - 1 - black)
else:
    print(-1)

Solution (Python):
directions = [(1, 0), (0, 1), (-1, 0), (0, -1)]
 
 
def main():
    H, W = map(int, input().split())
    s = [input() for _ in range(H)]
    path = [[float("inf")] * W for _ in range(H)]
    white = sum([len(row.replace("
    scan = [(0, 0, 1)]  
    while len(scan):
        i, j, cost = scan.pop(0)
        if cost >= path[i][j]:
            continue
        path[i][j] = cost
        for d in directions:
            nexti = i + d[0]
            nextj = j + d[1]
            if 0 <= nexti and nexti < H and \
               0 <= nextj and nextj < W and \
               s[nexti][nextj] == ".":
                scan.append((nexti, nextj, cost + 1))
    if path[H-1][W-1] == float("inf"):
        print(-1)
    else:
        print(white - path[H-1][W-1])
 
 
if __name__ == "__main__":
    main()

Solution (Python):
from collections import deque
import sys

H,W  = map(int, input().split())
sx, sy = 1,1
gx, gy = W,H
count=-1
maze=[0]*(H+2)
maze[0] = list("
for i in range(1,H+1):
    maze[i] = list("
    count+=maze[i].count('.')
maze[H+1] = list("
ans = [[-1 for i in range(W+2)] for j in range(H+2)]
q = deque()
dx = [1, 0, -1, 0]
dy = [0, 1, 0, -1]
q.append((sx, sy))
ans[sx][sy] = 0
 
while q:
    cx, cy = q.popleft()
    if cx == gx and cy == gy:
        print(count-ans[gy][gx])
        sys.exit()
    for i in range(4):
        nx, ny = cx + dx[i], cy + dy[i]
        if ans[ny][nx] == -1 and maze[ny][nx] != "
            q.append((nx, ny))
            ans[ny][nx] = ans[cy][cx] + 1
print(-1)

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

def pixel_input(H,W,border="
    pixel = \
    [[border]*(W+2)] + \
    [[border] + list(input()) + [border] for _ in range(H)] + \
    [[border]*(W+2)]
    return pixel
p=pixel_input(H,W)
s=sum([p[i].count("

que=[(1,1)]
cnt=1

while(1):
    que2=[]
    for x,y in que:
        if p[x-1][y]==".":
            que2.append((x-1,y))
            p[x-1][y]="
        if p[x+1][y]==".":
            que2.append((x+1,y))
            p[x+1][y]="
        if p[x][y-1]==".":
            que2.append((x,y-1))
            p[x][y-1]="
        if p[x][y+1]==".":
            que2.append((x,y+1))
            p[x][y+1]="
    cnt+=1
    if (H,W) in que2:
        break
    elif que2==[]:
        cnt=-1
        break
    else:
        que=que2

if cnt>=0:
    print(H*W-s-cnt)
else:
    print(-1)

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


def bfs(h, w):  
    for i in dhw:
        dh = i[0]
        dw = i[1]
        if h+dh < 0 or h+dh > H-1 or w+dw < 0 or w+dw > W-1 or field[h+dh][w+dw] == '
            continue
        if seen[h+dh][w+dw] == -1:
            seen[h+dh][w+dw] = seen[h][w] + 1
            todo.append([h+dh, w+dw])
        
        
H, W = map(int, input().split())
field = [list(input()) for _ in range(H)]
black_origin = 0
for i in range(H):
    black_origin += field[i].count('
dhw = ((-1, 0), (1, 0), (0, -1), (0, 1))
seen = [[-1]*W for _ in range(H)]
todo = deque()
seen[0][0] = 0
todo.append([0, 0])

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

if seen[H-1][W-1] == -1:
    print(-1)
else:
    print(H*W-(seen[H-1][W-1]+1)-black_origin)

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

map_list = []
black = 0
for i in range(H):
    map_list.append(input())
    black += map_list[i].count('

queue = [(0,0)]
check = [(0,0)]
C = [0,0]
count = 0
hNow,wNow = 0,0

while 1:
    count += 1
    if len(queue) != 0:
        if queue[0] == (H-1,W-1):
            print(H*W - black -1 - max(C))
            break 
    if len(queue) == 0:
        print(-1)
        break
    hNow,wNow = queue[0][0],queue[0][1]
    queue.pop(0)
    if hNow < H-1:
        if map_list[hNow+1][wNow] != "
            if (hNow+1,wNow) not in check:
                queue.append((hNow+1,wNow))
                check.append((hNow+1,wNow))
                C.append(C[count]+1)
    if wNow < W-1:
        if map_list[hNow][wNow+1] != "
            if (hNow,wNow+1) not in check:
                queue.append((hNow,wNow+1))
                check.append((hNow,wNow+1))
                C.append(C[count]+1)
    if hNow > 0:
        if map_list[hNow-1][wNow] != "
            if (hNow-1,wNow) not in check:
                queue.append((hNow-1,wNow))
                check.append((hNow-1,wNow))
                C.append(C[count]+1)
    if wNow > 0:
        if map_list[hNow][wNow-1] != "
            if (hNow,wNow-1) not in check:
                queue.append((hNow,wNow-1))
                check.append((hNow,wNow-1)) 
                C.append(C[count]+1)

Solution (Python):
from collections import deque

H, W = map(int, input().split())
S = [["
white = 0
for h in range(H):
    s = ["
    white += s.count(".")
    S.append(s)
S.append(["

S[1][1] = 0
start = (1, 1)
goal = (H, W)
ans = -1
stack = deque()
stack.append(start)
move = [(1, 0), (-1, 0), (0, 1), (0, -1)]
while stack:
    x, y = stack.pop()
    if (x, y) == goal:
        ans = white - S[x][y] - 1
        print(ans)
        exit()
    for dx, dy in move:
        nx, ny = x + dx, y + dy
        if S[nx][ny] != ".":
            continue
        stack.appendleft((nx, ny))
        S[nx][ny] = S[x][y] + 1
print(ans)

Solution (Python):
from collections import deque
H,W = map(int,input().split())
maze = []
point = -1
kabe = 0
for i in range(H):
    maze.append(input())
for i in range(H):
    for k in range(W):
        if maze[i][k] == '
            kabe += 1

def bfs(sy,sx,gy,gx,h,w):
    jikan = 0
    q = deque([sy*w + sx])
    saitan = [1000000]*h*w
    saitan[sy*w + sx] = 0
    dx = [1,-1,0,0]
    dy = [0,0,1,-1]
    while len(q)>0 and saitan[gy*w +gx] == 1000000:
        j = q.popleft()
        y = int(j/w)
        x = j%w
        
        for k in range(4):
            my = y + dy[k]
            mx = x + dx[k]
            
            if not((0 <=my <= h-1) and (0 <= mx <= w-1)):
                
                continue
            if maze[my][mx] == '
                
                continue
            if saitan[(my*w + mx)] <= saitan[y*w + x] + 1:
                
                continue
                
            saitan[(my*w + mx)] = saitan[y*w + x] + 1
            q.append(my*w + mx)
    jikan = saitan[gy*w +gx]
    return jikan

    
    
time = bfs(0,0,H-1,W-1,H,W)

if time == 1000000:
    point = -1
else:
    point = point + 1 +(H * W - time - kabe-1)
print(point)

Solution (Python):
import collections

h,w=map(int,input().split())
checked=[[0]*(w+2) for _ in range(h+2)]
board=[['
for _ in range(h):
  board.append(['
board.append(['
q=collections.deque()
q.append((1,1,1))
checked[1][1]=1
ans=-1
while 1:
  if len(q)==0:
    break
  x,y,t=q.popleft()
  if x==w and y==h:
    ans=t
    break
  if board[y][x-1]=='.' and checked[y][x-1]==0:
    checked[y][x-1]=1
    q.append((x-1,y,t+1))
  if board[y][x+1]=='.' and checked[y][x+1]==0:
    checked[y][x+1]=1
    q.append((x+1,y,t+1))
  if board[y-1][x]=='.' and checked[y-1][x]==0:
    checked[y-1][x]=1
    q.append((x,y-1,t+1))
  if board[y+1][x]=='.' and checked[y+1][x]==0:
    checked[y+1][x]=1
    q.append((x,y+1,t+1))
if ans==-1:
  print(-1)
else:
  cnt=0
  for i in range(1,h+1):
    cnt+=board[i].count('
  print(h*w-cnt-ans)

Solution (Python):
from collections import deque

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

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

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

visited = [[float('inf')] * W for i in range(H)]

def bfs():
    queue = deque([[0,0]])
    visited[0][0] = 1

    while queue:
        y,x = queue.popleft()

        if y == H - 1 and x == W - 1:
            return visited[y][x]
        
        for i in range(4):
            nx = x + dy[i]
            ny = y + dx[i]

            if 0 <= nx < W and 0 <= ny < H and s[ny][nx] != '
                queue.append([ny,nx])
                visited[ny][nx] = visited[y][x] + 1
    
    return -1

num = bfs()

if num == -1:
    print(num)
else:
    print(cnt - num)

Solution (Python):
H, W = map(int, input().split())
grid = []
for i in range(H):
    grid.append(input())

visit = [[False for j in range(W)] for i in range(H)]


queue = [[0,0]]
count = 0
while len(queue) > 0:
    count += 1
    next = []
    for now in queue:
        visit[now[0]][now[1]] = True
        for i, j in [[0,-1], [1,0], [0,1], [-1,0]]:
            if 0 <= now[0]+i <= H-1 and 0 <= now[1]+j <= W-1:
                if [now[0]+i,now[1]+j] not in next and not visit[now[0]+i][now[1]+j] and grid[now[0]+i][now[1]+j] == ".":
                    next.append([now[0]+i, now[1]+j])

    if visit[-1][-1]:
        break
    queue = next[:]


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

if visit[-1][-1]:
    print(H*W-black)
else:
    print(-1)

Solution (Python):
from collections import deque

def bfs(grid, sy, sx, target, wall):
    grid[sy][sx] = wall
    queue = deque([])
    queue.append([sy, sx, 0])
    dxy = [(1,0), (-1,0), (0,1), (0,-1)]
    while queue:
        y,x,cnt = queue.popleft()
        for dy, dx in dxy:
            y_,x_ = y+dy,x+dx
            if [y_, x_] == target:
                return cnt+1
            if grid[y_][x_] == wall:
                continue
            queue.append([y_,x_,cnt+1])
            grid[y_][x_] = wall
    return -1

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

edges = ['
grid = [edges]
white = 0
for i in range(H):
    s = input()
    grid.append(['
    for j in range(W):
        grid[i+1].append(s[j])
        white += 1 if s[j] == '.' else 0
    grid[i+1].append('
grid.append(edges)

ans = bfs(grid, 1, 1, [H,W], '

if ans == -1:
    print(ans)
else:
    print(white - ans - 1)