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():
  q = deque()
  q.append([[1,1],0])
  used = set((1,1))
  
  while len(q)>0:
    prv_pos,prv_cost = q.popleft()
    i,j = prv_pos
    for ii,jj in [[i+1,j],[i,j+1],[i-1,j],[i,j-1]]:
      if (ii,jj) in used: continue
      if S[jj][ii]=='.':
        if [ii,jj] == [W,H]:
          return prv_cost+1
        else:
          q.append([[ii,jj],prv_cost+1])
          used.add((ii,jj))
  return -1

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

res = bfs()
if res == -1:
  print(-1)
else:
  cntb = sum([row.count('
  print(H*W-res-cntb-1)

Solution (Python):
from collections import deque

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

field = [list(input()) for _ in range(h)]
dx = [1, 0, -1, 0]
dy = [0, 1, 0, -1]

def bfs(x, y):
    distance = [[-1]*w for _ in range(h)]
    que = deque([])
    que.append((y, x))
    distance[y][x] = 0
    while que:
        y, x = que.popleft()
        if x == w-1 and y == h-1:
            break
        for i, j in zip(dx, dy):
            nx = x + i
            ny = y + j
            if 0 <= nx < w and 0 <= ny < h and field[ny][nx] == "." and distance[ny][nx] == -1:
                distance[ny][nx] = distance[y][x] + 1
                que.append((ny, nx))
    return distance

d = bfs(0, 0)
if d[h-1][w-1] == -1:
    print("-1")
    exit()
cnt = 0
for row in field:
    cnt += row.count(".")

ans = cnt - d[h-1][w-1] - 1
print(ans)

Solution (Python):

from collections import deque
def bfs():
    d = [[float("inf")] * w for i in range(h)]

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

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

    while que:
        p = que.popleft()
        if p[0] == gx and p[1] == gy:
            break
        for i in range(4):
            nx = p[0] + dx[i]
            ny = p[1] + dy[i]

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

    return d[gx][gy]


h, w = map(int, input().split())
maze = [list(input()) for i in range(h)]
sx, sy = 0, 0
gx, gy = h - 1, w - 1


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

res = bfs()
if 0 < res < float("inf"):
    
    
    print(white - res - 1)
else:
    print(-1)

Solution (Python):











import sys
sys.setrecursionlimit(10**6)
input=sys.stdin.readline
from math import floor,ceil,sqrt,factorial,hypot,log 
from heapq import heappop, heappush, heappushpop
from collections import Counter,defaultdict,deque
from itertools import accumulate,permutations,combinations,product,combinations_with_replacement
from bisect import bisect_left,bisect_right
from copy import deepcopy
inf=float('inf')
mod = 10**9+7
def pprint(*A): 
    for a in A:     print(*a,sep='\n')
def INT_(n): return int(n)-1
def MI(): return map(int,input().split())
def MF(): return map(float, input().split())
def MI_(): return map(INT_,input().split())
def LI(): return list(MI())
def LI_(): return [int(x) - 1 for x in input().split()]
def LF(): return list(MF())
def LIN(n:int): return [I() for _ in range(n)]
def LLIN(n: int): return [LI() for _ in range(n)]
def LLIN_(n: int): return [LI_() for _ in range(n)]
def LLI(): return [list(map(int, l.split() )) for l in input()]
def I(): return int(input())
def F(): return float(input())
def ST(): return input().replace('\n', '')
def main():
    H,W = MI()
    def is_inside(to):
        return 0<=to[0]<H and 0<=to[1]<W
    S=[ST() for _ in range(H)]
    queue = deque([(0,0)])
    visited = set()
    ans=0
    for s in S:
        ans += Counter(s)["."]
    for i in range(H*W+1):
        tmp = deque()
        while queue:
            fr = queue.popleft()
            if fr in visited:
                continue
            visited.add(fr)
            for dh,dw in [(-1,0),(0,-1),(1,0),(0,1)]:
                to = (fr[0]+dh,fr[1]+dw)
                if to not in visited and is_inside(to) and S[to[0]][to[1]]==".":
                    tmp.append(to)
        queue = tmp
        if (H-1,W-1) in tmp:
            print(ans-(i+2))
            return
    print(-1)
if __name__ == '__main__':
    main()

Solution (Python):
import sys
input = sys.stdin.readline
H,W = map(int,input().split())
meiro = []
for h in range(H):
    meiro.append(input())
from collections import deque
Q = deque([[0,0]])
ansmap = [[-1 for _ in range(W)] for __ in range(H)]
ansmap[0][0] = 0
step = 0
while Q:
    cue = Q.popleft()
    step = ansmap[cue[0]][cue[1]]
    for i in range(4):
        
        if cue[0]-1 >= 0:
            if meiro[cue[0]-1][cue[1]] == "." and (ansmap[cue[0]-1][cue[1]] > step+1 or ansmap[cue[0]-1][cue[1]] == -1):
                ansmap[cue[0]-1][cue[1]] = step+1
                Q.append([cue[0]-1,cue[1]])
        
        if cue[1]+1 < W:
            if meiro[cue[0]][cue[1]+1] == "." and (ansmap[cue[0]][cue[1]+1] > step+1 or ansmap[cue[0]][cue[1]+1] == -1):
                ansmap[cue[0]][cue[1]+1] = step+1
                Q.append([cue[0],cue[1]+1])
        
        if cue[0]+1 < H:
            if meiro[cue[0]+1][cue[1]] == "." and (ansmap[cue[0]+1][cue[1]] > step+1 or ansmap[cue[0]+1][cue[1]] == -1):
                ansmap[cue[0]+1][cue[1]] = step+1
                Q.append([cue[0]+1,cue[1]])
        
        if cue[1]-1 >= 0:
            if meiro[cue[0]][cue[1]-1] == "." and (ansmap[cue[0]][cue[1]-1] > step+1 or ansmap[cue[0]][cue[1]-1] == -1):
                ansmap[cue[0]][cue[1]-1] = step+1
                Q.append([cue[0],cue[1]-1])
cnt=0
for m in meiro:
    cnt += m.count('
if ansmap[H-1][W-1] == -1:
    print(-1)
else:
    print(H*W - ansmap[H-1][W-1]-1 - cnt)

Solution (Python):
import sys
input = sys.stdin.readline
H,W = map(int,input().split())
meiro = []
for h in range(H):
    meiro.append(input())
from collections import deque
Q = deque([[0,0]])
ansmap = [[-1 for _ in range(W)] for __ in range(H)]
ansmap[0][0] = 0
step = 0
while Q:
    cue = Q.popleft()
    step = ansmap[cue[0]][cue[1]]
    for i in range(4):
        
        if cue[0]-1 >= 0:
            if meiro[cue[0]-1][cue[1]] == "." and (ansmap[cue[0]-1][cue[1]] > step+1 or ansmap[cue[0]-1][cue[1]] == -1):
                ansmap[cue[0]-1][cue[1]] = step+1
                Q.append([cue[0]-1,cue[1]])
        
        if cue[1]+1 < W:
            if meiro[cue[0]][cue[1]+1] == "." and (ansmap[cue[0]][cue[1]+1] > step+1 or ansmap[cue[0]][cue[1]+1] == -1):
                ansmap[cue[0]][cue[1]+1] = step+1
                Q.append([cue[0],cue[1]+1])
        
        if cue[0]+1 < H:
            if meiro[cue[0]+1][cue[1]] == "." and (ansmap[cue[0]+1][cue[1]] > step+1 or ansmap[cue[0]+1][cue[1]] == -1):
                ansmap[cue[0]+1][cue[1]] = step+1
                Q.append([cue[0]+1,cue[1]])
        
        if cue[1]-1 >= 0:
            if meiro[cue[0]][cue[1]-1] == "." and (ansmap[cue[0]][cue[1]-1] > step+1 or ansmap[cue[0]][cue[1]-1] == -1):
                ansmap[cue[0]][cue[1]-1] = step+1
                Q.append([cue[0],cue[1]-1])
cnt=0
for m in meiro:
    cnt += m.count('
if ansmap[H-1][W-1] == -1:
    print(-1)
else:
    print(H*W - ansmap[H-1][W-1]-1 - cnt)

Solution (Python):
from collections import deque

def bfs():
    dx = [1, 0, -1, 0]
    dy = [0, 1, 0, -1]
    d = [[float("inf")] * w for _ in range(h)]
    que = deque([])
    que.append((0, 0))
    d[0][0] = 1
    
    while que:
        p = que.popleft()
        for i in range(4):
            nx = p[0] + dx[i]
            ny = p[1] + dy[i]
            
            if 0 <= nx < h and 0 <= ny < w:
                if F[nx][ny] != "
                    d[nx][ny] = d[p[0]][p[1]] + 1
                    que.append((nx, ny))
    return d[h-1][w-1]

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

if bfs() == float("inf"):
    print(-1)
    exit()
else:
    count = 0
    for i in range(h):
        for j in range(w):
          if F[i][j] == ".":
            count += 1
    ans = count - bfs()
    print(ans)

Solution (Python):
H, W = map(int, input().split(" "))
grid = list()
for _ in range(H):
    l = list()
    for c in input():
        if c == ".":
            l.append(True)
        else:
            l.append(None)
    grid.append(l)


def get_neighbors(x, y):
    neighbors = ((x-1, y), (x+1, y), (x, y-1), (x, y+1))
    result = list()
    for neighbor in neighbors:
        x, y = neighbor
        if 0 <= x <= W-1 and 0 <= y <= H-1:
            result.append((x, y))
    return result


current_x = 0
current_y = 0
distance = 0
queue = list()
grid[0][0] = 0
queue.append((current_x, current_y, distance+1))
while True:
    if not queue:
        break
    current_x, current_y, distance = queue.pop(0)
    if current_y == H - 1 and current_x == W - 1:
        break
    for neighbor in get_neighbors(current_x, current_y):
        x, y = neighbor
        if grid[y][x] is not None:
            if grid[y][x] is True:
                grid[y][x] = distance
                queue.append((x, y, distance+1))


if grid[H-1][W-1] is None or grid[H-1][W-1] is True:
    print(-1)
else:
    test = [l.count(None) for l in grid]
    num_black = sum(l.count(None) for l in grid)
    print(H*W - num_black - grid[H-1][W-1] - 1)

Solution (Python):
import queue

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

def bfs():
    x = 0
    y = 0
    cnt = 0
    Q = queue.Queue()
    check = [[True for i in range(W)] for j in range(H)]
    
    Q.put((x, y, cnt))
    while Q.qsize() > 0:
        x, y , cnt = Q.get()
        for i in range(4):
            if 0 <= x + dx[i] < H and 0 <= y + dy[i] < W and check[x + dx[i]][y + dy[i]]:
                check[x + dx[i]][y + dy[i]] = False
                if field[x + dx[i]][y + dy[i]] == "
                    pass
                elif x + dx[i] == H - 1 and y + dy[i] == W - 1:
                    return cnt + 1
             
                else:
                    Q.put((x + dx[i], y + dy[i], cnt + 1))
                    
    return -1

nums=list(map(int,input().split()))
H = nums[0]
W = nums[1]


field = [[None for i in range(W)] for j in range(H)]

black = 0
for i in range(H):
    str1 = input()
    for j in range(W):
        field[i][j] = str1[j]
        if str1[j] == "
            black += 1
            
Q = queue.Queue()
res = bfs()
if res >= 0:
    result = H * W - black -(res + 1)
    print(result)
else:
    print(res)

Solution (Python):
import sys
from heapq import heappop, heappush

H, W = map(int, sys.stdin.readline().split())
grid = ['
grid += ['
grid += ['

def heuristic_cost(y, x):
    return abs(H - y) + abs(W - x)

def main():
    h = heuristic_cost(1, 1)
    c = 0
    s = h + c
    hq = [(s, c, 1, 1)]
    nex = [(1, 0), (0, 1), (-1, 0), (0, -1)]
    cost = [[None] * (W+1) for _ in range(H+1)]
    while hq:
        s, c, y, x = heappop(hq)
        if not cost[y][x] is None:
            continue
        cost[y][x] = c
        for dy, dx in nex:
            i = y + dy
            j = x + dx
            if grid[i][j] == '.' and cost[i][j] is None:
                h = heuristic_cost(i, j)
                s = h + (c + 1)
                heappush(hq, (s, c+1, i, j))

    white_cnt = 0
    for i in range(1, H+1):
        for j in range(1, W+1):
            white_cnt += (grid[i][j] == '.') & 1
    
    ans = white_cnt - (cost[H][W] + 1) if not cost[H][W] is None else -1
    return ans 

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

Solution (Python):
from queue import Queue
H,W=map(int,input().split())
s=[list(input()) for _ in range(H)]

white=sum([1 if s[y][x]=='.' else 0 for x in range(W) for y in range(H)])
used=[[False for x in range(W)] for y in range(H)]
q=Queue()
q.put((0,0,1))
while True:
    if q.empty():
        print(-1)
        break
    x,y,l=q.get()
    if used[y][x]:
        continue
    if x==W-1 and y==H-1:
        print(white-l)
        break
    used[y][x]=True
    for d in [(1,0),(0,1),(-1,0),(0,-1)]:
        nx=x+d[0]
        ny=y+d[1]
        if ny>=0 and ny<H and nx>=0 and nx<W:
            if s[ny][nx]=='.':
                q.put((nx,ny,l+1))

Solution (Python):
from collections import deque
H,W=map(int,input().split())
white=0
s=[]
for y in range(H):
    line=input()
    white+=line.count('.')
    s.append(list(line))

q = deque([(0,0,1)])
q_append=q.append
q_popleft=q.popleft
while q:
    x,y,l=q_popleft()
    if s[y][x]!='.':
        continue
    if x==W-1 and y==H-1:
        print(white-l)
        break
    s[y][x]='*'
    for d in [(1,0),(0,1),(-1,0),(0,-1)]:
        nx, ny=(x+d[0],y+d[1])
        if 0<=nx<W and 0<=ny<H:
            q_append((nx,ny,l+1))
else:
    print(-1)

Solution (Python):
from collections import deque


def solve():
    H, W = map(int, input().split())
    p_black = 0
    maze = [[3000 for _ in range(W)] for _ in range(H)]
    for i in range(H):
        line = input()
        for j in range(W):
            if line[j] == '
                maze[i][j] = -1
                p_black += 1
    maze[0][0] = 0
    
    move = [[-1, 0], [0, 1], [1, 0], [0, -1]]
    que = deque([[0, 0]])
    white = 1
    while que:
        cy, cx = que.popleft()
        if cy == H - 1 and cx == W - 1:
            white += maze[H - 1][W - 1]
            break
        
        for i in range(4):
            ny = cy + move[i][0]
            nx = cx + move[i][1]
            if 0 <= ny <= H - 1 and 0 <= nx <= W - 1:
                if maze[ny][nx] == 3000:
                    maze[ny][nx] = maze[cy][cx] + 1
                    que.append([ny, nx])
    
    if white == 1:
        print(-1)
    else:
        ans = H * W - p_black - white
        print(ans)


if __name__ == '__main__':
    solve()

Solution (Python):


import copy
import sys
from collections import deque

H,W = (int(i) for i in input().split())
s_tmp = []
for _ in range(H):
    s_tmp.append(list(input()))
d = [[1, 0], [-1, 0], [0, 1], [0, -1]]
q = deque()
s = copy.deepcopy(s_tmp)
q.append([0,0,0])
s[H-1][W-1] = 'g'
s[0][0] = 's'
flg = False

def result():
    cnt = 0
    for j in range(W):
        for i in range(H):
            if s_tmp[i][j] =='.':
                cnt += 1
    if flg == False:
        print(-1)
    else :
        print(cnt-z-2)
        
while len(q) > 0:
    
    node = q.popleft()
    if node is not None:
        y = node[0]
        x = node[1]
        z = node[2]
        s[y][x] = '
        
        for dx, dy in d:
            nx, ny = x + dx, y + dy
            if not (0 <= nx < W and 0 <= ny < H) or s[ny][nx] == '
                continue
            else:
                tmp = [ny,nx,z+1]
                if s[ny][nx] != 'y':
                    q.append(tmp)
                if s[ny][nx] == 'g' and flg == False:
                    
                    flg = True
                    result()
                    sys.exit()
                s[ny][nx] = 'y'
if flg == False:
        print(-1)

Solution (Python):
import sys
from collections import deque
sys.setrecursionlimit(10**9)
INF=10**18
def input():
    return sys.stdin.readline().rstrip()

def main():
    H,W=map(int,input().split())
    s=[[] for _ in range(H+2)]
    s[0]=s[H+1]=['
    white=-1
    for i in range(1,H+1):
        row=['
        s[i]=row
        for cell in row:
            if cell=='.':
                white+=1
    queue=deque()
    queue.append([1,1])
    d=[[INF]*(W+2) for _ in range(H+2)]
    d[1][1]=0
    dx=[1,0,-1,0]
    dy=[0,1,0,-1]
    while queue:
        cell=queue.popleft()
        for k in range(4):
            if s[cell[0]+dx[k]][cell[1]+dy[k]]=='.' and d[cell[0]+dx[k]][cell[1]+dy[k]]==INF:
                queue.append([cell[0]+dx[k],cell[1]+dy[k]])
                d[cell[0]+dx[k]][cell[1]+dy[k]]=min(d[cell[0]+dx[k]][cell[1]+dy[k]],d[cell[0]][cell[1]]+1)
    if d[H][W]==INF:
        print(-1)
    else:
        print(white-d[H][W])

if __name__ == '__main__':
    main()

Solution (Python):
from sys import stdin


def fetch_one_line():
    return stdin.readline().rstrip()


def fetch_int_input():
    return [int(s) for s in fetch_one_line().split()]


def fetch_inputs(times):
    return [fetch_one_line() for _ in range(times)]


def fetch_int_inputs(times):
    return [[int(s) for s in fetch_one_line()] for _ in range(times)]

import sys
from collections import deque

moves = ((1, 0), (0, 1), (-1, 0), (0, -1))
H, W = fetch_int_input()
maze = [list(fetch_one_line()) for _ in range(H)]
X, Y = 0, 1
STARTS = (0, 0)
GOALS = (H - 1, W - 1)


def count_wall(maze, wall="
    wall_num = 0
    for one_line in maze:
        wall_num += "".join(one_line).count(wall)
    return wall_num

def bfs():
    que = deque()
    d = [[sys.maxsize for _ in range(W)] for _ in range(H)]
    que.append(STARTS)
    d[STARTS[X]][STARTS[Y]] = 0

    while que:
        now_pos = que.popleft()
        if now_pos == GOALS:
            break
        for move in moves:
            np = (now_pos[X] + move[X], now_pos[Y] + move[Y])
            if np[X] >= 0 and np[Y] >= 0 and np[X] < H and np[Y] < W and maze[np[X]][np[Y]] == '.' and d[np[X]][np[Y]] == sys.maxsize:
                que.append(np)
                d[np[X]][np[Y]] = d[now_pos[X]][now_pos[Y]] + 1

    return d[GOALS[X]][GOALS[Y]]

min_distance = bfs()
if min_distance == sys.maxsize:
    changable_num = -1
else:
    wall_num = count_wall(maze, "
    changable_num = H * W - 2 - (min_distance - 1) - wall_num
print(changable_num)

Solution (Python):


import sys
from collections import deque

def input(): return sys.stdin.readline().strip()
def list2d(a, b, c): return [[c] * b for i in range(a)]
def list3d(a, b, c, d): return [[[d] * c for j in range(b)] for i in range(a)]
def list4d(a, b, c, d, e): return [[[[e] * d for j in range(c)] for j in range(b)] for i in range(a)]
def ceil(x, y=1): return int(-(-x // y))
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(N=None): return list(MAP()) if N is None else [INT() for i in range(N)]
def Yes(): print('Yes')
def No(): print('No')
def YES(): print('YES')
def NO(): print('NO')
sys.setrecursionlimit(10 ** 9)
INF = 10 ** 18
MOD = 10 ** 9 + 7

def build_grid(H, W, intv, _type, space=True, padding=False):
    
    if space:
        _input = lambda: input().split()
    else:
        _input = lambda: input()
    _list = lambda: list(map(_type, _input()))
    
    if padding:
        offset = 1
    else:
        offset = 0
    grid = list2d(H+offset*2, W+offset*2, intv)
    for i in range(offset, H+offset):
        row = _list()
        for j in range(offset, W+offset):
            grid[i][j] = row[j-offset]
    return grid

H, W = MAP()
grid = build_grid(H, W, '


directions = ((1,0),(-1,0),(0,1),(0,-1))
que = deque([(1, 1, 0)])
dist = list2d(H+2, W+2, INF)
while que:
    h, w, c = que.popleft()
    if dist[h][w] != INF:
        continue
    dist[h][w] = c
    for dh, dw in directions:
        h2 = h + dh
        w2 = w + dw
        if grid[h2][w2] == '
            continue
        que.append((h2, w2, c+1))


if dist[H][W] == INF:
    print(-1)
    exit()


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

ans = cnt - (dist[H][W] + 1)
print(ans)

Solution (Python):


import sys
from collections import deque

def input(): return sys.stdin.readline().strip()
def list2d(a, b, c): return [[c] * b for i in range(a)]
def list3d(a, b, c, d): return [[[d] * c for j in range(b)] for i in range(a)]
def list4d(a, b, c, d, e): return [[[[e] * d for j in range(c)] for j in range(b)] for i in range(a)]
def ceil(x, y=1): return int(-(-x // y))
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(N=None): return list(MAP()) if N is None else [INT() for i in range(N)]
def Yes(): print('Yes')
def No(): print('No')
def YES(): print('YES')
def NO(): print('NO')
sys.setrecursionlimit(10 ** 9)
INF = 10 ** 18
MOD = 10 ** 9 + 7

def build_grid(H, W, intv, _type, space=True, padding=False):
    
    if space:
        _input = lambda: input().split()
    else:
        _input = lambda: input()
    _list = lambda: list(map(_type, _input()))
    
    if padding:
        offset = 1
    else:
        offset = 0
    grid = list2d(H+offset*2, W+offset*2, intv)
    for i in range(offset, H+offset):
        row = _list()
        for j in range(offset, W+offset):
            grid[i][j] = row[j-offset]
    return grid

H, W = MAP()
grid = build_grid(H, W, '


directions = ((1,0),(-1,0),(0,1),(0,-1))
que = deque([(1, 1, 0)])
dist = list2d(H+2, W+2, INF)
while que:
    h, w, c = que.popleft()
    if dist[h][w] != INF:
        continue
    dist[h][w] = c
    for dh, dw in directions:
        h2 = h + dh
        w2 = w + dw
        if grid[h2][w2] == '
            continue
        que.append((h2, w2, c+1))


if dist[H][W] == INF:
    print(-1)
    exit()


que = deque([(H, W)])
while que:
    h, w = que.popleft()
    grid[h][w] = '@'
    for dh, dw in directions:
        h2 = h + dh
        w2 = w + dw
        if dist[h2][w2] == dist[h][w] - 1:
            que.append((h2, w2))
            break


ans = 0
for i in range(1, H+1):
    for j in range(1, W+1):
        if grid[i][j] == '.':
            ans += 1
print(ans)

Solution (Python):
import sys
from collections import deque

H, W = map(int, input().split())
s_y, s_x = (0, 0)
g_y, g_x = (H-1, W-1)

c = [input() for a in range(H)]

d = [[ sys.maxsize for b in range(W)] for a in range(H)]

blackcount = 0
for y in range(H):
  blackcount += c[y].count('

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

q = deque([[s_y, s_x]])

d[s_y][s_x] = 0

while len(q) > 0:
  y, x = q.popleft()
  if y==g_y and x==g_x:
    print(H * W - blackcount - 1 - d[y][x])
    exit()
  for i in range(4):
    ny = y + dy[i]
    nx = x + dx[i]
    if 0 <= nx and nx <= W-1 and 0 <= ny and ny <= H-1 and c[ny][nx] == '.' and d[ny][nx] == sys.maxsize:
      q.append([ny, nx])
      d[ny][nx] = d[y][x]+1
      
print(-1)

Solution (Python):
from collections import deque
H,W = map(int,input().split())
mat = []
wsum = 0
for i in range(H):
    mat.append(list(input()))
    wsum += mat[i].count('.')
start = [0,0]
x1 = [0,0,1,-1]
y1 = [1,-1,0,0]
alr = [[-1 for i in range(W)] for j in range(H)]
alr[0][0] = 0
que = deque()
count = 0
que.append([0,0])
flag = False
while que:
    q = que.popleft()
    for i in range(4):
        if (0 <= q[0]+x1[i] <= H-1) and (0 <= q[1]+y1[i] <= W-1):
            if q[0]+x1[i] == H-1 and q[1]+y1[i] == W-1:
                count = alr[q[0]][q[1]] + 1
                flag = True
                que.clear()
            elif mat[q[0]+x1[i]][q[1]+y1[i]] == '.' and alr[q[0]+x1[i]][q[1]+y1[i]] == -1:
                alr[q[0]+x1[i]][q[1]+y1[i]] = alr[q[0]][q[1]] + 1
                que.append([q[0]+x1[i],q[1]+y1[i]])
if flag:
    print(wsum - (count+1))
else:
    print(-1)

Solution (Python):
import sys
from collections import deque
 
 
def bfs(H, W, maze, visited, sharp):
    queue = deque([[0, 0]])
    visited[0][0] = 0
    while queue:
        y, x = queue.popleft()
        if[y, x] == [H-1, W-1]:
            return ((H*W-sharp)-(visited[y][x]+1))
        for j, k in ([1, 0], [-1, 0], [0, 1], [0, -1]):
            new_y, new_x = y+j, x+k
            if  new_y != -1 and new_y != H and  \
                new_x != -1 and new_x != W and  \
                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 -1
 

def main():
    sharp = 0
 
    H, W = map(int,input().split())
    maze = [input() for i in range(H)]
    visited = [[-1]*W for j in range(H)]
 
    for k in range(H):
        sharp += maze[k].count('
 
    print(bfs(H, W, maze, visited, sharp))
 
main()

Solution (Python):
import sys
from collections import deque


def bfs(H, W, maze, visited, sharp):
    queue = deque([[0, 0]])
    visited[0][0] = 0
    while queue:
        y, x = queue.popleft()
        if[y, x] == [H-1, W-1]:
            return ((H*W-sharp)-(visited[y][x]+1))
        for j, k in ([1, 0], [-1, 0], [0, 1], [0, -1]):
            new_y, new_x = y+j, x+k
            if  new_y != -1 and new_y != H and  \
                new_x != -1 and new_x != W and  \
                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 -1












def main():
    sharp = 0

    H, W = map(int,input().split())
    maze = [input() for i in range(H)]
    visited = [[-1]*W for j in range(H)]

    for k in range(H):
        sharp += maze[k].count('

    print(bfs(H, W, maze, visited, sharp))

main()

Solution (Python):
import copy
from collections import deque

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

    walled_maze = copy.copy(maze)
    walled_maze[H:H] = [''.join(['
    walled_maze[0:0] = [''.join(['
    for row_num in range(1, H+1):
        walled_maze[row_num] = '
    
    

    stack = deque()
    sx, sy = 1, 1
    gx, gy = H, W
    distances = [[-1]*(W+2) for _ in range(H+2)]
    vectors = ((1, 0), (-1, 0), (0, 1), (0, -1))

    distances[sx][sy] = 0
    for vec_x, vec_y in vectors:
        x = sx + vec_x
        y = sy + vec_y
        stack.append((x, y))
        distances[x][y] = float('inf')

    min_path_dist = -1
    while len(stack):
        x, y = stack.popleft()
        if x < 0 or x >= H+1 or y < 0 or y >= W+1 or walled_maze[x][y] == '
            continue
        for vec_x, vec_y in vectors:
            try:
                next_x = x + vec_x
                next_y = y + vec_y
                if distances[next_x][next_y] < 0:
                    stack.append((next_x, next_y))
                    distances[next_x][next_y] = float('inf')
                else:
                    if distances[x][y] > distances[next_x][next_y] + 1:
                        distances[x][y] = distances[next_x][next_y] + 1
            except IndexError:
                pass

        
        
        
        

        if x == gx and y == gy:
            min_path_dist = distances[x][y]
            break

    if min_path_dist < 0:
        print('-1')
    else:
        black_square_num = sum([row.count('
        print(H*W-(min_path_dist+1)-black_square_num)

if __name__ == '__main__':
    main()

Solution (Python):
Y,X=map(int,input().split())
info=[]
come=[[0]*X for i in range(Y)]
num=[[0]*X for i in range(Y)]
bl=0 
come[0][0]=1
for i in range(Y):
    a=list(input())
    info.append(a)
    for j in range(X):
        if a[j]=="
            bl+=1
def bfs(y,x,nanpo):
    if not(0<=y<=(Y-1) and 0<=x<=(X-1)):
        return
    if info[y][x]=="
        return
    if come[y][x]==1:
        return
    come[y][x]=1
    num[y][x]=nanpo
    next_.append([y,x])
    
next_=[[0,0]]
l=1
nanpo=1
while l>0:
    for i in range(l):
        
        
        bfs(next_[0][0]+1,next_[0][1],nanpo)
        bfs(next_[0][0]-1,next_[0][1],nanpo)
        bfs(next_[0][0],next_[0][1]+1,nanpo)
        bfs(next_[0][0],next_[0][1]-1,nanpo)
        del next_[0]
    nanpo+=1
    l=len(next_)

if come[Y-1][X-1]==0:
    print(-1)
else:
    print(X*Y-bl-(num[Y-1][X-1]+1))

Solution (Python):
import heapq
import sys

sys.setrecursionlimit(1000)

BLACK = '
WHITE = '.'


def m():
    H, W = [int(x) for x in input().split(' ')]
    board = [[c for c in list(input())] for _ in range(H)]

    
    q = [(0, 0, 0)]
    is_reachable = False
    while len(q) > 0:
        p, x, y = heapq.heappop(q)
        if x == H - 1 and y == W - 1:
            is_reachable = True

        nexts = [(x+1, y), (x, y+1), (x-1, y), (x, y-1)]
        for i, j in nexts:
            if 0 <= i and i < H and 0 <= j and j < W:
                if board[i][j] == BLACK:
                    continue

                if board[i][j] == WHITE:
                    board[i][j] = p+1
                    heapq.heappush(q, (p+1, i, j))
                    continue

                if board[i][j] > p+1:
                    board[i][j] = p+1
                    heapq.heappush(q, (p+1, i, j))
                    continue

    if is_reachable:
        blacks = 0
        for i in range(H):
            for j in range(W):
                if board[i][j] == BLACK:
                    blacks += 1
        ans = H*W - blacks - board[H-1][W-1] - 1
        print(ans)
    else:
        print(-1)


m()

Solution (Python):
from collections import deque
def bfs(field,visited,sy,sx,gy,gx):
    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 new_y < 0 or new_y > gy or new_x < 0 or new_x > gx:
              continue
            if field[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])
                
if __name__ == "__main__":
 
    h,w=map(int,input().split())
    sy=1
    sx=1
    field=[list(input()) for i in range(h)]
    visited = [[-1]*w for i in range(h)]
    sy, sx, gy, gx = sy-1, sx-1, h-1, w-1
    ans=bfs(field,visited,sy,sx,gy,gx)
    
    cnt=0
    for i in range(h):
      for j in range(w):
        if field[i][j]==".":
          cnt+=1
    if ans == None:
      print(-1)
    else:
      print(cnt - ans -1)