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 = [list(input()) for _ in range(h)]
dist = [[-1 for _ in range(w+2)] for _ in range(h+2)]
dist[1][1] = 1
white = 0
dl = [[1, 0], [0, 1], [-1, 0], [0, -1]]
tmp = ["
S = [tmp]
for i in range(h):
    S.append([])
    for j in range(w):
        white += 1 if s[i][j] == "." else 0
    S[i+1].extend("
    S[i+1].extend(s[i])
    S[i+1].extend("
S.append(tmp)


def dfs():
    global S, dl
    queue = deque([[1, 1]])

    while queue:
        [x, y] = queue.popleft()
        for d in dl:
            if dist[x + d[0]][y + d[1]] == -1 and S[x + d[0]][y + d[1]] == ".":
                dist[x + d[0]][y + d[1]] = dist[x][y] + 1
                queue.append([x + d[0], y + d[1]])


dfs()
if dist[h][w] == -1:
    print(-1)
else:
    print(white-dist[h][w])

Solution (Python):

from collections import deque 

def bfs():
    d = [[float('inf')]*w for _ 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 _ 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():
    H, W = map(int, input().split())
    S = [list(input()) for _ in range(H)]
    Q = deque([])
    Q.append([0,0])
    dh = [1,0,-1,0]
    dw = [0,1,0,-1]
    d = [[float('inf')] * W for _ in range(H)]
    d[0][0] = 0
    while Q:
        h, w = Q.popleft()
        if h == H - 1 and w == w - 1:
            break
        for i in range(4):
            nh = h + dh[i]
            nw = w + dw[i]
            if 0 <= nh < H and 0 <= nw < W:
                if S[nh][nw] == '.' and d[nh][nw] == float('inf'):
                    d[nh][nw] = min(d[nh][nw], d[h][w] + 1)
                    Q.append([nh,nw])

    if d[H-1][W-1] == float('inf'):
        print(-1)
        exit()
    
    cnt = 0
    for h in range(H):
        for w in range(W):
            if S[h][w] == '.':
                cnt += 1

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

if __name__ == "__main__":
    main()

Solution (Python):
from collections import deque
H,W = map(int,input().split())
S = []
Blank = 0
for i in range(H):
  temp = str(input());temp = list(temp)
  Blank += temp.count(".")
  S.append(temp)

INF = float("inf")
Q = deque([])
Q.append([0,0])
dxdy = [[1,0],[-1,0],[0,1],[0,-1]]
visited = [[INF]*W for _ in range(H)]
visited[0][0] = 1
while Q:
  temp = Q.popleft()
  x = temp[0]; y = temp[1]
  for i in range(4):
    nx = x+dxdy[i][0]
    ny = y+dxdy[i][1]
    if 0<=nx<H and 0<=ny<W and visited[nx][ny] == INF and S[nx][ny] == ".":
      visited[nx][ny] = visited[x][y] + 1
      Q.append([nx,ny])
      if [nx,ny] == [H,W]:
        break

if visited[H-1][W-1] == INF:
  print(-1)
  exit()
ans = Blank - visited[H-1][W-1]
print(ans)

Solution (Python):
h,w=map(int,input().split())
s=[list(input()) for _ in range(h)]
black=0
for i in range(h):
    black+=s[i].count("




from collections import deque
que=deque()
que.append([0,0])
s[0][0]="
count=[[0]*w for _ in range(h)]
while que:
    
    x=que.pop()
    dx_dy=[[0,1],[1,0],[0,-1],[-1,0]]
    for k in range(4):
        nx=x[0]+dx_dy[k][0]
        ny=x[1]+dx_dy[k][1]
        if 0<=nx<=h-1 and 0<=ny<=w-1 and s[nx][ny]==".":
            s[nx][ny]="
            count[nx][ny]=count[x[0]][x[1]]+1
            que.appendleft([nx,ny])
if s[-1][-1]=="
    print(h*w-count[-1][-1]-black-1)
else:
    print(-1)

Solution (Python):
from collections import deque
h, w = map(int, input().split())
maze = [list(input()) for i in range(h)]
dh = [1, 0, -1, 0]
dw = [0, 1, 0, -1]

sh, sw, gh, gw = 0, 0, h - 1, w - 1
d = [[float("inf")] * w for _ in range(h)]

que = deque([])
que.append((sh, sw))
d[sh][sw] = 0


def bfs():
    while que:
        p = que.popleft()
        if p[0] == gh and p[1] == gw:
            break
        for i in range(4):
            nh = p[0] + dh[i]
            nw = p[1] + dw[i]
            if 0 <= nh < h and 0 <= nw < w and maze[nh][nw] != "
                que.append((nh, nw))
                d[nh][nw] = d[p[0]][p[1]] + 1
    return d[gh][gw]


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

Solution (Python):
from collections import deque
h, w = map(int, input().split())
maze = [list(input()) for i in range(h)]
dx = [1, 0, -1, 0]
dy = [0, 1, 0, -1]

sx, sy, gx, gy = 0, 0, h - 1, w - 1
d = [[float("inf")] * w for _ in range(h)]

que = deque([])
que.append((sx, sy))
d[sx][sy] = 0


def bfs():
    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]


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

Solution (Python):
h,w=map(int,input().split())
g=[input() for _ in range(h)]
d=[[-1]*w for _ in range(h)]
d[0][0]=0
q=[(0,0)]
while q:
  tx,ty=q.pop(0)
  for dx,dy in [(1,0),(0,1),(-1,0),(0,-1)]:
    nx,ny=tx+dx,ty+dy
    if 0<=nx<h and 0<=ny<w and g[nx][ny]=='.' and d[nx][ny]<0:
      d[nx][ny]=d[tx][ty]+1
      q+=[(nx,ny)]
print((sum(s.count('.') for s in g)-d[-1][-1])*(d[-1][-1]>0)-1)

Solution (Python):
h,w=map(int,input().split())
g=[input() for _ in range(h)]
d=[[-1]*w for _ in range(h)]
d[0][0]=0
q=[(0,0)]
while q:
  tx,ty=q.pop(0)
  for dx,dy in [(1,0),(0,1),(-1,0),(0,-1)]:
    nx,ny=tx+dx,ty+dy
    if 0<=nx<h and 0<=ny<w and g[nx][ny]=='.' and d[nx][ny]<0:
      d[nx][ny]=d[tx][ty]+1
      q+=[(nx,ny)]
print((h*w-sum(s.count('

Solution (Python):
h,w=map(int,input().split())
g=[input() for _ in range(h)]
from collections import *
d=[[-1]*w for _ in range(h)]
d[0][0]=0
q=deque([(0,0)])
while q:
  tx,ty=q.popleft()
  for dx,dy in [(1,0),(0,1),(-1,0),(0,-1)]:
    nx,ny=tx+dx,ty+dy
    if 0<=nx<h and 0<=ny<w and g[nx][ny]=='.' and d[nx][ny]<0:
      d[nx][ny]=d[tx][ty]+1
      q.append((nx,ny))
print((h*w-sum(s.count('

Solution (Python):
h,w=map(int,input().split())
g=[input() for _ in range(h)]
from collections import *
def bfs(x,y):
  d=[[-1]*w for _ in range(h)]
  d[x][y]=0
  q=deque([(x,y)])
  while q:
    tx,ty=q.popleft()
    for dx,dy in [(1,0),(0,1),(-1,0),(0,-1)]:
      nx,ny=tx+dx,ty+dy
      if 0<=nx<h and 0<=ny<w and g[nx][ny]=='.' and d[nx][ny]<0:
        d[nx][ny]=d[tx][ty]+1
        q.append((nx,ny))
  return d
d=bfs(0,0)[-1][-1]
print((h*w-sum(s.count('

Solution (Python):
from collections import deque

INF = 10**18

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

live_cell_count = 0
for S_line in S:
    live_cell_count += S_line.count(".")

dist = [[INF for _ in range(W)] for _ in range(H)]
dist[0][0] = 0
q = deque([(0, 0)])
while q:
    t_pos = tx, ty = q.popleft()
    t_dist = dist[ty][tx]

    for dx, dy in ((0, 1), (1, 0), (-1, 0), (0, -1)):
        pos = x, y = tx+dx, ty+dy
        if not (0 <= x < W and 0 <= y < H):
            continue
        elif S[y][x] == "
            continue
        elif dist[y][x] <= t_dist + 1:
            continue
        dist[y][x] = t_dist + 1
        q.append(pos)


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

Solution (Python):
from collections import defaultdict, deque

H, W = map(int, input().split())
sss = [[int(c == '

dhw = [
    [0, 1],
    [1, 0],
    [0, -1],
    [-1, 0],
]


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

queued = {(0, 0)}

fdist = -1
while dq:
    h, w, dist = dq.popleft()
    
    if h == H - 1 and w == W - 1:
        fdist = dist
        break
        
    for dh, dw in dhw:
        nh = h + dh
        nw = w + dw
        ndist = dist + 1

        if (nh,nw) in queued:
            continue
        if not(0 <= nh < H) or not(0 <= nw < W):
            continue
        if sss[nh][nw]:
            continue

        dq.append((nh, nw, ndist))
        queued.add((nh, nw))

if fdist == -1:
    print(-1)
else:
    print(H * W - sum(sum(sss,[])) - fdist - 1)

Solution (Python):
from collections import defaultdict, deque
hwsss = [s.rstrip() for s in open(0)]
H,W = map(int, hwsss[0].split())
sss = [[int(c=='

dhw = [
    [0, 1],
    [1, 0],
    [0, -1],
    [-1, 0],
]


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

queued = {(0, 0)}

fdist = -1
while dq:
    h, w, dist = dq.popleft()
    
    if h == H - 1 and w == W - 1:
        fdist = dist
        break
        
    for dh, dw in dhw:
        nh = h + dh
        nw = w + dw
        ndist = dist + 1

        if (nh,nw) in queued:
            continue
        if not(0 <= nh < H) or not(0 <= nw < W):
            continue
        if sss[nh][nw]:
            continue

        dq.append((nh, nw, ndist))
        queued.add((nh, nw))

if fdist == -1:
    print(-1)
else:
    print(H * W - sum(sum(sss,[])) - fdist - 1)

Solution (Python):
from collections import deque
printn = lambda x: print(x,end='')
inn = lambda : int(input())
inl   = lambda: list(map(int, input().split()))
inm   = lambda:      map(int, input().split())
ins = lambda : input().strip()
DBG = True 
BIG = 10**18
R = 10**9 + 7


def ddprint(x):
  if DBG:
    print(x)

h,w = inm()
s = []
nb = 0
for i in range(h):
    ss = ins()
    s.append(ss)
    nb += ss.count('
q = deque([(0,0)])
d = [[BIG]*w for i in range(h)]
d[0][0] = 0
while len(q)>0:
    x,y = q.popleft()
    dd = d[x][y]
    for dx,dy in [(0,1),(0,-1),(1,0),(-1,0)]:
        xx = x+dx
        yy = y+dy
        if 0<=xx<h and 0<=yy<w and s[xx][yy]=='.' and d[xx][yy]>dd+1:
            d[xx][yy] = dd+1
            q.append((xx,yy))
z = d[h-1][w-1]
print(-1 if z==BIG else (h*w-nb-z-1))

Solution (Python):
def neighbor(i, j):
    dxy4 = [(0, 1), (-1, 0), (0, -1), (1, 0)]
    neighL = []
    for dxy in dxy4:
        ni, nj = i+dxy[0], j+dxy[1]
        if 0<= ni < H and 0<= nj < W:
            if map_[ni][nj] =='.':
                neighL.append((ni, nj))
    return neighL
            
def bfs(start, goal):
    from collections import deque
    WHITE, GRAY, BLACK, INF = 0, 1, 2, float('inf')
    
    color = [[WHITE]*W for _ in range(H)]
    d = [[INF]*W for _ in range(H)]
    
    i0, j0 = start
    i1, j1 = goal
    depth = 0
    color[i0][j0] = GRAY
    d[i0][j0] = depth + 1
    Q = deque([(i0, j0)])
    while Q:
        i, j = Q.popleft()
        depth = d[i][j]
        for ni, nj in neighbor(i, j):
            if color[ni][nj] == WHITE:
                color[ni][nj] = GRAY
                d[ni][nj] = depth + 1
                Q.append((ni, nj))
        color[i][j] = BLACK
    return d[i1][j1]


H, W = map(int, input().split())
map_ =  [list(input().strip()) for _ in range(H)]   
n_open = sum([map_[i].count('.') for i in range(H)])
start, goal = (0, 0), (H-1, W-1)
min_d = bfs(start, goal)
if min_d == float('inf'):
    print(-1)
else:
    print(n_open - min_d)

Solution (Python):

H, W = map(int, input().split())
map = [list(input()) for i in range(H)]
cost_map =  [[None]*W for i in range(H)]
whites = 0
for i in range(H):
    for j in range(W):
        if map[i][j]==".":
            whites += 1

queue = list()
queue.append([0, 0])
cost_map[0][0] = 0
while queue:
    x,y = queue.pop(0)
    if x==H-1 and y==W-1:break
    current = cost_map[x][y]
    if 0<=x+1<H:
        if cost_map[x+1][y] is None and map[x+1][y]==".":
            queue.append([x+1, y])
            cost_map[x+1][y] = current + 1
    if 0<=x-1<H:
        if cost_map[x-1][y] is None and map[x-1][y]==".":
            queue.append([x-1, y])
            cost_map[x-1][y] = current + 1
    if 0<=y+1<W:
        if cost_map[x][y+1] is None and map[x][y+1]==".":
            queue.append([x, y+1])
            cost_map[x][y+1] = current + 1
    if 0<=y-1<W:
        if cost_map[x][y-1] is None and map[x][y-1]==".":
            queue.append([x, y-1])
            cost_map[x][y-1] = current + 1

if cost_map[H-1][W-1] is None:
    print("-1")
else:
    print(whites - cost_map[H-1][W-1]-1)

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

from collections import deque

def bfs():
    seen = [[float('inf')]*W for _ in range(H)]
    que = deque([(0,0)])
    seen[0][0] = 0
    while que:
        a,b = que.popleft()
        if a==W-1 and b==H-1:
            break
        for x,y in [[0,1],[1,0],[0,-1],[-1,0]]:
            nx = x + a
            ny = y + b
            if 0<=nx<W and 0<=ny<H and masu[ny][nx]!='
                que.append((nx,ny))
                seen[ny][nx] = seen[b][a]+1
    return seen[H-1][W-1]
saitan = bfs()
count = 0
for h in range(H):
    for w in range(W):
        if masu[h][w] == '
            count += 1
if saitan == float('inf'):
    print(-1)
else:print(H*W-saitan-count-1)

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

sys.setrecursionlimit(1000000)
MOD = 10 ** 9 + 7
input = lambda: sys.stdin.readline().strip()

NI = lambda: int(input())
NMI = lambda: map(int, input().split())
NLI = lambda: list(NMI())
SI = lambda: input()


def main():
    R,C = NMI()
    sy, sx = 0,0
    gy, gx = R-1,C-1
    board = [list(input()) for _ in range(R)]

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

    
    INF = R*C*2
    distance = [[INF for _ in range(C)] for _ in range(R)]

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

    
    distance[sy][sx] = 0
    
    
    shortest = INF

    
    while len(que) != 0:
        
        pop = que.popleft()
        if pop[0]==gy and pop[1]==gx:
            shortest = distance[gy][gx]+1


        
        for i in range(len(dx)):
            
            ny = pop[0]+dy[i]
            nx = pop[1]+dx[i]

            
            if 0<= ny < R and 0 <= nx < C and board[ny][nx]!='
                
                que.append((ny,nx))
                
                distance[ny][nx] = distance[pop[0]][pop[1]]+1
    
    if shortest == INF:
        print(-1)
    else:
        dots = 0
        for r in range(R):
            for c in range(C):
                if board[r][c] == '.':
                    dots += 1
        print(dots-shortest)

if __name__ == '__main__':
    main()

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

h,w=map(int,readline().split())
wb={'
s=[wb[g] for g in read() if g!='\n']
dist=[0]*(h*w)
dist[0]=1
stack=deque([(0,0)])
while stack:
  cg=stack.popleft()
  for i in range(4):
    ng=(cg[0]+(1-2*(i&1))*(i>>1),cg[1]+(1-2*(i&1))*(1-(i>>1)))
    fcg=w*cg[0]+cg[1]
    fng=w*ng[0]+ng[1]
    if 0<=ng[0]<=h-1 and 0<=ng[1]<=w-1 and \
        s[fng] and dist[fng]==0:
      stack.append(ng)
      dist[fng]=dist[fcg]+1
if dist[-1]:
  print(sum(s)-dist[-1])
else:
  print(-1)

Solution (Python):
from collections import deque
h,w=[int(x) for x in input().split()]
c=[]
b=0
for i in range(h):
  C=input()
  b+=C.count("
  c.append(C)

dist=[[0]*w for i in range(h)]
dist[0][0]=1
d=deque()
d.append([0,0])

dydx=[[1,0],[0,1],[-1,0],[0,-1]]

while d:
  y,x=d.popleft()
  if y==h-1 and x==w-1:
    break
  for i in range(4):
    ny,nx=y+dydx[i][0],x+dydx[i][1]
    if not(0 <= ny < h) or not(0 <= nx < w) or dist[ny][nx]!=0 or c[ny][nx]=="
      continue
    dist[ny][nx]=dist[y][x]+1
    d.append([ny,nx])

if dist[h-1][w-1]==0:
  print(-1)
else:
  ans=h*w-b-dist[h-1][w-1]
  print(ans)

Solution (Python):
from collections import deque
h, w = map(int, input().split())
wall = '
maze = [[wall] * (w + 2)]
wn = 0
for y in range(1, h+1):
    maze.append([wall] + [c for c in input()] + [wall])
    for x in range(1, w+1):
        if maze[y][x] == '.':
            wn += 1
maze.append([wall] * (w + 2))

q = deque()
q.append((1, 1, 0))
reachable = False
while q:
    y, x, i = q.popleft()
    if maze[y][x] == '
        continue
    if y == h and x == w:
        reachable = True
        break
    maze[y][x] = '
    i += 1
    q.append((y+1, x, i))
    q.append((y-1, x, i))
    q.append((y, x+1, i))
    q.append((y, x-1, i))
print(wn - i - 1 if reachable else -1)

Solution (Python):
import sys
import math
from collections import defaultdict, deque
from copy import deepcopy
    
input = sys.stdin.readline
def RD(): return input().rstrip()
def F(): return float(input().rstrip())
def I(): return int(input().rstrip())
def MI(): return map(int, input().split())
def MF(): return map(float,input().split())
def LI(): return list(map(int, input().split()))
def LF(): return list(map(float,input().split()))
def Init(H, W, num): return [[num for i in range(W)] for j in range(H)]
    
    
def main():
    H, W = MI()
    d = Init(H, W, -1)
    mylist = [input().rstrip() for i in range(H)]
    move = [[1,0],[0,1],[-1,0],[0,-1]]
    dq = deque()
    dq.append([0,0])
    goal = [H-1,W-1]
    d[0][0] = 0
    while dq:
        ht, wt = dq.popleft()
        for h, w in move:
            h += ht
            w += wt
            if h >= 0 and h < H and w >= 0 and w < W and d[h][w] == -1 and mylist[h][w] != "
                d[h][w] = d[ht][wt]+1
                dq.append([h,w])
                
    goal_dist = d[goal[0]][goal[1]]
    if goal_dist == -1:
        print(-1)
    else:
        white = 0
        for i in mylist:
            white += i.count('.')
        print(white-goal_dist-1)


        
    
if __name__ == "__main__":
    main()

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

input = sys.stdin.readline
digtmp = [(0, 1), (1, 0), (0, -1), (-1, 0)]

def main():
    H, W = map(int, input().split())
    field = []
    white = 0
    for h in range(H):
        tmp = list(input()[:-1])
        white += collections.Counter(tmp)['.']
        field.append(tmp)

    
    field[0][0] = 1
    que = deque([(0, 0)])
    while True:
        fr_x, fr_y = que.popleft()
        cnt = field[fr_x][fr_y]
        for d_x, d_y in digtmp:
            to_x = fr_x + d_x
            to_y = fr_y + d_y
            if 0 <= to_x < H and 0 <= to_y < W:
                if field[to_x][to_y] == '.':
                    field[to_x][to_y] = cnt + 1
                    que.append((to_x, to_y))
                else:
                    continue
        if len(que) == 0:
            break

    goal = field[H-1][W-1]
    if goal in ['.', '
        print(-1)
        return
    ans = white - goal
    print(ans)
    return

if __name__ == "__main__":
    main()

Solution (Python):


import sys
readline = sys.stdin.readline

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

G = [None] * H
white = 0
for i in range(H):
  G[i] = readline().rstrip()
  white += G[i].count(".")

from collections import deque
q = deque([])

q.append([0, 0, 0])
seen = set()
cases = ((0,1),(0,-1),(1,0),(-1,0))
while q:
  y,x,d = q.popleft()
  if G[y][x] == "
    continue
  if (y,x) in seen:
    continue
  seen.add((y,x))
  if y == H - 1 and x == W - 1:
    print(white - d - 1)
    break
  for c in cases:
    if 0 <= y + c[0] < H and 0 <= x + c[1] < W:
      q.append([y + c[0], x + c[1], d + 1])
else:
  print(-1)

Solution (Python):
h,w=map(int,input().split())
m=[]
for _ in range(h): m.append(list(input()))
black=0
white=0
for i in range(h):
    for j in range(w):
        if m[i][j]=="
white=h*w-black
node=[[0,0,1]]
dx,dy=[-1,0,1,0],[0,1,0,-1]
while node:
    temp=node.pop(0)
    if temp[0]==h-1 and temp[1]==w-1:
        print(h*w-black-temp[2])
        exit()
    m[temp[0]][temp[1]]="
    for i in range(4):
        if 0<=temp[0]+dx[i]<h and 0<=temp[1]+dy[i]<w:
            if m[temp[0]+dx[i]][temp[1]+dy[i]]==".":
                node.append([temp[0]+dx[i],temp[1]+dy[i],temp[2]+1])
                m[temp[0]+dx[i]][temp[1]+dy[i]]="
print(-1)

Solution (Python):
import re
import sys
from collections import *
from functools import lru_cache
from heapq import *
from itertools import *

INF=float('inf')

sys.setrecursionlimit(2**31-1)

rfs=lambda:rl().split()
ri=lambda:int(rl())
ris=lambda:list(map(int,rfs()))
rl=lambda:next(sys.stdin)
rls=lambda:list(map(str.strip,sys.stdin))
rs=lambda:rl().strip()
rt=lambda:sys.stdin.read()
rg=lambda:list(list(ln) for ln in rls())

def n4(i,j):
    return [
                (i-1,j),
        (i,j+1),        (i,j-1),
                (i+1,j),
    ]

def n8(i,j):
    return [
        (i-1,j-1),(i-1,j),(i-1,j+1),
        (  i,j-1),        (  i,j+1),
        (i+1,j-1),(i+1,j),(i+1,j+1),
    ]

inb=lambda i,j,m,n:0<=i<m and 0<=j<n



H,W=ris()
s=rg()

nbl=sum(row.count('
s[0][0]='
que=deque([(0,0,1)])
ok=False
while que:
    i,j,k=que.popleft()
    if i+1==H and j+1==W:
        ok=True
        break
    for ni,nj in n4(i,j):
        if inb(ni,nj,H,W) and s[ni][nj]!='
            s[ni][nj]='
            que.append((ni,nj,k+1))

if ok:
    print(H*W-nbl-k)
else:
    print(-1)

Solution (Python):
h,w=map(int,input().split())
A=[]
for i in range(h):
    A.append(list(input()))
kabe=0
for i in range(h):
    for j in range(w):
        if A[i][j]=="
            kabe+=1
def bfs():
    while queue:
        x,y,d=queue.pop()
        
        for i in range(4):
            xx=x+dx[i] ; yy=y+dy[i]
            if xx==h-1 and yy==w-1:
                print(h*w-d-2-kabe);exit()
            if 0<=xx<h and 0<=yy<w and A[xx][yy]==".":
                A[xx][yy]="
                queue.appendleft([xx,yy,d+1])


from collections import deque
dx=[-1,0,1,0] ;dy=[0,1,0,-1]
queue=deque([[0,0,0]])
bfs()
print(-1)

Solution (Python):
from collections import deque
INF=10**18
h,w=map(int,input().split())
e=[input() for _ in range(h)]
cnt=0
for i in range(h):
  for j in range(w):
    if e[i][j]=='.':cnt+=1
dx=[-1,0,1,0]
dy=[0,-1,0,1]
sx,sy=0,0
gx,gy=h-1,w-1
q=deque([(sx,sy)])
d=[[INF]*w for _ in range(h)]
d[sx][sy]=1
while q:
  x,y=q.popleft()
  for i in range(4):
    nx=x+dx[i]
    ny=y+dy[i]
    if 0<=nx<h and 0<=ny<w and e[nx][ny]=='.' and d[nx][ny]==INF:
      q.append((nx,ny))
      d[nx][ny]=d[x][y]+1
if d[gx][gy]==INF:print(-1)
else:print(cnt-d[gx][gy])

Solution (Python):
from collections import deque
H,W = map(int,input().split())
grid = [0] * H
num_black = 0
for i in range(H):
    s = input()
    for j in range(len(s)):
        if s[j] == '
            num_black += 1
    grid[i] = list(s)
time_grid = [[-1] * W for _ in range(H)]
time_grid[0][0] = 0
queue = deque()
queue.append([0,0,0])
while queue:
    y,x,t = queue.popleft()
    for next_y, next_x in [[y+1,x],[y,x+1],[y-1,x],[y,x-1]]:
        if 0 <= next_x < W and 0 <= next_y < H and grid[next_y][next_x] == '.':
            queue.append([next_y,next_x,t+1])
            time_grid[next_y][next_x] = t+1
            grid[next_y][next_x] = '
if time_grid[H-1][W-1] != -1:
    print(H*W-time_grid[-1][-1]-1-num_black)
else:
    print(-1)

Solution (Python):
from collections import deque


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


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

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

Solution (Python):
import collections

h, w = map(int, input().split())
s = []
count = 0
s.append("
for i in range(h):
    temp = input()
    count += temp.count(".")
    s.append("
s.append("
dis = [[float("inf") for i in range(w + 2)] for i in range(h + 2)]
dis[1][1] = 0
p = collections.deque([[1, 1]])
d = [[-1, 0], [1, 0], [0, -1], [0, 1]]
while p:
    temp = p.popleft()
    x, y = temp[0], temp[1]
    for i in d:
        dx, dy = i[0], i[1]
        if s[y + dy][x + dx] == "
            continue
        else:
            if dis[y][x] + 1 < dis[y + dy][x + dx]:
                dis[y + dy][x + dx] = dis[y][x] + 1
                p.append([x + dx, y + dy])
if dis[h][w] == float("inf"):
    print(-1)
else:
    print(count - dis[h][w] - 1)

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

H,W=map(int,input().split())
S=[]
c = []
for i in range(H):
  s = input()
  S.append(s)
  c.extend(list(s))
c = Counter(c)

def bfs(s):
  seen = [[0 for i in range(W)] for j in range(H)]
  total = [[0 for i in range(W)] for j in range(H)]
  todo = deque([])
  now = s
  if S[now[0]][now[1]]=='
  seen[now[0]][now[1]],total[now[0]][now[1]] = 1,0
  todo.append(now)
  while 1:
    if len(todo)==0:break
    now = todo.popleft()
    for d in [(1,0),(-1,0),(0,1),(0,-1)]:
      new = (now[0]+d[0], now[1]+d[1])
      if new[0]<0 or new[0]>=H:continue
      if new[1]<0 or new[1]>=W:continue
      if seen[new[0]][new[1]]==1:continue
      if S[new[0]][new[1]]=='
      seen[new[0]][new[1]] = 1
      todo.append(new)
      total[new[0]][new[1]] = total[now[0]][now[1]] + 1
  return total

d = bfs((0,0))[-1][-1]
if d == 0:
  print(-1)
  exit()
print(c['.']-d-1)

Solution (Python):
import heapq

max_d = 10**9
dest_vecs = [(1,0), (0,1), (-1,0), (0, -1)]

def solve():
    H,W = map(int, input().split())
    
    S = [list(input()) for _ in range(H)]
    wall_num = sum(S_row.count('
    
    
    d = [[max_d]*W for _ in range(H)]
    d[0][0] = 0
    prev = [[None]*W for _ in range(H)]
    heap_queue = [(0,0,0)]
    while heap_queue:
        src_distance,y,x = heapq.heappop(heap_queue)
        for dy,dx in dest_vecs:
            ty = y+dy
            tx = x+dx
            if ty < 0 or ty >= H or tx < 0 or tx >= W or S[ty][tx] == '
                continue
            
            if d[ty][tx] > src_distance+1:
                d[ty][tx] = src_distance+1
                prev[ty][tx] = (y,x)
                heapq.heappush(heap_queue, (src_distance+1, ty, tx))
                
    ret = -1
    if d[H-1][W-1] < max_d:
        ret = H*W-d[H-1][W-1]-wall_num-1
    
    print(ret)
    
solve()

Solution (Python):
import sys,math,collections,itertools
input = sys.stdin.readline

H,W=list(map(int,input().split()))
s = [input().rstrip() for _ in range(H)]
memo = [[0]*W for _ in range(H)]
memo[0][0]=1
q = collections.deque([[0,0]])
while q:
    h,w = q.popleft()
    if h>0 and s[h-1][w]=='.' and memo[h-1][w]==0:
        q.append([h-1,w])
        memo[h-1][w] = memo[h][w] +1
    if h<H-1 and s[h+1][w]=='.' and memo[h+1][w]==0:
        q.append([h+1,w])
        memo[h+1][w] = memo[h][w] +1
    if w>0 and s[h][w-1]=='.' and memo[h][w-1]==0:
        q.append([h,w-1])
        memo[h][w-1] = memo[h][w] +1
    if w<W-1 and s[h][w+1]=='.' and memo[h][w+1]==0:
        q.append([h,w+1])
        memo[h][w+1] = memo[h][w] +1
if memo[H-1][W-1] == 0:
    print(-1)
else:
    cnt = 0
    for i in range(H):
        cnt += s[i].count('
    print(H*W-cnt-memo[H-1][W-1])

Solution (Python):
import collections

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

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

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

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

while q:
    y, x, d = q.popleft()

    if y < 0 or H <= y or x < 0 or W <= x:
        continue

    if s[y][x] == '
        continue

    if dist[y][x] != -1:
        continue

    dist[y][x] = d + 1

    q.append((y + 1, x, d + 1))
    q.append((y - 1, x, d + 1))
    q.append((y, x + 1, d + 1))
    q.append((y, x - 1, d + 1))

if dist[-1][-1] == -1:
    print(-1)
else:
    num_white = sum(block == '.' for row in s for block in row)
    print(num_white - dist[-1][-1])

Solution (Python):
from collections import deque
h,w=map(int,input().split())
c=[list(input()) for _ in range(h)]
dhdw = [[-1,0],[1,0],[0,-1],[0,1]]
min_dis=[[-1]*w for _ in range(h)]
que=deque()
def bfs(x,y):
  que.append([x,y])
  min_dis[x][y]=0
  while que:
    sh,sw=que.popleft()
    for dh,dw in dhdw:
      nh,nw = sh+dh,sw+dw
      if not(0<=nh<=h-1) or not(0<=nw<=w-1) or min_dis[nh][nw]!=-1 or c[nh][nw]=='
        continue
      min_dis[nh][nw]=min_dis[sh][sw]+1
      que.append([nh,nw])
      if [nh,nw]==[h-1,w-1]:
        return min_dis[sh][sw]+1
a=bfs(0,0) or 0
if a==0:
  print(-1)
  exit()
ans=0
for i in c:
  ans+=i.count(".")
print(ans-1-a)