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 DFS(graph,start,end):
    
    c,r = len(graph[0]),len(graph)
    que = deque([])
    que.append(start)
    visited = [[0 for _ in range(c)] for _ in range(r)]

    while visited[end[0]][end[1]]==0:
        if len(que)== 0:
            break
        now = que.popleft()
        y,x = now
        up,down,left,right = [y-1,x],[y+1,x],[y,x-1],[y,x+1]

        
        if visited[up[0]][up[1]]==0:
            if graph[up[0]][up[1]]==".":
                que.append(up)
                visited[up[0]][up[1]]= visited[y][x]+1
            
        
        if visited[down[0]][down[1]]==0:
            if graph[down[0]][down[1]]==".":
                que.append(down)
                visited[down[0]][down[1]]= visited[y][x]+1
        
        if visited[left[0]][left[1]]==0:
            if graph[left[0]][left[1]]==".":
                que.append(left)
                visited[left[0]][left[1]]= visited[y][x]+1
        
        if visited[right[0]][right[1]]==0:
            if graph[right[0]][right[1]]==".":
                que.append(right)
                visited[right[0]][right[1]]= visited[y][x]+1
    
    return visited[end[0]][end[1]]

def main():
    h,w = map(int,input().split())
    ls = [list(input()) for _ in range(h)]
    cnt = 0
    for i in range(h):
        for j in range(w):
            if ls[i][j]=="
                cnt += 1

    dummy = ["
    for i in range(h):
        ls[i].append("
        ls[i].insert(0,"
    ls.insert(0,dummy)
    ls.append(dummy)

    step = DFS(ls,[1,1],[h,w])+1

    if step == 1:
        print(-1)
    else:
        print(h*w-step-cnt)


if __name__ == "__main__":
    main()

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

origin = 0
for i in maze:
    origin += i.count('



def bfs(y, x, cnt):
    if (y < 0 or h <= y or x < 0 or w <= x):
        return
    if (maze[y][x] != '.'):
        return
    maze[y][x] = cnt
    if (y == h - 1 and x == w - 1):
        return cnt
    queue.append([y + 1, x, cnt + 1])
    queue.append([y - 1, x, cnt + 1])
    queue.append([y, x+1, cnt+1])
    queue.append([y, x-1, cnt+1])


queue.append([0, 0, 0])
while (len(queue) > 0):
    l = queue.popleft()
    bfs(l[0], l[1], l[2])
if (maze[h - 1][w - 1] == '.'):
    print(-1)
    exit()


print(h*w-origin-maze[h-1][w-1]-1)

Solution (Python):
from collections import deque
"""
-1 -> not visited
else -> step count
"""
def bfs(maze, visited, sh, sw):
    stack = deque([[sh, sw]])
    visited[sh][sw] = 1
    while stack:
        h, w = stack.popleft()
        
        if h == H - 1 and w == W - 1:
            break
        for j, k in ([1, 0], [-1, 0], [0, 1], [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
            elif maze[new_h][new_w] != "
                 visited[new_h][new_w] == -1:
                visited[new_h][new_w] = visited[h][w] + 1
                stack.append([new_h, new_w])
    
    return visited[H-1][W-1]

if __name__ == "__main__":
    H, W = map(int, input().split())
    maze = [input() for _ in range(H)]

    sh, sw = 0, 0

    visited = [[-1] * W for _ in range(H)]
    
    step_cnt = bfs(maze, visited, sh, sw)

    white_cnt = sum([i.count(".") for i in maze])

    if step_cnt > 0:
        print(white_cnt - step_cnt)
    else:
        print(-1)

Solution (Python):

def bfs() -> None:
    dxy = [(1, 0), (-1, 0), (0, 1), (0, -1)]
    q = [(0, 0)]
    while q:
        x, y = q.pop(0)
        for dx, dy in dxy:
            nx, ny = x + dx, y + dy  
            
            if 0 <= nx < H and 0 <= ny < W and S[nx][ny] == "." and D[nx][ny] == 0:
                q.append((nx, ny))
                D[nx][ny] = D[x][y] + 1


def main():
    
    global H, W, S, D
    H, W, *S = open(0).read().split()
    H, W = int(H), int(W)
    D = [[0] * W for _ in range(H)]  
    D[0][0] = 1
    bfs()
    white, x = sum(s.count(".") for s in S), D[-1][-1]
    ans = white - x if x else -1  
    print(ans)


if __name__ == "__main__":
    main()

Solution (Python):

from collections import deque

def bfs() -> None:
    dxy = [(1, 0), (-1, 0), (0, 1), (0, -1)]
    q = deque([(0, 0)])
    while q:
        x, y = q.popleft()
        for dx, dy in dxy:
            nx, ny = x + dx, y + dy  
            
            if 0 <= nx < H and 0 <= ny < W and S[nx][ny] == "." and D[nx][ny] == 0:
                q.append((nx, ny))
                D[nx][ny] = D[x][y] + 1


def main():
    
    global H, W, S, D
    H, W, *S = open(0).read().split()
    H, W = int(H), int(W)
    D = [[0] * W for _ in range(H)]  
    D[0][0] = 1
    bfs()
    white, x = sum(s.count(".") for s in S), D[-1][-1]
    ans = white - x if x else -1  
    print(ans)


if __name__ == "__main__":
    main()

Solution (Python):
import sys



lines = [x.strip() for x in sys.stdin.readlines()]
h,w=[int(x) for x in lines[0].split()]
map=[[x for x in y] for y in lines[1:]]
memo=[[-1 for x in y] for y in lines[1:]]

def slv(lines):
    white = sum([r.count(".") for r in map])
    q=[[0,0]]
    memo[0][0]=1
    while q!=[]:
        x,y=q.pop(0)
        for pm1 in [1,-1]:
            if x+pm1>=0 and x+pm1<w:
                if map[y][x+pm1] == "." and memo[y][x+pm1]<0:
                    q.append([x+pm1,y])
                    memo[y][x+pm1]=memo[y][x]+1
            if y+pm1>=0 and y+pm1<h:
                if map[y+pm1][x] == "." and memo[y+pm1][x]<0:
                    q.append([x,y+pm1])
                    memo[y+pm1][x]=memo[y][x]+1

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

    if goal == -1:
        return -1
    else:
        return white - goal
    


if __name__ == "__main__":
    print(slv(lines))

Solution (Python):
import queue

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

maze = [0 for i in range(h)]
maze2 = [[10**5 for i in range(w)] for j in range(h)]

for i in range(h):
    s = input()
    li = []
    for j in s:
        li.append(j)
    maze[i] = li
 
cnt = 0
for i in range(h):
    for j in range(w):
        if maze[i][j] == "
            cnt += 1

que = queue.Queue()
maze2[0][0] = 1
que.put([0,0])

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

while not que.empty():
    q = que.get()
    a = q[0]
    b = q[1]
    
    for i in range(4):
        c = a+dx[i]
        d = b+dy[i]
       
        
        if ((0<=c) and (c<h) and (0<=d) and (d<w) and (maze2[c][d]==100000) and (maze[c][d]=='.')):
            maze2[c][d] = maze2[a][b]+1
            que.put([c,d])
            

ans = maze2[h-1][w-1]

if maze2[h-1][w-1] == 100000:
    print(-1)
else:
    print(h*w - ans - cnt)

Solution (Python):
t,*g=open(0);h,w=map(int,t.split());v=[[0]*w for _ in range(h)];v[0][0]=1;q=[(0,0)]
while q:
	a,b=q.pop(0)
	for c,d in((-1,0),(0,-1),(1,0),(0,1)):
		x=a+c;y=b+d
		if w>x>=0<=y<h and v[y][x]<1 and g[y][x]==".":q+=[(x,y)];v[y][x]=v[b][a]+1
t=v[-1][-1];print((-1,h*w-sum(c.count("

Solution (Python):
from collections import deque
h,w=map(int,input().split())
grid=[input() for _ in range(h)]
vis=[[0]*w for _ in range(h)]
vis[0][0]=1
que=deque([(0,0)])
while que:
	p,q=que.popleft()
	for x,y in ((-1,0),(0,-1),(1,0),(0,1)):
		if 0<=p+x<w and 0<=q+y<h and vis[q+y][p+x]<1 and grid[q+y][p+x]==".":
			vis[q+y][p+x]=vis[q][p]+1
			que.append((p+x,q+y))
if not vis[h-1][w-1]:
	print(-1)
else:
	print(h*w-sum(c.count("

Solution (Python):
from collections import deque, Counter
import sys
H, W = map(int, input().split())
count = 0
grid = ['s' for h in range(H)]
for h in range(H):
    grid[h] = list(input())
    tmp_count = Counter(grid[h])['
    if tmp_count == W:
        print(-1)
        sys.exit()
    count += tmp_count

deq = deque([(0, 0)])
visited = [[-1 for w in range(W)] for h in range(H)]
visited[0][0] = 0
route = 0
while deq:
    for _ in range(len(deq)):
        h, w = deq.popleft()
        
        if (h, w) == (H - 1, W - 1):
            print(H * W - visited[h][w] - 1 - count)
            sys.exit()
        for j, k in ([-1, 0], [0, -1], [0, 1], [1, 0]):
            new_h, new_w = h + j, w + k
            if 0 <= new_h <= H - 1 and 0 <= new_w <= W - 1:
                if grid[new_h][new_w] != '
                    visited[new_h][new_w] = visited[h][w] + 1
                    deq.append((new_h, new_w))
print(-1)

Solution (Python):
class Queue:
    def __init__(self, data=[]):
        self.data = data

    def enqueue(self, x):
        self.data.append(x)  

    def dequeue(self):
        return self.data.pop(0)  

    def is_Empty(self):  
        if len(self.data) == 0:
            return True
        else:
            return False


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

gridgraph = [list(input()) for _ in range(H)]

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

flag = [[False] * W for _ in range(H)]
counter = [[0] * W for _ in range(H)]
counter[0][0] = 1
flag[0][0] = True
q = Queue()

q.enqueue((0, 0))

adjacent = [(1, 0), (0, 1), (-1, 0), (0, -1)]  
while not q.is_Empty():
    cy, cx = q.dequeue()
    for dy, dx in adjacent:
        if cy+dy >= H or cy+dy < 0 or cx+dx >= W or cx+dx < 0:
            continue
        if flag[cy+dy][cx+dx] or gridgraph[cy+dy][cx+dx] == '
            continue
        counter[cy+dy][cx+dx] = counter[cy][cx] + 1
        flag[cy+dy][cx+dx] = True
        q.enqueue((cy+dy, cx+dx))


if flag[H-1][W-1]:
    print(H*W - counter[H-1][W-1] - black_count)
else:
    print(-1)

Solution (Python):
from collections import deque
H, W = map(int, input().split())
sy, sx = 0, 0
gy, gx = H-1, W-1
field = [list(input()) for _ in range(H)]
step = [[-1]*W for _ in range(H)]
step[sy][sx] = 0
tovisit = deque()
tovisit.append([sy, sx])

while tovisit:
  y, x = tovisit.popleft()
  for next_y, next_x in [[y+1, x], [y-1, x], [y, x+1], [y, x-1]]:
    if 0 <= next_y < H and 0 <= next_x < W and field[next_y][next_x] != '
      if step[next_y][next_x] == -1:
        tovisit.append([next_y, next_x])
        step[next_y][next_x] = step[y][x] + 1

sum_block = sum([l.count('
steps = step[gy][gx]
print(-1 if steps == -1 else H*W - sum_block - steps - 1)

Solution (Python):
from collections import deque
import sys
input = sys.stdin.readline
INF = float('inf')

def main():
    def bfs(x, y):
        L = [[INF]*W for _ in range(H)]
        L[0][0] = 1
        Q = deque([[0,0]])
        while len(Q)!=0:
            x, y = Q.popleft()
            if x==W-1 and y==H-1:
                break
            for i in range(4):
                nx, ny = x + [1,0,-1,0][i], y + [0,1,0,-1][i]
                if 0<=nx and nx<W and 0<=ny and ny<H:
                    if M[ny][nx]=='.' and L[ny][nx]==INF:
                        Q.append([nx, ny])
                        L[ny][nx] = L[y][x] + 1
        return L[H-1][W-1]
    
    H, W = map(int, input().split())
    M = []
    cnt = 0
    for _ in range(H):
        m = list(input()[:-1])
        cnt += m.count('
        M.append(m)

    b = bfs(0, 0)
    if b==INF:
        print(-1)
    else:
        print(H*W - cnt - b)


if __name__ == '__main__':
    main()

Solution (Python):
import collections

h, w = map(int, input().split())
ls = [input().rstrip() for _ in range(h)]
ds = [[float('inf') for _ in range(w)] for _ in range(h)]
ds[0][0] = 1

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


def bfs(x, y):
    for i in range(4):
        dx, dy = dxdy[i]
        nx = x + dx
        ny = y + dy
        if 0 <= nx < w and 0 <= ny < h and ls[ny][nx] == '.':
            if ds[ny][nx] == float('inf'):
                ds[ny][nx] = ds[y][x] + 1
                q.append([nx, ny])


q = collections.deque([[0, 0]])
while q:
    x, y = q.popleft()
    bfs(x, y)
d = ds[h - 1][w - 1]
if d < float('inf'):
    s = sum([l.count('.') for l in ls])
    print(s - d)
else:
    print(-1)

Solution (Python):
h, w = map(int, input().split())
ls = [input().rstrip() for _ in range(h)]
ds = [[float('inf') for _ in range(w)] for _ in range(h)]
ds[0][0] = 1

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

q = [[0, 0]]


def bfs():
    while q:
        x, y = q.pop()
        for i in range(4):
            dx, dy = dxdy[i]
            nx = x + dx
            ny = y + dy
            if 0 <= nx < w and 0 <= ny < h and ls[ny][nx] == '.':
                if ds[ny][nx] > ds[y][x] + 1:
                    ds[ny][nx] = ds[y][x] + 1
                    q.append([nx, ny])


bfs()
d = ds[h - 1][w - 1]
if d < float('inf'):
    s = sum([l.count('.') for l in ls])
    print(s - d)
else:
    print(-1)

Solution (Python):
h, w = map(int, input().split())
ls = [input().rstrip() for _ in range(h)]
ds = [[float('inf') for _ in range(w)] for _ in range(h)]
ds[0][0] = 1

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


def bfs(q):
    while q:
        x, y = q.pop()
        for i in range(4):
            dx, dy = dxdy[i]
            nx = x + dx
            ny = y + dy
            if 0 <= nx < w and 0 <= ny < h and ls[ny][nx] == '.':
                if ds[ny][nx] > ds[y][x] + 1:
                    ds[ny][nx] = ds[y][x] + 1
                    q.append([nx, ny])


q = [[0, 0]]
bfs(q)
d = ds[h - 1][w - 1]
if d < float('inf'):
    s = sum([l.count('.') for l in ls])
    print(s - d)
else:
    print(-1)

Solution (Python):
import sys

sys.setrecursionlimit(10**6)

h, w = map(int, input().split())
ls = [input().rstrip() for _ in range(h)]
ds = [[float('inf') for _ in range(w)] for _ in range(h)]
ds[0][0] = 1

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


def dfs(x, y):
    for i in range(4):
        dx, dy = dxdy[i]
        nx = x + dx
        ny = y + dy
        if 0 <= nx < w and 0 <= ny < h and ls[ny][nx] == '.':
            if ds[ny][nx] > ds[y][x] + 1:
                ds[ny][nx] = ds[y][x] + 1
                dfs(nx, ny)


dfs(0, 0)
d = ds[h - 1][w - 1]
if d < float('inf'):
    s = sum([l.count('.') for l in ls])
    print(s - d)
else:
    print(-1)

Solution (Python):
import collections
H,W = map(int,input().split())
Map = []
black_cnt = 0
for i in range(H):
    tmp = list(input())
    black_cnt += tmp.count('
    Map.append(tmp)

Counter = [[float('inf') for j in range(W)]for i in range(H)]
Visited = [[False for j in range(W)]for i in range(H)]
q = collections.deque()
q.append((0,0,0))
while q:
    y,x,cnt = q.popleft()
    if 0>y or H<=y or 0>x or W<=x:
        continue
    if Map[y][x] == '
        continue
    Counter[y][x] = min(Counter[y][x],cnt)
    if Visited[y][x]:
        continue
    Visited[y][x]=True
    
    cnt += 1
    q.append((y+1,x,cnt))
    q.append((y-1,x,cnt))
    q.append((y,x+1,cnt))
    q.append((y,x-1,cnt))
if Visited[H-1][W-1] == False:
    print('-1')
else:
    print(H*W-Counter[H-1][W-1]-black_cnt-1)

Solution (Python):
import collections
H,W = map(int,input().split())
Map = []
black_cnt = 0
for i in range(H):
    tmp = list(input())
    black_cnt += tmp.count('
    Map.append(tmp)

Counter = [[float('inf') for j in range(W)]for i in range(H)]
Visited = [[False for j in range(W)]for i in range(H)]
q = collections.deque()
q.append((0,0,0))
while q:
    y,x,cnt = q.popleft()
    if 0>y or H<=y or 0>x or W<=x:
        continue
    if Map[y][x] == '
        continue
    if cnt > Counter[y][x]:
        continue
    if Visited[y][x]:
        continue
    Visited[y][x]=True
    Map[y][x] = cnt
    cnt += 1
    q.append((y+1,x,cnt))
    q.append((y-1,x,cnt))
    q.append((y,x+1,cnt))
    q.append((y,x-1,cnt))
if Visited[H-1][W-1] == False:
    print('-1')
else:
    print(H*W-Map[H-1][W-1]-black_cnt-1)

Solution (Python):
import numpy as np
H, W = map(int,input().split())
S = []
maxval = 10000
blacknum = 0
for i in range(H):
    S.append(input())
board = np.zeros((H+2,W+2), dtype=np.int64)
dist = np.full((H+2,W+2), maxval, dtype=np.int64)
for i in range(1,H+1):
    for j in range(1,W+1):
        if S[i-1][j-1] == '
            board[i][j] = 1
            dist[i][j] = maxval
            blacknum += 1
        else:
            board[i][j] = 0
            dist[i][j] = maxval
dist[1][1] = 0
for iter in range(563):
    update_flag = 0
    for i in range(1,H+1):
        for j in range(1,W+1):
            if board[i][j] == 1:
                continue
            newdist = min([dist[i-1][j], dist[i+1][j], dist[i][j-1], dist[i][j+1]])+1
            if newdist < dist[i][j]:
                dist[i][j] = newdist
                update_flag = 1
    if update_flag == 0:
        break
pass_cell = dist[H][W] + 1
maxscore = H*W - pass_cell - blacknum
if pass_cell >= maxval:
    print(-1)
else:
    print(maxscore)

Solution (Python):
from collections import deque


def main():
    h, w = [int(i) for i in input().split()]
    f = []
    c_of_sharp = 0
    for i in range(h):
        line = list(input())
        for c in line:
            if c == '
                c_of_sharp += 1
        f.append(line)
    sy, sx = (0, 0)
    q = deque([[sy, sx]])
    BIG = 100000
    f2 = [[BIG for i in range(w)] for j in range(h)]
    f2[0][0] = 0
    s = True

    while q:
        y, x = q.pop()
        if (y, x) == (h-1, w-1):
            break
        for dy, dx in [[-1, 0], [1, 0], [0, -1], [0, 1]]:
            if 0 <= y+dy < h and 0 <= x+dx < w and f2[y+dy][x+dx] == BIG and \
                f[y+dy][x+dx] != '
                f2[y+dy][x+dx] = f2[y][x]+1
                q.appendleft([y+dy, x+dx])
    else:
        s = False
        print(-1)

    if s:
        print(h*w-f2[h-1][w-1]-c_of_sharp-1)


if __name__ == '__main__':
    main()

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

maze = ['
maze += ['
maze.append('
maze_map = [[float('inf')]*(W+2) for _ in range(H+2)]
maze_map[1][1] = 1


mem = [(1,1)]

while True:
  if len(mem) == 0: break
  x,y = mem.pop()
  for dx,dy in [(1,0),(-1,0),(0,1),(0,-1)]:
    if maze[y+dy][x+dx] == '.':
      if maze_map[y+dy][x+dx] > maze_map[y][x]+1:
        maze_map[y+dy][x+dx] = maze_map[y][x]+1
        mem.append((x+dx,y+dy))
        
if maze_map[H][W] == float('inf'):
  print(-1)
else:
  w = sum(m.count('.') for m in maze)
  print(w-maze_map[H][W])

Solution (Python):
import queue
Data = []
Path = []
H,W = map(int,input().split())

def bfs(sy,sx,R,C):
    q = queue.Queue()
    q.put([sy,sx])

    diff = [[1,0],[-1,0],[0,1],[0,-1]]
    Path[sy][sx] = 0
    Data[sy][sx] = 'x'

    count = 1 
    while not q.empty():
        x = q.get()
        r,c = x
        for di in diff:
            rr = r + di[0]
            cc = c + di[1]

            if rr >= 0 and cc >= 0 and rr < R and cc < C:
                if Data[rr][cc] == '.':
                    q.put([rr,cc])
                    Path[rr][cc] = Path[r][c]+1
                    Data[rr][cc] = 'x'

for _ in range(H):
    Data.append(list(input()))
block = 0
for d in Data:
    for x in d:
        if x == '
            block += 1

for _ in range(H):
    Path.append([-1]*W)
bfs(0,0,H,W)
n = Path[H-1][W-1]

if n == -1:
    print(-1)
else:
    ans = H*W-block-n-1
    print(ans)

Solution (Python):
from collections import deque

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

move = ((1, 0), (-1, 0), (0, 1), (0, -1))
visited = [[False] * W for _ in range(H)]


que = deque([(0, 0, 1)])


result = -1
while que:
    ci, cj, step = que.popleft()
    visited[ci][cj] = True
    if (ci, cj) == (H-1, W-1):
        result = step
        break

    for di, dj in move:
        ni, nj = ci + di, cj + dj
        if not (0 <= ni < H and 0 <= nj < W) or visited[ni][nj]:
            continue
        if S[ni][nj] == '.':
            visited[ni][nj] = True
            que.append((ni, nj, step+1))

if result == -1:
    print(-1)
else:
    W = 0
    for s in S:
        W += s.count('.')
    print(W-result)

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

Q = [[0, 0, 0]]
V = [[0] * w for i in range(h)]
D = [[float("inf")] * w for i in range(h)]
st = 0
while st < len(Q):
    
    if Q[st] == [h-1, w-1]:
        D[-1][-1] = Q[st][2]
        break
    else:
        i = Q[st][0]
        j = Q[st][1]
        d = min(Q[st][2], D[i][j])
        D[i][j] = d

        if V[i][j] == 0:
            V[i][j] = 1
            for di, dj in [[-1,0], [1,0], [0,-1], [0,1]]:
                if 0 <= i+di <= h-1 and 0 <= j+dj <= w-1 and S[i+di][j+dj] == "." and V[i+di][j+dj] == 0:
                    Q.append([i+di, j+dj, d+1])
    st += 1

white = sum([S[i].count(".") for i in range(h)])




ans = white - D[-1][-1] - 1
if ans == -float("inf"):
    ans = -1
print(ans)

Solution (Python):
from collections import Counter,defaultdict,deque
import sys,heapq,bisect,math,itertools,string,queue
sys.setrecursionlimit(10**8)
mod = 10**9+7
def inp(): return int(sys.stdin.readline())
def inpl(): return list(map(int, sys.stdin.readline().split()))
def inpl_str(): return list(sys.stdin.readline().split())
def inpln(n): return list(int(sys.stdin.readline()) for i in range(n))

h,w = inpl()
dx = [1,0,-1,0]
dy = [0,1,0,-1]
field = []
for i in range(h):
    field.append(list(input()))

dist = [[-1 for i in range(w)] for j in range(h)]
dist[0][0] = 0
q = deque([[0,0]])
while q:
    v = q.popleft()
    for i in range(4):
        nh = v[0] + dx[i]
        nw = v[1] + dy[i]
        if nh < 0 or nh >= h or nw < 0 or nw >= w:
            continue
        if field[nh][nw] == '
            continue
        if dist[nh][nw] != -1:
            continue
        dist[nh][nw] = dist[v[0]][v[1]] + 1
        q.append([nh,nw])

if dist[h-1][w-1] == -1:
    print(-1)
else:
    black_cnt = 0
    for i in range(h):
        for j in range(w):
            if field[i][j] == '
                black_cnt += 1
    print(h*w - black_cnt - dist[h-1][w-1] - 1)

Solution (Python):
H,W = map(int,input().split())
S = ["
for i in range(H):
    s = input()
    S.append("
S.append("

white = 0
for i in range(H+2):
    for j in range(W+2):
        if S[i][j] == ".":
            white += 1
flag = 0 
visited = {}
import heapq

heap = []
heapq.heappush(heap, [0,1,1])
while heap != []:
    cost, i, j = heapq.heappop(heap)
    
    visited[(i,j)] = cost
    if i == H and j == W:
        flag = 1
        break
    else:
        for k in range(2):
            d = 2*k - 1
            if S[i+d][j] == ".":
                if (i+d,j) in visited:
                    if visited[(i+d,j)] > cost + 1:
                        visited[(i+d,j)] = cost + 1
                        heapq.heappush(heap, [cost+1,i+d,j])
                else:
                    visited[(i+d,j)] = cost + 1
                    heapq.heappush(heap, [cost+1,i+d,j])
            if S[i][j+d] == ".":
                if (i,j+d) in visited:
                    if visited[(i,j+d)] > cost + 1:
                        visited[(i,j+d)] = cost + 1
                        heapq.heappush(heap, [cost+1,i,j+d])
                else:
                    visited[(i,j+d)] = cost + 1
                    heapq.heappush(heap, [cost+1,i,j+d])



if flag == 1:
    print(white - cost - 1)
else:
    print(-1)

Solution (Python):
import sys
from bisect import *
from collections import *
from copy import deepcopy
from heapq import *
from itertools import *
from math import *
from operator import *
from pprint import *
import numpy as np

sys.setrecursionlimit(10**8)

input = sys.stdin.readline

def main():
    """ main """
    H,W = map(int, input().split())
    grid = [list(input().rstrip()) for _ in range(H)]
    black_cnt = 0
    for y in range(H):
        for x in range(W):
            if grid[y][x] == '

    q = deque([(0,0,0)])
    visited = [[False]*W for _ in range(H)]
    visited[0][0] = True
    while q:
        y,x,step = q.popleft()
        if y == H-1 and x == W-1:
            print(H*W-(step+1)-black_cnt)
            return 0
        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 and not visited[ny][nx] and grid[ny][nx] == '.':
                q.append((ny,nx,step+1))
                visited[ny][nx] = True

    print(-1)

if __name__ == '__main__':
    main()

Solution (Python):
import sys
sys.setrecursionlimit(200000)
input = sys.stdin.readline

N, M, = map(int, input().split())
L = [list(input().strip()) for _ in range(N)]

m = [[10 ** 18 for _ in range(M)] for _ in range(N)]

def bfs(x, y, c):
    if L[x][y] == "
        return

    if m[x][y] <= c:
        return

    m[x][y] = c

    if x + 1 < N:
        bfs(x + 1, y, c + 1)

    if y + 1 < M:
        bfs(x, y + 1, c + 1)

    if x - 1 >= 0:
        bfs(x - 1, y, c + 1)

    if y - 1 >= 0:
        bfs(x, y - 1, c + 1)

bfs(0, 0, 0)

if m[-1][-1] == 10 ** 18:
    print(-1)
    exit()

def dfs(x, y, c):
    if x == 0 and y == 0:
        L[x][y] = "o"
        return True
    for (_x, _y) in [(-1, 0), (0, -1), (1, 0), (0, 1)]:
        if x + _x < N and x + _x >= 0 and y + _y < M and y + _y >= 0:
            if c - 1 == m[x + _x][y + _y]:
                if dfs(x + _x, y + _y, c - 1):
                    L[x][y] = "o"
                    return True
    return False

dfs(N - 1, M - 1, m[-1][-1])

ans = 0
for v in L:
    ans += len([0 for c in v if c == "."])

print(ans)

Solution (Python):
import sys
from pprint import pprint

from collections import deque

h, w = map(int, sys.stdin.readline().strip().split(" "))

field = []
for _ in range(h):
    field.append(list(sys.stdin.readline().strip()))

black = 0
for i in range(h):
    for j in range(w):
        if field[i][j] == "
            black += 1

def bfs(field, h, w, sy, sx, gy, gx):
    q = deque()
    q.append((0, sy, sx))
    visited = set()
    while q:
        count, y, x = q.popleft()
        for dy, dx in ((-1, 0), (1, 0), (0, 1), (0, -1)):
            if 0 <= y+dy < h and 0 <= x+dx < w:
                if field[y+dy][x+dx] == "
                    continue
                elif (y+dy, x+dx) in visited:
                    continue
                elif (y+dy, x+dx) == (h-1, w-1):
                    return count+1

                visited.add((y+dy, x+dx))
                q.append((count+1, y+dy, x+dx))
    return -1

shortest = bfs(field, h, w, 0, 0, h-1, w-1)

if shortest == -1:
    print(-1)
else:
    print(h*w - black - (shortest+1))

Solution (Python):
def main():

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

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

    cur = [[0, 0]]
    goal = [H-1, W-1]
    turn = 0
    mv = [[1, 0], [-1, 0], [0, 1], [0, -1]]
    reached = False
    grid[0][0] = "
    while cur and not reached:
        temp = []
        for i, j in cur:
            if [i, j] == goal:
                reached = True
                break
            for di, dj in mv:
                i1 = i + di
                j1 = j + dj
                if 0 <= i1 < H and 0 <= j1 < W and grid[i1][j1] == ".":
                    grid[i1][j1] = "
                    temp.append([i1, j1])
        if not reached:
            cur = temp
            turn += 1
    if not reached:
        return -1
    return  white - (turn+1)


if __name__ == '__main__':
    print(main())

Solution (Python):
from collections import defaultdict, deque, Counter
from heapq import heappush, heappop, heapify
import math
import bisect
import random
from itertools import permutations, accumulate, combinations
import sys
import string
from bisect import bisect_left, bisect_right
from math import factorial, ceil, floor


INF = float('inf')
def LI(): return list(map(int, sys.stdin.readline().split()))
def I(): return int(sys.stdin.readline())
def LIM(): return list(map(lambda x:int(x) - 1, sys.stdin.readline().split()))
def LS(): return sys.stdin.readline().split()
def S(): return sys.stdin.readline().strip()
def IR(n): return [I() for i in range(n)]
def LIR(n): return [LI() for i in range(n)]
def LIRM(n): return [LIM() for i in range(n)]
def SR(n): return [S() for i in range(n)]
def LSR(n): return [LS() for i in range(n)]
def SRL(n): return [list(S()) for i in range(n)]
mod = 1000000007



def main():
    h, w = LI()
    grid = SRL(h)
    cnt = 0
    for y in range(h):
        for x in range(w):
            if grid[y][x] == '.':
                cnt += 1
                grid[y][x] = INF



    que = deque([(0, 0)])
    grid[0][0] = 1
    while que:
        x, y = que.pop()
        cost = grid[y][x]
        for i, j in [(0,1),(1,0),(-1,0),(0,-1)]:
            nxt_x, nxt_y = x + i, y + j
            if not (0<=nxt_x<w and 0<=nxt_y<h):
                continue
            elif grid[nxt_y][nxt_x] != '
                grid[nxt_y][nxt_x] = cost + 1
                que += [(nxt_x, nxt_y)]


    if grid[h-1][w-1] == INF:
        return -1


    return cnt - grid[h-1][w-1]







print(main())

Solution (Python):
from heapq import heappush, heappop
H, W = map(int, input().split())
s = [input() for _ in range(H)]

dist = [[float('inf')] * W for _ in range(H)]
q = [(0, 0, 0)]
while q :
    cost, cx, cy = heappop(q)
    if cost >= dist[cy][cx] :
        continue
    dist[cy][cx] = cost
        
    for dx, dy in ((0, 1), (0, -1), (1, 0), (-1, 0)) :
        if 0 <= cx + dx < W and 0 <= cy + dy < H and s[cy+dy][cx+dx] != '
            heappush(q, (cost+1, cx+dx, cy+dy))
            
if dist[H-1][W-1] == float('inf') :
    print(-1)
else :
    ret = 0
    for s_ in s :
        ret += s_.count('
    print(H * W - ret - dist[H-1][W-1] - 1)