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

from collections import deque, Counter, defaultdict

input = sys.stdin.readline
sys.setrecursionlimit(10**6)

h, w= list(map(int,input().split()))

s=[list(input().strip()) for i in range(h)]

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

total_point=0
for i in range(h):
    for u in range(w):
        if s[i][u]==".":
            total_point+=1

def bfs(y, x):
    q = deque([])
    q.append((y, x, -1))
    while len(q):
        
        y, x, d = q.popleft()
        if visited[y][x]==0:
            dis[y][x] = d+1
            visited[y][x] = 1
            if y==h-1 and x==w-1:
                break
            
            dx = [0, -1 ,0 ,1]
            dy = [-1 ,0 ,1 ,0]
            for i in range(4):
                
                nx = x + dx[i]
                ny = y + dy[i]
                if nx<0 or ny<0 or nx>=w or ny>=h or visited[ny][nx]==1 or s[ny][nx]=="
                    continue
                q.append((ny, nx, dis[y][x]))
bfs(0,0)
if visited[h-1][w-1]==0:
    print(-1)
else:
    print(total_point-dis[h-1][w-1]-1)

Solution (Python):
h,w = map(int,input().split())
grid = []
count = 0
for _ in range(h):
    x = input()
    count += x.count(".")
    grid.append(x)
from collections import deque
que = deque([])
dist = [[-1]*w for _ in range(h)]
dist[0][0] = 0

delta = [(-1,0),(0,-1),(0,1),(1,0)]
que.append((0,0))
while len(que) > 0:
    vy,vx = que.popleft()
    for dy,dx in delta:
        y = vy + dy
        x = vx + dx
        if not (0<=y<h and 0<=x<w):
            continue
        if dist[y][x] != -1:
            continue
        if grid[y][x] == "
            continue
        dist[y][x] = dist[vy][vx] + 1
        que.append((y,x))
ans = dist[h-1][w-1] 
if ans == -1:
    print(-1)
else:
    print(count - ans - 1)

Solution (Python):
H,W = map(int,input().split())
maze = []
for _ in range(H):
    l = list(input())
    maze.append(l)
import collections as col
q = col.deque()
q.append((0,0))
maze[0][0] = 0
def bfs(maze):
    while True:
        if len(q) == 0:
            print("-1")
            quit()
        else: nowx,nowy = q.popleft()
        if nowx == (H - 1) and nowy == (W - 1): return
        for x in [1,-1]: 
            if nowx + x == H or nowy == W or \
             maze[nowx + x][nowy] != '.' : continue
            if 0 <= nowx + x and nowx + x <= H - 1:
                q.append((nowx+x,nowy))
                maze[nowx + x][nowy] = maze[nowx][nowy] + 1
        for y in [1,-1]: 
            if nowx == H or nowy + y== W or \
             maze[nowx][nowy + y] != '.' : continue
            if 0 <= nowy + y and nowy + y <= W - 1:
                q.append((nowx,nowy+y))
                maze[nowx][nowy + y] = maze[nowx][nowy] + 1
bfs(maze)
cnt = 0
for x in maze:
    for y in x:
        if y == '
            cnt += 1
print(H*W - maze[H-1][W-1] - cnt - 1)

Solution (Python):
H,W = map(int,input().split())
maze = []
for _ in range(H):
    l = list(input())
    maze.append(l)
import collections as col
q = col.deque()
q.append((0,0))
maze[0][0] = 0
def bfs(maze):
    while True:
        try: nowx,nowy = q.popleft()
        except IndexError:
            print("-1")
            quit()
        if nowx == (H - 1) and nowy == (W - 1): return
        for x in [1,-1]: 
            if nowx + x == H or nowy == W: continue
            if maze[nowx + x][nowy] != '.' : continue
            if 0 <= nowx + x and nowx + x <= H - 1:
                q.append((nowx+x,nowy))
                maze[nowx + x][nowy] = maze[nowx][nowy] + 1
        for y in [1,-1]: 
            if nowx == H or nowy + y== W: continue
            if maze[nowx][nowy + y] != '.' : continue
            if 0 <= nowy + y and nowy + y <= W - 1:
                q.append((nowx,nowy+y))
                maze[nowx][nowy + y] = maze[nowx][nowy] + 1
bfs(maze)
cnt = 0
for x in maze:
    for y in x:
        if y == '
            cnt += 1
print(H*W - maze[H-1][W-1] - cnt - 1)

Solution (Python):
from collections import deque
h, w = map(int, input().split())
C = [list(input()) for _ in range(h)]
black_cells = 0
for y in range(h):
    for x in range(w):
        if C[y][x] == '
            black_cells += 1

dist = [[-1] * w for _ in range(h)]
dist[0][0] = 0
que = deque()
que.append((0, 0))
flag = False

while len(que) > 0:
    now_y, now_x = que.popleft()
    now_dist = dist[now_y][now_x]
    for dy, dx in ((1, 0), (-1, 0), (0, 1), (0, -1)):
        next_y = now_y + dy
        next_x = now_x + dx
        if 0 <= next_y < h and 0 <= next_x < w:
            if dist[next_y][next_x] == -1 and C[next_y][next_x] != '
                que.append((next_y, next_x))
                dist[next_y][next_x] = now_dist + 1
        if dist[h - 1][w - 1] != -1:
            flag = True
            break
    if flag:
        break

if flag:
    print(h * w - black_cells - dist[h - 1][w - 1] - 1)  
else:
    print('-1')

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

Ss = []
white_count = 0
for i in range(H):
    s = list(input())
    for masu in s:
        if masu == '.':
            white_count += 1
    Ss.append(s)




def search():
    global Ss_hosu
    
    Ss_hosu[0][0] = 1
    que = [[0, 0]]
    while len(que) > 0:
        x, y = que.pop(0)
        my_value = Ss_hosu[y][x]
        for dx, dy in [[1, 0], [-1, 0], [0, 1], [0, -1]]:
            if 0 <= x + dx <= W - 1 and 0 <= y + dy <= H - 1:
                if Ss[y + dy][x + dx] == '.' and Ss_hosu[y + dy][x + dx] is None:
                    Ss_hosu[y+dy][x+dx] = my_value + 1
                    que.append([x + dx, y + dy])

  
Ss_hosu = [[None for _ in range(W)] for _ in range(H)]
search()
min_hosu = Ss_hosu[H-1][W-1]






if min_hosu is None:
    print(-1)
else:
    print(white_count - min_hosu)

Solution (Python):
from collections import deque
def bfs():
  d=[[float("inf")]*m for _ in range(n)]
  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]==n-1 and p[1]==m-1:
      break
    for i in range(4):
      nx=p[0]+dx[i]
      ny=p[1]+dy[i]
      if 0 <= nx < n and 0 <= ny < m and c[nx][ny] != "
                
                que.append((nx, ny))
                d[nx][ny] = d[p[0]][p[1]] + 1
  return d[n-1][m-1]

n, m = map(int, input().split())
c = [list(input()) for i in range(n)]

count=0
for i in range(n):
  for j in range(m):
    if c[i][j]=="
      count+=1
g=bfs()
if 0<g<float("inf"):
  print(n*m-g-1-count)
else:
  print(-1)

Solution (Python):
import queue
h, w = list(map(int, input().split()))
s = [[' ']*(w+1) for i in range(h+1)]
for i in range(h):
    tmp = list(input())
    for j in range(w):
        s[i][j] = tmp[j]

dx = [1, 0, -1, 0]
dy = [0, 1, 0, -1]
cnt = 0
for i in range(h):
    for j in range(w):
        if s[i][j] == '.':
            cnt += 1
def bfs():
    d =[[10**10]*(w) for i in range(h)]

    que = queue.Queue()

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

    while not que.empty():
        p = que.get()
        if p[0] == h and p[1] == w:
            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.put([nx, ny])
                d[nx][ny] = d[p[0]][p[1]] + 1
    
    return d[h-1][w-1]

print(cnt - bfs() - 1) if bfs() != 10**10 else print(-1)

Solution (Python):
from collections import deque


def bfs():
    d = [[float("inf")] * w for i in range(h)]

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

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

    while que:
        p = que.popleft()
        if p[0] == gx and p[1] == gy:
            break
        for i in range(4):
            nx = p[0] + dx[i]
            ny = p[1] + dy[i]

            if 0 <= nx < 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]


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


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

res = bfs()
if 0 < res < float("inf"):
    
    
    print(white - res - 1)
else:
    print(-1)

Solution (Python):
import bisect
import collections
import functools
import heapq
import math
import sys
from collections import deque
from collections import defaultdict
input = sys.stdin.readline
MOD = 10**9+7

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

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

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

def distance(i,j):
    not_visit = [[-1]*W for i in range(H)]
    not_visit[i][j] = 0
    stack = [(i,j)]

    while stack != []:
        y,x = stack.pop(0)
        for i in range(4):
            if 0<= x+dx[i] <W and 0<= y+dy[i] <H and S[y+dy[i]][x+dx[i]] != "
                not_visit[y+dy[i]][x+dx[i]] =  not_visit[y][x] + 1
                stack.append((y+dy[i],x+dx[i]))
                if x+dx[i] == W-1 and y+dy[i] ==H-1:
                    break

    return not_visit[H-1][W-1]+1

if distance(0,0) != 0:
    print(c - distance(0,0))
else:
    print(-1)

Solution (Python):

from collections import deque

H, W = map(int, input().split())
grid = [[s for s in input()] for _ in range(H)]
done =[[True] * W for _ in range(H)]
done[0][0] = 0
d = [[-1] * W for _ in range(H)]
d[0][0] = 0
q = deque([(0, 0)])

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

while q:
    x, y = q.popleft()
    for i, j in [(0, 1), (0, -1), (1, 0), (-1, 0)]:
        x_n, y_n = x + i, y + j
        if (0 <= x_n and x_n <= H - 1 and 0 <= y_n and y_n <= W - 1
        and grid[x_n][y_n] == "." and done[x_n][y_n] is True):
            d[x_n][y_n] = d[x][y] + 1
            done[x_n][y_n] = 0
            q.append((x_n, y_n))

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

Solution (Python):
from collections import deque

class Pos:
    def __init__(self, x, y):
        self.x = x
        self.y = y

    def __str__(self):
        return 'Pos(' + str(self.x) + ', ' + str(self.y) + ')'
    
    def __add__(self, other):
        return Pos(self.x + other.x, self.y + other.y)

    def __sub__(self, other):
        return Pos(self.x - other.x, self.y - other.y)

    def __eq__(self, other):
        return self.x == other.x and self.y == other.y

    def __ne__(self, other):
        return not(self.x == other.x and self.y == other.y)

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


count = 0
for y in range(H):
    for x in range(W):
        count += 1 if s[y][x] == '


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


d = deque()

visited[0][0] = 0
d.appendleft(Pos(0, 0))

while d:
    now = d.pop()
    nexts = [now+Pos(0, 1), now+Pos(0, -1), now+Pos(1, 0), now+Pos(-1, 0)]
    for next in nexts:
        x, y = next.x, next.y
        if 0 <= x < W and 0 <= y < H:
            if s[y][x] == '.' and visited[y][x] == -1:
                visited[y][x] = visited[now.y][now.x] + 1
                d.appendleft(next)

if visited[H-1][W-1] == -1:
    print(-1)
else:
    print(H*W-(visited[H-1][W-1]+1)-count)

Solution (Python):
from collections import deque

h, w = map(int, input().split())
G = []
for i in range(h):
  g = list(input())
  G.append(g)
  
que = deque()
dist = [[-1]*w for _ in range(h)]

sx, sy = 0, 0
gx, gy = w-1, h-1
dx = [1, 0, -1, 0]
dy = [0, 1, 0, -1]

dist[0][0] = 0
que.append([sx,sy])

while que:
  x, y = que.popleft()
  
  for i in range(4):
    nx = x+dx[i]
    ny = y+dy[i]
    
    if nx<0 or nx>=w or ny<0 or ny>=h or G[ny][nx]=='
      continue

    if dist[ny][nx]==-1:
      que.append([nx, ny])
      dist[ny][nx] = dist[y][x] +1
      
bk = 0
for i in range(h):
  for j in range(w):
    if G[i][j] == '
      bk += 1
      

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

Solution (Python):
from collections import deque

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


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

n_black = 0

for i in range(H):
    n_black += field[i].count("


dist = [[-1 for x in range(W)] for y in range(H)]
dist[0][0] = 1

que = deque()
que.append((0, 0))



while len(que):
    n = que.popleft()
    ny = n[0]
    nx = n[1]

    for i in range(4):
        nny = ny + dy[i]
        nnx = nx + dx[i]

        if nny >= 0 and nny < H and nnx >= 0 and nnx < W and field[nny][nnx] == "." and dist[nny][nnx] == -1:
            dist[nny][nnx] = dist[ny][nx] + 1
            que.append((nny, nnx))

min = dist[H-1][W-1]

if min == -1:
    print(-1)

else:
    print(H * W - min - n_black)

Solution (Python):
import sys
from collections import deque

sys.setrecursionlimit(10 ** 6)
INF = float("inf")
MOD = 10 ** 9 + 7


def input():
    return sys.stdin.readline().strip()


def bfs(maze, H, W, sh, sw, gh, gw):
    visited = [[-1] * W for _ in range(H)]
    visited[sh][sw] = 0

    q = deque([(sh, sw)])

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

        if h == gh and w == gw:
            return visited[gh][gw]

        for dh, dw in [(1, 0), (-1, 0), (0, 1), (0, -1)]:
            nh = h + dh
            nw = w + dw
            if 0 <= nh < H and 0 <= nw < W:
                if visited[nh][nw] == -1 and maze[nh][nw] == ".":
                    visited[nh][nw] = visited[h][w] + 1
                    q.append((nh, nw))

    return -1


def main():
    H, W = map(int, input().split())
    S = [input() for _ in range(H)]
    white = 0
    for h in range(H):
        for w in range(W):
            if S[h][w] == ".":
                white += 1

    dist = bfs(S, H, W, 0, 0, H - 1, W - 1)
    if dist == -1:
        print(-1)
        return

    ans = white - (dist + 1)
    print(ans)


if __name__ == "__main__":
    main()

Solution (Python):
import sys
from collections import deque, Counter, defaultdict
import heapq


def resolve():
    n_rows, n_cols = map(int, sys.stdin.readline().strip().split())
    matrix = [[]] * n_rows
    n_whites = 0
    for i in range(n_rows):
        row = list(sys.stdin.readline().strip())
        for c in row:
            if c == '.':
                n_whites += 1
        matrix[i] = row

    shortest_path = 1
    queue = deque()
    queue.append((0, 0))
    found = True
    while queue:
        shortest_path += 1
        for _ in range(len(queue)):
            x, y = queue.popleft()
            nexts = (
                (x+1, y),
                (x-1, y),
                (x, y+1),
                (x, y-1),
            )
            for nx, ny in nexts:
                if (nx, ny) == (n_rows-1, n_cols-1):
                    break
                if 0 <= nx < n_rows and 0 <= ny < n_cols and matrix[nx][ny] == '.':
                    matrix[nx][ny] = '
                    queue.append((nx, ny))
            else:
                continue
            break
        else:
            continue
        break
    else:
        found = False

    if found:
        print(n_whites - shortest_path)
    else:
        print(-1)

if __name__ == "__main__":
    resolve()

Solution (Python):
from collections import deque
dirc = ((1, 0), (0, 1), (-1, 0), (0, -1))
H, W = map(int, input().split())
maze = [list(str(input())) for _ in range(H)]
white = 0
for h in range(H):
    for w in range(W):
        if maze[h][w]=='.':
            white += 1
queue = deque()
queue.appendleft((0, (0, 0)))
checked = [[0]*W for _ in range(H)]
ans = 0
while queue:
    c, (y, x) = queue.pop()
    c += 1
    if checked[y][x]:
        continue
    checked[y][x] = 1
    if (y, x)==(H-1, W-1):
        ans = c
        break
    for i, (dy, dx) in enumerate(dirc):
        ny, nx = y+dy, x+dx
        if nx<0 or nx>=W or ny<0 or ny>=H:
            continue
        if maze[ny][nx]=='
            continue
        if not checked[ny][nx]:
            queue.appendleft((c, (ny, nx)))
if ans==0:
    print(-1)
else:
    print(white-ans)

Solution (Python):
from collections import deque

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

s = ['1'*(W+2)]
cntw = 0

for i in range(H):
    a = input()
    a = a.replace('.', '0').replace('
    cntw += a.count('0')
    s.append('1'+a+'1')
s.append('1'*(W+2))

visited = [[0] * (W+2) for _ in range(H+2)]
visited[1][1] = 1
temp = deque([[1, 1, 0]])
ans = 0

while temp:
    p = temp.popleft()
    if p[0:2] == [H, W]:
        ans= p[2]
        break
    else:
        for k in [[1, 0], [-1, 0], [0, 1],[0, -1]]:
            if s[p[0]+k[0]][p[1]+k[1]] == '0' and visited[p[0]+k[0]][p[1]+k[1]] == 0:
                temp.append([p[0]+k[0], p[1]+k[1], p[2]+1])
                visited[p[0]+k[0]][p[1]+k[1]] = 1
    
print(cntw- (ans + 1) if ans!=0 else -1)

Solution (Python):
from collections import  deque

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

def bfs():
    d =  [[float('inf')] * W for _ 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] !='
                d[nx][ny] = d[p[0]][p[1]] + 1
                que.append((nx, ny))
    return d[gx][gy]
    

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

white = 0
for t in maze:
    for s in t:
        if  s == '.':
            white += 1
            
res = bfs()
if 0 < res < float('inf'):
    print(white - res - 1)
else:
    print(-1)

Solution (Python):
h,w=map(int,input().split())
G=[]
white=0
for _ in range(h):
    s=input()
    white+=s.count('.')
    G.append(s)

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

from collections import  deque
que=deque([(0,0,1)])

move=[(1,0),(-1,0),(0,1),(0,-1)]

while len(que)>0:
    ni,nj,c=que.popleft()
    for di,dj in move:
        mi,mj=ni+di,nj+dj
        if 0<=mi<h and 0<=mj<w and G[mi][mj]=='.' and vis[mi][mj]==0:
            vis[mi][mj]=c+1
            que.append((mi,mj,c+1))

print(white-vis[-1][-1]) if vis[-1][-1]!=0 else print(-1)

Solution (Python):
import sys
from collections import deque
sys.setrecursionlimit(10000)
a,b=map(int,input().split())
List=[]
sumup=0
for i in range(a):
  l=list(input())
  p=l.count(".")
  sumup+=p
  List.append(l)
List[0][0]=1
q=deque([[0,0]])
while q:
  h,w=q.popleft()
  aaa=[[0,1],[0,-1],[1,0],[-1,0]]
  for x,y in aaa:
    if 0<=h+x<a and 0<=w+y<b:
      if List[h+x][w+y]==".":
        List[h+x][w+y]=List[h][w]+1
        q.append([h+x,w+y])
if List[a-1][b-1]==".":
  print(-1)
else:  
  print(sumup-List[a-1][b-1])

Solution (Python):
from collections import deque
import pprint
H,W=map(int,input().split())
table=[list(input()) for _ in range(H)]
d=deque()
dp=[[float("inf") for _ in range(W)] for _ in range(H)]
dp[0][0]=1
d.append([0,0])
seen=[[0 for _ in range(W)] for _ in range(H)]
seen[0][0]=1
blnum=0
for i in range(H):
    for j in range(W):
        if table[i][j]=="
            blnum=blnum+1
while len(d)!=0:
    v=d.popleft()
    x=v[0]
    y=v[1]
    if x!=0:
        if (table[x-1][y]==".")and(seen[x-1][y]==0):
            d.append([x-1,y])
            seen[x-1][y]=1
            dp[x-1][y]=min(dp[x-1][y],dp[x][y]+1)
    if x!=H-1:
        if (table[x+1][y]==".")and(seen[x+1][y]==0):
            d.append([x+1,y])
            seen[x+1][y]=1
            dp[x + 1][y] = min(dp[x + 1][y], dp[x][y] + 1)
    if y!=0:
        if (table[x][y-1]==".")and(seen[x][y-1]==0):
            d.append([x,y-1])
            seen[x][y-1]=1
            dp[x][y-1]=min(dp[x][y-1],dp[x][y]+1)
    if y!=W-1:
        if (table[x][y+1]==".")and(seen[x][y+1]==0):
            d.append([x,y+1])
            seen[x][y+1]=1
            dp[x][y+1]=min(dp[x][y+1],dp[x][y]+1)
    
    
    
if dp[H-1][W-1]==float("inf"):
    print("-1")
else:
    print(H*W-dp[H-1][W-1]-blnum)

Solution (Python):
import sys
readline = sys.stdin.readline
from collections import deque
H,W = list(map(int, input().split()))
matrix = []
blocks = 0
for _ in range(H):
  
  row = readline().rstrip()
  blocks += row.count("
  matrix.append(row)

q = deque([(0,0,0)])
min_step = -1

visited = [ [False]*W for _ in range(H) ]
visited[0][0] = True

while q:
  r,c,step = q.popleft()
  
  

  for i,j in [(1,0),(0,1),(-1,0),(0,-1)]:
    nr,nc = r+i,c+j
    if nr==H-1 and nc==W-1: 
      min_step = step+1
      q = []
      break

    if nr<0 or nc<0 or nr>=H or nc>=W: continue
    if visited[nr][nc] or (nr,nc,step+1) in q: continue
    
    if matrix[nr][nc] == "
    visited[r][c] = True
    q.append((nr,nc,step+1))

if min_step == -1:
  print(-1)
else:
  print( H*W - blocks - min_step -1 )

Solution (Python):

from collections import Counter
from collections import deque

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


def checkRoute(matrix):
    
    
    queue = deque([  ( (1,1),1 )  ])

    delta = [(1,0),(-1,0),(0,1),(0,-1)]
    visited = set()
    
    while queue:
        (r,c),step = queue.popleft()
        
        for d in delta:
            next_r = r + d[0]
            next_c = c + d[1]
            
            if (next_r == H) and (next_c == W):
                return step+1
            
            if (1 <= next_r <= H) and (1 <= next_c <= W) and \
               (next_r, next_c) not in visited  and \
               matrix[next_r][next_c] == ".":
            
                queue.append( ( (next_r, next_c), step+1 ) )
                visited.add( (next_r, next_c) )

    return -1



for i in range(len(S_list)):
    S_list[i] = ["
    
S_list = [["


cnt_dic = Counter( sum(S_list,[]) )
min_step = checkRoute(S_list)

if min_step != -1:
    print( cnt_dic["."] - min_step )
else:
    print(-1)

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

def abc088_d():
    
    H, W = map(int, readline().split())
    grid = [['
    for ln in read().split():
        grid.append(['
    else:
        grid.append(['

    
    from collections import deque
    dist = [[-1] * (W+2) for _ in range(H+2)]
    dist[1][1] = 0  
    que = deque([(1,1)])
    while que:
        
        r, c = que.popleft()
        
        for i, j in ((r-1, c), (r, c-1), (r, c+1), (r+1, c)):
            if grid[i][j] == '
            if dist[i][j] != -1: continue  
            dist[i][j] = dist[r][c] + 1
            que.append((i,j))

    
    if dist[H][W] == -1:
        ans = -1  
    else:
        ans = sum([row.count('.') for row in grid])
        ans -= 1 + dist[H][W]
    print(ans)

abc088_d()

Solution (Python):
from _collections import deque
H, W = map(int, input().split())
maze = []
wall = 0
for i in range(H):
    s = input()
    maze.append(s)
    wall += s.count('

queue = deque()
queue.append([0,0])
steps = [[-1]*W for _ in range(H)]
steps[0][0] = 0
while queue:
    now = queue.popleft()
    

    UDLR = [[-1, 0], [1, 0], [0, -1], [0, 1]]
    for direction in UDLR:
        goto_y = now[0] + direction[0]
        goto_x = now[1] + direction[1]
        if (goto_x - 0)*(W-1 - goto_x) < 0 or (goto_y - 0)*(H-1 - goto_y) < 0:
            continue
        if maze[goto_y][goto_x] == '
            continue

        queue.append([goto_y, goto_x])
        steps[goto_y][goto_x] = steps[now[0]][now[1]] + 1


if steps[H-1][W-1] == -1:
    print(-1)
    exit()

print(H*W - wall - steps[H-1][W-1] - 1)

Solution (Python):
from collections import deque

h, w = map(int, input().split())

grid = [list(input()) for _ in range(h)]
visited = [[False] * w for _ in range(h)]

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

que = deque()
que.append((sx, sy))
visited[sy][sx] = 1
while que:
    cx, cy = que.popleft()
    for dx, dy in [(-1, 0), (1, 0), (0, -1), (0, 1)]:
        nx, ny = cx + dx, cy + dy
        if (0 <= nx < w) and (0 <= ny < h) and (visited[ny][nx] is False) and (grid[ny][nx] == '.'):
            if ny == gy and nx == gy:
                visited[ny][nx] = visited[cy][cx] + 1
                break
            else:
                visited[ny][nx] = visited[cy][cx] + 1
                que.append((nx, ny))

if visited[gy][gx] is False:
    print(-1)
else:
    cnt = 0
    for y in range(h):
        for x in range(w):
            if grid[y][x] == "
                cnt += 1
    print(h * w - visited[gy][gx] - cnt)

Solution (Python):
from _collections import deque
H,W = map(int,input().split())
T = []
for i in range(H):
    a = list(input())
    T.append(a)

K = [[0,0,0]]
P = deque(K)
dp = [[10**6]*W for _ in range(H)]
used = [[0]*W for _ in range(H)]
move = [(-1,0),(0,-1),(1,0),(0,1)]

while(len(P)>0):
    b = P.popleft()
    h = b[0]
    w = b[1]
    c = b[2]
    if c < dp[H-1][W-1]:
        for i,j in move:
            if h+i >= 0 and h+i <= H-1:
                if w+j >= 0 and w+j <= W-1:
                    if T[h+i][w+j] == ".":
                        dp[h+i][w+j] = min(c+1,dp[h+i][w+j])
                        if used[h+i][w+j] == 0:
                            used[h+i][w+j] = 1
                            P.append([h+i,w+j,c+1])

ans = 0
for i in range(H):
    for j in range(W):
        if T[i][j] == ".":
            ans += 1
if dp[H-1][W-1] == 10**6:
    print(-1)
else:
    print(ans-dp[H-1][W-1]-1)

Solution (Python):


def solve():
    import sys
    from collections import deque

    H, W = map(int, sys.stdin.readline().split())
    grid = []
    for _ in range(H):
        grid.append(list(sys.stdin.readline().rstrip()))

    
    ans = 0
    for h in range(H):
        for w in range(W):
            ans += 1 if grid[h][w]=="." else 0

    
    dist = [[float("inf") for _ in range(W)] for __ in range(H)]
    dist[0][0] = 1
    que = deque([(0,0)])
    while que:
        h, w = que.popleft()
        if grid[h][w] == "x": continue
        grid[h][w] = "x"

        for nh, nw in ((h-1,w), (h+1,w), (h,w-1), (h,w+1)):
            if nh==-1 or nh==H or nw==-1 or nw==W: continue
            if grid[nh][nw] != ".": continue
            dist[nh][nw] = dist[h][w] + 1
            que.append((nh, nw))

    if dist[H-1][W-1] == float("inf"):
        print(-1)
    else:
        print(ans - dist[H-1][W-1])


if __name__ == "__main__":
    solve()

Solution (Python):
from pprint import pprint
from collections import deque

def bfs(sy,sx):
    que = deque()
    que.append([sy,sx])
    checked_map = [[-1]*w for _ in range(h)]
    checked_map[sy][sx] = 0

    dyx = [[1,0],[-1,0],[0,1],[0,-1]]

    while que:
        y,x = que.popleft()
        if y == gy and x == gx:
            return checked_map[gy][gx]
        for d in dyx:
            ny = y + d[0]
            nx = x + d[1]
            
            if 0 <= ny <= h-1 and 0 <= nx <= w-1 and s[ny][nx] == "." and (checked_map[ny][nx] == -1 or checked_map[ny][nx] -1 > checked_map[y][x]):
                checked_map[ny][nx] = checked_map[y][x] + 1
                que.append([ny,nx])
            else:
                continue
    
    else:
        return -1





h,w = map(int,input ().split())

s = [list(input()) for _ in range(h)]


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

flg = bfs(sy,sx)

if flg == -1:
    print(-1)
    exit()
else:
    counter = 0
    for line in s:
        counter += line.count(".")
    
    result = counter - flg - 1
    
    
    print(result)

Solution (Python):
H, W = map(int, input().split())
graph = []
for _ in range(H):
    graph.append(input())

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

que = [[0, 0]]
distance = 0
while len(que) > 0:
    h, w = que.pop(0)
    if h == H - 1 and w == W - 1:
        distance = dist[h][w]
        break
    for a, b in [[0, 1], [0, -1], [1, 0], [-1, 0]]:
        ht, wt = h + a, w + b
        if 0 <= ht < H and 0 <= wt < W and graph[ht][wt] == "." and dist[ht][wt] == 0:
            dist[ht][wt] = dist[h][w] + 1
            que.append([ht, wt])

if distance == 0:
    print(-1)
    exit()

total = W * H - 1
for g in graph:
    total -= g.count("
print(total - distance)

Solution (Python):


from collections import deque

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

kuro = 0
for i in range(1, H+1):
    for j in range(1, W+1):
        if maze[i][j] == '
            kuro += 1

dist = [[0] * (W+2) for _ in range(H+2)]
q = deque()
q.append((1,1))
dist[1][1] = 1
siro = -1
while len(q) > 0:
    y, x = q.popleft()
    if (y, x) == (H, W):
        siro = dist[y][x]
        break
    for vy, vx in [(0, 1), (1, 0), (0, -1), (-1, 0)]:
        ny = y + vy
        nx = x + vx
        if maze[ny][nx] == '.' and dist[ny][nx] == 0:
            dist[ny][nx] = dist[y][x] + 1
            q.append((ny, nx))

if siro == -1:
    print(siro)
else:
    print(H*W - kuro - siro)