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


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

min_dist = -1
seen = set()
q = deque()
q.append((0, 0, 0))  
while len(q) > 0:
    i, j, dist = q.popleft()
    if i == H - 1 and j == W - 1:
        min_dist = dist
        break
    if i > 0 and S[i - 1][j] == '.' and (i - 1, j) not in seen:
        seen.add((i - 1, j))
        q.append((i - 1, j, dist + 1))
    if j > 0 and S[i][j - 1] == '.' and (i, j - 1) not in seen:
        seen.add((i, j - 1))
        q.append((i, j - 1, dist + 1))
    if i < H - 1 and S[i + 1][j] == '.' and (i + 1, j) not in seen:
        seen.add((i + 1, j))
        q.append((i + 1, j, dist + 1))
    if j < W - 1 and S[i][j + 1] == '.' and (i, j + 1) not in seen:
        seen.add((i, j + 1))
        q.append((i, j + 1, dist + 1))

if min_dist == -1:
    print(-1)
else:
    b = 0
    for r in S:
        for c in r:
            if c == '
                b += 1
    print(H * W - min_dist - b - 1)

Solution (Python):
import sys
sys.setrecursionlimit(3000)
h,w=map(int,input().split())
s=['
l=[[0]*(w+2) for _ in [0]*(h+2)]
for i in range(h+2):
    for j in range(w+2):
        if s[i][j]=='
            l[i][j]=-1
def sol(m,n):
    global l
    if l[m][n]>=0:
        for i,j in [(m-1,n),(m+1,n),(m,n-1),(m,n+1)]:
            if l[i][j]==0 and [i,j]!=[1,1]:
                l[i][j]=l[m][n]+1
                sol(i,j)
            elif l[i][j]>l[m][n]+1:
                l[i][j]=l[m][n]+1
                sol(i,j)
sol(1,1)
if l[h][w]==0:print(-1)
else:print(h*w-l[h][w]-(sum(x.count('

Solution (Python):
from collections import deque


def bfs(sx, sy, gx, gy):
    q = deque([(sx, sy)])
    cost[sx][sy] = 1
    while q:
        x, y = q.popleft()
        for dx, dy in nb:
            nx = x + dx
            ny = y + dy
            if 0 <= nx and nx < h and 0 <= ny and ny < w and grid[nx][ny] == "." and cost[nx][ny] == float("inf"):
                q.append((nx, ny))
                cost[nx][ny] = cost[x][y] + 1
                if nx == gx and ny == gy:
                    return cost[nx][ny]
    return -1


h, w = map(int, input().split())
grid = [list(input()) for _ in range(h)]
cost = [[float("inf")] * w for _ in range(h)]
nb = [(-1, 0), (0, -1), (1, 0), (0, 1)]
black_cnt = 0
ans = 0

for i in range(h):
    black_cnt += str(grid[i]).count("

can_reach = bfs(0, 0, h - 1, w - 1)
if can_reach > 0:
    print(h * w - can_reach - black_cnt)
else:
    print(can_reach)

Solution (Python):
H, W = map(int, input().split())
state = [[0 if s == '.' else 1 for s in list(input())] for _ in range(H)]

checked = [[False for _ in range(W)] for _ in range(H)]
qs = [(0, 0)]
checked[0][0] = True
goal = False
d = 0
while qs:
    qqs = []
    for qx, qy in qs:
        nexts = [(qx, qy+1), (qx, qy-1), (qx+1, qy), (qx-1, qy)]
        for nx, ny in nexts:
            if 0 <= nx <= W-1 and 0 <= ny <= H-1:
                if checked[ny][nx] or state[ny][nx] == 1:
                    continue
                qqs.append((nx, ny))
                checked[ny][nx] = True
            if nx == W-1 and ny == H-1:
                goal = True
                break
    d += 1
    if goal:
        break
    qs = qqs

black = 0
for h in range(H):
    for w in range(W):
        if state[h][w] == 1:
            black += 1

if goal:
    ans = H*W - black - d - 1
else:
    ans = -1

print(ans)

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

grid_array = [[0] * (W+2) for _ in range(H+2)]


white_count = 0
for i in range(1, H+1):
    grid = input()
    for j, x in enumerate(grid):
        if x == ".":
            grid_array[i][j+1] = 1
            white_count += 1

used_array = [[0] * (W+2) for _ in range(H+2)]

INF = 10 ** 5

distance_array = [[INF] * (W+2) for _ in range(H+2)]

tile_deque = deque()
tile_deque.append((1, 1))
used_array[1][1] = 1
distance_array[1][1] = 1
while len(tile_deque):
    i, j = tile_deque.popleft()
    
    if used_array[i-1][j] == 0 and grid_array[i-1][j] == 1:
        used_array[i-1][j] = 1
        tile_deque.append((i-1, j))
        distance_array[i-1][j] = min(distance_array[i-1]
                                     [j], distance_array[i][j]+1)
    if used_array[i+1][j] == 0 and grid_array[i+1][j] == 1:
        used_array[i+1][j] = 1
        tile_deque.append((i+1, j))
        distance_array[i+1][j] = min(distance_array[i+1]
                                     [j], distance_array[i][j]+1)
    if used_array[i][j-1] == 0 and grid_array[i][j-1] == 1:
        used_array[i][j-1] = 1
        tile_deque.append((i, j-1))
        distance_array[i][j-1] = min(distance_array[i]
                                     [j-1], distance_array[i][j]+1)
    if used_array[i][j+1] == 0 and grid_array[i][j+1] == 1:
        used_array[i][j+1] = 1
        tile_deque.append((i, j+1))
        distance_array[i][j+1] = min(distance_array[i]
                                     [j+1], distance_array[i][j]+1)

if distance_array[H][W] == INF:
    print(-1)
else:
    print(white_count-distance_array[H][W])

Solution (Python):
from collections import deque

h, w = map(int, input().split())
field = [input() for i in range(h)]
todo = deque([[0, 0]])
seen = [[-1]*w for _ in range(h)]
seen[0][0] = 0
dy = [1, -1, 0, 0]
dx = [0, 0, 1, -1]

count_black = 0
for line in field:
    count_black += line.count('

while todo:
    y, x = todo.popleft()

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

        if ny < 0 or h <= ny or nx < 0 or w <= nx:
            continue
        elif field[ny][nx] == '
            continue
        else:
            seen[ny][nx] = seen[y][x] + 1
            todo.append([ny, nx])

goal = seen[h-1][w-1]

if goal == -1:
    print(-1)
else:
    ans = h * w - count_black - goal - 1
    print(ans)

Solution (Python):
h , w = map(int, input().split())
field = [["
for i in range(h):
  temp = input()
  field.append("
field.append(["
now = [[1, 1]]
dots_count = 0
for i in field:
  dots_count += i.count(".")
move = [[0,1], [1, 0], [0,-1], [-1, 0]]
s_field = [[None for _ in range(w+2)] for _ in range(h+2)]
s_field[1][1] = 1
while now:
  x , y = now.pop(0)
  for v, u in move:
    if field[y+u][x+v] == "." and s_field[y+u][x+v] ==None:
      s_field[y+u][x+v] = s_field[y][x]+1
      if y+u == h and x+v == w:
        print(dots_count-s_field[y+u][x+v])
        break
      now.append([x+v, y+u])
  else:
    if not now:
      print(-1)
      break
    continue
  break

Solution (Python):

import sys
from collections import deque, defaultdict
import copy
import bisect


import math
import heapq

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

que = deque()
dist = [[-1 for i in range(W)] for j in range(H)]
que.append([0,0])
dist[0][0] = 0
while len(que) > 0:
	loc = que.popleft()
	if loc[0] < H - 1 and s[loc[0] + 1][loc[1]] == '.' and dist[loc[0] + 1][loc[1]] == -1:
		dist[loc[0] + 1][loc[1]] = dist[loc[0]][loc[1]] + 1
		que.append([loc[0] + 1, loc[1]])
	if loc[0] > 0 and s[loc[0] - 1][loc[1]] == '.' and dist[loc[0] - 1][loc[1]] == -1:
		dist[loc[0] - 1][loc[1]] = dist[loc[0]][loc[1]] + 1
		que.append([loc[0] - 1, loc[1]])
	if loc[1] < W - 1 and s[loc[0]][loc[1] + 1] == '.' and dist[loc[0]][loc[1] + 1] == -1:
		dist[loc[0]][loc[1] + 1] = dist[loc[0]][loc[1]] + 1
		que.append([loc[0], loc[1] + 1])
	if loc[1] > 0 and s[loc[0]][loc[1] - 1] == '.' and dist[loc[0]][loc[1] - 1] == -1:
		dist[loc[0]][loc[1] - 1] = dist[loc[0]][loc[1]] + 1
		que.append([loc[0], loc[1] - 1])


distance = dist[H - 1][W - 1]
if distance == -1:
	print(-1)
	exit()
num = H*W
for i in range(H):
	for j in range(W):
		if s[i][j] == '
			num -= 1
num -= 1 + distance
print(num)

Solution (Python):
import queue

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

whiteCount = 0

world = []
for i in range(H):
    row = [c for c in input()]
    world.append(row) 
    whiteCount += len([c for c in row if c == '.'])

minRoot = whiteCount + 1

def bfs(x, y, depth):
    if x == W - 1 and y == H - 1:
        return min(minRoot, depth)

    depth = depth + 1
    appendPosition(x + 1, y, depth)
    appendPosition(x - 1, y, depth)
    appendPosition(x, y + 1, depth)
    appendPosition(x, y - 1, depth)

    return minRoot

def appendPosition(newX, newY, depth):
    if newX < 0 or newY < 0 or newX >= W or newY >= H or world[newY][newX] == '
        return

    newPosition = (newX,newY)
    if newPosition in visitedPosition:
        return

    q.put((newX, newY, depth))
    visitedPosition.add(newPosition)

q = queue.Queue()
q.put((0,0,1))
visitedPosition = set()
visitedPosition.add((0,0))

while q.empty() == False:
    position = q.get()
    minRoot = min(minRoot, bfs(*position))

if whiteCount < minRoot:
    print(-1)
else:
    print(whiteCount - minRoot)

Solution (Python):
from collections import deque
H,W = map(int,input().split())
s = list(input() for i in range(H))
board = [[1]*(W+2) for i in range(H+2)]
white = 0
for i in range(H):
    for j in range(W):
        if s[i][j] == '.':
            white += 1
            board[i+1][j+1] = 0
queue = deque([[1,1]])
v = [[1,0],[-1,0],[0,-1],[0,1]]
while queue != deque([]):
    x,y = queue.popleft()

    for a,b in v:
        if board[x+a][y+b] == 0:
            board[x+a][y+b] = board[x][y]+1
            queue.append([x+a,y+b])

if board[H][W] != 0:
    print(white-board[H][W]-1)
else:
    print(-1)

Solution (Python):
from collections import deque
H,W = list(map(int, input().split()))
s = [input().split() for i in range(H)]
for i in range(H):
    s[i] = list(s[i][0])
black = 0
for i in range(H):
    for j in range(W):
        if s[i][j] == "
            black += 1
queue = deque([])
dist = [[-1 for i in range(W)] for j in range(H)]
dist[0][0] = 0
queue.append([0,0])
place_w = [0, 1, 0, -1]
place_h = [1, 0, -1, 0]
Flag = False
while len(queue) > 0:
    vh,vw = queue.popleft()
    for m in range(4):
        nvh = vh+place_h[m]
        nvw = vw+place_w[m]
        if 0<=nvh<H and 0<=nvw<W and dist[nvh][nvw] == -1 and s[nvh][nvw] == ".":
            queue.append([nvh,nvw])
            dist[nvh][nvw] = dist[vh][vw]+1
if dist[H-1][W-1] == -1:
    print(-1)
else:
    print(W*H-dist[H-1][W-1]-black-1)

Solution (Python):
from collections import deque

h, w = map(int, input().split())
INF = 10000000000
b = 0
maze = [[] for _ in range(h)]
for i in range(h):
  l = list(input())
  b += l.count("
  maze[i] = l

dist = [[INF for _ in range(w)] for _ in range(h)]
dx = [0, 1, 0, -1]
dy = [1, 0, -1, 0]

q = deque()
q.append((0,0))
dist[0][0] = 0

while q:
  x, y = q.popleft()
  if (x == w-1) and (y == h-1): break
  for i in range(len(dx)):
    nx = x + dx[i]
    ny = y + dy[i]
    if (nx >= 0) and (nx < w) and (ny >= 0) and (ny < h) and (maze[ny][nx] != "
      q.append((nx, ny))
      dist[ny][nx] = dist[y][x] + 1
      
if dist[h-1][w-1] == INF:
  print(-1)
else:
  print((h*w) - (dist[h-1][w-1]+1) - b)

Solution (Python):
import sys
def input():
    return sys.stdin.readline()[:-1]

"""
H Wの後に


みたいな文字列を受け取る
"""
H,W = map(int,input().split(' '))
MAP = [['

for i in range(1,H+1):
    MAP[i] = ['
import queue
q = queue.Queue()


MAP[H][W] = 'G'
visited = [None]*(H+1)
for i in range(H+1):
    visited[i] = [False]*(W+1)

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

def is_okay(x,y):
    if not (0<x<W+1) or not (0<y<H+1):
        return False
    if visited[y][x] or MAP[y][x]=='
        return False
    return True

n = 0
q.put([1,1,n])
ans = 10**7 + 7
delta = [[1,0],[-1,0],[0,1],[0,-1]]
while not q.empty():
    x,y,n = q.get()
    k = MAP[y][x]

    n += 1
    if k=='G':
        ans = min(ans,n)
        break
    for d in delta:
        dx = x+d[0]
        dy = y+d[1]
        if is_okay(dx,dy):
            q.put([dx,dy,n])
            visited[dy][dx] = True

if not ans==10**7 + 7:
    ANS = H*W - ans - d_num
else:
    ANS = -1

print(ANS)

Solution (Python):
import sys
def input():
    return sys.stdin.readline()[:-1]

"""
H Wの後に


みたいな文字列を受け取る
"""
H,W = map(int,input().split(' '))
MAP = [['

for i in range(1,H+1):
    MAP[i] = ['
import queue
q = queue.Queue()


MAP[H][W] = 'G'
visited = [None]*(H+1)
for i in range(H+1):
    visited[i] = [False]*(W+1)

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

def is_okay(x,y):
    if not (0<x<W+1) or not (0<y<H+1):
        return False
    if visited[y][x] or MAP[y][x]=='
        return False
    return True

n = 0
q.put([1,1,n])
ans = 10**7 + 7
delta = [[1,0],[-1,0],[0,1],[0,-1]]
while not q.empty():
    x,y,n = q.get()
    k = MAP[y][x]

    n += 1
    if k=='G':
        ans = min(ans,n)
        break
    for d in delta:
        dx = x+d[0]
        dy = y+d[1]
        if is_okay(dx,dy):
            q.put([dx,dy,n])
            visited[dy][dx] = True

if not ans==10**7 + 7:
    ANS = H*W - ans - d_num
else:
    ANS = -1

print(ANS)

Solution (Python):
import sys
def input():
    return sys.stdin.readline()[:-1]

"""
H Wの後に


みたいな文字列を受け取る
"""
H,W = map(int,input().split(' '))
MAP = [['

for i in range(1,H+1):
    MAP[i] = ['
import queue
q = queue.Queue()


MAP[H][W] = 'G'
visited = [None]*(H+1)
for i in range(H+1):
    visited[i] = [False]*(W+1)

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

def is_okay(x,y):
    if not (0<x<W+1) or not (0<y<H+1):
        return False
    if visited[y][x] or MAP[y][x]=='
        return False
    return True

n = 0
q.put([1,1,n])
ans = 10**7 + 7

while not q.empty():
    x,y,n = q.get()
    k = MAP[y][x]

    n += 1
    if k=='G':
        ans = min(ans,n)
        break

    if is_okay(x+1,y):
        q.put([x+1,y,n])
        visited[y][x+1] = True
    if is_okay(x-1,y):
        q.put([x-1,y,n])
        visited[y][x-1] = True
    if is_okay(x,y+1):
        q.put([x,y+1,n])
        visited[y+1][x] = True
    if is_okay(x,y-1):
        q.put([x,y-1,n])
        visited[y-1][x] = True


if not ans==10**7 + 7:
    ANS = H*W - ans - d_num
else:
    ANS = -1

print(ANS)

Solution (Python):
import sys
def input():
    return sys.stdin.readline()[:-1]

"""
H Wの後に


みたいな文字列を受け取る
"""
H,W = map(int,input().split(' '))
MAP = [['

for i in range(1,H+1):
    MAP[i] = ['
import queue
q = queue.Queue()


MAP[H][W] = 'G'
visited = [None]*(H+1)
for i in range(H+1):
    visited[i] = [False]*(W+1)

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

def is_okay(x,y):
    if not (0<x<W+1) or not (0<y<H+1):
        return False
    if visited[y][x] or MAP[y][x]=='
        return False
    return True

n = 0
q.put([1,1,n])
ans = 10**7 + 7

while not q.empty():
    x,y,n = q.get()
    k = MAP[y][x]

    n += 1
    if k=='G':
        ans = min(ans,n)
        break

    if is_okay(x+1,y):
        q.put([x+1,y,n])
        visited[y][x+1] = True
    if is_okay(x-1,y):
        q.put([x-1,y,n])
        visited[y][x-1] = True
    if is_okay(x,y+1):
        q.put([x,y+1,n])
        visited[y+1][x] = True
    if is_okay(x,y-1):
        q.put([x,y-1,n])
        visited[y-1][x] = True


if not ans==10**7 + 7:
    ANS = H*W - ans - d_num
else:
    ANS = -1

print(ANS)

Solution (Python):


from collections import deque

def solve(R, C, sy, sx, gy, gx, mz):
  queue = deque()
  checked = set( )
  queue.append((sx, sy, 0))
  while queue:
    x, y, n = queue.popleft()
    if x == gx and y == gy:
      return n
    if x < 1 or x > C or y < 1 or y > R or mz[y-1][x-1] == '
      continue
    if (x, y) in checked:
      continue
    checked.add((x, y))
    queue.append((x+1, y, n+1))
    queue.append((x-1, y, n+1))
    queue.append((x, y+1, n+1))
    queue.append((x, y-1, n+1))
  return -1


if __name__ == '__main__':
  R, C = map(int, input().split(' '))
  sy, sx = 1, 1
  gy, gx = R, C
  mz = []
  whites = 0
  for r in range(R):
    tmp = input()
    mz.append(tmp)
    whites += tmp.count('.')
  n = solve(R, C, sy, sx, gy, gx, mz)
  if n < 0:
    print(-1)
  else:
    print(whites - n - 1)

Solution (Python):



from collections import deque


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


ls = eval("input(),"*h)

kuro = 0
for i in range(h):
    kuro += ls[i].count("


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

s = deque()
yone =(0,0,1,-1)
xone =(1,-1,0,0)

s.append((0,0))
while s:
    y, x = s.popleft()
    for i,j in zip(yone,xone):
        ny = y+i
        nx = x+j
        if (0 <= ny < h) and (0 <= nx < w):
            if (ls[ny][nx]==".") and (done[ny][nx]==0):
                s.append([ny,nx])
                done[ny][nx] = done[y][x] + 1
               
 
if done[h-1][w-1]:
    print(h*w -kuro -done[h-1][w-1]-1)
else:
    print(-1)

Solution (Python):
from queue import Queue

def bfs(point):
    global visit, s
    while point.qsize() > 0:
        hh, ww = point.get()
        h_w_list = [[1, 0], [- 1, 0], [0, 1], [0, - 1]]
        for h_, w_ in h_w_list:
            h_ = h_ + hh
            w_ = w_ + ww
            if (h_ in range(h)) & (w_ in range(w)):
                if s[h_][w_] == ".":
                    if visit[h_][w_] == inf:                    
                        point.put([h_, w_])
                        visit[h_][w_] = visit[hh][ww] + 1
        
    
inf = 10 ** 9    
h, w = map(int, input().split())
s = []
point_num = 0
for _ in range(h):
    k = input()
    point_num += k.count(".")
    s.append(list(k))
visit = [[inf for _ in range(w)] for _ in range(h)]
point = Queue()
point.put([0, 0])
visit[0][0] = 0
bfs(point)
ans = point_num - visit[-1][-1] - 1
if ans < 0:
    ans = -1
print(ans)

Solution (Python):
from collections import deque

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

w_count = -2
for i in range(H):
  for j in range(W):
    if maze[i][j] == ".":
      w_count += 1

que = deque()
que.append([0, 0])
d[0][0] = 0
dxy = [[-1, 0], [1, 0], [0, -1], [0, 1]]
while len(que) != 0:
  p = que.popleft()
  for i in dxy:
    nx = p[0] + i[0]
    ny = p[1] + i[1]
    if 0 <= nx < H and 0 <= ny < W and d[nx][ny] == 10**9 and maze[nx][ny] == ".":
      d[nx][ny] = d[p[0]][p[1]] + 1
      que.append([nx, ny])
if d[H-1][W-1] == 10**9:
  print(-1)
else:
  print(w_count - d[H-1][W-1] + 1)

Solution (Python):


from collections import deque

def resolve():
    WALL = -1
    UNVISITED = -2

    H, W = map(int, input().split())
    sy, sx = 0, 0
    gy, gx = H-1, W-1

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

    num_aile = 0

    for i in range(H):
        tmp = input()
        for j in range(W):
            if tmp[j] == '.':
                c[i][j] = UNVISITED
                num_aile += 1
            else:
                c[i][j] = WALL

    que = deque([[sy, sx]])
    c[sy][sx] = 0

    def BFS(x, y):
        for i, j in [[x-1, y], [x+1, y], [x, y-1], [x, y+1]]:
            if i < 0 or H <= i or j < 0 or W <= j:
                continue
            if c[i][j] == UNVISITED:
                que.append([i, j])
                c[i][j] = c[x][y] + 1

    while len(que) > 0:
        p = que.popleft()
        BFS(p[0], p[1])

    if c[gy][gx] == -2:
        print(-1)
    else:
        print(num_aile - c[gy][gx] - 1)


if __name__ == "__main__":
    resolve()

Solution (Python):
from collections import deque
H, W = map(int, input().split())
s = []
for _ in range(H):
    s.append(input())

ans = H * W
for si in s:
    ans -= si.count("

visited = [[False] * W for _ in range(H)]
q = deque()
q.append((1, 0, 0))
visited[0][0] = True

while len(q):
    n, i, j = q.popleft()
    if (i, j) == (H - 1, W - 1):
        ans -= n
        break
    for x, y in ((i-1, j), (i+1, j), (i, j-1), (i, j+1)):
        if not 0 <= x < H or not 0 <= y < W:
            continue
        if visited[x][y] or s[x][y] == "
            continue
        q.append((n+1, x, y))
        visited[x][y] = True
else:
    print(-1)
    exit()

print(ans)

Solution (Python):


from collections import deque

h, w = map(int, input().split())
table =[]
default_dot = 0
for _ in range(h):
  line = list(input())
  default_dot+=line.count(".")
  table.append(line)

default_dot-=2  
table[0][0] = 0

cur = [0, 0]   
queue = deque()
queue.append(cur)
steps = [0, 1, 0, -1, 0]

minimum_step = 0

while True:
  if len(queue)==0:
    print(-1)
    exit()
  now = queue.popleft()
  if now[0] == w-1 and now[1] == h-1:
    minimum_step = table[now[1]][now[0]]-1
    break
  for i in range(4):
    next_y, next_x = now[1]+steps[i], now[0]+steps[i+1]
    if 0<=next_y<h and 0<=next_x<w and table[next_y][next_x] == ".":
      table[next_y][next_x] = table[now[1]][now[0]]+1
      queue.append([next_x, next_y])


print(default_dot-minimum_step)

Solution (Python):



import queue

def ri():
    return int(input())

def rl():
    return list(input().split())

def rli():
    return list(map(int, input().split()))

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

class BFS:
    def __init__(self, h, w, board):
        self.h = h
        self.w = w
        self.board = board
        self.num_empty = 0
        for x in range(1, w+1):
            for y in range(1, h+1):
                if self.board[y][x] == '.':
                    self.num_empty += 1
        self.cost = [[-1 for _ in range(w+2)] for _ in range(h+2)]

    def search(self):
        q = queue.Queue()
        q.put((1, 1))
        self.cost[1][1] = 1
        while not q.empty():
            p = q.get()
            x, y = p[0], p[1]
            for i in range(4):
                nx = x+dx[i]
                ny = y+dy[i]
                if self.board[ny][nx] == '
                    continue
                if self.cost[ny][nx] >= 0:
                    continue
                q.put((nx, ny))
                self.cost[ny][nx] = self.cost[y][x]+1
        c = self.cost[self.h][self.w]
        if c == -1:
            return -1
        else:
            return self.num_empty - c

def main():
    h, w = rli()
    board = []
    board.append('
    for _ in range(h):
        board.append('
    board.append('
    bfs = BFS(h, w, board)
    ans = bfs.search()
    print(ans)



if __name__ == '__main__':
    main()

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


C[0][0] = 0
pre_list = [(0,0)]
count = 0
 
while C[H-1][W-1] == '.' and len(pre_list) > 0:
    count += 1
    next_list = []
    for y,x in pre_list:
        for i,j in ((1,0),(0,-1),(0,1),(-1,0)):
            if y+i < 0 or x+j < 0 or y+i >= H or x+j >= W:
                continue
            if C[y+i][x+j] == '.':
                C[y+i][x+j] = count
                next_list.append((y+i,x+j))
    pre_list = next_list

if C[H-1][W-1] == '.':
    print(-1)
else:
    black = 0
    for h in C:
        for v in h:
            if v == "
                black += 1
    print(H*W-black-count-1)

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

white = 0
for i in range(H):
  white += S[i].count('.')

q = [(0,0)]
S[0][0] = 0
while q:
  qq = []
  for xy in q:
    x,y = xy
    for dx,dy in ((1,0),(-1,0),(0,1),(0,-1)):
      if not(0 <= x+dx < W) or not(0 <= y+dy < H):
        continue
      elif S[y+dy][x+dx] != '.':
        continue
      S[y+dy][x+dx] = S[y][x] + 1
      qq.append((x+dx,y+dy))
  q = qq

print(white - S[-1][-1] -1 if S[-1][-1] != '.' else -1)

Solution (Python):
H,W = map(int,input().split())
s = [[c=="." for c in input()] for _ in [0]*H]

def bsf_dist_grid(grid,start):
    H = len(grid)
    W = len(grid[0])
    d = [[-1]*W for _ in [0]*H]
    d[start[0]][start[1]] = 0
    q = [start]
    while q:
        qq = []
        for xy in q:
            x,y = xy
            d0 = d[y][x]
            for dx,dy in ((1,0),(-1,0),(0,1),(0,-1)):
                if (not 0<=x+dx<W) or (not 0<=y+dy<H): continue
                if d[y+dy][x+dx] != -1: continue
                if not grid[y+dy][x+dx]: continue
                d[y+dy][x+dx] = d0+1
                qq.append((x+dx,y+dy))
        q = qq
    return d

d = bsf_dist_grid(s,(0,0))[-1][-1]
print((sum(sum(a) for a in s)-d-1) if d>=0 else -1)

Solution (Python):
from collections import deque
import time, sys


H, W = map(int, input().split())
fields = [""]*(H + 2)
fields[0] = ["
fields[H + 1] = ["
sx, sy = 1, 1
gx, gy = W, H
for i in range(1, H + 1):
    fields[i] = ["

    
p = deque()
p.appendleft([sx, sy])

dist = [[None] * (W + 2) for _ in range(0, H + 2)] 
dist[sy][sx] = 0
delta = [[0, 1], [1, 0], [0, -1], [-1, 0]]
while p:
    x, y = p.pop()
    
    
    if (x == gx) & (y == gy):
        break
    
    
    for dx, dy in delta:
        nx = x + dx
        ny = y + dy
        
        if fields[ny][nx] == "
            continue
        
        if dist[ny][nx] is not None:
            continue
        
        
        p.appendleft([nx, ny])
        dist[ny][nx] = dist[y][x] + 1
        
if dist[gy][gx] is None:
    print(-1)
    sys.exit()
        

white_cnt = 0

for line in fields:
    for j in line:
        if j == ".":
            white_cnt += 1


white_cnt = white_cnt - 2


white_cnt = white_cnt - dist[gy][gx] + 1

print(white_cnt)

Solution (Python):
import math
import copy
from operator import mul
from functools import reduce
from collections import defaultdict
from collections import Counter
from collections import deque

from itertools import product

from itertools import permutations

from itertools import combinations

from itertools import accumulate
from bisect import bisect_left, bisect_right

import re




def inside(y, x, H, W):
    return 0 <= y < H and 0 <= x < W


dy = [0, -1, 0, 1]
dx = [1, 0, -1, 0]
 
def i_inpl(): return int(input())
def l_inpl(): return list(map(int, input().split()))
def line_inpl(x): return [i_inpl() for _ in range(x)]

INF = int(1e18)
MOD = int(1e9)+7 



H, W = l_inpl()
field = [ input() for _ in range(H) ]
sy, sx = 0, 0
gy, gx = H-1, W-1
def bfs(field, number_of_moves, sy, sx):
    queue = deque([[sy, sx]])
    number_of_moves[sy][sx] = 0
    while queue:
        y, x = queue.popleft()
        current_number_of_move = number_of_moves[y][x]
        for i in range(4):
            ny, nx = y + dy[i], x + dx[i]
            if inside(ny, nx, H, W) and \
                field[ny][nx] == "." and \
                number_of_moves[ny][nx] == -1:
                number_of_moves[ny][nx] = current_number_of_move + 1
                queue.append([ny, nx])
    return number_of_moves

number_of_moves = [ [-1] * W for _ in range(H) ]
number_of_moves = bfs(field, number_of_moves, sy, sx)
b_cnt = sum([ f.count("

if number_of_moves[gy][gx] == -1:
    print(-1)
else:
    print(H*W-b_cnt-number_of_moves[gy][gx]-1)

Solution (Python):
import numpy as np

h,w = map(int,input().split())
f = []
bk = 0
f.append(["
for i in range(h):
    l = list(input())
    for c in l:
        if c=="
            bk += 1
    f.append(["
f.append(["
visited = {"1,1":0}

now = [[1,1]]
next = []

def to_key(l):
    return str(l[0])+","+str(l[1])

flag = True
count = 1
while 1:
    if len(now) == 0:
        flag = False
        break
    for state in now:
        x = state[0]
        y = state[1]

        if x==h and y == w:
            break

        if f[x+1][y]=="." and to_key([x+1,y]) not in visited:
            next.append([x+1,y])
            visited[to_key([x+1,y])] = count
        if f[x][y+1]=="." and to_key([x,y+1]) not in visited:
            next.append([x,y+1])
            visited[to_key([x,y+1])] = count
        if f[x-1][y]=="." and to_key([x-1,y]) not in visited:
            next.append([x-1,y])
            visited[to_key([x-1,y])] = count
        if f[x][y-1] == "." and to_key([x,y-1]) not in visited:
            next.append([x, y-1])
            visited[to_key([x,y-1])] = count
    count += 1
    now = next
    next = []
    

if flag:
    print(h*w-visited[to_key([h,w])]-bk-1)
else:
    if to_key([h,w]) in visited:
        print(h * w - visited[to_key([h, w])] - bk-1)
    else:
        print(-1)

Solution (Python):
h,w=map(int,input().split())
state=[]
for i in range(h):
    state.append(input())
count=0
for i in range(h):
    for j in range(w):
        if state[i][j]=='.':
            count+=1
def bfs():
    dist=[[-1]*w for i in range(h)]
    dist[0][0]=0
    stack=[]
    stack.append([0,0])

    while(stack):
        
        node=stack.pop(0)
        for i,j in zip([1,-1,0,0],[0,0,1,-1]):
            if 0<=node[0]+i<h and 0<= node[1]+j<w:
                if dist[node[0]+i][node[1]+j]==-1 and state[node[0]+i][node[1]+j]=='.':
                    dist[node[0]+i][node[1]+j]=dist[node[0]][node[1]]+1
                    if [node[0]+i,node[1]+j]==[h-1,w-1]:
                        break
                    stack.append([node[0]+i,node[1]+j])
    if dist[h-1][w-1]==-1:
        print(-1)
    else:
        print(count-1-dist[h-1][w-1])

bfs()

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

d = [(1, 0), (0, 1), (-1, 0), (0, -1)]
q = deque([(1, 1, 1)])
m[1][1] = '@'
ans = -1
while q:
    x, y, c = q.popleft()
    if x == h and y == w:
        ans = c
        break
    for dx, dy in d:
        nx, ny = x+dx, y+dy
        if m[nx][ny] == '.':
            q.append((nx, ny, c+1))
            m[nx][ny] = '@'

if ans != -1:
    for i in range(1, h+1):
        for j in range(1, w+1):
            if m[i][j] == '
                ans += 1
    ans = h*w - ans

print(ans)