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

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

ss = [input() for _ in range(h)]
start = [0,0]
goal = [w-1,h-1]
wall_count = 0
for s in ss:
    wall_count += s.count("

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

stack = collections.deque([start])
visited = [[-1 for _ in range(h)] for _ in range(w)]
visited[start[0]][start[1]] = 1

while len(stack) > 0:
    pos = stack.pop()
    if pos == goal:
        break
    
    for x,y in zip(dx, dy):
        next_pos = [pos[0]+x, pos[1]+y]
        
        if next_pos[0]<0 or (w-1)<next_pos[0] or next_pos[1]<0 or (h-1)<next_pos[1]:
            continue
        if ss[next_pos[1]][next_pos[0]] == "
            continue
        if visited[next_pos[0]][next_pos[1]] != -1:
            continue
        stack.appendleft(next_pos)
        visited[next_pos[0]][next_pos[1]] = visited[pos[0]][pos[1]] + 1

if visited[w-1][h-1] == -1:
    print("-1")
else:
    score = (h*w) - wall_count - visited[w-1][h-1]
    print(score)

Solution (Python):
import collections

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

ss = [input() for _ in range(h)]
start = [0,0]
goal = [w-1,h-1]
wall_count = 0
for s in ss:
    wall_count += s.count("

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

stack = collections.deque([start])
visited = [[-1 for _ in range(h)] for _ in range(w)]
visited[start[0]][start[1]] = 1

while len(stack) > 0:
    pos = stack.pop()
    if pos == goal:
        break
    
    for x,y in zip(dx, dy):
        next_pos = [pos[0]+x, pos[1]+y]
        
        if next_pos[0]<0 or (w-1)<next_pos[0] or next_pos[1]<0 or (h-1)<next_pos[1]:
            continue
        if ss[next_pos[1]][next_pos[0]] == "
            continue
        if visited[next_pos[0]][next_pos[1]] != -1:
            continue
        stack.appendleft(next_pos)
        visited[next_pos[0]][next_pos[1]] = visited[pos[0]][pos[1]] + 1

if visited[w-1][h-1] == -1:
    print("-1")
else:
    score = (h*w) - wall_count - visited[w-1][h-1]
    print(score)

Solution (Python):
from collections import deque
H, W = map(int, input().split())
G = [list(input()) for i in range(H)]  
D = [[-1] * W for i in range(H)]  
D[0][0] = 0

Black = 0  
for g in G:
    Black += g.count('


que = deque([[0, 0]])
direction = [(1, 0), (-1, 0), (0, 1), (0, -1)]
while que:
    nh, nw = que.pop()
    for dh, dw in direction:
        if not ((0 <= nh + dh < H) and (0 <= nw + dw < W)):
            continue

        if D[nh + dh][nw + dw] > 0:
            continue

        if G[nh + dh][nw + dw] == '
            continue

        D[nh + dh][nw + dw] = D[nh][nw] + 1
        que.appendleft([nh + dh, nw + dw])

if D[H - 1][W - 1] > 0:
    print(H * W - D[H - 1][W - 1] - Black - 1)
else:
    print(-1)

Solution (Python):


import sys
input = sys.stdin.readline

from collections import deque

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

start, goal = (1, 1), (H, W)

directions = [[0,-1],[0,1],[-1,0],[1,0]]

field = [['*'] * (W+2) for i in range(H+2)]
for i in range(1,H+1):
    row = list(input())[:-1]
    for j in range(1, W+1):
        field[i][j] = row[j-1]


memo = [[float('inf')] * (W+2) for i in range(H+2)]
memo[start[0]][start[1]] = 0

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

prevs = [[None] * (W+2) for i in range(H+2)]

def bfs():
    que = deque()
    
    que.append(start)
    while len(que) != 0:
        cur = que.popleft()
        
        if visited[cur[0]][cur[1]] == 1:
            continue
        
        visited[cur[0]][cur[1]] = 1
        
        for direction in directions:
            
            nxt = list(map(lambda x,y: x+y, cur, direction))
            
            if field[nxt[0]][nxt[1]] == '*' or field[nxt[0]][nxt[1]] == '
                continue
            
            if field[nxt[0]][nxt[1]] == '.' and memo[nxt[0]][nxt[1]] > memo[cur[0]][cur[1]] + 1:
                memo[nxt[0]][nxt[1]] = memo[cur[0]][cur[1]] + 1
                
                prevs[nxt[0]][nxt[1]] = (cur[0], cur[1])
                
                que.append(nxt)


bfs()

if memo[goal[0]][goal[1]] == float('inf'):
    print(-1)
    exit()

field[goal[0]][goal[1]] = '@'
nxt = prevs[goal[0]][goal[1]]
for _ in range(memo[goal[0]][goal[1]]):
    field[nxt[0]][nxt[1]] = '@'
    nxt = prevs[nxt[0]][nxt[1]]

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

Solution (Python):
from collections import deque

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

dist = [[10000] * W for i in range(H)]
dist[0][0] = 0

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

q = deque([(0, 0)])

while q:
    x, y = q.popleft()
    for dx, dy in dxy:
        nx, ny = x + dx, y + dy
        if nx < 0 or ny < 0 or nx >= W or ny >= H:
            continue
        if s[ny][nx] == "
            continue
        if dist[ny][nx] < 10000:
            continue
        q.append((nx, ny))
        dist[ny][nx] = dist[y][x] + 1

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

Solution (Python):

"""
Created on Sun Dec 30 19:55:40 2018
ABC088D
@author: maezawa
"""

h, w = list(map(int, input().split()))
a = []
for i in range(h):
    a.append(list(input()))
    
b = [[-1]*w for _ in range(h)]
dirs = [(-1, 0), (0, 1), (1, 0), (0, -1)]

a[0][0]=0
ok = True
finish = False
cnt = 1
current = [0, 0]
front = [current]
nextfront = []

while True:
    for cell in front:
        for direction in dirs:
            y, x = [cell[0]+direction[0], cell[1]+direction[1]]
            if y<0 or y>=h or x<0 or x>=w:
                continue
            if a[y][x] == '.':
                a[y][x] = cnt
                nextfront.append([y, x])
            if y == h-1 and x == w-1:
                finish = True
                break
    if finish == True:
        break
    elif nextfront == []:
        
        ok = False
        break
    front = nextfront[:]
    nextfront = []
    cnt += 1
cntblack = 0
for y in range(h):
    for x in range(w):
        if a[y][x] == '
            cntblack += 1

if ok:
    print(h*w-1-a[h-1][w-1]-cntblack)
else:
    print(-1)

Solution (Python):
import heapq


class Dijkstra:

    def __init__(self, rote_map, start_point, goal_point=None):
        self.rote_map = rote_map
        self.start_point = start_point
        self.goal_point = goal_point

    def execute(self):
        num_of_city = len(self.rote_map)
        dist = [float("inf") for _ in range(num_of_city)]
        prev = [float("inf") for _ in range(num_of_city)]

        dist[self.start_point] = 0
        heap_q = []
        heapq.heappush(heap_q, (0, self.start_point))
        route_count = [0 for _ in range(num_of_city)]
        route_count[self.start_point] = 1
        while len(heap_q) != 0:
            prev_cost, src = heapq.heappop(heap_q)

            if dist[src] < prev_cost:
                continue

            for dest, cost in self.rote_map[src].items():
                if cost != float("inf") and dist[dest] > dist[src] + cost:
                    dist[dest] = dist[src] + cost
                    heapq.heappush(heap_q, (dist[dest], dest))
                    prev[dest] = src
                if dist[dest] == dist[src] + cost:
                    route_count[dest] += route_count[src]

        if self.goal_point is not None:
            return self._get_path(self.goal_point, prev)
        else:
            return dist, route_count

    def _get_path(self, goal, prev):
        path = [goal]
        dest = goal

        while prev[dest] != float("inf"):
            path.append(prev[dest])
            dest = prev[dest]

        return list(reversed(path))

s_list = []
h, w = map(int, input().split())
for i in range(h):
    s_list.append(input())

route = [dict() for _ in range(h*w)]
all_white = 0
for i in range(h):
    for j in range(w):
        if s_list[i][j] == "
            continue
        else:
            all_white += 1
        if i != h-1 and s_list[i+1][j] == ".":
            route[w*i+j][w*(i+1)+j] = 1
        if j != w-1 and s_list[i][j+1] == ".":
            route[w*i+j][w*i+j+1] = 1
        if i != 0 and s_list[i-1][j] == ".":
            route[w*i+j][w*(i-1)+j] = 1
        if j != 0 and s_list[i][j-1] == ".":
            route[w*i+j][w*i+j-1] = 1

di = Dijkstra(route, 0, h*w-1)
r = di.execute()
count = len(r)
if count > 1:
    print(all_white-count)
else:
    print(-1)

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

A=[]
a=["
A.append(a)
for i in range(H):
    s=input()
    s="
    A.append(list(s))
A.append(a)


P=[[1,1]]
A[1][1]=1
x=[1,-1,0,0]
y=[0,0,1,-1]
while P!=[]:
    
    for j in range(4):
        if A[P[0][0]+x[j]][P[0][1]+y[j]]=="
            pass
        elif A[P[0][0]+x[j]][P[0][1]+y[j]]==".":
            A[P[0][0]+x[j]][P[0][1]+y[j]]=A[P[0][0]][P[0][1]]+1
            P.append([P[0][0]+x[j],P[0][1]+y[j]])
        elif A[P[0][0]+x[j]][P[0][1]+y[j]]<=A[P[0][0]][P[0][1]]+1:
            pass
        else:
            A[P[0][0]+x[j]][P[0][1]+y[j]]=A[P[0][0]][P[0][1]]+1
            P.append([P[0][0]+x[j],P[0][1]+y[j]])
    del P[0]
S=0
for i in range(H+2):
    for j in range(W+2):
        if A[i][j]=="
            S+=1
if A[H][W]==".":
    print(-1)
else:
    print((H+2)*(W+2)-S-A[H][W])

Solution (Python):
from collections import deque
H, W = map(int, input().split())
edges = [0] * (W + 2)
field = [edges]
WH = 0
for _ in range(H):
    row = [c == '.' for c in input()]
    field.append([0] + row + [0])
    WH += sum(row)
field.append(edges)
que = deque([(1, 1, 1)])  
enq, deq = que.append, que.popleft
while que:
    x, y, cnt = deq()
    if (x, y) == (W, H):
        print(WH - cnt)
        exit()
    for dx, dy in [(0, 1), (0, -1), (1, 0), (-1, 0)]:
        nx, ny = x + dx, y + dy
        if field[ny][nx]:
            enq((nx, ny, cnt + 1))
            field[ny][nx] = 0
print(-1)

Solution (Python):
from collections import deque
H, W = map(int, input().split())
edges = '
field = [edges]
BK = 0
for _ in range(H):
    row = input()
    field.append('
    BK += row.count('
field.append(edges)
que = deque([(1, 1, 1)])  
enq, deq = que.append, que.popleft
visited = [[0] * (W + 2) for _ in [0] * (H + 2)]
visited[1][1] = 1
dxy = [(0, 1), (0, -1), (1, 0), (-1, 0)]
while que:
    x, y, cnt = deq()
    for dx, dy in dxy:
        nx, ny = x + dx, y + dy
        if not visited[ny][nx] and field[ny][nx] == '.':
            if (nx, ny) == (W, H):
                res = cnt + 1
                print(H * W - BK - res)
                exit()
            else:
                enq((nx, ny, cnt + 1))
                visited[ny][nx] = 1
print(-1)

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

	D = [[0]*W for j in range(H)]

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

	
	sum_black = 0
	for h in range(H):
		for w in range(W):
			if ('
				sum_black += 1

	for k in range(2,H*W):
		L_next = []
		for l in L:
			w = l[0]
			h = l[1]
			
			if (0 < h):
				if ((0 == D[h-1][w]) and ('.'==S[h-1][w])):
					D[h-1][w] = k
					L_next.append((w,h-1))
			
			if (0 < w):
				if ((0 == D[h][w-1]) and ('.'==S[h][w-1])):
					D[h][w-1] = k
					L_next.append((w-1,h))
			
			if (h < (H - 1)):
				if ((0 == D[h+1][w]) and ('.'==S[h+1][w])):
					D[h+1][w] = k
					L_next.append((w,h+1))
			
			if (w < (W - 1)):
				if ((0 == D[h][w+1]) and ('.'==S[h][w+1])):
					D[h][w+1] = k
					L_next.append((w+1,h))
		L = L_next
		if (0 != D[H-1][W-1]):
			break
		if (not L):	
			return -1

	return W*H - D[H-1][W-1] - sum_black

print(main())

Solution (Python):
from queue import Queue

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

H, W = [int(_) for _ in input().split()]
S = [[1 if s == "

black_num = sum([sum(S[i]) for i in range(H)])


def solve():
    visited = [[0] * W for i in range(H)]

    q = Queue()
    q.put((0, 0))

    while not q.empty():
        i, j = q.get()

        for di, dj in directions:
            i_, j_ = i + di, j + dj

            if not (0 <= i_ < H and 0 <= j_ < W):
                continue

            if S[i_][j_] != 0 or visited[i_][j_] != 0:
                continue

            visited[i_][j_] = visited[i][j] + 1
            q.put((i_, j_))

            if i_ == H - 1 and j_ == W - 1:
                print(H * W - black_num - visited[H - 1][W - 1] - 1)
                return

    print(-1)

if __name__ == '__main__':
    solve()

Solution (Python):

h,w = map(int, input().split())
inf = 10**6
field = []
d = []
res = 0
for _ in range(h):
    line = list(input())
    field.append(line)
    d.append([inf]*w)
    for s in line:
        if s==".":
            res += 1

d[0][0] = 0
diff = [
    [1,0]
    ,[0,1]
    ,[-1,0]
    ,[0,-1]
]

flag = True
while flag:
    flag = False
    for hi in range(h):
        for wi in range(w):
            if d[hi][wi]<inf:
                for (dh,dw) in diff:
                    if h>hi+dh>=0 and w>wi+dw>=0 and field[hi+dh][wi+dw]=="." and d[hi+dh][wi+dw]>d[hi][wi]+1:
                        d[hi+dh][wi+dw] = d[hi][wi]+1
                        flag = True

if d[h-1][w-1]<inf:
    print(res-d[h-1][w-1]-1)
else:
    print(-1)

Solution (Python):
from collections import defaultdict
from heapq import heappop, heappush
h, w = map(int, input().split())
d = []
for i in range(h):
    d.append(input())

s = [str(m) for m in d]

dd = ((0, -1), (-1, 0), (0, 1), (1, 0))
dist = []
dotcount = 0
sharpcount = 0
for j in range(h):
    for i in range(w):
        if s[j][i] == ".":
            dotcount += 1
            for dx, dy in dd:  
                nx = i + dx
                ny = j + dy
                if 0 <= nx < w and 0 <= ny < h:  
                    if s[ny][nx] == ".":
                        dist.append([i + j * w, nx + ny * w, 1])
        else:
            sharpcount += 1

class Graph(object):
    """
    隣接リストによる有向グラフ
    """

    def __init__(self):
        self.graph = defaultdict(list)

    def __len__(self):
        return len(self.graph)

    def add_edge(self, src, dst, weight=1):
        self.graph[src].append((dst, weight))

    def get_nodes(self):
        return self.graph.keys()


class Dijkstra(object):
    """
    ダイクストラ法（二分ヒープ）による最短経路探索
    計算量: O((E+V)logV)
    """

    def __init__(self, graph, start):
        self.g = graph.graph

        
        
        self.dist = defaultdict(lambda: float('inf'))
        self.dist[start] = 0

        
        self.prev = defaultdict(lambda: None)

        
        self.Q = []
        heappush(self.Q, (self.dist[start], start))

        while self.Q:
            
            dist_u, u = heappop(self.Q)
            if self.dist[u] < dist_u:
                continue
            for v, weight in self.g[u]:
                alt = dist_u + weight
                if self.dist[v] > alt:
                    self.dist[v] = alt
                    self.prev[v] = u
                    heappush(self.Q, (alt, v))

    def shortest_distance(self, goal):
        """
        startノードからgoalノードまでの最短距離
        """
        return self.dist[goal]

    def shortest_path(self, goal):
        """
        startノードからgoalノードまでの最短経路
        """
        path = []
        node = goal
        while node is not None:
            path.append(node)
            node = self.prev[node]
        return path[::-1]

inputs = dist

g = Graph()
for src, dst, weight in inputs:
    g.add_edge(src, dst, weight)
    g.add_edge(dst, src, weight)

d = Dijkstra(g, h * w - 1)
sp = format(d.shortest_distance(0))


if sp != "inf":
    needcount = int(sp) + 1
    ans = dotcount - needcount
else:
    ans = -1

print(ans)

Solution (Python):
import sys

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

cc = 0
for ss in S:
    for st in ss:
        if st == ".":
            cc += 1

for i in range(len(S)):
    S[i] = "

temp = ["
S = temp + S + temp

dd = [[float("inf")] * W for i in range(H)]

def DFS(a, b, d):
    dd[a-1][b-1] = d
    for x, y in [(a+1, b), (a-1, b), (a, b+1), (a, b-1)]:
        if S[x][y] == "
            continue
        else:
            if dd[x-1][y-1] > d + 1:
                DFS(x, y, d + 1)

sys.setrecursionlimit(10000)

DFS(1,1,0)
if dd[H-1][W-1] != float("inf"):
    print(cc - dd[H-1][W-1] -1)
else:
    print("-1")

Solution (Python):

class Pair:
    x = 0
    y = 0
    def __init__(self, x, y):
        self.x = x
        self.y = y

import queue


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


def bfs():
    que = queue.Queue()
    d = [[-1 for _ in range(w)] for _ in range(h)]
    dx = [1, 0, -1, 0]
    dy = [0, 1, 0, -1]
    que.put(Pair(0, 0))
    d[0][0] = 0
    
    while not que.empty():
        p = que.get()
        
        for i in range(4):
            q_x = p.x + dx[i]
            q_y = p.y + dy[i]
            if q_x == w - 1 and q_y == h - 1:
                return d[p.y][p.x] + 1
            if 0 <= q_x < w and 0 <= q_y < h and grid[q_y][q_x] == "." and d[q_y][q_x] < 0:
                que.put(Pair(q_x, q_y))
                d[q_y][q_x] = d[p.y][p.x] + 1
    
    return -1

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

result = bfs()


if result == -1:
    print(-1)
else:
    print(white - 1 - result)

Solution (Python):

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

graph = [[-1 for _ in range(W)] for _ in range(H)]

que = deque()
x,y = 0,0 
que.append((x,y))
graph[x][y] = 0
while len(que) > 0:
    
    x,y = que.popleft() 
    step = graph[x][y]
    
    if y-1 >= 0 and s[x][y-1] == "." and graph[x][y-1] == -1:
        que.append((x,y-1))
        graph[x][y-1] = step + 1
    
    if y+1 < W and s[x][y+1] == "." and graph[x][y+1] == -1:
        que.append((x, y+1))
        graph[x][y+1] = step + 1
    
    if x-1 >= 0 and s[x-1][y] == "." and graph[x-1][y] == -1:
        que.append((x-1, y))
        graph[x-1][y] = step + 1
    
    if x+1 < H and s[x+1][y] == "." and graph[x+1][y] == -1:
        que.append((x+1, y))
        graph[x+1][y] = step + 1


que = deque()
x, y = H-1, W-1     
que.append((x,y))
step = graph[x][y]
graph[x][y] = -2  

if step == -1:
    print(-1)
    exit()

while len(que) > 0:
    x, y = que.popleft()  
    if x == y == 0:
        break
    
    if y-1 >= 0 and graph[x][y-1] == step - 1:
        que.append((x, y-1))
        graph[x][y-1] = -2
        step -= 1
        continue
    
    if y+1 < W and graph[x][y+1] == step - 1:
        que.append((x, y+1))
        graph[x][y+1] = -2
        step -= 1
        continue
    
    if x-1 >= 0 and graph[x-1][y] == step - 1:
        que.append((x-1, y))
        graph[x-1][y] = -2
        step -= 1
        continue
    
    if x+1 < H and graph[x+1][y] == step - 1:
        que.append((x+1, y))
        graph[x+1][y] = -2
        step -= 1
        continue

ans = 0
for h in range(H):
    for w in range(W):
        if s[h][w] == "." and graph[h][w] != -2:
            ans += 1

print(ans)

Solution (Python):
from collections import deque;h,w=map(int,input().split());m=[input()for _ in[0]*h];v=[[-1]*w for _ in[0]*h];q=deque([[0,0]]);v[0][0]=0;c=sum(t.count('
while q:
 y,x=q.popleft()
 for i,j in([1,0],[-1,0],[0,1],[0,-1]):
  t,u=y+i,x+j
  if t+1and t<h and u+1and u<w and m[t][u]=='.'and v[t][u]<0:v[t][u]=v[y][x]+1;q.append([t,u])
print(-(v[h-1][w-1]<0)or h*w-c-v[h-1][w-1]-1)

Solution (Python):
from collections import deque;h,w=map(int,input().split());m=[input()for _ in[0]*h];v=[[-1]*w for _ in[0]*h];q=deque([[0,0]]);v[0][0]=0;c=sum(t.count('
while q:
 y,x=q.popleft()
 for i,j in([1,0],[-1,0],[0,1],[0,-1]):
  t,u=y+i,x+j
  if t+1and t<h and u+1and u<w and m[t][u]=='.'and v[t][u]<0:v[t][u]=v[y][x]+1;q.append([t,u])
print(-1*(v[h-1][w-1]<0)or h*w-c-v[h-1][w-1]-1)

Solution (Python):
directions = [(1, 0), (0, 1), (-1, 0), (0, -1)]


def main():
    H, W = map(int, input().split())
    s = [input() for _ in range(H)]
    path = [[float("inf")] * W for _ in range(H)]
    white = sum([len(row.replace("
    scan = [(0, 0, 1)]  
    while len(scan):
        i, j, cost = scan.pop(0)
        if cost >= path[i][j]:
            continue
        path[i][j] = cost
        for d in directions:
            nexti = i + d[0]
            nextj = j + d[1]
            if 0 <= nexti and nexti < H and \
               0 <= nextj and nextj < W and \
               s[nexti][nextj] == ".":
                scan.append((nexti, nextj, cost + 1))
    if path[H-1][W-1] == float("inf"):
        print(-1)
    else:
        print(white - path[H-1][W-1])


if __name__ == "__main__":
    main()

Solution (Python):
from collections import deque
H,W=map(int,input().split())
Map=[list(input()) for i in range(H)]
for h in range(H):
  Map[h].insert(0,"
  Map[h].append("
Map.insert(0,["
Map.append(["
white=sum(Map[i].count(".") for i in range(H+2))

Que=deque([(1,1,1)])
visited=[[10**10]*(W+2) for i in range(H+2)]
while Que:
  x,y,stage=Que.popleft()
  if x==W and y==H:
    print(white-stage)
    exit()
  stage+=1
  for i,j in ((x+1,y),(x-1,y),(x,y+1),(x,y-1)):
    if Map[j][i]=="." and stage<visited[j][i]:
      visited[j][i]=stage
      Que.append((i,j,stage))
print(-1)

Solution (Python):
from collections import deque
from itertools import chain

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

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

l = [[None for _ in range(w)] for _ in range(h)]
l[0][0] = 0

q = deque([(0, 0)])
while q:
	this_x, this_y = q.popleft()
	this_num = l[this_y][this_x]
	if (this_x, this_y) == (w-1, h-1):
		
		print(sum(s_i.count(".") for s_i in s) - l[h-1][w-1] - 1)
		exit()

	for ad_x, ad_y in ADS:
		x, y = this_x+ad_x, this_y+ad_y
		if not (0 <= x < w and 0 <= y < h):
			continue
		
		square = s[y][x]
		if square == "
			continue

		num = l[y][x]
		if num != None:
			continue
		l[y][x] = this_num + 1

		q.append((x, y))

print(-1)

Solution (Python):
H, W = map(int, input().split())
S = [list(input()) for i in range(H)]
Inf = 1000
Dist, Fin = [[Inf for i in range(W)] for j in range(H)], [[False for i in range(W)] for j in range(H)]
Dist[0][0], Fin[0][0] = 0, True
Q, Search = [(0, 0)], [(-1, 0), (0, -1), (1, 0), (0, 1)]

while Q:
    next = Q.pop(0)
    for s in Search:
        if 0 <= next[0] + s[0] <= H-1 and 0 <= next[1] + s[1] <= W-1:
            if Fin[next[0] + s[0]][next[1]+s[1]] == False:
                Fin[next[0]+s[0]][next[1]+s[1]] = True
                if S[next[0]+s[0]][next[1]+s[1]] == ".":
                    Dist[next[0]+s[0]][next[1]+s[1]] = Dist[next[0]][next[1]] + 1
                    Q.append((next[0]+s[0], next[1]+s[1]))

if Dist[H-1][W-1] == Inf:
    print(-1)
else:
    now, dist = (H-1, W-1), Dist[H-1][W-1]
    S[H-1][W-1] = "
    while dist > 0:
        for s in Search:
            if 0 <= now[0] + s[0] <= H-1 and 0 <= now[1] + s[1] <= W-1:
                if Dist[now[0]+s[0]][now[1]+s[1]] == dist-1:
                    now, dist = (now[0]+s[0], now[1]+s[1]), dist-1
                    S[now[0]][now[1]] = "
                    break

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

Solution (Python):
from collections import deque


H, W = map(int, input().split())
S = [list(map(str, input())) for i in range(H)]
numWhite = -2  
for h in range(H):
    numWhite += S[h].count(".")


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


def bfs():
    que = deque([])
    que.append([0, 0])
    D = []
    for h in range(H):
        D.append([float('inf') for _ in range(W)])
    D[0][0] = 0
    while len(que) > 0:
        p = que.popleft()
        if p == [H-1, W-1]:
            break
        else:
            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
    return D[H-1][W-1]


ans = numWhite - bfs() + 1
if isinstance(ans, int):
    print(ans)
else:
    print(-1)

Solution (Python):
import itertools
H, W = [int(_) for _ in input().split()]
S = []
count_dot = 0
for _ in range(H):
    s = input()
    count_dot += s.count('.')
    S += [list(s)]
S[0][0] = '
coord = [[0, 0]]
count = 1
flag = True
while flag:
    count += 1
    coord_new = []
    for i, j in coord:
        for x, y in [i + 1, j], [i - 1, j], [i, j + 1], [i, j - 1]:
            if (x, y) == (H - 1, W - 1):
                print(count_dot - count)
                exit()
            elif 0 <= x and x < H and 0 <= y and y < W and S[x][y] == '.':
                S[x][y] = '
                coord_new += [[x, y]]
    coord = coord_new
    flag = len(coord)
print(-1)

Solution (Python):
inf = 2**31 - 1


def bfs(sx, sy, gx, gy):
    que = []
    d = {h: {w: inf for w in range(W)} for h in range(H)}

    que.append((sx, sy))
    d[sy][sx] = 0

    while len(que):
        p = que.pop(0)

        if p[0] == gx and p[1] == gy:
            break

        for i in range(4):
            nx, ny = p[0] + dx[i], p[1] + dy[i]

            if (0 <= nx < W) and (0 <= ny < H) and (maze[ny][nx] != '
                que.append((nx, ny))
                d[ny][nx] = d[p[1]][p[0]] + 1

    return d[gy][gx]


def wall_count(l):
    temp = []
    for s in l:
        temp.extend(s)
    return temp.count('


if __name__ == '__main__':
    dx = (1, 0, -1, 0)
    dy = (0, 1, 0, -1)

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

    maze = [list(input()) for h in range(H)]
    walls = wall_count(maze)

    goal = bfs(0, 0, W-1, H-1)

    if goal == inf:
        print(-1)
    else:
        print(H*W - walls - goal - 1)

Solution (Python):
from collections import deque
from itertools import chain
ads = [(0, 1), (1, 0), (0, -1), (-1, 0)]

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

def find_shortest(m):
	q = deque([(0, 0)])
	i = 0
	while q:
		for j in range(len(q)):
			this_x, this_y = q.popleft()
			
			if (this_x, this_y) == (w-1, h-1):
				return i
			m[this_y][this_x] = i

			for ad_x, ad_y in ads:
				x, y = this_x+ad_x, this_y+ad_y
				if not (0 <= x < w and 0 <= y < h):
					continue
				
				square = m[y][x]
				if square == "
					continue
					
				q.append((x, y))
				m[y][x] = "
		i += 1
	return None


white_num = "".join(chain(*s)).count(".")
shortest_lenght = find_shortest(s)
if shortest_lenght:
	print(white_num - 1 - shortest_lenght)
else:
	print(-1)

Solution (Python):
import heapq

class Dijkstra(object):
    def dijkstra(self, adj, start, goal=None):
        '''
        ダイクストラアルゴリズムによる最短経路を求めるメソッド
        入力
        adj: adj[i][j]の値が頂点iから頂点jまでの距離(頂点iから頂点jに枝がない場合，値はfloat('inf'))となるような2次元リスト(正方行列)
        start: 始点のID
        goal: オプション引数．終点のID
        出力
        goalを引数に持つ場合，startからgoalまでの最短経路を格納したリストを返す
        持たない場合は，startから各頂点までの最短距離を格納したリストを返す
        '''
        num = len(adj)          
        dist = [float('inf') for i in range(num)] 
        prev = [float('inf') for i in range(num)] 
        
        dist[start] = 0
        q = []                  
        heapq.heappush(q, (0, start)) 

        while len(q) != 0:
            prov_cost, src = heapq.heappop(q) 
            
            
            if dist[src] < prov_cost:
                continue

            
            for dest in range(num):
                cost = adj[src][dest]
                if cost != float('inf') and dist[dest] > dist[src] + cost:
                    dist[dest] = dist[src] + cost 
                    heapq.heappush(q, (dist[dest], dest)) 
                    prev[dest] = src                      
                    
        if goal is not None:
            return self.get_path(goal, prev)
        else:
            return dist

    def get_path(self, goal, prev):
        '''
        始点startから終点goalまでの最短経路を求める
        '''
        path = [goal]           
        dest = goal

        
        while prev[dest] != float('inf'):
            path.append(prev[dest])
            dest = prev[dest]

        
        return list(reversed(path))







H,W=map(int,input().split())
black=0
field=[["
for i in range(H):
    field.append(["

field.append(["

adj=[[float("inf")]*W*H for _ in range(H*W)]

for i in range(H):
    for j in range(W):
        if(field[i+1][j+1]=="
            black+=1
            continue
        if(field[i+1][j+2]=="."):
            adj[W*i+j][W*i+j+1]=1
            adj[W*i+j+1][W*i+j]=1
        if(field[i+1][j]=="."):
            adj[W*i+j][W*i+j-1]=1
            adj[W*i+j-1][W*i+j]=1
        if(field[i][j+1]=="."):
            adj[W*i+j][W*(i-1)+j]=1
            adj[W*(i-1)+j][W*i+j]=1
        if(field[i+2][j+1]=="."):
            adj[W*i+j][W*(i+1)+j]=1
            adj[W*(i+1)+j][W*i+j]=1

d=Dijkstra()
kyori=d.dijkstra(adj,0)[-1]
if(kyori==float("inf")):
    print(-1)
else:
    print(H*W-black-kyori-1)