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

Solution (Python):
from collections import deque
H,W=map(int,input().split())
s=[['
count=0
for i in range(1,H+1):
  S=list(input())
  s[i]=['
  count+=S.count('.')
move=[(1,0),(-1,0),(0,1),(0,-1)]
que=deque([(1,1)])
s[1][1]=1
while que:
  a,b=que.popleft()
  if (a,b)==(H,W):
    break
  for my,mx in move:
    ny=my+a
    nx=mx+b
    if s[ny][nx]=='
      continue
    elif s[ny][nx]=='.':
      que.append((ny,nx))
      s[ny][nx]=s[a][b]+1
ans=-1
if s[H][W]!='.':
  ans=count-s[H][W]
print(ans)

Solution (Python):
from collections import deque
def gridbfs(grid,sy,sx):
    INF = 10**18

    gridy = len(grid)
    gridx = len(grid[0])

    dist = [[INF]*gridx for _ in range(gridy)]
    dist[sy][sx] = 0
    q = deque([(sy,sx)])

    while q:
        y,x = q.popleft()
        for dy,dx in [(-1,0),(1,0),(0,-1),(0,1)]:
            ny,nx = y+dy, x+dx
            if not (0 <= ny < gridy and 0 <= nx < gridx):
                continue
            if grid[ny][nx] == '
                continue
            if dist[ny][nx] != INF:
                continue
            dist[ny][nx] = dist[y][x] + 1
            q.append((ny,nx))

    return dist

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

Grid = [input() for _ in range(H)]

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

d = gridbfs(Grid,0,0)

print(max(-1, cnt - d[H-1][W-1] -1))

Solution (Python):
from collections import deque
def gridbfs(grid,sy,sx):
    INF = 10**18

    gridy = len(grid)
    gridx = len(grid[0])

    dist = [[INF]*gridx for _ in range(gridy)]
    dist[sy][sx] = 0
    q = deque([(sy,sx)])

    while q:
        y,x = q.popleft()
        for dy,dx in [(-1,0),(1,0),(0,-1),(0,1)]:
            ny,nx = y+dy, x+dx
            if not (0 <= ny < gridy and 0 <= nx < gridx):
                continue
            if grid[ny][nx] == '
                continue
            if dist[ny][nx] != INF:
                continue
            dist[ny][nx] = dist[y][x] + 1
            q.append((ny,nx))

    return dist

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

Grid = [input() for _ in range(H)]

cnt = 0

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

d = gridbfs(Grid,0,0)

if d[H-1][W-1] == 10**18:
    print(-1)
else:
    print(cnt - d[H-1][W-1] -1)

Solution (Python):

import queue

h, w = map(int, input().split())
c = [list(input()) for i in range(h)]
emp = 0
for i in range(h):
    for j in range(w):
        if c[i][j] == '.':
            emp += 1

visited = [[0 for i in range(w)] for j in range(h)]
q = queue.Queue()
q.put([0, 0, 1])
visited[0][0] = 1
dyx = [[0, 1], [1, 0], [-1, 0], [0, -1]]
flag = False
while not q.empty():
    now = q.get()
    if now[0] == h-1 and now[1] == w-1:
        flag = True
        break
    for i in range(4):
        y = now[0] + dyx[i][0]
        x = now[1] + dyx[i][1]
        z = now[2]
        if 0 <= y < h and 0 <= x < w:
            if c[y][x] != '
                visited[y][x] = 1
                q.put([y, x, z+1])
if flag:
    print(emp-now[2])
else:
    print(-1)

Solution (Python):
from collections import deque

h, w = map(lambda x: int(x)+2, input().split())
MAZE = ['
for _ in range(h-2):
    MAZE.append('
else:
    MAZE.append('

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


i, j = (1, 1)
INF = 10**18
dist = [[INF] * w for _ in range(h)]
dist[i][j] = 1
next_v = deque([[i, j]])
while next_v:
    i, j = next_v.popleft()
    direction = [(-1, 0), (0, 1), (1, 0), (0, -1)]
    for di, dj in direction:
        x, y = i+di, j+dj
        if MAZE[x][y] == "
            continue
        if dist[x][y] <= dist[i][j] + 1:
            continue
        dist[x][y] = dist[i][j] + 1
        next_v.append((x, y))

last = dist[h-2][w-2]
if last != INF:
    ans = total - last
else:
    ans = -1
print(ans)

Solution (Python):
from collections import deque

h, w = map(lambda x: int(x)+2, input().split())
MAZE = ['
for _ in range(h-2):
    MAZE.append('
else:
    MAZE.append('

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


i, j = (1, 1)
INF = 10**18
dist = [[INF] * w for _ in range(h)]
dist[i][j] = 1
next_v = deque([[i, j]])
while next_v:
    i, j = next_v.popleft()
    direction = [(-1, 0), (0, 1), (1, 0), (0, -1)]
    for di, dj in direction:
        x, y = i+di, j+dj
        if MAZE[x][y] == "
            continue
        if dist[x][y] <= dist[i][j] + 1:
            continue
        dist[x][y] = dist[i][j] + 1
        next_v.append((x, y))

last = dist[h-2][w-2]
if last != INF:
    ans = total - last
else:
    ans = -1
print(ans)

Solution (Python):
h, w = map(lambda x: int(x)+2, input().split())
MAZE = ['
for _ in range(h-2):
    MAZE.append('
else:
    MAZE.append('

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

i, j = (1, 1)
INF = 10**18
dist = [[INF] * w for _ in range(h)]
dist[i][j] = 1
next_v = [(i, j)]
while next_v:
    i, j = next_v.pop()
    direction = [(-1, 0), (0, 1), (1, 0), (0, -1)]
    for di, dj in direction:
        x, y = i+di, j+dj
        if MAZE[x][y] == "
            continue
        if dist[x][y] <= dist[i][j] + 1:
            continue
        dist[x][y] = dist[i][j] + 1
        next_v.append((x, y))

last = dist[h-2][w-2]
if last != INF:
    ans = total - last
else:
    ans = -1

print(ans)

Solution (Python):
h,w=map(int,input().split())
maze=[list(input()) for i in range(h)]
black=0
for i in range(h):
  for j in range(w):
    if maze[i][j]=='
      black+=1
s=[0,0,1]
g=[h-1,w-1]
queue=[s]
go=[[0,1],[0,-1],[1,0],[-1,0]]
ans=-1
check=[[True for i in range(w)] for j in range(h)]
while len(queue)>0:
  p=queue.pop(0)
  for i in range(4):
    x=p[0]+go[i][0]
    y=p[1]+go[i][1]
    count=p[2]+1
    if x>-1 and x<h and y>-1 and y<w and check[x][y] and maze[x][y]=='.':
      if x==g[0] and y==g[1]:
        ans=count
        break
      else:
        check[x][y]=False
        queue.append([x,y,count])
  if ans>0:
    break
if ans<0:
  print(ans)
else:
  print(h*w-black-ans)

Solution (Python):


import sys
import math
import time

import collections
from collections import deque
from collections import Counter
import queue
import copy
import bisect
import heapq
import itertools


def bfs(sx, sy):
  que = deque([[sy,sx]])
  D =  [(0,1), (1,0), (0,-1), (-1,0)]
  while que:
    y,x = que.popleft()
    for i,j in D:
      if(x+i<0 or y+j<0 or x+i>W-1 or y+j>H-1):
        continue
      dist = G[y+j][x+i]
      if(G[y+j][x+i] != "
        if(type(G[y+j][x+i]) is str):
          G[y+j][x+i] = G[y][x]+1
          que.append([y+j,x+i])
        elif(dist>G[y][x]+1):
          G[y+j][x+i] = G[y][x]+1
          que.append([y+j,x+i])
  return









H,W = map(int,input().split())
G = [list(map(str, input())) for i in range(H)]
ans = 0
n = 0



for i in range(H):
    for j in range(W):
        if(G[i][j]=="."):
            n += 1

G[0][0] = 0
bfs(0,0)


if(type(G[H-1][W-1]) is str):
    ans = -1
else:
    ans = n - G[H-1][W-1]-1


print(ans)

Solution (Python):
from collections import deque

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


dotsum = 0
for row in maze:
    for j in row:
        if j == ".":
            dotsum += 1

dx = [0, 1, 0, -1]
dy = [1, 0, -1, 0]
dp = [[-1] * (w + 1) for i in range(h + 1)]
dp[0][0] = 0

pos = deque([[0, 0, 0]])
dotroute = 0

while len(pos) > 0:
    x, y, depth = pos.popleft()
    if x == w - 1 and y == h - 1:
        dotroute = depth + 1
        break
    for i in range(4):
        nx = x + dx[i]
        ny = y + dy[i]
        if 0 <= nx < w and 0 <= ny < h and maze[ny][nx] == "." and dp[ny][nx] == -1:
            dp[ny][nx] = dp[y][x] + 1
            pos.append([nx, ny, depth + 1])
if dotroute == 0:
    print(-1)
else:
    print(dotsum - dotroute)

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

dist = [[0]*W for _ in range(H)]
count = 0

for i in range(H):
    for j in range(W):
        if s[i][j] == '
            dist[i][j] = -1
        else:
            count += 1
dist[0][0] = 1  

move = deque()
move.append((0,0))

def bfs(move, dist):
    while move:
        y,x = move.popleft()
        d = dist[y][x]
        for dy,dx in ((0,1), (0,-1), (1,0), (-1,0)):
            new_y = y + dy
            new_x = x + dx
            if new_y < 0 or new_y >= H or new_x < 0 or new_x >= W:
                continue
            if dist[new_y][new_x] == 0:  
                dist[new_y][new_x] = d+1
                move.append((new_y,new_x))
    return dist[H-1][W-1]
move_score = bfs(move,dist)
if move_score == 0:
    print(-1)
else:
    print(count - move_score)

Solution (Python):
from collections import deque

H, W = map(int, input().split())
S = [['
c = 0
for i in range(1, H+1):
    s = list(input())
    S[i] = ['
    c += s.count('.')

step = [(1, 0), (-1, 0), (0, 1), (0, -1)]
que = deque([(1, 1)])
S[1][1] = 1
while que:
    h, w = que.popleft()
    if (h, w) == (H, W):
        break
    for dh, dw in step:
        nh = h + dh
        nw = w + dw
        if S[nh][nw] != '.':
            continue
        que.append((nh, nw))
        S[nh][nw] = S[h][w] + 1
print(-1 if S[H][W] == '.' else c - S[H][W])

Solution (Python):
h , w = map(int,input().split())
g = ['
s = [[100]*(w+2)]+[[100]+[0]*w+[100]for i in range(h)]+[[100]*(w+2)]
queue=[]
head = 0
tail = 0
s[1][1]=1
queue.append([1,1])
tail+=1
while tail!=head:
    y = queue[head][0]
    x = queue[head][1]
    if g[y][x+1]=='.' and s[y][x+1]==0:
        queue.append([y,x+1])
        tail+=1
        s[y][x+1]=s[y][x]+1
    if g[y][x-1]=='.' and s[y][x-1]==0:
        queue.append([y,x-1])
        tail+=1
        s[y][x-1]=s[y][x]+1
    if g[y+1][x]=='.' and s[y+1][x]==0:
        queue.append([y+1,x])
        tail+=1
        s[y+1][x]=s[y][x]+1
    if g[y-1][x]=='.' and s[y-1][x]==0:
        queue.append([y-1,x])
        tail+=1
        s[y-1][x]=s[y][x]+1
    head+=1
if s[h][w]==0:
    print('-1')
else:
    count = 0
    for i in range(1,h+1):
        for j in range(1,w+1):
            if g[i][j]=='
                count+=1
    ans = h*w - s[h][w]-count
    print(ans)

Solution (Python):
from collections import deque
H, W = list(map(int, input().split(' ')))
FIELD = list()
for _ in range(H):
    FIELD.append(input())
WHITE_CELL_NUM = 0
for h in range(H):
    for w in range(W):
        if FIELD[h][w] == '.':
            WHITE_CELL_NUM += 1
sh, sw = 0, 0  
gh, gw = H - 1, W - 1  


frontier = deque()
ch, cw = sh, sw
frontier.append((ch, cw))
steps = [[-1 for _ in range(W)] for _ in range(H)]
steps[ch][cw] = 0
while len(frontier) > 0:
    ch, cw = frontier.popleft()  
    if ch == gh and cw == gw:  
        break
    for dh, dw in [[1, 0], [-1, 0], [0, 1], [0, -1]]:
        nh, nw = ch + dh, cw + dw  
        if (nh < 0) or (H - 1 < nh) or (nw < 0) or (W - 1 < nw):
            continue
        if FIELD[nh][nw] == '
            continue
        if steps[nh][nw] >= 0:
            continue
        steps[nh][nw] = steps[ch][cw] + 1
        frontier.append((nh, nw))
if ch != gh and cw != gw:
    print(-1)
    exit(0)
shortest_path_length = steps[gh][gw] + 1
print(WHITE_CELL_NUM - shortest_path_length)

Solution (Python):
from collections import deque

H, W = map(int, input().split())
grid = '
for _ in range(H):
    grid += '
grid += '

root = list(i for i in range(len(grid)) if grid[i] == '.')
start = root[0]
goal = root[-1]

move = [1, -1, W + 2, -(W + 2)]
se = set([start])
q = deque([start])

T = [-1] * len(grid)
T[start] = 0


def bfs():
    while q:
        x = q.popleft()
        for dx in move:
            y = x + dx
            if grid[y] == '
                continue
            if y in se:
                continue
            if y == goal:
                return T[x] + 1
            T[y] = T[x] + 1
            se.add(y)
            q.append(y)
    return T[goal]


ret = bfs()
print(len(root[1:]) - ret if ret != -1 else -1)

Solution (Python):
from collections import deque

def main():
    h, w = map(int, input().split())
    s = [input() for _ in range(h)]
    b = sum(r.count("
    m = [[9999] * w for _ in range(h)]
    m[0][0] = 1
    n = deque([(0, 0)])
    d = set()
    while n:
        x, y = n.popleft()
        if (x, y) in d:
            continue
        if x == w - 1 and y == h - 1:
            break
        d.add((x, y))
        if x > 0 and s[y][x - 1] == ".":
            m[y][x - 1] = min(m[y][x - 1], m[y][x] + 1)
            n.append((x - 1, y))
        if x < w - 1 and s[y][x + 1] == ".":
            m[y][x + 1] = min(m[y][x + 1], m[y][x] + 1)
            n.append((x + 1, y))
        if y > 0 and s[y - 1][x] == ".":
            m[y - 1][x] = min(m[y - 1][x], m[y][x] + 1)
            n.append((x, y - 1))
        if y < h - 1 and s[y + 1][x] == ".":
            m[y + 1][x] = min(m[y + 1][x], m[y][x] + 1)
            n.append((x, y + 1))
    if m[h - 1][w - 1] == 9999:
        print(-1)
    else:
        print(h * w - b - m[h - 1][w - 1])

if __name__ == '__main__':
    main()

Solution (Python):
from collections import deque

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

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

cnt = 1

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

if bfs() == float("inf"):
    print(-1)
else:
    print(H*W-bfs()-cnt)

Solution (Python):
from collections import deque

def bfs():
    move=[[1,0],[0,1],[-1,0],[0,-1]]
    visited=[[-1]*yoko for i in range(tate)]
    queue=deque()
    queue.append([sy,sx]) 
    visited[sy][sx]=0 
    while queue:
        y,x=queue.popleft()
        if [y,x]==[gy,gx]: 
            return visited[gy][gx]
        for dy,dx in move:
            my,mx=y+dy,x+dx
            if not(0<=my<tate) or not(0<=mx<yoko):
                continue
            if maze[my][mx]=="." and visited[my][mx]==-1:
                queue.append([my,mx])
                visited[my][mx]=visited[y][x]+1 
    return -1 

tate,yoko=map(int,input().split())
maze=[]
black=0
for i in range(tate):
    line=list(input())
    maze.append(line)
    black+=line.count('
sy,sx=0,0
gy,gx=tate-1,yoko-1
white=1+bfs()
if white==0: 
    ans=-1
else:
    ans=tate*yoko-black-white
print(ans)

Solution (Python):
from collections import  deque

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

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

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

for h in range(H):
    for w in range(W):
        if s[h][w] == ".":
            white += 1

q = deque()
q.append([0, 0])
dist[0][0] = 0
while(q):
    a = q.popleft()
    for i in range(4):
        if a[0] + dx[i] < 0 or a[0] + dx[i] >= W or a[1] + dy[i] < 0 or a[1] + dy[i] >= H:
            continue
        if s[a[1] + dy[i]][a[0] + dx[i]] == "
            continue
        if dist[a[1] + dy[i]][a[0] + dx[i]] == -1:
            dist[a[1] + dy[i]][a[0] + dx[i]] = dist[a[1]][a[0]] + 1
            q.append([a[0] + dx[i], a[1] + dy[i]])

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

Solution (Python):
from collections import deque
h, w = map(int, input().split())
grid = [list(input()) for _ in range(h)]
move = [(1, 0), (0, 1), (-1, 0), (0, -1)]
gy = h - 1
gx = w - 1


def bfs(y, x):
    queue = deque([])
    queue.append((y, x))
    vgrid = [[float("inf")] * w for _ in range(h)]
    vgrid[y][x] = 0

    while queue:
        p = queue.popleft()
        if (p[0], p[1]) == (gy, gx):
            break
        for i in range(4):
            ny = p[0] + move[i][0]
            nx = p[1] + move[i][1]
            if 0 <= ny < h and 0 <= nx < w and vgrid[ny][nx] == float("inf") and grid[ny][nx] != "
                queue.append((ny, nx))
                vgrid[ny][nx] = vgrid[p[0]][p[1]] + 1

    return vgrid[gy][gx]


shortest_distance = bfs(0, 0)
if shortest_distance == float("inf"):
    print("-1")
    exit()
white = 0
for li in grid:
    white += li.count(".")
ans = white - shortest_distance - 1
print(ans)

Solution (Python):
from collections import deque
h,w=map(int,input().split())
s=[input() for _ in range(h)]
def bfs(maze,visited,sy,sx):
  queue=deque([[sy,sx]])
  visited[sy][sx]=1
  while queue:
    y,x=queue.popleft()
    if [y,x]==[h-1,w-1]:
      return visited[y][x]
    for j,k in ([1,0],[-1,0],[0,1],[0,-1]):
      n_y,n_x=y+j,x+k
      if not (0<=n_y<h and 0<=n_x<w):
        continue
      if maze[n_y][n_x]=='.' and visited[n_y][n_x]==0:
        visited[n_y][n_x]=visited[y][x]+1
        queue.append([n_y,n_x])
  return -1
cnt=0
for i in s:
  cnt+=i.count('.')
visited=[[0]*w for _ in range(h)]
route=bfs(s,visited,0,0)
print(-1 if route<0 else cnt-route)

Solution (Python):
from collections import deque

def bfs(maze,visited,start_h,start_w,goal_h,goal_w):
  queue=deque([[start_h,start_w]])
  visited[start_h][start_w]=0
  while queue:
    h,w=queue.popleft()
    if [h,w]==[goal_h,goal_w]:
      return visited[goal_h][goal_w]
    for i,j in ([1,0],[-1,0],[0,1],[0,-1]):
      new_h,new_w=h+i,w+j
      if new_h<0 or new_h>=H or new_w<0 or new_w>=W:
        continue
      if maze[new_h][new_w]=='.' and visited[new_h][new_w]==-1:
        visited[new_h][new_w]=visited[h][w]+1
        queue.append([new_h,new_w])

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

cost=bfs(maze,visited,0,0,H-1,W-1)
if cost==None:
  print(-1)
else:
  cnt=-1
  for i in range(H):
    cnt+=maze[i].count('.')
  print(cnt-cost)

Solution (Python):
import queue

INF = 10 ** 10

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

costs = [[-1] * (W+2)]
for _ in range(H):
    costs.append([-1] + list(map(lambda c: -1 if c == '
costs.append([-1] * (W+2))

num_of_white = sum(row.count(INF) for row in costs)

togo = queue.Queue()
togo.put((1, 1))
costs[1][1] = 1

arrived = False
while not togo.empty():
    x, y = togo.get()
    
    if x == H and y == W:
        arrived = True
        break
    
    for dx, dy in ((-1, 0), (1, 0), (0, -1), (0, 1)):
        if costs[x+dx][y+dy] > costs[x][y] + 1:
            costs[x+dx][y+dy] = costs[x][y] + 1
            togo.put( (x+dx, y+dy) )

if arrived:
    print(num_of_white - costs[H][W])
else:
    print(-1)

Solution (Python):




from collections import deque

INF = int(1e18)
neighbors = [(0, 1), (0, -1), (1, 0), (-1, 0)]

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


d = [[INF for _ in range(w)] for _ in range(h)]
queue = deque([(0, 0)])



d[0][0] = 0
while len(queue) > 0:
    (y, x) = queue.popleft()
    for (dy, dx) in neighbors:
        nx = x + dx
        ny = y + dy
        if 0 <= nx < w and 0 <= ny < h:
            if MAP[ny][nx] == '.' and d[ny][nx] > d[y][x] + 1:
                d[ny][nx] = d[y][x] + 1
                queue.append((ny, nx))


if d[h - 1][w - 1] == INF:
    print(-1)
else:
    distST = d[h - 1][w - 1]
    count0 = 0
    for row in MAP:
        for ch in row:
            if ch == '
                count0 += 1
    print(h * w - count0 - distST - 1)

Solution (Python):
import sys
from collections import deque

readline = sys.stdin.readline
H, W = map(int, readline().split())
S = [['
black = sum(row.count('


q = deque([(1, 1)])
S[1][1] = 1
direction = ((0, 1), (1, 0), (0, -1), (-1, 0))
while q:
    x, y = q.popleft()
    d = S[x][y]
    for dx, dy in direction:
        
        if S[x+dx][y+dy] == '.':
            S[x+dx][y+dy] = d + 1
            q.append((x+dx, y+dy))
ans = -1
if S[H][W] != '.':
    ans = H*W - S[H][W] - black
print(ans)

Solution (Python):
dy = (-1,0,1,0)
dx = (0,1,0,-1)
from collections import deque

def main():
    h,w = map(int,input().split())
    grid = [input() for _ in range(h)]
    cnt_white = sum(row.count('.') for row in grid)
    
    dist = [[-1] * w for _ in range(h)]
    q = deque([(0,0)])
    dist[0][0] = 1
    while q:
        i,j = q.popleft()
        for k in range(4):
            y = i + dy[k]
            x = j + dx[k]
            if y < 0 or y >= h:
                continue
            if x < 0 or x >= w:
                continue
            if dist[y][x] < 0 and grid[y][x] == '.':
                dist[y][x] = dist[i][j] + 1
                q.append((y,x))
    
    ans = cnt_white - dist[-1][-1]
    print(ans if dist[-1][-1] >= 0 else -1)          
if __name__ == '__main__':
    main()

Solution (Python):
import queue

h,w=map(int,input().split())
s=[]
dist=[]
cnt=0
for i in range(h):
  s.append(input())
  dist.append([5000]*w)
  cnt+=s[i].count("
que=queue.Queue()
que.put([0,0])
dist[0][0]=0
d=[[0,1],[0,-1],[1,0],[-1,0]]
while not que.empty():
  place=que.get()
  for p in d:
    if -1<place[0]+p[0]<h and -1<place[1]+p[1]<w:
      if s[place[0]+p[0]][place[1]+p[1]]=="." and dist[place[0]][place[1]]+1<dist[place[0]+p[0]][place[1]+p[1]]:
        dist[place[0]+p[0]][place[1]+p[1]] = dist[place[0]][place[1]]+1
        que.put([place[0]+p[0],place[1]+p[1]])
if dist[h-1][w-1]<5000:
  print(h*w-cnt-dist[h-1][w-1]-1)
else:
  print(-1)

Solution (Python):

from decimal import *
from itertools import permutations, combinations,combinations_with_replacement,product
import math



s = input().split()
p = [int(w) for w in s] 

H = p[0]
W = p[1]

a = []
for i in range(H):
    a.append(input())





b = ''
for i in range(W+2):
    b += '


a.insert(0, b)
for i in range(1, 1+H):
    a[i] = '
a.append(b)











header = ' '
for i in range(len(a[0])):
    header += ('{}'.format(i))

c=[]
for i in range(H+2):
    c.append([])

for i in range(H+2):
    for j in range(W+2):
        c[i].append(a[i][j])




    



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




start = [1, 1]
goal = [H, W]

c[start[0]][start[1]] = 'u'


def see_banmen():
    print(header)
    for i in range(len(c)):
        print('{}{}'.format(i,''.join(c[i])))


queue = [start]
next_list = [] 
step = 0
mode = 0
answer_mode = 0
status = True 
answer = -1

while status:
    if(len(queue) > 0):
        pivot = queue.pop(0) 
        x = pivot[0]
        y = pivot[1]
        if(c[x+1][y] == '.'):
            c[x+1][y] = 'u'
            next_list.append([x+1, y])
        if(c[x-1][y] == '.'):
            c[x-1][y] = 'u'
            next_list.append([x-1, y])
        if(c[x][y+1] == '.'):
            c[x][y+1] = 'u'
            next_list.append([x, y+1])
        if(c[x][y-1] == '.'):
            c[x][y-1] = 'u'
            next_list.append([x, y-1])
        c[x][y] = 'd'
    else:
        
        if(len(next_list) > 0):
            for i in range(len(next_list)):
                queue.append(next_list.pop(0))
            next_list = []
            
            
            if(c[goal[0]][goal[1]] == 'd' and answer_mode == 0):
                answer = step
                answer_mode = 1
                
                
                
            step += 1
            
        elif(mode == 0):
            
            mode = 1
            
            
            if(c[goal[0]][goal[1]] == 'd' and answer_mode == 0):
                
                answer = step
                answer_mode = 1
                
                
                
            
            step += 1
            
        else:
            status = False



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

Solution (Python):
from collections import deque
r,c =map(int,input().split())
G = [input() for _ in range(r)]
black = 0
for i in range(r):
    for j in range(c):
        if G[i][j] == "
            black += 1


M = [[10**7 for _ in range(c)] for i in range(r)]
queue = deque([(0,0)])
M[0][0] = 0
while len(queue) != 0:
    now = queue.popleft()
    dxy = [(0,1),(0,-1),(1,0),(-1,0)]
    for p in dxy:
        nexte = (now[0]+p[0],now[1]+p[1])
        if nexte[0]<0 or nexte[0]>=r or nexte[1]<0 or nexte[1]>=c:
            continue
        else:
            if G[nexte[0]][nexte[1]] == ".":
                if M[nexte[0]][nexte[1]] > M[now[0]][now[1]] + 1:
                    M[nexte[0]][nexte[1]] = M[now[0]][now[1]] + 1
                    queue.append(nexte)
if M[r-1][c-1] == 10**7:
    print("-1")
else:
    print(r*c-1 - M[r-1][c-1] - black)

Solution (Python):
from collections import deque

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

move = ((1, 0), (-1, 0), (0, 1), (0, -1))


def bfs(S, G):

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

    visited[S[0]][S[1]] = True
    que = deque([(S[0], S[1], 0)])

    while que:
        ci, cj, c = que.popleft()

        if ci == G[0] and cj == G[1]:
            return c

        for di, dj in move:
            ni, nj = ci + di, cj + dj
            if 0 <= ni < H and 0 <= nj < W and not visited[ni][nj] and C[ni][nj] != '
                visited[ni][nj] = True
                que.append((ni, nj, c+1))
    return 0


sg = [[0, 0], [H-1, W-1]]
ans = 0
ans += bfs(sg[0], sg[1])

if ans == 0:
    print('-1')
else:
    num = sum([n.count('
    result = H * W - (num + ans + 1)
    print(result)

Solution (Python):
r, c = map(int, input().split())
cc = [input() for i in range(r)]

from collections import deque






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

seen=[[-1 for i in range(c)] for j in range(r)]


bcount=0
for i in range(r):
    bcount+=cc[i].count("



seen[0][0]=0


ido=[[1,0],[0,1],[-1,0],[0,-1]]

f=0

while todo:
    y, x=todo.popleft() 
    for i in range(4): 
        ny, nx=y+ido[i][0], x+ido[i][1] 
        
        if 0<=ny<r and 0<=nx<c and seen[ny][nx]==-1 and cc[ny][nx]!="
            
            seen[ny][nx]=seen[y][x]+1 
            todo.append([ny,nx]) 
    if seen[r-1][c-1]!=-1:
        f=1
        break
if f==1: 
    
    print(r*c-seen[r-1][c-1]-1-bcount)
else:
    print(-1)

Solution (Python):
from collections import deque


def bfs(start):
    Q = deque()
    child = deque()
    Q.append(start)
    dist[start[1] - 1][start[0] - 1] = 0

    while Q:
        x, y = Q.popleft()
        x = x - 1
        y = y - 1

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

            if nx < 0 or nx >= W or ny < 0 or ny >= H:
                continue
            if G[ny][nx] == "
                continue
            if dist[ny][nx] != -1:
                continue

            child.append((nx + 1, ny + 1))

            if len(child) > 0:
                for c in child:
                    dist[c[1] - 1][c[0] - 1] = dist[y][x] + 1
                    Q.append(c)


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

kuro = 0
for i in range(H):
    G[i] = list(input())
    kuro += G[i].count('

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

start = (1, 1)
bfs(start)




if dist[H - 1][W - 1] == -1:
    res = -1
else:
    res = H * W - (dist[H - 1][W - 1] + 1) - kuro

print(res)

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

def bfs(sx, sy):
    ans = 10**9
    dire = ((0, -1), (-1, 0), (1, 0), (0, 1))
    dist = [[-1]*W for _ in range(H)] 
    dist[sx][sy] = 1
    que = deque([(sx, sy)]) 
    while que:
        x, y = que.popleft()
        d = dist[x][y]
        for dx, dy in dire:
            nx,ny = x+dx,y+dy
            if nx==H-1 and ny==W-1 and S[nx][ny] == '.':
                ans = min(d+1,ans)
            
            if 0<=nx<H and 0<=ny<W and S[nx][ny] == '.' and dist[nx][ny] == -1:
                dist[nx][ny] = d+1
                que.append((nx, ny))
    return ans 
black = 0
ans = bfs(0,0)
if ans == 10**9:
    print(-1)
else:
    for i in range(H):
        black += S[i].count('

    print(H*W-ans-black)

Solution (Python):
from collections import deque
h, w = map(int, input().split())
maze = []
maze.append('
for i in range(h):
    maze.append('
cnt = 0
for i in maze:
    cnt += i.count('.')
maze.append('
i, j = 1, 1
seen = {(1, 1)}
d = 0
stack = deque([[(i, j), d]])
while stack:
    pos, d = stack.popleft()
    i, j = pos
    for di, dj in [(-1, 0), (1, 0), (0, -1), (0, 1)]:
        if (i+di, j+dj) not in seen and maze[i + di][j + dj] == '.':
            if (i + di, j + dj) == (h, w):
                print(cnt - d -2)
                exit()
            stack.append([(i + di, j + dj), d + 1])
            seen.add((i + di, j + dj))
print(-1)

Solution (Python):
from collections import deque
INF = 10000

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

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

vx = [-1,1,0,0]
vy = [0,0,1,-1]

def bfs():
    while(q):
        x,y = q.popleft()
        for i in range(4):
            nx = x + vx[i]
            ny = y + vy[i]
            if 0 <= nx and nx < H and 0 <= ny and ny < W and S[nx][ny] == '.' and dist[nx][ny] == INF:
                q.append((nx,ny))
                dist[nx][ny] = dist[x][y] + 1
                if (nx, ny) == (gx, gy): return

q = deque()
q.append((0,0))
gx = H-1
gy = W-1
dist[0][0] = 1
bfs()
if dist[gx][gy] == INF: print(-1)
else:
    tmp = 0
    for h in range(H):
        tmp += S[h].count('
    print(H*W - dist[gx][gy] - tmp)