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):
H, W = list(map(int, input().split()))
s = []
black = 0
for i in range(H):
    s.append(input())
    black += s[i].count('



queue = [[0,0,1]] 
check = [[0,0]]
root = 0
hCurrent, wCurrent = 0, 0
while True:
    root += 1

    if hCurrent == H - 1 and wCurrent == W - 1:
        break
    if len(queue) == 0:
        root = -1
        break

    hCurrent, wCurrent, depth = queue[0]
    queue.pop(0)

    if hCurrent < H - 1:
        if s[hCurrent + 1][wCurrent] != "
            queue.append([hCurrent + 1, wCurrent, depth+1])
            check.append([hCurrent + 1, wCurrent])
    if wCurrent < W - 1:
        if s[hCurrent][wCurrent+1] != "
            queue.append([hCurrent, wCurrent + 1,depth+1])
            check.append([hCurrent, wCurrent + 1])
    if hCurrent > 0:
        if s[hCurrent - 1][wCurrent] != "
            queue.append([hCurrent - 1, wCurrent,depth+1])
            check.append([hCurrent - 1, wCurrent])
    if wCurrent > 0:
        if s[hCurrent][wCurrent - 1] != "
            queue.append([hCurrent, wCurrent-1,depth+1])
            check.append([hCurrent, wCurrent-1])

if root == -1:
    re = -1
else:
    re = max(-1, H * W - depth - black)
    

print(re)

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

import heapq
def dijkstra(adj, n, st=1):
    dj = [2**64] * (n)
    dj[st] = 0
    q = []
    heapq.heappush(q, (0, st))
    while q:
        fc, fn = heapq.heappop(q)
        if dj[fn] < fc: continue
        for tn, lc in adj[fn]:
            if dj[fn] + lc < dj[tn]:
                dj[tn] = dj[fn] + lc
                heapq.heappush(q, (dj[tn], tn))
    return dj

def cid(x):
    return x[0] * W + x[1]

def cl(adj, x, y):
    xid = cid(x)
    yid = cid(y)
    adj[xid].append((yid, 1))
    adj[yid].append((xid, 1))

adj = dict([(x, []) for x in range(H*W)])
for i in range(H):
    for j in range(W):
        if S[i][j] == "
        ni = i + 1
        if ni < H and S[ni][j] == ".":
            cl(adj, (i, j), (ni, j))
        nj = j + 1
        if nj < W and S[i][nj] == ".":
            cl(adj, (i, j), (i, nj))

c = dijkstra(adj, H*W, cid((0,0)))
hwc = c[cid((H-1,W-1))]
print(-1 if hwc == 2**64 else H * W - sum(s.count("

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


whites = sum([i.count('
S[0][0] = 0
goal = [H-1, W-1]
move = ((-1,0), (1,0), (0,-1), (0,1))
queue = deque()
queue.append((0,0))

while queue:
    now = queue.popleft()
    cnt = S[now[0]][now[1]] + 1
    for h,w in move:
        x,y = now[0]+h,now[1]+w
        if x < 0 or x >= H or y < 0 or y >= W:
            continue
        if S[x][y] == '.':
            S[x][y] = cnt
            queue.append((x,y))
if S[H-1][W-1] == '.':
    print(-1)
else:
    print(W*H - 1 - S[H-1][W-1] - whites)
exit(0)

Solution (Python):
H, W = map(int, raw_input().split())
s = []
w = 0
for i in range(H):
  l = raw_input()
  s.append(l)
  w += l.count(".")
C = []
for i in range(H):
  C.append([10000]*W)
C[0][0]=1
q = [(0,0)]
while q:
  i, j = q.pop(0)
  for d in [(+1,0),(-1,0),(0,+1),(0,-1)]:
    ni = i+d[0]
    nj = j+d[1]
    if 0<=ni<H and 0<=nj<W and s[ni][nj]=="." and C[i][j]+1<C[ni][nj]:
      C[ni][nj] = C[i][j]+1
      q.append((ni,nj))
if C[H-1][W-1]==10000:
  print -1
else:
  print w-C[H-1][W-1]

Solution (Python):
class BFS():
    def __init__(self, H, W, maze):
        self.H = H
        self.W = W
        self.maze = maze
        self.distance = [[0 for i in range(self.W)] for j in range(self.H)]
        self.sx = 0
        self.sy = 0
        self.gx = W-1
        self.gy = H-1

    def bfs(self):
        queue = []
        queue.insert(0, (self.sx, self.sy))

        self.distance[self.sx][self.sy] = 0

        while len(queue):
            x, y = queue.pop()

            if x == self.gx and y == self.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 and nx < self.W and 0 <= ny and ny < self.H and self.maze[ny][nx] != '
                    queue.insert(0, (nx, ny))
                    self.distance[ny][nx] = self.distance[y][x] + 1
        return self.distance[self.gy][self.gx]

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

bfs=BFS(H, W, sw)
distance=bfs.bfs()

init_white=0
for i in range(H):
    init_white+=sw[i].count('.')
print(init_white-(distance+1) if distance!=0 else -1)

Solution (Python):
from queue import Queue

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

dcount = -1
for h in range(H):
    for w in range(W):
        if C[h][w] == '.':
            dcount += 1

INF = 10 ** 6
D = [[INF] * W for i in range(H)]
D[0][0] = 0
q = Queue()
q.put((0, 0))

while q.qsize() > 0:
    h, w = q.get()
    if (h, w) == (H-1, W-1):
        break
    for dh, dw in zip((-1, 1, 0, 0), (0, 0, -1, 1)):
        if 0 <= h+dh < H and 0 <= w+dw < W and C[h+dh][w+dw] == '.' and D[h+dh][w+dw] == INF:
            D[h+dh][w+dw] = D[h][w] + 1
            q.put((h+dh, w+dw))

print(dcount - D[H-1][W-1] if D[H-1][W-1] != INF else -1)

Solution (Python):
MAX = 9999999
def m():
    h, w = map(int, input().split())
    s = []
    s.append(list(('
    for j in range(h):
        s.append(list('
    s.append(list(('

    g = [[[] for _ in range(w+2)] for _ in range(h+2)]
    cnt = 0
    for i in range(1, h+1):
        for j in range(1, w+1):
            if s[i][j] == '
                cnt +=1
                continue
            if s[i][j+1] == '.':
                g[i][j].append((i, j+1))
            if s[i+1][j] == '.':
                g[i][j].append((i+1, j))
            if s[i][j-1] == '.':
                g[i][j].append((i, j-1))
            if s[i-1][j] == '.':
                g[i][j].append((i-1, j))

    def dijkstra():
        d = [[MAX for _ in range(w + 2)] for _ in range(h + 2)]
        p = [[MAX for _ in range(w + 2)] for _ in range(h + 2)]
        visited = [[-1 for _ in range(w + 2)] for _ in range(h + 2)]
        d[1][1] = 0
        p[1][1] = -1
        while True:
            mincost = MAX
            for i in range(1, h + 1):
                for j in range(1, w + 1):
                    if visited[i][j] != 1 and d[i][j] < mincost:
                        mincost = d[i][j]
                        u = (i,j)
            if mincost == MAX:
                break
            visited[u[0]][u[1]] = 1

            for i in range(1, h + 1):
                for j in range(1, w + 1):
                    if visited[i][j] != 1 and u in g[i][j]:
                        if d[u[0]][u[1]] +1 < d[i][j]:
                            d[i][j] = d[u[0]][u[1]] + 1
                            p[i][j] = u
                            visited[i][j] = 0
        return d
    ans = dijkstra()
    if ans[h][w] == MAX:
        return -1
    return (w*h) - ans[h][w] - cnt -1

print(m())

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

white = 0
a = [[] for _ in range(h + 2)]
a[0] = [ '
a[h + 1] = [ '
for i in range(h):
    a[i + 1] = ['
    white += a[i + 1].count('.')

a[1][1] = '.'
a[h][w] = '.'

res = [[1,1]]
ans = 1
while 1:
    ans += 1
    temp = []
    for i, j in res:
        if a[i + 1][j] == '.':
            temp.append([i + 1, j])
        if a[i][j + 1] == '.':
            temp.append([i, j + 1])
        if a[i - 1][j] == '.':
            temp.append([i - 1, j])
        if a[i][j - 1] == '.':
            temp.append([i, j - 1])
        a[i][j] = '
    if len(temp) == 0:
        print('-1')
        exit()
    res = list(map(list, set(map(tuple, temp))))
    if [h, w] in res:
        break

print(white - ans)

Solution (Python):
class BFS():
    def __init__(self, H, W, maze):
        self.H = H
        self.W = W
        self.maze = maze
        self.distance = [[0 for i in range(self.W)] for j in range(self.H)]
        self.sx = 0
        self.sy = 0
        self.gx = W-1
        self.gy = H-1


    def bfs(self):
        queue = []
        queue.insert(0, (self.sx, self.sy))

        self.distance[self.sx][self.sy] = 0

        while len(queue):
            x, y = queue.pop()

            if x == self.gx and y == self.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 and nx < self.W and 0 <= ny and ny < self.H and self.maze[ny][nx] != '
                    queue.insert(0, (nx, ny))
                    self.distance[ny][nx] = self.distance[y][x] + 1
        return self.distance[self.gy][self.gx]

H, W = map(int, input().split())
maze = [list(input()) for _ in range(H)]
bfs = BFS(H,W,maze)
distance = bfs.bfs()
black = 0
for i in range(H):
    black += maze[i].count('

if distance == 0:
    print(-1)
else:
    print(H*W - (distance+1)-black)

Solution (Python):
 


from collections import deque


H, W = [int(elem) for elem in input().split(' ')]
s_list = [tuple(input()) for _ in range(H)]
assert len(s_list) == H
assert len(s_list[0]) == W


def calc_num_white(s_list):
    num_white = sum([sum([1 if elem == "." else 0 for elem in row]) for row in s_list])
    return num_white



visited = [[False] * W for _ in range(H)]
queue = deque([[[0, 0], [[0, 0]]]])
visited[0][0] = True
direction = ((-1, 0), (1, 0), (0, -1), (0, 1))
while queue:
    position, path = queue.popleft()
    y, x = position
    for dy, dx in direction:
        next_position = [y+dy, x+dx]
        if next_position[0] < 0 or next_position[0] >= H or next_position[1] < 0 or next_position[1] >= W:
            continue
        elif s_list[next_position[0]][next_position[1]] == "
            continue
        elif visited[next_position[0]][next_position[1]] == True:
            continue
        elif next_position == [H-1, W-1]:
            len_min_path = len(path) + 1
            num_white = calc_num_white(s_list)
            score = num_white - len_min_path
            print(score)
            exit(0)
        else:
            visited[next_position[0]][next_position[1]] = True
            queue.append([next_position, path+[next_position]])
print(-1)

Solution (Python):
from collections import deque

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

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

field = []
field.append(["
for h in range(H):
    field.append(["
field.append(["


def bfs():
    que = deque([])
    next_h = [1,0,-1, 0]
    next_w = [0,1, 0,-1]
    
    que.append([0,1,1])
    
    while len(que) != 0:
        dist,h,w = que.popleft()
        if field[h][w] != ".":
            continue
        
        field[h][w] = str(dist)
        
        for i in range(4):
            if field[h+next_h[i]][w+next_w[i]] == ".":
                que.append([dist+1, h+next_h[i], w+next_w[i]])
            
    return field[H][W]
    

points = 0
for field_row in field:
    for point in field_row:
        if point == ".":
            points += 1


min_dist = bfs()

if min_dist == '.':
    print(-1)
else:
    print(points - int(min_dist) - 1)

Solution (Python):
from collections import Counter, deque
H, W = map( int, input().split())
S = [list(input()) for x in range(H)]
white = 0
for i in range(H):
    white += Counter(S[i])['.']
Goal = False
Able = True

path = 1
Sunuke = [[0,0]]
S[0][0] = '
while Goal == False and len(Sunuke) != 0:
    Sunuke_temp = Sunuke
    Sunuke = []
    path += 1
    for x in Sunuke_temp:
        i = x[0]
        j = x[1]
        if (min(i+1,H-1) == H-1 and j == W-1) or (min(j+1,W-1) == W-1 and i == H-1):
            Goal = True
            Sunuke.append([1,1])
            break
        if S[max(i-1,0)][j] == '.':
            Sunuke.append([i-1,j])
            S[i-1][j] = '
        if S[min(i+1,H-1)][j] == '.':
            Sunuke.append([i+1,j])
            S[i+1][j] = '
        if S[i][max(j-1,0)] == '.':
            Sunuke.append([i,j-1])
            S[i][j-1] = '
        if S[i][min(j+1,W-1)] == '.':
            Sunuke.append([i,j+1])
            S[i][j+1] = '

print(-1 if len(Sunuke) == 0 else white - path)

Solution (Python):
from collections import deque

class Map_input():

    def __init__(self):
        line = input().split(" ")
        self.H = int(line[0])
        self.W = int(line[1])
        Map = [[] for i in range(self.H)]
        for i in range(self.H):
            line = input()
            for j in range(self.W):
                if line[j] == ".":
                    Map[i].append(0)
                else:
                    Map[i].append(1)
        self.Map = Map

class Maze_min():
    dx = [1, 0, -1, 0]
    dy = [0, 1, 0, -1]
    def __init__(self, H, W, Map, start, goal):
        self.H = H
        self.W = W
        self.Map = Map
        self.goal = goal
        self.queue = deque([start])
        self.dist = [[-1]*W for i in range(H)]
        self.dist[start[0]][start[1]] = 0

    def min_step(self):
        while len(self.queue) > 0:
            p = self.queue.popleft()
            if p == self.goal:
                break
            else:
                for i in range(len(Maze_min.dx)):
                    (nx, ny) = (p[0] + Maze_min.dx[i], p[1] + Maze_min.dy[i])
                    if nx in range(self.H) and ny in range(self.W) and self.Map[nx][ny] == 0 and self.dist[nx][ny] == -1:
                        self.queue.append((nx, ny))
                        self.dist[nx][ny] = self.dist[p[0]][p[1]] + 1
        return self.dist[self.goal[0]][self.goal[1]]

M = Map_input()
maze = Maze_min(M.H, M.W, M.Map, (0, 0), (M.H-1, M.W-1))
black_num = (sum(list(map(sum, M.Map))))
d = maze.min_step()
if d == -1:
    print(-1)
else:
    print(M.H*M.W - maze.min_step() - black_num -1)

Solution (Python):
arr=[]
numbero=list(map(int, input().split()))
for i in range(numbero[0]):
    arr.append(input())
way=[[0 for i in range(numbero[1])] for j in range(numbero[0])]
way[0][0]=1
head=0
whoop=[[0,0]]
while head<len(whoop):
    u=whoop[head][0]
    v=whoop[head][1]
    head+=1
    if u>0:
        if way[u-1][v]==0 and arr[u-1][v]=='.':
            way[u-1][v]=way[u][v]+1
            whoop.append([u-1,v])
    if v>0:
        if way[u][v-1]==0 and arr[u][v-1]=='.':
            way[u][v-1]=way[u][v]+1
            whoop.append([u,v-1])
    if u<numbero[0]-1:
        if way[u+1][v]==0 and arr[u+1][v]=='.':
            way[u+1][v]=way[u][v]+1
            whoop.append([u+1,v])
    if v<numbero[1]-1:
        if way[u][v+1]==0 and arr[u][v+1]=='.':
            way[u][v+1]=way[u][v]+1
            whoop.append([u,v+1])
if way[numbero[0]-1][numbero[1]-1]==0:
    print(-1)
else:
    head=0
    for i in arr:
        head+=i.count('.')
    print(head-way[numbero[0]-1][numbero[1]-1])

Solution (Python):

import bisect
import heapq
import math
import random
import sys
from collections import Counter, defaultdict
from decimal import ROUND_CEILING, ROUND_HALF_UP, Decimal
from functools import lru_cache, reduce
from itertools import combinations, combinations_with_replacement, product, permutations
from operator import add, mul

sys.setrecursionlimit(10000)


def read_int():
    return int(input())


def read_int_n():
    return list(map(int, input().split()))


def read_float():
    return float(input())


def read_float_n():
    return list(map(float, input().split()))


def read_str():
    return input()


def read_str_n():
    return list(map(str, input().split()))


def error_print(*args):
    print(*args, file=sys.stderr)


def mt(f):
    import time

    def wrap(*args, **kwargs):
        s = time.time()
        ret = f(*args, **kwargs)
        e = time.time()

        error_print(e - s, 'sec')
        return ret

    return wrap


@mt
def slv(H, W, S):
    
    
    
    
    
    
    
    

    def d(s):
        dist = defaultdict(lambda : sys.maxsize)
        q =[]
        dist[s] = 0
        heapq.heappush(q, (dist[s], s))
        while q:
            c, u = heapq.heappop(q)
            if dist[u] > c:
                continue
            i, j = u
            g = []            
            if i > 0 and S[i-1][j] == '.':
                g.append((i-1, j))

            if j > 0 and S[i][j-1] == '.':
                g.append((i, j-1))

            if i < H-1 and S[i+1][j] == '.':
                g.append((i+1, j))

            if j < W-1 and S[i][j+1] == '.':
                g.append((i, j+1))
            
            for v in g:
                alt = dist[u] + 1
                if dist[v] > alt:
                    dist[v] = alt
                    heapq.heappush(q, (alt, v))
        return dist

    dist = d((0, 0))[(H-1, W-1)]
    if dist == sys.maxsize:
        return -1
    return (H * W - sum(map(lambda x: x.count('


def main():
    H, W = read_int_n()
    S = [read_str() for _ in range(H)]

    
    print(slv(H, W, S))


if __name__ == '__main__':
    main()

Solution (Python):
h,w=map(int,input().split())
s=[]
p=0
for i in range(h):
    t=list(input())
    p+=t.count("
    s.append(t)
t=[[0]*w for i in range(h)]
t[0][0]=1
u=[(0,0)]
while u:
    (x,y)=u[0]
    for i,j in [(0,-1),(0,1),(-1,0),(1,0)]:
        xx=x+i
        yy=y+j
        if (xx!=-1 and xx!=h and yy!=-1 and yy!=w):
            if s[xx][yy]=="."and t[xx][yy]==0:
                u.append((xx,yy))
                if t[xx][yy]==0:
                    t[xx][yy]+=t[x][y]+1
                else:
                    t[xx][yy]+=min(t[xx][yy],t[x][y]+1)
    u.pop(0)
if t[h-1][w-1]==0:
    print(-1)
else:
    print(h*w-p-t[h-1][w-1])

Solution (Python):
from collections import deque

h, w = map(int, input().split())
grid = []
for i in range(h):
    grid.append([j for j in input()])

parent = [[-1 for j in range(w)] for i in range(h)]


def bfs(s):
    q = deque()
    check = [[0 for j in range(w)] for i in range(h)]

    q.append(s)
    check[s[0]][s[1]] = 1
    while len(q) != 0:
        u = q.popleft()
        x, y = u[0], u[1]
        if x > 0 and grid[x-1][y] == "." and check[x-1][y] == 0:
            check[x-1][y], parent[x-1][y] = 1, u
            q.append((x-1, y))
        if y > 0 and grid[x][y-1] == "." and check[x][y-1] == 0:
            check[x][y-1], parent[x][y-1] = 1, u
            q.append((x, y-1))
        if x < h-1 and grid[x+1][y] == "." and check[x+1][y] == 0:
            check[x+1][y], parent[x+1][y] = 1, u
            q.append((x+1, y))
        if y < w-1 and grid[x][y+1] == "." and check[x][y+1] == 0:
            check[x][y+1], parent[x][y+1] = 1, u
            q.append((x, y+1))

        check[x][y] = 2


def main():
    bfs((0, 0))

    if parent[h-1][w-1] != -1:
        x, y = h-1, w-1
        while x != 0 or y != 0:
            grid[x][y] = "
            x, y = parent[x][y]
        grid[0][0] = "

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

    else:
        pt = -1

    print(pt)


if __name__ == '__main__':
    main()

Solution (Python):
from collections import deque

h, w = map(int, input().split())
grid = []
for i in range(h):
    grid.append([j for j in input()])

parent = [[-1 for j in range(w)] for i in range(h)]


def bfs(s):
    q = deque()
    check = [[0 for j in range(w)] for i in range(h)]

    q.append(s)
    check[s[0]][s[1]] = 1
    while len(q) != 0:
        u = q.popleft()
        for i in range(h):
            for j in range(w):
                if grid[i][j] == '.' and check[i][j] == 0:
                    dx, dy = abs(i-u[0]), abs(j-u[1])
                    if dx <= 1 and dy <= 1 and dx + dy < 2:
                        check[i][j] = 1
                        parent[i][j] = u
                        q.append((i, j))
        check[u[0]][u[1]] = 2


def main():
    bfs((0, 0))

    if parent[h-1][w-1] != -1:
        x, y = h-1, w-1
        while x != 0 or y != 0:
            grid[x][y] = "
            x, y = parent[x][y]
        grid[0][0] = "

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

    else:
        pt = -1

    print(pt)


if __name__ == '__main__':
    main()

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

grid=[]
S=""
for i in range(W+2):
    S = S+'
grid.append(S)
for i in range(H):
    grid.append('
grid.append(S)

reached=[]
for i in range(H+2):
    reached.append([0*j for j in range(W+2)])

number_of_black_grid=0
for row in grid:
    number_of_black_grid += row.count('
s_x=1
s_y=1
g_x=W
g_y=H

def isGoal(x,y,g_x,g_y):
    if x==g_x and y==g_y:
        return True
    else:
        return False

def BFS_search(s_x, s_y, g_x, g_y):
    queue=[]
    queue.append([s_y, s_x, 0])
    reached[s_y][s_x]=0
    while len(queue)>0:
        v=queue.pop(0)
        if grid[v[0]+1][v[1]]=='.' and reached[v[0]+1][v[1]]==0 and [v[0]+1, v[1]]!=[s_y, s_x]:
            reached[v[0]+1][v[1]]=v[2]+1
            if isGoal(v[1], v[0]+1, g_x, g_y):
                break
            else:
                queue.append([v[0]+1, v[1], v[2]+1])
        if grid[v[0]][v[1]+1]=='.' and reached[v[0]][v[1]+1]==0 and [v[0], v[1]+1]!=[s_y, s_x]:
            reached[v[0]][v[1]+1]=v[2]+1
            if isGoal(v[1]+1, v[0], g_x, g_y):
                break
            else:
                queue.append([v[0], v[1]+1, v[2]+1])
        if grid[v[0]-1][v[1]]=='.' and reached[v[0]-1][v[1]]==0 and [v[0]-1, v[1]]!=[s_y, s_x]:
            reached[v[0]-1][v[1]]=v[2]+1
            if isGoal(v[1], v[0]-1, g_x, g_y):
                break
            else:
                queue.append([v[0]-1, v[1], v[2]+1])
        if grid[v[0]][v[1]-1]=='.' and reached[v[0]][v[1]-1]==0 and [v[0], v[1]-1]!=[s_y, s_x]:
            reached[v[0]][v[1]-1]=v[2]+1
            if isGoal(v[1]-1, v[0], g_x, g_y):
                break
            else:
                queue.append([v[0], v[1]-1, v[2]+1])

BFS_search(s_x, s_y, g_x, g_y)
if reached[g_y][g_x] == 0:
    print(-1)
else:
    maximum_score = ((H+2)*(W+2)-number_of_black_grid)-(reached[g_y][g_x]+1)
    print(maximum_score)

Solution (Python):
from collections import deque

def main():
	h, w = list(map(int, input().split()))

	cs = [list(input()) for _ in range(h)]
	ds = [[10 ** 10 for _ in range(w)] for _ in range(h)]

	goal = (h - 1, w - 1)
	move = [(1, 0), (0, -1), (-1, 0), (0, 1)]
	q = deque()
	
	ds[0][0] = 0
	q.append((0, 0))

	while len(q) >= 1:
		cur = q.popleft()
		if cur == goal:
			break

		for i in range(4):
			if 0 <= cur[0] + move[i][0] < h and 0 <= cur[1] + move[i][1] < w:
				if cs[cur[0] + move[i][0]][cur[1] + move[i][1]] == ".":
					if ds[cur[0] + move[i][0]][cur[1] + move[i][1]] == 10 ** 10:
						q.append((cur[0] + move[i][0], cur[1] + move[i][1]))
						ds[cur[0] + move[i][0]][cur[1] + move[i][1]] = ds[cur[0]][cur[1]] + 1

	if ds[goal[0]][goal[1]] < 10 ** 10:
		print(counter(cs) - ds[goal[0]][goal[1]] - 1)
	else:
		print(-1)

def counter(cs):
	ans = 0
	for c in cs:
		ans += c.count(".")
	return ans

if __name__ == '__main__':
	main()

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

R, C = map(int, input().split())
c = [["
tekazu = [[0 for _ in range(C + 2)] for _ in range(R + 2)]

def bfs(start, goal):
	queue = deque([start])
	visited = []
	while queue:
		
		label = queue.pop()
		
		if label == goal:
			visited.append(label)
			return True

		if label not in visited:
			visited.append(label)
			
			if c[label[0] + 1][label[1]] == "." and [label[0] + 1, label[1]] not in visited:
				queue.appendleft([label[0] + 1, label[1]])
				tekazu[label[0] + 1][label[1]] = tekazu[label[0]][label[1]] + 1

			if c[label[0] - 1][label[1]] == "." and [label[0] - 1, label[1]] not in visited:
				queue.appendleft([label[0] - 1, label[1]])
				tekazu[label[0] - 1][label[1]] = tekazu[label[0]][label[1]] + 1

			if c[label[0]][label[1] + 1] == "." and [label[0], label[1] + 1] not in visited:
				queue.appendleft([label[0], label[1] + 1])
				tekazu[label[0]][label[1] + 1] = tekazu[label[0]][label[1]] + 1

			if c[label[0]][label[1] - 1] == "." and [label[0], label[1] - 1] not in visited:
				queue.appendleft([label[0], label[1] - 1])
				tekazu[label[0]][label[1] - 1] = tekazu[label[0]][label[1]] + 1
		
	return False

if bfs([1, 1], [R, C]) == False:
	print(-1)
else:
	num = 0
	for r in c:
		num += r.count(".")
	print(num - tekazu[R][C] - 1)

Solution (Python):
from collections import deque
H,W = map(int,input().split())
s = [list(input()) for _ in range(H)]
if s[0][0] == '
    print(-1)
    exit()
m = s[:]
goal = [H-1,W-1]
move = ((-1,0),(1,0),(0,-1),(0,1))
queue = deque()
queue.append((0,0))
m[0][0] = 0
while queue:
    now = queue.popleft()
    count = m[now[0]][now[1]] + 1
    for h,w in move:
        y,x = now[0]+h,now[1]+w
        if y < 0 or y >= H or x < 0 or x >= W:
            continue
        if m[y][x] == '.':
            m[y][x] = count
            queue.append((y,x))
    if m[H-1][W-1] != '.':
        break
if m[H-1][W-1] == '.':
    print(-1)
    exit()
ans = H*W - m[H-1][W-1] - 1 - sum([i.count('
print(ans)

Solution (Python):
from collections import deque
H, W = map(int, input().split())
grid = [list(input()) for i in range(H)]
flag = [[-1 for i in range(W)] for j in range(H)]
whites = sum(grid[i].count('.') for i in range(H))

q = deque()
q.append([0,0])
flag[0][0] = 0
dx = [1, -1, 0, 0]
dy = [0, 0, 1, -1]
while q:
    v = q.popleft()
    for j in range(4):
        if 0 <= v[0] + dx[j] < H and 0 <= v[1] + dy[j] < W and grid[v[0]+dx[j]][v[1]+dy[j]] == '.' and flag[v[0]+dx[j]][v[1]+dy[j]] == -1:
            flag[v[0]+dx[j]][v[1]+dy[j]] = flag[v[0]][v[1]] + 1
            q.append([v[0]+dx[j], v[1]+dy[j]])
if flag[H-1][W-1] == -1:
    print(-1)
else:
    print(whites - flag[H-1][W-1] - 1)

Solution (Python):
import queue

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

temp = [[-1 for j in range(W+2)]]
B = temp+[[] for i in range(H)]+temp

dot = 0
for i in range(1,H+1):
    S = input()
    B[i].append(-1)
    for s in S:
        if s==".":
            B[i].append(H*W)
            dot += 1
        else:
            B[i].append(-1)
    B[i].append(-1)
    
Q = queue.Queue()
Q.put((1,1))
B[1][1]=1

min_root = dot
isok = False
while(not Q.empty()):
    y,x = Q.get()
    L = [[y-1,x],[y+1,x],[y,x-1],[y,x+1]]
    move = B[y][x]+1
    for dy,dx in L:
        if move < B[dy][dx]:
            Q.put((dy,dx))
            B[dy][dx] = move
            if dy==H and dx==W: isok=True
    

if isok:
    print(dot-B[H][W])
else:
    print(-1)

Solution (Python):
from collections import deque

h, w = map(int, input().split())
maze = {(i,j):c for i in range(h) for j, c in enumerate(input())}

blacks = sum(c == '

def bfs(i, j):
    dq = deque()
    dq.appendleft((1, (i, j)))
    while dq:
        steps, (i, j) = dq.pop()
        if (i, j) == (h-1, w-1):
            return steps
        if maze.get((i, j), '
            continue
        maze[(i, j)] = '
        dirs = ((-1, 0), (1, 0), (0, 1), (0, -1))
        dq.extendleft((steps+1, (i+di, j+dj)) for di, dj in dirs)

res = bfs(0, 0)
print(-1 if res is None else h*w - res - blacks)

Solution (Python):
from collections import deque

H, W = map(int, input().split())
grid = [list(input()) for _ in range(H)]
dot_cnt = 0
for g in grid:
    dot_cnt += g.count('.')
sy = 0
sx = 0
gy = H - 1
gx = W - 1

deq = deque()
deq.append((0, 0))
grid[0][0] = 0

y_list = [-1, 1, 0, 0]
x_list = [0, 0, -1, 1]

while deq:
    y, x = deq.popleft()
    if y == gy and x == gx:
        break
    for i in range(len(y_list)):
        dy = y + y_list[i]
        dx = x + x_list[i]
        if dy < 0 or H <= dy or dx < 0 or W <= dx:
            continue
        if grid[dy][dx] == '.':
            deq.append((dy, dx))
            grid[dy][dx] = grid[y][x] + 1
if grid[gy][gx] == '.':
    print(-1)
else:
    print(dot_cnt - (grid[gy][gx] + 1))

Solution (Python):
H,W = map(int, input().split())
S = [input() for i in range(H)]
queue = [(0,0,1)]
done ={(0,0)}
count = sum(row.count("

def bfs(x,y,c):
    if(x<0 or y<0 or x>=W or y>=H or S[y][x]=="
        return
    
    if(x,y) in done:
        return
    
    queue.append((x,y,c+1))
    done.add((x,y))

dx = [1,-1,0,0]
dy = [0,0,1,-1] 
flag= -1
while queue:
    x,y,c = queue.pop(0)
    if x==W-1 and y==H-1:
        flag=1
        break
    for i in range(4):
        bfs(x+dx[i],y+dy[i],c)

print(flag if flag == -1 else (H*W-count-c))