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
import sys

def bfs(maze, sy, sx):
    h = len(maze)
    w = len(maze[0])
    visited = [[-1 for _ in range(w)] for _ in range(h)]
    d = deque([[sy, sx]])
    visited[sy][sx] = 0
    while d:
        y, x = d.popleft()
        
        for k, l in ([1, 0], [0, 1], [-1, 0], [0, -1]):
            new_y, new_x = y + k, x + l
            if new_y < 0 or h <= new_y or new_x < 0 or w <= new_x:
                continue
            elif visited[new_y][new_x] != -1:
                continue
            elif maze[new_y][new_x] == '
                continue
            
            d.append([new_y, new_x])
            visited[new_y][new_x] = visited[y][x] + 1
    
    return visited

if __name__ == "__main__":
    h, w = map(int, input().split())
    
    maze = []
    cnt = 0
    for i in range(h):
        maze.append(input())
        cnt += maze[i].count('.')
        
    visited = bfs(maze, 0, 0)
    goal = visited[h - 1][w - 1]
    
    if goal == -1:
        print(-1)
    else:
        print(cnt - goal - 1)

Solution (Python):
from collections import deque
 
h , w = map(int,input().split())
cou = 0
ma = []
for i in range(h):
    kar = list(input())
    cou += kar.count("
    ma.append(kar)
 
 
ans = [[-1 for i in range(w)] for j in range(h)]
ans[0][0] = 1
q = deque([(0,0)])
xy = [(1,0),(-1,0),(0,1),(0,-1)]
 
while q:
    x , y = q.popleft()
    for i in range(4):
        nx = x + xy[i][0]
        ny = y + xy[i][1]
        if 0 <= nx <= h-1 and 0 <= ny <= w-1 and ans[nx][ny] == -1:
            if ma[nx][ny] == ".":
                q.append((nx,ny))
                ans[nx][ny] = ans[x][y] + 1
        if nx == h-1 and ny == w-1:
            break
 
if ans[h-1][w-1] == -1:
    print(-1)
else:
    print(h*w - cou - ans[h-1][w-1])

Solution (Python):
from collections import deque
inf=10**3


def BFS():
    color=[["white" for _ in range(w)] for _ in range(h)]
    D=[[inf for _ in range(w)] for _ in range(h)]

    D[0][0]=1
    color[0][0]="gray"
    queue=deque([[0,0]])
    while len(queue)>0:
        a,b=queue.popleft()
        for c,d in [[1,0],[-1,0],[0,1],[0,-1]]:
            X,Y=a+c,b+d
            if 0<=X<h and 0<=Y<w:
                if S[X][Y]=="." and color[X][Y]=="white":
                    D[X][Y]=min(D[X][Y],D[a][b]+1)
                    color[X][Y]="gray"
                    queue.append([X,Y])
        color[a][b]="black"

    return D[-1][-1]


h,w=map(int,input().split())
S=[list(input()) for _ in range(h)]
D=BFS()
black=sum([S[i].count("
print(h*w-D-black if D!=inf else -1)

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

M = [[-1] * W for _ in range(H)]


q = deque()
q.append((0, 0))
M[0][0] = 1

while q:
    p = q.popleft()

    directions = ((1, 0), (-1, 0), (0, 1), (0, -1))
    for d in directions:
        x = p[0] + d[0]
        y = p[1] + d[1]

        if 0 <= x and x < W and 0 <= y and y < H:
            if M[y][x] == -1 and S[y][x] == ".":
                M[y][x] = M[p[1]][p[0]] + 1
                q.append((x, y))

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

if minD == -1:
    print(-1)
else:
    print(count-minD)

Solution (Python):




import sys
from collections import deque
inf = 10**15
mod = 10**9+7
R, C = map(int, input().split())
maps = [input() for i in range(R)]
whole = R*C
defoB = 0
for s in maps:
    for c in s:
        if c == '
            defoB+=1
dis = [[-1 for j in range(C)] for i in range(R)]

def bfsC(init_y, init_x, goal_y, goal_x):
    q = deque([[init_y, init_x]])
    dis[init_y][init_x] = 0
    while q:
        y, x = q.popleft()
        if y == goal_y and x == goal_x:
            return dis[y][x]
        distance = dis[y][x]+1
        for dy, dx in [[1,0],[-1,0],[0,1],[0,-1]]:
            if 0 <= y+dy < R and 0 <= x+dx < C and maps[y+dy][x+dx] != '
                q.append([y+dy, x+dx])
                dis[y+dy][x+dx] = distance
    return -1 

result = bfsC(0, 0, R-1, C-1) + 1
if result != 0:
    print(whole - result - defoB)
else:
    print(-1)

Solution (Python):

import io
from queue import Queue

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

white=sum([1 if s[y][x]=='.' else 0 for x in range(mike) for y in range(nim)])
used=[[False for x in range(mike)] for y in range(nim)]
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==mike-1 and y==nim-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<nim and nx>=0 and nx<mike:
            if s[ny][nx]=='.':
                q.put((nx,ny,l+1))

Solution (Python):
import sys 
from collections import deque

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

p = [str(input()) for _ in range(H)]

reached = [[float("inf")]*W for _ in range(H)]
dxdy = [(1,0),(-1,0),(0,1),(0,-1)]
reached[0][0] = 1
queue = deque([[0,0]])

while queue:
  x,y = queue.popleft()
  for i in range(4):
    nx = x + dxdy[i][0]
    ny = y + dxdy[i][1]
    if 0<=nx<H and 0<=ny<W and p[nx][ny] != "
      queue.append([nx,ny])
      reached[nx][ny] = reached[x][y] + 1
    if nx == H-1 and ny == W-1:
      break

shiro = 0
for i in range(H):
  for j in range(W):
    if p[i][j] == ".":
      shiro += 1

ans = shiro - reached[H-1][W-1]
if ans >= 0:
  print(ans)
else:
  print("-1")

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

whitesum=0
for each in cmap:
    whitesum += each.count(".")

def nextpoint(y,x):
    global cmap
    tmp=[]
    returnlist=[]
    cmap[y]=cmap[y][:x] + "

    if y == 0:
        tmp.append([y+1,x])
    elif y == h-1:
        tmp.append([y-1,x])
    else:
        tmp.extend([[y-1,x],[y+1,x]])

    if x == 0:
        tmp.append([y,x+1])
    elif x == w-1:
        tmp.append([y,x-1])
    else:
        tmp.extend([[y,x+1],[y,x-1]])

    for l in tmp:
        if cmap[l[0]][l[1]] == ".":
            cmap[l[0]]=cmap[l[0]][:l[1]] + "
            returnlist.append(l)

    return returnlist

start=[0,0]
seen=[start]
todo=[]
todo.extend(nextpoint(start[0],start[1]))

i=2
finishflag=True

while finishflag:
    nextlist=[]

    for nep in todo:
        if nep == [h-1,w-1]:
            print(whitesum-i)
            sys.exit()
        else:
            nextlist.extend(nextpoint(nep[0],nep[1]))
    todo=[]
    todo.extend(nextlist)

    if todo == []:
        finishflag = False

    i += 1

print("-1")

Solution (Python):
from collections import deque

def bfs(sx, sy):
    queue = deque([[sx, sy]])
    visit[sx][sy] = 0
    while queue:
        x, y = queue.popleft()
        if [x, y] == [gx, gy]:
            return visit[x][y]
        for k in range(4):
            nx, ny = x + dx[k], y + dy[k]
            if nx < 0 or h <= nx or ny < 0 or w <= ny or graph[nx][ny] == "
                continue
            elif graph[nx][ny] == "." and visit[nx][ny] == -1:
                visit[nx][ny] = visit[x][y] + 1
                queue.append([nx, ny])

h, w = map(int, input().split())
graph = [list(input()) for _ in range(h)]
visit = [[-1 for _ in range(w)] for _ in range(h)]
dx = [0, 1, 0, -1]
dy = [1, 0, -1, 0]

sx, sy = 0, 0
gx, gy = h-1, w-1

cnt = 0
for i in range(h):
    for j in range(w):
        if graph[i][j] == "
            cnt += 1

bfs(sx, sy)
path = visit[gx][gy] + 1
if visit[gx][gy] == -1:
    print(-1)
else:
    print(h * w - path - cnt)

Solution (Python):

from collections import deque

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

root_num = 0
block_num = 0
for i in range(H):
    for j in range(W):
        if s[i][j] == ".":
            root_num+=1
        else:
            block_num+=1

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

seen = [[False for _ in range(W)] for _ in range(H)]
answer = [[-10000 for _ in range(W)] for _ in range(H)]
answer[0][0] = 0

todo = deque([[0,0]])
seen[0][0] = True
while len(todo) > 0:
    checking = todo.popleft()
    for direction in directions:
        moved = [checking[0] + direction[0], checking[1] + direction[1]]
        if moved[0] < 0 or moved[0] >= H or moved[1] < 0 or moved[1] >= W:
            continue
        if seen[moved[0]][moved[1]] == False and s[moved[0]][moved[1]] ==".":
            seen[moved[0]][moved[1]] = True
            answer[moved[0]][moved[1]] = answer[checking[0]][checking[1]] + 1
            todo.append([moved[0], moved[1]])

if answer[-1][-1] == -10000:
    print("-1")
else:
    print(root_num - (answer[-1][-1] + 1))

Solution (Python):
import sys
from collections import deque

input = sys.stdin.readline


def bfs(H, W, maze, dist, sh, sw):
    queue = deque([[sh, sw]])
    dist[sh][sw] = 0
    while queue:
        h, w = queue.popleft()
        for i, j in [(1, 0), (-1, 0), (0, -1), (0, 1)]:
            next_h, next_w = h + i, w + j
            if not ((0 <= next_h <= H - 1) and (0 <= next_w <= W - 1)):
                continue
            if (maze[next_h][next_w] == ".") and (dist[next_h][next_w] == -1):
                dist[next_h][next_w] = dist[h][w] + 1
                queue.append([next_h, next_w])
    return dist

def main():
    H, W = map(int, input().split())
    s = [""] * H
    for i in range(H):
        s[i] = input().rstrip()

    dist = [[-1] * W for _ in range(H)]
    bfs(H, W, s, dist, 0, 0)
    min_n_white_of_path = dist[H-1][W-1] + 1
    if min_n_white_of_path == 0:
        print(-1)
    else:
        n_white = 0
        for i in range(H):
            n_white += s[i].count(".")
        ans = n_white - min_n_white_of_path
        print(ans)


if __name__ == "__main__":
    main()

Solution (Python):
from collections import deque

H, W = map(int, input().split())
black = 0
s = ["
for _ in range(H):
    row = input()
    black += row.count("
    s.append("
s.append("

def bfs(x, y):
    if s[x][y] == "
        return 0
    queue = deque([(x, y)])
    dist = [[-1]*(W+2) for _ in range(H+2)]
    dist[x][y] = 0
    while queue:
        r, c = queue.popleft()
        d = dist[r][c]
        for i in [r-1, r+1]:
            if i >= 0 and i <= H:
                if s[i][c] == "." and dist[i][c] == -1:
                    dist[i][c] = d+1
                    queue.append((i, c))
        for j in [c-1, c+1]:
            if j >= 0 and j <= W:
                if s[r][j] == "." and dist[r][j] == -1:
                    dist[r][j] = d+1
                    queue.append((r, j))
    return dist
ans = bfs(1,1)[-2][-2]
if ans != -1:
    print(H*W-bfs(1,1)[-2][-2]-1-black)
else:
    print(-1)

Solution (Python):
import sys, math
from itertools import permutations, combinations
from collections import defaultdict, Counter, deque
from math import factorial
from bisect import bisect_left 
sys.setrecursionlimit(10**7)
enu = enumerate
MOD = 10**9+7
def input(): return sys.stdin.readline()[:-1]
def pri(x): print('\n'.join(map(str, x)))

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

cnt = 0
for row in c:
    for chara in row:
        if chara == '
            cnt += 1
res = H*W - cnt

def check(ny, nx):
    if 0<=ny<=H-1 and 0<=nx<=W-1 and c[ny][nx]=='.':
        return True
    else:
        return False

deq = deque()
deq.append([(0, 0)]) 
ddy = [-1, 0, 1, 0]
ddx = [0, -1, 0, 1]
step = 0
found = False
while deq[0]:
    nqueue = []
    cqueue = deq.popleft()
    for val in cqueue:
        y, x = val
        if val==(H-1, W-1):
            found = True
            break
        for dy, dx in zip(ddy, ddx):
            ny, nx = y+dy, x+dx
            if check(ny, nx):
                c[ny][nx] = '
                nqueue.append((ny, nx))
    if found: break
    deq.append(nqueue)
    step += 1

if not(found):
    print(-1)
    exit()
res -= (step+1)
print(res)

Solution (Python):
from collections import deque

H,W = map(int,input().split())
field = ["
field += ["
field += ["
d = [[-1]*(W+2) for _ in range(H+2)]
q = deque()
q.append([1,1])
d[1][1] = 1
dmov = [(-1,0),(1,0),(0,-1),(0,1)]
cnt = 0
for i in range(W+2):
  for j in range(H+2):
    if field[j][i] == ".":
      cnt += 1

while len(q) > 0:
  node = q.popleft()
  x = node[0]
  y = node[1]
  c = d[y][x]
  for i,j in dmov:
    xx = x+i
    yy = y+j
    if d[yy][xx] == -1 and field[yy][xx] == ".":
      d[yy][xx] = c+1
      q.append([xx,yy])
      
if d[H][W] == -1:
  print(-1)
else:
  print(cnt-d[H][W])

Solution (Python):
import collections

H, W = map(int, input().split((" ")))
mp = []
for _ in range(H):
    mp.append(input())

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

que = collections.deque()
dist = [[-1 for _ in range(W)] for _ in range(H)]
dist[0][0] = 1
que.append((0, 0))

while que:
    h, w = que.popleft()
    for dh, dw in ((0, 1), (0, -1), (1, 0), (-1, 0)):
        if h + dh < 0 or w + dw < 0 or h + dh >= H or w + dw >= W:
            continue
        elif mp[h + dh][w + dw] == '
            continue
        dist[h + dh][w + dw] = dist[h][w] + 1
        que.append((h + dh, w + dw))

if dist[H - 1][W - 1] == -1:
    print(-1)
else:
    print(max(white - (dist[H - 1][W - 1]), 0))

Solution (Python):
from collections import deque

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

w_cnt = 0
for i in range(h):
    w_cnt += s[i].count('.')

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((0, 0))
    d[0][0] = 0

    while que:
        p = que.popleft()
        if p[0] == h-1 and p[1] == w-1:
            break
        for i in range(4):
            n_row = p[0] + dx[i]
            n_col = p[1] + dy[i]

            if 0 <= n_row < h and 0 <= n_col < w and s[n_row][n_col] != "
                que.append((n_row, n_col))
                d[n_row][n_col] = d[p[0]][p[1]] + 1

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

if bfs() == float("inf"):
    print(-1)
else:
    print(w_cnt-bfs()-1)

Solution (Python):
import sys
from collections import deque
def input():return sys.stdin.readline().strip()

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

    move = [-1, 1, -(W+2), W+2]
    cost = [0] * (H+2) * (W+2)

    def bfs(s):
        q = deque()
        enqueue = q.append
        dequeue = q.popleft
        cost[s] = 1
        enqueue(s)

        while q:
            now = dequeue()
            for dx in move:
                nv = now + dx
                if field[nv] != "
                    cost[nv] = cost[now] + 1
                    enqueue(nv)
        
    start = (W+2) + 1
    goal = H*(W+2) + W

    bfs(start)
    white = field.count(".")
    if cost[goal]:
        print(white - cost[goal])
    else:
        print(-1)
    
if __name__ == "__main__":
    main()

Solution (Python):
from collections import deque

H,W=map(int,input().split())
S=[input() for i in range(H)]
black=0
for i in range(H):
    black+=S[i].count("

C=[[0 for _ in range(W)] for j in range(H)]
F=[[False for _ in range(W)] for j in range(H)]

def bfs():
    q=deque([[0,0]])
    F[0][0]=True
    d=[[0,1],[1,0],[-1,0],[0,-1]]
    while q:
        y,x=q.popleft()
        for a,b in d:
            ny=y+a
            nx=x+b
            if 0<=ny<H and 0<=nx<W:
                if S[ny][nx]=="." and F[ny][nx]!=True:
                    q.append([ny,nx])
                    C[ny][nx]=C[y][x]+1
                    F[ny][nx]=True
bfs()
if F[H-1][W-1]==False:
    print(-1)
    exit()

ans=H*W-C[H-1][W-1]-1-black
print(ans)

Solution (Python):
from collections import deque

H,W=map(int,input().split())
S=[input() for i in range(H)]
black=0
for i in range(H):
    black+=S[i].count("

C=[[0 for _ in range(W)] for j in range(H)]
F=[[False for _ in range(W)] for j in range(H)]

def bfs():
    q=deque([[0,0]])
    F[0][0]=True
    d=[[0,1],[1,0],[-1,0],[0,-1]]
    while q:
        y,x=q.popleft()
        for a,b in d:
            ny=y+a
            nx=x+b
            if 0<=ny<H and 0<=nx<W:
                if S[ny][nx]=="." and F[ny][nx]!=True:
                    q.append([ny,nx])
                    C[ny][nx]=C[y][x]+1
                    F[ny][nx]=True
bfs()
if F[H-1][W-1]==False:
    print(-1)
    exit()

ans=H*W-C[H-1][W-1]-1-black
print(ans)

Solution (Python):
H, W = map(int, input().split())
s_tmp = [input() for i in range(H)]
s = [[0] * W for i in range(H)]
b = 0
for i in range(H):
    for j in range(W):
        if s_tmp[i][j] == '
            s[i][j] = -1
            b += 1
c = [(0, 0)]
i = 0
while (H - 1, W - 1) not in c:
    c_tmp = []
    i += 1
    for h, w in c:
        if h > 0 and s[h - 1][w] == 0:
            s[h - 1][w] = i
            c_tmp.append((h - 1, w))
        if h < H - 1 and s[h + 1][w] == 0:
            s[h + 1][w] = i
            c_tmp.append((h + 1, w))
        if w > 0 and s[h][w - 1] == 0:
            s[h][w - 1] = i
            c_tmp.append((h, w - 1))
        if w < W - 1 and s[h][w + 1] == 0:
            s[h][w + 1] = i
            c_tmp.append((h, w + 1))
    if len(c_tmp) == 0:
        break
    c = c_tmp
if len(c_tmp) == 0:
    print(-1)
else:
    print(H * W - b - i - 1)

Solution (Python):
from queue import Queue
H, W = map(int,input().split())
MAP = []
for _ in range(H):
    MAP.append(list(input()))
tx = [1,0,-1,0]
ty = [0,1,0,-1]
cnt = 0
INF = 10 ** 8
for i in range(H):
    for j in range(W):
        if MAP[i][j] == '
            cnt += 1
d = [[INF for i in range(W)] for j in range(H)]
q = Queue()
q.put([0,0])
d[0][0] = 1
flag = 1
while not q.empty():
    x, y = q.get()
    if x == H - 1 and y == W - 1:
        flag = 0
        break
    for i in range(4):
        nx = x + tx[i]
        ny = y + ty[i]
        if 0 <= nx <= H-1 and 0 <= ny <= W-1 and MAP[nx][ny] == '.' and d[nx][ny] == INF:
            d[nx][ny] = d[x][y] + 1
            q.put([nx,ny])
if flag:
    print(-1)
else:
    ans = H * W - d[H-1][W-1] - cnt
    print(ans)

Solution (Python):
from collections import deque
H, W = map(int, input().split())
maze = [[0 for i in range(W)]for j in range(H)]
ans = -1
for i in range(H):
    S = input()
    for j in range(W):
        maze[i][j] = S[j]
        if maze[i][j] == '.':
            ans += 1

q = deque()
q.append([0, 0])
maze[0][0] = 0
while len(q) != 0:
    x, y = q.popleft()
    for i in range(4):
        nx, ny = x + [0, 1, 0, -1][i], y + [1, 0, -1, 0][i]
        if nx < 0 or ny < 0 or nx >= W or ny >= H:
            continue
        elif maze[ny][nx] == '
            continue
        elif maze[ny][nx] == '.':
            maze[ny][nx] = maze[y][x] + 1
            q.append([nx, ny])
if maze[H-1][W-1] == '.':
    print(-1)
else:
    print(ans - maze[H-1][W-1])

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

mat=[]
mat.append([False]*(W+2))
for i in range(H):
  array=[False]+[x=="." for x in input()]+[False]
  mat.append(array)
mat.append([False]*(W+2))


true_num=0
for i in range(1,H+1):
  for j in range(1,W+1):
    if mat[i][j]:
      true_num+=1

if not mat[1][1] or not mat[H][W]:
  print(-1)
  sys.exit(0)

visited_dic={}
dist=0
queue={(1,1)}
while(len(queue)>0):
  new_queue=set()
  
  for q in queue:
    visited_dic[q]=dist
    if q==(H,W):
      break
    
    x,y=q
    if mat[x-1][y] and not (x-1,y) in visited_dic:
      new_queue.add((x-1,y))
    if mat[x+1][y] and not (x+1,y) in visited_dic:
      new_queue.add((x+1,y))
    if mat[x][y-1] and not (x,y-1) in visited_dic:
      new_queue.add((x,y-1))
    if mat[x][y+1] and not (x,y+1) in visited_dic:
      new_queue.add((x,y+1))
      
  queue=new_queue
  dist+=1
  
if not (H,W) in visited_dic:
  print(-1)
else:
  
  print(true_num-visited_dic[(H,W)]-1)

Solution (Python):
from collections import deque

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

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

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

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

while q:
    y,x = q.pop()
    for dy,dx in directions:
        if not (0<= y+dy < H and 0 <= x+dx < W):
            continue
        elif s[y+dy][x+dx] == '
            continue
        elif A[y+dy][x+dx] != -1:
            continue
        else:
            A[y+dy][x+dx] = A[y][x] + 1
            q.appendleft([y+dy,x+dx])
if A[H-1][W-1] == -1:
    print(-1)
    exit()

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

print(a-A[H-1][W-1]-1)

Solution (Python):
import heapq

H,W = map(int,input().split())
maze = []
for i in range(H):
    maze.append(list(input()))
nodes = []
nodedict = {}
for i in range(H):
    for j in range(W):
        if maze[i][j] == '.':
            nid = len(nodes)
            nodedict[(i,j)] = nid
            nodes.append((i,j))

N = len(nodes)
INF = H*W
edges = [[False]*N for _ in range(N)]

def link(i1,j1,i2,j2):
    n1 = nodedict[(i1,j1)]
    n2 = nodedict[i2,j2]
    edges[n1][n2] = edges[n2][n1] = True

for i in range(H):
    for j in range(W):
        if maze[i][j] != '.': continue
        if i > 0 and maze[i-1][j]=='.': link(i,j,i-1,j)
        if i < H-1 and maze[i+1][j]=='.': link(i,j,i+1,j)
        if j > 0 and maze[i][j-1]=='.': link(i,j,i,j-1)
        if j < W-1 and maze[i][j+1]=='.': link(i,j,i,j+1)

dist = [INF] * len(nodes)

def solve():
    dist[0] = 0
    n0 = nodedict[(0, 0)]
    pq = [(0, n0)]
    determined = {n0}
    while pq:
        d, nid = heapq.heappop(pq)
        for i, linked in enumerate(edges[nid]):
            if linked and i not in determined:
                dist[i] = min(dist[i], d+1)
                determined.add(i)
                heapq.heappush(pq, (d+1, i))
    goal = nodedict[(H-1, W-1)]
    if dist[goal] == INF:
        return -1
    return len(nodes) - dist[goal] - 1

print(solve())

Solution (Python):
import sys
import queue
input = sys.stdin.readline
sys.setrecursionlimit(int(1E+7))
dxdy = ((-1,0), (1,0), (0,-1), (0,1))
H, W = map(int,input().split())
maze = []
visited = [ [0]*W for _ in range(H)]
black = 0
for h in range(H):
    s = input()
    maze.append(s)
    for c in s:
        if c=='
            black += 1
q = queue.Queue()
q.put((0,0,0))
cost = -1
while(not q.empty()):
    y, x, d = q.get()
    if x == W-1 and y == H-1:
        cost = d
        break
    if visited[y][x] == 1:
        continue
    else:
        visited[y][x] = 1
        for dx, dy in  dxdy:
            if (0<= x+dx < W) and (0<= y+dy < H):                
                if visited[y+dy][x+dx] == 0 and maze[y+dy][x+dx]=='.':
                    q.put((y+dy,x+dx,d+1))
if cost==-1:
    print (-1)
else:
    print (H*W-cost-1-black)

Solution (Python):
import queue
h,w = map(int,input().split())
sij = [input() for i in range(h)]

if sij[0][0] == '
    print(-1)
    exit()

q = queue.Queue()

q.put([0,0])

vx = [0,1,0,-1]
vy = [1,0,-1,0]

check = [0]*(h*w)
check[0] = 1

while not q.empty():
    x,y = q.get()
    for i in range(4):
        nx = x+vx[i]
        ny = y+vy[i]
        if nx >= 0 and nx <= w-1 and ny >= 0 and ny <= h-1:
            if check[ny*w+nx] == 0 and sij[ny][nx] == '.':
                q.put([nx,ny])
                check[ny*w+nx] = check[y*w+x] + 1
                if ny == h-1 and nx == w-1:
                    check[ny*w+nx] = check[y*w+x] + 1
                    break
kuro = 0

for i in range(h):
    for j in range(w):
        if sij[i][j] == '
            kuro += 1
if check[-1] == 0:
    print(-1)
    exit()
print(h*w-kuro-check[-1])

Solution (Python):
from collections import deque

H,W = map(int,input().split())
S = [list(input()) for _ in range(H)]
C_Count = [[1 for _ in range(W)] for _ in range(H)]
num = 0
goal_flag = False

def bfs(x,y,S):
    que = deque()
    que.append((x,y))

    while que:
        x,y = que.popleft()
        if S[x][y] == "
            continue
        if x == (H - 1) and y == (W - 1):
            return C_Count[x][y]
        S[x][y] = "
        for dx,dy in ((-1,0),(1,0),(0,-1),(0,1)):
            sx = x + dx
            sy = y + dy
            if sx < 0 or sx >= H or sy < 0 or sy >= W:
                continue
            que.append((sx,sy))
            C_Count[sx][sy]=C_Count[x][y] + 1
    return -1

for i in S:
    num += i.count("

tmp = bfs(0,0,S)
if tmp == -1:
    print(tmp)
else:
    print(H * W - tmp - num)

Solution (Python):
from collections import deque

H,W=map(int,input().split())
count=0
S=[['
for i in range(1,H+1):
    S_comp=list(str(input()))
    for j in range(1,W+1):
        if S_comp[j-1]=='.':
            count+=1
        S[i][j]=S_comp[j-1]


def sur(v):  
    vx=v[0]
    vy=v[1]
    preE=[(vx-1,vy),(vx+1,vy),(vx,vy-1),(vx,vy+1)]
    E=[]
    for nv in preE:
        if 1<=nv[0]<=H and 1<=nv[1]<=W:
            if S[nv[0]][nv[1]]=='.':
                E.append(nv)
    return E

q=deque()
s=(1,1)
g=(H,W)
q.append(s)
dist=[[-1]*(W+1) for k in range(H+1)]
dist[s[0]][s[1]]=0

while q:
    now=q.popleft()
    for next in sur(now):
        if dist[next[0]][next[1]]!=-1:
            continue
        q.append(next)
        dist[next[0]][next[1]]=dist[now[0]][now[1]]+1
        if next==g:
            ans=dist[g[0]][g[1]]
            print(count-1-ans)
            break
    else:
        continue
    break
else:
    print(-1)

Solution (Python):
from collections import deque
h,w = map(int,input().split())
map_a = [[] for _ in range(h)]
for i in range(h):
    for c in input():
            map_a[i].append(0 if c == "
d = [(1,0),(0,1),(-1,0),(0,-1)]

area = 0
stack = deque()
stack.append((0,0))

while stack:
    x,y = stack.popleft()
    for u,v in d:
        m = x + u; n = y + v
        if 0<=m<h and 0<=n<w:
            if map_a[m][n]==1:
                map_a[m][n] = map_a[x][y]+1
                stack.append((m,n))
                area += 1
if map_a[-1][-1] == 1:
    print(-1);exit()

pound = 0
for i in range(h):
    for c in map_a[i]:
        if c == 1:
            pound += 1
print(area-map_a[-1][-1]+pound)

Solution (Python):
from collections import deque
H, W = map(int, input().split())
areas = []
blacks = 0
for _ in range(H):
    texts = list(input().rstrip())
    for char in texts:
        if char == '
            blacks += 1
    areas.append(texts)







inf = float('inf')


def bfs(start_point, goal_point):
    scores = [[inf for _ in range(W)] for _ in range(H)]
    queue = deque([start_point])
    scores[0][0] = 0
    move_positions = [[-1, 0], [0, -1], [1, 0], [0, 1]]
    while queue:
        now_point = queue.popleft()
        for move_position in move_positions:
            next_point = [now_point[0] + move_position[0],
                          now_point[1] + move_position[1]]
            if 0 <= next_point[0] < H and 0 <= next_point[1] < W:
                if areas[next_point[0]][next_point[1]] == '.':
                    if scores[next_point[0]][next_point[1]] > scores[now_point[0]][now_point[1]] + 1:
                        scores[next_point[0]][next_point[1]
                                              ] = scores[now_point[0]][now_point[1]] + 1
                        queue.append(next_point)
    return scores[H - 1][W - 1]


cost = bfs([0, 0], [H - 1, W - 1]) + 1
if cost == inf:
    print(-1)
else:
    print(H * W - blacks - cost)

Solution (Python):
import sys
sys.setrecursionlimit(10**8)
def ii(): return int(sys.stdin.readline())
def mi(): return map(int, sys.stdin.readline().split())
def li(): return list(map(int, sys.stdin.readline().split()))
def li2(N): return [list(map(int, sys.stdin.readline().split())) for _ in range(N)]
def dp2(ini, i, j): return [[ini]*i for _ in range(j)]
def dp3(ini, i, j, k): return [[[ini]*i for _ in range(j)] for _ in range(k)]




from collections import deque

H, W = mi()
S = [input() for _ in range(H)]

d = dp2(-1, W, H)
d[0][0] = 1
que = deque([[0, 0]])

h = [1, 0, -1, 0]
v = [0, -1, 0, 1]

while que != deque():
    i, j = que.popleft()
    for x in range(4):
        di, dj = h[x], v[x]
        if 0 <= i+di < H and 0 <= j+dj < W:
            if S[i+di][j+dj] !='
                d[i+di][j+dj] = d[i][j] + 1
                que.append([i+di, j+dj])

if d[H-1][W-1] == -1:
    print('-1')
else:
    ans = H*W - d[H-1][W-1] - sum([S[i].count('
    print(ans)

Solution (Python):
h,w=map(int,input().split())
sx,sy=0,0
gx,gy=w-1,h-1

maze=[]
white=0
for _ in range(h):
    temp=input()
    t=[]
    for s in temp:
        t.append(s)
        if s==".":
            white+=1
    maze.append(t)

maze[sy][sx]=1

from collections import deque
fifo = deque()
fifo.append([sy,sx])

result=-1

while len(fifo)>0:
    temp=fifo.popleft()
    y,x=temp[0],temp[1]

    if y==gy and x==gx:
        result=maze[y][x]

    if y>0:
        if maze[y-1][x]==".":
            fifo.append([y-1,x])
            maze[y-1][x]=maze[y][x]+1
    if y<h-1:
        if maze[y+1][x]==".":
            fifo.append([y+1,x])
            maze[y+1][x]=maze[y][x]+1
    if x>0:
        if maze[y][x-1]==".":
            fifo.append([y,x-1])
            maze[y][x-1]=maze[y][x]+1
    if x<w-1:
        if maze[y][x+1]==".":
            fifo.append([y,x+1])
            maze[y][x+1]=maze[y][x]+1



if result==-1:
    print(result)
else:
    print(white-result)