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(si, sj, gi, gj):
    visited = set()
    q = deque([(si, sj, {(si, sj)})])
    while q:
        i, j, path = q.popleft()
        for di, dj in (1, 0), (-1, 0), (0, 1), (0, -1):
            ni, nj = i + di, j + dj
            if 0 <= ni < H and 0 <= nj < W and field[ni][nj] == '.' and (ni, nj) not in visited:
                if (ni, nj) == (gi, gj):
                    return path | {(gi, gj)}
                visited.add((ni, nj))
                q.append((ni, nj, path | {(ni, nj)}))
    return set()


H, W = map(int, input().split())
field = [input() for _ in range(H)]
path = bfs(0, 0, H - 1, W - 1)
if path:
    print(sum(field[i][j] == '.' for i in range(H) for j in range(W)) - len(path))
else:
    print(-1)

Solution (Python):
from collections import deque


def bfs(si, sj, gi, gj):
    visited = set()
    q = deque([(si, sj, {(si, sj)})])
    while q:
        i, j, path = q.popleft()
        for di, dj in (1, 0), (-1, 0), (0, 1), (0, -1):
            ni, nj = i + di, j + dj
            if 0 <= ni < H and 0 <= nj < W and field[ni][nj] == '.' and (ni, nj) not in visited:
                if (ni, nj) == (gi, gj):
                    return path | {(gi, gj)}
                visited.add((ni, nj))
                q.append((ni, nj, path | {(ni, nj)}))
    return set()


H, W = map(int, input().split())
field = [input() for _ in range(H)]
path = bfs(0, 0, H - 1, W - 1)
if path:
    print(sum(field[i][j] == '.' and (i, j) not in path for i in range(H) for j in range(W)))
else:
    print(-1)

Solution (Python):
from collections import deque

H, W = map(int, input().split())
s = [input() for i in range(H)]
Map = [[0]*W for i in range(H)]
num_b = 0
for i in range(H):
  for j in range(W):
    if s[i][j] == '
      num_b += 1
      Map[i][j] = -1

dxy = [(1, 0), (0, 1), (-1, 0), (0, -1)]
que = deque([[0, 0]])
Map[0][0] = 1
while que:
  x, y = que.popleft()
  for dx, dy in dxy:
    xx, yy = x + dx, y + dy
    if 0<=xx<H and 0<=yy<W and Map[xx][yy] == 0:
      Map[xx][yy] = Map[x][y] + 1
      if (xx, yy) == (H-1, W-1):
        print(H*W - Map[xx][yy] - num_b)
        quit()
      que.append([xx, yy])

print(-1)

Solution (Python):
import sys
sys.setrecursionlimit(10 ** 9)

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


from collections import deque
b = 0
INF = float("inf")
checked = [[INF]*w for i in range(h)]

q = deque([])
q.append((0,0))
checked[0][0] = 1
while len(q)>0:
    pos = q.popleft()
    if pos == (h-1,w-1):
        b = (checked[h-1][w-1])
        break
    if pos[0] > 0:
        if not maze[pos[0] - 1][pos[1]] == '
            checked[pos[0] - 1][pos[1]] = checked[pos[0]][pos[1]] + 1
            q.append((pos[0] - 1, pos[1]))

    if pos[0] < h - 1:
        if not maze[pos[0] + 1][pos[1]] == '
            checked[pos[0] + 1][pos[1]] = checked[pos[0]][pos[1]] + 1
            q.append((pos[0] + 1, pos[1]))

    if pos[1] > 0:
        if not maze[pos[0]][pos[1] - 1] == '
            checked[pos[0]][pos[1] - 1] = checked[pos[0]][pos[1]] + 1
            q.append((pos[0], pos[1] - 1))

    if pos[1] < w - 1:
        if not maze[pos[0]][pos[1] + 1] == '
            checked[pos[0]][pos[1] + 1] = checked[pos[0]][pos[1]] + 1
            q.append((pos[0], pos[1] + 1))
a = []
for i in range(h):
    a.append(maze[i].count("."))
if not b == 0:
    print(sum(a)-b)
else:
    print(-1)

Solution (Python):
import sys
sys.setrecursionlimit(10 ** 9)

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


from collections import deque
b = 0
INF = float("inf")
checked = [[INF]*w for i in range(h)]

q = deque([])
q.append((0,0))
checked[0][0] = 1
while len(q)>0:
    pos = q.popleft()
    if pos == (h-1,w-1):
        b = (checked[h-1][w-1])
        break
    if pos[0] > 0:
        if not maze[pos[0] - 1][pos[1]] == '
            checked[pos[0] - 1][pos[1]] = checked[pos[0]][pos[1]] + 1
            q.append((pos[0] - 1, pos[1]))

    if pos[0] < h - 1:
        if not maze[pos[0] + 1][pos[1]] == '
            checked[pos[0] + 1][pos[1]] = checked[pos[0]][pos[1]] + 1
            q.append((pos[0] + 1, pos[1]))

    if pos[1] > 0:
        if not maze[pos[0]][pos[1] - 1] == '
            checked[pos[0]][pos[1] - 1] = checked[pos[0]][pos[1]] + 1
            q.append((pos[0], pos[1] - 1))

    if pos[1] < w - 1:
        if not maze[pos[0]][pos[1] + 1] == '
            checked[pos[0]][pos[1] + 1] = checked[pos[0]][pos[1]] + 1
            q.append((pos[0], pos[1] + 1))
a = []
for i in range(h):
    a.append(maze[i].count("."))
if not b == 0:
    print(sum(a)-b)
else:
    print(-1)

Solution (Python):
from collections import deque
h, w = map(int, input().split())
maze = [list(input()) for i in range(h)]
sx, sy = 0, 0
gx, gy = h - 1, w - 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((sx, sy))
  d[sx][sy] = 0
  while que:
    p = que.popleft()
    if p[0] == gx and p[1] == gy:
      break
    for i in range(4):
      nx = p[0] + dx[i]
      ny = p[1] + dy[i]
      if 0 <= nx < h and 0 <= ny < w and maze[nx][ny] != '
        que.append((nx, ny))
        d[nx][ny] = d[p[0]][p[1]] + 1
  return d[gx][gy]
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
h, w = map(int, input().split())
s = []
for _ in range(h):
    s.append(input())
q = deque([(0, 0)])
INF = 10**5
dist = [[INF]*w for _ in range(h)]
dist[0][0] = 0
dxdy = [(-1,0), (0,-1), (0,1), (1,0)]
while q:
    x, y = q.popleft()
    for dx, dy in dxdy:
        if not(0<=x+dx<w and 0<=y+dy<h):
            continue
        if s[y+dy][x+dx]=='
            continue
        dist[y+dy][x+dx] = dist[y][x] + 1
        q.append((x+dx, y+dy))
if dist[h-1][w-1]==INF:
    print(-1)
else:
    white = 0
    for r in s:
        white += r.count('.')
    print(white-dist[h-1][w-1]-1)

Solution (Python):
from collections import deque
h,w = map(int,input().split())
m = ["
temp = [[-1]*(w+2) for i in range(h+2)]
sy,sx = 1,1
temp[sy][sx] = 0
opt = [(1,0),(0,1),(-1,0),(0,-1)]
dq = deque([(sy,sx)])
while dq:
    y,x = dq.popleft()
    for i in opt:
        y1 = y+i[0]
        x1 = x+i[1]
        if m[y1][x1] == "." and temp[y1][x1] == -1:
            temp[y1][x1] = temp[y][x]+1
            dq.append((y1,x1))

cnt = 0
for i in m:
    cnt+=i.count("
if temp[h][w] == -1:
    print(-1)
else:
    print((h+2)*(w+2)-cnt-temp[h][w]-1)

Solution (Python):
from collections import deque

def bfs(s_l, visited, sy, sx, gy, gx, h, w):
    q = deque([[sy,sx]])
    visited[0][0] = 0
    while q:
        y, x = q.popleft()
        if [y, x] == [gy, gx]:
            return visited[gy][gx]
        for j, k in ([1, 0], [-1, 0], [0, 1], [0, -1]):
            n_y, n_x = y+j, x+k
            if n_y >= h or n_x >= w or n_y < 0 or n_x < 0:
                continue
            if s_l[n_y][n_x] == '.' and visited[n_y][n_x] == -1:
                visited[n_y][n_x] = visited[y][x] + 1
                q.append([n_y,n_x])
    return -1

def main():
    h, w = map(int, input().split()) 
    s_l = []
    all_dot_cnt = 0
    for i in range(h):
        row = list(input())
        s_l.append(row)
        all_dot_cnt += row.count('.')
    
    visited = [ [-1]*w for i in range(h)]
    res = bfs(s_l, visited, 0, 0, h-1, w-1, h, w)
    if res == -1:
        print(-1)
    else:
        
        
        print(all_dot_cnt-res-1)

if __name__ == "__main__":
    main()

Solution (Python):
H, W = map(int, input().split())
M = [list(input()) for _  in range(H)]
visited = [[0]*W for _ in range(H)]

from collections import deque
q = deque([[0, 0, 1]])
goal = False
while q:
    i, j, count = q.popleft()
    if i == H-1 and j == W-1:
        goal = True
        break
    
    for movei, movej in ((0, 1), (0, -1), (1, 0), (-1, 0)):
        ni = i + movei; nj = j + movej
        if ni < 0 or H <= ni or nj < 0 or W <= nj:
            continue
        if M[ni][nj] == '
            continue
        if visited[ni][nj] != 0:
            continue
        visited[ni][nj] = 1
        q.append([ni, nj, count+1])

if goal:
    numdots = 0
    for i in range(H):
        numdots += M[i].count('.')
    print(numdots - count)
else:
    print(-1)

Solution (Python):
H, W = map(int, input().split())
M = [list(input()) for _  in range(H)]
visited = [[0]*W for _ in range(H)]

from collections import deque
q = deque([[0, 0]])
while q:
    i, j = q.popleft()
    if i == H-1 and j == W-1:
        break
    
    for movei, movej in ((0, 1), (0, -1), (1, 0), (-1, 0)):
        ni = i + movei; nj = j + movej
        if ni < 0 or H <= ni or nj < 0 or W <= nj:
            continue
        if M[ni][nj] == '
            continue
        if visited[ni][nj] != 0:
            continue
        visited[ni][nj] = (i, j)
        q.append([ni, nj])
else:
    print(-1)
    exit()

si, sj = H-1, W-1
M[si][sj] = '*'
while si != 0 or sj != 0:
    si, sj = visited[si][sj]
    M[si][sj] = '*'
c = 0 
for i in range(H):
    c += M[i].count('.')
print(c)

Solution (Python):
from collections import deque
h, w = map(int, input().split())
maze = [[] for _ in range(h)]
seen = [[0 for i in range(w)] for _ in range(h)]
dx = deque()
dy = deque()
for i in range(h):
    l = input()
    for k in range(w):
        maze[i].append(l[k])
dx.append(0)
dy.append(0)
seen[0][0] = 1
while len(dx) != 0 and len(dy) != 0:
    nx = dx.popleft()
    ny = dy.popleft()
    if nx == w-1 and ny == h-1:
        black_all = 0
        for i in range(h):
            for k in range(w):
                if maze[i][k] == '
                    black_all += 1
        all_masu = h*w
        print(all_masu-black_all-seen[ny][nx])
        exit()
    for next_m in [(1,0), (-1, 0), (0, 1), (0, -1)]:
        next_x = nx + next_m[0]
        next_y = ny + next_m[1]
        if 0 <= next_x < w and 0 <= next_y < h:
            if maze[next_y][next_x] == '.' and seen[next_y][next_x] == 0:
                dx.append(next_x)
                dy.append(next_y)
                seen[next_y][next_x] = seen[ny][nx] + 1
print(-1)

Solution (Python):
from sys import stdin
from collections import deque
from collections import Counter


def grid2adj(arr_grid,direction=4):
    def cand(i,j,direction):
        if direction == 4:
            return [[i-1,j],[i+1,j],[i,j-1],[i,j+1]]
        elif direction == 8:
            return [[i-1,j],[i+1,j],[i,j-1],[i,j+1],
                    [i-1,j-1],[i-1,j+1],[i+1,j-1],[i+1,j+1]]
        else:
            print('Error')
    
    M,N = len(arr_grid),len(arr_grid[0])
    arr_con = [[] for i in range(M*N)]
    for i in range(M):
        for j in range(N):
            v = i*N+j
            for _cand in cand(i,j,direction):
                if 0<=_cand[0]<M and 0<=_cand[1]<N:
                    next_v = _cand[0]*N+_cand[1]
                    arr_con[v].append(next_v)
    arr_val = sum(arr_grid,[])

    return arr_con, arr_val


class BFS():
    def __init__(self, con, val=None):
        
        self.con = con
        self.val = val
        self.N = len(self.con)
        
        self.dist = [-1]*self.N
        self.que = deque()

    def bfs(self, start_v):
        
        self.dist[start_v] = 0
        self.que.append(start_v)

        while len(self.que)>0:
            v = self.que.popleft()
            for next_v in self.con[v]:
                if self.dist[next_v] != -1:
                    continue
                if self.val[next_v] == '
                    continue
                self.dist[next_v] = self.dist[v] + 1
                self.que.append(next_v)


if __name__ == "__main__":
    _in = [_.rstrip() for _ in stdin.readlines()]
    H, W = list(map(int,_in[0].split(' ')))  
    graph = []
    for i in range(H):
        _ = list(_in[i+1])  
        graph.append(_)
    
    g_con, g_val = grid2adj(graph)
    bfs = BFS(g_con,g_val)

    cnt = 0
    bfs.bfs(0)
    if bfs.dist[-1] == -1:
        cnt = -1
    else:
        cnt = H*W-bfs.val.count('
    
    print(cnt)

Solution (Python):
import sys
from collections import deque
    
def main(*args, **kwargs):
    
    H, W = map(int, sys.stdin.readline().split())
    total_cells = H * W
    existing_black_cells = 0
 
    grid = []
    for i in range(H):
        line = sys.stdin.readline()
        existing_black_cells += line.count('
        grid.append(line)
 
    
    queue = deque()
    queue.append((0, 0))  
    visited = set()
    visited.add((0, 0))
    movement = 0
 
    while len(queue) > 0:
        movement += 1
        for i in range(len(queue)):  
            coodinate = queue.popleft()
            y = coodinate[0]
            x = coodinate[1]
 
            
            if y == H - 1 and x == W - 1:
                print(total_cells - movement - existing_black_cells)
                return
 
            for dx, dy in [(1, 0), (0, 1), (-1, 0), (0, -1)]:
                X = x + dx
                Y = y + dy
                adjacent = (Y, X)
                if 0 <= X < W and 0 <= Y < H and grid[Y][X] == '.' and adjacent not in visited:
                    queue.append(adjacent)
                    visited.add(adjacent)
    print(-1)
    return
main()

Solution (Python):
from collections import deque
 
 
def dfs(field):
    q = deque([(0, 0, 0)])
    visited = [[False] * w for _ in range(h)]
    while q:
        i, j, d = q.popleft()
        if i == h - 1 and j == w - 1:
            return d
        if visited[i][j]:
            continue
        visited[i][j] = True
        if i > 0 and field[i - 1][j] == '.':
            q.append((i - 1, j, d + 1))
        if i < h - 1 and field[i + 1][j] == '.':
            q.append((i + 1, j, d + 1))
        if j > 0 and field[i][j - 1] == '.':
            q.append((i, j - 1, d + 1))
        if j < w - 1 and field[i][j + 1] == '.':
            q.append((i, j + 1, d + 1))
    else:
        return -1
 
 
h, w = map(int, input().split())
field = [input() for _ in range(h)]
dot_cnt = sum(r.count('.') for r in field)
d = dfs(field)
if d == -1:
    print(-1)
else:
    print(dot_cnt - (d+1))

Solution (Python):
cin = open(0).read().strip().split('\n')
h,w = map(int, cin[0].split(' '))
s = [list(a) for a in cin[1:]]

from collections import deque
q = deque()

dist = [[-1 for _ in range(w)] for _ in range(h)]
dist[0][0]=0

q.append((0,0))
while q:
    ph, pw = q.popleft()
    for dyi, dxi in zip([0,-1,0,1],[1,0,-1,0]):
        if 0<=ph+dyi<h and 0<=pw+dxi<w:
            if dist[ph+dyi][pw+dxi] != -1: continue
            if s[ph+dyi][pw+dxi] == '
            q.append((ph+dyi, pw+dxi))
            dist[ph+dyi][pw+dxi] = dist[ph][pw]+1

last = dist[h-1][w-1]
if last == -1:
    print(-1)
else:
    print(sum(s, []).count('.')-last-1)

Solution (Python):
import math
import bisect
from queue import Queue
from collections import deque

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

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

q = deque()
q.append(0)
q.append(0)
table[0][0] = 1
flag = -1
while(len(q)):
    nowx = q.popleft()
    nowy = q.popleft()

    if((nowx == h-1) and (nowy == w-1)):
        flag = int(table[nowx][nowy])

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

    for i in range(4):
        tempx = nowx + dx[i]
        tempy = nowy + dy[i]
        if((0 <= tempx)and(tempx < h)and(0 <= tempy)and(tempy < w)):
            if(table[tempx][tempy] =="."):
                table[tempx][tempy] = table[nowx][nowy] + 1
                q.append(tempx)
                q.append(tempy)


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

Solution (Python):
import sys
 
h,w=[int(x) for x in input().rstrip().split()]
l=[]
black=0
for i in range(h):
  s=[x for x in input()]
  l.append(s)
  black+=sum(j.count("
 
done=[[float('inf')]*w for i in range(h)]
def bfs():
  stack=[[0,0]]
  done[0][0]=0
  while(stack):
    x,y=stack.pop(0)
    move=[[x+1,y],[x-1,y],[x,y+1],[x,y-1]]
 
    for mx,my in move:
      if not(0<=my<=h-1) or not(0<=mx<=w-1) or l[my][mx]=="
        continue

      done[my][mx]=done[y][x]+1
      stack.append([mx,my])
      
      if my==h-1 and mx==w-1:
        print(h*w-done[my][mx]-black-1)
        sys.exit()
  print(-1)
 
if __name__=="__main__":
  bfs()

Solution (Python):
from collections import deque

h,w=map(int,input().split())
l=[list(input()) for i in range(h)]
visited=[[float('inf')]*w for i in range(h)]
def bfs():
  que =deque()
  visited[0][0]=0
  que.append([0,0])
  while que:
    p=que.popleft()
    if p[1]==w-1 and p[0]==h-1:
      break
    for dx,dy in ([0,1],[0,-1],[1,0],[-1,0]):
      ny=p[1]+dy
      nx=p[0]+dx
      if nx>=0 and ny>=0 and nx<h and ny<w and visited[nx][ny]==float('inf') and l[nx][ny]!='
        visited[nx][ny]=visited[p[0]][p[1]]+1
        que.append([nx,ny])

  return visited[h-1][w-1]


suml=0
for i in range(h):
  suml+=l[i].count('
  
if bfs()==float('inf'):
  print(-1)
else:
  print(h*w-suml-bfs()-1)

Solution (Python):

import sys
from collections import defaultdict
import math
import itertools
import bisect
from copy import deepcopy
from collections import deque
read = sys.stdin.buffer.read
readline = sys.stdin.readline
readlines = sys.stdin.buffer.readlines
sys.setrecursionlimit(10000)

H , W = map(int,readline().split())
board = ["
for  _ in range(H):
    board += ["
board += ["0" for _ in range(W+2)]
white = 0
for tile in board:
    if tile == ".":
        white += 1
H , W = H+2 , W+2
visit = [-1 for _ in range(W*H)]
D = [ [1,0] , [0,1] , [-1,0] , [0,-1] ]

def bfs():
    root = W + 1
    q = deque([root])
    visit[root] = 1
    while q :
        index = q.popleft()

        if index == (H-2)*W+W-2:
            break

        x =  index // W
        y =  index % W
        for d in D :
            dx , dy = d
            X , Y = x+dx , y+dy
            if 1<=X and X<= H-1 and 1<=Y and Y <= W-1:
                dot = X*W+Y
                if visit[dot] == -1 and board[dot] == ".":
                    visit[dot] = visit[index] + 1
                    q.append(dot)

    length = visit[(H-2)*W+W-2]
    if  length == -1:
        return -1
    else:
        return white - length


def solve():
    print(bfs())

if __name__ == "__main__":
    solve()

Solution (Python):



import sys
input = sys.stdin.readline
sys.setrecursionlimit(10**7)
from collections import Counter, deque
from collections import defaultdict
from itertools import combinations, permutations, accumulate, groupby, product
from bisect import bisect_left,bisect_right
from heapq import heapify, heappop, heappush
from math import floor, ceil,pi
from operator import itemgetter
def I(): return int(input())
def MI(): return map(int, input().split())
def LI(): return list(map(int, input().split()))
def LI2(): return [int(input()) for i in range(n)]
def MXI(): return [[LI()]for i in range(n)]
def SI(): return input().rstrip()
def printns(x): print('\n'.join(x))
def printni(x): print('\n'.join(list(map(str,x))))
inf = 10**17
mod = 10**9 + 7

h,w=MI()
lis=[[0]*(w+2) for i in range(h+2)]
for i in range(h):
    s=SI()
    for j in range(w):
        if s[j]==".":
            lis[i+1][j+1]=1

step=[[1,0],[0,-1],[-1,0],[0,1]]
counter=[[-1]*(w+2) for i in range(h+2)]
counter[1][1]=0
q=deque([[1,1]])
while q:
    x,y=q.popleft()
    
    for i,j in step:
        if counter[x+i][y+j]<0 and lis[x+i][y+j]==1:
            q.append([x+i,y+j])
            counter[x+i][y+j]=counter[x][y]+1
if counter[h][w]<0:
    print(-1)
    sys.exit()
white=0
for i in range(h+2):
    white+=sum(lis[i])

if lis[1][1]==1:
    white-=1
ans=white-counter[h][w]
print(ans)

Solution (Python):
from collections import deque
q = deque()
h,w=map(int,input().split())
sx,sy=1,1
ex,ey=h,w
q.append([sx-1,sy-1,0])
global finished 
finished = set()
c=[]
for i in range(h):
    c.append(list(map(str,input())))

def check(x,y):
    if 0<=x and x<h:
        if 0<=y and y<w:
            return True
    return False

count=0
def search():
    while (q):
        x,y,count=q.popleft()
        
        if check(x,y)==False or (x,y) in finished or c[x][y]=='
            continue
        else:
            q.append([x,y-1,count+1])
            q.append([x,y+1,count+1])
            q.append([x+1,y,count+1])
            q.append([x-1,y,count+1])
            finished.add((x,y))
            c[x][y]=count
            if x==ex-1 and y==ey-1:
                return c[x][y]+1 
    return -1
black_count=0
for i in range(h):
    black_count+=c[i].count("
path=search()
if path==-1:
    print(path)
else:
    print(h*w-black_count-path)

Solution (Python):
from collections import deque

h,w=map(int,input().split(' '))
maze=[0]*h
kuro=0
for y in range(h):
    line=input()
    kuro+=line.count('
    maze[y]=line
count=[[-1]*w for _ in range(h)]
count[0][0]=1

q=deque([[0,0]])
def BFS():
    while q:
        y,x=q.popleft()
        if (y,x)==(h-1,w-1):
            return h*w-kuro-count[h-1][w-1]
        for dy,dx in [[0,1],[1,0],[-1,0],[0,-1]]:
            ny,nx=y+dy,x+dx
            if not (0<=ny<h and 0<=nx<w):
                continue
            if maze[ny][nx]=='.' and count[ny][nx]==-1:
                q.append([ny,nx])
                count[ny][nx]=count[y][x]+1
    return -1

print(BFS())

Solution (Python):
H,W = map(int, input().split())
field = []
countd = 0
for _ in range(H):
    ls = []
    st = str(input())
    for ss in st:
        ls.append(ss)
        if ss =='.':
            countd += 1
    field.append(ls)
import heapq

def caldis(field):
    used = [[False]*50 for i in range(50)]
    dis = [[float('inf')]*51 for i in range(51)]
    dis[0][0] = 0
    que = []
    heapq.heappush(que,[0,0,0])
    while len(que)>0:
        pre = heapq.heappop(que)
        d = pre[0]
        px = pre[1]
        py = pre[2]
        if used[px][py] ==True:
            continue
        used[px][py] = True
        dis[px][py] = d
        for dx in [-1,1]:
            for dy in [-1,1]:
                if 0<=px+dx<=H-1:
                    if field[px+dx][py]=='.':
                        heapq.heappush(que,[d+1,px+dx,py])
                if 0<=py+dy<=W-1:
                    if field[px][py+dy]=='.':
                        heapq.heappush(que,[d+1,px,py+dy])
    res = dis[H-1][W-1]
    return res
an = caldis(field)
if an==float('inf'):
    print(-1)
else:
    print(countd-an-1)

Solution (Python):
from queue import Queue
import copy
import collections

R, C = map(int, input().split(' '))
M = [[s for s in input()] for _ in range(R)]
trial = 0


Sy = 1
Sx = 1
Gy = R
Gx = C

cnt  = 0
for i in range(R):
  cnt += M[i].count('

L = copy.deepcopy(M)

move = [(0, -1), (0, 1), (1, 0), (-1, 0)]
q = Queue()
ans = 0

q.put([(Sy, Sx)])
L[Sy-1][Sx-1] = '

while not q.empty():
  pos = q.get()
  valid_pos = []
  for p in pos:
      for m in move:
          y, x = p[0]+m[0], p[1]+m[1]
          if y == Gy and x == Gx:
            ans += 1
            print(R*C-ans-1-cnt)
            exit()            
          if 1<= y  <= R and 1<= x <= C:
            if L[y-1][x-1] == '.':
              L[y-1][x-1] = '
              valid_pos.append((y, x))
  if len(valid_pos) != 0:
      q.put(valid_pos)
  ans += 1
print(-1)

Solution (Python):
from collections import deque
if __name__ == "__main__":
    h, w = map(int, input().split())
    grid = []
    for _ in range(h):
        grid.append(input())
    
    white = 0
    for i in range(h):
        for j in range(w):
            if grid[i][j] == ".":
                white += 1
    
    qu = deque()
    qu.append(((0, 0), 0))
    
    visited = [[False] * w for _ in range(h)]
    visited[0][0] = True
    ans = -1

    while qu:
        now, dis = qu.pop()
        if now[0] == h-1 and now[1] == w-1:
            ans = white - dis - 1
            break

        if now[0] + 1 < h and grid[now[0] + 1][now[1]] != "
            visited[now[0] + 1][now[1]] = True
            qu.appendleft(((now[0] + 1, now[1]), dis + 1))
        
        if now[0] - 1 >= 0 and grid[now[0] - 1][now[1]] != "
            visited[now[0] - 1][now[1]] = True
            qu.appendleft(((now[0] - 1, now[1]), dis + 1))

        if now[1] + 1 < w and grid[now[0]][now[1] + 1] != "
            visited[now[0]][now[1] + 1] = True
            qu.appendleft(((now[0], now[1] + 1), dis + 1))
        
        if now[1] - 1 >= 0 and grid[now[0]][now[1] - 1] != "
            visited[now[0]][now[1] - 1] = True
            qu.appendleft(((now[0], now[1] - 1), dis + 1))
    print(ans)

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

def bfs(i0, j0):
    INF = 1000
    search = deque([(i0, j0)])
    d = [[INF] * w for i in range(h)]
    d[i0][j0] = 1
    while search:
        i, j = search.popleft()
        if (i, j) == (h - 1, w - 1):
            break
        for di, dj in ((1, 0), (0, 1), (-1, 0), (0, -1)):
            ni, nj = i + di, j + dj
            if 0 <= ni < h and 0 <= nj < w and s[ni][nj] == '.' and d[ni][nj] == INF:
                search.append((ni, nj))
                d[ni][nj] = d[i][j] + 1
    return d[i][j] if d[h - 1][w - 1] != INF else 0 
solvable = bfs(0, 0)
print(h*w - cnt_b - solvable if solvable else -1)

Solution (Python):
from collections import deque

def main():
    N,M = map(int,input().split())
    s = [list(str(input())) for _ in range(N)]
    count = 0
    for i in range(N):
        for j in range(M):
            if s[i][j] == ".":
                count += 1
    
    q = deque([(0,0)])
    dx,dy = [1,0,-1,0],[0,1,0,-1]
    dist = [[10**10 for _ in range(M)] for _ in range(N)]
    dist[0][0] = 1
    
    while q:
        x,y = q.pop()
        for _x,_y in zip(dx,dy):
            nx,ny = x+_x,y+_y
            if (0<=nx<N and 0<=ny<M and s[nx][ny] == "."):
                if dist[nx][ny] > dist[x][y]+1:
                    dist[nx][ny] = dist[x][y]+1
                    q.append((nx,ny))
    
    if dist[-1][-1] == 10**10:
        print(-1)
    else:
        print(count-dist[-1][-1])

if __name__ == "__main__":
    main()

Solution (Python):
import collections,itertools,sys
def S(): return sys.stdin.readline().rstrip()
def LI(): return list(map(int,sys.stdin.readline().rstrip().split()))
h,w=LI()
s=[S() for _ in range(h)]
blackcount=0
for i,j in itertools.product(range(h),range(w)):
    if s[i][j]=="
        blackcount+=1
dhdw=[[-1,0],[1,0],[0,-1],[0,1]]
mindist=[[-1]*w for _ in range(h)]
seen=[[0]*w for _ in range(h)]
queue=collections.deque()
def bfs():
    seen[0][0]=1
    queue.append([0,0])
    mindist[0][0]=1
    while queue:
        qh,qw=queue.popleft()
        for dh,dw in dhdw:
            nh,nw=qh+dh,qw+dw
            if not(0<=nh<=h-1) or not(0<=nw<=w-1) or seen[nh][nw] or s[nh][nw]=="
                continue
            if [nh,nw]==[h-1,w-1]:
                return mindist[qh][qw]+1
            seen[nh][nw]=1
            queue.append([nh,nw])
            mindist[nh][nw]=mindist[qh][qw]+1
    else:
        return -1
mindist=bfs()
print(h*w-blackcount-mindist if mindist!=-1 else -1)

Solution (Python):
from collections import deque
import sys
input = sys.stdin.readline
H,W = map(int,input().split())
lst=[[] for f in range(H)]
for i in range(H):
 lst[i] = [d for d in input()]
stack = deque([[0,0]])
muki=[[1,0],[-1,0],[0,1],[0,-1]]
check=[[0 for e in range(W)] for f in range(H)] 
check[0][0]=1
t=0
while stack != deque([]) :
 a=stack.popleft()
 for i in muki:
  b0=a[0]+i[0]
  b1=a[1]+i[1]
  if b0<=H-1 and b0>=0 and b1<=W-1 and  b1>=0:
   if check[b0][b1]==0 and lst[b0][b1]==".":
    check[b0][b1]=check[a[0]][a[1]]+1
    stack.append([b0,b1])
if check[H-1][W-1]==0:
 print(-1)
else:
 ct=0
 for i in range(H):
  for j in range(W):
   if lst[i][j]==".":
    ct+=1
 print(ct-check[H-1][W-1])

Solution (Python):
from collections import deque
H, W = map(int, input().split())
s = [list(input()) for i in range(H)]
Q = deque()
Q.append([0, 0])
dist = [[-1] * W for i in range(H)]
dist[0][0] = 0
c = 0
for i in range(H):
    for j in range(W):
        if s[i][j] == '.':
            c += 1

yudrl = [0, 1, 0, -1]
xudrl = [1, 0, -1, 0]

while (len(Q) > 0):
    q = Q.popleft()

    for i in range(4):
        y = q[0] + yudrl[i]
        x = q[1] + xudrl[i]

        if y < 0 or y > H - 1 or x < 0 or x > W - 1:
            continue  
        if dist[y][x] != -1 or s[y][x] == '
            continue
        dist[y][x] = dist[q[0]][q[1]] + 1
        Q.append([y, x])
if dist[H - 1][W - 1] == -1:
    print('-1')
else:
    print(c - dist[H - 1][W - 1] - 1)

Solution (Python):
from collections import deque
H, W = map(int, input().split())
s = []
for _ in range(H):
    s.append(input())
queue = deque([[0,0]])
dist = [[-1 for j in range(W)] for i in range(H)]
dist[0][0] = 0
dh = [0, 0, 1, -1]
dw = [1, -1, 0, 0]
while len(queue) != 0:
    now = queue.popleft()
    h = now[0]
    w = now[1]
    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
        elif dist[nh][nw] == -1 and s[nh][nw] == ".":
            queue.append([nh, nw])
            dist[nh][nw] = dist[h][w] + 1
ans = 0
if dist[H-1][W-1] == -1:
    print(-1)
    exit()

for i in range(H):
    for j in range(W):
        if s[i][j] == ".":
            ans += 1
ans = ans - dist[H-1][W-1] -1
print(ans)