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())
A = [[1 if a == "

dd = [(0, 1), (0, -1), (1, 0), (-1, 0)]
def BFS():
    Q = deque([(0, 0)])
    D = [[-1] * W for _ in range(H)]
    D[0][0] = 0
    while Q:
        i, j = Q.popleft()
        for di, dj in dd:
            ni, nj = i + di, j + dj
            if 0 <= ni < H and 0 <= nj < W:
                if D[ni][nj] == -1 and A[ni][nj] == 0:
                    D[ni][nj] = D[i][j] + 1
                    Q.append((ni, nj))
    return D

print(H * W - sum([sum(a) for a in A]) - BFS()[-1][-1] - 1 if BFS()[-1][-1] >= 0 else -1)

Solution (Python):

h, w = map(int, input().split())
maze = []
wall = 0
for _ in range(h):
    row = list(input())
    wall += row.count('
    maze.append(row)

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

def bfs():
    from collections import deque
    que = deque([])

    d = [[float("inf")] * w for _ in range(h)]
    que.append((0, 0))
    d[0][0] = 0
    step = 0

    while que:
        step += 1
        p = que.popleft()
        if p == (h - 1, w - 1):
            break
        for i in range(4):
            ny = p[0] + dy[i]
            nx = p[1] + dx[i]

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

    return d[h - 1][w - 1]

print(-1 if bfs() == float("inf") else h * w - wall - bfs() - 1)

Solution (Python):
import sys
input = sys.stdin.readline
from operator import itemgetter
sys.setrecursionlimit(10000000)
INF = 10**30
from collections import Counter

W = 0
def g_i(i, j):
    return i * W + (j+1) - 1

def dijkstra(n, start, nbl):
    """n: 頂点数, start: 始点, nbl: 隣接リスト"""
    import heapq
    WHITE = 1<<5
    GRAY = 1<<10
    BLACK = 1<<15
    color = [WHITE] * n
    distance = [INF] * n
    parent = [-1] * n
    q = []

    distance[start] = 0
    heapq.heappush(q, (0, start))
    while len(q) != 0:
        du, u = heapq.heappop(q)
        
        color[u] = BLACK
        if distance[u] < du:
            continue
        for next, cost in nbl[u]:
            if color[next] != BLACK and distance[u] + cost < distance[next]:
                distance[next] = distance[u] + cost
                parent[next] = u
                color[next] = GRAY
                heapq.heappush(q, (distance[next], next))
    return (distance, parent)

def main():
    global W
    h, W = map(int, input().strip().split())
    w = W
    s = [[0] * w for _ in range(h)]
    G = [[] for _ in range(h * w)]
    for i in range(h):
        s[i] = list(input().strip())
    sc = 0
    dc = 0
    for i in range(h):
        for j in range(w):
            if s[i][j] == '
                sc += 1
                continue
            dc += 1
            if i != 0 and s[i-1][j] == '.':
                G[g_i(i, j)].append((g_i(i-1, j), 1))
            if i != h-1 and s[i+1][j] == '.':
                G[g_i(i, j)].append((g_i(i+1, j), 1))
            if j != 0 and s[i][j-1] == '.':
                G[g_i(i, j)].append((g_i(i, j-1), 1))
            if j != w-1 and s[i][j+1] == '.':
                G[g_i(i, j)].append((g_i(i, j+1), 1))
    
    d, p = dijkstra(h * w, 0, G)
    
    
    
    
    
    
    
    
    
    
    
    if d[h*w - 1] == INF:
        print(-1)
    else:
        print(dc - d[h*w - 1] - 1)

if __name__ == '__main__':
    main()

Solution (Python):
from collections import deque

qx = deque([])
qy = deque([])

nowx = 0
nowy = 0
tmpx = 0
tmpy = 0

ans = -1
ans2 = 0
cnt = 1
m = []

sx=[0,1,0,-1]
sy=[1,0,-1,0]
H,W = map(int, input().split())
for i in range(H):
    m.append(list(input()))
f = 0
p=[[999 for i in range(W)] for j in range(H)]

qx.append(nowx)
qy.append(nowy)
p[nowx][nowy]=0

while(len(qx) > 0 and f == 0):
    nowx = qx.popleft()
    nowy = qy.popleft()
    for i in range(4):
        tmpx = nowx + sx[i]
        tmpy = nowy + sy[i]
        if (tmpx < 0 or tmpx > W-1 or tmpy < 0 or tmpy > H-1):
            continue
        if (m[tmpy][tmpx] == '
            continue
        if (tmpx == W-1 and tmpy == H-1):
            p[tmpy][tmpx] = p[nowy][nowx]+1
            ans = p[nowy][nowx]+1
            f = 1
            break
        if (p[tmpy][tmpx] > p[nowy][nowx]+1):
            p[tmpy][tmpx] = p[nowy][nowx]+1
            qx.append(tmpx)
            qy.append(tmpy)

if(ans == -1):
    ans2 = -1
else:
    ans2 = sum(x.count('.') for x in m) - ans -1 
print(ans2)

Solution (Python):


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

maze=[]
m=[]
wn=0
INF = 10**5

for i in range(h):
    row=list(input())
    maze.append(row)
    m.append([INF for i in range(w)])
    for j in range(w):
        if row[j]==".":
            wn+=1


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

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

while len(queue)>0:

    y,x=queue.pop(0)
    for i in range(4):
        ny=y+dy[i]
        nx=x+dx[i]
        if 0<=ny<h and 0<=nx<w:
            if maze[ny][nx]==".":
                queue.append([ny,nx])
                maze[ny][nx]="
                m[ny][nx]=min(m[ny][nx],m[y][x]+1)


if m[-1][-1]==INF:
    print(-1)
else:
    print(wn-2-(m[-1][-1]-1))

Solution (Python):
from collections import deque
h, w = map(int, input().split())
s = [list(input()) for _ in range(h)]
moves = ((0, 1), (1, 0), (0, -1), (-1, 0))
path = [[float('inf')]*w for _ in range(h)]
path[0][0] = 0
def bfs():
    q = deque([[0, 0]])
    while q:
        y, x = q.popleft()
        if y == h and x == w:
            return 
        for dy, dx in moves:
            ny = y + dy 
            nx = x + dx 
            if 0 <= ny < h and 0 <= nx < w and s[ny][nx] == '.' and path[ny][nx] == float('inf'):
                path[ny][nx] = min(path[ny][nx], path[y][x]+1)
                q.append([ny, nx])

bfs()

black = 0

for i in range(h):
    for j in range(w):
        if s[i][j] == '
            black += 1 

if path[h-1][w-1] != float('inf'):
    print(h*w - black - path[h-1][w-1] - 1)
else:
    print(-1)

Solution (Python):
import copy
import queue
import numpy as np

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








def bfs(array,start,goal,height,width):
    v=[[-1]*width for _ in range(height)]

    q=queue.Queue()
    q.put([start[0],start[1]])
    move=[[0,1],[0,-1],[1,0],[-1,0]]
    v[start[0]][start[1]]=0
    while not q.empty():
        pos=q.get()
        if pos[0]==goal[0] and pos[1]==goal[1]:          
            break
        
        for m in move:
            y=pos[0]+m[0]
            x=pos[1]+m[1]
            if y>=0 and y<height and x>=0 and x<width and array[y][x]=="." and v[y][x]==-1 :
                v[y][x]=v[pos[0]][pos[1]]+1
                q.put([y,x])
    return v[goal[0]][goal[1]]


cnt=0
for i in range(H):
    for j in range(W):
        if c[i][j]=="
            cnt+=1

d=bfs(c,[0,0],[H-1,W-1],H,W)
if d==-1:
    print(-1)
else:
    print(H*W-1-d-cnt)

Solution (Python):
def main():
    import sys
    input=sys.stdin.readline
    from collections import deque
    
    
    
    
    H,W=map(int,input().split())
    ls=["
    for i in range(H):
        ls.append("
    ls.append("
    q=deque([])
    
    
    q.append((1,1))
    
    
    lf=[[float("inf") for _ in range(W+2)] for _ in range(H+2)]
    
    lf[1][1]=0
    while q:
        tmpij=q.popleft()
        
        
        if tmpij==(H,W):
            break
        lind=[(-1,0),(1,0),(0,-1),(0,1)]
        for i in range(4):
            
            ntmpij=(tmpij[0]+lind[i][0],tmpij[1]+lind[i][1])
            
            
            if lf[ntmpij[0]][ntmpij[1]]==float("inf") and ls[ntmpij[0]][ntmpij[1]]==".":
                
                
                q.append(ntmpij)
                
                lf[ntmpij[0]][ntmpij[1]]=lf[tmpij[0]][tmpij[1]]+1
                
    if tmpij==(H,W):
        nw=0
        for i in range(1,H+1):
            
             
              
            nw+=ls[i].count(".")
        
        print(nw-lf[H][W]-1)
    else:
        print(-1)

if __name__=='__main__':
    main()

Solution (Python):
import sys
from collections import deque as dq
input = sys.stdin.readline
H, W = map(int, input().split())
c = []
for _ in range(H):
  c.append(list(input()))
Q = dq([])
Q.append((0, 0))
dist = [[float("inf")] * W for _ in range(H)]
d = [-1, 0, 1, 0]
dist[0][0] = 1
while len(Q):
  p = Q.popleft()
  for i in range(4):
    y = p[0] + d[i]
    x = p[1] + d[-1 - i]
    if (0 <= y < H) and (0 <= x < W):
      if c[y][x] == "." and (dist[y][x] > dist[p[0]][p[1]] + 1):
        Q.append((y, x))
        dist[y][x] = dist[p[0]][p[1]] + 1
if dist[H - 1][W - 1] == float("inf"):
  print(-1)
  exit(0)
black = 0
for i in range(H):
  black += c[i].count("
print(H * W - dist[H - 1][W - 1] - black)

Solution (Python):
from collections import deque

def bfs(sx, sy, gx, gy):
    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[sy][sx] = 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 <= ny and ny <= H-1 and 0 <= nx and nx <= W-1 and \
                    grid[ny][nx] != '
                d[ny][nx] = d[p[1]][p[0]] + 1
                que.append((nx, ny))
    return d[gy][gx]


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

a = bfs(0, 0, W-1, H-1)
white = 0
for x in grid:
    white += x.count('.')

if a == float('inf'):
    answer = -1
else:
    answer = white - (a + 1)
print(answer)

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

white = 0

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

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

g = [[10**9]*W for i in range(H)]
g[0][0] = 0
for i in range(H*W):
    if len(q) == 0:
        break
    x, y = q.popleft()
    if (x, y) == (H-1, W-1):
        break
    else:
        if x < H-1 and s[x+1][y] == ".":
            if g[x+1][y] == 10**9:
                q.append((x+1, y))
            g[x+1][y] = min(g[x+1][y], g[x][y]+1)
        if y < W-1 and s[x][y+1] == ".":
            if g[x][y+1] == 10**9:
                q.append((x, y+1))
            g[x][y+1] = min(g[x][y+1], g[x][y]+1)
        if x > 0 and s[x-1][y] == ".":
            if g[x-1][y] == 10**9:
                q.append((x-1, y))
            g[x-1][y] = min(g[x-1][y], g[x][y]+1)
        if y > 0 and s[x][y-1] == ".":
            if g[x][y-1] == 10**9:
                q.append((x, y-1))
            g[x][y-1] = min(g[x][y-1], g[x][y]+1)
if g[H-1][W-1] == 10**9:
    print(-1)
else:
    print(white - (g[H-1][W-1]+1))

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

dist = [[float('inf')] * W for _ in range(H)]
q = [(0, 0, 0)]
while q :
    cost, cx, cy = heappop(q)
    if cost >= dist[cy][cx] :
        continue
    dist[cy][cx] = cost
        
    for dx, dy in ((0, 1), (0, -1), (1, 0), (-1, 0)) :
        if 0 <= cx + dx < W and 0 <= cy + dy < H and s[cy+dy][cx+dx] != '
            heappush(q, (cost+1, cx+dx, cy+dy))
            
if dist[H-1][W-1] == float('inf') :
    print(-1)
else :
    ret = 0
    for s_ in s :
        ret += s_.count('
    print(H * W - ret - dist[H-1][W-1] - 1)

Solution (Python):
import sys
import collections


def solve():
    input = sys.stdin.readline
    mod = 10 ** 9 + 7
    h, w = list(map(int, input().rstrip('\n').split()))
    s = [list(str(input().rstrip('\n'))) for _ in range(h)]
    bl = 0
    for i in range(h):
        for j in range(w):
            if s[i][j] == "
                bl += 1

    ql = [[0, 0, 0]]
    ql = collections.deque(ql)
    fq = collections.defaultdict(list)
    fq[0, 0]
    mc = 10 ** 10
    while True:
        if len(ql) != 0:
            cost, xv, yv = ql.popleft()
            if xv == h - 1 and yv == w - 1:
                mc = min(mc, cost)
            for xv, yv in [[xv + 1, yv], [xv - 1, yv], [xv, yv + 1], [xv, yv - 1]]:
                if 0 <= xv < h and 0 <= yv < w:
                    if (xv, yv) not in fq and s[xv][yv] != "
                        ql.append([cost + 1, xv, yv])
                        fq[xv, yv]
        else:
            break
    print(h * w - mc - 1 - bl if mc != 10 ** 10 else -1)


if __name__ == '__main__':
    solve()

Solution (Python):
import sys
from heapq import *

sys.setrecursionlimit(10 ** 6)
int1 = lambda x: int(x) - 1
p2D = lambda x: print(*x, sep="\n")

def main():
    h, w = map(int, input().split())
    t = [[(c == "
    b0 = sum(sum(tk) for tk in t)
    
    hp = []
    
    heappush(hp, (1, 0, 0))
    while hp:
        d, i, j = heappop(hp)
        if (i, j) == (h - 1, w - 1):
            print(h * w - d - b0)
            exit()
        for di, dj in [(1, 0), (0, 1), (-1, 0), (0, -1)]:
            ni, nj = i + di, j + dj
            if not (0 <= ni < h and 0 <= nj < w): continue
            if t[ni][nj]: continue
            t[ni][nj] = 1
            heappush(hp, (d + 1, ni, nj))
    print(-1)

main()

Solution (Python):
import numpy as np


def main():
    H, W = map(int, input().split())

    ps = np.zeros([H, W])
    for i in range(H):
        ps[i, :] = list(map(lambda x: -1 if x == "
    hashnum = np.sum(ps)

    costs = np.zeros([H, W])
    s = (0, 0)
    g = (H-1, W-1)
    dd = ((1, 0), (-1, 0), (0, 1), (0, -1))
    q = [s]
    costs[s] = 1
    ps[s] = 1
    moves = 1
    dame = 1

    while q:
        qn = []
        moves += 1
        for x, y in q:
            for dx, dy in dd:
                nx, ny = int(x + dx), int(y + dy)
                if 0 <= nx < H and 0 <= ny < W:
                    if ps[nx, ny] == 0:
                        costs[nx, ny] = moves
                        ps[nx, ny] = 1
                        qn.append((nx, ny))

        q = qn
        if g in q:
            dame = 0
            break

    if dame == 0:
        print(int(H * W + hashnum - np.max(costs)))
    else:
        print(-1)


main()

Solution (Python):
def BFS(x,y): 
    dx=[1,0,-1,0]
    dy=[0,1,0,-1]
    que=[]
    que.append([x,y])
    d[x][y]=0
    while len(que)!=0:
        [qx,qy]=que[0]
        que.pop(0)
        for i in range(4):
            nx=qx+dx[i]
            ny=qy+dy[i]
            if nx>=0 and h>nx and ny>=0 and w>ny and maze[nx][ny]=="." and d[nx][ny]==-1:
                d[nx][ny]=d[qx][qy]+1
                que.append([nx,ny])
    return d[h-1][w-1]

def main():
    global h,w,maze,d
    h,w = map(int,input().split())
    d=[[-1 for _ in range(w)] for _ in range(h)]
    maze=[]
    for _ in range(h):
        maze.append(list(input()))
    n=BFS(0,0)
    if n==-1:
        print(-1)
    else:
        cnt=0
        for i in range(h):
            for j in range(w):
                if maze[i][j]==".":
                    cnt+=1
        print(cnt-n-1)

        
    





if __name__ == "__main__":
    main()

Solution (Python):
import sys

sys.setrecursionlimit(4100000)

H,W = map(int,input().split(' '))
sx,sy = 0,0
move_list = [ list(input()) for _ in range(H) ]
possible_list = [ [-1 for _ in range(W) ] for _ in range(H) ]
possible_list[sx][sy] = 0

x_start_list = [sx]
y_start_list = [sy]

def bfs(target_list,possible_list,x_queue,y_queue,cnt=0):
    x_list = [1,-1,0,0,]
    y_list = [0,0,1,-1]
    cnt += 1
    next_x_queue = []
    next_y_queue = []

    for i in range(4):
        for j in range(len(x_queue)):
            dx = x_queue[j] + x_list[i]
            dy = y_queue[j] + y_list[i]
            if dx < 0 or H <= dx or dy < 0 or W <= dy:
                continue
            if target_list[dx][dy] == '
                continue
            if possible_list[dx][dy] != -1:
                continue
            possible_list[dx][dy] = cnt
            next_x_queue.append(dx)
            next_y_queue.append(dy)
    if len(next_x_queue) > 0:
        bfs(target_list,possible_list,next_x_queue,next_y_queue,cnt)
    else:
        return

bfs(move_list,possible_list,x_start_list,y_start_list)

cnt_all_panel = 0
for row in move_list:
    for val in row:
        if val == '.':
            cnt_all_panel += 1
if possible_list[H-1][W-1] == -1:
    print(-1)
else:
    print(cnt_all_panel - possible_list[H-1][W-1] -1)

Solution (Python):
H,W = map(int, input().split())
field = [list(input()) for _ in range(H)]
dy = [1,-1,0,0]
dx = [0,0,1,-1]


count = 0







sy,sx = 0,0
gy,gx = H-1,W-1
seen = [[0 for i in range(W)] for j in range(H)]
queue = [[sy,sx]]
flag = False
while queue != []:
    h,w = queue.pop(0)
    before = seen[h][w]
    for i in range(4):
        nh = h + dy[i]
        nw = w + dx[i]
        if (nh == gy) and (nw == gx):
            count = before+1
            flag = True
        if (0<=nh<H) and (0<=nw<W):
            if field[nh][nw] != '
                if seen[nh][nw] == 0:
                    seen[nh][nw] = before+1
                    queue.append([nh,nw])
    if flag:
        break
whites = 0
for i in range(H):
    for j in range(W):
        if field[i][j] == '.':
            whites += 1
if count != 0 :
    print(whites - count-1)
else:
    print(-1)

Solution (Python):
import copy

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



visited = []
for _ in range(h):
    visited.append([-1 for __ in range(w)])

visited[0][0] = 0
here = [[0,0]]
count = 0



def udlr(line):
    ans = []
    for cell in line:
        if cell[0]-1 >= 0:
            ans.append([cell[0]-1, cell[1]])
        if cell[0]+1 < h:
            ans.append([cell[0]+1, cell[1]])
        if cell[1]-1 >= 0:
            ans.append([cell[0], cell[1]-1])
        if cell[1]+1 < w:
            ans.append([cell[0], cell[1]+1])
    return ans

flag = 0



while True:
    count += 1
    line = []
    for cell in udlr(here):
        a = cell[0]
        b = cell[1]
        if s[a][b] == "." and visited[a][b] == -1:
            visited[a][b] = count
            line.append([a, b])
            if a == h-1 and b == w-1:
                flag = 1
    here = copy.deepcopy(line)
    if flag:
        break
    if here == []:
        break



if visited[h-1][w-1] == -1:
    print(-1)
else:
    cnt = 0
    for i in range(h):
        for j in range(w):
            if s[i][j] == "
                cnt += 1
    print(h*w - 1 - visited[h-1][w-1] - cnt)

Solution (Python):
from collections import deque

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

p = [[0 for j in range(W)] for i in range(H)]
p[0][0] = 1
visited = [[False for j in range(W)] for i in range(H)]
Q = deque()
Q.append((0, 0))
while len(Q) > 0:
    i, j = Q.popleft()
    neighbors = [(i - 1, j), (i + 1, j), (i, j - 1), (i, j + 1)]
    for ni, nj in neighbors:
        if 0 <= ni < H and 0 <= nj < W and s[ni][nj] != '
            p[ni][nj] = p[i][j] + 1
            Q.append((ni, nj))
    visited[i][j] = True

n_black = sum([row.count('
print(H * W - n_black - p[H - 1][W - 1] if p[H - 1][W - 1] != 0 else - 1)

Solution (Python):
def debug_print(maze):
    for xx in maze:
        print(xx)



def clear_maze(h,w,sx, sy, gx, gy, maze):

    INF = 100000000
    distance = [[INF for _ in range(w)] for _ in range(h)]
    def bfs():
        queue = []
        queue.insert(0, (sy, sx))
        distance[sy][sx] = 0
        while len(queue):
            y, x = queue.pop()
            if x == gx and y == gy:
                break
            for i in range(0, 4):
                nx, ny = x + [1, 0, -1, 0][i], y + [0, 1, 0, -1][i]
                if (0<= nx <w and 0<= ny <h and maze[ny][nx] != '
                    queue.insert(0, (ny, nx))
                    distance[ny][nx] = distance[y][x] + 1
        return distance[gy][gx]
    return bfs()


import sys
def I(): return int(sys.stdin.readline())
def LI(): return list(map(int,sys.stdin.readline().split()))
def LSI(): return list(map(str,sys.stdin.readline().split()))
mod = 10**9 + 7
inf = float('inf')

H, W = LI()
cur = int(0)
S = [list(str(input().rstrip('\n'))) for _ in range(H)]
for i in range(H):
    for j in range(W):
        if S[i][j]=="
            cur +=1

ans = H*W - (clear_maze(H,W,0,0,W-1,H-1,S) + 1 + cur)
if ans<0:
    ans = -1
print(ans)

Solution (Python):
import sys
import collections


def solve():
    input = sys.stdin.readline
    mod = 10 ** 9 + 7
    h, w = list(map(int, input().rstrip('\n').split()))
    s = [list(str(input().rstrip('\n'))) for _ in range(h)]
    ql = [[0, 0, 0]]
    ql = collections.deque(ql)
    fq = collections.defaultdict(list)
    fq[0, 0]
    mt = 10 ** 10
    while True:
        if len(ql) != 0:
            cost, xv, yv = ql.popleft()
            if xv == h - 1 and yv == w - 1:
                mt = min(mt, cost)
            for xv, yv in [[xv + 1, yv], [xv - 1, yv], [xv, yv + 1], [xv, yv - 1]]:
                if 0 <= xv < h and 0 <= yv < w:
                    if (xv, yv) not in fq and s[xv][yv] != "
                        ql.append([cost + 1, xv, yv])
                        fq[xv, yv]
        else:
            break
    if mt == 10 ** 10:
        print(-1)
    else:
        cnt = 0
        for i in range(h):
            cnt += s[i].count("
        print(h * w - cnt - (mt + 1))


if __name__ == '__main__':
    solve()

Solution (Python):
from collections import deque

h, w = map(int, input().split())
maze = [list(input()) for _ in range(h)]
INF = 1001001001
dist = [[INF for _ in range(w)] for _ in range(h)]
dist[0][0] = 0

d = deque()
d.append([0, 0])
while(d):
    y,x = d.popleft()
    difflist = [[1,0], [0,1], [-1, 0], [0, -1]]
    for dy, dx in difflist:
        y2 = y + dy
        x2 = x + dx
        if 0 <= y2 < h and 0 <= x2 < w and maze[y2][x2] != '
            d.append([y2, x2])
            dist[y2][x2] = dist[y][x] + 1

distribution = [0]*(h*w)
ans = 0
for i in range(h):
    for j in range(w):
        if dist[i][j] != INF:
            distribution[dist[i][j]] += 1
        elif maze[i][j] == '.':
            ans += 1

if dist[h-1][w-1] != INF:
    distend = dist[h-1][w-1]
    ans += sum(distribution) - distend -1
    print(ans)
else:
    print(-1)

Solution (Python):
from collections import deque

r, c = map(int, input().split())
s_y, s_x = 1, 1
g_y, g_x = r, c
s_y -= 1
s_x -= 1
g_y -= 1
g_x -= 1

maze = [list(input()) for i in range(r)]
dot_num = 0
for i in maze:
    dot_num += i.count('.')
reached = [[0] * c for i in range(r)]

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

queue = deque([[s_y, s_x, 0]])
reached[s_y][s_x] = 1

while queue:
    now = queue.popleft()
    depth = now[2] + 1
    for d in directions:
        next_y = now[0] + d[0]
        next_x = now[1] + d[1]
        if 0 <= next_y < r and 0 <= next_x < c:
            if maze[next_y][next_x] == '.':
                if reached[next_y][next_x] == 0:
                    queue.append([next_y, next_x, depth])
                    reached[next_y][next_x] = 1

                    if next_y == g_y and next_x == g_x:
                        print(dot_num - depth - 1)
                        exit()
print(-1)

Solution (Python):


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

ku=0
for _ in range(H): 
    S.append(list(input()))
    ku+=S[-1].count(".")


def bfs(h,w,num):
    if h==H-1 and w==W-1:
        print(ku-num-1)
        exit() 
    else:
        pass

    if h!=0: 
        if S[h-1][w]!="
            temp.append([h-1,w])
            S[h-1][w]="

    if w!=0: 
        if S[h][w-1]!="
            temp.append([h,w-1]) 
            S[h][w-1]="

    if h!=H-1: 
        if S[h+1][w]!="
            temp.append([h+1,w]) 
            S[h+1][w]="

    if w!=W-1: 
        if S[h][w+1]!="
            temp.append([h,w+1]) 
            S[h][w+1]="
        
q=[[0,0]] 
count=-1
while True: 
    count+=1
    
    temp=[]
    while q:
        l=q.pop(0)
        bfs(l[0],l[1],count)
        
    q=temp[:]
    if len(q)==0:
        print(-1)
        exit()

Solution (Python):
H, W = map(int, input().split())
F = [list(input()) for _ in range(H)]
cnt = 0
for i in range(H):
    for j in range(W):
        if F[i][j] == '.':
            cnt += 1


que = [[0, 0, 0]]
flag = True

while len(que) > 0 and flag:
    sp = que.pop(0)
    y, x, c = sp[0], sp[1], sp[2]
    for dy, dx in [[1,0], [-1,0], [0,1], [0,-1]]:
        if 0 <= y+dy < H and 0 <= x+dx < W and F[y+dy][x+dx] == ".":
            F[y+dy][x+dx] = c+1
            que.append([y+dy, x+dx, c+1])
            if y+dy == H-1 and x+dx == W-1:
                flag = False

if flag:
    print(-1)
else:
    print(cnt-F[H-1][W-1]-1)

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

q=[(0,0)]
s[0][0]=0
dxy=[(1,0),(-1,0),(0,1),(0,-1)]
while q:
    x,y=q.pop(0)
    for dx,dy in dxy:
        nx,ny=x+dx,y+dy
        if not 0<=nx<w:
            continue
        if not 0<=ny<h:
            continue
        if s[ny][nx]=="
            continue
        if s[ny][nx]==".":
            s[ny][nx]=s[y][x]+1
            q.append((nx,ny))
        else:
            continue
if s[h-1][w-1]=="." or s[h-1][w-1]=="
    print(-1)
else:
    kuro=0
    for i in range(h):
        kuro+=s[i].count("

    print(h*w-s[h-1][w-1]-1-kuro)

Solution (Python):
from collections import deque

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

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

dxdy = [(0,1),(0,-1),(1,0),(-1,0)]
queue = deque()
queue.append((0,0))

while queue:
    x,y = queue.popleft()

    if S[x][y] == "
        continue

    for dx,dy in dxdy:
        if 0 <= x+dx < H  and  0 <= y+dy < W:
            if S[x+dx][y+dy] == "." and A[x+dx][y+dy] == -1:
                A[x+dx][y+dy] = A[x][y] + 1
                queue.append((x+dx,y+dy))

cnt_white = 0
for h in range(H):
    for w in range(W):
        if S[h][w] == ".":
            cnt_white += 1

if A[H-1][W-1] == -1:
    print(-1)
else:
    print(cnt_white - A[H-1][W-1])

Solution (Python):
h,w=map(int,input().split())
a=['*'*(w+2)]+['*'+input()+'*' for _ in range(h)]+['*'*(w+2)]
s=0
for i in range(1,h+1):
  s+=a[i].count('.')
from collections import deque
d=deque()
d.append([1,1])
c=[[10000]*w for _ in range(h)]
c[0][0]=1
di=[[0,1],[1,0],[-1,0],[0,-1]]
while d:
  g=d.popleft()
  for i in di:
    x=g[0]+i[0]
    y=g[1]+i[1]
    if a[x][y]=='.':
      if c[x-1][y-1]==10000:
        d.append([x,y])
        c[x-1][y-1]=c[g[0]-1][g[1]-1]+1
if c[h-1][w-1]==10000:
  print(-1)
else:
  print(s-c[h-1][w-1])

Solution (Python):
from collections import deque
h,w=map(int,input().split())
l=[["
for i in range(h):
  l1=list(input())
  l1=["
  l.append(l1)
l2=["
l.append(l2)
q=deque([[1,1]])
inf=1000000000
d=[[inf for i in range(w+2)] for j in range(h+2)]
d[1][1]=0
move=[[1,0],[-1,0],[0,1],[0,-1]]
while q:
  a=q.popleft()
  n1=a[0]
  n2=a[1]
  for i in move:
    m1=i[0]
    m2=i[1]
    if l[n1+m1][n2+m2]!="
      if d[n1+m1][n2+m2]>d[n1][n2]+1:
        d[n1+m1][n2+m2]=d[n1][n2]+1
        q.append([n1+m1,n2+m2])
dis=d[h][w]
count=0
for i in range(1,h+1):
  for j in range(1,w+1):
    if l[i][j]=="
      count+=1
if dis==inf:
  print(-1)
else:
  print(h*w-dis-1-count)

Solution (Python):
from collections import deque

def main():
    h, w = map(int, input().split())
    G = [list(input()) for i in range(h)]
    dy, dx = [-1, 1, 0, 0], [0, 0, -1, 1]
    
    dist = [[-1 for j in range(w)] for i in range(h)]
    que = deque()
    px = [[-1 for j in range(w)] for i in range(h)]
    py = [[-1 for j in range(w)] for i in range(h)]
    dist[0][0] = 0
    que.append((0, 0))
    while (len(que) != 0):
        y, x = que[0][0], que[0][1]
        que.popleft()

        for i in range(4):
            ny, nx = y+dy[i], x+dx[i]
            if (ny < 0) or (h <= ny) or (nx < 0) or (w <= nx):
                continue
            if G[ny][nx] == "
                continue
            if dist[ny][nx] == -1:
                dist[ny][nx] = dist[y][x] + 1
                py[ny][nx], px[ny][nx] = y, x
                que.append((ny, nx))

    if dist[h-1][w-1] == -1:
        print(dist[h-1][w-1])
    else:
        y, x = h - 1, w - 1
        while y != -1 and x != -1:
            G[y][x] = "o"
            y, x = py[y][x], px[y][x]
        ans = 0
        for i in G:
            for j in i:
                if j == ".":
                    ans += 1
        print(ans)

if __name__ == "__main__":
    main()

Solution (Python):
h,w = map(int,input().split())
g = [['
c = 0
for i in range(h):
  g[i+1][1:-1] = list(input())
  c += g[i+1][1:-1].count('
d = {}
d[0] = [(1,1)]
vi = set()
vi.add((1,1))
i = 0
while d[i]:
  l = d[i]
  d[i+1] = []
  for cur in l:
    for a,b in [[1,0],[0,1],[-1,0],[0,-1]]:
      to = (cur[0]+a,cur[1]+b)
      if to == (h,w):
        print(h*w-c-i-2)
        exit()
      if g[to[0]][to[1]] == '.' and to not in vi:
        vi.add(to)
        d[i+1].append(to)
  i += 1
print(-1)