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 sys
from collections import deque

def main():
    h, w = map(int, sys.stdin.readline().split())
    s = tuple(list(e for e in line.strip()) for line in sys.stdin.readlines())
    nwhites = sum(si.count('.') for si in s)

    que = deque([(0, 0, 1)])
    d = (1, 0, -1)
    h -= 1
    w -= 1
    while len(que) > 0:
        y, x, nsteps = que.popleft()
        if y < 0 or y > h or x < 0 or x > w or s[y][x] == '
            continue
        elif y == h and x == w:
            print(nwhites - nsteps)
            break
        s[y][x] = '
        nsteps += 1
        que.extend([(y + dy, x + dx, nsteps) for dy in d for dx in d
                    if (dy != 0 or dx != 0) and dy * dx == 0])
    else:
        print('-1')

if __name__ == '__main__':
    main()

Solution (Python):



import sys
from collections import deque

def main():
    h, w = map(int, sys.stdin.readline().split())
    s = tuple(tuple(e for e in line.strip()) for line in sys.stdin.readlines())
    nwhites = sum(si.count('.') for si in s)

    que = deque([(0, 0, 1)])
    d = (1, 0, -1)
    visited = [[False] * w for _ in range(h)]
    h -= 1
    w -= 1
    while len(que) > 0:
        y, x, nsteps = que.popleft()
        if y < 0 or y > h or x < 0 or x > w or visited[y][x] == True or s[y][x] == '
            continue
        elif y == h and x == w:
            print(nwhites - nsteps)
            break
        visited[y][x] = True
        nsteps += 1
        que.extend([(y + dy, x + dx, nsteps) for dy in d for dx in d
                    if (dy != 0 or dx != 0) and dy * dx == 0])
    else:
        print('-1')

if __name__ == '__main__':
    main()

Solution (Python):



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


def walk(pos):
    queue = [pos]

    while len(queue)>0:
        pos = queue.pop(0)
        x, y = pos
        val = M[y][x]
        

        
        if y>0 and (M[y-1][x]=='.' or (isinstance(M[y-1][x], int) and val+1<M[y-1][x])):
            M[y-1][x] = val + 1
            queue += [(x, y-1)]
        
        if y<H-1 and (M[y+1][x]=='.' or (isinstance(M[y+1][x], int) and val+1<M[y+1][x])):
            M[y+1][x] = val + 1
            queue += [(x, y+1)]
        
        if x>0 and (M[y][x-1]=='.' or (isinstance(M[y][x-1], int) and val+1<M[y][x-1])):
            M[y][x-1] = val + 1
            queue += [(x-1, y)]
        
        if x<W-1 and (M[y][x+1]=='.' or (isinstance(M[y][x+1], int) and val+1<M[y][x+1])):
            M[y][x+1] = val + 1
            queue += [(x+1, y)]
        


M[H-1][W-1] = 1
walk((W-1, H-1))




if M[0][0]=='.':
    print(-1)
else:
    blocks = sum([m.count('
    print(H*W - blocks - M[0][0])

Solution (Python):
h,w = map(int, input().split())
from collections import defaultdict
G = defaultdict(list)

def mind(Q, d):
    c = float('inf')
    ret = 0
    for i, j in enumerate(d):
        if c > j and i in Q:
            c = j
            ret = i
    return ret
 
def dijkstra(G, n, start):
    d = [float('inf')] * n
    d[start] = 0
    Q = set(range(n))
    preQ = None
    while len(Q) != 0:
        preQ = Q
        u = mind(Q, d)
        Q = Q - set([u])
        for v in G[u]:
            if d[v] > d[u] + 1:
                d[v] = d[u] + 1
        if Q == preQ:
            break
    return d
s = []

i2num = {}
count = 0
start = 0

for i in range(h):
    r = input()
    s.append([r[j] for j in range(w)])
    count += s[i].count('
num=-1
for i in range(h):
    r = s[i]
    for j in range(w):
        if r[j] != '1':
            num += 1
            i2num[(i,j)] = num
        if r[j] == 's':
            start = num
            r[j] = '0'
        elif r[j] == 'g':
            goal = num
            r[j] = '0'
G = defaultdict(list)
r = c = 1
for r in range(h):
    for c in range(w):
        t = s[r][c]
        if t == '
        num = i2num[(r,c)]
        if r - 1 >= 0 and s[r - 1][c] == '.':
            G[num].append(i2num[(r - 1, c)])
        if r + 1 < h and s[r+1][c] == '.':
            G[num].append(i2num[(r + 1, c)])
        if c - 1 >= 0 and s[r][c - 1] == '.':
            G[num].append(i2num[(r, c - 1)])
        if c + 1 < w and s[r][c + 1] == '.':
            G[num].append(i2num[(r, c + 1)])

d = dijkstra(G, h*w, start)
if d[-1] == float('inf'):
    print('-1')
else:
    print(h*w-(d[-1]+1)-count)

Solution (Python):
H, W = (int(i) for i in input().split())
S = []
for i in range(H):
	row = input()
	S.append([(0 if row[j]=="." else 1) for j in range(W)])

D = [[10000 for j in range(W)] for i in range(H)]
R = [[False for j in range(W)] for i in range(H)]

N_black = 0
for i in range(H):
	for j in range(W):
		if S[i][j] == 1:
			D[i][j] = -1
			R[i][j] = True
			N_black += 1

def update(i0, j0, i1, j1):
	global D
	center = D[i0][j0]
	adj = D[i1][j1]
	r = R[i1][j1]
	if adj != -1 and r == False and center + 1 < adj:
		D[i1][j1] = center + 1


def check_around(i ,j):
	
	if i != 0:
		update(i, j, i-1, j)
	
	if j != 0:
		update(i, j, i, j-1)
	
	if i != H-1:
		update(i, j, i+1, j)
	
	if j != W-1:
		update(i, j, i, j+1)

def minimum_point():
	global H, W
	m = 10001
	ni = 0
	nj = 0
	for i in range(H):
		for j in range(W):
			d = D[i][j]
			if d != -1 and R[i][j] == False and d < m:
				m = d
				ni = i
				nj = j
	return (ni, nj)


D[0][0] = 1
R[0][0] = True

pi = 0
pj = 0

for idx in range(W*H):
	check_around(pi, pj)
	pi, pj = minimum_point()
	R[pi][pj] = True

if D[H-1][W-1] == 10000:
	print(-1)
else:
	print(W*H-D[H-1][W-1]-N_black)

Solution (Python):
def d_grid_epainting(H, W, S):
    INF = float('inf')
    white = 0  
    for i in range(H):
        for j in range(W):
            if S[i][j] == '.':
                white += 1

    def bfs():
        
        queue = [(0, 0)]
        dist = [[INF for _ in range(W)] for _ in range(H)]  
        dist[0][0] = 0  
        while len(queue):
            i, j = queue.pop()
            if i == H - 1 and j == W - 1:
                
                break
            for k in range(4):
                nh, nw = i + [1, 0, -1, 0][k], j + \
                    [0, 1, 0, -1][k]  
                if 0 <= nh < H and 0 <= nw < W and S[nh][nw] != '
                    
                    queue.insert(0, (nh, nw))  
                    dist[nh][nw] = dist[i][j] + 1
        return dist[H - 1][W - 1]

    tmp = bfs()
    if tmp == INF:
        ans = -1
    else:
        
        
        ans = white - (tmp + 1)
    return ans

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

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

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

q = deque([(0, 0, 0)])
used = {(0, 0)}
res = None

while q:
    i, j, cost = q.popleft()
    if i == w - 1 and j == h - 1:
        res = cost
        break
    for k in range(4):
        if not (0 <= i + dx[k] < w):
            continue
        if not (0 <= j + dy[k] < h):
            continue

        if s[j + dy[k]][i + dx[k]] == '
            continue
        if (i + dx[k], j + dy[k]) in used:
            continue

        used.add((i + dx[k], j + dy[k]))
        q.append((i + dx[k], j + dy[k], cost + 1))

if res:
    ans = h * w - cost - 1
    for j in range(h):
        ans -= s[j][:].count('
    print(ans)
else:
    print(-1)

Solution (Python):

from collections import deque
def inpl(): return tuple(map(int, input().split()))

H, W = inpl()

S = [input() for _ in range(H)]
V = [[True if S[h][w]=="." else False for w in range(W)] for h in range(H)]
V[0][0] = True

Q = deque() 
Q.append([1, 0, 0])

ok = False
while Q:
    s, h, w = Q.popleft()
    if h == H-1 and w == W-1:
        ok = True
        break
    
    if h > 0:
        if V[h-1][w]:
            V[h-1][w] = False
            Q.append([s+1, h-1, w])
    
    if h < H-1:
        if V[h+1][w]:
            V[h+1][w] = False
            Q.append([s+1, h+1, w])

    if w > 0:
        if V[h][w-1]:
            V[h][w-1] = False
            Q.append([s+1, h, w-1])
    
    if w < W-1:
        if V[h][w+1]:
            V[h][w+1] = False
            Q.append([s+1, h, w+1])

if ok:
    b = sum([s.count("
    print(H*W - b - s)
else:
    print(-1)

Solution (Python):
h,w = map(int,input().split())
m = [list(map((lambda x: 0 if x == '
ret = sum(list(map(sum,m)))

q = [[0,0,0]]
m[0][0] = 0
while len(q)!=0:
    qtop = q.pop(0)
    x = qtop[0]
    y = qtop[1]
    d = qtop[2]
    if x == h-1 and y == w-1:
        print(ret-d-1)
        break
    if 0 < x and m[x-1][y] == 1:
        m[x-1][y] = 0
        q.append([x-1,y,d+1])
    if h-1 > x and m[x+1][y] == 1:
        m[x+1][y] = 0
        q.append([x+1,y,d+1])
    if 0 < y and m[x][y-1] == 1:
        m[x][y-1] = 0
        q.append([x,y-1,d+1])
    if w-1 > y and m[x][y+1] == 1:
        m[x][y+1] = 0
        q.append([x,y+1,d+1])
else:
    print(-1)

Solution (Python):
h, w = map(int, input().split())
s = []
s.append(list('w' * (w+2)))
d = []
d.append([-1]*(w+2))
sharp = 0
for i in range(h):
    ipt = list('w' + input() + 'w')
    sharp += ipt.count('
    s.append(ipt)
    d.append([-1]*(w+2))
s.append(list('w' * (w+2)))
d.append([-1]*(w+2))
queue = [(h, w)]
d[h][w] = 1


while len(queue) > 0 and d[1][1] == -1:
    c = queue.pop(0)
    r = c[0]
    c = c[1]
    dst = d[r][c] + 1
    if s[r-1][c] == '.' and d[r-1][c] == -1:
        queue.append((r-1, c))
        d[r-1][c] = dst

    if s[r+1][c] == '.' and d[r+1][c] == -1:
        queue.append((r+1, c))
        d[r+1][c] = dst

    if s[r][c-1] == '.' and d[r][c-1] == -1:
        queue.append((r, c-1))
        d[r][c-1] = dst

    if s[r][c+1] == '.' and d[r][c+1] == -1:
        queue.append((r, c+1))
        d[r][c+1] = dst

    '''for i in d:
        print(i)
    print(" ")'''
if d[1][1] == -1:
    print(-1)
else:
    print(h * w - sharp - d[1][1])

Solution (Python):
import numpy as np
import scipy as sp
import scipy.sparse.csgraph as sg

H, W = [int(a) for a in input().split()]
ss = []
for _ in range(H):
    ss.append(input())

g = np.zeros((H*W,H*W))

v_edges = [((i,j), (i,j+1)) for i in range(H) for j in range(W-1) if ss[i][j] == "." and ss[i][j+1] == "."]
h_edges = [((i,j), (i+1,j)) for i in range(H-1) for j in range(W) if ss[i][j] == "." and ss[i+1][j] == "."]

for (si,sj), (di,dj) in v_edges + h_edges:
    g[si*W+sj][di*W+dj] = 1
    g[di*W+dj][si*W+sj] = 1

r = sg.dijkstra(g, indices=[0,H*W-1])
score = r[0,H*W-1]

if sp.isinf(score):
    print(-1)
    exit(0)
else:
    
    

    ss_ = "".join(ss)
    num = len([0 for c in ss_ if c == '.'])
    
    
    print("%d" % (num - (score+1)))

Solution (Python):
import sys
H,W=map(int,input().split())
s=[]
bla=0
whi=0
maze=[["" for i in range(W)] for j in range(H)]
for i in range(H):
    s.append(input())
for i in range(H):
    for j in range(W):
        if(s[i][j]=="
            bla+=1
            maze[i][j]="
        else:
            whi+=1
            maze[i][j]="."

def clear_maze(sx,sy,gx,gy,maze,W,H):
    INF=100000000
    distance=[[INF for i in range(W)] for j in range(H)]
    
    def bfs():
        testx=[1,0,-1,0]
        testy=[0,1,0,-1]
        queue=[]
        
        queue.insert(0,(sy,sx))
        
        distance[sy][sx]=0
        count=0
        while len(queue):
            if(count>100000000):
                return -1
            count+=1
            x,y=queue.pop()
            
            if(x==gx and y==gy):
                break
            
            for i in range(0,4):
                nx,ny=x+testx[i],y+testy[i]
                
                if(0<=nx and nx<W and 0<=ny and ny<H):
                    if(maze[ny][nx]!="
                        if(distance[ny][nx]==INF):
                            queue.insert(0,(nx,ny))
                            distance[ny][nx]=distance[y][x]+1
        if(distance[gy][gx]==INF):
            return -1
        else:
            return distance[gy][gx]
        
    return bfs()

area=W*H
step=clear_maze(0,0,W-1,H-1,maze,W,H)
if(step==-1):
    print(-1)
elif(maze[0][0]=="
    print(-1)
elif(maze[H-1][W-1]=="
    print(-1)
else:
    score=area-step-1-bla
    print(score)

Solution (Python):
H,W=map(int,input().split())
s=[]
dst=[]
INF=1e8
for i in range(H):
    s.append(input())
    dst.append([INF for i in range(W)])

gx=W-1
gy=H-1
que=[]
que.append([0,0])
dst[0][0]=0
x=[-1,1,0,0]
y=[0,0,-1,1]

goalFlag=False
while len(que)>0:
    p=que.pop(0)
    if p[0]==gx and p[1]==gy: 
        goalFlag=True
        break
    for (dx,dy) in zip(x,y):
        nextx=p[0]+dx
        nexty=p[1]+dy
        if H>nexty>=0 and W>nextx>=0 and s[nexty][nextx]=='.' and dst[nexty][nextx]==INF:
            que.append([nextx,nexty])
            dst[nexty][nextx]=dst[p[1]][p[0]]+1
if goalFlag:
    count=0 
    for h in range(H):
        for w in range(W):
            if h==w==0 or (h==gy and w==gx):
                continue
            elif s[h][w]=='.':
                count+=1
    print(count-dst[gy][gx]+1)
else: print(-1)

Solution (Python):
import sys,collections;sys.setrecursionlimit(10**7)
def Is(): return [int(x) for x in sys.stdin.readline().split()]
def Ss(): return sys.stdin.readline().split()
def I(): return int(sys.stdin.readline())
def S(): return input()

def debug_print(maze):
    for xx in maze:
        for yy in xx:
            print(yy,end="")
        print("\n",end="")

def clear_maze(sx, sy, gx, gy, maze):

    INF = 100000000
    field_x_length = len(maze)
    field_y_length = len(maze[0])
    distance = [[INF for i in range(field_y_length)] for j in range(field_x_length)]
    def bfs():
        queue = []
        queue.insert(0, (sx, sy))
        distance[sx][sy] = 0
        while len(queue):
            x, y = queue.pop()
            if x == gx and y == gy:
                break
            for i in range(0, 4):
                nx, ny = x + [1, 0, -1, 0][i], y + [0, 1, 0, -1][i]
                if (0 <= nx and nx < field_x_length and 0 <= ny and ny < field_y_length and maze[nx][ny] != '
                    queue.insert(0, (nx, ny))
                    distance[nx][ny] = distance[x][y] + 1
        if distance[H-1][W-1] == INF:
            print(-1)
            exit()
        return distance[gx][gy] 
    return bfs()

H,W = Is()
maze = []
for _ in range(H):
    maze.append(list(S()))
sx, sy = 0, 0 
gx, gy = H-1, W-1 
a = clear_maze(sx, sy, gx, gy, maze)
for i in range(H):
    a += maze[i].count("
print(H*W-a-1)

Solution (Python):
import sys
import Queue

sys.setrecursionlimit(1000000)

def s(m, h, w, d, q):
    if q.empty(): return d[h - 1][w - 1]
    k, i, j = q.get()
    if i > 0 and m[i - 1][j] == '.' and k + 1 < d[i - 1][j]:
        d[i - 1][j] = k + 1
        q.put((k + 1, i - 1, j))
    if i < h - 1 and m[i + 1][j] == '.' and k + 1 < d[i + 1][j]:
        d[i + 1][j] = k + 1
        q.put((k + 1, i + 1, j))
    if j > 0 and m[i][j - 1] == '.' and k + 1 < d[i][j - 1]:
        d[i][j - 1] = k + 1
        q.put((k + 1, i, j - 1))
    if j < w - 1 and m[i][j + 1] == '.' and k + 1 < d[i][j + 1]:
        d[i][j + 1] = k + 1
        q.put((k + 1, i, j + 1))
    return s(m, h, w, d, q)

h, w = map(int, raw_input().split())
m = [raw_input()[:w] for _ in range(h)]
q = Queue.PriorityQueue()
d = [None] * h
for i in range(h):
    d[i] = [1000000] * w
d[0][0] = 1
for i in range(h):
    for j in range(w):
        if m[i][j] == '.':
            q.put((d[i][j], i, j))
c = s(m, h, w, d, q)
if c == 1000000: print -1
else:
    a = 0
    for row in m:
        a += row.count('
    print h * w - c - a

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

    
    

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

    q = []
    q.insert(0, (0,0))
    hist = [[0 for i in range(w)] for j in range(h)]
    hist[0][0] = 1


    while(len(q) > 0):
        x, y = q.pop()

        if x == w-1 and y == h-1:
            return h*w - nwall - hist[h-1][w-1]

        for i in range(0, 4):
            nx, ny = x+[1,0,-1,0][i], y+[0,1,0,-1][i]

            if nx<0 or nx>=w or ny<0 or ny>=h:
                continue
            if maze[ny][nx] == '
                continue
            if hist[ny][nx] >= 1:
                continue
            
            

            q.insert(0, (nx,ny))
            hist[ny][nx] = hist[y][x] + 1

    return -1


print(solve())

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

def isWay(x, y):
    if x >= 0 and x < h and y >= 0 and y < w and arr[x][y] == '.':
        return True
    else:
        return False

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

queue = [[0, 0]]
arr[0][0] = 1
while 1:
    if len(queue) == 0:
        break
    cell = queue[0]
    queue.pop(0)
    x = cell[0]
    y = cell[1]
    n = arr[x][y]
    if(isWay(x-1, y)):
        arr[x-1][y] = n+1
        queue.append([x-1, y])
    if(isWay(x+1, y)):
        arr[x+1][y] = n+1
        queue.append([x+1, y])
    if(isWay(x, y-1)):
        arr[x][y-1] = n+1
        queue.append([x, y-1])
    if(isWay(x, y+1)):
        arr[x][y+1] = n+1
        queue.append([x, y+1])
if arr[h-1][w-1] == '.':
    print(-1)
else:
    print(numWay - arr[h-1][w-1])

Solution (Python):
from collections import Counter

h, w = [int(i) for i in input().split()]
maze = []
c = 0
for i in range(h):
    l = list(input().strip())
    maze.append(l)
    counter = Counter(l)
    c += counter['


def clear_maze(sx, sy, gx, gy, maze):
    INF = 1000000000

    distance = [[INF for i in range(gy)] for j in range(gx)]

    def bfs():
        queue = []

        queue.insert(0, (sx, sy))

        distance[sx][sy] = 0

        while len(queue):
            x, y = queue.pop()

            if x == gx - 1 and y == gy - 1:
                break

            for i in range(0, 4):
                nx, ny = x + [1, 0, -1, 0][i], y + [0, 1, 0, -1][i]

                
                if (0 <= nx < gx) and (0 <= ny < gy):
                    if maze[nx][ny] != '
                        queue.insert(0, (nx, ny))
                        distance[nx][ny] = distance[x][y] + 1


        
        return distance[gx-1][gy-1]

    return bfs()


try:
  q=w * h - clear_maze(0, 0, h, w, maze)-1 - c
  if q<0:
    print('-1')
  else:
    print(w * h - clear_maze(0, 0, h, w, maze)-1 - c)
except:
  print('-1')

Solution (Python):

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

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

distance = [[float("inf") for i in range(W)] for j in range(H)]

def bfs():
    queue = []
    sx = 0
    sy = 0
    gx = H-1
    gy = W-1

    queue.insert(0, (sx, sy))

    distance[sx][sy] = 0

    while len(queue):
        x, y = queue.pop()

        if x == gx and y == gy:
            break

        for i in range(0, 4):
            nx, ny = x + [1, 0, -1, 0][i], y + [0, 1, 0, -1][i]
            
            if (0 <= nx < H and 0 <= ny < W):
                if maze[nx][ny] != '
                    queue.insert(0, (nx, ny))
                    distance[nx][ny] = distance[x][y] + 1

    return distance[gx][gy]

d = bfs()
cnt = 0
for i in range(H):
    for j in range(W):
        if maze[i][j] == ".":
            cnt += 1
if  d == float("inf"):
    print(-1)
else:
    print(cnt - d - 1)

Solution (Python):
h, w = [int(x) for x in input().split()]
s = []
for i in range(h):
  s += [input()]

black = 0
for si in s:
  for sij in si:
    if sij == '
      black += 1

cnt = 0
d = []
for i in range(h):
  d.append([])
  for j in range(w):
    d[-1].append(10 ** 9)

d[0][0] = 1
q = [(0, 0)]
for k in range(h * w):
  p = q.pop(0)
  i = p[0]
  j = p[1]
  dis = d[i][j]

  if i + 1 < h:
    if s[i + 1][j] == '.':
      if dis + 1 < d[i + 1][j]:
        d[i + 1][j] = dis + 1
        q.append((i + 1, j))
  if j + 1 < w:
    if s[i][j + 1] == '.':
      if dis + 1 < d[i][j + 1]:
        d[i][j + 1] = dis + 1
        q.append((i, j + 1))
  if i - 1 >= 0:
    if s[i - 1][j] == '.':
      if dis + 1 < d[i - 1][j]:
        d[i - 1][j] = dis + 1
        q.append((i - 1, j))
  if j - 1 >= 0:
    if s[i][j - 1] == '.':
      if dis + 1 < d[i][j - 1]:
        d[i][j - 1] = dis + 1
        q.append((i, j - 1))

  if len(q) <= 0:
    break

cnt = d[h - 1][w - 1]
if cnt != 10 ** 9:
  res = h * w - black - cnt
  print(res)
else:
  print(-1)

Solution (Python):



R,C = map(int, input().split())



count=0

sy,sx = 2,2
gy,gx = R+1, C+1

c_org = [ [ -1 if c_org == "

for i in range(R):
    c_org[i].append( -1)
    c_org[i].insert(0,-1)

    count=count+c_org[i].count(9999)

c_plus=[-1 for i in range(C+2)]

c=[]
c.append(c_plus)
for i in range(R):
    c.append(c_org[i])
c.append(c_plus)



 
c[sy - 1][sx - 1] = 0
 
neighbors = [(1, 0), (-1, 0), (0, 1), (0, -1)]
check_list = [(sy - 1, sx - 1)]
index = 0
 
while index < len(check_list):
    check_rc = check_list[index]
    for neighbor in [ (check_rc[0] + n[0], check_rc[1] + n[1]) for n in neighbors]:
        if c[neighbor[0]][neighbor[1]] >= 0 and  c[neighbor[0]][neighbor[1]] > c[check_rc[0]][check_rc[1]] + 1:
            c[neighbor[0]][neighbor[1]] = c[check_rc[0]][check_rc[1]] + 1
            check_list.append(neighbor)
    index += 1





if c[gy - 1][gx - 1]!=9999:
    print(count-c[gy - 1][gx - 1]-1)
else:
    print(-1)

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

count = 0
for i in s:
  count += i.count('

c = 1
queue = []
s[0][0] = c
queue.append((0,0))
while len(queue) != 0:
  v = queue.pop(0)
  c = s[v[0]][v[1]]+1
  if 0 <= v[0]-1:
    if s[v[0]-1][v[1]] == '.':
      s[v[0]-1][v[1]] = c
      queue.append((v[0]-1, v[1]))
  if 0 <= v[1]-1:
    if s[v[0]][v[1]-1] == '.':
      s[v[0]][v[1]-1] = c
      queue.append((v[0], v[1]-1))

  if v[0]+1 < h:
    if s[v[0]+1][v[1]] == '.':
      s[v[0]+1][v[1]] = c
      queue.append((v[0]+1, v[1]))

  if v[1]+1 < w:
    if s[v[0]][v[1]+1] == '.':
      s[v[0]][v[1]+1] = c
      queue.append((v[0], v[1]+1))
if s[h-1][w-1] == '.':
  print(-1)
else:
  print(h*w-count-s[h-1][w-1])

Solution (Python):
from collections import deque

H, W = map(int, input().split())
ss = ['
ss = ['

numWhite = sum(map(lambda s: s.count('.'), ss))

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

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

Q = deque()
Q.append((1, 1))
while Q:
    i, j = Q.popleft()

    for di, dj in dij:
        if ss[i + di][j + dj] == '
        if dist[i + di][j + dj] == float('inf'):
            dist[i + di][j + dj] = dist[i][j] + 1
            Q.append((i + di, j + dj))

if dist[H][W] == float('inf'):
    print(-1)
else:
    print(numWhite - dist[H][W])

Solution (Python):
import numpy as np

def solve(posi):
    INF = 100000000000
    d = np.zeros((H, W))
    for i in range(H):
        for j in range(W):
            d[i][j] = INF
    que = [posi]
    d[posi[0],posi[1]] = 0

    move = np.array([[1,0], [-1,0], [0,1], [0,-1]])
    while len(que):
        p = que.pop(0)
        if np.allclose(posi, np.array([H-1,W-1])):
            break

        for dir in move:
            new_p = p + dir
            if 0 <= new_p[0] and new_p[0] < H and 0 <= new_p[1] and new_p[1] < W:
                if d[new_p[0],new_p[1]] == INF and maze[new_p[0]][new_p[1]] != '
                    que.append(new_p)
                    d[new_p[0],new_p[1]] = d[p[0], p[1]] + 1

    if d[H-1][W-1] == INF:
        return -1
    return d[H-1][W-1]

if __name__=='__main__':
    H, W  = map(int, input().split(' '))
    maze = []
    for i in range(H):
        maze.append(list(input()))
    counter = 0
    for i in range(H):
        for j in range(W):
            if maze[i][j] == '.':
                counter += 1

    posi = np.array([0,0])
    if solve(posi) != -1:
        print(int(counter - solve(posi) - 1))
    else:
        print(-1)

Solution (Python):
R,C=map(int,input().split())
sx,sy=1,1
gx,gy=R,C
count=0
mp = [[i for i in input().rstrip()] for i in range(R)]
for i in range(R):
  mp[i]=list(mp[i])
for i in range(R):
	for j in range(C):
		if(mp[i][j]=='
			count+=1
ans=[[3000 for i in range(C)] for j in range(R)]
ans[sx-1][sy-1]=0
start=[sx-1,sy-1]
goal=[gx-1,gy-1]
nsx=[1,0,-1,0]
nsy=[0,1,0,-1]

def bfs(graph,st,end):
  queue=[st]
  while queue:
    nw=queue.pop(0)
    if nw==end:
      return ans[end[0]][end[1]]
    else:
      for i in range(4):
        ns1=nw[0]+nsx[i]
        ns2=nw[1]+nsy[i]
        if (0 <= ns1)and(ns1<=(R-1))and(0<=ns2)and(ns2<=(C-1)) and ans[ns1][ns2]==3000 and mp[ns1][ns2]=='.':
          ans[ns1][ns2]=ans[nw[0]][nw[1]]+1
          queue.append([ns1,ns2])
  return

while True:
	try:
		print(R*C-bfs(mp,start,goal)-1-count)
		break
	except (RuntimeError,TypeError,NameError):
		print(-1)
		break

Solution (Python):
import math,string,itertools,fractions,heapq,collections,re,array,bisect,sys,random,time,copy,functools

sys.setrecursionlimit(10**7)
inf = 10**20
eps = 1.0 / 10**15
mod = 10**9+7

def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LI_(): return [int(x)-1 for x in sys.stdin.readline().split()]
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def I(): return int(sys.stdin.readline())
def F(): return float(sys.stdin.readline())
def S(): return input()
def pf(s): return print(s, flush=True)


def main():
    h,w = LI()
    a = [[c=='

    def search():
        d = collections.defaultdict(lambda: inf)
        s = (0,0)
        d[s] = 1
        q = []
        heapq.heappush(q, (1, s))
        v = collections.defaultdict(bool)
        while len(q):
            k, u = heapq.heappop(q)
            if v[u]:
                continue
            v[u] = True

            for ni,nj in [(0,1),(0,-1),(1,0),(-1,0)]:
                ny = u[0] + ni
                nx = u[1] + nj
                if ny < 0 or ny >= h or nx < 0 or nx >= w:
                    continue
                if v[(ny,nx)] or a[ny][nx]:
                    continue
                uv = (ny,nx)
                vd = k + 1
                if d[uv] > vd:
                    d[uv] = vd
                    heapq.heappush(q, (vd, uv))

        return d

    d = search()
    r = d[(h-1,w-1)]
    if r == inf:
        return -1
    for ai in a:
        for aj in ai:
            if not aj:
                r -= 1

    return -r


print(main())

Solution (Python):
R,C=map(int,input().split())
mp = [[i for i in input().rstrip()] for i in range(R)]
for i in range(R):
  mp[i]=list(mp[i])
ans=[[3000 for i in range(C)] for j in range(R)]
ans[0][0]=0
start=[0,0]
goal=[R-1,C-1]
nsx=[1,0,-1,0]
nsy=[0,1,0,-1]

def bfs(graph,st,end):
  queue=[st]
  while queue:
    nw=queue.pop(0)
    if nw==end:
      return ans[end[0]][end[1]]
    else:
      for i in range(4):
        ns1=nw[0]+nsx[i]
        ns2=nw[1]+nsy[i]
        if (0 <= ns1)and(ns1<=(R-1))and(0<=ns2)and(ns2<=(C-1)) and ans[ns1][ns2]==3000 and mp[ns1][ns2]==".":
          ans[ns1][ns2]=ans[nw[0]][nw[1]]+1
          queue.append([ns1,ns2])
  return 

bfs(mp,start,goal)
if ans[R-1][C-1]==3000:
  print("-1")
else:
  max_ans=R*C-ans[R-1][C-1]-1
  for i in range(R):
    for j in range(C):
      if mp[i][j]=='
        max_ans-=1
  print(max_ans)

Solution (Python):
from collections import deque

WHITE = -1
BLACK = -2
GOAL = -3
field_mapping = {
    '.': WHITE,
    '
}


def neighbors(y, x):
    points = []
    if y-1 >= 0:
        points.append([y-1, x])
    if y+1 < H:
        points.append([y+1, x])
    if x-1 >= 0:
        points.append([y, x-1])
    if x+1 < W:
        points.append([y, x+1])
    return points


def searching():
    field[0][0] = 1
    queue = deque([[0, 0]])
    while len(queue) > 0:
        [y, x] = queue.popleft()
        current_distance = field[y][x]
        for [n_y, n_x] in neighbors(y, x):
            point_status = field[n_y][n_x]
            if point_status == WHITE:
                field[n_y][n_x] = current_distance + 1
                queue.append([n_y, n_x])
            elif point_status == GOAL:
                return current_distance + 1
    return -1


def main():
    global H, W, field
    [H, W] = [int(i) for i in input().split()]
    field = []
    white_num = 0
    for i in range(H):
        line = []
        for color in [field_mapping[s] for s in input()]:
            line.append(color)
            if color == WHITE:
                white_num += 1
        field.append(line)
    field[H-1][W-1] = GOAL
    walked_points = searching()
    if walked_points < 0:
        print(-1)
    else:
        print(white_num - walked_points)


if __name__ == '__main__':
    main()

Solution (Python):
from sys import exit

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

P = set()
Q = {(0, 0)}
QQ = set()

def add(x, y):
    if s[x][y] == '.' and (x, y) not in P:
        QQ.add((x, y))

def search_next(x, y):
    if x > 0:
        add(x-1, y)
    if x < H-1:
        add(x+1, y)
    if y > 0:
        add(x, y-1)
    if y < W-1:
        add(x, y+1)

count = 0

while True:
    count += 1
    for q in Q:
        search_next(*q)
    P = P.union(Q)
    Q = QQ
    QQ = set()
    if (H-1, W-1) in Q:
        break
    elif len(Q) == 0:
        print(-1)
        exit(0)

white = 0
for line in s:
    white += line.count('.')

print(white - count - 1)