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):


h,w = list(map(int,input().split()))
inf=float("inf")
s = [[-1]*(w+2)] + [[-1] + [inf if i=="." else -1 for i in input()] + [-1] for _ in range(h)] + [[-1]*(w+2)]
from math import isinf
white = 0
for i in s:
    for j in i:
        if isinf(j):
            white+=1


inf=float("inf")
from collections import deque
s[1][1] = 0
stack_deque = deque([[1,1]])
ret = -1
cnt = 0
while len(stack_deque) > 0:
    curh,curw = stack_deque.popleft()
    cnt = s[curh][curw]+1
    if curh == h and curw==w:
        ret = white - (cnt-1) -1
        break
    if isinf(s[curh-1][curw]):
        s[curh-1][curw]=cnt
        stack_deque.append([curh-1,curw])
    if isinf(s[curh+1][curw]):
        s[curh+1][curw]=cnt
        stack_deque.append([curh+1,curw])
    if isinf(s[curh][curw-1]):
        s[curh][curw-1]=cnt
        stack_deque.append([curh,curw-1])
    if isinf(s[curh][curw+1]):
        s[curh][curw+1]=cnt
        stack_deque.append([curh,curw+1])
print(ret)

Solution (Python):
from collections import deque

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

graph = [input() for i in range(H)]
q = deque([(0,0)])
dist = [[-1] * W for i in range(H)]
dist[0][0] = 1

while q:
    y, x = q.popleft()
    L = [(1,0), (-1,0), (0,1), (0,-1)]
    for i, j in L:
        if ((0 <= y+i <= H-1 and 0 <= x+j <= W-1)
            	and dist[y+i][x+j] == -1
            	and graph[y+i][x+j] == "."):
        	dist[y+i][x+j] = dist[y][x] + 1
        	q.append((y+i, x+j))

white = 0
for i in range(H):
    white += graph[i].count(".")
    
if dist[H-1][W-1] == -1:
    print("-1")
else:
    ans = white - dist[H-1][W-1]
    print(ans)

Solution (Python):
from itertools import permutations
import sys

sys.setrecursionlimit(10 ** 6)
from bisect import *
from collections import *
from heapq import *

def II(): return int(sys.stdin.readline())
def MI(): return map(int, sys.stdin.readline().split())
def LI(): return list(map(int, sys.stdin.readline().split()))
def SI(): return sys.stdin.readline()[:-1]
def LLI(rows_number): return [LI() for _ in range(rows_number)]
int1 = lambda x: int(x) - 1
def MI1(): return map(int1, sys.stdin.readline().split())
def LI1(): return list(map(int1, sys.stdin.readline().split()))
p2D = lambda x: print(*x, sep="\n")
dij = [(1, 0), (0, 1), (-1, 0), (0, -1)]

def main():
    h,w=MI()
    ss=[[c=="
    dist=[[-1]*w for _ in range(h)]
    q=deque()
    q.append((0,0))
    dist[0][0]=1
    while q:
        i,j=q.popleft()
        d=dist[i][j]
        for di,dj in dij:
            ni,nj=i+di,j+dj
            if (ni,nj)==(h-1,w-1):
                ans = h * w - (d + 1) - sum(sum(row) for row in ss)
                print(ans)
                exit()
            if ni<0 or nj<0 or ni>=h or nj>=w:continue
            if dist[ni][nj]!=-1:continue
            if ss[ni][nj]:continue
            dist[ni][nj]=d+1
            q.append((ni,nj))
    print(-1)

main()

Solution (Python):
from collections import deque
h,w = map(int,input().split())
S = [list(input()) for _ in range(h)]
cost = [[-1]*w for _ in range(h)]


sy,sx = 0,0
gy,gx = h-1, w-1
que = deque([(sy,sx,0)])

flg = False
ret = -1
while que:
    y,x,c = que.popleft()
    if y==gy and x==gx:
        flg = True
        ret = c
        break
    if cost[y][x] != -1:
        continue
    cost[y][x] = c
    for dy,dx in zip((-1, 1, 0, 0), (0, 0, -1, 1)):
        ny = y + dy
        nx = x + dx
        if 0<=ny<h and 0<=nx<w:
            if S[ny][nx]!='
                que.append((ny,nx,c+1))
if not flg:
    print(-1)
else:
    blk, wht = 0, 0
    for s in S:
        for ss in s:
            if ss=='
                blk += 1
            else:
                wht += 1
    print(h*w-ret-1-blk)

Solution (Python):
H,W = map(int, input().split())
S = [["
S += [["
S.append(["

INF = 10 ** 5

visited = [[False] * (W + 2) for _ in range(H + 2)]
dist = [[INF] * (W + 2) for _ in range(H + 2)]

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

from collections import deque
def bfs():
    visited[1][1] = True
    dist[1][1] = 0
    que = deque([(1,1)])
    while que:
        y,x = que.popleft()
        for dy,dx in zip(DY,DX):
            ny = y + dy
            nx = x + dx
            if visited[ny][nx]: continue
            if S[ny][nx] == "

            if dist[ny][nx] > dist[y][x] + 1:
                dist[ny][nx] = dist[y][x] + 1
                visited[ny][nx] = True
                que.append((ny,nx))
    return True if visited[H][W] else False

if not bfs():
    print(-1)
    exit()

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

print(ans - (dist[H][W] + 1))

Solution (Python):
def main():
    from collections import deque

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

    already_black = sum(row.count('

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

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

    while dq:
        r, c = dq.popleft()
        if r == H - 1 and c == W - 1:
            break
        if r > 0 and s[r - 1][c] == '.' and not (~dist[r - 1][c] and dist[r - 1][c] <= dist[r][c] + 1):
            dist[r - 1][c] = dist[r][c] + 1
            dq.append((r - 1, c))
        if c > 0 and s[r][c - 1] == '.' and not (~dist[r][c - 1] and dist[r][c - 1] <= dist[r][c] + 1):
            dist[r][c - 1] = dist[r][c] + 1
            dq.append((r, c - 1))
        if r < H - 1 and s[r + 1][c] == '.' and not (~dist[r + 1][c] and dist[r + 1][c] <= dist[r][c] + 1):
            dist[r + 1][c] = dist[r][c] + 1
            dq.append((r + 1, c))
        if c < W - 1 and s[r][c + 1] == '.' and not (~dist[r][c + 1] and dist[r][c + 1] <= dist[r][c] + 1):
            dist[r][c + 1] = dist[r][c] + 1
            dq.append((r, c + 1))

    if ~dist[H - 1][W - 1]:
        ans = H * W - (dist[H - 1][W - 1] + already_black)
    else:
        ans = -1
    print(ans)


if __name__ == '__main__':
    main()

Solution (Python):
from collections import deque


def main():
    h, w = map(int, input().split())
    inf = 10 ** 9 + 7
    grid = [list(input()) for _ in range(h)]
    count = [[inf for _ in range(w)] for _ in range(h)]
    d = [[0, 1], [1, 0], [0, -1], [-1, 0]]
    wall = 0
    count[0][0] = 1
    for g in grid:
        wall += g.count("
    s = deque([[0, 0]])
    while s:
        y, x = s.popleft()
        if grid[y][x] == ".":
            grid[y][x] = "
            for dy, dx in d:
                if 0 <= y + dy < h and 0 <= x + dx < w and grid[y + dy][x + dx] == ".":
                    count[y + dy][x + dx] = min(count[y + dy][x + dx], count[y][x] + 1)
                    s.append([y + dy, x + dx])
    print(h * w - count[-1][-1] - wall if count[-1][-1] != inf else -1)


if __name__ == '__main__':
    main()

Solution (Python):
def main():
    H, W = (int(i) for i in input().split())
    c = [input() for i in range(H)]
    from collections import deque

    def bfs(sy, sx):
        que = deque()
        dist = [[-1]*W for i in range(H)]
        dist[sy][sx] = 0
        que.append((sy, sx))
        d = ((1, 0), (0, 1), (-1, 0), (0, -1))
        while que:
            uh, uw = que.popleft()
            for dy, dx in d:
                next_h = uh + dy
                next_w = uw + dx
                if not(0 <= next_h < H and 0 <= next_w < W):
                    continue
                if dist[next_h][next_w] != -1:
                    continue
                if c[next_h][next_w] == '
                    continue
                dist[next_h][next_w] = dist[uh][uw] + 1
                que.append((next_h, next_w))
        return dist
    d = bfs(0, 0)
    if d[-1][-1] == -1:
        return print(-1)
    seen = [True]*(d[H-1][W-1] + 1)
    ans = 0
    for h in range(H):
        for w in range(W):
            if c[h][w] == "
                continue
            elif d[h][w] != -1 and d[h][w] <= d[-1][-1] and seen[d[h][w]]:
                seen[d[h][w]] = False
                continue
            else:
                ans += 1
    print(ans)


if __name__ == '__main__':
    main()

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

ans = H*W - 2
for i in range(H):
    for j in range(W):
        if s[i][j] == "
            ans -= 1
q = collections.deque()
q.append((0, 0, 0))
flag = False
while(q):
    x, y, d = q.popleft()
    if x == W-1 and y == H - 1:
        ans -= (d-1)
        flag = True
        break
    if y > 0 and s[y-1][x] == ".":
        q.append((x, y-1, d+1))
        s[y-1][x] = "
    if x > 0 and s[y][x-1] == ".":
        q.append((x-1, y, d+1))
        s[y][x-1] = "
    if y < H - 1 and s[y+1][x] == ".":
        q.append((x, y+1, d+1))
        s[y+1][x] = "
    if x < W - 1 and s[y][x+1] == ".":
        q.append((x+1, y, d+1))
        s[y][x+1] = "

if flag:
    print(ans)
else:
    print(-1)

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


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



import collections
from collections import deque
def clear_maze(sx, sy, gx, gy):

    INF=-10**9
    distance = [[INF for i in range(w+2)] for j in range(h+2)]
    
    def bfs():
        d = deque()
        d.append((sx, sy))
        distance[sx][sy] = 0

        while len(d):
            x, y = d.popleft()
            if x == gx and y == gy:
                break
            for i in range(0, 4):
                nx, ny = x + [1, 0, -1, 0][i], y + [0, 1, 0, -1][i]

                if 0 <= nx<h and  0 <= ny<w:
                    if maze[nx][ny] != '
                        d.append((nx, ny))
                        distance[nx][ny] = distance[x][y] + 1

        return distance[gx][gy]

    return bfs()

v=clear_maze(0,0,h-1,w-1)
INF=-10**9
if v!=INF:
    print(ans-v-1)
else:
    print(-1)

Solution (Python):
from collections import deque
def bfs():
    
    d = [[float("inf")]*m for _ in range(n)]
    dx = [1,0,-1,0]
    dy = [0,1,0,-1]
    
    sx,sy = 0,0
    gx,gy = n-1,m-1
    
    q = deque([])
    q.append((sx,sy))
    d[sx][sy] = 0
    
    
    while q:
        p = q.popleft()
        
        if p[0] == gx and p[1] == gy:
            break
        
        for k in range(4):
            xi,yi = p[0]+dx[k],p[1]+dy[k]
            
            if 0 <= xi < n and 0 <= yi < m and maze[xi][yi] != "
                q.append((xi,yi))
                d[xi][yi] = d[p[0]][p[1]] + 1

    
    return d[gx][gy]

n,m = map(int, input().split())
maze = [list(input()) for _ in range(n)]
c = 0
for i in range(n):
    for j in range(m):
        if maze[i][j] == ".":
            c += 1
res = bfs()

if 0 < res < float("inf"):
    print(c - res -1)
else:
    print(-1)

Solution (Python):
import sys
from collections import deque as dq
input = sys.stdin.readline
H, W = map(int, input().split())
S = [list(input())[: -1] for _ in range(H)]
sm = 0
for i in range(H): sm += S[i].count(".")
Q = dq([0])
dp = [H * W] * (H * W)
dp[0] = 1
d = [-1, 0, 1, 0]
while len(Q):
  p = Q.popleft()
  y = p // W
  x = p % W
  for k in range(4):
    u = y + d[k]
    v = x + d[-1 - k]
    if u in range(H) and (v in range(W)):
      if S[u][v] == "
      if dp[u * W + v] == H * W:
        dp[u * W + v] = dp[p] + 1
        Q.append(u * W + v)

if dp[-1] == H * W: print(-1)
else: print(sm - dp[-1])

Solution (Python):
from collections import deque
h,w = map(int, input().split())
data = []
ans = h*w
for i in range(h):
    s = input()
    for x in s:
        if x == "
            ans -= 1
    data.append(s)
dist = [[-1]*w for _ in range(h)]
dist[0][0] = 0
queue = deque()
queue.append((0,0))
while queue:
    x,y = queue.popleft()
    for dx,dy in [[-1,0],[1,0],[0,1],[0,-1]]:
        tox = x+dx
        toy = y+dy
        if 0<=tox<h and 0<=toy<w and dist[tox][toy] == -1 and data[tox][toy] == ".":
            dist[tox][toy] = dist[x][y] + 1
            queue.append((tox,toy))

if dist[-1][-1] == -1:
    print(-1)
else:
    print(ans-dist[-1][-1]-1)

Solution (Python):
from collections import deque
h, w = map(int, input().split())
S = [input() for _ in range(h)]

que = deque()
que.append((0, 0))
dist = [[-1]*w for _ in range(h)]
dist[0][0] = 1
while que:
  y, x = que.pop()
  for i, j in ((-1, 0), (1, 0), (0, -1), (0, 1)):
    ny, nx = y+i, x+j
    if 0 <= ny < h and 0 <= nx < w:
      if S[ny][nx] == "
        continue
      if dist[ny][nx] == -1:
        dist[ny][nx] = dist[y][x] + 1
        que.appendleft((ny, nx))
  if ny == h-1 and nx == w-1:
    break
    
if dist[h-1][w-1] == -1:
  ans = -1
else:
  cnt = 0
  for i in range(h):
    cnt += S[i].count(".")
  ans = cnt - dist[h-1][w-1]
print(ans)

Solution (Python):
from collections import Counter,defaultdict,deque
from heapq import heappop,heappush,heapify
import sys,bisect,math,itertools,fractions,pprint
sys.setrecursionlimit(10**8)
mod = 10**9+7
INF = float('inf')
def inp(): return int(sys.stdin.readline())
def inpl(): return list(map(int, sys.stdin.readline().split()))

dx = [0,1,0,-1]; dy = [1,0,-1,0]
h,w = inpl()
g = [input() for _ in range(h)]
dist = [[-1] * w for _ in range(h)]
dist[0][0] = 0
q = deque()
q.append([0,0])

while q:
    y,x = q.popleft()
    for i in range(4):
        ny = y + dy[i]
        nx = x + dx[i]
        if 0 <= ny < h and 0 <= nx < w and dist[ny][nx] == -1 and g[ny][nx] == '.':
            dist[ny][nx] = dist[y][x] + 1
            q.append([ny,nx])

if dist[-1][-1] == -1:
    print(-1)
    quit()
bl = sum(i.count('
wh = dist[-1][-1] + 1
print(h*w - (wh+bl))

Solution (Python):
import queue
class gridMan:
  def __init__(s, L):
    s.L = L
    s.H = len(s.L)
    s.W = len(s.L[0])
  def makeWall(s, x = -2):
    w = len(s.L[0]) + 2
    s.L = [[x] * w] + [[x] + i + [x] for i in s.L] + [[x] * w]
  def dist(s, S): 
    T = [[-1] * s.W for _ in range(s.H)]
    q = queue.Queue()
    q.put([S[0], S[1]])
    T[S[0]][S[1]] = 0
    k = 0
    while not q.empty():
      h, w = q.get()
      k = T[h][w]
      for i, j in [[1, 0], [-1, 0], [0, 1], [0, -1]]:
        hh = h + i
        ww = w + j
        if s.L[hh + 1][ww + 1] >= 0 and T[hh][ww] == -1:
          q.put([hh, ww])
          T[hh][ww] = k + 1
    return T, k

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

ans = 0
D = [[0] * W for _ in range(H)]
for i in range(H):
  for j in range(W):
    if s[i][j] == ".":
      D[i][j] = 0
      ans += 1
    else:
      D[i][j] = -1

g = gridMan(D)
g.makeWall()

L, ma = g.dist([0, 0])

if L[-1][-1] == -1:
  print(-1)
  exit()

print(ans - L[-1][-1] - 1)

Solution (Python):
from collections import deque
H,W=map(int,input().split(' '))
S=[list(input()) for i in range(H)]
S[0][0]=1
next  = deque([[0,0]])
ans = H*W
while next:
    x,y =next.popleft()
    s = S[x][y]
    for i,j in [[1,0],[0,1],[-1,0],[0,-1]]:
        if 0<=x+i<H and 0<=y+j<W and S[x+i][y+j]=='.':
            S[x+i][y+j]=s+1
            next.append([x+i,y+j])
for i in S:
    ans -=i.count('
if type(S[H-1][W-1])==str:
    print(-1)
else:
    print(ans-S[H-1][W-1])

Solution (Python):
import collections
import itertools

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


def is_white(i, j):
    return i in range(H) and j in range(W) and s[i][j] == "."


def adjacent_white_squares(i, j):
    return [
        (i + di, j + dj)
        for di, dj in [(0, -1), (0, 1), (-1, 0), (1, 0)]
        if is_white(i + di, j + dj)
    ]


def distance_to_goal():
    distances = [[-1 for _ in range(W)] for _ in range(H)]
    distances[0][0] = 0
    queue = collections.deque([(0, 0)])

    d = 0
    while queue:
        i, j = queue.popleft()
        to_visit = [
            (k, l) for k, l in adjacent_white_squares(i, j) if distances[k][l] == -1
        ]
        for k, l in to_visit:
            if (k, l) == (H - 1, W - 1):
                return distances[i][j] + 1

            distances[k][l] = distances[i][j] + 1
            queue.append((k, l))

    return -1


def black_squares():
    return sum(1 for c in itertools.chain.from_iterable(s) if c == "


distance = distance_to_goal()
if distance == -1:
    print(-1)
else:
    print(H * W - (distance + 1) - black_squares())

Solution (Python):
from collections import deque
h,w=map(int,input().split())
s=[ input() for _ in range(h)]
dist=[ [float('inf') for _ in range(w)] for _ in range(h)]


dq=deque()
dist[0][0]=0
dq.append([0,0])
white=0
for i in s:
    white+=i.count('.')

while len(dq)>0:
    xx,yy=dq.popleft()
    if xx==h-1 and yy==w-1:
        break
    for i,j in zip([-1,0,1,0], [0,1,0,-1]):
            x=xx+i
            y=yy+j
            def valid(x,y):
                if not(x>=0 and x<h and y>=0 and y<w) == True:
                    return False
                if s[x][y]=='.':
                    return True
                else:
                    return False
            if valid(x,y):
                if dist[x][y]>dist[xx][yy]+1:
                    dist[x][y]=1+dist[xx][yy]
                    dq.append([x,y])

if dist[h-1][w-1]!=float('inf'):
    print(white-1-dist[h-1][w-1])
else:
    print(-1)

Solution (Python):
import collections

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

tizu = []
ans = 0
for i in range(h):
    s = list(input())
    ans += s.count(".")
    tizu.append(s)
  

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

def f(y,x,count):
    for i in range(4):
        newy = y + dy[i]
        newx = x + dx[i]
        if 0 <= newy and newy < h and 0 <= newx and newx < w:
            if tizu[newy][newx] == ".":
                q.append((newy,newx))
                tizu[newy][newx] = count


q = collections.deque()
q.append((0,0))
tizu[0][0] = 0
while q:
    s =  q.popleft()
    count = tizu[s[0]][s[1]]
    f(s[0],s[1],count+1)


if tizu[h-1][w-1] == ".":
    print(-1)
    exit()

            
print(ans-tizu[h-1][w-1] - 1)

Solution (Python):
from collections import deque
def bfs():
    d = [[float("inf")] * w for i in range(h)]
    dx = [1, 0, -1, 0]
    dy = [0, 1, 0, -1]
 
    que = deque([])
    que.append((sy, sx))
    d[sy][sx] = 0
 
    while que:
        p = que.popleft()
        if p[0] == gy and p[1] == gx:
            break
        for i in range(4):
            nx = p[0] + dx[i]
            ny = p[1] + dy[i]
            if 0 <= nx < h and 0 <= ny < w and s[nx][ny] != "
                que.append((nx, ny))
                d[nx][ny] = d[p[0]][p[1]] + 1
    if d[gy][gx] != float("inf"):
        return d[gy][gx]
    else:
        return -1
h, w = map(int, input().split())
sy, sx = 0, 0
gy, gx = h - 1, w - 1
s = [list(input()) for i in range(h)]
black = 0
for i in range(h):
    for j in range(w):
        if s[i][j] == "
            black += 1
if bfs() == -1:
    print(-1)
else:
    print(h * w - bfs() - black - 1)

Solution (Python):
def calc_distance(maze):
    sx,sy,gx,gy = 0,0,w-1,h-1
    
    INF = 10000000000
    field_x_length = w
    field_y_length = h
        
    distance = []
    for i in range(field_y_length):
        distance.append([])
        for j in range(field_x_length):
            distance[i].append(INF)
        
    queue = []
    queue.insert(0, (sy,sx))
    distance[sy][sx] = 0
        
    while queue:
        y, x = queue.pop()
        if(x == gx and y == gy):
            break
                
        for i in range(0,4):
            nx, ny = x +[1,0,-1,0][i], y +[0,1,0,-1][i]
                
            if(0 <= nx and nx < field_x_length and 0 <= ny and ny < field_y_length and maze[ny][nx] != '
                queue.insert(0,(ny, nx))
                distance[ny][nx] = distance[y][x] + 1
    return distance[gy][gx]
    
h,w = map(int, input().split())
maze = [input() for _ in range(h)]

import collections
count = 0
for i in range(0,h):
    c = collections.Counter(maze[i])
    count += c["

if (calc_distance(maze) < 200):
    print(w*h - count - calc_distance(maze) -1)
else:
    print(-1)

Solution (Python):


import sys
import math
from bisect import bisect_right as br
from bisect import bisect_left as bl
sys.setrecursionlimit(2147483647)
from heapq import heappush, heappop,heappushpop
from collections import defaultdict
from itertools import accumulate
from collections import Counter
from collections import deque
from operator import itemgetter
from itertools import permutations
mod = 10**9 + 7
inf = float('inf')
def I(): return int(sys.stdin.readline())
def LI(): return list(map(int,sys.stdin.readline().split()))

h,w = LI()
s = [input() for _ in range(h)]
cnt = h*w-1
for i in range(h):
    for j in range(w):
        if s[i][j] == '
            cnt -= 1

dx,dy = [1,0,-1,0],[0,1,0,-1]
que = deque()
que.append((0,0))
d = [[0]*w for _ in range(h)]
check = [[True]*w for _ in range(h)]
check[0][0] = False
while que:
    x,y = que.popleft()
    for i in range(4):
        nx,ny = x+dx[i], y+dy[i]
        if 0 <= nx < w and 0 <= ny < h:
            if check[ny][nx] and s[ny][nx] == '.':
                check[ny][nx] = False
                d[ny][nx] = d[y][x] + 1
                que.append((nx,ny))
if d[h-1][w-1] == 0:
    print(-1)
else:
    print(cnt-d[h-1][w-1])

Solution (Python):
from collections import deque

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

dh = [1,0,-1,0]
dw= [0,1,0,-1]

def bfs():
  m = [[float('inf')]*w for _ in range(h)]
  que = deque([])
  que.append([0,0])
  m[0][0] = 0
  
  while que:
    cur = que.popleft()
    
    
    
    for i in range(4):
      nh = cur[0] + dh[i]
      nw = cur [1] + dw[i]
      
      if nh >= 0 and nh < h and nw >= 0 and nw < w and \
          m[nh][nw] == float('inf') and par[nh][nw] == '.':
        que.append([nh,nw])
        m[nh][nw] = m[cur[0]][cur[1]] + 1
        
  return m

m = bfs()

if m[h-1][w-1] == float('inf'):
  print(-1)
  exit()

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

print(cnt - m[h-1][w-1] -1)

Solution (Python):
from collections import deque
import sys
sys.setrecursionlimit(10 ** 6)
def input():
    return sys.stdin.readline()[:-1]
 
H,W=[int(i) for i in input().split()]
C=[input() for _ in range(H)]
C=[list(i) for i in C] 
 
ans = 10**9
 
visited_list = [[10**9]*W for _ in range(H)]
stack = deque([[0, 0, 0]])
visited_list[0][0] = 0
 
w_cnt=0
for c in C: w_cnt += c.count(".")
 
def dfs(town, visited_list, stack):
    global ans
    flag = 0
    while len(stack) > 0:
        h, w, cnt = stack.pop()
        if h == H-1 and w == W-1 and ans > cnt:
            ans = cnt
            flag = 1
            continue
        for j, k in ([1, 0], [0, 1], [-1, 0], [0, -1]):
            new_h, new_w = h+j, w+k
            if new_h < 0 or new_h >= H or new_w < 0 or new_w >= W:
                continue
            if  town[new_h][new_w] != "
                visited_list[new_h][new_w] = cnt + 1
                stack.append([new_h, new_w, cnt+1])
    if flag: 
        ans = w_cnt-(ans+1)
        return ans
    else: return -1
 
print(dfs(C, visited_list, stack))

Solution (Python):
import sys
from io import StringIO
import unittest
import queue


def resolve():
    
    h, w = map(int, input().split())

    grid = [["" for i in range(w)] for j in range(h)]

    for i in range(h):
        line = input()
        for j in range(w):
            grid[i][j] = line[j:j+1]

    
    
    distance = [[-1 for i in range(w)] for j in range(h)]
    que = queue.Queue()

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

    while not que.empty():

        now = que.get()

        
        for move_y, move_x in ((1, 0), (-1, 0), (0, 1), (0, -1)):

            
            target = [now[0] + move_y, now[1] + move_x]
            if not h > target[0] >= 0 or not w > target[1] >= 0:
                continue

            
            if grid[target[0]][target[1]] == '
                continue

            
            if not distance[target[0]][target[1]] == -1:
                continue

            
            que.put(target)

            
            distance[target[0]][target[1]] = distance[now[0]][now[1]] + 1

    
    shortest_distance = distance[h-1][w-1]
    
    if shortest_distance == -1:
        print("-1")
        return

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

    
    a = len(grid) * len(grid[0]) - not_repaint_count - shortest_distance
    print(a)


class TestClass(unittest.TestCase):
    def assertIO(self, input, output):
        stdout, stdin = sys.stdout, sys.stdin
        sys.stdout, sys.stdin = StringIO(), StringIO(input)
        resolve()
        sys.stdout.seek(0)
        out = sys.stdout.read()[:-1]
        sys.stdout, sys.stdin = stdout, stdin
        self.assertEqual(out, output)
    def test_入力例_1(self):
        input = """3 3
..

..."""
        output = """2"""
        self.assertIO(input, output)
    def test_入力例_2(self):
        input = """10 37
.....................................
...
..
..
.
.
.
.
.
....................................."""
        output = """209"""
        self.assertIO(input, output)

if __name__ == "__main__":
    resolve()

Solution (Python):
from collections import deque
h, w = map(int, input().split())
a = ["
maze = [a]
nsum = 0
for i in range(h):
  b = list(input())
  nsum += b.count(".")
  maze.append(["
maze.append(a)
d = [[-1]*(w+2) for i in range(h+2)]  
def bfs(i, j):
  q = deque()
  q.append([i, j])
  d[i][j] = 0
  while q:
    p = q.popleft()
    if p[0] == h and p[1] == w:
      break
    for i, j in ([-1, 0], [0, -1], [1, 0], [0, 1]):
      np = [p[0]+i, p[1]+j]
      if maze[np[0]][np[1]] != "
        q.append(np)
        d[np[0]][np[1]] = d[p[0]][p[1]] + 1
  if d[h][w] == -1:
    return -1
  if d[h][w] != -1:
    return nsum - d[h][w] - 1
print(bfs(1, 1))

Solution (Python):
from collections import deque
def gridbfs(grid,sy,sx):
    INF = 10**18
 
    gridy = len(grid)
    gridx = len(grid[0])
 
    dist = [[INF]*gridx for _ in range(gridy)]
    dist[sy][sx] = 0
    q = deque([(sy,sx)])
 
    while q:
        y,x = q.popleft()
        for dy,dx in [(-1,0),(1,0),(0,-1),(0,1)]:
            yy,xx = y+dy, x+dx
            if not (0 <= yy < gridy and 0 <= xx < gridx):
                continue
            if grid[yy][xx] == '
                continue
            if dist[yy][xx] != INF:
                continue
            dist[yy][xx] = dist[y][x] + 1
            q.append((yy,xx))
 
    return dist
 
H,W = map(int,input().split())
grid = [input() for i in range(H)]
d = gridbfs(grid,0,0)
b = 0
for h in range(H):
    for w in range(W):
        if grid[h][w] == '
            b += 1
 
print(max(H*W-b-d[H-1][W-1]-1,-1))

Solution (Python):
from collections import deque

def resolve():
    H, W = map(int, input().split())
    grid = [["
    cnt = 0
    for i in range(1,H+1):
        g = list(input())
        cnt += g.count(".")
        grid[i][1:-1] = g

    q = deque()
    q.append((1, 1))
    dxy = [(-1, 0), (0, 1), (1, 0), (0, -1)]
    visited = [[0] * (W + 2) for _ in range(H + 2)]
    visited[1][1] = 1

    while q:
        x, y = q.popleft()
        for dx, dy in dxy:
            nx = dx + x
            ny = dy + y
            if grid[ny][nx] == "." and visited[ny][nx] == 0:
                visited[ny][nx] += 1 + visited[y][x]
                q.append((nx, ny))
    if visited[H][W] > 0:
        ans = cnt - visited[H][W]
    else:
        ans = -1

    return print(ans)

if __name__ == "__main__":
    resolve()

Solution (Python):
from queue import Queue

H, W = map(int, input().split())
field = [list(input()) for _ in range(H)]
dist = [[-1 for _ in range(W)] for __ in range(H)]
searched = [[False for _ in range(W)] for __ in range(H)]
bfq = Queue()

def search(x, y, d):
    if not (0 <= x < W and 0 <= y < H):
        return
    if searched[y][x]:
        return
    searched[y][x] = True
    if field[y][x] == '
        return
    dist[y][x] = d
    bfq.put([x, y, d])
    return

search(0, 0, 0)

while not (searched[H-1][W-1] or bfq.empty()):
    x, y, d = bfq.get()
    search(x-1, y, d+1)
    search(x+1, y, d+1)
    search(x, y-1, d+1)
    search(x, y+1, d+1)

walls = sum(list(map(lambda x: x.count('

print(W*H - walls - dist[H-1][W-1] - 1 if searched[H-1][W-1] else "-1")

Solution (Python):


from collections import deque

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

dist = [[0] * W for _ in range(H)]
dist[0][0] = 1 
q = deque([(0, 0)])

while q:
    y, x = q.popleft()
    for i, j in [(-1, 0), (1, 0), (0, -1), (0, 1)]:
        if (not (0 <= y + i < H and 0 <= x + j < W)
                or graph[y + i][x + j] == "
                or dist[y + i][x + j] > 0):
            continue
            
        dist[y + i][x + j] = dist[y][x] + 1
        q.append((y + i, x + j))

if dist[H-1][W-1] > 0:
    print(W * H - dist[H-1][W-1] - sum(s.count("
else:
    print(-1)

Solution (Python):


from collections import deque

if __name__ == "__main__":
    H, W = list(map(int, input().split()))
    A = []
    A.append('
    for i in range(H):
        A.append('
    A.append('

    
    

    queue = deque()
    queue.appendleft((1, 1, 1))
    checked = set()
    goal = (H, W)

    dist = -1
    while queue:
        i, j, d = queue.pop()
        if (i, j) in checked:
            continue
        checked.add((i, j))

        if (i, j) == goal:
            dist = d

        for dx, dy in [(-1, 0), (1, 0), (0, -1), (0, 1)]:
            ii = i + dx
            jj = j + dy
            if A[ii][jj] == '.':
                queue.appendleft((ii, jj, d+1))

    if dist == -1:
        result = -1
    else:
        white = sum([row.count('.') for row in A])
        result = white - dist
    print(result)