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):
import queue

q = queue.Queue()
H,W = map(int, input().split())
memo = [[-1]*W for _ in range(H)]
board = [input() for _ in range(H)]
wall=0
direction = [(1, 0), (-1, 0), (0, 1), (0, -1)]


def bfs():
    memo[0][0] = 0
    q.put((0, 0))
    while not q.empty():
        y,x= q.get()
        for (dy, dx) in direction:
            if 0<=y+dy<=H-1 and 0<=x+dx<=W-1 and board[y+dy][x+dx] == '.' and memo[y+dy][x+dx] == -1:
                q.put((y + dy, x + dx))
                memo[y + dy][x + dx] = memo[y][x] + 1
                if (y+dy, x+dx) == (H-1, W-1):
                    return memo[H-1][W-1]
    return -1


for s in board:
    wall+=s.count('

min_dist=bfs()
print(H*W-wall-(min_dist+1) if min_dist>0 else -1)

Solution (Python):
H,W = (int(i) for i in input().split())
grid = ['
smap = [[-1 for i in range(W+2)] for i in range(H+2)]
q = []
dot = 0
angle = [[1,0],[-1,0],[0,1],[0,-1]]

for i in grid:
  dot += i.count('.')

smap[1][1] = 1
q.append([1,1])

while len(q) > 0:
  pos = q.pop(0)
  cnt = smap[pos[0]][pos[1]] + 1
  for a in angle:
    if grid[pos[0]+a[0]][pos[1]+a[1]] == '.' and smap[pos[0]+a[0]][pos[1]+a[1]] == -1:
      q.append([pos[0]+a[0],pos[1]+a[1]])
      smap[pos[0]+a[0]][pos[1]+a[1]] = cnt

print(-1) if smap[H][W] == -1 else print(dot - smap[H][W])

Solution (Python):
from collections import deque
H,W = map(int, input().split())
maze = [input() for _ in range(H)]
cnt_wall = 0
for y in range(H):
    for x in range(W):
        if maze[y][x]=="
            cnt_wall += 1
            
q = deque([(0,0)])
dist = [[float('inf')]*W for _ in range(H)]
dist[0][0] = 1

while q:
    y,x = q.popleft()
    
    if (y,x)==(H-1,W-1):
        print(H*W - cnt_wall - dist[y][x])
        break
    for dy,dx in zip([0,0,1,-1], [1,-1,0,0]):
        nx,ny = x+dx, y+dy
        if not(0<=ny<H and 0<=nx<W):
            continue
        if maze[ny][nx]=="." and dist[ny][nx]==float('inf'):
            q.append((ny, nx))
            dist[ny][nx] = dist[y][x] + 1
else:
    print(-1)

Solution (Python):
from sys import exit
import queue
dxy = [[1,0],[-1,0],[0,1],[0,-1]]
INF = (1 << 21)
H,W = [int(n) for n in input().split()]
ans = 0
Map = [[0 for _ in range(W)] for __ in range(H)]
D = [[INF for _ in range(W)] for __ in range(H)]
for h in range(H):
    Map[h] = list(input())
    ans+=Map[h].count(".")



def bfs(s):
    q = queue.Queue()
    q.put(s)
    D[s[0]][s[1]] = 1
    while(not q.empty()):
        u = q.get()
        for d in dxy:
            v = [u[0] + d[0], u[1] + d[1]]
            if (v[0] < 0 or v[1] < 0 or v[0] >= H or v[1] >= W or Map[v[0]][v[1]] == "
            if (D[v[0]][v[1]] != INF):continue
            D[v[0]][v[1]] = D[u[0]][u[1]] + 1
            q.put(v)
bfs([0,0])


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

Solution (Python):
h, w = [int(s) for s in input().split(' ')]
 
s = []
for i in range(h):
    s.append([s == '.' for s in input()])
 
inf = 10000
dx = [1, 0, -1, 0]
dy = [0, 1, 0, -1]

queue = [(0, 0)]
p = []
for i in range(h):
    p.append([inf] * w)
p[0][0] = 1
 
while len(queue) > 0:
    x, y = queue.pop()
    for i in range(4):
        xx = x + dx[i]
        yy = y + dy[i]
        if 0 <= xx and xx < w and 0 <= yy and yy < h:
            if s[yy][xx] and p[yy][xx] > p[y][x] + 1:
                p[yy][xx] = p[y][x] + 1
                queue.insert(0, (xx, yy))
           
if p[h-1][w-1] == inf:
    print('-1')
else:
    print(sum(sum(x) for x in s) - p[h-1][w-1])

Solution (Python):
h, w = [int(s) for s in input().split(' ')]
 
s = []
for i in range(h):
    s.append([s == '.' for s in input()])
 
inf = 10000
dx = [1, 0, -1, 0]
dy = [0, 1, 0, -1]

queue = [(0, 0)]
p = []
for i in range(h):
    p.append([inf] * w)
p[0][0] = 1
 
while len(queue) > 0:
    x, y = queue.pop()
    for i in range(4):
        xx = x + dx[i]
        yy = y + dy[i]
        if 0 <= xx and xx < w and 0 <= yy and yy < h and s[yy][xx] and p[yy][xx] > p[y][x] + 1:
           p[yy][xx] = p[y][x] + 1
           queue.insert(0, (xx, yy))
           
if p[h-1][w-1] == inf:
    print('-1')
else:
    print(sum(sum(x) for x in s) - p[h-1][w-1])

Solution (Python):
h, w = [int(s) for s in input().split(' ')]
 
s = []
for i in range(h):
    s.append([s == '.' for s in input()])

inf = 10000
dx = [1, 0, -1, 0]
dy = [0, 1, 0, -1]
q = [(0, 0)]
p = []
for i in range(h):
    p.append([inf] * w)
p[0][0] = 1

while len(q) > 0:
    x, y = q.pop()
    for i in range(4):
        xx = x + dx[i]
        yy = y + dy[i]
        if 0 <= xx and xx < w and 0 <= yy and yy < h and s[yy][xx] and (p[yy][xx] > p[y][x] + 1):
           p[yy][xx] = p[y][x] + 1
           q.insert(0, (xx, yy))
if p[h-1][w-1] == inf:
    print('-1')
else:
    print(sum(sum(x) for x in s) - p[h-1][w-1])

Solution (Python):
def grid_repainting(H: int, W: int, S: int) -> int:
    
    
    INF = float('inf')
    R = [[INF] * W for _ in range(H)]
    R[0][0] = 1
    white_num = 0

    update = True
    while update:
        update = False
        white_num = 0
        for h in range(H):
            for w in range(W):
                if S[h][w] == '
                    
                    continue
                white_num += 1

                before = R[h][w]
                if w > 0:
                    R[h][w] = min(R[h][w], R[h][w - 1] + 1)
                if h > 0:
                    R[h][w] = min(R[h][w], R[h - 1][w] + 1)
                if w < W - 1:
                    R[h][w] = min(R[h][w], R[h][w + 1] + 1)
                if h < H - 1:
                    R[h][w] = min(R[h][w], R[h + 1][w] + 1)

                if before != R[h][w]:
                    update = True

    if R[H - 1][W - 1] is INF:
        return - 1

    
    
    
    return white_num - R[H-1][W-1]


if __name__ == "__main__":
    H = 0
    H, W = map(int, input().split())
    S = [input() for _ in range(H)]
    ans = grid_repainting(H, W, S)
    print(ans)

Solution (Python):
from collections import deque

h,w = (int(i) for i in input().split())
maze = [['

f = 0
for i in range(1,h+1):
 for j in range(1,w+1):
  
  if maze[i][j]:f+=1

flag= 0
pos = deque([(1,1,0)])
while pos:
  x,y,c = pos.popleft()
  
  if (x,y) == (h,w):
    print(h*w-f-c-1)
    exit()
  elif maze[x][y]:
    
    continue
  
  pos.append((x-1, y, c+1))
  pos.append((x+1, y, c+1))
  pos.append((x, y-1, c+1))
  pos.append((x, y+1, c+1))
  
  maze[x][y] = True
if flag == 0:
 print(-1)

Solution (Python):
H,W = map(int,input().split())
S = [[1]*(W+2)]
for _ in range(H):
    tmp = [1]
    [tmp.append(int(c=="
    tmp.append(1)
    S.append(tmp)
S.append([1]*(W+2))
       
ans = 0
for w in range(W+2):
    for h in range(H+2):
        if S[h][w]==0:  
            ans += 1

Q = [[1,1,1]]
S[1][1] = 1

def Step():
    while Q:
        q = Q.pop(0)
        if q[0]==H and q[1]==W:
            return(q[2])
        else:
            for M in [[-1,0],[1,0],[0,-1],[0,1]]:
                if S[q[0]+M[0]][q[1]+M[1]] == 0:
                    S[q[0]+M[0]][q[1]+M[1]] = 1
                    Q.append([q[0]+M[0],q[1]+M[1],q[2]+1])
    else:           
        return(-1)
    
step = Step()
if(step==-1):  
    print(-1)
else:
    print(ans-step)

Solution (Python):
from collections import deque
h,w=map(int,input().split())
maze=[['
f=0
for i in range(1,h+1):
  for j in range(1,w+1):
    if maze[i][j]:
	    f+=1
z=0
pos=deque([(1,1,0)])
while pos:
    x,y,c=pos.popleft()
    if (x,y)==(h,w):
        print(h*w-f-c-1)
        z=1
        break
    elif maze[x][y]:
        continue
    pos.append((x-1, y, c+1))
    pos.append((x+1, y, c+1))
    pos.append((x, y-1, c+1))
    pos.append((x, y+1, c+1))
    maze[x][y] = True
if z==0:
	print(-1)

Solution (Python):
import sys
from collections import defaultdict

nesw = [[0, 1], [0, -1], [1, 0], [-1, 0]]
height, width = map(int, input().split(" "))
root = []
black = 0
for i in range(height):
    temp = [n for n in input()]
    root.append(temp)
    black += temp.count("
start_y, start_x = 0, 0
end_y, end_x = height - 1, width - 1

queue = [(start_y, start_x)]
used_white = 1
flag = 0
while queue:
    new_queue = []
    used_white += 1
    for q in queue:
        h, w = q
        for t in nesw:
            new_h, new_w = h + t[0], w + t[1]
            if 0 <= new_h < height and 0 <= new_w < width:
                if new_h == end_y and new_w == end_x:
                    flag = 1
                    break
                elif root[new_h][new_w] != "
                    root[new_h][new_w] = "
                    new_queue.append((new_h, new_w))
    if flag:
        break
    queue = new_queue
if flag:
    print(height * width - black - used_white)
else:
    print(-1)

Solution (Python):
import sys

def wfs(queue, S, step, goal):
    next_queue = set()
    for q in queue:
        if q == goal:
            return step+1

        i, j = q[0], q[1]
        S[i][j] = '

        if S[i+1][j] == '.':
            next_queue.add((i+1, j))
        if S[i-1][j] == '.':
            next_queue.add((i-1, j))
        if S[i][j+1] == '.':
            next_queue.add((i, j+1))
        if S[i][j-1] == '.':
            next_queue.add((i, j-1))

    if len(next_queue) == 0:
        return -1
    else:
        return wfs(next_queue, S, step+1, goal)


def main():
    input = sys.stdin.readline
    H, W = map(int, input().split())
    S = []
    black = 0
    for _ in range(H):
        s = [c for c in input().strip()]
        black += sum([c == '
        S.append(['
    S = [['
    init = set([(1, 1)])
    minstep = wfs(init, S, 0, (H, W))
    if minstep == -1:
        print(-1)
    else:
        print(H*W - minstep - black)


if __name__ == '__main__':
    main()

Solution (Python):
import sys

def wfs(queue, S, step, goal):
    next_queue = set()
    for q in queue:
        if q == goal:
            return step+1

        i, j = q[0], q[1]
        S[i][j] = '

        if S[i+1][j] == '.':
            next_queue.add((i+1, j))
        if S[i-1][j] == '.':
            next_queue.add((i-1, j))
        if S[i][j+1] == '.':
            next_queue.add((i, j+1))
        if S[i][j-1] == '.':
            next_queue.add((i, j-1))

    if len(next_queue) == 0:
        return -1
    else:
        next_queue = list(set(next_queue))
        return wfs(next_queue, S, step+1, goal)


def main():
    input = sys.stdin.readline
    H, W = map(int, input().split())
    S = []
    black = 0
    for _ in range(H):
        s = [c for c in input().strip()]
        black += sum([c == '
        S.append(['
    S = [['
    init = set([(1, 1)])
    minstep = wfs(init, S, 0, (H, W))
    if minstep == -1:
        print(-1)
    else:
        print(H*W - minstep - black)


if __name__ == '__main__':
    main()

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

queue=deque()
sy,sx=(0,0)
gy,gx=(H-1,W-1)
reached=[[-1 for i in range(W)] for j in range(H)]
queue.append([sy,sx])
reached[sy][sx]=0
dx=[1,-1,0,0]
dy=[0,0,1,-1]
while(queue):
    p=queue.pop()
    for i in range(4):
        y=p[0]+dy[i]
        x=p[1]+dx[i]
        if x<0 or x>=W or y<0 or y>=H or s[y][x]=="
            continue
        if reached[y][x]!=-1:
            continue
        reached[y][x]=reached[p[0]][p[1]]+1
        queue.appendleft([y,x])
n=H*W
for i in range(H):
    for j in range(W):
        if s[i][j]=="
            n-=1
if reached[gy][gx]==-1:
  n=-1       
print(n-reached[gy][gx]-1)

Solution (Python):
h, w = map(int, input().split())
map = [['
n_white = sum(len([s for s in ss if s == '.']) for ss in map)
map = [['

def wfs(next_xy, c):
  tmp_next = set()
  for x, y in next_xy:
    map[y][x] = '
    if x == w and y == h:
      return c + 1
    if map[y][x-1] == '.':
      tmp_next.add((x-1, y))
    if map[y][x+1] == '.':
      tmp_next.add((x+1, y))
    if map[y-1][x] == '.':
      tmp_next.add((x, y-1))
    if map[y+1][x] == '.':
      tmp_next.add((x, y+1))
  if len(tmp_next) == 0:
    return -1
  else:
    return wfs(tmp_next, c+1)

pathl = wfs([(1,1)], 0)
if pathl == -1:
  print(-1)
else:
  print(n_white - pathl)

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

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

s = []
cnt = 0
for i in range(h):
    ss = input()
    s.append(ss)
    cnt += ss.count('

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

visited[0][0] = 1

while queue:
    a = queue.popleft()
    dydx = [[1,0],[-1,0],[0,1],[0,-1]]
    for j,k in dydx:
        newy,newx = a[1]+j,a[0]+k
        if (0 <= newy <h) and (0 <= newx < w):
            if (visited[newy][newx] == -1) and (s[newy][newx] == "."):
                visited[newy][newx] = visited[a[1]][a[0]] + 1
                queue.append((newx,newy))




if(visited[h-1][w-1] == -1): print("-1")
else:
    print(h*w-visited[h-1][w-1]-cnt)

Solution (Python):
h, w = map(int, input().split())
field = [input() for _ in range(h)]
direction = [(1,0), (0,1), (-1,0), (0,-1)]
def wfs(c, search, done):
    if search == set():
        return -1
    if (h-1, w-1) in search:
        return c
    newsearch = set()
    for x, y in search:
        for dx, dy in direction:
            xa = x + dx
            ya = y + dy
            if xa in range(h) and ya in range(w) and (xa, ya) not in done and field[xa][ya] == '.':
                newsearch.add((xa, ya))
        done.add((x, y))
    return wfs(c+1, newsearch, done)
ret = wfs(0, {(0,0)}, set())
if ret == -1:
    print(-1)
else:
    white = 0
    for i in range(h):
        for j in range(w):
            if field[i][j] == '.':
                white += 1
    print(white - ret - 1)

Solution (Python):
h, w = map(int, input().split(' '))
s = [input() for _ in range(h)]
sy, sx = 0, 0
gy, gx = h - 1, w - 1

move = [(1, 0), (-1, 0), (0, 1), (0, -1)]
que = [(sy, sx)]
d = [[float('inf') for _ in range(w)] for _ in range(h)]
d[sy][sx] = 0

while len(que) > 0:
    y, x = que.pop(0)

    for dy, dx in move:
        ny = y + dy
        nx = x + dx

        if ny >= 0 and ny < h and nx >= 0 and nx < w and s[ny][nx] != '
            que.append((ny, nx))
            d[ny][nx] = d[y][x] + 1

if d[gy][gx] == float('inf'):
    print(-1)
else:
    n_white = 0
    for i in s:
        n_white += i.count('.')
    print(n_white - d[gy][gx] - 1)

Solution (Python):
def BFS_one_search(map_,counts,y,x,wall):
    can_be_new_count = []
    new_ques = []
    for i in range(-1,2):
        for j in range(-1,2):
            if i * j == 0 and i != j:
                if counts[y + i][x + j] != -1:
                    can_be_new_count.append(counts[y + i][x + j] + 1)
                elif not(map_[y + i][x + j] in wall):
                    new_ques.append((y + i,x + j))
    new_count = min(can_be_new_count) if len(can_be_new_count) > 0 else 0
    return new_count,new_ques

def breadth_first_search(map_,s_y,s_x,wall = ['
    ques = [(s_y,s_x)]
    counts = []
    for _ in range(len(map_)):
        counts.append([-1] * len(map_[0]))
    while(len(ques) > 0):
        here_count,new_que = BFS_one_search(map_,counts,ques[0][0],ques[0][1],wall)
        counts[ques[0][0]][ques[0][1]] = here_count
        for i in range(len(new_que)):
            if not new_que[i] in ques:
                ques.append(new_que[i])
        ques.pop(0)
    return counts

def make_map_data(H,W,wall = '
    map_ = []
    if make_wall:
        map_.append([wall] * (W + 2))
        for _ in range(H):
            map_.append([wall] + list(input()) + [wall])
        map_.append([wall] * (W + 2))
    else:
        for _ in range(H):
            map_.append(list(input()))
    return map_
H,W= (int(i) for i in input().split())  
s_y = 1
s_x = 1
g_y = H 
g_x = W
map_ = make_map_data(H,W,make_wall = True)
min_counts = breadth_first_search(map_,s_y,s_x)[g_y][g_x]
if min_counts == -1:
    print(-1)
else:
    wall_count = 0
    for y in range(H + 2):
        for x in range(W + 2):
            if map_[y][x] == '
                wall_count += 1
    
    print((H + 2) * (W + 2) - wall_count - (min_counts + 1))

Solution (Python):
import heapq
def dijkstra_heap(s):
    
    d = [float("inf")] * n
    used = [True] * n 
    d[s] = 0
    used[s] = False
    edgelist = []
    for e in edge[s]:
        heapq.heappush(edgelist,e)
    while len(edgelist):
        minedge = heapq.heappop(edgelist)
        
        if not used[minedge[1]]:
            continue
        v = minedge[1]
        d[v] = minedge[0]
        used[v] = False
        for e in edge[v]:
            if used[e[1]]:
                heapq.heappush(edgelist,[e[0]+d[v],e[1]])
    return d

h,w = map(int,input().split())
white = 0
n = h*w
edge = [[] for i in range(n)]

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

for i in range(h):
    for j in range(w):
        if s[i][j] == ".":
            white += 1
            if i != h-1 and s[i+1][j] == ".":
                edge[w*i+j].append([1,w*i+j+w])
                edge[w*i+j+w].append([1,w*i+j])
            if j != w-1 and s[i][j+1] == ".":
                edge[w*i+j].append([1,w*i+j+1])
                edge[w*i+j+1].append([1,w*i+j])


d = dijkstra_heap(0)

if d[-1] == float("inf"):
    print(-1)
else:
    print(white-d[-1]-1)

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 and nx < h and 0 <= ny and 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):
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 and nx < h and 0 <= ny and 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

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

res = bfs()
if 0 < res < float("inf"):
    print(h * w - res - black - 1)
else:
    print(-1)

Solution (Python):
import queue
import sys

write = sys.stdout.write

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

class Block:
    visited = False
    parent = None
    def __init__(self, c, x, y):
        self.color = c
        self.x = x
        self.y = y

def trace(A, blk):
    blk.color = "r"
    if blk.x == 1 and blk.y == 1:
        return
    trace(A, blk.parent)

def solve(A):
    global H
    global W

    
    if A[1][1].color == "
        return -1

    q = queue.Queue()
    q.put(A[1][1])
    while not q.empty():
        blk = q.get()
        if blk.x == H and blk.y == W: 
            trace(A, blk)
            return 1
        
        
        
        

        
        if A[blk.x - 1][blk.y].visited == False and A[blk.x - 1][blk.y].color == ".":
            A[blk.x - 1][blk.y].parent = blk
            A[blk.x - 1][blk.y].visited = True
            q.put(A[blk.x - 1][blk.y])

        
        if A[blk.x + 1][blk.y].visited == False and A[blk.x + 1][blk.y].color == ".":
            A[blk.x + 1][blk.y].parent = blk
            A[blk.x + 1][blk.y].visited = True
            q.put(A[blk.x + 1][blk.y])

        
        if A[blk.x][blk.y + 1].visited == False and A[blk.x][blk.y + 1].color == ".":
            A[blk.x][blk.y + 1].parent = blk
            A[blk.x][blk.y + 1].visited = True
            q.put(A[blk.x][blk.y + 1])

        
        if A[blk.x][blk.y - 1].visited == False and A[blk.x][blk.y - 1].color == ".":
            A[blk.x][blk.y - 1].parent = blk
            A[blk.x][blk.y - 1].visited = True
            q.put(A[blk.x][blk.y - 1])
    return -1



cnt = 0 

maze = [[Block("d", i, j) for j in range(W+2)] for i in range(H+2)]
for i in range(1, H+1):
    row = input()
    for j in range(W):
        maze[i][j+1] = Block(row[j], i, j+1)

possible = solve(maze)

if possible == -1:
    print("-1")
else:
    for i in range(1, H+1):
        for j in range(1, W+1):
            if maze[i][j].color == ".":
                cnt += 1
    print(str(cnt))

Solution (Python):
from collections import deque

H,W = map(int,input().split())
_input = []
for i in range(H):
    row = list(map(str,input().split()))
    _input.append(list(row[0]))

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

queue = deque([(sy,sx)])

dyx=((1,0),(-1,0),(0,1),(0,-1))

counted_map = [[-1]*W for _ in range(H)]
counted_map[sy][sx] = 0

reach = False

while queue:
    y,x = queue.popleft()

    if (y,x) == (gy,gx):
        reach = True
        break

    for dy,dx in dyx:
        ny = y + dy
        nx = x + dx

        if ny < 0 or nx < 0 or ny >= H or nx >= W:
            continue

        
        if _input[ny][nx] == '.' and counted_map[ny][nx] == -1:
            counted_map[ny][nx] = counted_map[y][x] + 1
            queue.append((ny,nx))

if not reach:
    print(-1)
    exit()
'''
y,x = gy,gx
move_num = counted_map[gy][gx]
while move_num != 0:
    _input[y][x] = 'o'
    for dy,dx in dyx:
        ny = y + dy
        nx = x + dx

        if ny < 0 or nx < 0 or ny >= H or nx >= W:
            continue
        
        if _input[ny][nx] == '.':
            tmp_dist = counted_map[ny][nx]
            if tmp_dist < move_num:
                move_num = tmp_dist
                next_y,next_x = ny,nx
    
    y,x = next_y,next_x

_input[sy][sx] = 'o'
'''

res = 0

for raw in _input:
    for i in raw:
        if i == '.':
            res += 1

print(res-counted_map[gy][gx]-1)

Solution (Python):
import math,string,itertools,fractions,heapq,collections,re,array,bisect,sys,random,time,copy,functools

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

move = [[0,1],[1,0],[-1,0],[0,-1]]
distance = [[-1]*W for _ in range(H)]
distance[0][0] = 0
q = collections.deque()
q.append((0,0))

while q:
    h, w = q.popleft()
    cur = distance[h][w]
    for dh, dw in move:
        if not 0<=h+dh<=H-1 or not 0<=w+dw<=W-1:
            continue
        if distance[h+dh][w+dw] == -1 and s[h+dh][w+dw] == '.':
            distance[h+dh][w+dw] = cur + 1
            q.append((h+dh, w+dw))

num_white = 0
for x in s:
    num_white += x.count('.')

if distance[H-1][W-1] == -1:
    print(-1)
else:
    print(num_white - distance[H-1][W-1] - 1)

Solution (Python):
H, W = [int(i) for i in input().split()]
sy, sx = [0,0]
gy, gx = [H-1, W-1]
c_ls = list()
yet_ls = [(sy,sx)]
dist_dict = {(sy, sx): 0}
road_len = 0
for i in range(H):
    c_ls.append([i for i in list(input())])
    road_len += len([i for i in c_ls[-1] if i == "."])


def dfs():
    ind = 0
    while len(yet_ls) > ind:
        y, x = yet_ls[ind]
        for move_y, move_x in [(1,0),(-1,0),(0,1),(0,-1)]:
            next_y = y + move_y
            next_x = x + move_x
            if 0 <= next_y < H and 0 <= next_x < W:
                pass
            else:
                continue
            if c_ls[next_y][next_x] == "
                continue
            c_ls[next_y][next_x] = "
            if (next_y, next_x) not in dist_dict:
                dist_dict[(next_y, next_x)] = dist_dict[(y,x)] + 1
                yet_ls.append((next_y,next_x))
            if (next_y, next_x) == (gy, gx):
                return dist_dict[(next_y, next_x)]
        ind += 1
    return road_len


print(road_len - dfs() - 1)

Solution (Python):
from collections import deque
h,w = map(int,input().split())
hw = [];count = 0;check = False
for i in range(h):
    ls = [x for x in input()]
    for j in range(w):
        if ls[j] == '.':count += 1
    hw.append(ls)
deq = deque()
matrix = [[False for j in range(w)] for i in range(h)]
deq.appendleft([0,0,0])
while deq:
    ls = deq.pop()
    for i in [[1,0],[-1,0],[0,1],[0,-1]]:
        x = ls[0]+i[0];y = ls[1]+i[1]
        if x < 0 or y < 0 or x >= h or y >= w:continue
        if matrix[x][y] or hw[x][y] == '
        if h-1 == x and w-1 == y:check = True;num = ls[2];break
        deq.appendleft([x,y,ls[2]+1])
        matrix[x][y] = True
    if check:break
if check:print(count-num-2)
else:print(-1)

Solution (Python):


H,W = map(int, input().split())
S   = [ input() for _ in range(H)]
inf = float("inf")
costmap = [ [inf] * W for _ in range(H)]


kuro_num = 0
for h in range(H):
    for w in range(W):
        if S[h][w] == "
            kuro_num += 1
shiro_num = H*W - kuro_num

from collections import deque
q = deque()

q.append( (0,0,0) )

shortest  = inf
while q:
    h,w,cost = q.popleft()
    if h == H-1 and w == W-1:
        shortest = cost
        break

    if w < W-1 and S[h][w+1] == "." and  costmap[h][w+1]==inf:
        q.append( (h, w+1, cost+1) )
        costmap[h][w+1] = cost+1

    if h < H-1 and S[h+1][w] == "." and  costmap[h+1][w] == inf:
        q.append( (h+1, w, cost+1) )
        costmap[h+1][w] = cost+1

    if 0< h and S[h-1][w] == "." and  costmap[h-1][w] == inf:
        q.append( (h-1, w, cost+1) )
        costmap[h-1][w] = cost+1
    if 0< w and S[h][w-1] == "." and  costmap[h][w-1] == inf:
        q.append( (h, w-1, cost+1) )
        costmap[h][w-1] = cost+1
if shortest == inf:
    ans = -1
else:
    ans  =  shiro_num - (shortest+1)
print(ans)

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

kabe = 0
for x in range(w):
    for y in range(h):
        if board[y][x] == "
            kabe += 1
s = [0, 0]
g = [h-1, w-1]
d = [[-1 for _ in range(w)] for _ in range(h)]
queue = []
queue.append(s)
dx = [1, 0, -1, 0]
dy = [0, 1, 0, -1]
while len(queue) != 0:
    p = queue.pop(0)
    if p[0] == g[0] and p[1] == g[1]:
        break
    for x, y in zip(dx, dy):
        nx = p[1] + x
        ny = p[0] + y
        if 0<=nx<w and 0<=ny<h and board[ny][nx] != "
            d[ny][nx] = d[p[0]][p[1]] + 1
            queue.append([ny, nx])
if d[g[0]][g[1]] == -1:
    print(-1)
else:
    print(h*w - d[g[0]][g[1]] - kabe - 2)

Solution (Python):
from collections import deque
H, W = map(int, input().split())
M = [list(input()) for _ in range(H)]
white = 0
for line in M:
    white += line.count('.')
visited = [[False for _ in range(W)] for _ in range(H)]
que = deque()
que.append((0, 0, 1))
visited[0][0] = True
dirction = ((1, 0), (0, 1), (-1, 0), (0, -1))
while que:
    h, w, count = que.popleft()
    if (h, w) == (H - 1, W - 1):
        print(white - count)
        break
    for i in range(4):
        nh, nw = (h + dirction[i][0], w + dirction[i][1])
        if 0 <= nh <= H - 1 and 0 <= nw <= W - 1:
            if M[nh][nw] == '.' and not visited[nh][nw]:
                que.append((nh, nw, count + 1))
                visited[nh][nw] = True
else:
    print(-1)

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

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

grid[0][0]=0
loc=[[0,0]]      
    
ans=0
for k in range(1,h*w):
  next_loc=[]
  for [y,x] in loc:
    for [i,j] in ([1,0],[-1,0],[0,1],[0,-1]):
      if 0<=y+i<=h-1 and 0<=x+j<=w-1:
        if grid[y+i][x+j]=='.':
          grid[y+i][x+j]=k
          next_loc.append([y+i,x+j])
    loc=next_loc
  if [h-1,w-1] in loc:
    ans=k
    break

if ans==0:
  print(-1)
else:
  print(sum-k-1)

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

INF = 100000000
D = [[INF] * w for i in range(h)]
dx = [1, 0, -1, 0]
dy = [0, 1, 0 , -1]

def bfs():
    que = []
    que.append([sx, sy])
    D[sx][sy] = 0
    
    while que != []:
        p = que.pop(0)
        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 A[nx][ny] != '
                que.append([nx, ny])
                D[nx][ny] = D[p[0]][p[1]] + 1
            
    return D[gx][gy]

r = bfs()

cnt = 0
for i in range(h):
    for j in range(w):
        if A[i][j] == '.':
            cnt += 1
            
print(cnt - r - 1 if r != INF else -1)

Solution (Python):
import queue
H,W=map(int,input().split())
s=[list(input()) for i in range(H)]
dist=[[-1 for i in range(W)] for i in range(H)]
q=queue.Queue()
q.put((0,0))
dist[0][0]=0
dx=[-1,1,0,0]
dy=[0,0,1,-1]
while(not(q.empty())):
    r=q.get()
    x,y=r
    for k in range(4):
        nx=x+dx[k]
        ny=y+dy[k]
        if 0<=nx<H and 0<=ny<W:
            if dist[nx][ny]!=-1:
                continue
            if s[nx][ny]=="
                continue
            dist[nx][ny]=dist[x][y]+1
            q.put((nx,ny))
ans=dist[H-1][W-1]
sharp=0
for i in range(H):
    for j in range(W):
        if s[i][j]=="
            sharp+=1
if ans==-1:
    print(ans)
else:
    print(H*W-ans-1-sharp)