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

def bfs(H,W,G):
    d  = [[-1] * W for i in range(H)]
    dx = [1,0,-1,0]
    dy = [0,1,0,-1]
    q = deque([])
    q.append((0,0))
    d[0][0] = 0

    while(len(q) != 0):
        x,y = q.popleft()

        if(x == (H-1) & y == (W-1)):
            break

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

            if (0 <= nx and nx <= (H-1) and 0<= ny and ny <= (W-1) and G[nx][ny] == 0 and d[nx][ny] == -1):
                q.append((nx,ny))
                d[nx][ny] = d[x][y]+1
    return d


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

for i in range(H):
    a = input()
    for j in range(len(a)):
        if a[j] == "
            G[i][j] = 1

d = bfs(H,W,G)
point = -1

if d[H-1][W-1] != -1:
    point = H * W - sum(map(sum,G)) - d[H-1][W-1] -1

print(point)

Solution (Python):
height, width = map(int, input().split(" "))
grids = list()
grids_accessed = list()
whites = 0
for h in range(height):
    inputted = input()
    whites += inputted.count(".")
    grids.append(list(inputted))
    grids_accessed.append([False]*len(inputted))


def get_next(x, y):
    nexts = ((x-1, y),
             (x+1, y),
             (x, y-1),
             (x, y+1))
    for x, y in nexts:
        if (0 <= x <= width-1) and (0 <= y <= height-1):
            if grids[y][x] == ".":
                yield x, y


def dfs():
    queue = list()
    x, y = 0, 0
    queue.append((x, y))
    while True:
        try:
            x, y = queue.pop(0)
        except IndexError:
            return
        if x == width-1 and y == height-1:
            return
        for n_x, n_y in get_next(x, y):
            if grids_accessed[n_y][n_x] is False:
                grids_accessed[n_y][n_x] = (x, y)
                queue.append((n_x, n_y))


def get_shortest():
    x, y = width-1, height-1
    distance_traveled = 0
    while True:
        if x == 0 and y == 0:
            return distance_traveled
        else:
            x, y = grids_accessed[y][x]
            distance_traveled += 1


dfs()
if grids_accessed[height-1][width-1] is False:
    print(-1)
else:
    d = get_shortest() + 1
    score = whites - d
    if score < 0:
        score = -1
    print(score)

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





sys.setrecursionlimit(10**9)

num = 10**8
d = [(1,0),(-1,0),(0,1),(0,-1)]
H,W = map(int,input().split())
maze = [list(input()) for _ in range(H)]
visited=[[0 for _ in range(W)]for _ in range(H)]
def bfs(maze,visited,x,y):
    queue = deque()
    queue.append([0,0])
    visited[x][y] = 1
    while queue:
        x,y = queue.popleft()
        if x == H-1 and y == W-1:
            return visited[x][y]
        for dx,dy in d:
            nx,ny=x+dx,y+dy
            if 0<=nx<H and 0<=ny<W:
                if maze[nx][ny] == "." and visited[nx][ny] == 0:
                    visited[nx][ny]=visited[x][y]+1
                    queue.append([nx,ny])
    return -1
def main():
    """code here"""
    cnt = 0
    for i in range(H):
        for j in range(W):
            if maze[i][j]==".":
                cnt+=1
    ans = bfs(maze,visited,0,0)
    if ans == -1:
        print(-1)
        exit()

    print(cnt-ans)
    
    
if __name__ == '__main__':
    main()

Solution (Python):
from collections import deque
H, W = map(int,input().split())
grid = [list(input()) for _ in range(H)]
w_cnt = 0
for i in range(H):
    w_cnt += grid[i].count('.')


inf = float('inf')
d = [[inf]*W for _ in range(H)]
dx = [0,1,0,-1]
dy = [1,0,-1,0]


d[0][0] = 0
que = deque()
que.append([0,0])
while len(que) != 0:
    p = que.popleft()
    if p[0] == W-1 and p[1] == H-1:break
    for i in range(4):
        nx = p[0] + dx[i]
        ny = p[1] + dy[i]
        
        if 0 <= nx <= W-1 and 0 <= ny <= H-1 and grid[ny][nx] == '.' and d[ny][nx] == inf:
            que.append([nx,ny])
            d[ny][nx] = d[p[1]][p[0]] + 1



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

Solution (Python):
h,w = map(int,input().split())
s = list(list(input())for i in range(h))
cntng = 0
for i in range(h):
    cntng+= s[i].count("


start = (0,0) 
goal = (h-1,w-1)
vec = ((1,0),(0,1),(-1,0),(0,-1))

stack = [start]
move = 0

while stack:
    next = []
    move+=1
    for y,x in stack:
        for ny,nx in vec:
            ty,tx = y+ny,x+nx
            
            if ty>h-1 or tx>w-1 or ty<0 or tx<0:continue
            if s[ty][tx] == ".":
                s[ty][tx] = move
                next.append((ty,tx))
    stack = next
         
    stack = next
    if goal in stack:
        break
if s[h-1][w-1]== ".":
    print(-1)
    exit(0)
ans = max(0,h*w - (move+1)-cntng)
print(ans)

Solution (Python):
from collections import deque
d=deque()
e=deque()
h,w=map(int,input().split())
field=[0 for i in range(h+2)]
field[0]=[True for i in range(w+2)]
distance=0
white=0
for i in range(h):
    s=input()
    a=[False for i in range(w+2)]
    a[0]=True
    for j in range(w):
        if s[j]=="
            a[j+1]=True
        else:
            white+=1

    a[w+1]=True
    field[i+1]=a
field[h+1]=[True for i in range(w+2)]
d.append((1,1))
ans=-1
while d:
    while d:
        some=d.popleft()
        index1,index2=some[0],some[1]
        if index1==h and index2==w:
            ans=distance
        if field[index1-1][index2]==False:
                field[index1-1][index2]=True
                e.append((index1-1,index2))
        if field[index1+1][index2]==False:
                field[index1+1][index2]=True
                e.append((index1+1,index2))
        if field[index1][index2+1]==False:
                field[index1][index2+1]=True
                e.append((index1,index2+1))
        if  field[index1][index2-1]==False:
                field[index1][index2-1]=True
                e.append((index1,index2-1))
    distance+=1
    d=e
    e=deque()
if ans>=0:
    print(white-ans-1)
else:
    print(-1)

Solution (Python):
from collections import deque
H, W = map(int,input().split())
maze = [input() for i in range(H)]
visit = [[-1]*W for i in range(H)]
x, y = 0, 0
cnt = 0
for i in range(H):
  for j in range(W):
    if maze[i][j] == ".":
      cnt += 1
def bfs(maze, visit, x, y):
  queue = deque()
  queue.append([0, 0])
  visit[y][x] = 0
  while queue:
    y, x = queue.popleft()
    if y == H-1 and x == W-1:
      return cnt-visit[y][x]-1
    for i, j in [[1,0],[-1,0],[0,1],[0,-1]]:
      nextx, nexty = x+i, y+j
      if nextx<0 or nextx>=W or nexty<0 or nexty>=H:
        continue
      elif maze[nexty][nextx] != "
        visit[nexty][nextx] = visit[y][x] + 1
        queue.append([nexty,nextx])
  return -1
print(bfs(maze,visit,x,y))

Solution (Python):
from collections import deque

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

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

while q:
  h, w, c = q.popleft()
  if s[h][w] != ".": continue
  s[h][w] = c
  if h+1 == H and w+1 == W: break
  if 0 <= h-1: q.append((h-1, w, c+1))
  if h+1 < H : q.append((h+1, w, c+1))
  if 0 <= w-1: q.append((h, w-1, c+1))
  if w+1 < W : q.append((h, w+1, c+1))
else:
  print(-1)
  exit()

print(H*W - sum([sum([x == "

Solution (Python):
import numpy as np
temp=list(map(int, input().split()))
H=temp[0]
W=temp[1]

s=(0,0)
g=(H-1,W-1)

c=np.zeros((H,W)).astype(int)

for i in range(H):
  temp=input()
  a=np.zeros(W).astype(int)
  for j in range(W):
      if temp[j]=='
        a[j]=1
      else:
        a[j]=0
  c[i]=a
n_black=int(np.sum(c))
def Adj(u):
  adj=[]
  for v in [(u[0]-1,u[1]),(u[0]+1,u[1]),(u[0],u[1]-1),(u[0],u[1]+1)]:
      if v[0]>=0 and v[0]<H and v[1]>=0 and v[1]<W:
        adj.append(v)
  return adj  

color=np.zeros((H,W)).astype(int)
d=np.zeros((H,W)).astype(int)-1
d[s[0],s[1]]=0
def BFS():
  Q=[s]
  while Q !=[]:
    u=Q[0]
    if g==u:
      print(H*W-n_black-(d[u[0],u[1]]+1))
      return
    del Q[0]
    for v in Adj(u):  
      if c[v[0],v[1]]==0 and color[v[0],v[1]]==0:
        color[v[0],v[1]]=1
        d[v[0],v[1]]=d[u[0],u[1]]+1
        Q.append(v)
  print(-1)
BFS()

Solution (Python):
lst = []
H, W = map(int, input().split())
for _ in range(H):
    l = list(input())
    lst.append(l)
gy = H - 1
gx = W - 1

def bfs(sy, sx, gy, gx):
    queue = deque()
    visited = [[-1 for _ in range(W)] for _ in range(H)]
    visited[sy][sx] = 0
    queue.append([sy,sx])
    while queue:
        now = queue.popleft()
        if now == [gy, gx]:
            return visited[gy][gx]
        for _ in range(4):
            ny = now[0] + y[_]
            nx = now[1]+ x[_]
            if 0 < nx < W and 0 < ny < H: 
                if lst[ny][nx] != "X" and visited[ny][nx] == -1:
                    visited[ny][nx] = visited[now[0]][now[1]] +1
                    queue.append([ny, nx])
                    print(now, [gy, gx], visited[ny][nx])
    return -1

from collections import deque
x = [1, -1, 0, 0]
y = [0, 0, 1, -1]

def bfs(sy, sx, gy, gx):
    queue = deque()
    visited = [[-1 for _ in range(W)] for _ in range(H)]
    visited[sy][sx] = 0
    queue.append([sy,sx])
    while queue:
        now = queue.popleft()
        if now == [gy, gx]:
            return visited[gy][gx]
        for _ in range(4):
            ny = now[0] + y[_]
            nx = now[1]+ x[_]
            if 0 <= nx < W and 0 <= ny < H:
                if lst[ny][nx] != "
                    visited[ny][nx] = visited[now[0]][now[1]] +1
                    queue.append([ny, nx])
    return -1

step = bfs(0,0, gy, gx)
if step == -1:
    print(step)
else:
    ans = H * W -  sum([_.count('
    print(ans)

Solution (Python):
from collections import deque

H,W=map(int,input().split())
c=[['
ten=0
for i in range(H):
    ip=list(input())
    ten+=ip.count('.')
    c.append(['
c.append(['
Q=deque([[1,1,1]])

def move(yxc):
    global Q,c
    y,x,cost=yxc[0],yxc[1],yxc[2]
    if c[y+1][x]=='.':
        c[y+1][x]=cost+1
        Q.append([y+1,x,cost+1])
    if c[y-1][x]=='.':
        c[y-1][x]=cost+1
        Q.append([y-1,x,cost+1])
    if c[y][x+1]=='.':
        c[y][x+1]=cost+1
        Q.append([y,x+1,cost+1])
    if c[y][x-1]=='.':
        c[y][x-1]=cost+1
        Q.append([y,x-1,cost+1])

c[1][1]=1
while len(Q)>0:
    move(Q.popleft())

goal=c[H][W]
if goal=='.' or goal=='
    print(-1)
else:
    print(ten-goal)

Solution (Python):
from queue import Queue
h,w = map(int, input().split(' '))
s = [list(input()) for _ in range(h)]
num_w = 0
for i in range(h):
    num_w += s[i].count("
for i in range(h):
    s[i] = ["
s.insert(0,["
s.append(["
q = Queue()
cnt = 0
q.put([1,1,0])
s[1][1]="
Z = -1
while (not q.empty()):
    x,y,cnt = q.get()
    if (x,y) == (h,w):
        Z = cnt
        break
    for (i,j) in [(x+1,y),(x-1,y),(x,y+1),(x,y-1)]:
        if s[i][j] != "
            s[i][j] = "
            q.put([i,j,cnt+1])
if Z == -1:
    print(-1)
else:
    print(h*w-Z-1-num_w)

Solution (Python):
from queue import Queue
h,w = map(int, input().split(' '))
s = [list(input()) for _ in range(h)]
num_w = 0
for i in range(h):
    num_w += s[i].count("
for i in range(h):
    s[i] = ["
s.insert(0,["
s.append(["
q = Queue()
cnt = 0
q.put([1,1,0])
s[1][1]="
Z = -1
while (not q.empty()):
    x,y,cnt = q.get()
    if (x,y) == (h,w):
        Z = cnt
        break
    for (i,j) in [(x+1,y),(x-1,y),(x,y+1),(x,y-1)]:
        if s[i][j] != "
            s[i][j] = "
            q.put([i,j,cnt+1])
if Z == -1:
    print(-1)
else:
    print(h*w-Z-1-num_w)

Solution (Python):
import sys
import collections


def solve():
    readline = sys.stdin.buffer.readline
    mod = 10 ** 9 + 7
    h, w = list(map(int, readline().split()))
    s = [list(str(readline().rstrip().decode('utf-8'))) for _ in range(h)]
    bc = 0
    for i in range(h):
        for j in range(w):
            if s[i][j] == "
                bc += 1

    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
    print((h * w - mt - 1) - bc if mt != 10 ** 10 else -1)


if __name__ == '__main__':
    solve()

Solution (Python):
def solve():
    from collections import deque
    from sys import stdin
    f_i = stdin
    
    H, W = map(int, f_i.readline().split())
    
    brd = '
    for i in range(H):
        brd += '
    brd += '
    
    INF = W * H
    move = (1, -1, W + 2, -W - 2)
    start = W + 3
    goal = (W + 2) * (H + 1) - 2
    distance = [INF] * ((W + 2) * (H + 2))
    distance[start] = 0
    q = deque()
    q.append(start)
    
    while q:
        pos = q.popleft()
        
        if pos == goal:
            black_cell = brd.count('
            ans = H * W - black_cell - distance[pos] - 1
            print(ans)
            break
        
        for mv in move:
            next_pos = pos + mv
            if brd[next_pos] == '.' and distance[next_pos] == INF:
                q.append(next_pos)
                distance[next_pos] = distance[pos] + 1
    else:
        print(-1)

solve()

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

M=["."]*H
C=[[0]*50 for i in range(50)]
L=[[0,0,0] for i in range(10**5)]

s=0
for i in range(H):
    t=list(input())
    s+=t.count("
    M[i]=t

c=0
i=0
p=0
while(True):
    x=L[i][0]
    y=L[i][1]
    p=L[i][2]
    if(i>c):
        print(-1)
        break
    
    if((H-1)==y and (W-1)==x):
        print(H*W-s-p-1)
        exit()

    if(y>0):
        if(M[y-1][x]=="." and C[y-1][x]==0):    
            c+=1
            L[c][0]=x
            L[c][1]=y-1
            L[c][2]=p+1
            C[y-1][x]=1
    if(x<(W-1)):
        if(M[y][x+1]=="." and C[y][x+1]==0):
            c+=1
            L[c][0]=x+1
            L[c][1]=y
            L[c][2]=p+1
            C[y][x+1]=1
    if(y<(H-1)):
        if(M[y+1][x]=="." and C[y+1][x]==0):
            c+=1
            L[c][0]=x
            L[c][1]=y+1
            L[c][2]=p+1
            C[y+1][x]=1
    if(x>0):
       if(M[y][x-1]=="." and C[y][x-1]==0):
            c+=1
            L[c][0]=x-1
            L[c][1]=y
            L[c][2]=p+1
            C[y][x-1]=1
    i+=1

Solution (Python):
from collections import deque


def bfs(sx, sy, gx, gy):
    q = deque([(sx, sy)])
    cost[sx][sy] = 1
    while q:
        x, y = q.popleft()
        for dx, dy in nb:
            nx = x + dx
            ny = y + dy
            if 0 <= nx and nx < h and 0 <= ny and ny < w and grid[nx][ny] == "." and cost[nx][ny] == float("inf"):
                q.append((nx, ny))
                cost[nx][ny] = cost[x][y] + 1
                if nx == gx and ny == gy:
                    return cost[nx][ny]
    return -1


h, w = map(int, input().split())
grid = [list(input()) for _ in range(h)]
cost = [[float("inf")] * w for _ in range(h)]
nb = [(-1, 0), (0, -1), (1, 0), (0, 1)]
black_cnt = 0
ans = 0


for i in range(h):
    black_cnt += str(grid[i]).count("

can_reach = bfs(0, 0, h - 1, w - 1)

if can_reach > 0:
    print(h * w - can_reach - black_cnt)
else:
    print(can_reach)

Solution (Python):
from queue import Queue
H, W = map(int, input().split())
s = [input() for _ in range(H)]
d = [[float('inf')]*W for _ in range(H)]
d[0][0] = 1
cs = 0
for i in range(H):
    for j in range(W):
        if s[i][j] == '
            cs += 1
            d[i][j] = 0


def check(t):
    if 0 <= t[0] < H and 0 <= t[1] < W and d[t[0]][t[1]] == float('inf'):
        return True
    return False


q = Queue()
q.put((0, 0))
while not q.empty():
    h, w = q.get()
    for v in [(h-1, w), (h+1, w), (h, w-1), (h, w+1)]:
        if check(v):
            d[v[0]][v[1]] = d[h][w]+1
            q.put(v)

print(H*W-cs-d[-1][-1] if not (d[-1][-1] == float('inf')) else -1)

Solution (Python):
import queue

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

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

ans = [[0 for _ in range(W)] for _ in range(H)]

q = queue.Queue()

def bfs(x,y):
	global q
	global c
	q.put([x,y])
	s[y][x] = '
	while not q.empty():
		x,y = q.get()
		if [x,y] == [W-1,H-1]:
			return ans[H-1][W-1]
		if x > 0 and s[y][x-1] == '.':
			q.put([x-1,y])
			ans[y][x-1] = ans[y][x] + 1
			s[y][x-1] = '
		if x < W-1 and s[y][x+1] == '.':
			q.put([x+1,y])
			ans[y][x+1] = ans[y][x] + 1
			s[y][x+1] = '
		if y > 0 and s[y-1][x] == '.':
			q.put([x,y-1])
			ans[y-1][x] = ans[y][x] + 1
			s[y-1][x] = '
		if y < H-1 and s[y+1][x] == '.':
			q.put([x,y+1])
			ans[y+1][x] = ans[y][x] + 1
			s[y+1][x] = '

	return -1

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

Solution (Python):


H,W=map(int,input().split())
grid=[None]*H
white=0
for i in range(H):
  grid[i]=input()
  white+=grid[i].count(".")
  
from collections import deque
q=deque()
q.append([0,0,0])

seen=[[False for i in range(W)] for j in range(H)]

while q:
  v=q.popleft()
  y=v[0]
  x=v[1]
  p=v[2]
  if grid[y][x]=="
    continue
  if y==H-1 and x==W-1:
    print(white-(p+1))
    break
  seen[y][x]=True
  if y-1>=0:
    q.append([y-1,x,p+1])
  if y+1<H:
    q.append([y+1,x,p+1])
  if x-1>=0:
    q.append([y,x-1,p+1])
  if x+1<W:
    q.append([y,x+1,p+1])
else:
  print(-1)

Solution (Python):


import sys
sys.setrecursionlimit(1005)
h,w=map(int,input().split())

def go_next(I,J,n):
    n+=1
    global dp,w,h
    if n>1000:
        return
    if 0<=I<h-1:
        if x[I+1][J]=="." and dp[I+1][J]>dp[I][J]+1:
            dp[I+1][J]=dp[I][J]+1
            go_next(I+1,J,n)
    if 0<I<=h-1:
        if x[I-1][J]=="." and dp[I-1][J]>dp[I][J]+1:
            dp[I-1][J]=dp[I][J]+1
            go_next(I-1,J,n)
    if 0<=J<w-1:
        if x[I][J+1]=="." and dp[I][J+1]>dp[I][J]+1:
            dp[I][J+1]=dp[I][J]+1
            go_next(I,J+1,n)
    if 0<J<=w-1:
        if x[I][J-1]=="." and dp[I][J-1]>dp[I][J]+1:
            dp[I][J-1]=dp[I][J]+1
            go_next(I,J-1,n)

x=[]
for i in range(h):
    x.append(list(input()))

c=0
for i in range(h):
    for j in range(w):
        if x[i][j]==".":
            c+=1
dp=[[10000000000 for i in range(w)]for j in range(h)]
dp[0][0]=1
go_next(0,0,0)
if dp[h-1][w-1]==10000000000:
    print(-1)
else:
    print(c-dp[h-1][w-1])

Solution (Python):
import numpy as np
from collections import deque
h, w = map(int, input().split())

inf = 1009
grid = np.zeros((h + 2, w + 2), dtype=int)
for i in range(h):
    grid[i + 1][1:-1] = np.array([1 if j == "." else 0 for j in input()])
white = grid.sum()

cost = np.ones((h+2, w+2), dtype=int)*inf
cost[1][1] = 1

d = ((1, 0), (0, 1), (-1, 0), (0, -1))
to = deque([(1, 1)])
while to:
    x, y = to.popleft()
    c = cost[x][y]
    for xi, yi in d:
        nx = x + xi
        ny = y + yi
        if not grid[nx][ny]:
            continue
        to.append((nx, ny))
        cost[nx][ny] = min(cost[nx][ny], c+1)
        grid[nx][ny] = 0

if cost[-2][-2] == inf:
    ans = -1
else:
    ans = white-cost[-2][-2]
print(ans)

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
import sys
sys.setrecursionlimit(10**5)

H, W = map(int, input().split())
M = [["
seen = deque((1, 1)) 
q = deque([(1, 1, 0)]) 
depth = -1
goal = False
wall = 0
for m in M[1:H+1]:
  for b in m[1:W+1]:
    if b == "
      wall += 1
while q:
  x, y, d = q.popleft()
  if x == W and y == H:
    depth = d
    goal = True
    break
  for dx, dy in zip((0, 0, -1, 1), (1, -1, 0, 0)):
    if M[y+dy][x+dx] != "
      seen.append((x+dx, y+dy))
      q.append((x+dx, y+dy, d+1))

if goal:
  print(W*H-wall-(depth+1))
else:
  print(-1)

Solution (Python):
h,w = map(int,input().split())
s = list(list(input())for i in range(h))
cntng = 0
for i in range(h):
    cntng+= s[i].count("


start = (0,0) 
goal = (h-1,w-1)
vec = ((1,0),(0,1),(-1,0),(0,-1))

stack = [start]
move = 0

while stack:
    next = []
    move+=1
    for y,x in stack:
        for ny,nx in vec:
            ty,tx = y+ny,x+nx
            
            if ty>h-1 or tx>w-1 or ty<0 or tx<0:continue
            if s[ty][tx] == ".":
                s[ty][tx] = move
                next.append((ty,tx))
    stack = next
         
    stack = next
    if goal in stack:
        break
if s[h-1][w-1]== ".":
    print(-1)
    exit(0)
ans = max(0,h*w - (move+1)-cntng)
print(ans)

Solution (Python):
r, c = map(int, input().strip().split())

maze = [["

points = sum(row.count(".") for row in maze)

def BFS_maze(maze, start_pos, goal_pos, symbol_wall):
    sr, sc = start_pos
    maze[sr][sc] = symbol_wall
    queue = [(sr, sc)]

    gr, gc = goal_pos
    maze[gr][gc] = "g"

    depth = 0
    nextqueue = []

    while queue:
        depth += 1
        for pos in queue:
            posr, posc = pos
            for r, c in zip([1, -1, 0, 0], [0, 0, 1, -1]):
                nextr = posr + r
                nextc = posc + c
                terrein = maze[nextr][nextc]
                if terrein == "g":
                    return depth
                elif terrein == symbol_wall:
                    continue
                else:
                    maze[nextr][nextc] = symbol_wall
                    nextqueue.append((nextr, nextc))
        queue = nextqueue[:]
        nextqueue.clear()
    return -1

path_length = BFS_maze(maze, (1, 1), (r, c), "
print(-1 if path_length == -1 else points - path_length - 1)

Solution (Python):
dbflag=""

def next(b):
	result = []
	x,y = b
	if x -1 >= 0 and S[x-1,y]=='.' and depthS[x-1,y]== -1:
		result.append((x-1,y))
	if y -1 >= 0 and S[x,y-1]=='.' and depthS[x,y-1]== -1:
		result.append((x,y-1))
	if x +1 < H and S[x+1,y]=='.' and depthS[x+1,y]== -1:
		result.append((x+1,y))
	if y +1 < W and S[x, y+1]=='.' and depthS[x,y+1]== -1:
		result.append((x,y+1))
	
	return result

  
def debug(*args):
  if ""!=dbflag: print(*args)

if ""!=dbflag: _INDATA=open(dbflag)

def readline():
  if ""!=dbflag:return _INDATA.readline()
  else: return input()


result = -1

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


import numpy as np

S= np.ndarray(shape=(H,W), dtype=object)

for i in range(0,H):
	S[i,0:W] =list(readline().rstrip())
	

wNum = S[S == "."].size
bNum = H * W - wNum

debug(H,W)
debug(S)
debug(wNum)



from collections import deque
queue = deque([])




depthS = np.full((H,W), -1, dtype=int)

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

while len(queue) > 0 and depthS[H-1,W-1]==-1:
	base = queue.popleft()
	baseDepth = depthS[base]

	debug("----")
	debug(base,baseDepth)
	debug("depthS")	
	debug(depthS)	


	neighbors = next(base)
	
	debug('depthS',depthS)
	for n in neighbors: depthS[n[0],n[1]]=baseDepth + 1

	debug('depthS2',depthS)
	debug('neighbors',neighbors)
	
	for n in neighbors:
		queue.append(n)
	debug("queue",queue)	


if depthS[H-1,W-1]!=-1:
	result = wNum - (depthS[H-1,W-1] + 1)
else:
	result = -1

print(result)

Solution (Python):
from collections import deque

def main():
    H, W = map(int, input().split())
    S = list(input() for _ in range(H))

    Q = deque([(0, 0)])
    d = [[float('inf')] * W for _ in range(H)]
    d[0][0] = 0
    dx = [1,0,-1,0]
    dy = [0,1,0,-1]
    while Q:
        h, w = Q.popleft()

        if h == H - 1 and w == W - 1:
            break

        for i in range(4):
            nh = h + dy[i]
            nw = w + dx[i]

            if 0 <= nh < H and 0 <= nw < W and S[nh][nw] == '.' and d[nh][nw] == float('inf'):
                d[nh][nw] = min(d[nh][nw], d[h][w] + 1)
                Q.append((nh,nw))

    if d[H-1][W-1] == float('inf'):
        print(-1)
        exit()
    cnt = 0
    for h in range(H):
        for w in range(W):
            if S[h][w] == '.':
                cnt += 1

    print(cnt - d[H-1][W-1] - 1)

         

    


if __name__ == "__main__":
    main()

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

    t=0
    b=0
    l=0
    r=0
    cntw=0
    si=[[-1 for _ in range(w)]for _ in range(h)]
    before=0
    after=0
    
    si[0][0]=0

    tempw=0

    
    for i in range(0,h):
        for j in range(0,w):
            if s[i][j]=='.':
                tempw+=1


    before=1
    temps=0
    flag=1
    while flag==1:
        
        flag=0
        for i in range(0,h):
            for j in range(0,w):

                if i==0 and j ==0:
                    j=1

                if s[i][j]=='.' :
                    cntw+=1
                    if i==0 or s[i-1][j]=='
                        t=10000
                    else:
                        t=si[i-1][j]
                    if j ==0 or s[i][j-1]=='
                        
                        
                        
                        
                        l=10000
                    else:
                        l=si[i][j-1]
                    if i==h-1 or s[i+1][j] =='
                        b=10000
                    else:
                        b=si[i+1][j]
                    if j==w-1 or s[i][j+1]=='
                        r=10000
                    else:
                        r=si[i][j+1]
                    temps=min(t,l,b,r)+1
                    
                    if temps<si[i][j] or (si[i][j]==-1 and temps!=10001):
                        si[i][j]=temps
                        flag=1
                        
                        
                        


    if si[-1][-1]<0:
        print(-1)
        return
    else:
        print(tempw-si[-1][-1]-1)





if __name__=='__main__':
    main()

Solution (Python):
from collections import deque

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

INF = 10**5
d = [[10**5] * W for _ in range(H)]
d[0][0] = 0

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

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

while len(q):
    y, x = q.popleft()

    if y == H-1 and x == W-1:
        break

    for i in range(4):
        ny = y + dy[i]
        nx = x + dx[i]

        if (0 <= ny < H and 0 <= nx < W and
            maze[ny][nx] != '

            d[ny][nx] = d[y][x] + 1
            q.append((ny, nx))

if d[H-1][W-1] == INF:
    print(-1)
else:
    black = 0
    for a in maze:
        black += a.count('
    
    print(H * W - black - d[H-1][W-1] - 1)

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

white = 0
for i in range(H):
  white += S[i].count('.')

q = [(0,0)]
S[0][0] = 0
while q:
  qq = []
  
  for xy in q:
    x,y = xy
    for dx,dy in ((1,0),(-1,0),(0,1),(0,-1)):
      if not(0 <= x+dx < W) or not(0 <= y+dy < H):
        continue
      elif S[y+dy][x+dx] != '.':
        continue
      S[y+dy][x+dx] = S[y][x] + 1
      qq.append((x+dx,y+dy))
  if S[-1][-1]!=".":
      break    
  q = qq

print(white - S[-1][-1] -1 if S[-1][-1] != '.' else -1)

Solution (Python):
from collections import deque


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

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


def bfs(s):
    q = deque()
    q.append(s)
    maze[s[0]][s[1]] = 1

    while len(q):
        x, y = q.popleft()

        for dx, dy in [(1, 0), (-1, 0), (0, 1), (0, -1)]:
            nx = x + dx
            ny = y + dy

            if (nx, ny) == (H - 1, W - 1) and maze[nx][ny] == '.':
                return maze[x][y] + 1
            elif (0 <= nx < H) and (0 <= ny < W) and maze[nx][ny] == '.':
                maze[nx][ny] = maze[x][y] + 1
                q.append((nx, ny))

    return 0


if maze[0][0] == '.':
    step = bfs((0, 0))
    if step:
        print(H * W - black - step)
    else:
        print(-1)
else:
    print(-1)

Solution (Python):
h,w = map(int,input().split())
S = [list(input()) for i in range(h)]
stack = [[0,0]]
S[0][0] = 0

total_dot = 0
for sss in S:
    for s in sss:
        if s == ".":
            total_dot += 1

move = [[0,1],[1,0],[-1,0],[0,-1]]
cnt = 1
while stack:
    cur_stack = stack
    stack = []
    for si,sj in cur_stack:
        for mi,mj in move:
            i,j = si+mi,sj+mj
            if 0 > i or i >= h or 0 > j or j >= w:
                continue
            next_mass = S[i][j]
            if next_mass == "
                continue
            elif next_mass == ".":
                S[i][j] = cnt
                stack.append([i,j])
    cnt += 1

print(total_dot-S[-1][-1]) if S[-1][-1] != "." else print(-1)