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

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

gh = H - 1
gw = W - 1

S = []
for h in range(H):
    S.append(list(input()))


queue = [(0, 0, 0)]
min_route = 0
while len(queue) > 0:
    (y, x, r) = queue.pop(0)
    if S[y][x] == 'X':
        continue
    S[y][x] = 'X'
    r += 1

    if y == gh and x == gw:
        min_route = r
        break

    
    for (dy, dx) in [(-1, 0), (1, 0), (0, -1), (0, 1)]:
        ny = y + dy
        nx = x + dx
        if ny >= 0 and ny < H and nx >= 0 and nx < W and S[ny][nx] == '.':
            queue.append((ny, nx, r))

if min_route == 0:
    print(-1)
    sys.exit()



white_square = 0
for h in range(H):
    white_square += S[h].count('.')
    white_square += S[h].count('X')


ans = white_square - min_route
print(ans)

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


def bfs(field, d, sx, sy, gx, gy):
    queue = deque([(sx, sy)])
    d[sx][sy] += 1
    
    while queue:
        x, y = queue.popleft()
        if (x, y) == (gx, gy):
            return d[x][y]

        dx = [1, 0, -1, 0]
        dy = [0, 1, 0, -1]
        for i in range(4):
            nx = x + dx[i]
            ny = y + dy[i]
            
            
            if (0 <= nx <= gx and 0 <= ny <= gy
                and field[nx][ny] != "
                and d[nx][ny] == -1):
                d[nx][ny] = d[x][y] + 1
                queue.append((nx, ny))

def main():
    H,W = map(int, readline().split())
    s = [readline() for i in range(H)]

    
    d = [[-1]*W for i in range(H)]

    min_path = bfs(s, d, 0, 0, H-1, W-1)
    if min_path is not None:
        min_path += 1
    else:
        print(-1)
        exit()

    black = 0
    for line in s:
        black += line.count("

    ans = H * W - min_path - black
    print(ans)


if __name__ == "__main__":
    main()

Solution (Python):
H, W = map(int, input().split())
area = [list(input()) for i in range(H)]
def calc(area):
    count = 0
    for i in range(H):
        for j in range(W):
            if area[i][j] == '
                count += 1
    
    return count

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

dh = [1,0,-1,0]
dw = [0,1,0,-1]

while len(que) != 0:
    idx = que.pop(0)
    
    for i in range(4):
        h = idx[0] + dh[i]
        w = idx[1] + dw[i]
        
        if h >= 0 and h < H and w >= 0 and w < W and dist[h][w] == -1 and area[h][w] != '
            que.append([h, w])
            dist[h][w] = dist[idx[0]][idx[1]] + 1
   
neededWhiteNum = dist[H-1][W-1] + 1 
if neededWhiteNum == 0:
    print(-1)
else:
    print(H*W - dist[H-1][W-1] - calc(area) -1)

Solution (Python):
def main():
    from queue import Queue
    h,w=map(int,input().split())
    grid=[list(input())  for i in range(h)]
    dx=[-1,0,1,0]
    dy=[0,1,0,-1]

    q=Queue()
    q.put([0,0])
    inf=10**5
    ans=[[inf]*w for i in range(h)]
    ans[0][0]=1
    while q.qsize()!=0:
        p=q.get()
        ny,nx=p[0],p[1]
        for i in range(4):
            y=ny+dy[i]
            x=nx+dx[i]    
            if 0<=x<w and 0<=y<h and ans[y][x]>10**4:
                if grid[y][x]=='.':
                    ans[y][x]=ans[ny][nx]+1
                    q.put([y,x])
    if ans[h-1][w-1]>10**4:
        print(-1)
    else:
        cnt_white=sum([grid[i].count('.') for i in range(h)])
        print(cnt_white-ans[h-1][w-1])

if __name__=='__main__':
    main()

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

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

white = 0
for m in maze:
    white += m.count(".")

d = [[1,0],[-1,0],[0,1],[0,-1]]
dist = 0
tovisit = deque()
tovisit.append([1,1]); tovisit.append([-1,-1])
visited = []
def BFS(x,y,dist):
    if x == W and y == H:
        return white - dist -1
    tovisit.popleft()
    visited.append([x,y])
    if x == -1 and y == -1:
        dist += 1
        if len(tovisit) == 0:
            return -1
        tovisit.append([-1,-1])
        return BFS(tovisit[0][0],tovisit[0][1],dist)
    for dx,dy in d:
        if maze[y+dy][x+dx] == ".":
            if [x+dx,y+dy] not in visited and [x+dx,y+dy] not in tovisit:
                tovisit.append([x+dx,y+dy])
    return BFS(tovisit[0][0],tovisit[0][1],dist)

print(BFS(1,1,0))

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

load=[]
for i in range(0,H):
    for j in range(0,W):
        if S[i][0][j]=='.':
            load.append((i,j))

ans=0
dp=[[500 for i in range(0,W)] for i in range(0,H)]
dp[0][0]=0
q=[]
q.append((0,0))
sub=[]
while q!=[]:
    while q!=[]:
        x=q[0]
        q.remove(x)
        s=x[0]
        t=x[1]
        if (s+1,t) in load and dp[s+1][t]>dp[s][t]+1:
            sub.append((s+1,t))
            dp[s+1][t]=dp[s][t]+1
        if (s,t+1) in load and dp[s][t+1]>dp[s][t]+1:
            sub.append((s,t+1))
            dp[s][t+1]=dp[s][t]+1
        if (s-1,t) in load and dp[s-1][t]>dp[s][t]+1:
            sub.append((s-1,t))
            dp[s-1][t]=dp[s][t]+1
        if (s,t-1) in load and dp[s][t-1]>dp[s][t]+1:
            sub.append((s,t-1))
            dp[s][t-1]=dp[s][t]+1
        if q==[]:
            q=sub
            sub=[]
            break
if dp[H-1][W-1]==500:
    print(-1)
else:
    print(len(load)-dp[H-1][W-1]-1)

Solution (Python):
from collections import deque
h,w=map(int,input().split())
G=[["
G[0]=["
for i in range(1,h+1):
  G[i]=["
G[h+1]=["
a=0
for i in range(h+2):
  for j in range(w+2):
    if G[i][j]==".":
      a=a+1
B=[[0]*(w+2) for i in range(h+2)]
for i in range(h+2):
  for j in range(w+2):
    if G[i][j]=="
      B[i][j]=1
INF=10**4
A=[[INF]*(w+2) for i in range(h+2)]
C=[-1,1,0,0]
D=[0,0,-1,1]
sx=1
sy=1
gx=h
gy=w
A[sx][sy]=0
E=deque([sx,sy])
while len(E)>0:
  x=E[0]
  E.popleft()
  y=E[0]
  E.popleft()
  for i in range(4):
    if B[x+C[i]][y+D[i]]==0:
      A[x+C[i]][y+D[i]]=A[x][y]+1
      B[x+C[i]][y+D[i]]=1
      E.append(x+C[i])
      E.append(y+D[i])
if A[gx][gy]==INF:
  print(-1)
else:
  print(a-A[gx][gy]-1)

Solution (Python):
import sys
import heapq
import copy
import numpy as np
from collections import deque

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

q=deque([[1,0,0]])

while len(q)>0:
    cnt,hh,ww=deque.popleft(q)

    if hh==h-1 and ww==w-1:
        nblack=np.sum(s=="
        print(h*w-nblack-cnt)
        exit(0)
    for nh,nw in [[hh+dh,ww+dw] for dh,dw in [[1,0],[-1,0],[0,1],[0,-1]]]:
        if 0>nh or nh>=h or 0>nw or nw>=w or d[nh][nw]==1 or s[nh][nw]=='
            continue
        d[nh][nw]=1
        deque.append(q,[cnt+1,nh,nw])

print(-1)

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

def main():
    H,W = map(int,input().split())
    s = [input() for _ in range(H)]
    isVisited = [[0]*W for _ in range(H)]
    queue = deque([(0,0,1)])

    while queue:
        i,j,count = queue.popleft()

        if 0<= i < H and 0<= j < W and isVisited[i][j] == 0 and s[i][j] == ".":
            isVisited[i][j] = count
            for dy,dx in [(0,1),(1,0),(-1,0),(0,-1)]:
                queue.append((i+dy,j+dx,count+1))
    
    wall_count = 0
    for i in range(H):
        wall_count += s[i].count("
    
    if isVisited[-1][-1]:
        print(H*W-wall_count-isVisited[-1][-1])
    else:
        print(-1)
    return


if __name__ == '__main__':
    main()

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

    input = sys.stdin.readline

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

    bk = 0
    for row in s:
        bk += row.count('

    def coods(r, c):
        if r > 0: yield r - 1, c
        if r < h - 1: yield r + 1, c
        if c > 0: yield r, c - 1
        if c < w - 1: yield r, c + 1

    q = deque()
    q.append((0, 0))
    count = [[-1] * w for _ in range(h)]
    count[0][0] = 1
    while q:
        r, c = q.popleft()
        k = count[r][c]
        for nr, nc in coods(r, c):
            nchar = s[nr][nc]
            if nchar == '
            if count[nr][nc] != -1: continue
            count[nr][nc] = k + 1
            if (nr, nc) == (h - 1, w - 1):
                print(h * w - (k + 1) - bk)
                return
            q.append((nr, nc))
    print(-1)


if __name__ == '__main__':
    main()

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

H,W = map(int,readline().split())
maze = []
for _ in range(H):
    maze += [list(readline().rstrip().decode())]

visited = [[-1]*W for _ in range(H)]
def bfs():
    queue = deque([[0,0]])
    visited[0][0] = 0
    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]):
            new_y, new_x = y+j, x+k
            if 0 <= new_y < H and \
                0 <= new_x < W and\
                maze[new_y][new_x] == "." and \
                visited[new_y][new_x] == -1: 
                
                visited[new_y][new_x] = visited[y][x] + 1
                queue.append([new_y, new_x])
    return -1 






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

    print(count-res-1)

Solution (Python):
h,w=map(int,input().split())
inp=["

cnt=0

for _ in range(h):
  temp=input()
  inp.append("
  cnt+=temp.count(".")

inp.append("
result=[[-1 for _ in range(w+2)] for _ in range(h+2)]
result[1][1]=1

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

import queue
q=queue.Queue()
q.put([1,1])


while not q.empty():
  temp=q.get()
  i=0
  while i <len(dx):
    x=temp[1]+dx[i]
    y=temp[0]+dy[i]
   
    
    if inp[y][x]=="." and result[y][x]==-1:
      
    
      q.put([y,x])
      result[y][x]=result[temp[0]][temp[1]]+1
    i+=1
    
if result[h][w]==-1:
  print(-1)
else:
  print(cnt-result[h][w])

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

from collections import deque
dxy = [(0,1),(1,0),(0,-1),(-1,0)]
dist = [[0]*W for i in range(H)]
visited = [[0]*W for i in range(H)]
visited[0][0] = 1
q = deque([(0,0)])
while q:
    x,y = q.popleft()
    for dx,dy in dxy:
        nx,ny = x+dx,y+dy
        if not 0 <= nx < W: continue
        if not 0 <= ny < H: continue
        if visited[ny][nx]: continue
        if S[ny][nx] == '
        visited[ny][nx] = 1
        dist[ny][nx] = dist[y][x] + 1
        q.append((nx,ny))
w = sum(row.count('.') for row in S)
if visited[-1][-1]:
    print(w - 1 - dist[-1][-1])
else:
    print(-1)

Solution (Python):
import queue

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

ans=0
for i in range(H+2):
    for g in range(W+2):
        if c[i][g]==".":
            ans+=1

dist=[[-1]*(W+2) for _ in range(H+2)]
que=queue.Queue()
que.put((1,1))
dist[1][1]=0

while not que.empty():
    h,w=que.get()
    direction=[(0,-1),(0,1),(1,0),(-1,0)]
    for y,x in direction:
        if c[h+y][w+x]=="." and dist[h+y][w+x]==-1:
            que.put((h+y,w+x))
            dist[h+y][w+x]=dist[h][w]+1

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

Solution (Python):
import queue

H, W = map(int, input().split())
s, count = [], 0
for _ in range(H):
    h = list(input())
    count += h.count('.')
    s.append(['
s = [['
around = [[-1, 0], [0, -1], [1, 0], [0, 1]]

ans, que, already = count + 1, queue.Queue(), set([1 + W])
que.put([1, 1, 1])
while not que.empty():
    q = que.get()
    if q[0] == W and q[1] == H:
        ans = q[2]
        break
    else:
        for a in around:
            nextx, nexty = q[0] + a[0], q[1] + a[1]
            if nextx + W*nexty not in already and s[nexty][nextx] == '.':
                que.put([nextx, nexty, q[2] + 1])
                already.add(nextx + W*nexty)

print(count - ans)

Solution (Python):
import queue

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

for i in range(H):
    s[i+1]="
    
s[-1]="

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

q=queue.Queue()
q.put((1,1))
d=[[-1]*(W+2) for _ in range(H+2)]
d[1][1]=0

while not q.empty():
    pos=q.get()
    l=d[pos[0]][pos[1]]
    for i in range(len(dx)):
        nxt=(pos[0]+dx[i],pos[1]+dy[i])
        if d[nxt[0]][nxt[1]]==-1 and s[nxt[0]][nxt[1]]==".":
            d[nxt[0]][nxt[1]]=l+1
            q.put(nxt)
            
use=d[H][W]+1

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



if use!=0:
    print(cnt-use)
else:
    print(-1)

Solution (Python):
from pprint import pprint
INF = 1000000
dx = [1, -1, 0,  0]
dy = [0,  0, 1, -1]

h, w = map(int, input().split())
maze = []
wallcount = 0
for i in range(h):
    l = list(input())
    maze.append(l)
    wallcount += l.count("



wsmap = lambda a, b: (a * w + b)
dp = []

for i in range(h * w):
    dp.append([INF] * (h * w))




goal = -1
dis = 0
import collections
q = collections.deque( [ (0,0,0) ] ) 

while len(q) > 0:
    x, y, d = q.popleft()
    if x == w - 1 and y == h - 1:
        goal = d
    for dir in range(len(dx)):
        nx, ny = x + dx[dir], y + dy[dir]
        if -1 < nx and nx < w and -1 < ny and ny < h:
            if nx == w-1 and ny == h - 1:
                goal = d + 1
                break
            if maze[ny][nx] == ".": 
                maze[ny][nx] = d
                q.append( (nx, ny, d + 1) )

    if goal != -1:
        break


import itertools
if goal == -1:
    print(-1)
else:
    needstep = goal
    res = h * w
    res -= wallcount
    res -= needstep + 1
    print(res)

Solution (Python):
h,w = map(int,input().split())
s = [input() for i in range(h)]
cost = [[2500] * w for i in range(h)]
cost[0][0] = 1
wall = 0
for i in range(h):
  for j in range(w):
    if s[i][j] == '
      wall += 1
for k in range(h*w):
  for i in range(h):
    for j in range(w):
      if s[i][j] != '
        u = cost[i-1][j] + 1 if i > 0 and s[i-1][j] != '
        d = cost[i+1][j] + 1 if i < h-1 and s[i+1][j] != '
        l = cost[i][j-1] + 1 if j > 0 and s[i][j-1] != '
        r = cost[i][j+1] + 1 if j < w-1 and s[i][j+1] != '
        cost[i][j] = min(cost[i][j], u, d, l, r)

if cost[h-1][w-1] == 2500:
  print(-1)
else:
  print(h*w - cost[h-1][w-1] - wall)

Solution (Python):
from collections import deque

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

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

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

reached = [[float('inf') for _ in range(W)] for _ in range(H)]
reached[0][0] = 1

while len(togo):

    h, w = togo[0][0], togo[0][1]
    togo.popleft()

    for d in range(4):
        nh, nw = h + dy[d], w + dx[d]
        if nh < 0 or nw < 0 or nh >= H or nw >= W:
            continue
        if maze[nh][nw] == '
            continue
        if reached[nh][nw] != float('inf'):
            continue
        togo.append((nh, nw))
        reached[nh][nw] = reached[h][w] + 1

if reached[H-1][W-1] == float('inf'):
    print(-1)
else:
    n_wall = 0
    for i in range(H):
        for j in range(W):
            if maze[i][j] == '
                n_wall += 1

    n_road = H * W - n_wall
    print(n_road - reached[H-1][W-1])

Solution (Python):
import sys
from collections import deque
h,w=map(int,input().split())
s=[]
wall_num=0
for i in range(h):
    s.append(list(input()))
    wall_num+=s[i].count("

q=deque()

i=0
j=0
s[0][0]=0
q.appendleft([0,0])
while(len(q)>0):
    qi=q.popleft()
    j,i=qi[0],qi[1]
    num=s[j][i]
    if(i==w-1 and j==h-1):
        print(h*w - wall_num - num - 1)
        sys.exit()
    if(i>0 and s[j][i-1]=="."):
        s[j][i-1]=num+1
        q.append([j,i-1])
    if(i<w-1 and s[j][i+1]=="."):
        s[j][i+1]=num+1
        q.append([j,i+1])
    if(j>0 and s[j-1][i]=="."):
        s[j-1][i]=num+1
        q.append([j-1,i])
    if(j<h-1 and s[j+1][i]=="."):
        s[j+1][i]=num+1
        q.append([j+1,i])

print(-1)

Solution (Python):
import sys
from collections import deque

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



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

G = [list(input()) for _ in range(H)]
INF = 1e10
G2 = [[INF] * W for _ in range(H)]

lst = deque()
lst.append((0, 0, 0))
while lst:
    y, x, v = lst.popleft()
    if G2[y][x] < INF: continue
    G2[y][x] = v
    if y == H - 1 and x == W - 1:
        break

    for a, b in [(-1, 0), (1, 0), (0, 1), (0, -1)]:
        ny = y + a
        nx = x + b
        if 0 <= ny < H and 0 <= nx < W:
            if G[ny][nx] == '.':
                lst.append((ny, nx, v + 1))
if G2[H - 1][W - 1] == INF:
    print(-1)
    exit()

white_cnt = 0
for i in range(H):
    for j in range(W):
        white_cnt += G[i][j] == '.'
print(white_cnt - G2[H-1][W-1]-1)

Solution (Python):
import sys
from collections import deque

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



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

G = [list(input()) for _ in range(H)]
INF = 1e10
G2 = [[INF] * W for _ in range(H)]

lst = deque()
lst.append((0, 0, 0))
while lst:
    y, x, v = lst.popleft()
    if G2[y][x] < INF: continue
    G2[y][x] = v
    if y == H - 1 and x == W - 1:
        break

    for a, b in [(-1, 0), (1, 0), (0, 1), (0, -1)]:
        ny = y + a
        nx = x + b
        if 0 <= ny < H and 0 <= nx < W:
            if G[ny][nx] == '.':
                lst.append((ny, nx, v + 1))
if G2[H - 1][W - 1] == INF:
    print(-1)
    exit()

route_cnt = 0
x, y = W - 1, H - 1
while 1:
    route_cnt += 1
    if x == 0 and y == 0:
        break
    for a, b in [(-1, 0), (1, 0), (0, 1), (0, -1)]:
        ny = y + a
        nx = x + b
        if 0 <= ny < H and 0 <= nx < W:
            if G2[ny][nx] == G2[y][x] - 1:
                x, y = nx, ny
                break

white_cnt = 0
for i in range(H):
    for j in range(W):
        white_cnt += G[i][j] == '.'
print(white_cnt - route_cnt)

Solution (Python):
import sys
from collections import *
import heapq
import math
import bisect
from itertools import permutations,accumulate,combinations,product
from fractions import gcd
def input():
    return sys.stdin.readline()[:-1]
mod=pow(10,9)+7

h,w=map(int,input().split())
s=[input() for i in range(h)]
d=[[1,0],[0,1],[-1,0],[0,-1]]

whitecnt=0
for i in range(h):
    for j in range(w):
        if s[i][j]==".":
            whitecnt+=1
grid=[[0]*w for i in range(h)]
grid[0][0]=1
q=deque([[0,0,1]])

if s[0][0]=="
    print(-1)
    exit()

while q:
    x,y,dist=q.popleft()
    for xd, yd in d:
        if 0<=x+xd<w and 0<=y+yd<h and grid[y+yd][x+xd]==0 and s[y+yd][x+xd]==".":
            if x+xd==w-1 and y+yd==h-1:
                print(whitecnt-(dist+1))
                exit()

            
            grid[y+yd][x+xd]=1
            q.append([x+xd,y+yd,dist+1])

print(-1)

Solution (Python):
import sys
from collections import *
import heapq
import math
import bisect
from itertools import permutations,accumulate,combinations,product
from fractions import gcd
def input():
    return sys.stdin.readline()[:-1]
mod=pow(10,9)+7

h,w=map(int,input().split())
s=[input() for i in range(h)]
d=[[1,0],[0,1],[-1,0],[0,-1]]

whitecnt=0
for i in range(h):
    for j in range(w):
        if s[i][j]==".":
            whitecnt+=1
grid=[[0]*w for i in range(h)]
grid[0][0]=1
q=deque([[0,0,1]])
while q:
    x,y,dist=q.popleft()
    for xd, yd in d:
        if 0<=x+xd<w and 0<=y+yd<h and grid[y+yd][x+xd]==0 and s[y+yd][x+xd]==".":
            if x+xd==w-1 and y+yd==h-1:
                print(whitecnt-(dist+1))
                exit()
            

            grid[y+yd][x+xd]=1
            q.append([x+xd,y+yd,dist+1])

print(-1)

Solution (Python):
import sys
from collections import *
import heapq
import math
import bisect
from itertools import permutations,accumulate,combinations,product
from fractions import gcd
def input():
    return sys.stdin.readline()[:-1]
mod=pow(10,9)+7

h,w=map(int,input().split())
s=[input() for i in range(h)]
d=[[1,0],[0,1],[-1,0],[0,-1]]

whitecnt=0
for i in range(h):
    for j in range(w):
        if s[i][j]==".":
            whitecnt+=1
grid=[[0]*w for i in range(h)]
grid[0][0]=1
q=deque([[0,0,1]])
while q:
    x,y,dist=q.popleft()
    for xd, yd in d:
        if 0<=x+xd<w and 0<=y+yd<h and grid[y+yd][x+xd]==0 and s[y+yd][x+xd]==".":
            if x+xd==w-1 and y+yd==h-1:
                print(whitecnt-(dist+1))
                exit()
            

            grid[y+yd][x+xd]=1
            q.append([x+xd,y+yd,dist+1])

print(-1)

Solution (Python):
import sys
from collections import *
import heapq
import math
import bisect
from itertools import permutations,accumulate,combinations,product
from fractions import gcd
def input():
    return sys.stdin.readline()[:-1]
mod=pow(10,9)+7

h,w=map(int,input().split())
s=[input() for i in range(h)]
d=[[1,0],[0,1],[-1,0],[0,-1]]

whitecnt=0
for i in range(h):
    for j in range(w):
        if s[i][j]==".":
            whitecnt+=1
grid=[[0]*w for i in range(h)]
grid[0][0]=1
q=deque([[0,0,1]])

if s[0][0]=="
    print(-1)
    exit()

while q:
    x,y,dist=q.popleft()
    for xd, yd in d:
        if 0<=x+xd<w and 0<=y+yd<h and grid[y+yd][x+xd]==0 and s[y+yd][x+xd]==".":
            if x+xd==w-1 and y+yd==h-1:
                print(whitecnt-(dist+1))
                exit()

            grid[y+yd][x+xd]=1
            q.append([x+xd,y+yd,dist+1])

print(-1)

Solution (Python):
import sys
from collections import *
import heapq
import math
import bisect
from itertools import permutations,accumulate,combinations,product
from fractions import gcd
def input():
    return sys.stdin.readline()[:-1]
mod=pow(10,9)+7

h,w=map(int,input().split())
s=[input() for i in range(h)]
d=[[1,0],[0,1],[-1,0],[0,-1]]

whitecnt=0
for i in range(h):
    for j in range(w):
        if s[i][j]==".":
            whitecnt+=1
grid=[[0]*w for i in range(h)]
grid[0][0]=1
q=deque([[0,0,1]])

while q:
    x,y,dist=q.popleft()
    for xd, yd in d:
        if 0<=x+xd<w and 0<=y+yd<h and grid[y+yd][x+xd]==0 and s[y+yd][x+xd]==".":
            if x+xd==w-1 and y+yd==h-1:
                print(whitecnt-(dist+1))
                exit()

            grid[y+yd][x+xd]=1
            q.append([x+xd,y+yd,dist+1])

print(-1)

Solution (Python):
def main():
  import sys
  from collections import deque
  
  h,w=map(int,input().split())

  countWhite=0
  maze=[]
  maze+=[["
  for e in sys.stdin.readlines():
    maze+=[["
    countWhite+=e.count(".")
  maze+=[["
  
  xy=[(1,0),(-1,0),(0,1),(0,-1)]
  
  que=deque()
  que.append([1,1,1])
  shortestPath=0
  while(que):
    point=que.popleft()
    x,y,step=point[0],point[1],point[2]

    if (x,y)==(h,w):
      print(countWhite-step)
      break
    if maze[x][y]!=".":
      continue
    maze[x][y]=str(step)
    for i,j in xy:
      que.append([x+i,y+j,step+1])
  else:
    print(-1)

  
if __name__=="__main__":
  main()

Solution (Python):
dy = [0, 0, 1, -1]
dx = [1, -1, 0, 0]


def bfs(start, goal):
    q = [[start]]
    while len(q) > 0:
        path = q.pop(0)
        n = path[len(path) - 1]
        if n == goal:
            return path
        else:
            for sy, sx in zip(dy, dx):
                py = n[0] + sy
                px = n[1] + sx
                if py < 0 or H <= py:
                    continue
                if px < 0 or W <= px:
                    continue
                if S[py][px] == "
                    continue
                if visited[py][px]:
                    continue
                visited[py][px] = True
                x = (py, px)
                if x not in path:
                    new_path = path[:]
                    new_path.append(x)
                    q.append(new_path)
    return None


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

visited = [[False for _ in range(W)] for _ in range(H)]
start = (0, 0)
goal = (H-1, W-1)
ans = bfs(start, goal)
if ans is None:
    print(-1)
    exit()

counter = 0
for i in range(H):
    for j in range(W):
        if (i, j) in ans:
            continue
        if S[i][j] == ".":
            counter += 1
print(counter)

Solution (Python):
n,m = map(int,input().split())
cnt = 0
grid = [list(input()) for i in range(n)]
grid2 = [[]]*n
for i in range(n):
  cnt += "".join(grid[i]).count("
  grid2[i] = ["
  
grid2.insert(0,["
grid2.append(["
grid2[1][1] = 0
loc =[[1,1]]

for k in range(1,n*m):
  next_loc = []
  for y,x in loc:
    for i,j in ([-1,0],[1,0],[0,-1],[0,1]):
      if grid2[y+i][x+j] == ".":
        grid2[y+i][x+j] = k
        next_loc.append([y+i,x+j])
  loc = next_loc

  if [n,m] in loc:
    break

ans = n*m - (k+1+cnt)

print(ans if ans >= 0 else -1)

Solution (Python):
from collections import deque
import numpy as np

H,W = [int(zz) for zz in input().split()]
map = [['

ans = 0
for i in range(1,H+1):
    tmp = input()
    s = list('
    map[i] = s
    ans += tmp.count('

check = [[1]*(W+2) for _ in range(H+2)]
count = [[0]*(W+2) for _ in range(H+2)]
q = deque([(1,1)])
check[1][1] = 0
while q:
    x,y = q.popleft()
    for i,j in [(1,0),(0,1),(-1,0),(0,-1)]:
        if check[x+i][y+j] and map[x+i][y+j] == '.':
            check[x+i][y+j] = 0
            q.append((x+i,y+j))
            count[x+i][y+j] = count[x][y]+1
zz = count[H][W]
if zz == 0:
    print(-1)
else:
    count = set((np.array(count)).flatten())
    for i in count:
        if i > zz:
            ans -= 1
    print(H*W-len(count)-ans)

Solution (Python):
from collections import deque


dis_x = [1, 0, -1, 0]
dis_y = [0, 1, 0, -1]


max_h, max_w = map(int, input().split())

wall_count = 0
s = []
for _ in range(max_h):
    line = input()
    wall_count += line.count("
    
    s.append(list("


s = [list("



dist = [ [0] * (max_w + 2) for _ in range(max_h+2)]

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

while que:
  h, w = que.popleft()

  for i in range(4):
    dx, dy = dis_x[i], dis_y[i]
    if s[h+dy][w+dx] == '.' and dist[h+dy][w+dx] == 0:
      dist[h+dy][w+dx] = dist[h][w] + 1
      que.append((h+dy, w+dx))

result = max_h*max_w - wall_count - dist[max_h][max_w] - 1
if dist[max_h][max_w] == 0:
  print(-1)
else:
  print(result)

Solution (Python):
from collections import deque

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

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


q = deque([])
seen = [[0 for _ in range(w)] for _ in range(h)]
q.append((0, 0, 0))
road = 0
while q:
    y, x, cnt = q.popleft()
    seen[y][x] = 1
    if y == h - 1 and x == w - 1:
        road = cnt + 1
        break
    for ny, nx in zip(dy, dx):
        if 0 <= y + ny < h and 0 <= x + nx < w:
            if seen[y + ny][x + nx] == 0 and m[y + ny][x + nx] == '.':
                seen[y + ny][x + nx] = 1
                
                q.append((y + ny, x + nx, cnt + 1))

if road == 0:
    print(-1)
else:
    print(h * w - road - cnt_sharp)

Solution (Python):
from collections import deque
H, W = [int(x) for x in input().split()]
maze = [input() for i in range(H)]
move = [[0, 1], [0, -1], [1, 0], [-1, 0]]
d = [[float('inf')] * W for i in range(H)]
black = 0
for i in range(H):
    for j in range(W):
        if maze[i][j] == '
            black += 1

def bfs():
    q = deque()
    q.append([0, 0])
    d[0][0] = 0

    while q:
        x, y = q.popleft()
        if x == H - 1 and y == W - 1:
            break
        for v in move:
            nx = x + v[0]
            ny = y + v[1]
            if 0 <= nx < H and 0 <= ny < W and maze[nx][ny] == '.' and d[nx][ny] == float('inf'):
                q.append([nx, ny])
                d[nx][ny] = d[x][y] + 1
    return d[H-1][W-1]

print(-1) if bfs() == float('inf') else print(H*W - black - (bfs() + 1))

Solution (Python):
from collections import deque
H, W = map(int, input().split())
m = [[-1] * (W + 1) for _ in range(H + 1)]
white = 0
for h in range(H):
    for w, c in enumerate(input()):
        if c == ".":
            m[h][w] = 0
            white += 1

gh = H - 1
gw = W - 1
mincount = 0
todo = deque()
todo.append((0, 0))
m[0][0] = 1
while todo:
    h, w = todo.popleft()
    ncount = m[h][w] + 1
    for dh, dw in ((1, 0), (-1, 0), (0, 1), (0, -1)):
        nh = h + dh
        nw = w + dw
        if nh == gh and nw == gw:
            mincount = ncount
            todo.clear()
            break
        if m[nh][nw] == 0:
            m[nh][nw] = ncount
            todo.append((nh, nw))

if mincount > 0:
    print(white - mincount)
else:
    print(-1)

Solution (Python):
import sys
from collections import deque

sys.setrecursionlimit(10**7)

H, W = map(int, input().split())
s = []
black = 0

for i in range(H):
    line = list(input())
    s.append(line)
    black += line.count('

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

q = deque()
dq = deque()
q.append((0, 0))
dq.append(1)

visited = [(0, 0)]
while len(q) != 0:
    pos = q.popleft()
    if pos == (W - 1, H - 1):
        break
    d = dq.popleft()
    for dir in dirs:
        next = (pos[0] + dir[0], pos[1] + dir[1])
        if 0 <= next[0] <= W - 1 and 0 <= next[1] <= H - 1 and \
                next not in visited and s[next[1]][next[0]] == '.':
            q.append(next)
            dq.append(d + 1)
            visited.append(next)
else:
    print(-1)
    sys.exit()

min_d = dq.popleft()
print(H * W - black - min_d)