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 周辺埋め(grid, W):
    U = "
    return [list(U)] + [["

H, W, *grid = open(0).read().split()
H, W = map(int, (H, W))

C = sum(g.count(".") for g in grid)

grid = 周辺埋め(grid, W)

grid[1][1] = "!"
grid[H][W] = "G"

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

def bfs():
    que = deque()
    que.append((1, 1, 0))

    while que:
        cy, cx, c = que.popleft()

        for my, mx in D:
            nx = cx + mx
            ny = cy + my

            if grid[ny][nx] == ".":
                
                que.append((ny, nx, c + 1))
                grid[ny][nx] = "!"  
            
            elif grid[ny][nx] == "G":  
                return C - (c + 2)

    return -1

print(bfs())

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

def int1(x): return int(x) - 1
def II(): return int(input())
def MI(): return map(int, input().split())
def MI1(): return map(int1, input().split())
def LI(): return list(map(int, input().split()))
def LI1(): return list(map(int1, input().split()))
def LLI(rows_number): return [LI() for _ in range(rows_number)]
def MS(): return input().split()
def LS(): return list(input())
def LLS(rows_number): return [LS() for _ in range(rows_number)]
def printlist(lst, k=' '): print(k.join(list(map(str, lst))))
INF = float('inf')

from collections import deque






def grid_wall(grid, h, w, wall='
    G = [[wall]*(w+2) for _ in range(h+2)]
    for hi in range(h):
        G[hi+1][1:w+1] = grid[hi]
    return G

def solve():
    H, W = MI()
    G = LLS(H)

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

    G[-1][-1] = 'G'
    G[0][0] = '

    G2 = grid_wall(G, H, W, '
    

    q = deque([(1, 1, 1)])
    move = [(0, 1), (0, -1), (1, 0), (-1, 0)]
    cost = INF
    while q:
        x, y, d = q.popleft()
        for dx, dy in move:
            nx, ny = x+dx, y+dy
            if G2[nx][ny] == 'G':
                cost = min(cost, d + 1)
            elif G2[nx][ny] == '
            else:
                q.append((nx, ny, d+1))
                G2[nx][ny] = '
    if cost == INF:
        print(-1)
        return
    
    print(H * W - black_cnt - cost)
if __name__ == '__main__':
    solve()

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

def int1(x): return int(x) - 1
def II(): return int(input())
def MI(): return map(int, input().split())
def MI1(): return map(int1, input().split())
def LI(): return list(map(int, input().split()))
def LI1(): return list(map(int1, input().split()))
def LLI(rows_number): return [LI() for _ in range(rows_number)]
def MS(): return input().split()
def LS(): return list(input())
def LLS(rows_number): return [LS() for _ in range(rows_number)]
def printlist(lst, k=' '): print(k.join(list(map(str, lst))))
INF = float('inf')

from collections import deque


import numpy as np

from pprint import pprint

def grid_wall(grid, h, w, wall='
    G = [[wall]*(w+2) for _ in range(h+2)]
    for hi in range(h):
        G[hi+1][1:w+1] = grid[hi]
    return G

def solve():
    H, W = MI()
    G = LLS(H)

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

    G[-1][-1] = 'G'
    G[0][0] = '

    G2 = grid_wall(G, H, W, '
    

    q = deque([(1, 1, 1)])
    move = [(0, 1), (0, -1), (1, 0), (-1, 0)]
    cost = INF
    while q:
        x, y, d = q.popleft()
        for dx, dy in move:
            nx, ny = x+dx, y+dy
            if G2[nx][ny] == 'G':
                cost = min(cost, d + 1)
            elif G2[nx][ny] == '
            else:
                q.append((nx, ny, d+1))
                G2[nx][ny] = '
    if cost == INF:
        print(-1)
        return
    
    print(H * W - black_cnt - cost)
if __name__ == '__main__':
    solve()

Solution (Python):
from sys import stdin

def main():
    from collections import deque
    import copy
    input = stdin.readline

    h, w = map(int, input().split())
    cm = [[0] * (w + 2) for _ in range(h + 2)]
    que = deque([])
    b = 0
    for i in range(1, h + 1):
        s = input()
        for j in range(1, w + 2):
            if s[j - 1] == ".":
                cm[i][j] = -1
            elif s[j - 1] == "
                b += 1
    que.append([1, 1, 0])
    while len(que) > 0:
        y, x, r = que.popleft()
        c = r + 1
        if cm[y + 1][x] == -1:
            cm[y + 1][x] = c
            que.append([y + 1, x, c])
        if cm[y - 1][x] == -1:
            cm[y - 1][x] = c
            que.append([y - 1, x, c])
        if cm[y][x + 1] == -1:
            cm[y][x + 1] = c
            que.append([y, x + 1, c])
        if cm[y][x - 1] == -1:
            cm[y][x - 1] = c
            que.append([y, x - 1, c])
    if cm[h][w] == -1:
        print(-1)
    else:
        print(h * w - b - cm[h][w] - 1)
main()

Solution (Python):
import sys
from collections import deque

input = sys.stdin.readline
digtmp = [(1, 0), (0, 1), (-1, 0), (0, -1)]

def main():
    H, W = map(int, input().split())
    grid = []; cnt = 0
    grid.append(['
    for _ in range(H):
        tmp = list(input())
        cnt += sum([1 for x in tmp if x == '
        grid.append(['
    grid.append(['

    que = deque([(1, 1)])
    grid[1][1] = 1
    for _ in range(10000):
        a, b = que.popleft()
        for dx, dy in digtmp:
            x, y = (a + dx, b + dy)
            if grid[x][y] == '.':
                grid[x][y] = grid[a][b] + 1
                que.append((x, y))
        if len(que) == 0:
            break
    if grid[H][W] in ['
        print(-1)
        return
    ans = H*W - grid[H][W] - cnt
    print(ans)

if __name__ == "__main__":
    main()

Solution (Python):
def resolve():
    H, W = list(map(int, input().split()))
    C = [list(input()) for i in range(H)]
    passed = [[False for _ in range(W)] for _ in range(H)]
    import collections
    q = collections.deque([[0,0,1]])
    minhop = float("inf")    
    while q:
        y, x, cnt = q.popleft()
        if y == H-1 and x == W-1:
            minhop = min(minhop, cnt)
            continue
        if passed[y][x]:
            continue
        passed[y][x] = True
        for i, j in [[-1, 0], [1, 0], [0, 1], [0, -1]]:
            _y, _x = y+i, x+j
            if 0 <= _y < H and 0 <= _x < W and C[_y][_x] == ".":
                q.append([_y, _x, cnt+1])
    
    nblack = 0
    for i in range(H):
        for j in range(W):
            if C[i][j] == "
                nblack += 1
    print(H*W-minhop-nblack if minhop != float("inf") else -1)

if '__main__' == __name__:
    resolve()

Solution (Python):
h, w = map(int, input().split())
m = [['
for j in range(h):
    m[j+1][1:w+1] = list(input()) 

white = 0
for i in range(h+2):
    for j in range(w+2):
        if m[i][j] == '.':
            white += 1

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

seen = [[0] * (w+2) for i in range(h+2)]

todo = [[1, 1]]
seen[1][1] = 1
while(todo != []):
    v = todo.pop(0)
    for i in range(4):
        if m[v[0]+dx[i]][v[1]+dy[i]] != '
            seen[v[0]+dx[i]][v[1]+dy[i]] = seen[v[0]][v[1]] + 1
            todo.append([v[0]+dx[i], v[1]+dy[i]])
    
print(white-seen[h][w] if seen[h][w] else -1)

Solution (Python):
import numpy as np
import scipy.sparse as sps
import scipy.misc as spm
import collections as col
import functools as func
import itertools as ite
import fractions as frac
import math as ma
import cmath as cma
import copy as cp
import sys
def sinput(): return sys.stdin.readline().strip()
def iinput(): return int(sinput())
def imap(): return map(int, sinput().split())
def fmap(): return map(float, sinput().split())
def iarr(n=0):
    if n: return [0 for _ in range(n)]
    else: return list(imap())
def farr(): return list(fmap())
def sarr(n=0):
    if n: return ["" for _ in range(n)]
    else: return sinput().split()
def barr(n): return [False for _ in range(n)]
sys.setrecursionlimit(10**7)
MOD = 10**9 + 7; EPS = sys.float_info.epsilon
PI = np.pi; EXP = np.e; INF = np.inf


h,w = imap()
grid = [[1]*(w+2)] + [[1]+[int(elm == "

q = col.deque([(1,1)])
dep = col.defaultdict(int)
dep[(1,1)] = 1
while q:
    now = q.popleft()
    if now == (h,w): break
    x,y = now[0],now[1]
    for next in [(x,y+1),(x,y-1),(x+1,y),(x-1,y)]:
        nx,ny = next[0],next[1]
        if grid[nx][ny] or dep[next]: continue 
        else: dep[next] = dep[now] + 1; q.append(next)

ans = 0
for elm in grid: ans += elm.count(0)
ans = ans - dep[(h,w)] if dep[(h,w)] else -1
print(ans)

Solution (Python):
from collections import deque

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

G = []
G.append(["
for i in range(H):
    G.append(["
G.append(["



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

INF = 10 ** 18
d = [[INF for i in range(W + 2)] for j in range(H + 2)]


def bfs(i, j):
    q = deque()
    q.append((i, j))
    d[i][j] = 0
    while q:
        a, b = q.popleft()
        for k in range(4):
            if G[a + dx[k]][b + dy[k]] == "
                continue
            if d[a + dx[k]][b + dy[k]] != INF:
                continue
            d[a + dx[k]][b + dy[k]] = d[a][b] + 1
            q.append((a + dx[k], b + dy[k]))


bfs(1, 1)




if d[H][W] == INF: 
    print(-1)
else:
    ans = (H + 2) * (W + 2)
    ans -= d[H][W] + 1
    cnt = 0
    for h in range(H + 2):
        for w in range(W + 2):
            if G[h][w] == "
                cnt += 1
    ans -= cnt
    print(ans)

Solution (Python):
from collections import deque

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

cnt_white = 0
for path in field:
    cnt_white += path.count('.')

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

dyx = [(1, 0), (-1, 0), (0, 1), (0, -1)]
q = deque()
q.append((sy, sx, 0))

while q:
    cy, cx, ct = q.popleft()
    for dy, dx in dyx:
        ny, nx = cy + dy, cx + dx
        if ny < 0 or ny >= H or nx < 0 or nx >= W:
            continue
        if (ny, nx) == (gy, gx):
            print(cnt_white - (ct + 2)) 
            exit()
        if field[ny][nx] == '
            continue
        q.append((ny, nx, ct + 1))
        field[ny][nx] = '

print('-1')

Solution (Python):
import queue

h, w = map(int, input().split())
S = [input() for _ in range(h)]
n_black = 0
for s in S:
    n_black += s.count('

q = queue.Queue()
if S[0][0] == '.': 
    q.put((0, 0))
else: 
    print(-1)
    exit()

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

while True:
    i, j = q.get()

    for ni, nj in ((i-1, j), (i, j-1), (i, j+1), (i+1, j)):
        if ni < 0 or ni >= h or nj < 0 or nj >= w: continue
        if S[ni][nj] == '.' and dist[ni][nj] == -1:
            q.put((ni, nj))
            dist[ni][nj] = dist[i][j] + 1
    
    if q.empty(): break

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

Solution (Python):
from sys import stdin,setrecursionlimit
setrecursionlimit(10**6)
def S(): return stdin.readline().rstrip()
def LI(): return list(map(int,stdin.readline().rstrip().split()))

def BFS(table,s,step,next,w,h):
    if table[h-1][w-1] != -2:
        return
    dx = [1,0,-1,0]
    dy = [0,1,0,-1]
    nnext = []
    for rep in next:
        for j in range(4):
            nx = rep[0] + dx[j]
            ny = rep[1] + dy[j]
            if nx<0  or ny<0 or w<=nx or h<=ny:
                continue
            else:
                if s[ny][nx]=='
                    continue
                if table[ny][nx]==-2 or step+1<table[ny][nx]:
                    table[ny][nx] = step+1
                    nnext.append([nx,ny])
    if 0<len(nnext):
        BFS(table,s,step+1,nnext,w,h)

def main():
    tmp = LI()
    w,h = tmp.pop(),tmp.pop()
    s = [S() for _ in range(h)]
    table = [[-2]*w for _ in range(h)]
    BFS(table,s,0,[[0,0]],w,h)
    step = table[h-1][w-1]
    if step==-2:
        print(-1)
        exit()
    c = 0
    for rep in s:
        c += rep.count('
    ans = w*h-step-c-1
    print(ans)
    return

if __name__=='__main__':
    main()

Solution (Python):
from collections import deque


def main():
    H, W = map(int, input().rstrip().rsplit())

    visited = [[0]*(W+2) for i in range(H+2)]
    maze = [["

    black_cnt = 0
    for i in range(H):
        
        row = input().rstrip()
        black_cnt += row.count("

        
        row = "
        maze.append(list(row))

    maze.append(["

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

    while queue:
        x, y = queue.popleft()
        
        if maze[x][y] == "
            continue

        for dx, dy in [(1, 0), (-1, 0), (0, 1), (0, -1)]:
            
            if visited[x+dx][y+dy] > 0:
                continue
            
            visited[x+dx][y+dy] = visited[x][y] + 1

            
            queue.append((x+dx, y+dy))

    if visited[H][W] == 0:
        print(-1)
        return
    ans = H*W - black_cnt - visited[H][W] - 1
    print(ans)


if __name__ == "__main__":
    main()

Solution (Python):

from collections import deque
from copy import deepcopy

def parse():
  H, W = map(int, input().split(" "))
  grid = []
  grid.append(["
  for y in range(H):
    grid.append(list("
  grid.append(["
  return H, W, grid

def print_grid(grid):
  H = len(grid)
  W = len(grid[0])
  for y in range(H):
    for x in range(W):
      print(grid[y][x], end="")
    print("")
  print("")

def print_visited(visited):
  H = len(visited)
  W = len(visited[0])
  for y in range(H):
    for x in range(W):
      if visited[y][x]:
        print(1, end="")
      else:
        print(0, end="")
    print("")
  print("")

def print_grid_with_paths(grid, paths):
  H = len(grid)
  W = len(grid[0])
  for y in range(H):
    for x in range(W):
      if (x, y) in paths:
        print("*", end="")
      else:
        print(grid[y][x], end="")
    print("")
  print("")

def main():
  H, W, grid = parse()

  visited = [[False for x in range(W + 2)] for y in range(H + 2)]
  for y in range(H + 2):
    for x in range(W + 2):
      if x == 0 or x == W + 1 or y == 0 or y == H + 1:
        visited[y][x] = True
  visited[0][0] = True

  
  

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

  
  q = deque([(1, 1, [])])
  while len(q) > 0:
    x, y, paths = q.popleft()
    paths.append((x, y))
    
    
    
    
    if y == H and x == W:
      
      ans = 0
      for y in range(H + 2):
        for x in range(W + 2):
          
          if (x, y) in paths:
            continue

          if grid[y][x] == ".":
            ans += 1

      
      
      
      
      
      
      

      
      
      
      
      
          
      
      
      
      
      
      
      
      
      print(ans)
      exit(0)

    for vec in vecs:
      next_x = x + vec[0]
      next_y = y + vec[1]
      if grid[next_y][next_x] == "
        continue

      if not visited[next_y][next_x]:
        visited[next_y][next_x] = True
        q.append((next_x, next_y, deepcopy(paths)))

  print(-1)

if __name__ == "__main__":
  main()

Solution (Python):
def resolve():
    from collections import deque
    h, w = map(int, input().split())
    maze = [list(input()) for _ in range(h)]
    visited = [[-1]*w for _ in range(h)]
    nxt = [[0,0]]
    nxt = deque(nxt)
    visited[0][0] = 1
    while nxt:
        x, y = nxt.popleft()
        for i, j in ([1,0], [0,1], [-1,0], [0,-1]):
            nx = x+ i
            ny = y+j
            if 0 <= nx < h and 0 <= ny < w and visited[nx][ny]== -1 and maze[nx][ny] != "
                visited[nx][ny] = visited[x][y] + 1
                nxt.append([nx, ny])
    totalsharp = 0
    for i in range(h):
        for j in range(w):
            if maze[i][j] == "
                totalsharp += 1
    if visited[h-1][w-1] == -1:
        print(-1)
    else:
        print(h*w-totalsharp-visited[h-1][w-1])
resolve()

Solution (Python):
import sys
from collections import deque

readline = sys.stdin.readline
readall = sys.stdin.read
ns = lambda: readline().rstrip()
ni = lambda: int(readline().rstrip())
nm = lambda: map(int, readline().split())
nl = lambda: list(map(int, readline().split()))
prl = lambda x: print(*x ,sep='\n')

def bfs(start,end):
    tansaku = deque()
    tansaku.append(start)
    visited = {i:set() for i in range(h)}
    kyori = [[0]*w for _ in range(h)]
    while tansaku:
        pre_y,pre_x = tansaku.popleft()
        if pre_x in visited[pre_y]:
            continue
        for i in range(pre_x-1,pre_x+2,2):
            if 0 <= i <= w-1 and tizu[pre_y][i] == '.':
                tansaku.append([pre_y,i])
                kyori[pre_y][i] = kyori[pre_y][pre_x] + 1
        for j in range(pre_y-1,pre_y+2,2):
            if 0 <= j <= h-1 and tizu[j][pre_x] == '.':
                tansaku.append([j,pre_x])
                kyori[j][pre_x] = kyori[pre_y][pre_x] + 1
        visited[pre_y].add(pre_x)
        if [pre_y,pre_x] == end:
            return kyori[pre_y][pre_x]
    return -1



h,w = nm()
white = 0
tizu = []
for i in range(h):
    temp = list(input())
    white += temp.count('.')
    tizu.append(temp)
res = bfs([0,0],[h-1,w-1])
if res == -1:
    print(res)
else:
    print(white-(res+1))

Solution (Python):
from collections import deque
def main():
    H, W = list(map(int, input().split()))
    A = [['
    printl = lambda l: [print(x) for x in l]
    stack = deque([[1, 1], ])
    dxy = [[1, 0], [-1, 0], [0, 1], [0, -1]]
    INF = float('inf')
    L = [[INF] * W for _ in range(H)]
    visited = [[0] * W for _ in range(H)]
    L[0][0] = 1
    while stack:
        x, y = stack.popleft()
        if visited[x - 1][y - 1] == 1:
            continue
        visited[x - 1][y - 1] = 1
        for (dx, dy) in dxy:
            X = x + dx
            Y = y + dy
            if A[X][Y] == '
                continue
            if visited[X - 1][Y - 1] == 0:
                stack.append([X, Y])
            L[X - 1][Y - 1] = min(L[X - 1][Y - 1], L[x - 1][y - 1] + 1)
    ans = 0
    for a in A:
        for i in a:
            if i == '.':
                ans += 1
    if L[H - 1][W - 1] == INF:
        print(-1)
    else:
        print(ans - L[H - 1][W - 1])

if __name__ == '__main__':
    main()

Solution (Python):
import sys 
from collections import deque
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
H, W = map(int,readline().split())
grid = ['
for _ in range(H):
  grid += ['
grid += ['
 
dist = [-1]*((H+2)*(W+2)-1)
 
s = W + 3
g = (H+1)*(W+2)-2
 
def bfs():
  while q:
    x = q.popleft()
    if x == g:
      return
    for dx in (1,W+2,-1,-W-2):
      if dist[x+dx] == -1 and grid[x+dx] =='.':
        dist[x+dx] = dist[x]+1
        q.append(x+dx)

dist[s]=0
q = deque([(s)])
bfs()

if dist[g] ==-1:
  print(-1)
else:
  print(grid.count('.')-dist[g]-1)

Solution (Python):
from collections import deque
h,w=map(int,input().split())
s=[list(input()) for i in range(h)]
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]!="
                d[nx][ny]=d[p[0]][p[1]]+1
                que.append((nx,ny))
    return d[h-1][w-1]
ans=h*w
for i in range(h):
    for j in range(w):
        if s[i][j]=="
            ans-=1
if 0<bfs()<float("inf"):
    print(ans-bfs()-1)
else:
    print(-1)

Solution (Python):
from collections import deque
h,w = map(int,input().split())
d = [input() for i in range(h)]
count = 0
for i in range(h):
    for j in range(w):
        if d[i][j] == '
            count+=1
visited = [[0 for i in range(w)] for i in range(h)]
def bfs(sy,sx,gy,gx):
    que = deque()
    que.append((sy,sx))
    visited[sy][sx] = 0
    while que:
        y,x = que.popleft()
        if y == gy and x == gx:
            return visited[y][x]
        for dy,dx in [(-1,0),(1,0),(0,-1),(0,1)]:
            ny,nx = y+dy, x+dx
            if ny < 0 or nx < 0 or ny >= h or nx >= w:
                continue
            elif d[ny][nx] == '
                continue
            elif visited[ny][nx] != 0:
                continue
            else:
                visited[ny][nx] = visited[y][x] + 1
                que.append((ny,nx))
    return visited[gy][gx]
ans = bfs(0,0,h-1,w-1)
if ans == 0:
    print(-1)
    exit()
print(h*w - ans - count - 1)

Solution (Python):
h,w=map(int,input().split())
s=[list(input()) for _ in range(h)]
dy=[1, 0, -1, 0]
dx=[0, 1, 0 ,-1]

from collections import deque
d=[[-1]*w for _ in range(h)]
queue=deque()
queue.append((0,0))
d[0][0]=1

while queue:
    y,x=queue.popleft()
    for d_y, d_x in zip(dx,dy):
        new_y=y+d_y
        new_x=x+d_x
        if new_y<0 or h<=new_y or new_x<0 or w<=new_x:
            continue
        if s[new_y][new_x]=='.' and d[new_y][new_x]==-1:
            d[new_y][new_x]=d[y][x]+1
            queue.append((new_y, new_x))

ans=0
black=0
for i in range(h):
    for j in range(w):
        if s[i][j]=='
            black+=1

print(h*w-black-d[h-1][w-1] if d[h-1][w-1]!=-1 else -1)

Solution (Python):
from collections import deque

R,C=list(map(int,input().split()))
ans=[[0 for _ in range(C+2)] for _ in range(R+2)]
wall,flag = 0,False

maze=[['

for i in range(R+2):
  wall += maze[i].count('
wall = wall - ((R+2)*(C+2)-R*C)

vector=[(1,0),(0,1),(-1,0),(0,-1)]
road=deque()
road.append([1,1])

while road:
  ny,nx=road.popleft()
  for i,j in vector:
    my,mx=ny+i,nx+j
    if not ans[my][mx] and maze[my][mx] == ".":
      ans[my][mx] = ans[ny][nx]+1
      road.append([my,mx])
      if my == R and mx == C:
        root=ans[my][mx]+1
        print(R*C-wall-root)
        exit()
        
if not flag:
  print("-1")

Solution (Python):


import sys
from collections import deque
input=sys.stdin.readline

def main():
    H,W=map(int,input().split())
    mas=[input() for i in range(H)]
    dist=[[-1]*W for i in range(H)]
    sharps=0
    for row in mas:
        sharps+=row.count("
    qu=deque([(0,0)])
    dist[0][0]=1
    d=((-1,0),(1,0),(0,-1),(0,1))
    qup=qu.popleft
    qua=qu.append
    while(len(qu)>0):
        v=qup()
        for di in d:
            nv=(v[0]+di[0],v[1]+di[1])
            if not(0<=nv[0]<H) or not(0<=nv[1]<W) or mas[nv[0]][nv[1]]=="
                continue
            else:
                dist[nv[0]][nv[1]]=dist[v[0]][v[1]]+1
                qua(nv)
    ms=dist[H-1][W-1]
    if ms==-1:
        print(ms)
    else:
        print(H*W-sharps-ms)
    
    
    
    
if __name__=="__main__":
    main()

Solution (Python):
from collections import deque

INF = float('inf')
H, W = map(int, input().split())
grid = [str(input()) for _ in range(H)]
d = [[-1] * W for _ in range(H)]
d[0][0] = 0
dh = [1, -1, 0, 0]
dw = [0, 0, 1, -1]
q = deque([[0, 0]])
while q:
    h, w = q.popleft()
    for i in range(4):
        nh = h + dh[i]
        nw = w + dw[i]
        if 0 <= nh < H and 0 <= nw < W and d[nh][nw] < 0:
            if grid[nh][nw] == '
                d[nh][nw] = INF
            else:
                d[nh][nw] = d[h][w] + 1
                q.append([nh, nw])
if d[H-1][W-1] == -1:
    print(-1)
else:
    cnt = 0
    for i in range(H):
        cnt += grid[i].count('.')
    print(cnt - d[H-1][W-1] - 1)

Solution (Python):
from collections import deque
from copy import deepcopy
def main():
    h, w = map(int, input().split())
    maze = {}
    white_cell = 0  
    for i1 in range(h):
        mazerow = input()
        for i2 in range(w):
            if mazerow[i2] == '.':
                maze[(i1, i2)] = 0  
                white_cell += 1
            else:
                maze[(i1, i2)] = -1  

    vx = (0, 0, 1, -1)
    vy = (1, -1, 0, 0)
    cnt = 1
    next_nodes = deque()
    next_nodes.append((0, 0))
    next2_nodes = deque()
    """
    方針：
    mazeをBFSで更新し「ゴール到達可否」「最短路」を求める。
    ゴール到達可なら「白いマスの数 - スタートとゴールを含む再短路のマス数」が
    塗ることのできる黒いマス数になる。
    (0,0)からの距離cntを１で開始し、１ずつカウントアップして更新してmapの各マスにいれる。
    ゴールセルに入った数が「スタートとゴールを含む再短路のセル数」になる。
    """
    while next_nodes:
        while next_nodes:
            nextn = next_nodes.popleft()
            nextny = nextn[0]
            nextnx = nextn[1]
            for j1 in range(4):
                ny = nextny + vy[j1]
                nx = nextnx + vx[j1]
                if ny == -1 or ny == h or nx == -1 or nx == w:
                    continue
                elif maze[(ny, nx)] == 0:
                    next2_nodes.append((ny, nx))
                    
                    maze[(ny, nx)] = cnt + 1
        cnt += 1
        next_nodes = deepcopy(next2_nodes)
        next2_nodes = deque()

    """
    結果出力。maze[(h-1, w-1)]が0のままなら「ゴール到達不可」なので-1、
    そうではないなら「黒にできるマスの数」をprint
    """
    if maze[(h-1, w-1)] == 0:
        print(-1)
    else:
        r = white_cell - maze[(h-1, w-1)]
        print(r)

if __name__ == '__main__':
    main()

Solution (Python):
from collections import deque


def main():
    H, W = map(int, input().split())
    maze = []
    wn = 0
    for _ in range(H):
        maze.append(input())
        wn += maze[-1].count(".")
    pc = -1
    que = deque([(0, 0, 1)])
    visited = {(0, 0)}
    while que:
        y, x, d = que.popleft()
        if y == H-1 and x == W-1:
            pc = d
        for dy, dx in moves:
            ny, nx = y+dy, x+dx
            if 0 <= ny < H and 0 <= nx < W and maze[ny][nx] == "." and (ny, nx) not in visited:
                que.append((ny, nx, d+1))
                visited.add((ny, nx))
    if pc == -1:
        print(-1)
    else:
        print(wn-pc)


if __name__ == "__main__":
    moves = [(1, 0), (-1, 0), (0, 1), (0, -1)]
    main()

Solution (Python):
from collections import deque
import sys

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

kuro = 0
for g in grid:
    kuro += g.count("

q = deque([[0, 0]])
grid[0][0] = 1
moves = [[1, 0], [-1, 0], [0, 1], [0, -1]]

while q:
    cx, cy = q.popleft()
    for m in moves:
        nx, ny = cx + m[0], cy + m[1]
        if nx < 0 or nx > h - 1 or ny < 0 or ny > w - 1:
            continue
        elif grid[nx][ny] == "
            continue
        elif grid[nx][ny] == ".":
            grid[nx][ny] = grid[cx][cy] + 1
            q.append([nx, ny])
            if nx == h - 1 and ny == w - 1:
                print(h * w - grid[nx][ny] - kuro)
                sys.exit()
else:
    print(-1)

Solution (Python):
from collections import deque
import sys

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

kuro = 0
for g in grid:
    kuro += g.count("

q = deque([[0, 0]])
grid[0][0] = 1
moves = [[1, 0], [-1, 0], [0, 1], [0, -1]]

while q:
    cx, cy = q.popleft()
    for m in moves:
        nx, ny = cx + m[0], cy + m[1]
        if nx < 0 or nx > h - 1 or ny < 0 or ny > w - 1:
            continue
        elif grid[nx][ny] == "
            continue
        elif grid[nx][ny] == ".":
            grid[nx][ny] = grid[cx][cy] + 1
            q.append([nx, ny])
            if nx == h - 1 and ny == w - 1:
                print(h * w - grid[nx][ny] - kuro)
                sys.exit()
else:
    print(-1)

Solution (Python):
from collections import deque

def bfs(maze, sy, sx):
    gy, gx = H - 1, W - 1
    q = deque()
    q.append((sy, sx))
    visited[sy][sx] = 1
    
    now = 0
    while q:
      y, x = q.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 - 1) and (0 <= new_x <= W - 1):
          if maze[new_y][new_x] == "." and visited[new_y][new_x] > 10 ** 5:
            visited[new_y][new_x] = visited[y][x] + 1
            q.append((new_y, new_x))
    return 0

          
if __name__ == "__main__":
    H, W = map(int, input().split())
    maze = [[0] * W for i in range(H)]
    count = 0
    for i in range(H):
      s = str(input())
      for j in range(W):
        maze[i][j] = s[j]
        if s[j] == ".":
          count += 1
    visited = [[float("inf")] * W for j in range(H)]
    ans = bfs(maze, 0, 0)
    if ans == 0:
      print(-1)
    else:
      print(count - ans)

Solution (Python):
from collections import deque

def bfs(maze, sy, sx):
    gy, gx = H - 1, W - 1
    q = deque([[sy, sx]])
    visited[sy][sx] = 1
    
    now = 0
    while q:
      y, x = q.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 - 1) and (0 <= new_x <= W - 1):
          if maze[new_y][new_x] == "." and visited[new_y][new_x] > 10 ** 5:
            visited[new_y][new_x] = visited[y][x] + 1
            q.append([new_y, new_x])
    return 0

          
if __name__ == "__main__":
    H, W = map(int, input().split())
    maze = [[0] * W for i in range(H)]
    count = 0
    for i in range(H):
      s = str(input())
      for j in range(W):
        maze[i][j] = s[j]
        if s[j] == ".":
          count += 1
    visited = [[float("inf")] * W for j in range(H)]
    ans = bfs(maze, 0, 0)
    if ans == 0:
      print(-1)
    else:
      print(count - ans)