Problem:
 Score: 400 points    Problem statement  We have an H \times W grid whose squares are painted black or white. The square at the i -th row from the top and the j -th column from the left is denoted as (i, j) . Snuke would like to play the following game on this grid. At the beginning of the game, there is a character called Kenus at square (1, 1) . The player repeatedly moves Kenus up, down, left or right by one square. The game is completed when Kenus reaches square (H, W) passing only white squares. Before Snuke starts the game, he can change the color of some of the white squares to black. However, he cannot change the color of square (1, 1) and (H, W) . Also, changes of color must all be carried out before the beginning of the game. When the game is completed, Snuke's score will be the number of times he changed the color of a square before the beginning of the game. Find the maximum possible score that Snuke can achieve, or print -1 if the game cannot be completed, that is, Kenus can never reach square (H, W) regardless of how Snuke changes the color of the squares.  The color of the squares are given to you as characters s_{i, j} . If square (i, j) is initially painted by white, s_{i, j} is . ; if square (i, j) is initially painted by black, s_{i, j} is # .      Constraints   H is an integer between 2 and 50 (inclusive).  W is an integer between 2 and 50 (inclusive).  s_{i, j} is . or #  (1 \leq i \leq H, 1 \leq j \leq W) .  s_{1, 1} and s_{H, W} are . .         Input  Input is given from Standard Input in the following format:  H  W  s_{1, 1}s_{1, 2}s_{1, 3} ... s_{1, W}  s_{2, 1}s_{2, 2}s_{2, 3} ... s_{2, W}  :  :  s_{H, 1}s_{H, 2}s_{H, 3} ... s_{H, W}       Output  Print the maximum possible score that Snuke can achieve, or print -1 if the game cannot be completed.        Sample Input 1 3 3
..#
#..
...      Sample Output 1 2  The score 2 can be achieved by changing the color of squares as follows:        Sample Input 2 10 37
.....................................
...#...####...####..###...###...###..
..#.#..#...#.##....#...#.#...#.#...#.
..#.#..#...#.#.....#...#.#...#.#...#.
.#...#.#..##.#.....#...#.#.###.#.###.
.#####.####..#.....#...#..##....##...
.#...#.#...#.#.....#...#.#...#.#...#.
.#...#.#...#.##....#...#.#...#.#...#.
.#...#.####...####..###...###...###..
.....................................      Sample Output 2 209

Solution (Python):


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

s = [raw_input() for i in range(h)]

accessible = [(0,0)]
accessible_now = [(0,0)]
n_black = sum([ss.count('

stroke = 1
while True:
  stroke += 1
  accessible_next = [] 
  for loc in accessible_now:
    for step in [(1,0),(0,1),(-1,0),(0,-1)]:
      loc_next = (loc[0]+step[0],loc[1]+step[1])
      if loc_next == (h-1,w-1):
        print h*w-n_black-stroke 
        exit(0)
      if ((-1 in loc_next) or (loc_next[0]==h) or (loc_next[1]==w)):
        continue
      if loc_next in accessible:
        continue
      if s[loc_next[0]][loc_next[1]] == '
        continue
      accessible.append(loc_next)
      accessible_next.append(loc_next)
  accessible_now = accessible_next
  if(len(accessible_next)==0):
    print -1
    exit(0)

Solution (Python):
from collections import deque


def get_arounds(point, grid, max_x, max_y):
    x = point[0]
    y = point[1]
    arounds = [(x + dx, y + dy) for dx, dy in ((0, -1), (1, 0), (0, 1), (-1, 0))]
    return list(filter(lambda a: 0 <= a[0] < max_x and
                                 0 <= a[1] < max_y and
                                 grid[a[0]][a[1]], arounds))


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

grid = []
for i in range(0, H):
    grid.append(list(map(lambda x: True if x == '.' else False, list(input()))))

black = sum(map(lambda l: l.count(False), grid))

grid[0][0] = False
p_grid = {(0, 0): 0}
queue = deque([(0, 0)])
while not len(queue) == 0:
    here = queue.popleft()
    if here == (H - 1, W - 1):
        break;
    arounds = get_arounds(here, grid, H, W)
    for a in arounds:
        grid[a[0]][a[1]] = False
        p_grid[a] = p_grid[here] + 1
    if not arounds:
        continue
    queue.extend(arounds)

if (H-1, W-1) in p_grid:
    print(H * W - (p_grid[H-1, W-1] + 1) - black)
else:
    print(-1)

Solution (Python):
from collections import deque
 
 
def dfs(field):
    q = deque([(0, 0, 1)])
    visited = [[False] * w for _ in range(h)]
    while q:
        i, j, d = q.popleft()
        if i == h - 1 and j == w - 1:
            return d
        if visited[i][j]:
            continue
        visited[i][j] = True
        if i > 0 and field[i - 1][j] == '.':
            q.append((i - 1, j, d + 1))
        if i < h - 1 and field[i + 1][j] == '.':
            q.append((i + 1, j, d + 1))
        if j > 0 and field[i][j - 1] == '.':
            q.append((i, j - 1, d + 1))
        if j < w - 1 and field[i][j + 1] == '.':
            q.append((i, j + 1, d + 1))
    else:
        return -1
 
 
h, w = map(int, input().split())
field = [input() for _ in range(h)]
init_black = sum(r.count('
res = dfs(field)
if res == -1:
    print(-1)
else:
    print(h * w - res - init_black)

Solution (Python):
def next(s,x,y):
	ans = []
	if s[x][y+1] == '.':
		ans.append([x,y+1])
	if s[x][y-1] == '.':
		ans.append([x,y-1])
	if s[x+1][y] == '.':
		ans.append([x+1,y])
	if s[x-1][y] == '.':
		ans.append([x-1,y])
	return ans

h,w = map(int,input().split())
s = []
add = ['
s.append(add)
counter = 0
for i in range(h):
	sinput = str(input())
	stemp = []
	for i in range(w):
		stemp.append(sinput[i])
	for i in range(w):
		if stemp[i] == '.':
			counter += 1
	stemp.insert(0,'
	stemp.append('
	s.append(stemp)
s.append(add)

arrival = [[0 for i in range(w+1)] for k in range(h+1)]
q = [[1,1]]
arrival[1][1] = 1
while len(q) > 0:
	nextcell = next(s,q[0][0],q[0][1])
	for i in range(len(nextcell)):
		if arrival[nextcell[i][0]][nextcell[i][1]] == 0:
			q.append(nextcell[i])
			arrival[nextcell[i][0]][nextcell[i][1]] = arrival[q[0][0]][q[0][1]] + 1
	q.pop(0)

if arrival[h][w] == 0:
	print(-1)
else:
	print(counter - arrival[h][w])

Solution (Python):
from collections import deque
h, w = map(int, input().split())
s = [input() for _ in range(h)]
def bfs():
    dist = {(0,0): 0}
    que = deque([(0,0)])
    while que:
        i, j = que.popleft()
        for k,l in ((0,1),(1,0),(0,-1),(-1,0)):
            k += i
            l += j
            if 0<=k<h and 0<=l<w and s[k][l]=='.' and (k,l) not in dist:
                dist[k,l] = dist[i,j] + 1
                que.append((k,l))
    return dist
dist = bfs()
if (h-1,w-1) in dist:
    black = sum(line.count('
    print(h*w - black - (dist[h-1,w-1]+1))
else:
    print(-1)

Solution (Python):
def main():
    H, W = [int(x) for x in input().strip().split()]
    tables = []
    white_count = 0
    for i in range(H):
        rows = [str(x) for x in list(input().strip())]
        white_count += rows.count(".")
        tables.append(rows)

    next_cells = [(0, 0, 1)]
    while(next_cells):
        _next_cells = []
        for next_cell in next_cells:
            y, x, step = next_cell
            if y == H-1 and x == W-1: 
                tables[y][x] = str(min(step+1, int(tables[y][x])))
                continue

            for cond, ys, xs in [(y != 0,y-1,x),(y != H-1,y+1,x),(x != 0,y,x-1),(x != W-1,y,x+1)]:
                if cond: 
                    if tables[ys][xs] != "
                        if tables[ys][xs] != ".": 
                            if step+1 < int(tables[ys][xs]):
                                tables[ys][xs] = str(step+1)
                                _next_cells.append((ys, xs, step+1))
                        else: 
                            tables[ys][xs] = str(step+1)
                            _next_cells.append((ys, xs, step+1))
            
        
        next_cells = list(set(_next_cells)) 
    
    if tables[H-1][W-1] == ".":
        return -1
    return white_count - int(tables[H-1][W-1])
    
if __name__ == '__main__':
    print(main())

Solution (Python):
def main():
    H, W = [int(x) for x in input().strip().split()]
    tables = []
    white_count = 0
    for i in range(H):
        rows = [str(x) for x in list(input().strip())]
        white_count += rows.count(".")
        tables.append(rows)

    next_cells = [(0, 0, 1)]
    while(next_cells):
        _next_cells = []
        for next_cell in next_cells:
            y, x, step = next_cell
            if y == H-1 and x == W-1: 
                tables[y][x] = str(min(step+1, int(tables[y][x])))
                continue

            if y != 0: 
                if tables[y-1][x] != "
                    if tables[y-1][x] != ".": 
                        if step+1 < int(tables[y-1][x]):
                            tables[y-1][x] = str(step+1)
                            _next_cells.append((y-1, x, step+1))
                    else: 
                        tables[y-1][x] = str(step+1)
                        _next_cells.append((y-1, x, step+1))

            if y != H-1: 
                if tables[y+1][x] != "
                    if tables[y+1][x] != ".": 
                        if step+1 < int(tables[y+1][x]):
                            tables[y+1][x] = str(step+1)
                            _next_cells.append((y+1, x, step+1))
                    else: 
                        tables[y+1][x] = str(step+1)
                        _next_cells.append((y+1, x, step+1))

            if x != 0: 
                if tables[y][x-1] != "
                    if tables[y][x-1] != ".": 
                        if step+1 < int(tables[y][x-1]):
                            tables[y][x-1] = str(step+1)
                            _next_cells.append((y, x-1, step+1))
                    else: 
                        tables[y][x-1] = str(step+1)
                        _next_cells.append((y, x-1, step+1))

            if x != W-1: 
                if tables[y][x+1] != "
                    if tables[y][x+1] != ".": 
                        if step+1 < int(tables[y][x+1]):
                            tables[y][x+1] = str(step+1)
                            _next_cells.append((y, x+1, step+1))
                    else: 
                        tables[y][x+1] = str(step+1)
                        _next_cells.append((y, x+1, step+1))
        
        next_cells = list(set(_next_cells)) 
    
    if tables[H-1][W-1] == ".":
        return -1
    return white_count - int(tables[H-1][W-1])
    
if __name__ == '__main__':
    print(main())

Solution (Python):
H, W = map(int, input().split())
s = [[i for i in input()]for i in range(H)]
maze = [[False for i in range(W)] for i in range(H)]
bknum = 0
for i in range(H):
    for j in range(W):
        if s[i][j]==".":
            maze[i][j]=True
        else:
            maze[i][j]=False
            bknum += 1


def ncell(i, j):
    tmp = [[i-1,j],[i+1,j],[i,j-1],[i,j+1]]
    out = []
    for p in tmp:
        if 0<=p[0]<H and 0<=p[1]<W and maze[i][j]:
            out.append(p)
    return out

d = [[1000 for j in range(W)] for i in range(H)]
prev = [[-1 for j in range(W)] for i in range(H)]
d[0][0]=0
Q = set()
for i in range(H):
    for j in range(W):
        if maze[i][j]:
            Q.add(i*W+j)
while(len(Q)!=0):
    u = list(Q)[0]
    du = d[u//W][u%W]
    for v in Q:
        if d[v//W][v%W]<du:
            du = d[v//W][v%W]
            u=v
    Q -=set([u])
    for v in ncell(u//W, u%W):
        if d[v[0]][v[1]]>d[u//W][u%W]+1:
            d[v[0]][v[1]]=d[u//W][u%W]+1
            prev[v[0]][v[1]]=u
length=d[H-1][W-1]
if length != 1000:
    print(H*W-length-1-bknum)
else:
    print(-1)

Solution (Python):
H, W = map(int, input().split())
s = [[i for i in input()]for i in range(H)]
maze = [[False for i in range(W)] for i in range(H)]
bknum = 0
for i in range(H):
    for j in range(W):
        if s[i][j]==".":
            maze[i][j]=True
        else:
            maze[i][j]=False
            bknum += 1


def ncell(i, j):
    tmp = [[i-1,j],[i+1,j],[i,j-1],[i,j+1]]
    out = []
    for p in tmp:
        if 0<=p[0]<H and 0<=p[1]<W and maze[i][j]:
            out.append(p)
    return out

d = [[1000 for j in range(W)] for i in range(H)]
prev = [[-1 for j in range(W)] for i in range(H)]
d[0][0]=0
Q = set()
for i in range(H):
    for j in range(W):
        if maze[i][j]:
            Q.add(i*W+j)
while(len(Q)!=0):
    u = list(Q)[0]
    du = d[u//W][u%W]
    for v in Q:
        if d[v//W][v%W]<du:
            du = d[v//W][v%W]
            u=v
    Q -=set([u])
    for v in ncell(u//W, u%W):
        if d[v[0]][v[1]]>d[u//W][u%W]+1:
            d[v[0]][v[1]]=d[u//W][u%W]+1
            prev[v[0]][v[1]]=u
length=d[H-1][W-1]
if length != 1000:
    print(H*W-length-1-bknum)
else:
    print(-1)

Solution (Python):
from collections import deque

def bfs(H, W, S):
    visited = [[False]*(W+2) for _ in range(H+2)]
    visited[1][1] = True
    unvisited = deque([(1,1)])
    dist = 1
    while unvisited:
        dist += 1
        un = deque()
        for x, y in unvisited:
            for t1, t2 in zip([-1,+1,0,0],[0,0,-1,1]):
                dx = x + t1
                dy = y + t2
                if S[dy][dx] != '
                    if dy == H and dx == W:
                        return dist
                    un.append((dx,dy))
                    visited[dy][dx] = True
        unvisited = un

    return -1

def main():
    H, W = map(int, input().split())
    S = ['
    S.insert(0,'
    S.append('
    step = bfs(H,W,S)
    white = sum([n.count('.') for n in S])
    if step == -1:
        print(step)
    else:
        print(white - step)

if __name__ == "__main__":
    main()

Solution (Python):
from collections import deque

H,W=map(int,input().split())
M=[input() for _ in range(H)]
dist=0
visited=[[False]*W for _ in range(H)]
q=deque([(0,0,0)])
visited[0][0]=True
while q:
    x,y,dist=q.popleft()
    for i in range(4):
        nx,ny=x+[-1,0,1,0][i],y+[0,-1,0,1][i]
        if 0<=nx and nx<W and 0<=ny and ny<H and M[ny][nx]=='.' and not visited[ny][nx]:
            q.append((nx,ny,dist+1))
            visited[ny][nx]=True
    if x==W-1 and y==H-1:
        c=0
        for m in M:
            c+=m.count('.')
        print(c-dist-1)
        exit()
print(-1)

Solution (Python):
import heapq

def change(i):
    if i == ".":
        return 500
    return -1

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

maze = []

for _ in range(h):
    maze.append([change(i) for i in input()])

B = 0
for _ in maze:
    B += _.count(-1)

l = []

maze[0][0] = 1
heapq.heappush(l, (1, 0, 0))
while len(l) > 0:
    S, H, W = heapq.heappop(l)
    if (H, W) == (h-1, w-1):
        break
    
    for i in range(-1, 2, 2):
        y = H+i
        if y >= 0 and y < h:
            if maze[H][W]+1 < maze[y][W]:
                maze[y][W] = maze[H][W]+1
                heapq.heappush(l, (maze[H][W]-1+h-y+w-W,y, W))
    for i in range(-1, 2, 2):
        x = W+i
        if x >= 0 and x < w:
            if maze[H][W]+1 < maze[H][x]:
                maze[H][x] = maze[H][W]+1
                heapq.heappush(l, (maze[H][W]-1+h-H+w-x, H, x))

if maze[-1][-1] == 500:
    print(-1)
else:
    print(h*w-B-maze[-1][-1])

Solution (Python):
from collections import deque

def main():
    H, W = map(int, input().split())
    S = tuple(input() for _ in [0] * H)

    maze = ['
    dot = 0
    for i, s in enumerate(S):
        dot += s.count('.')
        maze[i+1] = '

    before = deque([(1, 1)])
    step = [[None for i in range(W+2)] for j in range(H+2)]
    step[1][1] = 0
    while len(before) > 0:
        x, y = before.popleft()
        if (x, y) == (W, H):
            print(dot - (step[y][x] + 1))
            break
        for i, j in ((1, 0), (-1, 0), (0, 1), (0, -1)):
            if '.' in maze[y+j][x+i] and step[y+j][x+i] == None:
                before.append((x+i, y+j))
                step[y+j][x+i] = step[y][x] + 1
    else:
        print(-1)

main()

Solution (Python):


from collections import deque
def document_it(func):
    def new_function(*args,**kwargs):
        print('Running function:', func.__name__)
        print('Positional arguments:', args)
        print('Kewword arguments:', kwargs)
        result = func(*args,**kwargs)
        print('Result:', result)
        return result
    return new_function




def nb(i,j,H,W):
    ans = []
    a = i+1
    b = i-1
    c = j+1
    d = j-1
    if a >= 0 and a <= H-1:
        ans.append((a,j))
    if b >= 0 and b <= H-1:
        ans.append((b,j))
    if c >= 0 and c <= W-1:
        ans.append((i,c))
    if d >= 0 and d <= W-1:
        ans.append((i,d))
    return ans
        

def e():
    
    dist={}
    white = {}
    wtotal = 0
    H,W = map(int,input().split())
    for i in range(H):
        row = input()
        for j in range(W):
            dist[(i,j)] = -1
            if row[j] == '.':
                white[(i,j)] = True
                wtotal += 1
            else:
                white[(i,j)] = False
    
    
    
    link = {}
    for i in range(H):
        for j in range(W):
            link[(i,j)] = []
            if not white[(i,j)]:
                continue
            else:
                nlist = nb(i,j,H,W)
                for p in nlist:
                    if white[p]:
                        link[(i,j)].append(p)
    
    q = deque()
    dist[(0,0)] = 1
    q.append((0,0))
    while q:
        v = q.popleft()
        for w in link[v]:
            if dist[w] == -1:
                dist[w] = dist[v] + 1
                q.append(w)
                
    if dist[(H-1,W-1)] != -1:
        ans = wtotal - dist[(H-1,W-1)]
    else:
        ans = -1
    
    
                    
    print(ans)


if __name__ == '__main__':
    e()

Solution (Python):
from Queue import Queue
d = [0, 1, 0, -1]
h, w = map(int, raw_input().split())
m = list()
m.append(["
for _ in xrange(h):
    m.append(["
m.append(["
dat = len(filter(lambda x:x==".", [i for j in m for i in j]))

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

while not q.empty():
    xy = q.get()
    if not m[xy[0]][xy[1]] == ".":
        continue
    m[xy[0]][xy[1]] = xy[2]
    for i in xrange(4):
        e = (xy[0]+d[i], xy[1]+d[i+1&3], xy[2]+1)
        if m[xy[0]+d[i]][xy[1]+d[i+1&3]] == ".":
            q.put(e)

try:
    print dat-m[h][w]
except:
    print -1

Solution (Python):
H,W = map(int,input().split())
grid = [input() for x in range(H)]

num_black = 0
for i in range(H):
    num_black += grid[i].count("

dx = [0,0,1,-1,1,1,-1,-1]
dy = [1,-1,0,0,1,-1,1,-1]
dist = [[-1 for x in range(W)] for x in range(H)]

q = []
dist[0][0] = 0
q.append((0,0))

while len(q) != 0:
    current = q[0]
    del q[0]
    x = current[0]
    y = current[1]
    for i in range(4):
        nx = x + dx[i]
        ny = y + dy[i]

        if nx < 0 or ny < 0:
            continue
        if nx >= H or ny >= W:
            continue
        if dist[nx][ny] != -1:
            continue
        if grid[nx][ny] == "
            continue
        dist[nx][ny] = dist[x][y] + 1
        q.append((nx,ny))

if dist[H-1][W-1] == -1:
    print(-1)
else:
    print(H * W - dist[H-1][W-1] - num_black - 1)

Solution (Python):




R,C = [int(i) for i in input().split()]




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

count=0 

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):
from collections import deque
H,W=map(int,raw_input().split())
c=[]
for i in range(H):
	s=list(raw_input())
	for j in s:
		if j=="
			c.append(1)
		else:
			c.append(0)


nl=[ [] for i in range(H*W)]

p0=[-1,1,W]
p1=[-W,1,W]
p2=[-W,-1,W]
p3=[-W,-1,1]
p4=[-W,-1,1,W]
for i in range(H*W):
	if c[i]==0:
		if i==0:
			if c[i+1]==0:nl[i].append(i+1)
			if c[i+W]==0:nl[i].append(i+W)
		elif i==W-1:
			if c[i-1]==0:nl[i].append(i-1)
			if c[i+W]==0:nl[i].append(i+W)
		elif i==W*(H-1):
			if c[i-W]==0:nl[i].append(i-W)
			if c[i+1]==0:nl[i].append(i+1)		
		elif i==W*H-1:
			if c[i-W]==0:nl[i].append(i-W)
			if c[i-1]==0:nl[i].append(i-1)
		elif i<W-1:
			for j in p0:
				if c[i+j]==0:nl[i].append(i+j)			
		elif i%W==0:
			for j in p1:
				if c[i+j]==0:nl[i].append(i+j)	
		elif i%W==W-1:
			for j in p2:
				if c[i+j]==0:nl[i].append(i+j)
		elif i>W*(H-1):
			for j in p3:
				if c[i+j]==0:nl[i].append(i+j)
		else:
			for j in p4:
				if c[i+j]==0:nl[i].append(i+j)


V=[ None for i in range(H*W)]
d=[ float("inf") for i in range(H*W) ]

def bfs(start):
	q = deque([]) 
	V[start]=1
	d[start]=0
	q.append(start)

	while len(q)!=0:
		v=q.popleft()
		for i in nl[v]:
			if V[i] is None:
				V[i]=1
				q.append(i)
				d[i]=d[v]+1

bfs(0)

if V[H*W-1] is None:
	print -1
else:
	print H*W-(d[H*W-1]+1)-sum(c)

Solution (Python):
from collections import deque

def bfs(H,W,S):
	V = [[False for i in range(W)] for j in range(H)]
	qu = deque([(0,0,1)])
	V[0][0] = True
	while(qu):
		p,q,r = qu.popleft()
		S[p][q] = '
		for d in [(-1,0), (0,-1), (1,0), (0,1)]:
			s = p+d[0]
			t = q+d[1]
			if s < 0 or t < 0 or s >= H or t >= W:
				continue
			if s == (H-1) and t == (W-1) and S[s][t] == '.':
				return r+1
			if S[s][t] == '.' and V[s][t] == False:
				V[s][t] = True
				qu.append((s,t,r+1))
	return -1

H, W = list(map(int, input().split()))
S = []
cnt = 0
for i in range(H):
	a = str(input())
	tmp = []
	for i in a:
		if (i == '.'):
			cnt += 1
		tmp.append(i)
	S.append(tmp)

step = bfs(H, W, S)

if (step != -1):
	print(cnt - step)
else:
	print(step)

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


D = [[H*W]*W for _ in range(H)]
D[0][0] = 0
Q = [(0,0)]
while len(Q) > 0:
	cx,cy = Q.pop(0)
	for dx,dy in [(-1,0),(1,0),(0,-1),(0,1)]:
		x = cx + dx
		y = cy + dy
		if 0 <= x < W and 0 <= y < H and S[y][x] == "." and D[cy][cx] + 1 < D[y][x]: 
			D[y][x] = D[cy][cx] + 1
			Q.append((x, y))

if D[H-1][W-1] < H*W:
	print sum([s.count(".") for s in S]) - D[H-1][W-1] - 1
else:
	print -1

Solution (Python):
from collections import deque


def main():
    """
    ゲームの開始時点ではマス (1,1)
    上下左右の 4 方向のいずれかに 1 マスだけ動かすことを繰り返す
    白いマスだけを通って (H,W) にたどり着けばゲームクリア

    マス (i,j) 最初
    白で塗られている場合 .
    黒で塗られている場合 

    いくつかの白いマス目の色を黒に変えることができる
    ただし, マス (1,1) と (H,W) の色を変えることはできず
    -> ルートの変更は不可能

    ゲームをクリアしたとき, ゲームの開始前にマスの色を変えた回数がすぬけ君のスコアとなる
    最大のスコアを求めなさい
    → 最短距離を求め,必要ない白マスを黒に変えれば高スコア(BFS?)
    → 経路を覚えておかないといけない
    """
    H, W = map(int, input().split())
    S = [
        input()
        for _ in range(H)
    ]

    bfs(S, H, W)


def bfs(S, H, W):
    
    q = deque([(0, 0, 0)])
    visited = [
        [False] * W
        for _ in range(H)
    ]
    visited[0][0] = True

    goal = False
    dist = 0
    while q:
        x, y, dist = q.popleft()
        if (x, y) == (W-1, H-1):
            goal = True
            break

        for dx in (-1, 1):
            nx = x+dx
            if 0 <= nx < W:
                if S[y][nx] == "." and not visited[y][nx]:
                    q.append((nx, y, dist+1))
                    visited[y][nx] = True
        for dy in (-1, 1):
            ny = y+dy
            if 0 <= ny < H:
                if S[ny][x] == "." and not visited[ny][x]:
                    q.append((x, ny, dist+1))
                    visited[ny][x] = True

    if goal:
        w_count = 0
        for s in S:
            w_count += s.count(".")
        
        print(w_count - dist - 1)
    else:
        print(-1)


if __name__ == '__main__':
    main()

Solution (Python):
import queue
H, W = list(map(int, input().split()))
S = list()
for i in range(H) :
    S.append(input())
dist = [[3000 for j in range(W)] for i in range(H)]
dx = [-1, 0, 1, 0]
dy = [0, -1, 0, 1]
q = queue.Queue()
dist[0][0] = 0
q.put([0, 0])
while q.empty() == False:
    x, y = q.get()
    for i in range(4) :
        nx = x + dx[i]
        ny = y + dy[i]
        if nx >= 0 and ny >= 0 and nx < W and ny < H :
            if S[ny][nx] == '.' and dist[ny][nx] > dist[y][x] + 1 :
                dist[ny][nx] = dist[y][x] + 1
                q.put([nx, ny])
cnt = 0
for i in range(H) :
    for j in range(W) :
        if S[i][j] == '.' :
            cnt += 1
print(-1 if dist[H-1][W-1] == 3000 else cnt - dist[H-1][W-1] - 1)

Solution (Python):
H, W = map(int, input().split())
lst = []
for _ in range(H):
    lst.append(input())

A = []
whites = 0

for i in range(H):
    row_i = []
    for j in range(W):
        if lst[i][j] == '.':
            whites += 1
            tmp = []
            if i != 0:
                if lst[i-1][j] == '.':
                    tmp.append((i-1, j))
            if j != 0:
                if lst[i][j-1] == '.':
                    tmp.append((i, j-1))
            if i != H-1:
                if lst[i+1][j] == '.':
                    tmp.append((i+1, j))
            if j != W-1:
                if lst[i][j+1] == '.':
                    tmp.append((i, j+1))
            row_i.append(tmp)
        else:
            row_i.append([])
    A.append(row_i)

Q = [(0, 0, 0)]
visited = []

flag = False

while len(Q) != 0:
    x, y, path_length = Q.pop(0)
    if (x,y) == (H-1, W-1):
        flag = True
        break
    if (x,y) not in visited:
        visited.append((x,y))
        Q += [(i, j, path_length + 1) for (i, j) in A[x][y]]

if flag:
    print(whites - path_length - 1)
else:
    print(-1)

Solution (Python):
from collections import deque

nNM = []
nNM = input().rstrip().split(' ')

nH = int(nNM[0])
nW = int(nNM[1])
nTmp = [0 for i in range(nW)]

graph = {}
kyori = {}
checked = {}

nWallCnt = 0

for i in range(nH):
    nTmp=input()

    
    for i2 in range(nW):


        nPoi=('%d-%d' %(i,i2))
        graph[nPoi] = []
        kyori[nPoi] = float("inf")
        checked[nPoi] = 0
        
        if i==0 and i2==0:
            nStart = ('%d-%d' %(0,0))
            kyori[nPoi] = int (0)

        if i==nH - 1 and i2==nW - 1:
            nGoal = ('%d-%d' %(nH - 1, nW - 1))

        elif nTmp[i2]=='
            nWall = ('%d-%d' %(i,i2))
            nWallCnt += 1
            checked[nPoi] = 1

        else:
            if i - 1 >= 0:
                graph[nPoi].append('%d-%d' %(i - 1, i2))

            if i + 1 < nH :
                graph[nPoi].append('%d-%d' %(i + 1 , i2))

            if i2 - 1 >= 0:
                graph[nPoi].append('%d-%d' %(i , i2 - 1))

            if i2 + 1 < nW:
                graph[nPoi].append('%d-%d' %(i , i2 + 1))
        


root_queue = deque()
root_queue += graph[nStart]
nCount = len(graph[nStart])

for i in range(nCount):
    kyori[(graph[nStart][i])] = 1


nFlag = 0


while root_queue:
    nPoi2 = root_queue.popleft()

    if checked[nPoi2] == 0:
        if nPoi2 == nGoal:
            nFlag = 1
            break
        else:
            root_queue += graph[nPoi2]
            for i in range(len(graph[nPoi2])):
                nTmpCount = kyori[nPoi2] + 1
                if kyori[(graph[nPoi2][i])] > nTmpCount:
                    kyori[(graph[nPoi2][i])] = nTmpCount
            checked[nPoi2] = 1


if nFlag == 0:
    print('-1')
else:
    nTmp = kyori[nGoal] + 1
    nTotal = nH * nW
    nAns = nTotal - (nTmp + nWallCnt )
    print(nAns)

Solution (Python):
import queue
H, W = list(map(int, input().split()))
S = list()
for i in range(H) :
    t = input()
    S.append(t)
dist = [[3000 for j in range(W)] for i in range(H)]
dx = [-1, 0, 1, 0]
dy = [0, -1, 0, 1]
q = queue.Queue()
dist[0][0] = 0
q.put([0, 0])
while q.empty() == False:
    x, y = q.get()
    for i in range(4) :
        nx = x + dx[i]
        ny = y + dy[i]
        if nx >= 0 and ny >= 0 and nx < W and ny < H :
            if S[ny][nx] == '.' and dist[ny][nx] > dist[y][x] + 1 :
                dist[ny][nx] = dist[y][x] + 1
                q.put([nx, ny])
cnt = 0
for i in range(H) :
    for j in range(W) :
        if S[i][j] == '.' :
            cnt += 1
print(-1 if dist[H-1][W-1] == 3000 else cnt - dist[H-1][W-1] - 1)

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

   b = 0
   for i in range(H):
      for j in range(W):
         if s[i][j] == "
            b = b+1

   flag = [[0 for _ in range(W)] for _ in range(H)]
   Q = []
   Q.append((0,0,0))
   flag[0][0] = 1

   while Q != []:
      v = Q.pop(0)
      if v[0:2] == (H-1,W-1):
         return H*W - b - v[2] -1
      else:
         if v[0] != 0: 
            if (flag[v[0]-1][v[1]]==0)and(s[v[0]-1][v[1]]=="."):
               Q.append((v[0]-1, v[1],v[2]+1))
               flag[v[0]-1][v[1]] = 1
         if v[0] != H-1: 
            if (flag[v[0]+1][v[1]]==0)and(s[v[0]+1][v[1]]=="."):
               Q.append((v[0]+1, v[1], v[2]+1))
               flag[v[0]+1][v[1]] = 1
         if v[1] != 0: 
            if (flag[v[0]][v[1]-1]==0)and(s[v[0]][v[1]-1]=="."):
               Q.append((v[0], v[1]-1, v[2]+1))
               flag[v[0]][v[1]-1] = 1
         if v[1] != W-1: 
            if (flag[v[0]][v[1]+1]==0)and(s[v[0]][v[1]+1]=="."):
               Q.append((v[0], v[1]+1, v[2]+1))
               flag[v[0]][v[1]+1] = 1
   return -1

print(fanc())

Solution (Python):
from collections import deque

def bfs(field):
    q = deque([(0, 0, 1)])
    visited = [[False] * w for _ in range(h)]
    while q:
        i, j, d = q.popleft()
        if i == h - 1 and j == w - 1:
            return d
        if visited[i][j]:
            continue
        visited[i][j] = True
        if i > 0 and field[i - 1][j] == ".":
            q.append((i - 1, j, d + 1))
        if i < h - 1 and field[i + 1][j] == ".":
            q.append((i + 1, j, d + 1))
        if j > 0 and field[i][j - 1] == ".":
            q.append((i, j - 1, d + 1))
        if j < w - 1 and field[i][j + 1] == ".":
            q.append((i, j + 1, d + 1))
        
    else:
        return -1

h, w = map(int, input().split())
field = [input() for _ in range(h)]
b = sum(r.count("
res = bfs(field)
if res == -1:
    print(-1)
else:
    print(h * w - res - b)

Solution (Python):
import sys
import Queue

sys.setrecursionlimit(1000000)

def s(m, v, q):
    if q.empty(): return -1
    k, i, j = q.get()
    if i == len(m) - 1 and j == len(m[i]) - 1: return k
    if i > 0 and m[i - 1][j] == '.' and (i - 1, j) not in v:
        q.put((k + 1, i - 1, j))
        v.add((i - 1, j))
    if i < len(m) - 1 and m[i + 1][j] == '.' and (i + 1, j) not in v:
        q.put((k + 1, i + 1, j))
        v.add((i + 1, j))
    if j > 0 and m[i][j - 1] == '.' and (i, j - 1) not in v:
        q.put((k + 1, i, j - 1))
        v.add((i, j - 1))
    if j < len(m[i]) - 1 and m[i][j + 1] == '.' and (i, j + 1) not in v:
        q.put((k + 1, i, j + 1))
        v.add((i, j + 1))
    return s(m, v, q)
     
h, w = map(int, raw_input().split())
m = [raw_input() for _ in range(h)]
q = Queue.PriorityQueue()
q.put((1, 0, 0))
v = set((0, 0))
c = s(m, v, q)
if c == -1: print -1
else: print h * w - c - sum([r.count('