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):
def inpl(): return [int(i) for i in input().split()]
from collections import deque
H,W = inpl()
S =  []
for i in range(H):
    S.append(input())
    
dist = [[-1 for _ in range(W)] for _ in range(H)]
dist[0][0] = 1
Q = deque()
Q.append((0,0))
d = [(0, 1), (0, -1), (1, 0), (-1, 0)]
while Q:
    nw, nh = Q.pop() 
    for dw, dh in d:
        if not 0 <= nh + dh <= H-1:
            continue
        if not 0 <= nw + dw <= W-1:
            continue
        if S[nh+dh][nw+dw] == '
            continue
        if dist[nh+dh][nw+dw] != -1:
            continue
        dist[nh+dh][nw+dw] =dist[nh][nw] +1
        Q.appendleft((nw+dw,nh+dh))
if dist[H-1][W-1] == -1:
    print(-1)
else:
    ans = 0
    for i in range(H):
        ans += S[i].count('.')
    ans -= dist[H-1][W-1]
    print(ans)

Solution (Python):
h, w = map(int, input().split())
s = [['
s = s + [['
s = s + [['
n_white = 0
for i in range(1, h + 1):
    n_white += s[i].count('.')
q = [[1, 1]]
a = []
d = 1
while(True):
    qq = []
    for i in range(len(q)):
        if q[i] in a:
            continue
        x = q[i][0]
        y = q[i][1]
        if s[x][y - 1] == '.' and [x, y - 1] not in qq:
            qq.append([x, y - 1])
        if s[x - 1][y] == '.' and [x - 1, y] not in qq:
            qq.append([x - 1, y])
        if s[x + 1][y] == '.' and [x + 1, y] not in qq:
            qq.append([x + 1, y])
        if s[x][y + 1] == '.' and [x, y + 1] not in qq:
            qq.append([x, y + 1])
    d += 1
    if [h, w] in qq:
        break
    elif qq == []:
        print(-1)
        exit()
    a = a + q
    q = qq
print(n_white - d)

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


black = 0
for g in G:
    black += g.count("


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


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


direction = [(0, 1), (1, 0), (0, -1), (-1, 0)]
while que:
    nh, nw = que.pop()
    for dh, dw in direction:
        
        if not 0 <= nh + dh < H:
            continue
        if not 0 <= nw + dw < W:
            continue
        if G[nh + dh][nw + dw] == "
            continue
        if C[nh + dh][nw + dw] > 0:
            continue

        C[nh + dh][nw + dw] = C[nh][nw] + 1
        que.appendleft((nh + dh, nw + dw))

print(H * W - C[H - 1][W - 1] - black - 1 if C[H - 1][W - 1] > 0 else -1)

Solution (Python):
from collections import deque

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

s=['
s+=['
s+=['

deq=deque([(1,1,0)])
move=[(1,0),(0,1),(-1,0),(0,-1)]
dist=[[-1 for _ in range(W+2)] for _ in range(H+2) ]
while len(deq) !=0:
    x=deq.pop()
    if x[:-1]==(H,W):
        ans=x[-1]
        break
    for m in move:
        i=x[0]+m[0]
        j=x[1]+m[1]
        d=x[2]
        if s[i][j]=='.' and dist[i][j]==-1:
            deq.appendleft((i,j,d+1))
            dist[i][j]=d+1

if ans==-1:
    print(-1)
else:
    sum_=0
    for t in s:
        sum_+=t.count('
    b=sum_-(W+2)*2-H*2
    ans=H*W-b-ans-1
    print(ans)

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

black = 0
for h in range(H):
    for w in range(W):
        black += (G[h][w] == "

que = deque()
que.append([0, 0, 0])
direction = [(0, 1), (0, -1), (1, 0), (-1, 0)]

visited = set([(0, 0)])
while que:
    nh, nw, cost = que.pop()
    G[nh][nw] = cost
    if G[H - 1][W - 1] != ".":
        print(H * W - black - int(G[H - 1][W - 1]) - 1)
        break

    for dh, dw in direction:
        if (0 <= nh + dh < H) & (0 <= nw + dw < W):
            if G[nh + dh][nw + dw] == "." and (nh + dh, nw + dw) not in visited:
                que.appendleft((nh + dh, nw + dw, cost + 1))
                visited.add((nh + dh, nw + dw))
else:
    print(-1)

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

INF = float('inf')
dir = [[0, 1], [0, -1], [1, 0], [-1, 0]]
white = 0
for i in range(h):
    for j in range(w):
        if s[i][j] == ".":
            white += 1

def bfs(si, sj):
    dist = [[INF for i in range(w)] for j in range(h)]
    q = deque([((si, sj), 1)])
    dist[si][sj] = 1

    while q:
        (ni, nj), d = q.popleft()
        for x, y in dir:
            xi = ni + x
            yj = nj + y
            di = d + 1
            if xi < 0 or yj < 0 or xi > h-1 or yj > w-1:
                continue
            if dist[xi][yj] > di and s[xi][yj] == ".":
                dist[xi][yj] = di
                q.append(((xi, yj), di))
    if dist[h-1][w-1] == INF:
        return -1
    else:
        return white - dist[h-1][w-1]

print(bfs(0, 0))

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


ANS=0
for i in range(H):
    ANS+=MAP[i].count(".")

from collections import deque

QUE = deque()
QUE.append((0,0))
MAP[0][0]=0

while QUE:
    (x,y)=QUE.pop()

    for i,j in [(x+1,y),(x-1,y),(x,y+1),(x,y-1)]:
        if i<0 or j<0 or i>=H or j>=W:
            continue
        if MAP[i][j]==".":
            MAP[i][j]=MAP[x][y]+1
            QUE.appendleft((i,j))
            
        
if MAP[H-1][W-1]==".":
    print(-1)
else:
    print(ANS-MAP[H-1][W-1]-1)

Solution (Python):
import sys
stdin = sys.stdin
 
sys.setrecursionlimit(10**5) 
 
def li(): return map(int, stdin.readline().split())
def li_(): return map(lambda x: int(x)-1, stdin.readline().split())
def lf(): return map(float, stdin.readline().split())
def ls(): return stdin.readline().split()
def ns(): return stdin.readline().rstrip()
def lc(): return list(ns())
def ni(): return int(stdin.readline())
def nf(): return float(stdin.readline())

from collections import deque

def bfs(grid: list):
    h = len(grid)
    w = len(grid[0])
    
    dhs = [0, 1, 0, -1]
    dws = [1, 0, -1, 0]
    
    que = deque([(1,(0,0))])
    grid[0][0] = "1"
    
    while que:
        cost, (hcur, wcur) = que.popleft()
    
        for dh, dw in zip(dhs, dws):
            if 0 <= hcur+dh < h and 0 <= wcur+dw < w and grid[hcur+dh][wcur+dw] == ".":
                nex_cost = cost + 1
                grid[hcur+dh][wcur+dw] = str(nex_cost)
                que.append((nex_cost, (hcur+dh, wcur+dw)))
    

h,w = li()

grid = []
for _ in range(h):
    grid.append(lc())

whites = 0
for row in grid:
    whites += row.count(".")

bfs(grid)

if grid[-1][-1] == "
    print(-1)

else:
    print(whites - int(grid[-1][-1]))

Solution (Python):
from collections import deque

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

dxy = [(1,0),(0,1),(-1,0),(0,-1)]
dists = [[-1]*W for i in range(H)]
dists[0][0] = 0
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 dists[ny][nx] >= 0: continue
        if src[ny][nx] == '
        q.append((nx,ny))
        dists[ny][nx] = dists[y][x] + 1
d = dists[-1][-1]
if d == -1:
    print(d)
else:
    white = 0
    for row in src:
        for c in row:
            if c == '.':
                white += 1
    print(white - d - 1)

Solution (Python):
def ABC088D():
    
    H, W = map(int, input().split())
    s = [list(input()) for i in range(H)]
    visited = [[False for i in range(W)] for i in range(H)]
    black_cnt = 0
    for i in range(H):
        for j in range(W):
            if s[i][j] == "
                visited[i][j] = True
                black_cnt += 1
    will_visit = [[0, 0, 0]]
    def sarch(i, j, dist):
        visited[i][j] = True
        if 0 <= i - 1:
            if not visited[i - 1][j]:
                will_visit.append([i - 1, j, dist + 1])
        if 0 <= j - 1:
            if not visited[i][j - 1]:
                will_visit.append([i, j - 1, dist + 1])
        if j + 1 < W:
            if not visited[i][j + 1]:
                will_visit.append([i, j + 1, dist + 1])
        if i + 1 < H:
            if not visited[i + 1][j]:
                will_visit.append([i + 1, j, dist + 1])

    key = 0
    next = 0
    while len(will_visit) > next:
        
        next_i = will_visit[next][0]
        next_j = will_visit[next][1]
        next_dist = will_visit[next][2]
        if not visited[next_i][next_j]:
            if next_i == H - 1 and next_j == W - 1:
                key = next_dist
                break
            sarch(next_i, next_j, next_dist)
        if key != 0:
            break
        next += 1
    if key == 0:
        print(-1)
    else:
        key += 1
        print(H * W - key - black_cnt)
        
ABC088D()

Solution (Python):
import queue
H,W = map(int,input().split())
maze = [0]*H
for i in range(H):
    maze[i] = input()
inf = float('inf')
d = [[inf for i in range(W)] for i in range(H)]
dx = [1,0,-1,0]
dy = [0,1,0,-1]


def bfs():
    que = queue.Queue()
    que.put((0,0))
    d[0][0] = 0
    while que.qsize():
        p = que.get()
        if p == (H-1,W-1):
            break
        for i in range(4):
            nx = p[0]+dx[i]
            ny = p[1]+dy[i]
            if 0 <= nx and nx <= H-1 and 0 <= ny and ny <= W-1 \
            and maze[nx][ny] != '
                d[nx][ny] = d[p[0]][p[1]] + 1
                que.put((nx,ny))

bfs()

count = 0
for i in range(H):
    for j in range(W):
        if maze[i][j] == '
            count += 1

ans = -1
if d[H-1][W-1] != inf:
    ans = H*W-count-1-d[H-1][W-1]
print(ans)

Solution (Python):
from heapq import heappush, heappop
H, W = map(int, input().split())
s = [input() for _ in range(H)]
black = sum(x == '
INF = 10 ** 9
sp = [[INF] * W for _ in range(H)]
sp[0][0] = 0
q = [(0, 0, 0)]
while q:
    dist, prev_x, prev_y = heappop(q)
    for dx, dy in zip([1, 0, -1, 0], [0, -1, 0, 1]):
        x = prev_x + dx
        y = prev_y + dy
        if (0 <= x < W and 0 <= y < H
                and s[y][x] == '.' and dist + 1 < sp[y][x]):
            sp[y][x] = dist + 1
            heappush(q, (dist + 1, x, y))

if sp[H - 1][W - 1] == INF:
    print(-1)
else:
    print(H * W - black - sp[H - 1][W - 1] - 1)

Solution (Python):
def AppendQue(now, depth, que, past_visit, maze):
    Next = ((now[0] - 1, now[1]), (now[0], now[1] - 1),
            (now[0] + 1, now[1]), (now[0], now[1] + 1))
    for h, w in Next:
        if h < 0 or w < 0 or h >= H or w >= W:
            continue
        elif (h, w) in past_visit:
            continue
        elif maze[h][w] == "
            continue
        elif (h, w) in que:
            continue

        que.append((h, w))
        depth[(h, w)] = depth[now] + 1


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

maze = []
black = 0
for i in range(H):
    maze.append(input())
    black += maze[i].count("

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

que = []
now = (0, 0)
depth = {}
depth[now] = 1
que.append(now)
past_visit = set()
while True:
    if len(que) == 0:
        print(-1)
        exit()
    now, que = que[0], que[1:]
    if now == (H - 1, W - 1):
        break
    past_visit.add(now)
    AppendQue(now, depth, que, past_visit, maze)

print(H * W - black - depth[(H - 1, W - 1)])

Solution (Python):
H, W = map(int, input().split())

table = [["
table = [["

cnt = 0
for r in table:
    for s in r:
        if s == ".":
            cnt += 1


connect = [[0 for _ in range(W+1)] for _ in range(H+1)]
used = [[1000 for _ in range(W+1)] for _ in range(H+1)]


for r in range(1, H + 1):
    for c in range(W + 1):
        if table[r][c] == ".":
            connect_list = []
            if table[r+1][c] == ".":
                connect_list.append([r+1, c])

            if table[r-1][c] == ".":
                connect_list.append([r-1, c])

            if table[r][c+1] == ".":
                connect_list.append([r, c+1])

            if table[r][c-1] == ".":
                connect_list.append([r, c-1])

            connect[r][c] = connect_list



queue = [[1, 1, 0]]


def bfs(x, y, num):
    while len(queue) > 0:
        r, c, num = queue.pop(0)
        if used[r][c] == 1000:
            used[r][c] = num
            for t in connect[r][c]:
                queue.append([t[0], t[1], num + 1])


bfs(1, 1, 0)

if used[H][W] == 1000:
    print(-1)

else:
    print(cnt - used[H][W] - 1)

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

dxs = [1, 0, -1, 0]
dys = [0, 1, 0, -1]

dists = [[3000]*w for _ in range(h)]
dists[0][0] = 1
que = deque([(0, 0, 1)])
while len(que) > 0:
    i, j, score = que.popleft()
    
    for dy, dx in zip(dys, dxs):
        i_next, j_next = i+dy, j+dx
        if i_next < 0 or i_next >= h or j_next < 0 or j_next >= w:
            continue
        if s[i_next][j_next] == '
            continue
        if dists[i_next][j_next] <= score+1:
            continue
        dists[i_next][j_next] = score+1
        que.append((i_next, j_next, score+1))


if dists[h-1][w-1] == 3000:
    print(-1)
    exit()
d_min = dists[h-1][w-1]
n_black = 0
for i in range(h):
    for j in range(w):
        if s[i][j] == '
            n_black += 1
print(h*w - n_black - d_min)

Solution (Python):
h, w = map(int, input().split())
black = 0
ma = []
maa = []
go = [[0, 0]]
for i in range(h):
    ma.append(list(input()))
    black += ma[i].count("
    maa.append([0] * w)
maa[0][0] = 1
while go != []:
    k = go.pop(0)
    if k[0] == h - 1 and k[1] == w - 1:
        print(h * w - black - maa[h - 1][w - 1])
        break
    if k[0] != 0:  
        if ma[k[0] - 1][k[1]] == "." and maa[k[0] - 1][k[1]] == 0:
            maa[k[0] - 1][k[1]] = maa[k[0]][k[1]] + 1
            go.append([k[0] - 1, k[1]])
    if k[0] != h-1:  
        if ma[k[0] + 1][k[1]] == "." and maa[k[0] + 1][k[1]] == 0:
            maa[k[0] + 1][k[1]] = maa[k[0]][k[1]] + 1
            go.append([k[0] + 1, k[1]])
    if k[1] != 0:  
        if ma[k[0]][k[1]-1] == "." and maa[k[0]][k[1]-1] == 0:
            maa[k[0]][k[1]-1] = maa[k[0]][k[1]] + 1
            go.append([k[0], k[1]-1])
    if k[1] != w-1:  
        if ma[k[0]][k[1]+1] == "." and maa[k[0]][k[1]+1] == 0:
            maa[k[0]][k[1]+1] = maa[k[0]][k[1]] + 1
            go.append([k[0], k[1] + 1])
else:
    print(-1)

Solution (Python):
from collections import deque

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

s = []
white = 0
for y in range(h):
    s.append(input())
    white += s[y].count('.')

def gets(y, x):
    if 1 <= y <= h and 1 <= x <= w:
        return s[y - 1][x - 1] == '.'
    else:
        return False

v = set()
q = deque([(1, 1, 0)])
costMin = -1
while len(q) > 0:
    y, x, cost = q.popleft()
    if (y, x) == (h, w):
        costMin = cost
        break

    if (y, x) not in v:
        v.add((y, x))
        if gets(y - 1, x): q.append((y - 1, x, cost + 1))
        if gets(y + 1, x): q.append((y + 1, x, cost + 1))
        if gets(y, x - 1): q.append((y, x - 1, cost + 1))
        if gets(y, x + 1): q.append((y, x + 1, cost + 1))

if costMin < 0:
    print(-1)
else:
    print(white - costMin - 1)

Solution (Python):
from collections import deque

def bfs(maze, visited, sy, sx, gy, gx):
    H, W = len(maze), len(maze[0])
    queue = deque([[sy, sx]])
    visited[sy][sx] = 0
    while queue:
        y, x = queue.popleft()
        if [y, x] == [gy, gx]:
            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-1 and 0<=new_x<=W-1:
                if 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 False

if __name__ == "__main__":
    H, W = map(int, input().split())
    sy, sx = 0, 0
    gy, gx = H-1, W-1

    maze = [input() for _ in range(H)]
    visited = [[-1]*W for _ in range(H)]
    min_root = bfs(maze, visited, sy, sx, gy, gx)
    
    if min_root:
    	white = 0
    	for raw in maze:
    		white += raw.count('.')
    	print(white-min_root-1)
    else:
    	print(-1)

Solution (Python):
H, W = map(int, input().split())
Map = ['' for i in range(H)]
default = 0
for i in range(H):
  Map[i] = input()
  default += Map[i].count('
D = [[H * W + 1 for j in range(W)] for i in range(H)]
D[0][0] = 0
Q = [[0, 0]]
while Q:
  x, y = Q[0]
  Q = Q[1:]
  if x > 0 and Map[x - 1][y] == '.' and D[x][y] + 1 < D[x - 1][y]:
    D[x - 1][y] = D[x][y] + 1
    Q += [[x - 1, y]]
  if x < H - 1 and Map[x + 1][y] == '.' and D[x][y] + 1 < D[x + 1][y]:
    D[x + 1][y] = D[x][y] + 1
    Q += [[x + 1, y]]
  if y > 0 and Map[x][y - 1] == '.' and D[x][y] + 1 < D[x][y - 1]:
    D[x][y - 1] = D[x][y] + 1
    Q += [[x, y - 1]]
  if y < W - 1 and Map[x][y + 1] == '.' and D[x][y] + 1 < D[x][y + 1]:
    D[x][y + 1] = D[x][y] + 1
    Q += [[x, y + 1]]
if D[H - 1][W - 1] < H * W - 1:
  print(H * W - D[H - 1][W - 1] - default - 1)
else:
  print(-1)

Solution (Python):
from collections import deque
H,W = list(map(int,input().split()))
L = [list(input()) for _ in range(H)]  
s = sum(l.count('.') for l in L)
dd = [(0,1),(0,-1),(1,0),(-1,0)]

res = None
que = deque([(0,0,0)])
used = {(0,0)}
while que:
    i,j,cost = que.popleft()
    if i == H-1 and j == W-1:
        res = cost
        break
    for di,dj in dd:
        ni = i+di; nj = j+dj
        if not(0<=ni<H) or not (0<=nj<W) or L[ni][nj]=='
            continue
        que.append((ni,nj,cost+1))
        used.add((ni,nj))
if res:
    print(s-res-1)
else:
    print(-1)

Solution (Python):
import sys
import queue

H,W = map(int,input().split())
white = 0
maze = [['
for y in range(H):
	li = list(input())
	white += li.count('.')
	maze.append(['
maze.append(['



def check(x,y,n):
	if x == W and y == H:
		print (white - n - 1)
		sys.exit()
	elif maze[y][x] == '.':
		maze[y][x] = n
		q.put([x-1,y,n+1])
		q.put([x+1,y,n+1])
		q.put([x,y-1,n+1])
		q.put([x,y+1,n+1])
	else:
		return

q = queue.Queue()
q.put([1,1,0])
while not q.empty():
	x,y,n = q.get()
	check(x,y,n)

print(-1)

Solution (Python):
import sys
import queue

H,W = map(int,input().split())
white = 0
maze = [['
for y in range(H):
	li = list(input())
	white += li.count('.')
	maze.append(['
maze.append(['



def check(x,y,n):
	if 1 <= x < W+1 and 1 <= y < H+1:
		if x == W and y == H:
			print (white - n - 1)
			sys.exit()
		elif maze[y][x] == '.':
			maze[y][x] = n
			q.put([x-1,y,n+1])
			q.put([x+1,y,n+1])
			q.put([x,y-1,n+1])
			q.put([x,y+1,n+1])
		else:
			return
	else:
		return

q = queue.Queue()
q.put([1,1,0])
while not q.empty():
	x,y,n = q.get()
	check(x,y,n)

print(-1)

Solution (Python):
import sys
import queue

H,W = map(int,input().split())
white = 0
maze = []
for y in range(H):
	li = list(input())
	white += li.count('.')
	maze.append(li)

def check(x,y,n):
	if 0 <= x < W and 0 <= y < H:
		if x == W-1 and y == H-1:
			print (white - n - 1)
			sys.exit()
		elif maze[y][x] == '.':
			maze[y][x] = n
			q.put([x-1,y,n+1])
			q.put([x+1,y,n+1])
			q.put([x,y-1,n+1])
			q.put([x,y+1,n+1])
		else:
			return
	else:
		return

q = queue.Queue()
q.put([0,0,0])
while not q.empty():
	x,y,n = q.get()
	check(x,y,n)

print(-1)

Solution (Python):
import sys
import queue

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


white = 0
	
maze = []

for y in range(H):
	li = list(input())
	white += li.count('.')
	maze.append(li)

if maze[0][0] == '
	print (-1)
	sys.exit()

	
maze[H-1][W-1] = 'g'
	
q = queue.Queue()
q.put([0,0,0])

def check(x,y,n):
	if 0 <= x < W and 0 <= y < H:
		if maze[y][x] == 'g':
			print (white - n - 1)
			sys.exit()
		elif maze[y][x] == '.':
			maze[y][x] = n
			q.put([x-1,y,n+1])
			q.put([x+1,y,n+1])
			q.put([x,y-1,n+1])
			q.put([x,y+1,n+1])
		else:
			return
	else:
		return


while not q.empty():
	x,y,n = q.get()
	check(x,y,n)
	
print(-1)

Solution (Python):
from collections import deque
h,w=map(int,input().split())
l=[]
v=0

for _ in range(h):
  b=[0 if i=="." else 1 for i in input()]
  v+=b.count(1)
  l.extend([b])

dq=deque([])
dq.append((0,0,1))

while dq:
  x,y,d=dq.popleft()
  if x==w-1 and y==h-1:break
  for (dx,dy) in zip([-1,1,0,0],[0,0,-1,1]):
    nx=x+dx
    ny=y+dy
    if 0<=nx<w and 0<=ny<h and not l[ny][nx]:
      l[ny][nx]=2
      dq.append((nx,ny,d+1))

if x==w-1 and y==h-1:
  print(h*w-v-d)
else:
  print(-1)

Solution (Python):
R, C = list(map(int, input().split()))
sy, sx = 2, 2
gy, gx = R, C

meiro = ["
meiro = ["

kyori = [[int(0) for x in range(C+2)] for _ in range(R+2)]
kyori[sy-1][sx-1] = 0

visited = [[sy-1,sx-1]]
que = [[sy-1,sx-1]]

while True:
    x = que[0][1]
    y = que[0][0]
    que.pop(0)
    try:
        if meiro[y][x+1] == "." and [y,x+1] not in visited:
            que.append([y,x+1])
            visited.append([y,x+1])
            kyori[y][x+1] = kyori[y][x] + 1
        if meiro[y+1][x] == "." and [y+1,x] not in visited:
            que.append([y+1,x])
            visited.append([y+1,x])
            kyori[y+1][x] = kyori[y][x] + 1
        if meiro[y][x-1] == "." and [y,x-1] not in visited:
            que.append([y,x-1])
            visited.append([y,x-1])
            kyori[y][x-1] = kyori[y][x] + 1
        if meiro[y-1][x] == "." and [y-1,x] not in visited:
            que.append([y-1,x])
            visited.append([y-1,x])
            kyori[y-1][x] = kyori[y][x] + 1
    except:
        IndexError
    if que == []:
        break

if kyori[R][C] == 0:
    print(-1)
    exit(0)

t = 0
for k in range(1,R+1):
    t += meiro[k].count("

print(R*C-kyori[R][C]-t-1)

Solution (Python):
import heapq
import itertools
inf = 10 * 18

H, W = map(int, input().split())
map = [input() for _ in range(H)]
heuristic = {(i, j): int(((H - i) ** 2 + (W - j) ** 2) ** 0.5) for j in range(W) for i in range(H)}
count_white = sum([s.count(".") for s in map])

def astar(init_pos, goal):
    passed_list = [init_pos]
    init_score = distance(passed_list) + heuristic.setdefault(init_pos, inf)
    checked = {init_pos: init_score}
    searching_heap = []
    heapq.heappush(searching_heap, (init_score, passed_list))
    while len(searching_heap) > 0:

        score, passed_list = heapq.heappop(searching_heap)
        last_passed_pos = passed_list[-1]
        if last_passed_pos == goal:
            return passed_list
        for pos in nexts(last_passed_pos):
            new_passed_list = passed_list + [pos]
            pos_score = distance(new_passed_list) +  heuristic.setdefault(pos, inf)
            if pos in checked and checked[pos] <= pos_score:
                continue

            checked[pos] = pos_score
            heapq.heappush(searching_heap, (pos_score, new_passed_list))

    return []

def distance(path):
    return len(path)

def nexts(pos):
    i = pos[0]
    j = pos[1]
    res = []
    
    for p in [(i + 1, j), (i - 1, j), (i, j - 1), (i, j + 1)]:
        if 0<=p[0]<=H-1 and 0<=p[1]<=W-1 and map[p[0]][p[1]] != "
            res.append(p)

    return res
    
path = astar((0,0), (H-1,W-1))

if len(path) == 0:
    print(-1)
else:
    print(count_white - len(path))

Solution (Python):
from collections import deque

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

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

def bfs():
    visited = [[False for _ in range(W)] for _ in range(H)]
    dist = [[0 for _ in range(W)] for _ in range(H)]
    routes = deque()
    routes.append((0, 0))
    visited[0][0] = True

    while len(routes) > 0:
        x, y = routes.popleft()
        for move in moves:
            cx, cy = x + move[0], y + move[1]
            if cx < 0 or cy < 0 or cx >= W or cy >= H or c[cy][cx] == '
                continue
            if cx == W-1 and cy == H-1:
                return sum([line.count('.')for line in c]) - dist[y][x] - 2
            visited[cy][cx] = True
            routes.append((cx, cy))
            dist[cy][cx] = dist[y][x] + 1
    return -1

print(bfs())

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

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

def bfs():
    visited = [[False for _ in range(W)] for _ in range(H)]
    dist = [[0 for _ in range(W)] for _ in range(H)]
    routes = [(0, 0)]
    visited[0][0] = True

    while len(routes) > 0:
        x, y = routes.pop(0)
        for move in moves:
            cx, cy = x + move[0], y + move[1]
            if cx < 0 or cy < 0 or cx >= W or cy >= H or c[cy][cx] == '
                continue
            if cx == W-1 and cy == H-1:
                return sum([line.count('.')for line in c]) - dist[y][x] - 2
            visited[cy][cx] = True
            routes.append((cx, cy))
            dist[cy][cx] = dist[y][x] + 1
    return -1

print(bfs())

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

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

def bfs():
    visited = [[False for _ in range(W)] for _ in range(H)]
    dist = [[[] for _ in range(W)] for _ in range(H)]
    routes = [(0, 0)]
    visited[0][0] = True

    hop_count = 0
    while len(routes) > 0:
        x, y = routes.pop(0)
        for move in moves:
            cx, cy = x + move[0], y + move[1]
            if cx < 0 or cy < 0 or cx >= W or cy >= H or c[cy][cx] == '
                continue
            if cx == W-1 and cy == H-1:
                return sum([line.count('.')for line in c]) - len(dist[y][x]) - 2
            visited[cy][cx] = True
            routes.append((cx, cy))
            dist[cy][cx] += dist[y][x] + [(x, y)]
    return -1

print(bfs())

Solution (Python):


from collections import defaultdict, Counter
from itertools import product, groupby, count, permutations, combinations
from math import pi, sqrt
from collections import deque
from bisect import bisect, bisect_left, bisect_right
from string import ascii_lowercase
from functools import lru_cache
import sys
sys.setrecursionlimit(10000)
INF = float("inf")
YES, Yes, yes, NO, No, no = "YES", "Yes", "yes", "NO", "No", "no"
dy4, dx4 = [0, 1, 0, -1], [1, 0, -1, 0]


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


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

    white = 0
    for _ in range(H):
        line = input()
        field.append(line)
        white += line.count(".")

    cost = [[INF] * W for _ in range(H)]
    cost[0][0] = 1
    q = deque()
    q.append((0, 0))
    while len(q) != 0:
        y, x = q.popleft()

        for i in range(4):
            ny, nx = y + dy4[i], x + dx4[i]

            if inside(ny, nx, H, W) and cost[ny][nx] == INF and field[ny][nx] == ".":
                cost[ny][nx] = cost[y][x] + 1
                q.append((ny, nx))

    if cost[-1][-1] == INF:
        print(-1)
    else:
        print(white - cost[-1][-1])


if __name__ == '__main__':
    main()

Solution (Python):
def next(c,y,x):
    ans = []
    if c[y][x+1] == '.':
        ans.append([y,x+1])
    if c[y][x-1] == '.':
        ans.append([y,x-1])
    if c[y+1][x] == '.':
        ans.append([y+1,x])
    if c[y-1][x] == '.':
        ans.append([y-1,x])
    return ans

def bfs(maze,sy,sx,w,h):
    arrival = [[0 for i in range(w+2)]for k in range(h+2)]
    q = [[sy,sx]]
    arrival[q[0][0]][q[0][1]] = 1
	

    while len(q)>0:
        nextcell = next(maze,q[0][0],q[0][1])
        for i in range(len(nextcell)):
            if arrival[nextcell[i][0]][nextcell[i][1]] == 0:
                q.append([nextcell[i][0],nextcell[i][1]])
                arrival[nextcell[i][0]][nextcell[i][1]] = arrival[q[0][0]][q[0][1]] + 1
        q.pop(0)
    return arrival


h,w = map(int,input().split())
s = []
add = ["
s.append(add)
counter = 0
for i in range(h):
    stemp = list(input())
    for k in range(w):
        if stemp[k] == "
            counter += 1
    stemp.append("
    stemp.insert(0,"
    s.append(stemp)
s.append(add)


arrival = bfs(s,1,1,w,h)

if arrival[h][w] == 0:
    print('-1')
else:
    print(h*w-counter-arrival[h][w])

Solution (Python):
from collections import Counter, deque
from itertools import product

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


def bfs():
    dist = [[float('inf') for _ in range(W)] for _ in range(H)]
    mx = [1, 0, -1, 0]
    my = [0, 1, 0, -1]

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

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

    while que:
        x, y = que.popleft()
        if x == gx and y == gy:
            break

        for dx, dy in zip(mx, my):
            nx = x + dx
            ny = y + dy
            if 0 <= nx < W and 0 <= ny < H:
                if maze[ny][nx] != '
                    que.append((nx, ny))
                    dist[ny][nx] = dist[y][x] + 1

    return dist[gy][gx]


res = bfs()
if res == float('inf'):
    ans = -1
else:
    white = 0
    for i, j in product(range(H), range(W)):
        if maze[i][j] == '.':
            white += 1
    ans = white - res - 1
print(ans)