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 copy
h,w = (int(i) for i in input().split())
x = [input() for i in range(h)]
cf,list1,num = [[0,0]],[[0,0]],1
while [h-1,w-1] not in cf and len(list1) != 0:
	list2 = []
	for j in list1:
		list3 = [[j[0]+1,j[1]],[j[0]-1,j[1]],[j[0],j[1]+1],[j[0],j[1]-1]]
		for j2 in list3:
			if (-1<j2[0]<h) and (-1<j2[1]<w) and (j2 not in cf) and (x[j2[0]][j2[1]]=="."):
				cf.append(j2)
				list2.append(j2)
	num += 1
	list1 = copy.deepcopy(list2)
num2 = 0
for k in x: num2 += k.count(".")
if [h-1,w-1] not in cf: answer = -1
else: answer = num2-num
print(answer)

Solution (Python):

import queue
h,w=map(int,input().split())
m=[]
block=0
for i in range(h):
    m.append(list(input()))
    block+=m[-1].count('
q=queue.Queue()
q.put((0,0))
m[0][0]=0
while not q.empty():
    i,j=q.get()
    if i+1<h and m[i+1][j]=='.':
        m[i+1][j]=m[i][j]+1
        q.put((i+1,j))
    if i-1>=0 and m[i-1][j]=='.':
        m[i-1][j]=m[i][j]+1
        q.put((i-1,j))
    if j+1<w and m[i][j+1]=='.':
        m[i][j+1]=m[i][j]+1
        q.put((i,j+1))
    if j-1>=0 and m[i][j-1]=='.':
        m[i][j-1]=m[i][j]+1
        q.put((i,j-1))
if m[h-1][w-1]=='.':
    print(-1)
else:
    print(h*w-m[h-1][w-1]-block-1)

Solution (Python):
H, W = map(int, input().split())
List = [input() for i in range(H)]
queue = [(0, 0, 1)]
cout = sum([row.count("
used = [(0, 0)]


def check(x, y, c):
    if x > W - 1 or y > H - 1 or x < 0 or y < 0:
        return
    if List[y][x] == '
        return
    if (x, y) in used:
        return
    queue.append((x, y, c))
    used.append((x, y))

f = -1
final =  0
while queue:
    x, y, c = queue.pop(0)
    if x == W - 1 and y == H - 1:
        f = 1
        final = c
        break
    check(x + 1, y, c + 1)
    check(x, y + 1, c + 1)
    check(x - 1, y, c + 1)
    check(x, y - 1, c + 1)

print(f if f == -1 else(H * W - final - cout))

Solution (Python):
import sys
import heapq as hp

def eval(x, y, c):
    return c + (w - 1 - x + h - 1- y)

h, w = [int(x) for x in input().rstrip().split()]
matrix = [list(input().rstrip()) for _ in range(h)]
open = [[False for _ in range(w)] for _ in range(h)]

x, y, cost = 0, 0, 0
open[y][x] = True
queue = []
hp.heappush(queue, (eval(x, y, 1), x, y, 1))
while [x, y] != [w-2, h-1] and [x, y] != [w-1, h-2]:
    e, x, y, c = hp.heappop(queue)
    for dx, dy in [[1,0], [-1,0], [0,1], [0,-1]]:
        if 0 <= x+dx <= w-1 and 0 <= y+dy <= h-1 and matrix[y+dy][x+dx] == "." and not open[y+dy][x+dx]:
            hp.heappush(queue, (eval(x+dx, y+dy, c+1), x+dx, y+dy, c+1))
            open[y+dy][x+dx] = True
    cost = c+1
    
    if not queue:
        print(-1)
        sys.exit()
print(sum(list(map(lambda x: x.count("."), matrix))) - cost)

Solution (Python):
from collections import deque
h, w = map(int, raw_input().split())
maze = [raw_input() for _ in xrange(h)]
visited = [[False] * w for _ in xrange(h)]
que = deque([(0, 0, 0)])  
dx, dy = (0, 1, 0, -1), (1, 0, -1, 0)
dis = flag = False
while que:
    x, y, d = que.popleft()
    if (x, y) == (h - 1, w - 1):
        dis, flag = d, True
        break
    for i in xrange(4):
        nx, ny = x + dx[i], y + dy[i]
        if 0 <= nx < h and 0 <= ny < w:
            if not visited[nx][ny] and maze[nx][ny] == '.':
                que.append((nx, ny, d + 1))
                visited[nx][ny] = True
print h * w - dis - 1 - sum([_.count('

Solution (Python):
tmp=input().split()
H,W=int(tmp[0]),int(tmp[1])
map = [['a' for x in range(W)] for y in range(H)]
countroad = 0
for i in range(H):
    tmp = input()
    for j in range(W):
        map[i][j] = tmp[j]
        if tmp[j] =='.':
            countroad += 1
count = 0
queue = [0]
check = [0]
dx,dy=0,0

def walkmap(pos1,pos2):
    if 0<=pos1 and pos1<H and 0<=pos2 and pos2<W:
        if map[pos1][pos2] == '.':
            mapIndex=pos1*W+pos2
            if mapIndex not in check:
                queue.append(mapIndex)
                check.append(mapIndex)
minstep = -1
while len(queue) > 0:
    count += 1
    
    if (H*W-1) in queue:
        minstep = count
        break
    target = len(queue)
    for j in range(target):
        
        dx = int(queue[0]/W)
        dy = int(queue[0]%W)
        queue.pop(0)
        walkmap(dx-1,dy)
        walkmap(dx+1,dy)
        walkmap(dx,dy-1)
        walkmap(dx,dy+1)
if minstep > 0:
    print(countroad-minstep)
else:
    print(minstep)

Solution (Python):
from queue import Queue

H, W = [int(x) for x in input().split()]
realH = H + 2
realW = W + 2
s = ["
wall = "
s.insert(0, wall)
s.append(wall)
dxy = [0, 1, 0, -1, 0]
inf = float("inf")

visited = [[False] * realW for x in range(realH)]
depth = [[inf] * realW for x in range(realH)]
depth[1][1] = 1
q = Queue()
q.put((1,1))

while not q.empty():
    place = q.get()
    if place == (H, W):
        break
    for i in range(4):
        nxt = (place[0] + dxy[i], place[1] + dxy[i+1])
        if s[nxt[0]][nxt[1]] == "." and not visited[nxt[0]][nxt[1]]:
            q.put(nxt)
            depth[nxt[0]][nxt[1]] = depth[place[0]][place[1]] + 1
            visited[nxt[0]][nxt[1]] = True

if depth[H][W] == inf:
    print(-1)
else:
    print(realH * realW - sum(map(lambda x: x.count("

Solution (Python):
from collections import deque

INF = 10101010

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

    ans = 0
    for i in range(h):
        ans += s[i].count('.')

    d = [[INF for j in range(w)] for i in range(h)]
    d[0][0] = 0
    que = deque()
    que.append((0,0))
    while que:
        y,x = que.pop()
        if (y,x) == (h-1,w-1):
            return ans - (d[h-1][w-1]+1)

        for dx,dy in [(1,0),(-1,0),(0,1),(0,-1)]:
            nx,ny = x+dx, y+dy
            if 0 <= nx < w and 0 <= ny < h:
                if s[ny][nx] != '
                    d[ny][nx] = d[y][x]+1
                    que.appendleft((ny,nx))

    return -1

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

Solution (Python):
from collections import deque

INF = 10101010

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

    d = [[INF for j in range(w)] for i in range(h)]
    d[0][0] = 0
    que = deque()
    que.append((0,0))
    while len(que):
        y,x = que.pop()
        for dx,dy in [(1,0),(-1,0),(0,1),(0,-1)]:
            nx,ny = x+dx, y+dy
            if 0 <= nx < w and 0 <= ny < h:
                if s[ny][nx] != '
                    d[ny][nx] = d[y][x]+1
                    que.append((ny,nx))

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

    ans = -(d[h-1][w-1]+1)
    for i in range(h):
        for j in range(w):
            if s[i][j] == '.':
                ans += 1
    return ans

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

Solution (Python):
from collections import deque

INF = 10101010

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



    d = [[INF for j in range(w)] for i in range(h)]
    d[0][0] = 0
    que = deque()
    que.append((0,0))
    while len(que):
        y,x = que.pop()
        for dx,dy in [(1,0),(-1,0),(0,1),(0,-1)]:
            nx,ny = x+dx, y+dy
            if 0 <= nx < w and 0 <= ny < h:
                if s[ny][nx] != '
                    d[ny][nx] = d[y][x]+1
                    que.append((ny,nx))

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

    ans = -(d[h-1][w-1]+1)
    for i in range(h):
        for j in range(w):
            if s[i][j] == '.':
                ans += 1
    return ans

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

Solution (Python):
a=map(int, raw_input().split())
lis=[]
for i in range(a[0]):
    b=list(raw_input())
    lis.append(b)

pro=[]
cou=0
for i in range(a[0]):
    pre=[]
    for j in range(a[1]):
        if lis[i][j]=="
            cou+=1
        pre.append(2501)
    pro.append(pre)

while True:
    ch=0
    for i in range(a[0]):
        for j in range(a[1]):
            if lis[i][j]==".":
                if i==0:
                    if j==0:
                        pro[i][j]=1
                    elif j==a[1]-1:
                        u = 2501
                        d = pro[i + 1][j]
                        r = 2501
                        l = pro[i][j - 1]
                        se = [u, d, r, l]
                        se.sort()
                        if se[0]+1 < pro[i][j]:
                            ch = 1
                            pro[i][j] = se[0] + 1
                    else:
                        u = 2501
                        d = pro[i + 1][j]
                        r = pro[i][j + 1]
                        l = pro[i][j - 1]
                        se = [u, d, r, l]
                        se.sort()
                        if se[0]+1 < pro[i][j]:
                            ch = 1
                            pro[i][j] = se[0] + 1
                elif i==a[0]-1:
                    if j==0:
                        u = pro[i - 1][j]
                        d = 2501
                        r = pro[i][j + 1]
                        l = 2501
                        se = [u, d, r, l]
                        se.sort()
                        if se[0]+1 < pro[i][j]:
                            ch = 1
                            pro[i][j] = se[0] + 1
                    elif j==a[1]-1:
                        u = pro[i - 1][j]
                        d = 2501
                        r = 2501
                        l = pro[i][j - 1]
                        se = [u, d, r, l]
                        se.sort()
                        if se[0]+1 < pro[i][j]:
                            ch = 1
                            pro[i][j] = se[0] + 1
                    else:
                        u = pro[i - 1][j]
                        d = 2501
                        r = pro[i][j + 1]
                        l = pro[i][j - 1]
                        se = [u, d, r, l]
                        se.sort()
                        if se[0]+1 < pro[i][j]:
                            ch = 1
                            pro[i][j] = se[0] + 1
                else:
                    if j==0:
                        u = pro[i - 1][j]
                        d = pro[i + 1][j]
                        r = pro[i][j+ 1]
                        l = 2501
                        se = [u, d, r, l]
                        se.sort()
                        if se[0]+1 < pro[i][j]:
                            ch = 1
                            pro[i][j] = se[0] + 1
                    elif j==a[1]-1:
                        u = pro[i - 1][j]
                        d = pro[i + 1][j]
                        r = 2501
                        l = pro[i][j - 1]
                        se = [u, d, r, l]
                        se.sort()
                        if se[0]+1 < pro[i][j]:
                            ch = 1
                            pro[i][j] = se[0] + 1
                    else:
                        u = pro[i - 1][j]
                        d = pro[i + 1][j]
                        r = pro[i][j + 1]
                        l = pro[i][j - 1]
                        se = [u, d, r, l]
                        se.sort()
                        if se[0]+1 < pro[i][j]:
                            ch = 1
                            pro[i][j] = se[0] + 1
    if ch==0:
        break
if pro[a[0]-1][a[1]-1]==2501:
    print -1
else:
    print a[0]*a[1]-cou-pro[a[0]-1][a[1]-1]

Solution (Python):
H, W = map(int, input().split())
List = [input() for i in range(H)]
queue = [(0,0,1)]
shape = sum(row.count("
used = {(0,0)}

def check(x,y,c):
    if x > W-1 or y > H-1 or x < 0 or y < 0:
        return
    if List[y][x] == '
        return
    if (x,y) in used:
        return
    queue.append((x,y,c))
    used.add((x,y))
    
f = -1
while queue:
    x,y,c = queue.pop(0)
    if x == W-1 and y == H-1:
        f = 1
        break
    check(x+1, y, c+1)
    check(x,y+1,c+1)
    check(x-1,y,c+1)
    check(x,y-1,c+1)
print(f if f == -1 else(H*W - c - shape))

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

while deq:
    i,j,k = deq.popleft()
    if not((i in range(h)) and (j in range(w))):
        continue
    if s[i][j] != '.':
        continue
    s[i][j]=k
    if i==h-1 and j == w-1:
        break
    deq.append([i + 1, j, k + 1])
    deq.append([i - 1, j, k + 1])
    deq.append([i, j + 1, k + 1])
    deq.append([i, j - 1, k + 1])
if s[h-1][w-1] == '
    print(-1)
else:
    black = sum([y.count('
    print(h*w-black-s[h-1][w-1]-1)

Solution (Python):
def reach(s,t,G):
    V,E=G
    check=set()
    step=0
    nex={s}
    while nex!=set():
        if t in nex:
            return(step)
        else:
            check|=nex
            nex={v for v in V if v not in check and any([(v,w) in E for w in nex])}
            step+=1
    return(-1)

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

point=0
sharp=0
V=set()
E=set()
for i in range(H):
    for j in range(W):
        if S[i][j]=='.':
            point+=1
            V|={(i,j)}
            if i-1>=0:
                if S[i-1][j]=='.':
                    E|={((i,j),(i-1,j))}
            if i+1<=H-1:
                if S[i+1][j]=='.':
                    E|={((i,j),(i+1,j))}
            if j-1>=0:
                if S[i][j-1]=='.':
                    E|={((i,j),(i,j-1))}
            if j+1<=W-1:
                if S[i][j+1]=='.':
                    E|={((i,j),(i,j+1))}
        if S[i][j]=='
            sharp+=1
G=(V,E)

if reach((0,0),(H-1,W-1),G)==-1:print(-1)
else:print(point-(reach((0,0),(H-1,W-1),G)+1))

Solution (Python):
h,w = map(int, input().split())

smap = [list(input()) for _ in range(h)]
cmap = [[float('inf') for _ in range(w)] for _ in range(h)]
queue = [(0,0)]
l = [(1,0), (-1,0), (0,1), (0,-1)]

smap[0][0] = '

initial_whites = 0

for x in smap:
    for y in x:
        if y == '.':
            initial_whites += 1

cmap[0][0] = 0

while queue:
    v = queue.pop(0)
    for x in l:
        y = (v[0]+x[0], v[1]+x[1])
        if 0 <= y[0] <= h-1 and 0 <= y[1] <= w-1:
            if smap[y[0]][y[1]] == '.':
                smap[y[0]][y[1]] = '
                cmap[y[0]][y[1]] = cmap[v[0]][v[1]] + 1
                queue.append(y)
            else:
                pass
        else:
            pass


if cmap[h-1][w-1] == float('inf'):
    print(-1)
else:
    print(initial_whites - cmap[h-1][w-1])

Solution (Python):
h,w = map(int, input().split())

smap = []
for _ in range(h):
    s = input()
    ss = []
    for i in range(w):
        ss.append(s[i])
    smap.append(ss)
cmap = [[float('inf') for _ in range(w)] for _ in range(h)]
queue = [(0,0)]
l = [(1,0), (-1,0), (0,1), (0,-1)]

initial_whites = 0

for x in smap:
    for y in x:
        if y == '.':
            initial_whites += 1

cmap[0][0] = 0

while queue:
    v = queue.pop(0)
    smap[v[0]][v[1]] = '
    for x in l:
        y = (v[0]+x[0], v[1]+x[1])
        if 0 <= y[0] <= h-1 and 0 <= y[1] <= w-1:
            if smap[y[0]][y[1]] == '.':
                smap[y[0]][y[1]] = '
                cmap[y[0]][y[1]] = cmap[v[0]][v[1]] + 1
                queue.append(y)
            else:
                pass
        else:
            pass


if cmap[h-1][w-1] == float('inf'):
    print(-1)
else:
    print(initial_whites - cmap[h-1][w-1] - 1)

Solution (Python):
H, W = tuple(map(int, input().split()))
s = [input() for _ in range(H)]
q = [(0, 0, 0)]
h = {(0, 0)}
opt = float('inf')
while q:
    i, j, k = q.pop(0)
    if i == H - 1 and j == W - 1:
        opt = k
        break
    a = [(u, v)
         for u, v in ((i + 1, j), (i, j + 1), (i - 1, j), (i, j - 1))
         if 0 <= u < H and 0 <= v < W and s[u][v] == '.' and (u, v) not in h]
    q += [(u, v, k + 1) for u, v in a]
    h |= set(a)
print(max(-1, sum(t.count('.') for t in s) - opt - 1))

Solution (Python):
import sys

H, W = [int(x) for x in input().split()]

grid = [[c for c in input()] for i in range(H)]
visited = [[False for i in range(W)] for j in range(H)]
dist = [[0 for i in range(W)] for j in range(H)]


nw = sum([line.count('.') for line in grid])


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

visited[start[0]][start[1]] = True
dist[start[0]][start[1]] = 1
queue = [start]
while len(queue) > 0:
    v = queue[0]
    queue.remove(v)

    if v == goal:
        print(nw - dist[v[0]][v[1]])
        sys.exit()
    else:
        if (v[0] > 0 and not visited[v[0] - 1][v[1]]
                and grid[v[0] - 1][v[1]] == '.'):
            queue.append((v[0] - 1, v[1]))
            visited[v[0] - 1][v[1]] = True
            dist[v[0] - 1][v[1]] = dist[v[0]][v[1]] + 1

        if (v[0] < H - 1 and not visited[v[0] + 1][v[1]]
                and grid[v[0] + 1][v[1]] == '.'):
            queue.append((v[0] + 1, v[1]))
            visited[v[0] + 1][v[1]] = True
            dist[v[0] + 1][v[1]] = dist[v[0]][v[1]] + 1

        if (v[1] > 0 and not visited[v[0]][v[1] - 1]
                and grid[v[0]][v[1] - 1] == '.'):
            queue.append((v[0], v[1] - 1))
            visited[v[0]][v[1] - 1] = True
            dist[v[0]][v[1] - 1] = dist[v[0]][v[1]] + 1

        if (v[1] < W - 1 and not visited[v[0]][v[1] + 1]
                and grid[v[0]][v[1] + 1] == '.'):
            queue.append((v[0], v[1] + 1))
            visited[v[0]][v[1] + 1] = True
            dist[v[0]][v[1] + 1] = dist[v[0]][v[1]] + 1

print(-1)

Solution (Python):
H , W= map(int, input().split())
que = [(0, 0)]
S = [input() for i in range(H)]
flag = [[1<<30 for i in range(W)] for j in range(H)]
flag[0][0] = 1
cnt = sum(row.count('.') for row in S)
while que:
	y, x = que.pop(0)
	for ny, nx in [1, 0], [-1, 0], [0, 1], [0, -1]:
		nx += x
		ny += y
		if ny >= 0 and nx >= 0 and ny < H and nx < W and S[ny][nx] != '
			que.append((ny, nx))
			flag[ny][nx] = flag[y][x] + 1
			if (ny, nx) == (H - 1, W - 1):
				print(cnt - flag[ny][nx])
				exit()
print(-1)

Solution (Python):
import queue
INF = 1 << 30
H , W= map(int, input().split())
que = [(0, 0)]
S = [input() for i in range(H)]
flag = [[INF for i in range(W)] for j in range(H)]
flag[0][0] = 1
cnt = sum(row.count('.') for row in S)
while que:
	y, x = que[0]
	que.pop(0)
	for ny, nx in [1, 0], [-1, 0], [0, 1], [0, -1]:
		nx += x
		ny += y
		if ny >= 0 and nx >= 0 and ny < H and nx < W and S[ny][nx] != '
			que.append((ny, nx))
			flag[ny][nx] = flag[y][x] + 1
			if (ny, nx) == (H - 1, W - 1):
				print(cnt - flag[ny][nx])
				exit()
print(-1)

Solution (Python):
H, W = map(int, input().split())
maze = []
distances = []
n_aisle = 0
for i in range(H):
    row = input()
    maze.append(row)
    distances.append([100000000 for i in range(W)])
    n_aisle += row.count('.')

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

visited = [(0, 0)]
queue = [(0, 0)]
while len(queue) > 0:
    y, x = queue.pop(0)
    for dy, dx in directions:
        y2, x2 = y + dy, x + dx
        if y2 < 0 or y2 >= H or x2 < 0 or x2 >= W:
            continue
        if (y2, x2) in visited:
            continue
        if maze[y2][x2] == '.':
            distances[y2][x2] = distances[y][x] + 1
            visited.append((y2, x2))
            queue.append((y2, x2))

if distances[H - 1][W - 1] == 100000000:
    print(-1)
else:
    print(n_aisle - distances[H - 1][W - 1] - 1)

Solution (Python):
H,W = map(int, input().split())
List = [input() for i in range(H)]
queue = [(0,0,1)]
shape = sum(row.count("
used ={(0,0)}

def check(x,y,c):
    if(x>W-1 or y>H-1 or x<0 or y<0):
        return
    if(List[y][x] == '
        return
    if(x,y) in used:
        return
    queue.append((x,y,c+1))
    used.add((x,y))

f= -1
while queue:
    x,y,c = queue[0]
    if x==W-1 and y==H-1:
        f=1
        break
    queue.pop(0)
    check(x+1,y,c)
    check(x, y+1,c)
    check(x-1,y,c)
    check(x, y-1,c)
print(f if f == -1 else(H*W-c-shape))

Solution (Python):
H,W = map(int, input().split())
List = []
queue = [(0,0,1)]
shape = 0
used ={(0,0)}
for i in range(H):
    x = input()
    shape += x.count('
    List.append(x)

def check(x,y,c):
    if(x>W-1 or y>H-1 or x<0 or y<0):
        return
    if(List[y][x] == '
        return
    if(x,y) in used:
        return
    queue.append((x,y,c+1))
    used.add((x,y))

flag = -1
while(len(queue) != 0):
    x,y,c = queue[0]
    if x==W-1 and y==H-1:
        flag = 1
        break
    queue.pop(0)
    check(x+1,y,c)
    check(x, y+1,c)
    check(x-1,y,c)
    check(x, y-1,c)
if(flag == 1):
    print(H*W - c - shape)
else:
    print(-1)

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

que=deque([(0,0,1)])
used={(0,0)}
bcount =sum(s.count("


def check(x,y,c):
    if x<0 or x>w-1 or y<0 or y>h-1:
        return
    if maplis[y][x]=="
        return
    if  (x,y) in used:
        return
    que.append((x,y,c+1))
    used.add((x,y))

f=-1
while que:
    x,y,c=que.popleft()
    if x==w-1 and y==h-1:
        f=c
        break
    check(x-1,y,c)
    check(x+1,y,c)
    check(x,y-1,c)
    check(x,y+1,c)
print(f if f==-1 else(h*w-f-bcount))

Solution (Python):
import numpy as np

def iterate2(mapdata, passed, start):
    queue = [(start, 0)]

    while len(queue) > 0:
        curr, count = queue[0]
        del queue[0]
        if curr == (passed.shape[0] - 1, passed.shape[1] - 1):
            return count
        if mapdata[curr[0]][curr[1]] == '
            continue
        if passed[curr] > 0:
            continue
        passed[curr] = 1

        if curr[0] < passed.shape[0] - 1:
            queue.append(((curr[0] + 1, curr[1]), count + 1))
        if curr[1] < passed.shape[1] - 1:
            queue.append(((curr[0], curr[1] + 1), count + 1))
        if curr[0] > 0:
            queue.append(((curr[0] - 1, curr[1]), count + 1))
        if curr[1] > 0:
            queue.append(((curr[0], curr[1] - 1), count + 1))
    
    return -1

h, w = map(int, input().split())
mapdata = [input() for y in range(h)]
dotsum = sum(mapdata[y].count('.') for y in range(h))

passed = np.zeros((h, w), np.int8)
count = iterate2(mapdata, passed, (0, 0))


if count > 0:
    print(dotsum - count - 1)
else:
    print(-1)

Solution (Python):
from collections import deque


H,W = map(int, input().split())
S = [input() for i in range(H)]
C = sum(s.count('.') for s in S)

dd = ((-1,0), (0, -1), (1,0), (0,1))
que = deque([(0,0,0)])
used = {(0,0)}

res = None
while que :
    s, t, cost = que.popleft()
    if s == H-1 and t == W-1:
        res = cost
        break
    for di, dj in dd:
        ni = s + di; nj = t + dj
        if(not 0 <= ni < H) or (not 0 <= nj < W) or S[ni][nj] == '
            continue
        used.add((ni,nj))
        que.append((ni,nj,cost+1))


if res:
    print(C - 1 - res)
else:
    print(-1)

Solution (Python):
import sys
import math

H, W = map(int, input().split(' '))
S = [input() for i in range(H)]
M = [[10000]*W for i in range(H)]
M[0][0] = 0
for k in range(H*W):
    for i in range(H):
        for j in range(W):
            if M[i][j] == k:
                if i > 0 and M[i-1][j] > k+1 and S[i-1][j] == '.':
                    M[i-1][j] = k+1
                if i < H-1 and M[i+1][j] > k+1 and S[i+1][j] == '.':
                    M[i+1][j] = k+1
                if j > 0 and M[i][j-1] > k+1 and S[i][j-1] == '.':
                    M[i][j-1] = k+1
                if j < W-1 and M[i][j+1] > k+1 and S[i][j+1] == '.':
                    M[i][j+1] = k+1
if M[-1][-1] == 10000:
    print(-1)
    sys.exit()
minDis = M[-1][-1] + 1
numWhite = 0
for line in S:
    numWhite += line.count('.')
print(numWhite-minDis)

Solution (Python):
import copy
import sys
def advance(visited,now):
    result=W*H+1
    if now==W*H-1:
        result=min( len(visited),result)
    else:
        for i in range(W*H):
            if i in visited:
                continue
            elif G[i][now]==1:
                _visited=copy.copy(visited)
                _visited.append(now)
                result=advance(_visited,i)
    return result

H,W=[int(i) for i in input().split(" ")]
Map=[]
white=0
for i in range(H):
    l=[]
    s=input()
    for j in s:
        if j==".":
            l.append(0)
            white+=1
        else:
            l.append(-1)

    Map.append(l)
Map[0][0]=1
G=[[0 for i in range(H*W)] for j in range(H*W)]

for i in range(H):
    for j in range(W):
        if Map[i][j]==-1 :
            continue
        else:
            try:
                if Map[i+1][j]==0:
                    G[W*i+j][W*(i+1)+j]=1
                    G[W*(i+1)+j][W*i+j]=1
            except IndexError:
                pass
            try:
                if Map[i][j+1]==0:
                    G[W*i+j][W*i+j+1]=1
                    G[W*i+j+1][W*i+j]=1
            except IndexError:
                pass

advanced=[[0,0]]
step=2
while Map[-1][-1]==0:
    _advanced=[]
    for i in advanced:
        try:
            if Map[i[0]+1][i[1]]==0:
                Map[i[0]+1][i[1]]=step
                _advanced.append([i[0]+1,i[1]])
        except IndexError:
            pass
        try:
            if Map[i[0]][i[1]+1]==0:
                Map[i[0]][i[1]+1]=step
                _advanced.append([i[0],i[1]+1])
        except IndexError:
            pass
        try:
                if Map[i[0]-1][i[1]]==0 and i[0]!=0:
                    Map[i[0]-1][i[1]]=step
                    _advanced.append([i[0]-1,i[1]])
        except IndexError:
                pass
        try:
                if Map[i[0]][i[1]-1]==0 and i[1]!=0:
                    Map[i[0]][i[1]-1]=step
                    _advanced.append([i[0],i[1]-1])
        except IndexError:
                pass
    step+=1
    advanced=copy.deepcopy(_advanced)
    if len(advanced)==0:
        print(-1)
        sys.exit()
print(white-Map[-1][-1])

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

start = (0, 0, 0)
queue = [start]
white = 0
isGoal = False
depth = 0

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

while(len(queue)):
    i, j, d = queue.pop(0)
    if i < 0 or i >= H or j < 0 or j >= W or S[i][j] == "
        continue
    elif i == H - 1 and j == W - 1:
        isGoal = True
        depth = d
        break
    M[i][j] = "
    for ni, nj in [(-1, 0), (1, 0), (0, 1), (0, -1)]:
        queue.append((i+ni, j+nj, d+1))

print(white-d-1 if isGoal else -1)

Solution (Python):
H, W = map(int, input().split())
s = [list(input()) for x in range(H)]
d = [[None for y in range(W)] for x in range(H)]
q = []
white = 0
for x in range(H):
  for y in range(W):
    if s[x][y] == '.':
      white += 1
dx = [1, 0, -1, 0]
dy = [0, 1, 0, -1]
q.append([0, 0, 0])

def Haba(x_now, y_now, d_now, s, d, q):
  for i in range(4):
    if 0 <= x_now + dx[i] and x_now + dx[i] < H and 0 <= y_now + dy[i] and y_now + dy[i] < W:
      if s[x_now + dx[i]][y_now + dy[i]] == '.':
        s[x_now + dx[i]][y_now + dy[i]] = '
        d[x_now + dx[i]][y_now + dy[i]] = d_now + 1
        q.append([x_now+dx[i], y_now+dy[i], d_now + 1])

while(len(q) > 0):
  x_now, y_now, d_now = q.pop(0)
  Haba(x_now, y_now, d_now, s, d, q)
if d[H - 1][W - 1] is not None:
  ans = white - d[H - 1][W - 1]  - 1
else:
  ans = -1
print(ans)

Solution (Python):
import numpy as np

temp = input()
H,W = temp.split()
H = int(H)
W = int(W)
pref = np.zeros((H,W))
for i in range(H):
    row = input()
    for j in range(W):
        if row[j] == ".":
            pref[i][j] = 1
        else:
            pref[i][j] = 0
totalw = np.count_nonzero(pref)

a = np.zeros((H,W))     

quere = []
quere.append(0)
while quere != []:
    locas = quere[0]
    tempscore = (H+1)*(W+1)
    if locas % W > 0 :
        left = locas - 1
        if a[(left // W)][(left % W)] == 0 and pref[(left // W)][(left % W)] == 1:
            if left not in quere:
                quere.append(left)
        elif a[(left // W)][(left % W)] > 0:
            tempscore = min(tempscore,a[(left // W)][(left % W)])
    if locas % W < W-1:
        right = locas + 1
        if a[(right // W)][(right % W)] == 0 and pref[(right // W)][(right % W)] == 1:
            if right not in quere:
                quere.append(right)
        elif a[(right // W)][(right % W)] > 0:
            tempscore = min(tempscore,a[(right // W)][(right % W)])
    if locas // W > 0 :
        up = locas - W
        if a[(up // W)][(up % W)] == 0 and pref[(up // W)][(up % W)] == 1:
            if up not in quere:
                quere.append(up)
        elif a[(up // W)][(up % W)] > 0:
            tempscore = min(tempscore,a[(up // W)][(up % W)])
    if (locas // W) < (H - 1):
        down = locas + W
        if a[(down // W)][(down % W)] == 0 and pref[(down // W)][(down % W)] == 1:
            if down not in quere:
                quere.append(down)
        elif a[(down // W)][(down % W)] > 0:
            tempscore = min(tempscore,a[(down // W)][(down % W)])
    
    if locas == 0:tempscore=0
    
    a[(locas // W)][(locas % W)] = tempscore + 1
    quere.pop(0)
    

leng = a[H-1][W-1]
if leng > 0 and leng < (H+1)*(W+1):
    score = totalw-leng
    print(int(score))
else:print(-1)