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

H,W=map(int,input().split())
dots=H*W
field=[]
for _ in range(H):
    tmp=input()
    dots-=tmp.count("
    field.append(tmp)

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

while que:
    y,x=que.popleft()
    for dx,dy in zip(DX,DY):
        nx=x+dx
        ny=y+dy
        if nx<0 or nx>=W or ny<0 or ny>=H: continue
        if field[ny][nx]=="
        if dist[ny][nx]==-1:
            dist[ny][nx]=dist[y][x]+1
            que.append([ny,nx])

score=-1
goal=dist[H-1][W-1]
if goal!=-1:
    score=dots-goal-1
print(score)

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



ss=copy.deepcopy(s)
q=deque([[0,0]])
ss[0][0]=0
move=[[1,0],[0,1],[0,-1],[-1,0]]
num=0
t=False
while q:
    num+=1
    for i in range(len(q)):
        b=q.popleft()
        
        if b==[H-1,W-1]:
            t=True
            num-=1
            break
        for m in move:
         
            if 0<=b[0]+m[0]<=H-1 and 0<=b[1]+m[1]<=W-1 and ss[b[0]+m[0]][b[1]+m[1]]=='.':
                ss[b[0]+m[0]][b[1]+m[1]]=num
                q.append([b[0]+m[0],b[1]+m[1]])
    else:
        continue
    break
if not t :
    print('-1')
else:
    x=num
    b=H-1,W-1
    ss[b[0]][b[1]]='
    while x!=0:
        for m in move:
            if 0<=b[0]+m[0]<=H-1 and 0<=b[1]+m[1]<=W-1 and ss[b[0]+m[0]][b[1]+m[1]]==x-1:
                x=x-1
                ss[b[0]+m[0]][b[1]+m[1]]='
                b=b[0]+m[0],b[1]+m[1]
                break
    ans=0
    for h in range(H):
        for w in range(W):
            if ss[h][w]!='
                ans+=1
    print(ans)

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


wall=[]
for h in range(H):
    for w_idx,w in enumerate(list(input())):
        if w == '
            wall.append(W*h+w_idx+1)

path=[_ for _ in range(1,N+1) if _ not in wall]


ad = {}
for n in range(N):
    ad[n+1]=[]
    
for n in range(N):
    n=n+1
    if n not in wall:
        up = n-W
        if up > 0 and up not in wall:
            ad[n].append(up)
            
        down = n+W
        if down <= N and down not in wall:
            ad[n].append(down)
            
        left = n-1
        if n % W != 1 and left not in wall and left > 0:
            ad[n].append(left)
        
        right = n+1
        if n % W != 0 and right not in wall:
            ad[n].append(right)   

from collections import deque
    
color = {}
for n in range(N):
    color[n+1] = -1

depth = {}
for n in range(N):
    depth[n+1] = -1
    
parent = {}
for n in range(N):
    parent[n+1] = -1
    
group = {}
    
group_= 0
for p in path:
    if color[p] != -1: 
        continue
    elif color[p] == -1: 
        start = p
        color[start] = 0
        que = deque([start])
        visit = deque([])
        group_+=1
        group[group_] = [start]

    depth[start] = 0
    while len(que) > 0:
        start = que[0]
        for v in ad[start]:
            if color[v] == -1:
                que.append(v)
                color[v] = 0
                depth[v] = depth[start]+1
                group[group_].append(v)
                parent[v] = start
                
        color[start] = 1
        visit.append(que.popleft())
        
ans_ = {}
for n in range(N):
    ans_[n+1]=1

for w in wall:
    ans_[w]=0

start = N
short_path=[]

while True:
    short_path.append(start)
    start = parent[start]
    if start == 1:
        short_path.append(start)
        for s in short_path:
            ans_[s] = 0
        print(sum(ans_.values()))
        break
        
    if start == -1:
        print(start)
        break

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

maze = []
s_init_cnt = 0
for i in range(H):
    gyo = list(input())
    s_init_cnt += gyo.count('.')
    maze.append(gyo)




direction = [(-1, 0), (0, -1), (1, 0), (0, 1)]
reached = [[-1] * W for i in range(H)]
reached[0][0] = 1
from collections import deque


def bfs():
    d = deque([[0, 0]])
    while len(d) > 0:
        px, py = d.popleft()
        for dx, dy in direction:
            tx = px + dx
            ty = py + dy
            if tx >= H or ty >= W or tx < 0 or ty < 0:
                continue
            if reached[tx][ty] != -1 or maze[tx][ty] == '
                continue
            else:
                reached[tx][ty] = reached[px][py] + 1
                d.append([tx, ty])
bfs()
ans = reached[H-1][W-1]
if ans == -1:
    print(ans)
else:
    ans = s_init_cnt - ans
    print(ans)

Solution (Python):
def main():
	H, W = [int(n) for n in input().split(" ")]
	iniBlack = 0
	S = []
	S.append(["X"] * (W + 2))
	for i in range(H):
		row = list(input())
		iniBlack += row.count("
		S.append(["X"] + row + ["X"])
	S.append(["X"] * (W + 2))

	to_visit = [{"row": 1, "col": 1, "step": 1}]
	checked = [[0] * (W + 2) for i in range(H + 2)]
	checked[1][1] = 1

	while len(to_visit) > 0:
		visiting = to_visit.pop(0)
		r0 = visiting["row"]
		c0 = visiting["col"]
		s0 = visiting["step"]
		for d in [[0, 1], [0, -1], [1, 0], [-1, 0]]:
			r = r0 + d[0]
			c = c0 + d[1]
			if S[r][c] == "." and checked[r][c] == 0:
				to_visit.append({"row": r, "col": c, "step": s0 + 1})
				checked[r][c] = s0 + 1

	if checked[H][W] == 0:
		print(-1)
		return 0
	print(H * W - iniBlack - checked[H][W])

main()

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

H,W = map(int,input().split())
sy, sx = 0,0
gy, gx = H-1,W-1
D = [list(input()) for i in range(H)]
Bs = 0
for i in range(H):
    Bs += D[i].count("

Q = deque()
Q.append((sy,sx))
dist = [[-1]*W for i in range(H)]
dist[sy][sx] = 0
dx = [1,0,-1,0]
dy = [0,-1,0,1]

while Q:
    x,y = Q.popleft()
    for i in range(4):
        nx = x+dx[i]
        ny = y+dy[i]
        if 0<=nx<=W-1 and 0<=ny<=H-1 and D[ny][nx]!="
            Q.append((nx,ny))
            dist[ny][nx] = dist[y][x]+1

print(H*W-Bs-1-dist[gy][gx] if dist[gy][gx]!=-1 else -1)

Solution (Python):



def solve(H, W, s):
    from heapq import heappop, heappush
    blacks = sum(sum(e == "
    hq = [(1, (0, 0))]
    visited = set()
    while hq:
        c, h_w = heappop(hq)
        h, w = h_w
        if h_w in visited:
            continue
        if h_w == (H-1, W-1):
            return H * W - blacks - c
        visited.add(h_w)
        for dh, dw in zip((0, 0, 1, -1), (1, -1, 0, 0)):
            nh, nw = nh_nw = h + dh, w + dw
            if not(0 <= nh < H and 0 <= nw < W):
                continue
            if nh_nw in visited:
                continue
            if s[nh][nw] == "
                continue
            heappush(hq, (c+1, nh_nw))
    return -1


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

def test():
    import doctest
    doctest.testmod()

if __name__ == '__main__':
    
    main()

Solution (Python):
def cal():
    import queue
    h, w = map(int, input().split())
    s = [list(input()) for _ in range(h)]
    cost = [[-1]*w for _ in range(h)]
    INF = float('inf')
    count, ans = 0, INF
    for i in range(h):
        for j in range(w):
            if s[i][j] != '
                cost[i][j] = INF
            else:
                count += 1        
    q = queue.Queue()
    q.put((0, 0, 1))
    while not q.empty():
        c0, c1, c2 = q.get()
        s[c0][c1] = '
        if c0 == h-1 and c1 == w-1:
            return h*w-count-c2
        for i, j in ((1, 0), (-1, 0), (0, 1), (0, -1)):
            x, y = c0+i, c1+j
            if 0 <= x < h and 0 <= y < w:
                if s[x][y] != '
                    cost[x][y] = c2+1
                    q.put((x, y, c2+1))

    return ans

ans = cal()
if ans == float('inf'):
    print(-1)
else:
    print(ans)

Solution (Python):
from collections import deque
h,w=map(int,input().split())
G=[]
for _ in range(h):
  s=input()
  S=[]
  for i in range(w):
    S.append(s[i])
  G.append(S)

si,sj=0,0
gi,gj=h-1,w-1
INF=float('inf')
dist=[[INF for i in range(w)] for j in range(h)]
dist[si][sj]=1
Q=deque()
Q.append((si,sj))
while Q:
  pi,pj=Q.popleft()
  for di,dj in [[-1,0],[1,0],[0,-1],[0,1]]:
    ni,nj=pi+di,pj+dj
    if 0>ni or ni>h-1:
      continue
    if 0>nj or nj>w-1:
      continue
    if G[ni][nj]=='
      continue
    if dist[ni][nj]>dist[pi][pj]+1:
      dist[ni][nj]=dist[pi][pj]+1
      Q.append((ni,nj))
ans=0      
for i in range(h):
  for j in range(w):
    if G[i][j]=='.':
      ans+=1
ans-=dist[gi][gj]
if ans<0:
  print(-1)
else:
  print(ans)

Solution (Python):
H, W = map(int, input().split())
inf = 101
s = [''] * H
cnt = 0
for i in range(H):
	s[i] = input()
	cnt += s[i].count('.')
d = [[inf] * W for i in range(H)]
from collections import deque
queue = deque([[0, 0]])
d[0][0] = 0

while queue:
	x, y = queue.popleft()
	if x+1 == H and y+1 == W:
		break
	dx, dy = [-1, 0, 1, 0], [0, -1, 0, 1]
	for i in range(4):
		nx, ny = x + dx[i], y + dy[i]
		if 0 <= nx and nx < H and 0 <= ny and ny < W and s[nx][ny] != '
			queue.append([nx, ny])
			d[nx][ny] = d[x][y] + 1

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

Solution (Python):
import collections
import math


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

c=[list(str(input())) for i in range(H)]

d=[[0 for j in range(W)]for i in range(H)]
inf=10**6
ans=0
for i in range(H):
    for j in range(W):
        if c[i][j]=='
            d[i][j]=-1
        else:
            d[i][j]=inf
            ans+=1


d[0][0]=0
queue=collections.deque([[0,0]])
gy,gx=H-1,W-1

moves=[[1,0],[-1,0],[0,1],[0,-1]]

flag=False
while len(queue)>0:
    now=queue.popleft()
    for i in range(4):
        ny=now[0]+moves[i][0]
        nx=now[1]+moves[i][1]
        
        if 0<=ny and ny<H and 0<=nx and nx<W and c[ny][nx]=='.' and d[ny][nx]==inf:
            d[ny][nx]=d[now[0]][now[1]]+1
            queue.append([ny,nx])
            if ny==gy and nx==gx:
                print(ans-d[ny][nx]-1)
                exit()
print(-1)

Solution (Python):

def main():
    from collections import deque

    H, W = map(int, input().split())
    S = []
    num_path = 0
    for _ in range(H):
        s = input()
        num_path += s.count('.')
        S.append(s)

    move = ((0, 1), (0, -1), (1, 0), (-1, 0))
    distance = [[1] * W for _ in range(H)]
    queue = deque([(0, 0)])
    while queue:
        y, x = queue.popleft()
        if y == H - 1 and x == W - 1:
            break
        for dy, dx in move:
            ny = y + dy
            nx = x + dx
            if (1
                    and 0 <= ny < H
                    and 0 <= nx < W
                    and distance[ny][nx] == 1
                    and S[ny][nx] == '.'):
                queue.append((ny, nx))
                distance[ny][nx] = distance[y][x] + 1
    if distance[H - 1][W - 1] == 1:
        print(-1)
    else:
        print(num_path - distance[H - 1][W - 1])


if __name__ == '__main__':
    main()

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

Q = deque([[0,0]])
dist = [[-1] * W for _ in range(H)]
dist[0][0] = 0

while Q:
    h, w = Q.popleft()

    for nh, nw in [[h+1,w],[h-1,w],[h,w-1],[h,w+1]]:
        if 0 <= nh < H and 0 <= nw < W and S[nh][nw] == "." and dist[nh][nw] == -1:
            dist[nh][nw] = dist[h][w] + 1
            Q.append([nh,nw])

if dist[H-1][W-1] == -1:
    print(-1)
else:
    ans = 0
    for s in S: ans += s.count(".")
    print(ans - dist[H-1][W-1] - 1)

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

Q = deque([[0,0]])
dist = [[-1] * W for _ in range(H)]
dist[0][0] = 0

while Q:
    h, w = Q.popleft()

    for nh, nw in [[h+1,w],[h-1,w],[h,w-1],[h,w+1]]:
        if 0 <= nh < H and 0 <= nw < W and S[nh][nw] == "." and dist[nh][nw] == -1:
            dist[nh][nw] = dist[h][w] + 1
            Q.append([nh,nw])

if dist[H-1][W-1] == -1:
    print(-1)
else:
    ans = 0
    for s in S: ans += s.count(".")
    print(ans - dist[H-1][W-1] - 1)

Solution (Python):
def abc088d_grid_repainting():
    import heapq
    h, w = map(int, input().split())
    maze = []
    cnt = h * w
    for _ in range(h):
        s = input()
        maze.append(s)
        cnt -= s.count('
    q = [(1, 0, 0)]
    heapq.heapify(q)
    check = [[False] * w for _ in range(h)]
    while len(q) != 0:
        dis, x, y = heapq.heappop(q)
        if (x, y) == (h - 1, w - 1):
            print(cnt - dis)
            return
        for dx, dy in zip([0, 0, 1, -1], [1, -1, 0, 0]):
            if 0 <= x + dx < h and 0 <= y + dy < w and maze[x + dx][y + dy] != '
                check[x + dx][y + dy] = True
                heapq.heappush(q, (dis+1, x + dx, y + dy))
    print('-1')
abc088d_grid_repainting()

Solution (Python):
import queue
H , W = list(map(int, input().split()))
S = [input() for _ in range(H)]
Sum = 0
for i in range(H):
  for j in range(W):
    Sum += (S[i][j] == '
start = [1, 1, 1]
visited = [[0] * W for _ in range(H)]
visited[0][0] = 1
Q = queue.Queue()
Q.put(start)
now = start
while(now[:2] != [H, W] and not Q.empty()):
  now = Q.get()
  for i in range(2):
    for j in range(2):
      h = now[0] + ((-1) ** i + (-1) ** j) // 2
      w = now[1] + ((-1) ** i - (-1) ** j) // 2
      if(1 <= h and h <= H and 1 <= w and w <= W and visited[h - 1][w - 1] == 0 and S[h - 1][w - 1] == '.'):
        visited[h - 1][w - 1] = 1
        Q.put([h, w, now[2] + 1])
if(now[:2] == [H, W]):
  print(H * W - Sum - now[2])
else:
  print(-1)

Solution (Python):
import sys
h,w=map(int,input().split())
ss=[list(input()) for i in range(h)]
num=0
for i in range(h):
    num+=ss[i].count('.')

visited=[[0 for i in range(w)] for j in range(h)]
queue=[]
queue.append([0,0])
ss[0][0]='fin'
dy=[1,0,-1,0]
dx=[0,1,0,-1]


while len(queue)>0:
    now=queue.pop(0)
    for i in range(4):
        x= now[1]+dx[i]
        y= now[0]+dy[i]
        if 0<=x<w and 0<=y<h :
            if ss[y][x]=='.' and visited[y][x]==0:
                visited[y][x]=visited[now[0]][now[1]]+1
                queue.append([y,x])
            if x==w-1 and y==h-1:
                print(num-visited[y][x]-1)
                sys.exit()
print(-1)

Solution (Python):




from collections import deque


H, W = map(int, input().split())
grid = [list(input()) for _ in range(H)] 
visited = [[-1] * W for _ in range(H)]
moves = [(1, 0), (0, 1), (-1, 0), (0, -1)]

q = deque()
q.append((0, 0))
visited[0][0] = 0

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

    for dy, dx in moves:
        moved_y = y + dy
        moved_x = x + dx

        if moved_y < 0 or H-1 < moved_y or moved_x < 0 or W-1 < moved_x:
            continue
        if grid[moved_y][moved_x] == '
            continue
        if visited[moved_y][moved_x] != -1:
            continue

        visited[moved_y][moved_x] = visited[y][x] + 1
        q.append((moved_y, moved_x))

min_route = visited[H-1][W-1]

if min_route == -1:
    answer = -1
else:
    total_white = 0
    for row in grid:
        total_white += row.count('.')

    answer = total_white - min_route - 1

print(answer)

Solution (Python):
from queue import Queue
dx = [1, 0, -1, 0]
dy = [0, 1, 0, -1]

H, W = map(int, input().split())
S = [input() for _ in range(H)]
dist = [[-1] * W for _ in range(H)]
que = Queue()


dist[0][0] = 0
que.put((0, 0))


while not que.empty():
    x, y = que.get()
    for dir in range(4):
        x2, y2 = x + dx[dir], y + dy[dir]
        if x2 < 0 or x2 >= H or y2 < 0 or y2 >= W or S[x2][y2] == '
            continue
        if dist[x2][y2] != -1:
            continue
        dist[x2][y2] = dist[x][y] + 1
        que.put((x2, y2))


white = sum(sum(1 if S[x][y] == '.' else 0 for y in range(W)) for x in range(H))


print(white - dist[H-1][W-1] - 1 if dist[H-1][W-1] != -1 else -1)

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

s = [[]*w for _ in range(h)]
white =0
for i in range(h):
    t = input()
    for j in range(w):
        if t[j] == ".":
            white += 1
            s[i].append(10**5)
        elif t[j] == "
            s[i].append(t[j])
now = [0,0]
steps =[]
steps.append(now)
direction = []
s[0][0] =0
a = [2]
while len(steps) >0:
    now = copy.copy(steps[0])
    if s[now[0]][now[1]] =="
        continue
    for k in [[0,1],[1,0],[-1,0],[0,-1]]:
        now = copy.copy(steps[0])
        if now[0] + k[0] >=0 and now[0] + k[0] < h:
            now[0] += k[0]
            if now[1] + k[1] >=0 and now[1] + k[1] <w:
                now[1] += k[1]
                if s[now[0]][now[1]] == 10**5:
                    if not [now[0],now[1]] in steps:
                        steps.append([now[0],now[1]])
            else:
                continue
        else:
            continue
    
    
    
    if s[steps[0][0]][steps[0][1]] >10**4:
        direction =[]
        for l in [[0,1],[1,0],[-1,0],[0,-1]]:
            if steps[0][0]+l[0]>=0 and steps[0][0]+l[0]<h and steps[0][1]+l[1]< w and steps[0][1]+l[1] >=0 and s[steps[0][0]+l[0]][steps[0][1]+l[1]] != "
                s[steps[0][0]][steps[0][1]]=min(s[steps[0][0]+l[0]][steps[0][1]+l[1]]+1,s[steps[0][0]][steps[0][1]])
    steps.pop(0)
if s[h-1][w-1] == "
    print(-1)
else:
    print(white-1 - s[h-1][w-1])

Solution (Python):






from collections import deque





H,W = map(int, input().split())
grid = [list("
b_cnt = 0
for _ in range(H):
    tmp = list(input())
    grid.append(["
grid.append(list("





grid[1][1] = 1
q = deque([[1,1]])
move = [
    [1,0],[-1,0],[0,1],[0,-1]
]
while q:
    x,y = q.popleft()
    for dx,dy in move:
        if grid[x+dx][y+dy] == ".":
            grid[x+dx][y+dy] = grid[x][y]+1
            q.append([x+dx,y+dy])
if grid[H][W] == ".":
    print(-1)
else:
    print((H+2)*(W+2) - sum(g.count("

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

sq=[list(input()) for i in range(H)]

pos=[[0,0,0]]
g=True

while pos!=[]:
    y,x,depth=pos.pop(0)

    if y==H-1 and x==W-1:
        g=False
        break
    
    if x-1>=0:
        if sq[y][x-1]==".":
            pos.append([y,x-1,depth+1])
            sq[y][x-1]="!"
    if x+1<=W-1:
        if sq[y][x+1]==".":
            pos.append([y,x+1,depth+1])
            sq[y][x+1]="!"
    if y-1>=0:
        if sq[y-1][x]==".":
            pos.append([y-1,x,depth+1])
            sq[y-1][x]="!"
    if y+1<=H-1:
        if sq[y+1][x]==".":
            pos.append([y+1,x,depth+1])

if g==True:
    print(-1)
else:
    temp=0
    for k in range(H):
        for m in range(W):
            if sq[k][m]=="
                temp+=1


    print(H*W-temp-depth-1)

Solution (Python):
from collections import deque
import sys

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

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

d=deque([(0,0)])
distance=[[-1]*W for _ in range(H)]
distance[0][0]=0
goal_distance=0

while d:
  h,w=d.popleft()
  if h==H-1 and w==W-1:
    goal_distance=distance[h][w]
    break
  
  if h-1>=0 and S[h-1][w]=='.':
    d.append((h-1,w))
    distance[h-1][w]=distance[h][w]+1
    S[h-1][w]='
    
  if h+1<=H-1 and S[h+1][w]=='.':
    d.append((h+1,w))
    distance[h+1][w]=distance[h][w]+1
    S[h+1][w]='
    
  if w-1>=0 and S[h][w-1]=='.':
    d.append((h,w-1))
    distance[h][w-1]=distance[h][w]+1
    S[h][w-1]='
    
  if w+1<=W-1 and S[h][w+1]=='.':
    d.append((h,w+1))
    distance[h][w+1]=distance[h][w]+1
    S[h][w+1]='
else:
  if distance[H-1][W-1]==-1:
    print(-1)
    sys.exit()

print(count-(goal_distance+1))

Solution (Python):
from collections import deque
import sys
h,w = map(int,input().split())
mp = [list(input()) for _ in range(h)]

visited = [[0]*w for _ in range(h)]

dxdy = [[1,0],[0,1],[-1,0],[0,-1]]

queue = deque()
queue.append([0,0,1])
visited[0][0]=1

while queue:
    x,y,d = queue.popleft()
    for dx,dy in dxdy:
        nx,ny = x+dx,y+dy
        if -1<nx<h and -1<ny<w and visited[nx][ny]==0 and mp[nx][ny]!="
            visited[nx][ny]=d+1
            queue.append([nx,ny,d+1])
            
            

if visited[-1][-1]==0:
    print(-1)
    sys.exit()

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

print(cnt-visited[-1][-1])

Solution (Python):
import bisect,collections,copy,itertools,math,string
import sys
def I(): return int(sys.stdin.readline().rstrip())
def LI(): return list(map(int,sys.stdin.readline().rstrip().split()))
def S(): return sys.stdin.readline().rstrip()
def LS(): return list(sys.stdin.readline().rstrip().split())
def main():
    h,w = LI()
    board = [["
    num = 0
    for _ in range(h):
        line = ["
        num += line.count(".")
        board.append(line)
    board.append(["
    
    queue = collections.deque([(1,1)])
    explored = {(1,1)}
    nbh = [[0,1],[0,-1],[1,0],[-1,0]]
    level = 0
    cnt = 0
    
    while len(queue)!=0 and (h,w) not in explored:
        if cnt==0:
            level+=1
            cnt=len(queue)
        nxt = queue.popleft()
        for dx,dy in nbh:
            ex = (nxt[0]+dx, nxt[1]+dy)
            if board[ex[0]][ex[1]] == ".":
                if ex not in explored:
                    explored.add(ex)
                    queue.append(ex)
        cnt -= 1
    ans = num-(level+1) if (h,w) in explored else -1
    print(ans)
main()

Solution (Python):
from collections import deque
h, w = map(int, input().split())
field = [input() for _ in range(h)]
d = [(1, 0), (-1, 0), (0, 1), (0, -1)]
white = 0
for i in range(h):
    white += field[i].count(".")
cnt = [[-1]*w for _ in range(h)]
cnt[0][0] = 0
q = deque([[0, 0]])

while q:
    y, x = q.pop()
    for dy, dx in d:
        ny = y + dy
        nx = x + dx
        if 0 <= ny < h and 0 <= nx < w and field[ny][nx] == "." and cnt[ny][nx] < 0:
            cnt[ny][nx] = cnt[y][x] + 1
            q.appendleft([ny, nx])
        if ny == h-1 and nx == w-1:
            print(white - cnt[h-1][w-1] - 1)
            exit()

print(-1)

Solution (Python):
from collections import deque

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

s = 0
for c in S:
    s += c.count('.')

que = deque()
dist = [[-1 for j in range(W)] for i in range(H)]
dist[0][0] = 0
st = (0, 0)
que.append(st)
dydx = [(1, 0), (0, 1), (-1, 0), (0, -1)]

while que:
    p, q = que.popleft()

    for dy, dx in dydx:
        if 0 <= p+dy and p+dy < H and 0 <= q+dx and q+dx < W:
            if dist[p+dy][q+dx] != -1 or S[p+dy][q+dx] != '.':
                continue

            dist[p+dy][q+dx] = dist[p][q] + 1
            que.append((p+dy, q+dx))

if dist[H-1][W-1] == -1:
    print(-1)
else:
    print(s-dist[H-1][W-1]-1)

Solution (Python):
from collections import *
H,W = map(int,input().split())
S = [(W+2)*["
S[1][1] = 1
Q = deque([[1,1]])
D = [[1,0],[-1,0],[0,1],[0,-1]]

while Q:
  x,y = Q.popleft()
  for dx,dy in D:
    if S[x+dx][y+dy]==".":
      S[x+dx][y+dy] = S[x][y]+1
      Q.append([x+dx,y+dy])

if S[H][W]==".":
  print(-1)
else:
  print((H+2)*(W+2)-sum(s.count("

Solution (Python):
from collections import *
H,W = map(int,input().split())
S = [input() for h in range(H)]
V = [W*[0] for h in range(H)]
V[0][0] = 1
Q = deque([(0,0)])
while Q:
  x,y = Q.popleft()
  for dx,dy in ((-1,0),(0,-1),(1,0),(0,1)):
    if 0<=x+dx<H and 0<=y+dy<W and V[x+dx][y+dy]==0 and S[x+dx][y+dy]==".":
      V[x+dx][y+dy] = V[x][y]+1
      Q.append((x+dx,y+dy))

if V[H-1][W-1]==0:
  print(-1)
else:
  print(H*W-sum(s.count("

Solution (Python):
H,W=map(int,input().split())
sq=[list(input()) for i in range(H)]
ans=False
c=H*W
pos=[[0,0,0]]

while pos!=[]:
    y,x,depth=pos.pop(0)

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

    if 0<=x+1<=W-1:
        if sq[y][x+1]==".":
            pos.append([y,x+1,depth+1])
            sq[y][x+1]="!"
            
    if 0<=x-1<=W-1:
        if sq[y][x-1]==".":
            pos.append([y,x-1,depth+1])
            sq[y][x-1]="!"
            
    if 0<=y+1<=H-1:
        if sq[y+1][x]==".":
            pos.append([y+1,x,depth+1])
            sq[y+1][x]="!"
            
    if 0<=y-1<=H-1:
        if sq[y-1][x]==".":
            pos.append([y-1,x,depth+1])
            sq[y-1][x]="!"
    
    
for j in range(H):
    for k in range(W):
        if sq[j][k]=="
            c-=1

if ans==True:
    print(c-depth-1)
else:
    print(-1)

Solution (Python):
from collections import deque
h,w=map(int,input().split())
queue=deque()
s=[list(input()) for _ in range(h)]
seen=[[False]*w for _ in range(h)]
queue.append([0,0])
ans=[[1000000000]*w for _ in range(h)]
seen[0][0]=True
ans[0][0]=1
for i in range(h*w*10):
    if len(queue)==0:
        break
    cnt=queue.popleft()
    if cnt[0]!=0:
        if seen[cnt[0]-1][cnt[1]]==False and s[cnt[0]-1][cnt[1]]==".":
            queue.append([cnt[0]-1,cnt[1]])
            ans[cnt[0]-1][cnt[1]]=ans[cnt[0]][cnt[1]]+1
            seen[cnt[0]-1][cnt[1]]=True
    if cnt[1]!=0:
        if seen[cnt[0]][cnt[1]-1]==False and s[cnt[0]][cnt[1]-1]==".":
            queue.append([cnt[0],cnt[1]-1])
            ans[cnt[0]][cnt[1]-1]=ans[cnt[0]][cnt[1]]+1
            seen[cnt[0]][cnt[1]-1]=True
    if cnt[0]!=h-1:
        if seen[cnt[0]+1][cnt[1]]==False and s[cnt[0]+1][cnt[1]]==".":
            queue.append([cnt[0]+1,cnt[1]])
            ans[cnt[0]+1][cnt[1]]=ans[cnt[0]][cnt[1]]+1
            seen[cnt[0]+1][cnt[1]]=True
    if cnt[1]!=w-1:
        if seen[cnt[0]][cnt[1]+1]==False and s[cnt[0]][cnt[1]+1]==".":
            queue.append([cnt[0],cnt[1]+1])
            ans[cnt[0]][cnt[1]+1]=ans[cnt[0]][cnt[1]]+1
            seen[cnt[0]][cnt[1]+1]=True
cnt2=0
for i in range(h):
    for j in range(w):
        if s[i][j]==".":
            cnt2+=1
if seen[-1][-1]==False:
    print(-1)
else:
    print(cnt2-ans[-1][-1])

Solution (Python):
import sys
input = sys.stdin.buffer.readline




def RD(): return input().rstrip().decode()
def II(): return int(input())
def FI(): return float(input())
def MI(): return map(int,input().split())
def MF(): return map(float,input().split())
def LI(): return list(map(int,input().split()))
def LF(): return list(map(float,input().split()))
def TI(): return tuple(map(int,input().split()))


from collections import deque

def main():
	h,w=MI()
	G=[]
	G+=["
	for _ in range(h):
		G+=["
	G+=["

	cnt=G.count(".")


	Q=deque()
	Q.append([w+3,1])
	G[w+3]=1

	while Q:
		now,d=Q.popleft()
		for i in [1,-1,w+2,-w-2]:
			if G[now+i]==".":
				G[now+i]=d+1
				Q.append([now+i,d+1])

	ans=-1
	if G[(w+2)*(h+2)-(w+4)]!=".":
		ans=cnt-G[(w+2)*(h+2)-(w+4)]

	print(ans)












if __name__ == "__main__":
	main()

Solution (Python):
from collections import deque


def bfs(start, goal):
    q = deque([[start]])
    visited = set()
    while q:
        path = q.popleft()
        i, j = path[-1]
        if (i, j) == goal:
            return path
        for di, dj in [(1, 0), (-1, 0), (0, 1), (0, -1)]:
            ni, nj = i + di, j + dj
            if not (0 <= ni < H and 0 <= nj < W and field[ni][nj] == "."):
                continue
            if (ni, nj) not in visited:
                q.append(path + [(ni, nj)])
                visited.add((ni, nj))
    return []


H, W = map(int, input().split())
field = [input() for _ in range(H)]
shortest_path = bfs((0, 0), (H - 1, W - 1))
if shortest_path:
    print(sum(v == "." for row in field for v in row) - len(shortest_path))
else:
    print(-1)

Solution (Python):
t,*g=open(0);h,w=map(int,t.split());v=[[0]*w for _ in range(h)];v[0][0]=1;q=[(0,0)]
while q:
	a,b=q.pop(0)
	for c,d in((-1,0),(0,-1),(1,0),(0,1)):
		x=a+c;y=b+d
		if w>x>=0<=y<h and v[y][x]<1 and g[y][x]==".":q+=[(x,y)];v[y][x]=v[b][a]+1
t=v[-1][-1];print((-1,sum(c.count(".")for c in g)-t)[t>0])

Solution (Python):
from collections import deque


dh = [-1, 0, 1, 0]
dw = [0, 1, 0, -1]


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



def count_white():
    res = 0
    for i in range(H):
        for j in range(W):
            if G[i][j] == '.':
                res += 1
    return res



def minimum_step():
    dist = [[0] * W for _ in range(H)]
    dist[0][0] = 1
    que = deque([[0, 0]])

    
    while que:
        h, w = que.popleft()
        for i in range(4):
            nh = h + dh[i]
            nw = w + dw[i]
            if nh < 0 or nw < 0 or nh >= H or nw >= W:
                continue
            if G[nh][nw] == '
                continue
            if dist[nh][nw]:
                continue
            dist[nh][nw] = dist[h][w] + 1
            que.append([nh, nw])
    return dist[H - 1][W - 1]


def main():
    step = minimum_step()
    print(count_white() - step if step else -1)

if __name__ == "__main__":
    main()

Solution (Python):
from collections import deque


dh = [-1, 0, 1, 0]
dw = [0, 1, 0, -1]


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



def count_black():
    res = 0
    for i in range(H):
        for j in range(W):
            if G[i][j] == '
                res += 1
    return res



def minimum_step():
    dist = [[0] * W for _ in range(H)]
    dist[0][0] = 1
    que = deque([[0, 0]])

    
    while que:
        h, w = que.popleft()
        for i in range(4):
            nh = h + dh[i]
            nw = w + dw[i]
            if nh < 0 or nw < 0 or nh >= H or nw >= W:
                continue
            if G[nh][nw] == '
                continue
            if dist[nh][nw]:
                continue
            dist[nh][nw] = dist[h][w] + 1
            que.append([nh, nw])
    return dist[H - 1][W - 1]


def main():
    step = minimum_step()
    print(H * W - step - count_black() if step else -1)

if __name__ == "__main__":
    main()