Problem:
 Score: 400 points    Problem statement  We have an H \times W grid whose squares are painted black or white. The square at the i -th row from the top and the j -th column from the left is denoted as (i, j) . Snuke would like to play the following game on this grid. At the beginning of the game, there is a character called Kenus at square (1, 1) . The player repeatedly moves Kenus up, down, left or right by one square. The game is completed when Kenus reaches square (H, W) passing only white squares. Before Snuke starts the game, he can change the color of some of the white squares to black. However, he cannot change the color of square (1, 1) and (H, W) . Also, changes of color must all be carried out before the beginning of the game. When the game is completed, Snuke's score will be the number of times he changed the color of a square before the beginning of the game. Find the maximum possible score that Snuke can achieve, or print -1 if the game cannot be completed, that is, Kenus can never reach square (H, W) regardless of how Snuke changes the color of the squares.  The color of the squares are given to you as characters s_{i, j} . If square (i, j) is initially painted by white, s_{i, j} is . ; if square (i, j) is initially painted by black, s_{i, j} is # .      Constraints   H is an integer between 2 and 50 (inclusive).  W is an integer between 2 and 50 (inclusive).  s_{i, j} is . or #  (1 \leq i \leq H, 1 \leq j \leq W) .  s_{1, 1} and s_{H, W} are . .         Input  Input is given from Standard Input in the following format:  H  W  s_{1, 1}s_{1, 2}s_{1, 3} ... s_{1, W}  s_{2, 1}s_{2, 2}s_{2, 3} ... s_{2, W}  :  :  s_{H, 1}s_{H, 2}s_{H, 3} ... s_{H, W}       Output  Print the maximum possible score that Snuke can achieve, or print -1 if the game cannot be completed.        Sample Input 1 3 3
..#
#..
...      Sample Output 1 2  The score 2 can be achieved by changing the color of squares as follows:        Sample Input 2 10 37
.....................................
...#...####...####..###...###...###..
..#.#..#...#.##....#...#.#...#.#...#.
..#.#..#...#.#.....#...#.#...#.#...#.
.#...#.#..##.#.....#...#.#.###.#.###.
.#####.####..#.....#...#..##....##...
.#...#.#...#.#.....#...#.#...#.#...#.
.#...#.#...#.##....#...#.#...#.#...#.
.#...#.####...####..###...###...###..
.....................................      Sample Output 2 209

Solution (Python):
from collections import deque

def bfs(grid, sy, sx, target, wall):
    grid[sy][sx] = wall
    queue = deque([])
    queue.append([sy, sx, 1])
    dxy = [(1,0), (-1,0), (0,1), (0,-1)]
    while queue:
        y,x,cnt = queue.popleft()
        for dy, dx in dxy:
            y_,x_ = y+dy,x+dx
            if [y_, x_] == target:
                return cnt+1
            if grid[y_][x_] == wall:
                continue
            queue.append([y_,x_,cnt+1])
            grid[y_][x_] = wall
    return 0

H,W = map(int, input().split())
wall = '
edges = [wall] * (W+2)
grid = [edges]
b_cnt = 0
for i in range(H):
    s = input()
    grid.append([wall] + list(s) + [wall])
    b_cnt += s.count(wall)
grid.append(edges)
cost = bfs(grid, 1,1, [H,W], wall)
print(H*W - b_cnt - cost if cost else -1)

Solution (Python):
from collections import deque
h, w = map(int, input().split())
maze = []
total_white_square = 0
for i in range(h):
    row = list(input())
    total_white_square += row.count('.')
    maze.append(row)
visited = [[False for i in range(w)] for j in range(h)]
queue = deque()
start = (0, 0)
end = (h - 1, w - 1)
queue.append((start, 1))
visited[0][0] = True
num_white_row = 0
while len(queue) > 0:
    curr, time = queue.popleft()
    if curr == end:
        num_white_row = time
        break
    x, y = curr
    if x - 1 >= 0 and not visited[x - 1][y] and maze[x - 1][y] == '.':
        visited[x - 1][y] = True
        queue.append(((x - 1, y), time + 1))
    if x + 1 <= h - 1 and not visited[x + 1][y] and maze[x + 1][y] == '.':
        visited[x + 1][y] = True
        queue.append(((x + 1, y), time + 1))
    if y - 1 >= 0 and not visited[x][y - 1] and maze[x][y - 1] == '.':
        visited[x][y - 1] = True
        queue.append(((x, y - 1), time + 1))
    if y + 1 <= w - 1 and not visited[x][y + 1] and maze[x][y + 1] == '.':
        visited[x][y + 1] = True
        queue.append(((x, y + 1), time + 1))
if num_white_row != 0:
    print(total_white_square - num_white_row)
else:
    print(-1)

Solution (Python):
from collections import deque
h,w=map(lambda x: int(x), input().split())
s=[[] for _ in range(h)]
black=0
for i in range(h):
    s[i]=input()
    black+=s[i].count('

dist=[[-1 for _ in range(w)] for _ in range(h)]
que = deque([(0, 0)])
dist[0][0]=0
while que:
    y, x=que.popleft()
    for y1, x1 in [(y-1, x), (y+1, x), (y, x-1), (y, x+1)]:
        if y1<0 or y1>h-1 or x1<0 or x1>w-1:
            continue
        if s[y1][x1]=='
            continue
        if dist[y1][x1]!=-1:
            continue
        dist[y1][x1]=dist[y][x]+1
        que.append((y1,x1))

if dist[h-1][w-1]==-1:
    print(-1)
else:
    print(h*w-black-dist[h-1][w-1]-1)

Solution (Python):
import sys
import collections


def solve():
    input = sys.stdin.readline
    mod = 10 ** 9 + 7
    h, w = list(map(int, input().rstrip('\n').split()))
    s = []
    b_cnt = 0
    for i in range(h):
        st = list(str(input().rstrip('\n')))
        s.append(st)
        b_cnt += st.count("

    ql = [[0, 0, 0]]
    ql = collections.deque(ql)
    fq = collections.defaultdict(int)
    fq[0, 0] = 1
    m_cost = 10 ** 10
    while True:
        if len(ql) != 0:
            cost, x, y = ql.popleft()
            if x == h - 1 and y == w - 1:
                m_cost = min(m_cost, cost)
            for x, y in [[x + 1, y], [x - 1, y], [x, y + 1], [x, y - 1]]:
                if 0 <= x < h and 0 <= y < w:
                    if (x, y) not in fq and s[x][y] == ".":
                        ql.append([cost+1, x, y])
                        fq[x, y] += 1
        else:
            break
    if m_cost == 10 ** 10:
        print(-1)
    else:
        print(h * w - b_cnt - m_cost - 1)


if __name__ == '__main__':
    solve()

Solution (Python):
from collections import deque

def bfs(maze,visited,sy,sx,gy,gx):
    Step = ([1,0],[0,1],[-1,0],[0,-1])
    
    que = deque([[sx,sy]])
    visited[sx][sy] = 1
    
    while que:
        y,x = que.popleft()
        if [y,x] == [gy,gx]:
            return visited[y][x]
        for j,k in Step:
            ny,nx = y+j , x+k
            if 0 <= ny <= gy and 0 <= nx <= gx:
                if maze[ny][nx] == '.' and visited[ny][nx] == INF:
                    visited[ny][nx] = visited[y][x] + 1
                    que.append([ny,nx])


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

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

INF = 10**5
visited = [[INF]*w for _ in range(h)]

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

minStep = bfs(maze,visited,sy,sx,gy,gx)
print(cntSharp - minStep if visited[gy][gx] != INF else -1)

Solution (Python):
n,m=map(int,input().split())
mat=[]
blk=0 
for i in range(n):
    mat.append(list(input()))
for i in range(n):
    for j in range(m):
        if mat[i][j]=='.':
            mat[i][j]=0 
        else:
            mat[i][j]=1 
            blk+=1 
vis=[[0 for j in range(m)]for i in range(n)]
dist=[[-1 for j in range(m)]for i in range(n)]
q=[[0,0]]
dx=[0,0,1,-1]
dy=[-1,1,0,0]
if mat[0][0] or mat[n-1][m-1]:
    print(-1)
    exit()
dist[0][0]=0 
while q: 
    t=q.pop(0)
    x=t[0]
    y=t[1]
    for i in range(4):
        if 0<=x+dx[i]<n and 0<=y+dy[i]<m and vis[x+dx[i]][y+dy[i]]==0 and mat[x+dx[i]][y+dy[i]]==0:
            vis[x+dx[i]][y+dy[i]]=1 
            q.append([x+dx[i],y+dy[i]])
            dist[x+dx[i]][y+dy[i]]=dist[x][y]+1 
if not vis[n-1][m-1]:
    print(-1)
    exit()
print(n*m-dist[n-1][m-1]-blk-1)

Solution (Python):
from collections import deque

H , W = map(int,input().split())
maze = []
white_cnt = -1
for _ in range(H):
    row = list(input())
    white_cnt += row.count(".")
    maze.append(row)

def bfs(sy,sx,gy,gx , ma):
    dx = [0,1,0,-1]
    dy = [1,0,-1,0]
    score = [[-1 for _ in range(W)] for _ in range(H)]
    score[sy][sx] = 0
    q = deque()
    q.append([sy,sx])
    while q:
        now_y , now_x = q.popleft()
        for i in range(4):
            next_y , next_x = now_y + dy[i] , now_x + dx[i]
            if 0 <= next_y and next_y < H and 0 <= next_x and next_x < W and score[next_y][next_x] == -1 and ma[next_y][next_x] == ".":
                q.append([next_y,next_x])
                score[next_y][next_x] = score[now_y][now_x] + 1
    return score[gy][gx]


min_distance = bfs(0 , 0,H - 1,W - 1 , maze)
if min_distance == -1:
    print(min_distance)
else:
    print(white_cnt - min_distance)

Solution (Python):
from collections import deque
h,w = map(int,input().split())
list1 = [list(input()) for i in range(h) ]
visited = [[-1]*w for i in range(h)]
black_count = 0
for i in range(h):
	black_count += list1[i].count("
def bfs(maze, visited, sy, sx, gy, gx):
	queue = deque([[sy, sx]])
	visited[sy][sx] = 0
	while queue:
		y, x = queue.popleft()
		if [y, x] == [gy, gx]:
			return visited[y][x]
		for j, k in ([1, 0], [-1, 0], [0, 1], [0, -1]):
			new_y, new_x = y+j, x+k
			if 0 <= new_y < h and \
				0 <= new_x < w and\
				maze[new_y][new_x] == "." and \
				visited[new_y][new_x] == -1:
				
				visited[new_y][new_x] = visited[y][x] + 1
				queue.append([new_y, new_x])
	return -1

shortest = bfs(list1,visited,0,0,h-1,w-1)
if shortest == -1:
	print(-1)
	exit()
print(h*w - black_count - shortest-1)

Solution (Python):
r,c=map(int,input().split())
meiro=[list(input()) for i in range(r)]

white=0
for i in range(r):
    for j in range(c):
        if meiro[i][j]==".":
            white+=1

for i in range(r):
    meiro[i].insert(c,"
    meiro[i].insert(0,"
meiro.insert(0,["
meiro.append(["

idou=[[0,1],[0,-1],[1,0],[-1,0]]
tesuu=[[-1]*(c+2) for i in range(r+2)]
from collections import deque
tesuu[1][1]=1

quest=deque([[1,1]])
while len(quest)!=0:
    see=quest.popleft()
    for i in idou:
        if meiro[see[0]+i[0]][see[1]+i[1]]=="
            continue
        if tesuu[see[0]+i[0]][see[1]+i[1]]!=-1:
            continue
        quest.append([see[0]+i[0],see[1]+i[1]])
        tesuu[see[0]+i[0]][see[1]+i[1]]=tesuu[see[0]][see[1]]+1


gy=r;gx=c
if tesuu[gy][gx]==-1:
    print(-1)
else:
    print(white-tesuu[gy][gx])

Solution (Python):
from collections import deque
H, W = map(int, input().split())
S = []
w = 0
for i in range(H):
    s = input()
    w += s.count(".")
    S.append(list(s))

Q = deque([(0, 0, 0)])
ans = float("inf")
flag = False
while Q:
    i, j, n = Q.popleft()
    if i == H-1 and j == W-1:
        flag = True
        ans = min(ans, n)
    if S[i][j] == ".":
        S[i][j] = "
        for dx, dy in [(1, 0), (0, 1), (-1, 0), (0, -1)]:
            if 0 <= i + dx < H and 0 <= j + dy < W:
                Q.append((i+dx, j+dy, n+1))
if flag:
    print((w-2)-(ans-1))
else:
    print(-1)

Solution (Python):
from collections import deque

H, W = map(int, input().split())
sy = 0
sx = 0
gy = H-1
gx = W-1
c = []
d = [[-1 for i in range(W)] for j in range(H)]
d[sy][sx] = 0
cnt=0
for i in range(H):
	c.append(input())
for j in range(H):
  cnt=cnt+c[j].count(".")

dirr = [[1, 0], [0, 1], [-1, 0], [0, -1]]
q = deque()
q.append([sy, sx, 0])
while len(q) != 0:
	y, x, w = q[0]
	if y == gy and x == gx:
		break

	for i in range(4):
		ny, nx = y + dirr[i][0], x + dirr[i][1]
		if ny>=0 and nx>=0 and ny<H and nx<W and d[ny][nx] == -1 and c[ny][nx] != "
			q.append([ny, nx, w + 1])
			d[ny][nx] = w + 1

	q.popleft()

if d[gy][gx]==-1:
  print(-1)
else:
  print(cnt-w-1)

Solution (Python):

from collections import deque

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

    for s in S:
        for ss in s:
            if ss == ".":
                white_count+=1

    vector = [[1,0],[-1,0],[0,-1],[0,1]]
    min_distance = [[float('inf')]*W for _ in range(H)]
    queue = deque([[0,0]])
    min_distance[0][0] = 0

    while queue:
        q = queue.popleft()
        for v in vector:
            nqy = q[0]+v[0]
            nqx = q[1]+v[1]

            if nqx>=0 and nqy>=0 and nqx<=W-1 and nqy<=H-1 and min_distance[nqy][nqx]==float('inf') and S[nqy][nqx]!="
                queue.append([nqy,nqx])
                min_distance[nqy][nqx]=min_distance[q[0]][q[1]]+1

    if min_distance[H-1][W-1] == float('inf'):
        print(-1)
    else:
        print(white_count - min_distance[H-1][W-1]-1)



if __name__ == '__main__':
    main()

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

l=[input() for _ in range(H)]

sx,sy=0,0

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

def bfs(sx,sy,l):
  que=deque()
  que.append([sx,sy])
  count=[[-1]*W for _ in range(H)]
  count[sx][sy]=0
  dx=[1,-1,0,0]
  dy=[0,0,1,-1]
  while que:
    x,y=que.popleft()
    if x==H-1 and y==W-1:
      return count[x][y]
    for j in range(4):
      a,b=x+dx[j],y+dy[j]
      if a<0 or a>=H or b<0 or b>=W or count[a][b]!=-1 or l[a][b]=='
        continue
      else:
        count[a][b]=count[x][y]+1
        que.append([a,b])
  return 0
print(-1 if bfs(sx,sy,l)==0 else H*W-(bfs(sx,sy,l)+black+1))

Solution (Python):
from collections import deque
import itertools

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

s = []
for _ in range(H):
    s.append(input())

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

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

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

diff = [[-1, 0], [1, 0], [0, -1], [0, 1]]

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

    for dy, dx in diff:
        ny, nx = y + dy, x + dx
        if nx >= 0 and ny >= 0 and nx < W and ny < H and s[ny][nx] != '
            score[ny][nx] = score[y][x] + 1
            d.append([ny, nx])

min_cell = score[gy][gx]
if min_cell != -1:
    whites = list(itertools.chain.from_iterable(s)).count('.')

    repaintings = whites - min_cell - 1
    print(repaintings)
else:
    print(-1)

Solution (Python):
from collections import deque

h, w = map(int, input().split())
c = []
d = [[-1 for i in range(w)] for j in range(h)]
d[0][0] = 0
white = 0
for i in range(h):
	s = input()
	c.append(s)
	white += s.count('.')

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

min_dist = -1
while len(q) != 0:
	y, x, z = q[0]
	if y == h - 1 and x == w - 1:
		min_dist = z
		break

	for i in range(4):
		ny, nx = y + dirr[i][0], x + dirr[i][1]
		if 0 <= ny < h and 0 <= nx < w and d[ny][nx] == -1 and c[ny][nx] != "
			q.append([ny, nx, z + 1])
			d[ny][nx] = z + 1

	q.popleft()

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

Solution (Python):
import collections
h, w = list(map(int, input().split()))
inf = h * w + 1
sharp = 0
data = []
for i in range(h):
    data.append(list(input()))
    
    sharp += data[i].count('

ans = [[inf for i in range(w)] for j in range(h)]
def dfs(row, column, count,data):
    
    if(row > w - 1) or (column > h - 1) or ( row < 0 ) or ( column < 0 ):
        return

    if data[column][row] == '
        return
    data[column][row] == '
    
    count += 1
    if row == w - 1 and column == h - 1:
        ans[column][row] = min(count, ans[column][row])
        return
    
    
    
    dfs(row + 1, column,     count, data)
    dfs(row,     column + 1, count, data)
    dfs(row - 1, column,     count, data)
    dfs(row,     column - 1, count, data)
def bfs(row, column, count,data):
    becter = [-1,1]
    queue = collections.deque()
    queue.append([column, row,count])
    while len(queue) != 0:
        v = queue.popleft()
        if v[0] < 0 or v[1] < 0 or v[0] >= h or v[1] >= w:
            continue
        if data[v[0]][v[1]] != '

            data[v[0]][v[1]] = '
            v[2] += 1
            ans[v[0]][v[1]] = min(ans[v[0]][v[1]], v[2])
            queue.append([v[0] + 1, v[1],v[2]])
            queue.append([v[0], v[1] + 1,v[2]])
            queue.append([v[0] - 1, v[1],v[2]])
            queue.append([v[0], v[1] - 1,v[2]])


bfs(0, 0, 0,data)
if ans[-1][-1] == inf:
    print(-1)
    exit()
print(h * w - sharp - ans[-1][-1])

Solution (Python):
import sys
sys.setrecursionlimit(1000000)
from collections import deque
h,w=map(int,input().split())
s=[list(input()) for i in range(h)]
c=0
for i in range(w):
    for j in range(h):
        if s[j][i]=='.':
            c+=1
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:
            print(c-d[h-1][w-1]-1)
            exit()
        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 s[nx][ny]!='
                que.append((nx,ny))
                d[nx][ny]=d[p[0]][p[1]]+1
    print(-1)

bfs()

Solution (Python):
from collections import deque
h,w=map(int,input().split())
field=[["
queue=deque([[1,1]])
cost=[[50000 for i in range(w)]for j in range(h)]
cost[0][0]=0
while queue:
  now=queue.popleft()
  for i in [(-1,0),(1,0),(0,1),(0,-1)]:
    if field[now[0]+i[0]][now[1]+i[1]]=="
    if cost[now[0]+i[0]-1][now[1]+i[1]-1]!=50000:continue
    queue.append((now[0]+i[0],now[1]+i[1]))
    cost[now[0]+i[0]-1][now[1]+i[1]-1]=cost[now[0]-1][now[1]-1]+1
cnt=0
for i in range(h+2):
  for j in range(w+2):
    if field[i][j]=="
cnt-=(h+w)*2+4
blackable=h*w-cnt
if cost[-1][-1]==50000:print(-1)
else:
  print(blackable-cost[-1][-1]-1)

Solution (Python):
import sys
from collections import defaultdict

input = sys.stdin.readline


class AtCoder:
    def main(self):
        H, W = map(int, input().split())
        field = defaultdict(lambda: '
        dot_cnt = 0
        for h in range(H):
            for w, c in enumerate(list(input().rstrip())):
                field[str(h + 1) + '-' + str(w + 1)] = c
                if c == '.':
                    dot_cnt += 1

        q = [(1, 1)]
        field['1-1'] = '
        moving_range = ((1, 0), (-1, 0), (0, 1), (0, -1))
        moves = 1
        while q:
            if (H, W) in q:
                break

            next_q = []
            for x, y in q:
                for m_x, m_y in moving_range:
                    n_x, n_y = x + m_x, y + m_y
                    if field[str(n_x) + '-' + str(n_y)] == '.':
                        next_q.append((n_x, n_y))
                        field[str(n_x) + '-' + str(n_y)] = '
            moves += 1
            q = next_q
            if not q:
                print(-1)
                exit()

        print(dot_cnt - moves)



if __name__ == '__main__':
    AtCoder().main()

Solution (Python):
import sys
from collections import defaultdict

input = sys.stdin.readline


class AtCoder:
    def main(self):
        H, W = map(int, input().split())
        field = defaultdict(lambda: '
        dot_cnt = 0
        for h in range(H):
            for w, c in enumerate(list(input().rstrip())):
                field[str(h + 1) + '-' + str(w + 1)] = c
                if c == '.':
                    dot_cnt += 1

        q = [(1, 1)]
        field['1-1'] = '
        moving_range = ((1, 0), (-1, 0), (0, 1), (0, -1))
        moves = 1
        goal_is_reachable = False
        while q:
            if (H, W) in q:
                goal_is_reachable = True
                break

            next_q = []
            for x, y in q:
                for m_x, m_y in moving_range:
                    n_x, n_y = x + m_x, y + m_y
                    if field[str(n_x) + '-' + str(n_y)] == '.':
                        next_q.append((n_x, n_y))
                        field[str(n_x) + '-' + str(n_y)] = '
            moves += 1
            q = next_q

        if not goal_is_reachable:
            print(-1)
        else:
            print(dot_cnt - moves)



if __name__ == '__main__':
    AtCoder().main()

Solution (Python):
from collections import deque

h, w = map(int, input().split())
INF = float("inf")
vect = ((0, 1), (0, -1), (1, 0), (-1, 0))
field = [[INF] * w for _ in range(h)]
bcnt = 0

for i in range(h):
    for j, s in enumerate(input()):
        if s == "
            field[i][j] = -1
            bcnt += 1

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

while q:
    y, x = q.popleft()
    if y == h-1 and x == w-1: break
    for dy, dx in vect:
        ny, nx = y + dy, x + dx
        if ny < 0 or ny >= h or nx < 0 or nx >= w or field[ny][nx] != INF: continue
        q.append((ny, nx))
        field[ny][nx] = field[y][x] + 1

res = field[h-1][w-1]
if res == INF or res == -1: print(-1)
else: print(h*w - bcnt - (res + 1))

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

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


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

visited = [[-1] * (W + 2) for _ in range(H + 2)]


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


visited[sy][sx] = 1


shortest = H * W

while queue:
    
    y, x = queue.popleft()
    if [y, x] == [gy, gx]:
        shortest = visited[y][x]
        break

    for i, j in ([1, 0], [-1, 0], [0, 1], [0, -1]):
        new_y, new_x = y + j, x + i
        if c[new_y][new_x] == '.' and visited[new_y][new_x] == -1:
            
            visited[new_y][new_x] = visited[y][x] + 1
            
            queue.append([new_y, new_x])
            
else:
    print(-1)
    exit()

print(sum([i.count('.') for i in c]) - shortest)

Solution (Python):
h, w = map(int, input().split())
s = [['
    + [['
p = [[1, 1]]
d = 0
for i in range(1, h+1):
    for j in range(1, w+1):
        if s[i][j] == '.':
            d += 1
s[1][1] = '
k = 0
while [h, w] not in p:
    k += 1
    g = []
    for i in range(len(p)):
        x, y = p[i][0], p[i][1]
        if s[x-1][y] == '.':
            s[x-1][y] = 'Q'
            g.append([x-1, y])
        if s[x+1][y] == '.':
            s[x+1][y] = 'Q'
            g.append([x+1, y])
        if s[x][y+1] == '.':
            g.append([x, y+1])
        if s[x][y-1] == '.':
            s[x][y-1] = 'Q'
            g.append([x, y-1])
    else:
        p = g
        if len(p) == 0:
            print(-1)
            break
else:
    print(d - k - 1)

Solution (Python):
h,w=map(int,input().split())
s=[]
for i in range(h):
	x=input()
	s.append(x)
inf=1000
dis=[[inf for _ in range(w)]for _ in range(h)]
dis[0][0]=0
lis=[[0,0]]
for i in range(1,101):
	p=[]
	for j in range(len(lis)):
		if lis[j][1]-1>=0:
			if s[lis[j][0]][lis[j][1]-1]=="." and dis[lis[j][0]][lis[j][1]-1]==1000:
				p.append([lis[j][0],lis[j][1]-1])
				dis[lis[j][0]][lis[j][1]-1]=min(i,dis[lis[j][0]][lis[j][1]-1])
		if lis[j][1]+1<w:
			if s[lis[j][0]][lis[j][1]+1]=="." and dis[lis[j][0]][lis[j][1]+1]==1000:
				p.append([lis[j][0],lis[j][1]+1])
				dis[lis[j][0]][lis[j][1]+1]=min(i,dis[lis[j][0]][lis[j][1]+1])
		if lis[j][0]-1>=0:
			if s[lis[j][0]-1][lis[j][1]]=="." and dis[lis[j][0]-1][lis[j][1]]==1000:
				p.append([lis[j][0]-1,lis[j][1]])
				dis[lis[j][0]-1][lis[j][1]]=min(i,dis[lis[j][0]-1][lis[j][1]])
		if lis[j][0]+1<h:
			if s[lis[j][0]+1][lis[j][1]]=="." and dis[lis[j][0]+1][lis[j][1]]==1000:
				p.append([lis[j][0]+1,lis[j][1]])
				dis[lis[j][0]+1][lis[j][1]]=min(i,dis[lis[j][0]+1][lis[j][1]])
	if dis[-1][-1]!=1000:
		break
	lis=p
cnt=0
for i in range(h):
	cnt+=s[i].count(".")
if dis[-1][-1]==1000:
	print(-1)
	exit()
print(cnt-dis[-1][-1]-1)

Solution (Python):
import sys
import os
from collections import deque

INF = 10**5
H, W = map(int,input().split())
S = ["" for _ in range(H)]
cntSharp = 0
for i in range(H):
    S[i] = input()
    cntSharp += S[i].count("

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

dx = [1,0,-1,0]
dy = [0,1,0,-1]
P = deque([])
P.append((0,0))
while P:
    p = P.popleft()
    s,t = p[0], p[1]
    for i in range(4):
        nx,ny = s + dx[i], t + dy[i]
        if 0 <= nx and 0 <= ny and nx <= H-1 and ny <= W-1 and S[nx][ny] =="." and dp[nx][ny] == INF:
            dp[nx][ny] = dp[s][t] + 1
            P.append((nx,ny))
if dp[H-1][W-1] == INF:
    print(-1)
else:
    print(H*W - dp[H-1][W-1] - cntSharp - 1)

Solution (Python):
from collections import deque

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

C = [[-1]*(W+2) for _ in range(H+2)]
C[1][1] = 1
q = deque()
q.append((1, 1))
xlist = [0, 0, 1, -1]
ylist = [1, -1, 0, 0]
while len(q) > 0:
    x, y = q.popleft()
    for i in range(4):
        mx = x + xlist[i]
        my = y + ylist[i]
        if S[mx][my] == '
            continue
        C[mx][my] = C[x][y] + 1
        q.append((mx, my))
if C[H][W] == -1:
    print(-1)
else:
    print(white_num - C[H][W])

Solution (Python):
def main():
    H, W = (int(i) for i in input().split())
    c = [input() for j in range(H)]
    sh, sw = 0, 0
    gh, gw = H-1, W-1

    from collections import deque
    def bfs():
        que = deque()
        dist = [[-1]*W for i in range(H)]

        dist[sh][sw] = 0
        que.append((sh,sw))
        d = ((1,0),(0,1),(-1,0),(0,-1))
        while que:
            uy,ux = que.popleft()
            for dy, dx in d:
                next_y = uy + dy
                next_x = ux + dx
                if not(0 <= next_y < H and 0 <= next_x < W): continue
                if dist[next_y][next_x] != -1: continue
                if c[next_y][next_x] == '
                dist[next_y][next_x] = dist[uy][ux] + 1
                que.append((next_y, next_x))
                if next_y == gh and next_x == gw:
                    return dist[gh][gw]
        return -1

    white_cnt = -1
    for i in range(H):
        for j in range(W):
            if c[i][j] == '.': white_cnt += 1
    
    goal = bfs()
    print(white_cnt - goal if goal != -1 else -1)

if __name__ == '__main__':
    main()

Solution (Python):
from collections import deque

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

INF = 10 ** 5
d = [[INF for i in range(W)] for j in range(H)]
d[0][0] = 0
nexts = [(-1, 0), (1, 0), (0, -1), (0, 1)]
q = deque()
q.append((0, 0))
while len(q) > 0:
  x, y = q.popleft()
  for dx, dy in nexts:
    nx, ny = x+dx, y+dy
    if nx < 0 or nx >= W or ny < 0 or ny >= H:
      continue
    if M[ny][nx] == '
      continue
    d[ny][nx] = d[y][x] + 1
    q.append((nx, ny))

if d[H-1][W-1] == INF:
  print(-1)
else:
  res = 0
  for y in range(H):
    for x in range(W):
      if M[y][x] == '.':
        res += 1
  print(res-(d[H-1][W-1]+1))

Solution (Python):
from collections import deque

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

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):
            nx = p[0] + dx[i]
            ny = p[1] + dy[i]

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

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

ans = bfs()
if ans == float("inf"):
    print(-1)
else:
    print((h*w) - (ans+1) - count)

Solution (Python):
from collections import deque

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

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):
            nx = p[0] + dx[i]
            ny = p[1] + dy[i]

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

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

ans = bfs()
if ans == float("inf"):
    print(-1)
else:
    print((h*w) - (ans+1) - count)

Solution (Python):
from collections import deque

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

gx, gy = w-1, h-1

q = deque()
q.appendleft([0,0])
INF = 10**5

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

while q:
  x,y = q.pop()
  
  for dx,dy in [[1,0],[0,1],[-1,0],[0,-1]]:
    nx = x+dx
    ny = y+dy
    
    if 0<=nx<w and 0<=ny<h:
      if dist[ny][nx]==INF and maze[ny][nx] != '
        dist[ny][nx] = dist[y][x]+1
        q.appendleft([nx,ny])      

black_num = sum([maze[i].count('

if dist[gy][gx] == INF:
  print(-1)
else:  
  print( h*w - dist[gy][gx] - black_num -1 )

Solution (Python):
H, W = map(int, input().split())
maze = [input() for _ in range(H)]
p_flg = [[0]*W for _ in range(H)]
dyx = [(-1,0),(1,0),(0,-1),(0,1)]

def bfn(y,x,cnt):
    stack = [(y,x,cnt)]
    p_flg[y][x] = cnt
    while stack:
        sy, sx, cnt= stack.pop(0)
        cnt += 1
        for dy, dx in dyx:
            ny, nx = sy+dy, sx+dx
            if ny == H-1 and nx == W-1:
                return cnt
            elif 0<=ny<H and 0<=nx<W:
                if maze[ny][nx] !="
                    p_flg[ny][nx] = cnt
                    stack.append((ny,nx,cnt))
    return 0

def main():
    n_obs = 0
    for h in range(H):
        for w in range(W):
            if maze[h][w] == "
                n_obs += 1
    n_path = bfn(0,0,1) -1
    if n_path == -1:
        print(-1)
        return
    else:
        ans = H*W - n_obs - n_path -1
        print(ans)

if __name__ == "__main__":
    main()

Solution (Python):
h,w=map(int,input().split())
b=[["
a=0
for i in range(h):
  c=["
  for j in input():
    a+=j=="
    c.append(j)
  b.append(c+["
b+=[["
b[h][w]=0
Q=[(1,1)]
x=0
y=-1
while Q:
	x+=1
	p=[]
	for i,j in Q:
		for dx,dy in [(1,0),(-1,0),(0,1),(0,-1)]:
			if b[i+dx][j+dy]==".":
				p+=[(i+dx,j+dy)]
				b[i+dx][j+dy]="
			elif b[i+dx][j+dy]==0:
				y=x
	if y>0:break
	Q=p
if y>0:print((h*w)-a-y-1)
else:print(-1)

Solution (Python):

import queue


def f(x,y):
    if x < 0 or y < 0 or x >= r or y >= c:
        return False
    if m[x][y] == "
        return False
    elif not (x,y) in done:
        if (x,y) == (gx,gy):
            return True
        else:
            done.add((x,y))
            q.put((x,y))
            return False
    else:
        return False          


q = queue.Queue()

r,c = map(int,input().split())
sx,sy = 1,1
gx,gy = r,c

sx -= 1
sy -= 1
gx -= 1
gy -= 1


m = ["" for _ in range(r)] 
sharp_counter = 0
for i in range(r):
    m[i] = input()
    sharp_counter += m[i].count("
    
    
q.put((sx,sy))
done = set()
counter = 1
while True:
    q_list = []
    for _ in range(q.qsize()):
        tx,ty = q.get()
        q_list.append((tx,ty))
        
    for one in q_list:
        tx,ty = one
        flags = [f(tx,ty-1),f(tx,ty+1),f(tx-1,ty),f(tx+1,ty)]
        if sum(flags) == 1:
            print(r*c -sharp_counter -(counter-1)-2)
            break
            
    if sum(flags) == 1:
        break
    if q_list == []:
        print(-1)
        break
    else:
        counter += 1