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):
import sys
input = sys.stdin.readline
from collections import deque

move = [(1, 0), (-1, 0), (0, 1), (0, -1)]     
visit = set()                                 
next_set = deque()                            

def debug(p, t):
    player = p
    debug_grid = list(list(grid[h]) for h in range(H))
    debug_grid[start[0]][start[1]] = "S"
    debug_grid[goal[0]][goal[1]] = "G"
    debug_grid[player[0]][player[1]] = "P"
    print("~~~~~~~~~ t = " + str(t+1) + "  ~~~~~~~~")
    for debug_h in range(H):
        print("".join(debug_grid[debug_h][debug_w] for debug_w in range(W)))

def search(start=(0,0), goal=(None,None)):      
    visit.add(start)                            
    next_set.append((start, 0))                 
    while next_set:                             
        p, t = next_set.popleft()               
        h, w = p
        for dh, dw in move:                     
            q = (h + dh, w + dw)
            if q[0] < 0 or q[0] >= H or q[1] < 0 or q[1] >= W:
                continue
            if grid[q[0]][q[1]] == "
                continue
            if q in visit:                      
                continue
            
            
            
            if q == goal:                       
                return t + 1                    
            visit.add(q)                        
            next_set.append((q, t + 1))         
    return -1


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

grid = []
cnt = 0

for h in range(H):
    grid.append(input())
    cnt += grid[-1].count(".")
start = (0,0)
goal = (H-1, W-1)
res = search(start,goal)
if res == -1:
    print(-1)
else:
    print(cnt - res - 1)

Solution (Python):
import sys
from collections import deque

sys.setrecursionlimit(10 ** 7)
f_inf = float('inf')
mod = 10 ** 9 + 7


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

    maze = [[f_inf] * W for _ in range(H)]
    maze[0][0] = 0
    que = deque([[0, 0]])
    while que:
        h, w = que.popleft()
        for dh, dw in [(1, 0), (-1, 0), (0, 1), (0, -1)]:
            next_h, next_w = h + dh, w + dw
            if next_h < 0 or next_h >= H or next_w < 0 or next_w >= W or grid[next_h][next_w] == "
                continue
            if maze[next_h][next_w] > maze[h][w] + 1:
                maze[next_h][next_w] = maze[h][w] + 1
                que.append([next_h, next_w])

    if maze[H - 1][W - 1] == f_inf:
        print(-1)
        exit()

    mi = maze[H - 1][W - 1] + 1

    cnt = 0
    for h in range(H):
        for w in range(W):
            if grid[h][w] == "
                cnt += 1
    res = H * W - cnt - mi
    print(res)


if __name__ == '__main__':
    resolve()

Solution (Python):

from collections import deque
H, W = map(int, input().split())
s = [list(input()) for _ in range(H)]
moves = ((1, 0), (0, 1), (0, -1), (-1, 0))

def bfs(sy, sx):
    q = deque([[sy, sx]])
    dist = [[float('inf')]*(W) for _ in range(H)]
    dist[sy][sx] = 0

    while q:
        y, x = q.popleft()
        for dy, dx in moves:
            ny = y + dy
            nx = x + dx
            if 0 <= ny < H and 0 <= nx < W and s[ny][nx] == '.' and dist[ny][nx] == float('inf'):
                dist[ny][nx] = dist[y][x] + 1
                q += [[ny, nx]]

    return dist

d = bfs(0, 0)

if d[-1][-1] == float('inf'):
    print(-1)
    exit()

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

ans -= d[-1][-1] + 1
print(ans)

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


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

  white = 0
  black = 0
  for i in range(H):
    for j in range(W):
      if M[i][j] == '.':
        white += 1
      elif M[i][j] == '
        black += 1

  start = (0, 0)
  q = deque()
  q.append(start)
  is_visited = [[0]*W for _ in range(H)]
  d = [[float('inf')]*W for _ in range(H)]
  d[0][0] = 0

  while len(q):

    ur, uc = q.popleft()

    for vr, vc in [(ur, uc+1), (ur, uc-1), (ur-1, uc), (ur+1, uc)]:
      if 0 <= vr < H and \
         0 <= vc < W and \
         not(is_visited[vr][vc]) and not(M[vr][vc] == '

        q.append((vr, vc))
        is_visited[vr][vc] = True
        d[vr][vc] = d[ur][uc] + 1

  if d[H-1][W-1] == float('inf'):
    print(-1)
  else:
    print(white - (d[H-1][W-1] + 1))


if(__name__ == '__main__'):
  main()

Solution (Python):
import sys
import math
import itertools
import bisect
from copy import copy
from collections import deque,Counter
from decimal import Decimal
def s(): return input()
def i(): return int(input())
def S(): return input().split()
def I(): return map(int,input().split())
def L(): return list(input().split())
def l(): return list(map(int,input().split()))
def lcm(a,b): return a*b//math.gcd(a,b)
sys.setrecursionlimit(10 ** 9)
mod = 10**9+7

H,W = I()
maze = [list(s()) for _ in  range(H)]
cnt = 0
for i in range(H):
    for j in range(W):
        if maze[i][j] == '
            cnt += 1
dist = [[-1]*W for _ in range(H)]
dist[0][0] = 0
que = deque([[0,0]])
while que:
    h,w = que.pop()
    for dh,dw in [[1,0],[0,1],[-1,0],[0,-1]]:
        nh,nw = h+dh,w+dw
        if nh < 0 or nw < 0 or nh >= H or nw >= W:
            continue
        if maze[nh][nw] == '
            continue
        if dist[nh][nw] == -1:
            dist[nh][nw] = dist[h][w]+1
            que.appendleft([nh,nw])
if dist[H-1][W-1] == -1:
    print(-1)
    exit()
print(H*W-cnt-dist[H-1][W-1]-1)

Solution (Python):
n,m = map(int,input().split())
from collections import deque
a = []
for _ in range(n):
    a.append(list(input()))

count = 0
for x in a:
    count += x.count("


b = [[-1 for i in range(m)] for i in range(n)]


x = [0, 0, -1, 1]
y = [-1, 1, 0, 0]
queue = deque([[0,0]])
b[0][0] = 1
while queue:
    now = queue.popleft()
    if now == [n-1,m-1]:
        print(n * m - (b[n-1][m-1] + count))
        exit()
    a[now[0]][now[1]] = "
    for i in range(4):
        if 0 <= now[0] + y[i] < n and 0 <= now[1] + x[i] < m and b[now[0]+y[i]][now[1]+x[i]] == -1:
            if a[now[0]+y[i]][now[1]+x[i]] == '.':
                queue.append([now[0]+y[i],now[1]+x[i]])
                b[now[0]+y[i]][now[1]+x[i]] = b[now[0]][now[1]] + 1

print(-1)

Solution (Python):
from collections import deque

H, W = 10, 37
ARR = [
    ".....................................",
    "...
    "..
    "..
    ".
    ".
    ".
    ".
    ".
    ".....................................",
]

H, W = map(int, input().split())
ARR = []

for i in range(H):
    ARR.append(input())


def calculate(h, w, arr):
    q = deque()

    q.append((0, 0))

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

    distance = [[0 for i in range(w)] for j in range(h)]
    distance[0][0] = 1
    while q.__len__() > 0:
        y, x = q.popleft()
        for i in range(4):
            my = y + dy[i]
            mx = x + dx[i]
            if (my >= 0) and (mx >= 0) and (my <= (h - 1)) and (mx <= (w - 1)) and (distance[my][mx] == 0) and (
                    arr[my][mx] == "."):
                distance[my][mx] = distance[y][x] + 1
                q.append((my, mx))

    mmk = 0
    for j in range(h):
        mmk += arr[j].count("

    if distance[h - 1][w - 1] == 0:
        print(-1)
    else:
        print(h * w - distance[h - 1][w - 1] - mmk)


calculate(H, W, ARR)

Solution (Python):
from collections import deque
import collections
import math

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

def bfs():
    res=0
    for y in range(h):
        for x in range(w):
            if c[y][x]=='.':
                c[y][x]=math.inf
                res += 1
    c[0][0]=0
    que=deque([[0,0]])
    while que:
        y,x=que.popleft()
        for i,j in [(1,0),(0,1),(-1,0),(0,-1)]:
            ny,nx=y+i,x+j
            if h > ny >= 0 and w > nx >= 0:
                dist=c[ny][nx]
                if dist!='
                    if dist>c[y][x]+1:
                        c[ny][nx]=c[y][x]+1
                        que.append([ny,nx])
            else:
                pass
    if c[h-1][w-1] ==math.inf:
        return (-1)
    else:
        return res - c[h-1][w-1] -1

print (bfs())

Solution (Python):
import sys
from collections import deque


def input():
    return sys.stdin.readline()[:-1]


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

white_cnt = 0
grid = [[] for i in range(H+2)]
check = [[0] * (W+2) for i in range(H+2)]
grid[0] = ['
for i in range(1, H+1):
    w = list(input())
    white_cnt += w.count('.')
    grid[i] = ['
grid[-1] = ['

mv_list = [(1, 0), (-1, 0), (0, 1), (0, -1)]
que_hwc = deque([(1, 1, 1)])
check[1][1] = 1
while que_hwc:
    hwc = que_hwc.popleft()
    h = hwc[0]
    w = hwc[1]
    cnt = hwc[2]
    if h == H and w == W:
        print(white_cnt-cnt)
        exit(0)

    for mv in mv_list:
        mv_h = h + mv[0]
        mv_w = w + mv[1]
        if grid[mv_h][mv_w] == '.' and check[mv_h][mv_w] != 1:
            check[mv_h][mv_w] = 1
            que_hwc.append((mv_h, mv_w, cnt+1))
print(-1)

Solution (Python):
from collections import deque

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

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

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

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

q = deque()
q.append([0, 0, 1])  
dis[0][0] = 1

while len(q) > 0:
    x, y, d = q.popleft()
    dxy = [[0, 1], [0, -1], [1, 0], [-1, 0]]

    for dx, dy in dxy:
        nx = x + dx
        ny = y + dy
        if 0 > nx or w <= nx or 0 > ny or h <= ny:
            continue
        if dis[ny][nx] != -1 or s[ny][nx] == "
            continue
        q.append([nx, ny, d + 1])
        dis[ny][nx] = d + 1

if dis[h - 1][w - 1] == -1:
    print(-1)
else:
    print(white_cnt - dis[h - 1][w - 1])

Solution (Python):
from collections import deque
H, W = map(int, input().split())
field = [list(input()) for i in range(H)]
sx, sy, gx, gy = 0, 0, H-1, W-1
x = [1, 0, -1, 0]
y = [0, 1, 0, -1]
def bfs():
    d = [[float("inf")] * W for _ in range(H)]
    d[sx][sy] = 0
    Q = deque([])
    Q.append((sx, sy))
    while Q:
        px, py = Q.popleft()
        if px==gx and py==gy:
            break
        for dx, dy in zip(x, y):
            nx = px+dx
            ny = py+dy
            if 0<=nx<H and 0<=ny<W and field[nx][ny]=='.' and d[nx][ny]==float('inf'):
                d[nx][ny]=d[px][py]+1
                Q.append((nx, ny))
    return d[gx][gy]

count = 0
for i in field:
    count += i.count('.')
res = bfs()
if 0 < res < float("inf"):
    print(count-res-1)
else:
    print(-1)

Solution (Python):
from collections import deque
H,W = map(int,input().split())
l = [str(input()) for _ in range(H)]
white_count = 0
for s in l:
  white_count += s.count('.')
sy = 0
sx = 0
gy = H-1
gx = W-1
visited = [[-1]*W for _ in range(H)]
visited[sy][sx] = 0
Q = deque([[sy,sx]])
while Q:
  y,x = Q.popleft()
  if [y,x] == [gy,gx]:
    print(white_count - visited[y][x] - 1)
    exit()
  for i,j in [(1,0),(0,1),(-1,0),(0,-1)]:
    if 0 <= x+j < W and 0 <= y+i < H and visited[y+i][x+j] == -1 and l[y+i][x+j] == '.':
      visited[y+i][x+j] = visited[y][x]+1
      Q.append([y+i,x+j])
    else:
      continue
print(-1)

Solution (Python):
from collections import deque


def bfs():
  d = [[float('inf')]* w for i in range(h)]
  
  dx = [1, 0, -1, 0]
  dy = [0, 1, 0, -1]
  
  que = deque([])
  que.append((sx, sy))
  d[sx][sy] = 0
  
  while que:
    p = que.popleft()
    if p[0] == gx and p[1] == gy:
      break
    for i in range(4):
      nx = p[0] + dx[i]
      ny = p[1] + dy[i]
      
      if 0 <= nx < h and 0 <= ny < w and maze[nx][ny] != '
        que.append((nx, ny))
        d[nx][ny] = d[p[0]][p[1]] + 1
        
  return d[gx][gy]
  
  
h, w = map(int, input().split())
maze = [list(input()) for i in range(h)]
sx, sy = 0, 0
gx, gy = h-1, w-1

white = 0
for i in range(h):
  for j in range(w):
    if maze[i][j] == '.':
      white += 1
      
res = bfs()
if 0 < res < float('inf'):
  print(white - res - 1)
else:
  print(-1)

Solution (Python):
from collections import deque

def main():
    R,C= map(int,input().split())

    S = [0,0]

    mv = [[1,0],[-1,0],[0,-1],[0,1]]
    MAP = []
    flg = 0
    block = 0
    for _ in range(R):
        t = list(input())
        block += t.count('
        MAP.append(t)
    stack = deque([S])
    MAP_c = [[None]*C for _ in range(R)]
    MAP_c[0][0] = 1
    while stack:
        v = stack.popleft()
        for m in mv:
            u = [v[0]+m[0],v[1]+m[1]]
            if u[0] >=0 and u[0] < R and u[1] >= 0 and u[1] < C and MAP[u[0]][u[1]] == '.':
                MAP[u[0]][u[1]] = '
                MAP_c[u[0]][u[1]] = MAP_c[v[0]][v[1]] + 1
                stack.append(u)
                if u == [R-1,C-1]:
                    flg = 1

        if flg == 1:
            break

    if flg == 1:
        a = MAP_c[R-1][C-1]
        print(R*C - a - block)
    else:
        print(-1)


main()

Solution (Python):
from collections import deque

h, w = map(int,input().split())
S = [input() for _ in range(h)]
s = deque([(0,0)])  
e = [[-1] * w for _ in range(h)]  
e[0][0] = 0

def main():
    while len(s) > 0:  
        t = s.popleft()
        if is_end(t):  
            break
        for i in get_children(t):  
            if is_legal(i):  
                if e[i[0]][i[1]] != -1:  
                    continue
                s.append(i)
                e[i[0]][i[1]] = e[t[0]][t[1]] + 1 
    cnt = 0
    for x in S:
        cnt += x.count(".")
    end = e[h-1][w-1]
    
    if end == -1:
        print(-1)
    else:
        print((cnt-2)-(end-1))
    
def printing():
    for i in range(len(e)):
        for j in range(len(e[i])):
            if e[i][j] == -1:
                print(S[i][j], end="")
            else:
                print(e[i][j], end="")
        print("")
    
def is_end(t):
    return t[0] == h-1 and t[1] == w-1

def get_children(t):
    return ((t[0]-1,t[1]),(t[0]+1,t[1]),(t[0],t[1]-1),(t[0],t[1]+1))

def is_legal(i):
    return -1 < i[0] < h and -1 < i[1] < w and S[i[0]][i[1]] == "."

if __name__ == "__main__":
    main()

Solution (Python):
from collections import deque
h, w = map(int, input().split())
map = [list(input()) for i in range(h)]
def bfs():
    d = [[float("inf")] * w for i in range(h)]
    sx = 0
    sy = 0
    dx = [0, -1, 0, 1]
    dy = [1, 0, -1, 0]
    d[sx][sy] = 0
    que = deque([])
    que.append((sx, sy))
    while que:
        p = que.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 < h and 0 <= ny < w and map[nx][ny] != "
            and d[nx][ny] == float("inf"):
                que.append((nx, ny))
                d[nx][ny] = d[p[0]][p[1]] + 1
    return d[h-1][w-1]
count = 0
for i in range(h):
    for j in range(w):
        if map[i][j] == '
            count += 1
short = bfs()
if short == float("inf"):
    ans = -1
else:
    ans = h * w - count - short - 1
print(ans)

Solution (Python):
from collections import deque

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

G = []
black = 0
for i in range(H):
    line = list(input())
    G.append(line)
    black += line.count("
    
ls = deque([[0, 0, 0]])
D = [[float("inf")] * W for i in range(H)]
direction = [[1,0], [-1,0], [0,1], [0,-1]]
find = False
while len(ls) > 0:
    h, w, depth = ls.popleft()
    
    if h == H-1 and w == W-1:
        route = depth + 1
        find = True
        break
        
    for dh, dw in direction:
        if h + dh < 0 or H-1 < h + dh: continue
        if w + dw < 0 or W-1 < w + dw: continue
        if depth + 1 < D[h+dh][w+dw] and G[h+dh][w+dw] != "
            ls.append([h+dh, w+dw, depth+1])
            D[h+dh][w+dw] = depth + 1
            
if find:
    ans = (H * W) - black - route
    print(ans)
else:
    print(-1)

Solution (Python):
from collections import deque
H,W = map(int, input().split())
L=[]
kuro=0
siro=0

for i in range(H):
    a=list(input())
    L.append(a)
    for i in a:
        if i=='
            kuro+=1
        else:
            siro+=1


q=deque([[1,1]])
move=[[1,0],[-1,0],[0,1],[0,-1]]
num=0
s=False
while q:
    
    for i in range(len(q)):
        b=q.popleft()
        
        if b==[H,W]:
            s=True
        
            print(H*W-kuro-num-1)
            break
        for m in move:
         
            if 1<=b[0]+m[0]<=H and 1<=b[1]+m[1]<=W and L[b[0]+m[0]-1][b[1]+m[1]-1]=='.':
                L[b[0]+m[0]-1][b[1]-1+m[1]]='
                q.append([b[0]+m[0],b[1]+m[1]])
        
    num+=1


if not s:
    print('-1')

Solution (Python):
from collections import deque
H, W = map(int, input().split())
area = [['
space = 0
for i in range(H):
    temp = ['
    for t in temp:
        if t=='.': space+=1 
    area.append(temp)
area.append(['
move = ((1, 0), (-1, 0), (0, 1), (0, -1))
    
dq = deque([(1,1)])
dist = [[-1]*(W+2) for _ in range(H+2)]
dist[1][1] = 1
    
while dq:
    nowx, nowy = dq.popleft()
    if (nowx, nowy) == (W, H): break
    for dx, dy in move:
        nxtx, nxty = nowx+dx, nowy+dy
        if not 0<=nxtx<W+2 and 0<=nxty<H+2: continue
        if dist[nxty][nxtx]>=0 or area[nxty][nxtx]=='
        dist[nxty][nxtx] = dist[nowy][nowx]+1
        dq.append((nxtx, nxty))
if dist[H][W]==-1: print(-1)
else: print(space-dist[H][W])

Solution (Python):
from collections import deque
import sys


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

M = []
w_count = 0
for i in range(H):
    s = input()
    w_count += s.count('.')
    M.append(s)

visited = [[False for _ in range(W)] for _ in range(H)]

q = deque([[0, 0, 1]])
while len(q) != 0:
    p = q.popleft()
    x = p[0]
    y = p[1]
    count = p[2]
    if x == W - 1 and y == H - 1:
        print(w_count - count)
        sys.exit(0)
    cands = []
    if x - 1 >= 0:
        cands.append([x-1, y])
    if x + 1 < W:
        cands.append([x+1, y])
    if y - 1 >= 0:
        cands.append([x, y-1])
    if y + 1 < H:
        cands.append([x, y+1])
    for cx, cy in cands:
        if M[cy][cx] == '.' and not visited[cy][cx]:
            q.append([cx, cy, count+1])
            visited[cy][cx] = True
print(-1)

Solution (Python):
import queue
INF=10**8
r,c=map(int,input().split())


maze=[input() for _ in range(r)]
d=[[INF for i in range(r)] for _ in range(c)]
sx,sy=1,1
gx,gy=r,c
cnt=0
for i in range(r):
  for j in range(c):
    if maze[i][j]=='.':
      cnt+=1

sx-=1
sy-=1
gx-=1
gy-=1
q=queue.Queue()
dx=[-1,0,1,0]
dy=[0,-1,0,1]
q.put((sx,sy))
d[sy][sx]=0

while not q.empty():
  x,y=q.get()
  if (x,y)==(gx,gy):break
  for i in range(4):
    nx=x+dx[i]
    ny=y+dy[i]
    if 0<=nx<c and 0<=ny<r:
      if maze[ny][nx]=='.' and d[nx][ny]==INF:
        q.put((nx,ny))
        d[nx][ny]=d[x][y]+1
if d[gy][gx]==INF:
  print(-1)
else:print(cnt-d[gy][gx]-1)

Solution (Python):
from collections import deque

def solve():
    if s[0][0] == '
        print(-1)
        return

    stack = deque()
    stack.append([0, 0, 0])
    used = [[False for _ in range(W)] for _ in range(H)]
    costs = [[float('inf') for _ in range(W)] for _ in range(H)]
    while stack:
        i, j, cost = stack.popleft()
        costs[i][j] = cost
        for x, y in [(i + 1, j), (i - 1, j), (i, j + 1), (i, j - 1)]:
            if not 0 <= x < H or not 0 <= y < W or used[x][y] or s[x][y] == '
                continue
            stack.append([x, y, cost + 1])
            used[x][y] = True

    print(dot_num - 1 - costs[H - 1][W - 1] if costs[H - 1][W - 1] != float('inf') else -1)

if __name__ == "__main__":
    H, W = map(int, input().split())
    s = []
    dot_num = 0
    for _ in range(H):
        tmp = list(input())
        dot_num += tmp.count('.')
        s.append(tmp)
    solve()

Solution (Python):
import sys

readline = sys.stdin.readline
MOD = 10 ** 9 + 7
INF = float('INF')
sys.setrecursionlimit(10 ** 5)

from collections import deque


def initialize_maze(h, w):
    grid = [["."] * (w + 2) for _ in range(h + 2)]

    for row in range(h + 2):
        grid[row][0] = "
        grid[row][w + 1] = "

    for col in range(w + 2):
        grid[0][col] = "
        grid[h + 1][col] = "

    return grid


def main():
    def bfs():
        que = deque()
        que.append((1, 1, 0))

        while que:
            row, col, count = que.popleft()
            for mr, mc in ((1, 0), (0, 1), (-1, 0), (0, -1)):
                nr, nc = row + mr, col + mc
                if grid[nr][nc] == ".":
                    que.append((nr, nc, count + 1))
                    grid[nr][nc] = "!"
                elif grid[nr][nc] == "G":
                    min_count = count + 1
                    return min_count
        return - 1

    h, w = map(int, readline().split())
    grid = initialize_maze(h, w)

    black_num = 0
    for row in range(1, h + 1):
        s = input()
        for col, state in enumerate(s, 1):
            grid[row][col] = state
            if state == "
                black_num += 1

    grid[h][w] = "G"

    grid[1][1] = "!"
    min_count = bfs()

    if min_count == -1:
        print(-1)
    else:
        print(h * w - black_num - min_count - 1)


if __name__ == '__main__':
    main()

Solution (Python):
import sys

readline = sys.stdin.readline
MOD = 10 ** 9 + 7
INF = float('INF')
sys.setrecursionlimit(10 ** 5)

from collections import defaultdict, deque


def initialize_maze(h, w):
    grid = dict()

    for x in range(w + 2):
        grid[(x, 0)] = "
        grid[(x, h + 1)] = "

    for y in range(h + 2):
        grid[(0, y)] = "
        grid[(w + 1, y)] = "

    return grid


def main():
    def bfs():
        que = deque()
        que.append((1, 1, 0))

        while que:
            x, y, count = que.popleft()
            for mx, my in ((1, 0), (0, 1), (-1, 0), (0, -1)):
                nx, ny = x + mx, y + my
                if grid[(nx, ny)] == ".":
                    que.append((nx, ny, count + 1))
                    grid[(nx, ny)] = "!"
                elif grid[(nx, ny)] == "G":
                    min_count = count + 1
                    return min_count
        return - 1

    h, w = map(int, readline().split())
    grid = initialize_maze(h, w)

    black_num = 0
    for y in range(1, h + 1):
        s = input()
        for x, state in enumerate(s, 1):
            grid[(x, y)] = state
            if state == "
                black_num += 1

    grid[(w, h)] = "G"

    grid[(1, 1)] = "!"
    min_count = bfs()

    if min_count == -1:
        print(-1)
    else:
        print(h * w - black_num - min_count - 1)


if __name__ == '__main__':
    main()

Solution (Python):


import math



from collections import deque
from collections import Counter




h,w=map(int,input().split())
s=[input() for _ in range(h)]
seen=[[0]*w for _ in range(h)]
p=[(1,0),(-1,0),(0,1),(0,-1)]
cnt=0
for i in range(h):
    cnt+=s[i].count(".")
d=deque()
d.append((0,0))
seen[0][0]=1
res=0
while True:
    if not d:
        break
    i,j=d.pop()
    for idx in p:
        x,y=idx
        if 0<=i+x<h and 0<=j+y<w and seen[i+x][j+y]==0 and s[i+x][j+y]==".":
            d.appendleft((i+x,j+y))
            seen[i+x][y+j]=seen[i][j]+1
    if seen[h-1][w-1]!=0:
        break
if seen[h-1][w-1]==0:
  print(-1)
else:
  print(cnt-seen[h-1][w-1])

Solution (Python):
h,w = map(int,input().split())
m = [list(map((lambda x: 0 if x == '
ret = sum(list(map(sum,m)))

q = [[0,0,0]]
m[0][0] = 0
while len(q)!=0:
    qtop = q.pop(0)
    x = qtop[0]
    y = qtop[1]
    d = qtop[2]
    if x == h-1 and y == w-1:
        print(ret-d-1)
        break
    if 0 < x and m[x-1][y] == 1:
        m[x-1][y] = 0
        q.append([x-1,y,d+1])
    if h-1 > x and m[x+1][y] == 1:
        m[x+1][y] = 0
        q.append([x+1,y,d+1])
    if 0 < y and m[x][y-1] == 1:
        m[x][y-1] = 0
        q.append([x,y-1,d+1])
    if w-1 > y and m[x][y+1] == 1:
        m[x][y+1] = 0
        q.append([x,y+1,d+1])
else:
    print(-1)

Solution (Python):
H, W = [int(x) for x in input().split()]
G = []
for _ in range(H):
    G.append(input())

import queue, itertools
dist = {(i, j) : -1 for i, j in itertools.product(range(W), range(H))}
dist[(0, 0)] = 1
q = queue.Queue()
q.put((0, 0))

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

while not q.empty():
    x, y = q.get()
    d = dist[(x, y)]
    for i in range(4):
        nx, ny = x + dx[i], y + dy[i]
        if min(nx, ny) >= 0 and nx <= W - 1 and ny <= H - 1:
            if dist[(nx, ny)] == -1 and G[ny][nx] == '.':
                dist[(nx, ny)] = d + 1
                q.put((nx, ny))
            else: 
                continue

if dist[(W - 1, H - 1)] == -1:
    print(-1)
else:    
    print(H * W - ''.join(G).count('

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

h, w = map(int, input().split())
maze = [list("
white = 0
for _ in [0] * h:
    line = "
    maze.append(list(line))
    white += line.count(".")
maze += [list("
maze[1][1] = 0
maze[-2][-2] = "goal"

q = set([(1,1)])
dir = [[1, 0], [0, 1], [-1, 0], [0, -1]]
dis = 0
while q:
    next_q = set()
    dis += 1
    for x, y in q:
        
        maze[y][x] = dis

        for dx, dy in dir:
            next_x, next_y = x + dx, y + dy
            if maze[next_y][next_x] == ".":
                
                next_q.add((next_x, next_y))

            if maze[next_y][next_x] == "goal":
                print(white - dis - 1)
                exit()
    q = next_q
print(-1)

Solution (Python):
from collections import deque
import sys
sys.setrecursionlimit(4000)

def validCordinate(x, y, dist, Grid):
    if x < 0 or x >= len(Grid[0]):
        return False
    if y < 0 or y >= len(Grid):
        return False

    if dist[y][x] != -1:
        return False

    if Grid[y][x] != '.':
        return False

    return True

def bfs(x, y, q, dist, Grid):
    
    if validCordinate(x + 1, y, dist, Grid):
        q.append((x+1, y))
        dist[y][x+1] = dist[y][x] + 1
    if validCordinate(x, y + 1, dist, Grid):
        q.append((x, y + 1))
        dist[y+1][x] = dist[y][x] + 1
    if validCordinate(x - 1, y, dist, Grid):
        q.append((x-1, y))
        dist[y][x-1] = dist[y][x] + 1
    if validCordinate(x, y - 1, dist, Grid):
        q.append((x, y-1))
        dist[y-1][x] = dist[y][x] + 1


    
    if x == len(Grid[0]) - 1 and y == len(Grid) - 1:
        return dist
    if len(q) == 0:
        return False

    cx, cy = q.popleft()

    return bfs(cx, cy, q, dist, Grid)
    

def main():
    
    H, W = map(int, input().split())
    Grid = []
    dist = [[-1 for j in range(W)] for i in range(H)]
    q = deque()

    for i in range(H):
       Grid.append(input()) 


    dist[0][0] = 0
    res = bfs(0, 0, q, dist, Grid)

    if res:
        whiteNumber = 0
        for i in range(H):
            for j in range(W):
                if Grid[i][j] == ".":
                    whiteNumber += 1
        print(whiteNumber - res[-1][-1] - 1)
    else:
        print(-1)

if __name__ == "__main__":
    main()

Solution (Python):
import math
import itertools
from collections import deque
import bisect
import heapq

def IN(): return int(input())
def sIN(): return input()
def lIN(): return list(input())
def MAP(): return map(int,input().split())
def LMAP(): return list(map(int,input().split()))
def TATE(n): return [input() for i in range(n)]
ans = 0

def bfs(sx,sy):
    global count 
    
    d = [[-1] * 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] == h-1 and p[1] == w-1:
            break
        for m in range(4):
            nx = p[0] + dx[m]
            ny = p[1] + dy[m]

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

    if d[h-1][w-1] == -1:
      return -1
    else:
      for i in range(h):
        count += maze[i].count('.')
      count -= 2
      return count - d[h-1][w-1] + 1
  
  

h,w = MAP()
maze = [list(input()) for i in range(h)]
count = 0

print(bfs(0,0))

Solution (Python):
import math
import sys
from collections import deque
import copy
def mi() : return map(int,input().split())
a,b=mi()
l=[list(input()) for _ in range(a)]
count=0
for i in range(a):
  for _ in range(b):
    if l[i][_]==".":
      count+=1
l[0][0]=1
q=deque([[0,0]])
while q:
  x,y=q.popleft()
  if x==a-1 and y==b-1:
    print(count-l[x][y])
    sys.exit()
  for e,f in [[0,1],[0,-1],[1,0],[-1,0]]:
    if 0<=x+e<a and 0<=y+f<b and l[x+e][f+y]==".":
      l[x+e][f+y]=l[x][y]+1
      q.append([x+e,y+f])
print(-1)

Solution (Python):
import math
import sys
from collections import deque
import copy
def mi() : return map(int,input().split())
a,b=mi()
l=[list(input()) for _ in range(a)]
count=0
for i in range(a):
  for _ in range(b):
    if l[i][_]==".":
      count+=1
l[0][0]=1
q=deque([[0,0]])
while q:
  x,y=q.popleft()
  if x==a-1 and y==b-1:
    print(count-l[x][y])
    sys.exit()
  for e,f in [[0,1],[0,-1],[1,0],[-1,0]]:
    if 0<=x+e<a and 0<=y+f<b and l[x+e][f+y]==".":
      l[x+e][f+y]=l[x][y]+1
      q.append([x+e,y+f])
print(-1)