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):
R, C = map(int, input().split())
c = [list(input()) for _ in range(R)]
d = {}
q = [(0, 0, 0)]
d[0, 0] = 0
while q != []:
    (y, x, z) = q.pop(0)
    for v, w in [(-1, 0), (1, 0), (0, -1), (0, 1)]:
        t = x + v
        u = y + w
        if t < 0 or t >= C or u < 0 or u >= R:
            continue
        if c[u][t] == '.' and (u, t) not in d:
            q.append((u, t, z + 1))
            d[u, t] = z + 1
if (R - 1, C - 1) not in d:
    ans = -1
else:
    ans = R * C - d[R - 1, C - 1] - 1
    for i in c:
        for j in i:
            if j == '
                ans -= 1
print(ans)

Solution (Python):

H,W=map(int,input().split())
MAP=[]
brack=0
for i in range(H):
    line=input()
    brack+=line.count('
    MAP.append([line[j] for j in range(W)])
    

def bfs(H,W,MAP):
    dist=[[-1 for j in range(W)] for i in range(H)]
    dist[0][0]=1
    check=[(0,0)]
    while len(check)>0:
        now=check.pop(0)
        dnow=dist[now[0]][now[1]]
        for x in [(now[0]+1,now[1]),(now[0]-1,now[1]),(now[0],now[1]+1),(now[0],now[1]-1)]:
            if x[0]>=0 and x[1]>=0 and x[0]<H and x[1]<W:
                if x==(H-1,W-1):return dnow+1
                if MAP[x[0]][x[1]]=='.' and dist[x[0]][x[1]]==-1:
                    dist[x[0]][x[1]]=dnow+1
                    check.append(x)
    return dist[H-1][W-1]

ans=bfs(H,W,MAP)
if ans==-1:print(-1)
else:print(H*W-brack-ans)

Solution (Python):
from queue import deque

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

q = deque()
q.append((0,0))
distance = [[-1]*w for _ in range(h)]
distance[0][0] = 0
neighbors = [[0,1],[0,-1],[1,0],[-1,0]]

while q:
    pos_i, pos_j = q.popleft()
    cur_d = distance[pos_i][pos_j]
    for di, dj in neighbors:
        ni, nj = pos_i+di, pos_j+dj
        if not(0<=ni<h and 0<=nj<w):
            continue
        elif state[ni][nj]=='.' and distance[ni][nj]<0:
            distance[ni][nj] = cur_d+1
            q.append((ni,nj))

if distance[h-1][w-1] == -1:
    print(-1)
    exit()

n_white = sum(state[i].count('.') for i in range(h))
print(n_white-distance[h-1][w-1]-1)

Solution (Python):
from collections import deque

h,w = map(int, input().split())
adj = deque(maxlen=h*w)
maze = [list(input()) for _ in range(h)]

inf = 999999
dist = [[inf]*w for _ in range(h)]
max = h*w
for l in maze:
    max -= l.count('



def bfs(i,j):
    if maze[i][j]=='
        return
    maze[i][j]='
    d=dist[i][j] + 1
    if i+1<h:
        if maze[i+1][j]!='
            adj.append([i+1,j])
            dist[i+1][j] = d
    if j+1<w:
        if maze[i][j+1]!='
            adj.append([i,j+1])
            dist[i][j+1] = d
    if i-1>=0:
        if maze[i-1][j]!='
            adj.append([i-1,j])
            dist[i-1][j] = d
    if j-1>=0:
        if maze[i][j-1]!='
            adj.append([i,j-1])
            dist[i][j-1] = d

def print_maze(lst):
    for l in lst:
        print(l)
    print('\n')

adj.append([0,0])
dist[0][0]=1
time=0
while len(adj)>0:
    p = adj.popleft()
    bfs(p[0],p[1])
if dist[h-1][w-1] == inf:
    print(-1)
else:
    print(max - dist[h-1][w-1])

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

H, W = [int(x) for x in input().split()]
G = []
B = 0

G.append('
for i in range(H):
    s = input()
    B += s.count('.')
    G.append(['
G.append('

que = [(1, 1, 1)]
ans = -1

while que:
    y, x, c = que.pop(0)
    if (y, x) == (H, W):
        ans = c
        break
    for dir in DIR:
        ny = y + dir[0]
        nx = x + dir[1]
        if G[ny][nx] == '.':
            G[ny][nx] = '
            que.append((ny, nx, c + 1))

print(B - ans if ans != -1 else -1)

Solution (Python):


from collections import deque

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

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

F = []
nW = 0
for _ in range(H):
    F.append(list(input()))
    nW += sum([1 for s in F[-1] if s == '.'])

ans = -1
q = deque()
q.append((0, 0, 1))
F[0][0] = 'V' 

while q:
    y, x, count = q.popleft()
    if y == H - 1 and x == W - 1:
        ans = nW - count
        break
    for n in neig:
        ny, nx = y + n[0], x + n[1]
        if 0 <= ny < H and 0 <= nx < W:
            if F[ny][nx] == '.':
                q.append((ny, nx, count + 1))
                F[ny][nx] = 'V' 

print(ans)

Solution (Python):
h, w = map(int, input().split())
s = []
for j in range(h):
  s.append(list(map(str, input())))
  
def check(x, y):
  if x >= h or x < 0 or y >= w or y < 0:
    return False
  if s[x][y] ==  ".":
    return True
  else:
    return False

phase = 1
queue = [[0,0]]
while len(queue) > 0:
  tmp = []
  for q in queue:
    s[q[0]][q[1]] = phase
    if check(q[0] + 1, q[1]):
      tmp.append([q[0] + 1, q[1]])
    if check(q[0] - 1, q[1]):
      tmp.append([q[0] - 1, q[1]])
    if check(q[0], q[1] + 1):
      tmp.append([q[0], q[1] + 1])
    if check(q[0], q[1] - 1):
      tmp.append([q[0], q[1] - 1])
  queue = list(map(list, set(map(tuple, tmp)))) 
  phase += 1
count = 0
for i in range(h):
  count += s[i].count("
if s[h-1][w-1] == ".":
  print(-1)
else:
  print(h*w - count - s[h-1][w-1])

Solution (Python):


from collections import deque
H,W = map(int,input().split())
grid = [[""]*W for i in range(H)]
visited = [[0]*W for i in range(H)]
visited[0][0] = 1
white = 0

for i in range(H):
    s = input()
    for j in range(W):
        grid[i][j] = s[j]
        if grid[i][j] == ".":
            white += 1

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

while q:
    i,j = q.popleft()
    if (i,j) == (H-1,W-1):
        break
    for di,dj in d:
        ni = i+di; nj = j+dj
        if 0 <= ni <= H-1 and 0 <= nj <= W-1\
             and visited[ni][nj] == 0 and grid[ni][nj] == ".":
            visited[ni][nj] = visited[i][j] + 1
            np = [ni,nj]
            q.append(np)
if visited[H-1][W-1] > 0:
    ans = white - visited[H-1][W-1]
else:
    ans = -1
print(ans)

Solution (Python):


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


d[0][0] = 0

queue = []
queue.append([0, 0])

while len(queue) > 0:
    p = queue.pop(0)
    y, x = p[0], p[1]

    dx4 = [0, 0, 1, -1]
    dy4 = [1, -1, 0, 0]

    for dx, dy in zip(dx4, dy4):
        next_y = y + dy
        next_x = x + dx
        if 0 <= next_y < H and 0 <= next_x < W and s[next_y][next_x] != "
            d[next_y][next_x] = d[y][x] + 1
            queue.append([next_y, next_x])

count = 0
for l in s:
    count += l.count(".")

if d[H-1][W-1] == -1:
    print(-1)
else:
    print(count - d[H-1][W-1] - 1)

Solution (Python):


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


d[0][0] = 0

queue = []
queue.append([0, 0])

while len(queue) > 0:
    p = queue.pop(0)
    y, x = p[0], p[1]

    dx4 = [0, 0, 1, -1]
    dy4 = [1, -1, 0, 0]

    for dx, dy in zip(dx4, dy4):
        next_y = y + dy
        next_x = x + dx
        if 0 <= next_y < H and 0 <= next_x < W and s[next_y][next_x] != "
            d[next_y][next_x] = d[y][x] + 1
            queue.append([next_y, next_x])

count = 0
for l in s:
    for c in l:
        if c == ".":
            count += 1

if d[H-1][W-1] == -1:
    print(-1)
else:
    print(count - d[H-1][W-1] - 1)

Solution (Python):
from queue import Queue

inf = 10 ** 20

def bfs(H, W, s):
    d = [[inf for i in range(W)] for j in range(H)]
    q = Queue()

    d[0][0] = 1
    q.put([0, 0])

    dx = (0, -1, 1, 0)
    dy = (-1, 0, 0, 1)

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

    return d[H-1][W-1]

H, W = map(int, input().split())
s = []
wnum = 0
for i in range(H):
    s.append(input())
    for j in range(W):
        if(s[i][j] == "."):
            wnum += 1
d = bfs(H, W, s)
if(d == inf):
    print("-1")
else:
    print(wnum - d)

Solution (Python):
from collections import deque
h,w=map(int, input().split())
sy,sx=1,1
gy,gx=h,w
cnt=0
delta=[[1,0],[0,1],[-1,0],[0,-1]]
m=[]
d=[[float('inf')]*(w+2) for _ in range(h+2)]
d[sy][sx]=1
a=['
m.append(a)
for i in range(h):
    a='
    a+=input()
    a+='
    cnt+=a.count('.')
    m.append(a)
a=['
m.append(a)
q=deque()
q.append((sy,sx))
while len(q)>0:
    y,x=q.popleft()
    if y==gy and x==gx:
        break
    for dx,dy in delta:
        if d[y+dy][x+dx]==float('inf') and m[y+dy][x+dx]=='.':
            q.append((y+dy,x+dx))
            d[y+dy][x+dx]=d[y][x]+1
if d[gy][gx]==float('inf'):
    print(-1)
else:
    print(cnt-d[gy][gx])

Solution (Python):
from collections import deque

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


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


kuro = 0
for row in masu:
    for s in row:
        if s == '
            kuro += 1



que = deque([(0, 0, 0)])
move = [(1, 0), (-1, 0), (0, 1), (0, -1)]
visited = [[False for _ in range(W)] for _ in range(H)]



while (que):
    i, j, cost = que.popleft()
    

    visited[j][i] = True
    if (j == H - 1) and (i == W - 1):
        break
    for movex, movey in move:
        tmpx, tmpy = i + movex, j + movey
        

        
        if not(tmpx in range(W)) or not(tmpy in range(H)):
            continue

        if (masu[tmpy][tmpx] == '.') and not(visited[tmpy][tmpx]):
            que.append((i + movex, j + movey, cost + 1))
            visited[tmpy][tmpx] = True
else:
    print(-1)
    exit()

print(H * W - kuro - cost - 1)

Solution (Python):


inf = 10 ** 20

def bfs(H, W, s):
    d = [[inf for i in range(W)] for j in range(H)]
    q = []

    d[0][0] = 1
    q.append([0, 0])

    dx = (0, -1, 1, 0)
    dy = (-1, 0, 0, 1)

    while q:
        p = q.pop()
        x, y = p[0], p[1]
        for i in range(4):
            nx = x + dx[i]
            ny = y + dy[i]
            if(nx >= 0 and nx < H and ny >= 0 and ny < W):
                if(s[nx][ny] == '.' and d[x][y] + 1 < d[nx][ny]):
                    d[nx][ny] = d[x][y] + 1
                    q.append([nx, ny])

    return d[H-1][W-1]

H, W = map(int, input().split())
s = []
wnum = 0
for i in range(H):
    s.append(input())
    for j in range(W):
        if(s[i][j] == "."):
            wnum += 1
d = bfs(H, W, s)
if(d == inf):
    print("-1")
else:
    print(wnum - d)

Solution (Python):

from collections import deque
import sys
sys.setrecursionlimit(10**9)
input = sys.stdin.readline


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

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



dp = [[float('inf')]*W for _ in range(H)]


def check_in(x, y):
    return 0 <= x < W and 0 <= y < H


def bfs():
    dx = [1, -1, 0, 0]
    dy = [0, 0, 1, -1]
    Q = deque([[0, 0]])
    dp[0][0] = 0

    while Q:
        s = Q.popleft()
        if s[0] == H-1 and s[1] == W-1:
            return
        else:
            s_x = s[1]
            s_y = s[0]
            for x, y in zip(dx, dy):
                n_x = s_x+x
                n_y = s_y+y

                if check_in(n_x, n_y):
                    if grid[n_y][n_x] != "
                        Q.append([n_y, n_x])
                        dp[n_y][n_x] = dp[s_y][s_x]+1


def solve():
    bfs()
    min_dist = dp[H-1][W-1]
    if min_dist == float('inf'):
        return -1
    else:
        return cnt - min_dist-1


print(solve())

Solution (Python):
from collections import deque

h, w = map(int, input().split())
mp = ["
white = 0
for y in range(h + 2):
    white += mp[y].count(".")
vec = ((1, 0), (0, -1), (-1, 0), (0, 1))
que = deque()
que.append((1, 1, 1))
visited = [[False] * (w + 2) for _ in range(h + 2)]
visited[1][1] = True
while que:
    score, x, y = que.popleft()
    if (x, y) == (w, h):
        print(white - score)
        break

    for dx, dy in vec:
        nx, ny = x + dx, y + dy
        if mp[ny][nx] != "
            que.append((score + 1, nx, ny))
            visited[ny][nx] = True
else:
    print(-1)

Solution (Python):
h, w = list(map(int, input().split()))
li = []
for _ in range(h):
    li.append(input())


from collections import defaultdict
edges = defaultdict(list)
for i in range(h):
    for j in range(w):
        idx = i * w + j
        if li[i][j] == '.':
            if i + 1 < h and li[i + 1][j] == '.':
                edges[idx].append(idx + w)
                edges[idx + w].append(idx)
            if j + 1 < w and li[i][j + 1] == '.':
                edges[idx].append(idx + 1)
                edges[idx + 1].append(idx)
goal = h * w - 1

from collections import deque
Q = deque()
Q.append(0)
reach = False
visited = {0}
pre = {0: None}
while len(Q) > 0:
    u = Q.popleft()
    if u == goal:
        reach = True
        break
    for v in edges[u]:
        if v not in visited:
            pre[v] = u
            visited |= {v}
            Q.append(v)

ans = -1
if reach:
    white = sum(a.count('.') for a in li)
    path = [goal]
    while True:
        path.append(pre[path[-1]])
        if pre[path[-1]] is None:
            break
    ans = white - len(path)

print(ans)

Solution (Python):
from collections import deque
H, W = map(int, input().split())
con = [[1,0],[0,1],[-1,0],[0,-1]]
m=[]
c = 0
d = [[0]*(W+2) for _ in range(H+2)]
d[1][1]= 1
m.append("
for i in range(H):
    b = input()
    c +=b.count(".")
    a= "
    m.append(a)
q = deque()
m.append("
q.append((1,1))

while len(q)>0:
    y,x = q.popleft()
    if y == H and x == W:
        print(c-d[H][W])
        exit()
    for dx,dy in con:
        
        if d[y+dy][x+dx] == 0 and m[y+dy][x+dx] ==".":
            q.append((y+dy,x+dx))
            d[y+dy][x+dx]+=d[y][x]+1
    
print(-1)

Solution (Python):
from collections import deque

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

def bfs(i,j):
  visited = [[-1]*w for i in range(h)]
  que = deque()
  que.append([i,j])
  visited[i][j]=0
  
  while True:
    if not que:
      return -1
    
    [current_i,current_j] = que.popleft()
    
    if  current_i == h-1 and current_j == w-1:
      return visited[current_i][current_j]
  
    for next in [[-1,0],[+1,0],[0,-1],[0,+1]]:
      next_i = current_i + next[0]
      next_j = current_j + next[1]
      if 0<=next_i<h and 0<=next_j<w:
        if visited[next_i][next_j] == -1 and s[next_i][next_j]==".":
          visited[next_i][next_j] = visited[current_i][current_j]+1
          que.append([next_i,next_j])

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


if bfs(0,0)==-1:
  print(-1)
else:
  print(count_point-bfs(0,0)-1)

Solution (Python):
def bfs_min(w,h,data):
    queue = [[0,0]]
    check = [[0,0]]
    memo = [[0 for j in range(w)] for i in range(h)]
    while True:
        if len(queue) != 0:
            s = queue[0]
            hNow,wNow = s[0],s[1]
        else:
            return -1

        if hNow == H-1 and wNow == W-1:
            return memo[H-1][W-1]
        queue.pop(0)

        if hNow < h-1:
            if (data[hNow+1][wNow] == '.') and ([hNow+1,wNow] not in check):
                queue.append([hNow+1,wNow])
                check.append([hNow+1,wNow])
                memo[hNow+1][wNow] = memo[hNow][wNow] + 1

        if wNow < w-1:
            if (data[hNow][wNow+1] == '.') and ([hNow,wNow+1] not in check):
                queue.append([hNow,wNow+1])
                check.append([hNow,wNow+1])
                memo[hNow][wNow+1] = memo[hNow][wNow] + 1

        if hNow > 0:
            if (data[hNow-1][wNow] == '.') and ([hNow-1,wNow] not in check):
                queue.append([hNow-1,wNow])
                check.append([hNow-1,wNow])
                memo[hNow-1][wNow] = memo[hNow][wNow] + 1

        if wNow > 0:
            if (data[hNow][wNow-1] == '.') and ([hNow,wNow-1] not in check):
                queue.append([hNow,wNow-1])
                check.append([hNow,wNow-1])
                memo[hNow][wNow-1] = memo[hNow][wNow] + 1
        
        
            
    
    
    
    





H,W = list(map(int,input().split()))
s = [list(input()) for i in range(H)]
wh = 0
bl = 0
for i in range(H):
    for j in range(W):
        if s[i][j] == '.':
            wh += 1
        else:
            bl += 1

if bfs_min(W,H,s) >= 0:
    print(wh - bfs_min(W,H,s) - 1)
else:
    print(-1)

Solution (Python):
import queue


class HW(object):
    def __init__(self, height: int, width: int):
        self.h = height
        self.w = width


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

cnt = 0
visited = [[0] * w for j in range(h)]


def bfs() -> int:
    q = queue.Queue()
    start = HW(0, 0)
    goal = HW(h - 1, w - 1)
    q.put([start.h, start.w])
    visited[start.h][start.w] = 1

    while q.qsize() > 0:
        tmp = q.get()
        now = HW(tmp[0], tmp[1])
        if now.h == goal.h and now.w == goal.w:
            return cnt - visited[now.h][now.w]

        for k in [(-1, 0), (1, 0), (0, 1), (0, -1)]:
            nxt = HW(now.h + k[0], now.w + k[1])
            if not 0 <= nxt.h < h or not 0 <= nxt.w < w:
                continue
            elif maze[nxt.h][nxt.w] == '
                continue
            elif visited[nxt.h][nxt.w] == 0:
                q.put([nxt.h, nxt.w])
                visited[nxt.h][nxt.w] = visited[now.h][now.w] + 1
    return -1


def main() -> None:
    global cnt
    for i in range(h):
        cnt += maze[i].count('.')

    cnt = bfs()
    print(cnt)


if __name__ == "__main__":
    main()

Solution (Python):
H,W=map(int,input().split())
white=0
S=[]
for _ in range(H):
    s=list(input())
    white+=s.count('.')
    S.append(s)

f=[[0 for i in range(W)] for j in range(H)]

def path(i,j):
    q=[]
    for k in [1,-1]:
        if 0<=i+k<H and f[i+k][j]==0 and S[i+k][j]=='.':
            q.append((i+k,j))
        if 0<=j+k<W and f[i][j+k]==0 and S[i][j+k]=='.':
            q.append((i,j+k))
    return q

flag=False
if S[0][0]=='.' and S[-1][-1]=='.':
    que = path(0,0)
else:
    que = []
f[0][0]=1

l=1
while len(que)>0 and flag==False:
    l+=1
    tmp=[]
    for q in que:
        if f[q[0]][q[1]]==0:
            tmp+=path(*q)
            f[q[0]][q[1]]=1
            if q==(H-1,W-1):
                flag=True
        que=tmp

if flag:
    print(white-l)
else:
    print(-1)

Solution (Python):
from collections import deque

INF = float('inf')

dr = (-1, 0, 0, 1)
dc = (0, -1, 1, 0)

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

s = []
total_white_count = 0
for _ in range(H):
    t = input()
    s.append(t)
    total_white_count += t.count('.')
p = [[INF for _ in range(W)] for _ in range(H)]

ans = -1

dq = deque()
dq.append((0, 0, 1))
while dq:
    r, c, d = dq.popleft() 

    nd = d + 1
    for i in range(4):
        nr = r + dr[i]
        nc = c + dc[i]
        if not (0 <= nr < H and 0 <= nc < W): continue
        if s[nr][nc] == '
        if p[nr][nc] <= nd: continue
        p[nr][nc] = nd
        if nr == H - 1 and nc == W - 1:
            ans = total_white_count - nd
            break
        dq.append((nr, nc, nd))
    else:
        continue
    break

print(ans)

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

water=[[0]*w for _ in range(h)]
water[0][0]=1
a_index=[]
a_column=[]
a_index.append(0)
a_column.append(0)
b=[]
count=0

for i in range(h):
    for j in range(w):
        if s[i][j] == '
            water[i][j]=3000
            count+=1
while water[h-1][w-1]==0:
    for i,j in zip(a_index,a_column):
        if water[i][j]==1:
            if i>0:
                if water[i-1][j]==0:
                    water[i-1][j]+=1
                    b.insert(0,[i-1,j])
            if i<h-1:
                if water[i+1][j]==0:
                    water[i+1][j]+=1
                    b.insert(0,[i+1,j])
            if j>0:
                if water[i][j-1]==0:
                    water[i][j-1]+=1
                    b.insert(0,[i,j-1])
            if j<w-1:
                if water[i][j+1]==0:
                    water[i][j+1]+=1
                    b.insert(0,[i,j+1])
        water[i][j]+=1

    a_index+=[x[0] for x in b]
    a_column+=[x[1] for x in b]

    if not b:
        print(-1)
        exit()
    b=[]

print(h*w-water[0][0]-count)

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

water=[[0]*w for _ in range(h)]
water[0][0]=1
a_index=[]
a_column=[]
a_index.append(0)
a_column.append(0)
b=[]
count=0

for i in range(h):
    for j in range(w):
        if s[i][j] == '
            water[i][j]=3000
            count+=1
while water[h-1][w-1]==0:
    for i,j in zip(a_index,a_column):
        if water[i][j]==1:
            if i>0:
                if water[i-1][j]==0:
                    water[i-1][j]+=1
                    b.insert(0,[i-1,j])
            if i<h-1:
                if water[i+1][j]==0:
                    water[i+1][j]+=1
                    b.insert(0,[i+1,j])
            if j>0:
                if water[i][j-1]==0:
                    water[i][j-1]+=1
                    b.insert(0,[i,j-1])
            if j<w-1:
                if water[i][j+1]==0:
                    water[i][j+1]+=1
                    b.insert(0,[i,j+1])
        water[i][j]+=1

    a_index+=[x[0] for x in b]
    a_column+=[x[1] for x in b]

    if not b:
        print(-1)
        exit()
    b=[]

print(h*w-water[0][0]-count)

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

water=[[0]*w for _ in range(h)]
water[0][0]=1
a_index=[]
a_column=[]
a_index.append(0)
a_column.append(0)
b=[]
count=0

for i in range(h):
    for j in range(w):
        if s[i][j] == '
            water[i][j]=3000
            count+=1
while water[h-1][w-1]==0:
    for i,j in zip(a_index,a_column):
        if water[i][j]==1:
            if i>0:
                if water[i-1][j]==0:
                    water[i-1][j]+=1
                    b.insert(0,[i-1,j])
            if i<h-1:
                if water[i+1][j]==0:
                    water[i+1][j]+=1
                    b.insert(0,[i+1,j])
            if j>0:
                if water[i][j-1]==0:
                    water[i][j-1]+=1
                    b.insert(0,[i,j-1])
            if j<w-1:
                if water[i][j+1]==0:
                    water[i][j+1]+=1
                    b.insert(0,[i,j+1])
        water[i][j]+=1

    a_index+=[x[0] for x in b]
    a_column+=[x[1] for x in b]

    if not b:
        print(-1)
        exit()
    b=[]

print(h*w-water[0][0]-count)

Solution (Python):
from queue import Queue

inf = 10 ** 20

def bfs(H, W, s):
    d = [[inf for i in range(W)] for j in range(H)]
    q = Queue()

    d[0][0] = 1
    q.put([0, 0])

    dx = (0, -1, 1, 0)
    dy = (-1, 0, 0, 1)

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

    return d[H-1][W-1]

H, W = map(int, input().split())
s = []
wnum = 0
for i in range(H):
    s.append(input())
    for j in range(W):
        if(s[i][j] == "."):
            wnum += 1
d = bfs(H, W, s)
if(d == inf):
    print("-1")
else:
    print(wnum - d)

Solution (Python):
import queue


def func(R, C, c, queue):
    
    sy, sx = [1, 1]
    gy, gx = [R, C]
    score = R * C
    for i in range(1, R + 1):
        for j in range(1, C + 1):
            if c[i][j] == "
                score -= 1

    queue.put([sy, sx])
    visited = [[-1 for i in range(len(c[0]))] for i in range(len(c))]
    count = 0

    def search(sy, sx, queue, visited):
        if c[sy][sx] != "
            queue.put([sy, sx])
            visited[sy][sx] = 1
        return

    while 1:
        size = queue.qsize()
        if size == 0:
            return -1
        for i in range(size):
            [sy, sx] = queue.get()
            visited[sy][sx] = count
            if sy == gy and sx == gx:
                return score - count - 1
            search(sy + 1, sx, queue, visited)
            search(sy - 1, sx, queue, visited)
            search(sy, sx + 1, queue, visited)
            search(sy, sx - 1, queue, visited)
        count += 1


R, C = [int(i) for i in input().split()]
c = [["
for i in range(1, R + 1):
    c[i][1:-1] = input()
print(func(R, C, c, queue.Queue()))
"""

print(func(3, 3, [['
print(func(10, 37, [['
"""

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

cnt = Counter(reduce(add, s))

queue = deque()
depth = [[-1]*W for _ in range(H)]
dx = [1, -1, 0, 0]
dy = [0, 0, 1, -1]


def bfs():
    
    
    queue.append((0, 0))
    depth[0][0] = 1
    while queue:
        x, y = queue.popleft()
        for i in range(4):
            nx = dx[i] + x
            ny = dy[i] + y
            if nx < 0 or nx >= W or ny < 0 or ny >= H:
                continue
            if depth[ny][nx] != -1:
                continue
            if nx == W-1 and ny == H-1:
                depth[ny][nx] = depth[y][x] + 1
                return True
            if s[ny][nx] == '.':
                depth[ny][nx] = depth[y][x] + 1
                queue.append((nx, ny))
    return False

if bfs():
    print(H*W-depth[H-1][W-1]-cnt['
else:
    print(-1)

Solution (Python):
def main():
    h, w = map(int, input().split())
    matrix = [list(input()) for _ in range(h)]

    stack = [(0, 0)]
    diffs = ((0, 1), (1, 0), (0, -1), (-1, 0))
    distance = [[float('inf')] * w for _ in range(h)]
    distance[0][0] = 1
    while stack:
        x, y = stack.pop()
        for dx, dy in diffs:
            nx, ny = x + dx, y + dy
            if 0 <= nx < h and 0 <= ny < w \
                           and matrix[nx][ny] == '.' \
                           and distance[x][y] + 1 < distance[nx][ny]:
                distance[nx][ny] = distance[x][y] + 1
                stack.append((nx, ny))

    if distance[h - 1][w - 1] == float('inf'):
        return -1
    else:
        white = sum(row.count('.') for row in matrix)
        return white - distance[h - 1][w - 1]

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

Solution (Python):
from collections import deque

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

MAP = [input() for i in range(H)]
INF = 10000
DISTANCE = [[INF for i in range(W)] for j in range(H)]
DISTANCE[0][0] = 0
QUEUE = deque([(0,0)])
dxy = [(-1,0),(1,0),(0,-1),(0,1)]
while QUEUE :
    y,x = QUEUE.popleft()
    for dy,dx in dxy :
        ny = y+dy
        nx = x+dx
        if (ny < 0) or (nx < 0) or (ny >= H) or (nx >= W) :
            continue
        if MAP[ny][nx] == "
            continue
        if DISTANCE[ny][nx] < INF :
            continue
        QUEUE.append((ny,nx))
        DISTANCE[ny][nx] = min(DISTANCE[ny][nx], DISTANCE[y][x]+1)

if DISTANCE[-1][-1] < INF :
    path = 1 + DISTANCE[-1][-1]
    not_score = 0
    for y in range(H) :
        not_score += MAP[y].count("
    ans = H*W - path - not_score
else :
    ans = -1
print(ans)

Solution (Python):
from collections import deque

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

sy = 0
sx = 0

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

INF = 10**9+7

DISTANCE = [[INF for i in range(W)] for j in range(H)]
DISTANCE[sy][sx] = 0

QUEUE = deque([(sy,sx)])

flg = 0

while QUEUE :
    y,x = QUEUE.popleft()
    
    for dy,dx in dxy :
        ny = y+dy
        nx = x+dx
        if (ny < 0) or (nx < 0) or (ny >= H) or (nx >= W) :
            continue
        if MAP[ny][nx] == "
            continue
        if DISTANCE[ny][nx] < INF :
            continue
        
        QUEUE.append([ny,nx])
        DISTANCE[ny][nx] = min(DISTANCE[ny][nx], DISTANCE[y][x]+1)

if DISTANCE[H-1][W-1] < INF :
    flg = 1
        
if flg == 0 :
    ans = -1
else :
    path = DISTANCE[H-1][W-1] + 1
    not_score = 0
    for y in range(H) :
        not_score += MAP[y].count("
    
    ans = H*W - path - not_score
print(ans)

Solution (Python):


def main():
    na = list(map(int, input().split()))
    H, W = na[0], na[1]
    mp = []
    for i in range(H):
        mp.append(input())

    w_count = 0
    for s in mp:
        w_count += s.count('.')

    dist = [-1 for i in range(H * W)]
    v = (0, 0, 1)
    dist[0] = 1
    q = []
    q.append(v)
    while 0 < len(q):
        x, y, d = v = q.pop(0)
        if 0 < x and dist[W * y + x - 1] == -1 and mp[y][x - 1] == '.':
            dist[W * y + x - 1] = d + 1
            q.append((x - 1, y, d + 1))
        if x < W - 1 and dist[W * y + x + 1] == -1 and mp[y][x + 1] == '.':
            dist[W * y + x + 1] = d + 1
            q.append((x + 1, y, d + 1))
        if 0 < y and dist[W * (y - 1) + x] == -1 and mp[y - 1][x] == '.':
            dist[W * (y - 1) + x] = d + 1
            q.append((x, y - 1, d + 1))
        if y < H - 1 and dist[W * (y + 1) + x] == -1 and mp[y + 1][x] == '.':
            dist[W * (y + 1) + x] = d + 1
            q.append((x, y + 1, d + 1))
        if dist[H * W - 1] != -1:
            break

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


if __name__ == '__main__':
    main()