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(h, w, board, start, goal):

    bfs_deque = deque()
    bfs_deque.append(start)

    dx = [1, 0, -1, 0]
    dy = [0, 1, 0, -1]
    x, y = start
    reached_area[y][x] = 0

    min_distance = INF

    while len(bfs_deque) > 0:

        coord = bfs_deque.popleft()
        x, y= coord

        if coord == goal:
            
            if min_distance > reached_area[y][x]:
                min_distance = reached_area[y][x]


        
        for i in range(len(dx)):
            nx = x + dx[i]
            ny = y + dy[i]

            
            if 0 <= nx < w and 0 <= ny < h and board[ny][nx] != "
                
                reached_area[ny][nx] = reached_area[y][x] + 1
                
                bfs_deque.append([nx, ny])

    if min_distance != INF:
        return min_distance
    else:
        return -1


h, w = map(int, input().split())
board = [input().rstrip() for i in range(h)]

start = [0, 0]
goal = [w-1, h-1]

movable_area_count = 0
INF = 999
reached_area = [[INF for i in range(w)] for j in range(h)]


for i in range(h):
    for j in range(w):
        if board[i][j] == ".":
            movable_area_count += 1


min_distance = bfs(h, w, board, start, goal)

if min_distance != -1:
    print(movable_area_count - min_distance -1)
else:
    print(min_distance)

Solution (Python):
h,w=map(int,input().split())
a=[input() for _ in range(h)]
b=[[h*w]*w for _ in range(h)]
b[0][0]=1
d=[(0,0)]
while d:
    y,x=d.pop(0)
    for i,j in([1,0],[-1,0],[0,1],[0,-1]):
        t,u=y+i,x+j
        if h>t>=0<=u<w and a[t][u]=="." and b[t][u]>b[y][x]+1:
            d+=[(t,u)]
            b[t][u]=b[y][x]+1
print(max(-1,sum([i.count(".") for i in a])-b[-1][-1]))

Solution (Python):
from collections import *
h,w=map(int,input().split())
a=[input() for _ in range(h)]
b=[[h*w]*w for _ in range(h)]
b[0][0]=1
d=deque([[0,0]])
while d:
    y,x=d.popleft()
    for i,j in([1,0],[-1,0],[0,1],[0,-1]):
        t,u=y+i,x+j
        if h>t>=0<=u<w:
            if a[t][u]=="." and b[t][u]>b[y][x]+1:
                d.append([t,u])
                b[t][u]=b[y][x]+1
print(max(-1,sum([i.count(".") for i in a])-b[-1][-1]))

Solution (Python):
from collections import *
h,w=map(int,input().split())
a=[input() for _ in range(h)]
b=[[h*w]*w for _ in range(h)]
b[0][0]=1
d=deque([[0,0]])
while d:
    y,x=d.popleft()
    for i,j in([1,0],[-1,0],[0,1],[0,-1]):
        t,u=y+i,x+j
        if 0<=t<h and 0<=u<w:
            if a[t][u]=="." and b[t][u]>b[y][x]+1:
                d.append([t,u])
                b[t][u]=b[y][x]+1
c=sum([i.count(".") for i in a])
print(max(-1,c-b[-1][-1]))

Solution (Python):
from collections import *
h,w=map(int,input().split())
a=[input() for _ in range(h)]
b=[[h*w]*w for _ in range(h)]
b[0][0]=1
d=deque([[0,0]])
while d:
    y,x=d.pop()
    if y<h-1:
        if a[y+1][x]=="." and b[y+1][x]>b[y][x]+1:
            d.append([y+1,x])
            b[y+1][x]=b[y][x]+1
    if x<w-1:
        if a[y][x+1]=="." and b[y][x+1]>b[y][x]+1:
            d.append([y,x+1])
            b[y][x+1]=b[y][x]+1
    if y>0:
        if a[y-1][x]=="." and b[y-1][x]>b[y][x]+1:
            d.append([y-1,x])
            b[y-1][x]=b[y][x]+1
    if x>0:
        if a[y][x-1]=="." and b[y][x-1]>b[y][x]+1:
            d.append([y,x-1])
            b[y][x-1]=b[y][x]+1
c=sum([i.count(".") for i in a])
print(max(-1,c-b[-1][-1]))

Solution (Python):
h,w = map(int,input().split())
s = [0]*(h+2)
for i in range(1,h+1):
    s[i] = ["
s[0] = ["
s[-1] = ["

from collections import deque
qx = deque([])
qy = deque([])
qx.append(1)
qy.append(1)
r = [[0 for j in range(w+2)] for i in range(h+2)]
r[1][1] = 1
ans = 0
while qx:
    x = qx.popleft()
    y = qy.popleft()
    
    if s[x-1][y] == "." and r[x-1][y] == 0:
        qx.append(x-1)
        qy.append(y)
        r[x-1][y] = r[x][y] + 1
    if s[x+1][y] == "." and r[x+1][y] == 0:
        qx.append(x+1)
        qy.append(y)
        r[x+1][y] = r[x][y] + 1
    if s[x][y-1] == "." and r[x][y-1] == 0:
        qx.append(x)
        qy.append(y-1)
        r[x][y-1] = r[x][y] + 1
    if s[x][y+1] == "." and r[x][y+1] == 0:
        qx.append(x)
        qy.append(y+1)
        r[x][y+1] = r[x][y] + 1

c = 0
for i in range(h+2):
    for j in range(w+2):
        if s[i][j] == ".":
            c += 1
if r[h][w] != 0:    
    print(c-r[h][w])
else:
    print(-1)

Solution (Python):
from collections import deque

h ,w = map(int, input().split())
s = ['$'*(w+2)] * (h+2)
cnt = 0
for i in range(1,h+1):
    s[i] = '$' + input() + '$'
    cnt += s[i].count('.')

dist = [[-1]*(w+2) for _ in range(h+2)] 
dist[1][1] = 0 
q = deque()
q.append((1,1))
while q:
    x, y = q.popleft() 

    vx = [-1,0,1,0]
    vy = [0,-1,0,1]
    for i in range(4):
        nx = x + vx[i]
        ny = y + vy[i]
        if s[nx][ny] == '$' or s[nx][ny] == '
        if dist[nx][ny] != -1: continue 
        dist[nx][ny] = dist[x][y] + 1
        q.append((nx, ny)) 

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

Solution (Python):
h,w = map(int,input().split())
s = [input() for _ in range(h)]

from collections import deque

ans = 0
stack = deque([[0,0,1]])
dxdy = [(0,1),(0,-1),(1,0),(-1,0)]
visited = [[0 for i in range(w)] for j in range(h)]
minus = 0
for i in range(h):
    for j in range(w):
        if s[i][j] == "
            visited[i][j] = 1
            minus += 1


ans = -1
while(stack):
    ne = stack.popleft()
    x,y = ne[0],ne[1]
    if x < 0 or x > h-1: continue
    if y < 0 or y > w-1: continue
    if visited[x][y] == 1: continue
    if x== h -1 and y == w-1:
        ans = h*w - ne[2] - minus

    visited[x][y] = 1

    for dx,dy in dxdy:
        stack.append([dx+x,dy+y,ne[2]+1])

print(ans)

Solution (Python):
import copy
from collections import deque
H, W = map(int, input().split())
s = [list(input()) for _ in range(H)]
route = [[0, 0]]
visited = copy.deepcopy(s)
visited[0][0] = '
q = deque([[0, 0, route]])
score = -1

while q:
    y, x, route = q.popleft()
    r = copy.deepcopy(route)
    if [y, x] == [H-1, W-1]:
        score = sum(len(l) for l in s) - (sum(l.count('
        break
    if y > 0 and visited[y-1][x] == '.':
        visited[y-1][x] = '
        r.append([y-1, x])
        q.append([y-1, x, r])
        r = copy.deepcopy(route)
    if y < H-1 and visited[y+1][x] == '.':
        visited[y+1][x] = '
        r.append([y+1, x])
        q.append([y+1, x, r])
        r = copy.deepcopy(route)
    if x > 0 and visited[y][x-1] == '.':
        visited[y][x-1] = '
        r.append([y, x-1])
        q.append([y, x-1, r])
        r = copy.deepcopy(route)
    if x < W-1 and visited[y][x+1] == '.':
        visited[y][x+1] = '
        r.append([y, x+1])
        q.append([y, x+1, r])
        r = copy.deepcopy(route)

print(score)

Solution (Python):
from collections import deque
def main():
  h,w = map(int,input().split())
  s = [input() for _ in range(h)]
  
  
  def bfs(st):
    que = deque([st])
    c = [[0]*w for _ in range(h)]
    while que:
      ph,pw = que.popleft()
      step = c[ph][pw] + 1
      for dh,dw in ((1,0),(0,1),(-1,0),(0,-1)):
        nh = ph+dh
        nw = pw+dw
        if nh<0 or nw<0 or nh>=h or nw>=w:
          continue
        if s[nh][nw]=="
          continue
        c[nh][nw] = step
        if (nh,nw) == (h-1,w-1):
          return step
        que.append((nh,nw))
  
  result = bfs((0,0))
  if result:
    return sum([i.count(".") for i in s])-result-1
  else:
    return -1

print(main())

Solution (Python):
h,w = map(int,input().split())
s = [input() for i in range(h)]
reach = [[0]*w for i in range(h)]
reach[0][0]=1
from collections import deque
q = deque([(0,0)])

goal = False
while q:
    x,y = q.popleft()
    for i,j in [[1,0],[-1,0],[0,1],[0,-1]]:
        if 0<=x+i<h and 0<=y+j<w:
            if reach[x+i][y+j]==0 and s[x+i][y+j]=='.':
                reach[x+i][y+j] = reach[x][y]+1
                if x+i==h-1 and y+j==w-1:
                    goal = True
                    break
                q.append([x+i,y+j])

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

if goal:
    print(c-reach[h-1][w-1])
else:
    print(-1)

Solution (Python):






import sys
input = sys.stdin.readline

import math

import bisect
from collections import defaultdict
from collections import deque
from functools import lru_cache






MOD = 10**9+7
INF = float('inf')






def I(): return int(input().strip())
def S(): return input().strip()
def IL(): return list(map(int,input().split()))
def SL(): return list(map(str,input().split()))
def ILs(n): return list(int(input()) for _ in range(n))
def SLs(n): return list(input().strip() for _ in range(n))
def ILL(n): return [list(map(int, input().split())) for _ in range(n)]
def SLL(n): return [list(map(str, input().split())) for _ in range(n)]


def P(arg): print(arg); return
def Y(): print("Yes"); return
def N(): print("No"); return
def E(): exit()
def PE(arg): print(arg); exit()
def YE(): print("Yes"); exit()
def NE(): print("No"); exit()


def DD(arg): return defaultdict(arg)



def inv(n): return pow(n, MOD-2, MOD)


kaijo_memo = []
def kaijo(n):
  if(len(kaijo_memo) > n):
    return kaijo_memo[n]
  if(len(kaijo_memo) == 0):
    kaijo_memo.append(1)
  while(len(kaijo_memo) <= n):
    kaijo_memo.append(kaijo_memo[-1] * len(kaijo_memo) % MOD)
  return kaijo_memo[n]

gyaku_kaijo_memo = []
def gyaku_kaijo(n):
  if(len(gyaku_kaijo_memo) > n):
    return gyaku_kaijo_memo[n]
  if(len(gyaku_kaijo_memo) == 0):
    gyaku_kaijo_memo.append(1)
  while(len(gyaku_kaijo_memo) <= n):
    gyaku_kaijo_memo.append(gyaku_kaijo_memo[-1] * pow(len(gyaku_kaijo_memo),MOD-2,MOD) % MOD)
  return gyaku_kaijo_memo[n]

def nCr(n,r):
  if(n == r):
    return 1
  if(n < r or r < 0):
    return 0
  ret = 1
  ret = ret * kaijo(n) % MOD
  ret = ret * gyaku_kaijo(r) % MOD
  ret = ret * gyaku_kaijo(n-r) % MOD
  return ret


def factorization(n):
  arr = []
  temp = n
  for i in range(2, int(-(-n**0.5//1))+1):
    if temp%i==0:
      cnt=0
      while temp%i==0: 
        cnt+=1 
        temp //= i
      arr.append([i, cnt])
  if temp!=1:
    arr.append([temp, 1])
  if arr==[]:
    arr.append([n, 1])
  return arr


def make_divisors(n):
  divisors = []
  for i in range(1, int(n**0.5)+1):
    if n % i == 0:
      divisors.append(i)
      if i != n // i: 
        divisors.append(n//i)
  return divisors


def gcd(a, b):
    while b:
        a, b = b, a % b
    return a


def lcm(a, b):
    return a * b // gcd (a, b)


def count_bit(n):
  count = 0
  while n:
    n &= n -1
    count += 1
  return count


def base_10_to_n(X, n):
  if X//n:
    return base_10_to_n(X//n, n)+[X%n]
  return [X%n]

def base_n_to_10(X, n):
  return sum(int(str(X)[-i-1])*n**i for i in range(len(str(X))))


def int_log(n, a):
  count = 0
  while n>=a:
    n //= a
    count += 1
  return count





H,W = IL()
maze = SLs(H)

count = 0
for item in maze:
  for i in item:
    if i == ".":
      count += 1
      
dx = [0,0,1,-1]
dy = [1,-1,0,0]

d = [[-1 for j in range(W)] for i in range(H)] 
d[0][0] = 0
q = deque([(0,0)])
while q:
  x,y = q.popleft()
  for i in range(4):
    nx = x + dx[i]
    ny = y + dy[i]
    if 0<=nx<W and 0<=ny<H:
      if maze[ny][nx] == ".":
        if d[ny][nx] == -1:
          d[ny][nx] = d[y][x] + 1
          q.append((nx,ny))
if d[H-1][W-1] == -1:
  print(-1)
else:
  print(count- d[H-1][W-1] -1)

Solution (Python):
from collections import deque
h, w = map(int, input().split())
maze = [input() for _ in range(h)]
dist = [[99999] * w for _ in range(h)]
kuromasu_count = 0
for i in maze:
    kuromasu_count += i.count("

def bfs(x, y):
    q = deque()
    q.append((x, y))
    while q:
        x, y = q.popleft()    
        for dx, dy in [(0,1),(1,0),(0,-1),(-1,0)]:
            nx = x + dx
            ny = y + dy 
            if not 0 <= nx < h or not 0 <= ny < w:
                continue
            if maze[nx][ny] == "
                continue
            if dist[nx][ny] != 99999:
                continue      
            dist[nx][ny] = dist[x][y] + 1            
            q.append((nx, ny))



dist[0][0] = 0
goal_x, goal_y = h-1, w-1
bfs(0, 0)
shiromasu = dist[goal_x][goal_y]
if shiromasu == 99999:
    print("-1")
else:
    answer = h * w - (shiromasu + 1) - kuromasu_count
    print(answer)

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

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

sharp_num = 0
for y in range(h):
    for x in range(w):
        if m[y][x] == '
            sharp_num += 1

def bfs(s):
    que = deque([s])
    log = [[0]*w for _ in range(h)]
    while len(que):
        y,x = que.popleft()
        for dy, dx in [(1,0),(-1,0),(0,1),(0,-1)]:
            ny = y + dy
            nx = x + dx
            if not (0<=ny<h and 0<=nx<w) or m[ny][nx] == '
                continue
            log[ny][nx] = log[y][x] + 1
            if (ny,nx) == (h-1, w-1):
                return log[ny][nx]

            que.append((ny,nx))

    return 0

result = bfs((0,0))

if result:
    print(h*w - sharp_num - (result+1))
else:
    print('-1')

Solution (Python):
from collections import deque

icase=0
if icase==0:
    r,c=map(int,input().split())




    xy=[["
    for i in range(1,r+1):
        xy[i]=["
elif icase==1:
    c,r=3,3       
    xy=[["
        ["
        ["
        ["
        ["

sc=[0,1,-1,0]
sr=[1,0,0,-1]
        
g=[[[] for j in range(c+2)] for i in range(r+2)]

for ri in range(1,r+1):
    for ci in range(1,c+1):
        if xy[ri][ci]==".":
            for i in range(4):
                if xy[ri+sr[i]][ci+sc[i]]==".":
                    g[ri][ci].append((ri+sr[i],ci+sc[i]))


sy,sx=1,1
gy,gx=r,c

q=deque()
q.append((sy,sx))

parent=[[-1]*(c+2) for i in range(r+2)]
parent[sy][sx]=0
dist=[[-1]*(c+2) for i in range(r+2)]
dist[sy][sx]=1
yn=""
while q:
    sty,stx = q.popleft()
    for vy,vx in g[sty][stx]:
        xy[vy][vx]=-1
        if vy==gy and vx==gx:
            parent[vy][vx]=(sty,stx)
            dist[vy][vx]=dist[sty][stx]+1
            yn="yes"
            break
        elif parent[vy][vx] !=-1:
            continue
        else:
            parent[vy][vx]=(sty,stx)
            dist[vy][vx]=dist[sty][stx]+1
            q.append((vy,vx))

    if yn=="yes":
        break

if yn!="yes":
    print(-1)
else:
    icnt=0
    for ri in range(1,r+1):
        for ci in range(1,c+1):
            if xy[ri][ci]=="." or xy[ri][ci]==-1:
                icnt+=1
    print(icnt-dist[gy][gx])

Solution (Python):
from collections import deque

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

whites = 0
for s in S:
    for w in s:
        if w == ".":
            whites += 1


def BFS(cur):
    
    x_path = [-1,0,1,0]
    y_path = [0,-1,0,1]

    q = deque()
    q.append(cur)
    while True:
        if len(q) == 0:
            break
        cur = q.popleft()
        if cur == (H,W):
            break

        for x,y in zip(x_path, y_path):
            nex = (cur[0] + x, cur[1] + y)
            if nex[0] < 1 or nex[0] > H or nex[1] < 1 or nex[1] > W:
                continue
            if S[nex[0]-1][nex[1]-1] == "
                continue
            if dist[nex[0]-1][nex[1]-1] > 0:
                continue

            dist[nex[0]-1][nex[1]-1] = dist[cur[0]-1][cur[1]-1] + 1 
            q.append(nex)


BFS((1,1))
if dist[H-1][W-1] == 0:
    print(-1)
else:
    print(whites - dist[H-1][W-1])

Solution (Python):
from copy import deepcopy
from collections import deque
import sys

M = []
H = 0
W = 0
qx = deque()
qy = deque()
qc = deque()

def main():
    global M,H,W
    H,W = map(int, input().split())  
    for i in range(H):
        M.append(list(input()))

    startX = 0
    startY = 0
    dot = 0
    for i in range(H):
        for j in range(W):
            if M[i][j]=='.':
                dot += 1
    
    cnt = bfs(0,0)
    if(cnt>=0):
        print(dot-cnt)
    else:
        print(-1)

def bfs(y,x):
    global M,H,W
    Mtemp = deepcopy(M)
    Mtemp[y][x] = '
    qx.append(x)
    qy.append(y)
    qc.append(1)

    while len(qx) !=0:
        x =  qx.popleft()
        y =  qy.popleft()
        cnt = qc.popleft()
        if(x==W-1 and y==H-1):
            return cnt

        if x-1>=0:
            if Mtemp[y][x-1] == '.':
                Mtemp[y][x-1] = '
                qx.append(x-1)
                qy.append(y)
                qc.append(cnt+1)
        if x+1<W:
            if Mtemp[y][x+1] == '.':
                Mtemp[y][x+1] = '
                qx.append(x+1)
                qy.append(y)
                qc.append(cnt+1)
        if y-1>=0:
            if Mtemp[y-1][x] == '.':
                Mtemp[y-1][x] = '
                qx.append(x)
                qy.append(y-1)
                qc.append(cnt+1)
        if y+1<H:
            if Mtemp[y+1][x] == '.':
                Mtemp[y+1][x] = '
                qx.append(x)
                qy.append(y+1)
                qc.append(cnt+1)

    return -1




if __name__ == '__main__':
    main()

Solution (Python):
h,w = map(int,input().split())
u = [list(input()) for _ in range(h)]

from collections import deque
q = deque([(0,0)])
dist = [[-1]*w for _ in range(h)]
dist[0][0]=0

while q:
    (i,j) = q.popleft()
    if 0<=i-1<h:
        if u[i-1][j]=='.' and dist[i-1][j]==-1:
            q.append((i-1,j))
            dist[i-1][j]=dist[i][j]+1
    if 0<=i+1<h:
        if u[i+1][j]=='.' and dist[i+1][j]==-1:
            q.append((i+1,j))
            dist[i+1][j]=dist[i][j]+1
    if 0<=j-1<w:
        if u[i][j-1]=='.' and dist[i][j-1]==-1:
            q.append((i,j-1))
            dist[i][j-1]=dist[i][j]+1
    if 0<=j+1<w:
        if u[i][j+1]=='.' and dist[i][j+1]==-1:
            q.append((i,j+1))
            dist[i][j+1]=dist[i][j]+1

count=0
for i in range(h):
    for j in range(w):
        if u[i][j]=='.':
            count+=1
if dist[h-1][w-1]==-1:
    print(-1)
else:
    print(count-dist[h-1][w-1]-1)

Solution (Python):
h,w=map(int,input().split())
cnt=0
s=[input() for _ in range(h)]
for x in s:
	cnt+=x.count(".")
ans=0
inf=10**8
dp=[[inf]*w for _ in range(h)]
dp[0][0]=0
from collections import deque
queue=deque([(0,0)])
d=((0,1),(0,-1),(1,0),(-1,0))
while queue:
	r=queue.popleft()
	for x in d:
		xx=r[0]+x[0];yy=r[1]+x[1]
		if 0<=xx<h and 0<=yy<w:
			if s[xx][yy]=="." and dp[xx][yy]==inf:
				dp[xx][yy]=dp[r[0]][r[1]]+1
				queue.append((xx,yy))
if dp[-1][-1]==inf:
	print(-1)
	exit()
print(cnt-dp[-1][-1]-1)

Solution (Python):

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

s = []
bl = 0

for i in range(H):

    tmp = list(input())
    s.append(tmp)

for i in range(H):

    for j in range(W):

        if s[i][j] == "
            bl += 1

d = [[float("inf")] * W for i in range(H)]
d[0][0] = 1

from collections import deque
q = deque([(0,0)])

while len(q) > 0:

    now = q.popleft()
    x,y = now

    if s[x][y] == "
        continue

    if x != 0 and d[x-1][y] > d[x][y] + 1:
        d[x-1][y] = d[x][y] + 1
        q.append( (x-1,y) )

    if x != H-1 and d[x+1][y] > d[x][y] + 1:
        d[x+1][y] = d[x][y] + 1
        q.append( (x+1,y) )

    if y != 0 and d[x][y-1] > d[x][y] + 1:
        d[x][y-1] = d[x][y] + 1
        q.append( (x,y-1) )

    if y != W-1 and d[x][y+1] > d[x][y] + 1:
        d[x][y+1] = d[x][y] + 1
        q.append( (x,y+1) )

if d[-1][-1] == float("inf"):
    print (-1)
else:
    print (H*W - bl - d[-1][-1])

Solution (Python):
from collections import deque

H, W = list(map(int,input().split()))
s = []
for i in range(H):
    s.append(input())
    
dx = [1, 0, -1, 0]
dy = [0, 1, 0, -1]
sx, sy = 0, 0
gx, gy = W - 1, H - 1

def bfs():
    q = deque([])
    d = [[-1 for _ in range(W)] for _ in range(H)]
    q.append([sx, sy])
    d[sy][sx] = 0
    
    while(q):
        pop = q.popleft()
        x, y = pop[0], pop[1]
        if x == gx and y == gy:
            break
        for i in range(4):
            nx = x + dx[i]
            ny = y + dy[i]
            if 0 <= nx and nx < W and ny >= 0 and ny < H:
                if s[ny][nx] != "
                    q.append([nx, ny])
                    d[ny][nx] = d[y][x] + 1
    return d[gy][gx]
                
ret = bfs()   

count = 0
for i in range(W):
    for j in range(H):
        if s[j][i] == "
            count += 1           
        
ans = H * W - (ret - 1) - count - 2
if ret == -1:
  	print(-1)
else:
	print(ans)

Solution (Python):
import sys
from collections import deque
H,W=map(int,input().split())
map = [[i for i in map(str,sys.stdin.readline().rstrip())] for _ in range(H)]
count_dot = 0
dist = [[0]*W for _ in range(H)]
for i in range(H):
  for j in range(W):
    if map[i][j] == '.':
      count_dot +=1
def bfs():
  while q:
    x,y = q.popleft()
    if x == H-1 and y ==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 0 <= nx < H and 0 <= ny < W and map[nx][ny]=='.' and dist[nx][ny] == 0:
        q.append((nx,ny))
        dist[nx][ny] = dist[x][y] + 1
q = deque()
q.append((0,0))
bfs()
dist_min = dist[H-1][W-1]
if dist_min ==0:
  print(-1)
else:
  print(count_dot-dist_min-1)

Solution (Python):
from collections import deque

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

maze = []
white_count = 0
for _ in range(H):
    line = list(input())
    white_count += line.count('.')
    maze.append(line)

queue = deque()
queue.append((0, 0, 1))

min_step = -1
while len(queue) > 0:
    y, x, step = queue.popleft()
    if maze[y][x] != '.':
        continue
    else:
        maze[y][x] = '

    if y == H - 1 and x == W - 1:
        min_step = step
        break

    for dy, dx in [(-1, 0), (1, 0), (0, -1), (0, 1)]:
        ny = y + dy
        nx = x + dx

        if 0 <= ny < H and 0 <= nx < W:
            queue.append((ny, nx, step + 1))

if min_step == -1:
    print(min_step)
else:
    print(white_count - min_step)

Solution (Python):
from collections import deque
h,w=map(int,input().split())
ttt=0
d=["
c=[]
for i in range(h):
    ca=input()
    ttt+=ca.count("
    ca=list(ca)
    b=["
    b.extend(ca)
    b.extend(d)
    c.append(b)
c.insert(0,['
c.append(['


kouho=deque([[1,1]])
kouho2=deque([])
ans=0
for _ in range(10**9):
    if kouho==deque([]):
        ans+=1
        if kouho2==deque([]):
            print(-1)
            exit()
        kouho=kouho2
        
        kouho2=deque([])
    a,b=kouho.popleft()
    
    if a==h and b==w:
        print(h*w-ans-1-ttt)
        exit()
    if c[a][b]=='.':
        c[a][b]='
        kouho2.append([a,b-1])
        kouho2.append([a-1,b])
        kouho2.append([a+1,b])
        kouho2.append([a,b+1])

Solution (Python):


import sys








from collections import deque                





















def main():
    mod = 1000000007                
    inf = float('inf')              
    
    sys.setrecursionlimit(10**6)    
    def input(): return sys.stdin.readline().rstrip()
    def ii():    return int(input())
    def mi():    return map(int, input().split())
    def mi_0():  return map(lambda x: int(x)-1, input().split())
    def lmi():   return list(map(int, input().split()))
    def lmi_0(): return list(map(lambda x: int(x)-1, input().split()))
    def li():    return list(input())


    dx = [1, 0, -1, 0]
    dy = [0, 1, 0, -1]
    def bfs(current):
        q = deque()
        q.append([current, 1])
        while q:
            (x, y), dist = q.popleft()
            if x == h and y == w:
                return dist
            if not visited[x][y]:
                visited[x][y] = True
                for i in range(4):
                    nx, ny = x + dx[i], y + dy[i]
                    if expanded_grid[nx][ny] == '.' and not visited[nx][ny]:
                        q.append([(nx, ny), dist+1])
        return 0

        

    
    h, w = mi()
    grid = [input() for _ in range(h)]
    expanded_grid = []
    expanded_grid.append('
    for line in grid:
        expanded_grid.append('
    expanded_grid.append('

    visited = [[False] * (w + 2) for _ in range(h + 2)]

    initial_black = sum([line.count('
    d = bfs((1, 1))
    if d > 0:
        print(h*w - d - initial_black)
    else:
        print(-1)



if __name__ == "__main__":
    main()

Solution (Python):
INF = 10**9
di = [-1, 0, 1, 0]
dj = [0, -1, 0, 1]
h, w = map(int, input().split())
s = [input() for _ in range(h)]
def conv_coor(i, j):
    return i*w+j
def update(i, j, d,  q):
    if dist[conv_coor(i, j)] != INF:
        return
    dist[conv_coor(i, j)] = d
    q.append((i, j))

dist = [INF]*h*w
dist[0] = 0
q = [(0,0)]
while len(q) > 0:
    current = q.pop(0)
    i = current[0]
    j = current[1]
    for direction in range(4):
        ni = i + di[direction]
        nj = j + dj[direction]
        if ni < 0 or h <= ni or nj < 0 or w <= nj:
            continue
        if s[ni][nj] == "
            continue
        d = dist[conv_coor(i, j)]
        update(ni, nj, d+1, q)
if dist[conv_coor(h-1,w-1)] == INF:
    print(-1)
    exit()
b_num = 0
for i in range(h):
    for j in range(w):
        if s[i][j] == '
            b_num += 1
print(h*w-b_num-dist[conv_coor(h-1, w-1)]-1)

Solution (Python):
H, W = map(int, input().split())
m = []
count = 0
for i in range(H):
    s = input()
    count += s.count('.')
    m.append(list(s))

que = [(0,0)]
keiro = {}
keiro[(0,0)] = 1

while que:
    h, w = que.pop(0)
    
    if h+1 < H:
        if m[h+1][w] == '.':
            if (h+1,w) in keiro:
                keiro[(h+1,w)] = min(keiro[(h+1,w)],keiro[(h,w)]+1)
            else:
                keiro[(h+1,w)] = keiro[(h,w)]+1
                que.append((h+1,w))
    if w+1 < W:
        if m[h][w+1] == '.':
            if (h,w+1) in keiro:
                keiro[(h,w+1)] = min(keiro[(h,w+1)],keiro[(h,w)]+1)
            else:
                keiro[(h,w+1)] = keiro[(h,w)]+1
                que.append((h,w+1))
    if h-1 >= 0:
        if m[h-1][w] == '.':
            if (h-1,w) in keiro:
                keiro[(h-1,w)] = min(keiro[(h-1,w)],keiro[(h,w)]+1)
            else:
                keiro[(h-1,w)] = keiro[(h,w)]+1
                que.append((h-1,w))
    if w-1 >= 0:
        if m[h][w-1] == '.':
            if (h,w-1) in keiro:
                keiro[(h,w-1)] = min(keiro[(h,w-1)],keiro[(h,w)]+1)
            else:
                keiro[(h,w-1)] = keiro[(h,w)]+1
                que.append((h,w-1))

if (H-1,W-1) in keiro:
    print(count-keiro[(H-1,W-1)])
else:
    print(-1)

Solution (Python):
from collections import deque

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

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

DX = [0, 0, 1, -1]
DY = [1, -1, 0, 0]

def bfs(sx, sy):
    d = deque([[sx, sy]])
    while len(d) > 0:
        x, y = d.popleft()
        for dx, dy in zip(DX, DY):
            nx = x+dx; ny = y+dy
            if 0 <= nx < h and 0 <= ny < w:
                if grid[nx][ny] == "." and dist[nx][ny] > dist[x][y]+1:
                    dist[nx][ny] = dist[x][y]+1
                    d.append([nx, ny])

bfs(0, 0)

if dist[h-1][w-1] == INF:
    print(-1)
else:
    ans = 0
    for i in range(h):
        for j in range(w):
            if grid[i][j] == ".":
                ans += 1
    print(ans-dist[h-1][w-1]-1)

Solution (Python):
from collections import deque

h, w = map(int, input().split())
white = 0
s = []
for i in range(h):
    line = list(input())
    white += len([j for j in line if j == '.'])
    s.append(line)

Q = deque([[0, 0]])
stamp = [[0]*w for _ in range(h)]

while Q:
    row, col = Q.popleft()
    for i, j in [[0, -1], [1, 0], [0, 1], [-1, 0]]:
        new_row, new_col = row+i, col+j
        if new_row < 0 or new_row >= h or new_col < 0 or new_col >= w:
            continue
        if s[new_row][new_col] == '
            continue
        stamp[new_row][new_col] = stamp[row][col] + 1
        Q.append([new_row, new_col])

if stamp[-1][-1] == 0:
    print(-1)
else:
    print(white - stamp[-1][-1] - 1)

Solution (Python):
h,w = map(int,input().split())
cnt = 0
L = []
for i in range(h):
    s = input()
    cnt +=s.count("
    L.append(list(s))


d = [[-1]*w for i in range(h)]
d[0][0] = 0
from collections import deque
q = deque([[0,0]])


li = ((1,0),(0,1),(-1,0),(0,-1))

while q:
    j,i = q.popleft()
    for dy,dx in li:
        ny,nx = j+dy,i+dx
        if (ny < 0 or ny >= h) or (nx < 0 or nx >= w) or L[ny][nx] == "
            continue
        else:
            if d[ny][nx] == -1:
                d[ny][nx] = d[j][i] + 1
                q.append((j+dy,i+dx))

if d[h-1][w-1] == -1:
    print(-1)
else:
    print(h*w - cnt - d[h-1][w-1]-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 (ni, nj) not in visited and 0 <= ni < H and 0 <= nj < W and field[ni][nj] == '.':
                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)