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


def bfs(maze, sy, sx):
    gy, gx = H - 1, W - 1
    q = [[sy, sx]]
    visited[sy][sx] = 1
    
    now = 0
    while q:
      y, x = q.pop(0)
      if (y, x) == (gy, gx):
        return visited[y][x]
      for j, k in ([1, 0], [-1, 0], [0, 1], [0, -1]):
        new_y, new_x = y + j, x + k 
        if (0 <= new_y <= H - 1) and (0 <= new_x <= W - 1):
          if maze[new_y][new_x] == "." and visited[new_y][new_x] > 10 ** 5:
            visited[new_y][new_x] = visited[y][x] + 1
            q.append([new_y, new_x])
    return 0

          
if __name__ == "__main__":
    H, W = map(int, input().split())
    maze = [[0] * W for i in range(H)]
    count = 0
    for i in range(H):
      s = str(input())
      for j in range(W):
        maze[i][j] = s[j]
        if s[j] == ".":
          count += 1
    visited = [[float("inf")] * W for j in range(H)]
    ans = bfs(maze, 0, 0)
    if ans == 0:
      print(-1)
    else:
      print(count - ans)

Solution (Python):
from collections import deque
h,w = map(int,input().split())
map = [list(input()) for _ in range(h)]
dx = (1, 0, -1, 0)
dy = (0, 1, 0, -1)

def bfs():
    q = deque([])
    q.append((0,0))
    d = [([-1]*w)for _ in range(h)]

    d[0][0] =  ~-sum(1 for i in range(h) for j in range(w) if map[i][j] == ".")

    while q:
        x,y = q.popleft()
        if (x,y) == (h-1,w-1):
            break
        for i in range(4):
            nx = x+dx[i]
            ny = y+dy[i]
            if 0<=nx<h and 0<=ny<w and d[nx][ny]==-1 and map[nx][ny]!="
                q.append((nx,ny))
                d[nx][ny]= d[x][y] -1
    return d[h-1][w-1]
print(bfs())

Solution (Python):
dir = [[1, 0], [0, 1], [-1, 0], [0, -1]]
def main():
  H, W = map(int, input().split())
  d = [[-1] *W for _ in range(H)]
  S = []
  for i in range(H):
    S.append(list(str(input())))
  ans =  -1
  que = [[0, 0]]
  d[0][0] = 1
  while len(que)>0:
    now = que.pop(0)
    for move in dir:
      nex = [now[0] + move[0], now[1] + move[1]]
      if 0 <= nex[0] < H and 0 <= nex[1] < W and S[nex[0]][nex[1]] == '.' and d[nex[0]][nex[1]] == -1:
        d[nex[0]][nex[1]] = d[now[0]][now[1]] + 1
        if nex[0] == H-1 and nex[1] == W-1:
          ans = d[H-1][W-1]
          break
        else:
          que.append(nex)
  if ans == -1:
    print(ans)
  else:
    num = 0
    for i in range(H):
      for j in range(W):
        if S[i][j] == '.':
          num += 1
    print(num - ans)
if __name__ == "__main__":
  main()

Solution (Python):
import sys
from collections import deque
H, W = map(int, input().split())
s = [input() for _ in range(H)]
dist = [[-1] * W for _ in range(H)]
dist[0][0] = 1
Q = deque()
Q.append([0, 0])
c = 0
for l in s:
    c += l.count('.')

yudlr = [1, -1, 0, 0]
xudlr = [0, 0, -1, 1]

while len(Q) > 0:
    q = Q.popleft()
    y, x = q[0], q[1]
    for i in range(4):
        y1 = y + yudlr[i]
        x1 = x + xudlr[i]
        if y1 < 0 or y1 >= H or x1 < 0 or x1 >= W:
            continue
        if s[y1][x1] == '
            continue
        if dist[y1][x1] != -1:
            continue
        dist[y1][x1] = dist[y][x] + 1
        if y1 == H - 1 and x1 == W - 1:
            print(c - dist[y1][x1])
            sys.exit()
        Q.append([y1, x1])

print('-1')

Solution (Python):
from collections import deque
m=[[1,0],[-1,0],[0,1],[0,-1]]
h,w=map(int,input().split())
l=list()
l.append('
p=0
for i in range(h):
    j=input()
    p+=j.count('
    l.append('
l.append('
q=deque([[1,1]])
s=[[-1 for j in i] for i in l]
s[1][1]=1
while len(q)>0:
    x,y=q.popleft()
    for i,j in m:
        if l[x+i][y+j]=='.' and s[x+i][y+j]==-1:
            q.append([x+i,y+j])
            s[x+i][y+j]=s[x][y]+1
    if s[h][w]!=-1:
        break
if s[h][w]!=-1:
  print(h*w-p-s[h][w]) 
else:
  print(-1)

Solution (Python):
from collections import deque
m=[[1,0],[-1,0],[0,1],[0,-1]]
h,w=map(int,input().split())
l=list()
l.append('
p=0
for i in range(h):
    j=input()
    p+=j.count('
    l.append('
l.append('
q=deque([[1,1]])
s=[[-1 for j in i] for i in l]
s[1][1]=1
while len(q)>0:
    x,y=q.popleft()
    for i,j in m:
        if l[x+i][y+j]=='.' and s[x+i][y+j]==-1:
            q.append([x+i,y+j])
            s[x+i][y+j]=s[x][y]+1
    if s[h][w]!=-1:
        break
print(h*w-p-s[h][w] if s[h][w]!=-1 else -1)

Solution (Python):
from collections import deque, Counter


def bfs():
    dist = [[float("inf")] * W for i in range(H)]
    dist[Sy][Sx] = 0

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

    que = deque([])
    que.append((Sy, Sx))

    while que:
        p = que.popleft()
        y = p[0]
        x = p[1]

        if y == Gy and x == Gx:
            break

        for i in range(4):
            ny = y + dy[i]
            nx = x + dx[i]

            if 0 <= ny < H and 0 <= nx < W and Map[ny][nx] != "
                dist[ny][nx] = dist[y][x] + 1
                que.append((ny, nx))

    return dist



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


Sy, Sx = 0, 0
Gy, Gx = H - 1, W - 1


sharp = 0
for l in Map:
    for s in l:
        if s == "
            sharp += 1


dist = bfs()


if dist[Gy][Gx] == float("inf"):
    print(-1)
    exit()


c = []
for l in dist:
    c += l

ans = H * W - (sharp + dist[Gy][Gx] + 1)

print(ans)

Solution (Python):
from collections import deque

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

stack = deque([(0, 0)])
d = [[-1]*W for _ in range(H)]
d[0][0] = 0

while stack:
  nowx, nowy = stack.popleft()
  if nowx >= 1:
    if s[nowy][nowx-1]=='.' and d[nowy][nowx-1]==-1:
      d[nowy][nowx-1] = d[nowy][nowx] + 1
      stack.append((nowx-1, nowy))
  if nowx <= W-2:
    if s[nowy][nowx+1]=='.' and d[nowy][nowx+1]==-1:
      d[nowy][nowx+1] = d[nowy][nowx] + 1
      stack.append((nowx+1, nowy))
  if nowy >= 1:
    if s[nowy-1][nowx]=='.' and d[nowy-1][nowx]==-1:
      d[nowy-1][nowx] = d[nowy][nowx] + 1
      stack.append((nowx, nowy-1))
  if nowy <= H-2:
    if s[nowy+1][nowx]=='.' and d[nowy+1][nowx]==-1:
      d[nowy+1][nowx] = d[nowy][nowx] + 1
      stack.append((nowx, nowy+1))

if d[H-1][W-1] == -1:
  print(-1)
  exit()
  
white = 0
for si in s:
  for sii in si:
    if sii == '.':
      white += 1
print(white-d[H-1][W-1]-1)

Solution (Python):
H, W = map(int, input().split())
sh, sw = 1,1
gh, gw = H,W

S = [0]*(H+2)
S[0] = '*'*(W+2)
S[H+1] = '*'*(W+2)
white = 0
for h in range(1,H+1):
    S[h] = '*' + input() + '*'
    white += S[h].count('.')

visited = [[False]*(W+2) for _ in range(H+2)]
dh = [0,1,0,-1]
dw = [1,0,-1,0]

from collections import deque
d = deque()

visited[sh][sw]=True
d.append((sh,sw,1))

while len(d)>0:
    h,w,cnt = d.popleft()
    for i in range(4):
        h0 = h+dh[i]
        w0 = w+dw[i]
        if (h0,w0) == (gh,gw):
            print(white-cnt-1)
            break
        if S[h0][w0]=='.' and visited[h0][w0]==False:
            visited[h0][w0]=True
            d.append((h0,w0,cnt+1))
    else:
        continue
    break
else:
    print(-1)

Solution (Python):
import queue
import itertools
H, W = map(int, input().split())
s = [list(input()) for _ in range(H)]
G = [[] for _ in range(H * W)]

for i in range(H * W):
    u = i // W
    v = i % W
    
    if s[u][v] == '
        continue
    if u-1 >= 0 :
        if s[u-1][v] == '.':
            G[i].append(i-W)
    if v-1 >= 0:
        if s[u][v-1] == '.':
            G[i].append(i-1)
    if v+1 < W:
        if s[u][v+1] == '.':
            G[i].append(i+1)
    if u+1 < H:
        if s[u+1][v] == '.':
            G[i].append(i+W)

def dfs(Graph, N, start):
    q = queue.Queue()
    dist = [-1] * N
    dist[start] = 0
    q.put(start)

    while not q.empty():
        v = q.get()
        for u in G[v]:
            if dist[u] != -1:
                continue
            dist[u] = dist[v] + 1
            q.put(u)

    return dist
dist = dfs(G, H*W, 0)

if dist[-1] == -1:
    print(-1)
    exit()
count = list(itertools.chain.from_iterable(s)).count('
print(H*W - (dist[-1] + 1) - count)

Solution (Python):
def resolve():
    '''
    code here
    '''
    import collections
    H, W = [int(item) for item in input().split()]
    grid = [[item for item in input()] for _ in range(H)]

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

    que = collections.deque([[0, 0, 1]])
    fp[0][0] = 1
    next_y_x = [[0, 1], [1, 0], [-1, 0], [0, -1]]
    is_found = False

    while que:
        temp = que.popleft()

        if temp[0] == H-1 and temp[1] == W-1:
            pass_num = temp[2]
            que = False
            is_found = True
        else:
            for dy, dx in next_y_x:
                ny = temp[0] + dy
                nx = temp[1] + dx

                if 0 <= ny <= H-1 and 0 <= nx <= W-1:
                    if grid[ny][nx] == '.' and fp[ny][nx] == -1:
                        que.append([ny, nx, temp[2]+1])
                        fp[ny][nx] = temp[2] + 1

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

    if is_found:
        print(H*W - black_cnt - pass_num)
    else:
        print(-1)


if __name__ == "__main__":
    resolve()

Solution (Python):
from collections import deque
def BFS(x,y,l):
   que=deque([(x,y)])
   visited=[[0]*W for i in range(H)]
   visited[0][0]=1
   while que:
      x,y=que.popleft()
      node=visited[y][x]
      if 0 < x:
         if l[y][x-1] != "
            visited[y][x-1]+=node+1
            que.append((x-1,y))
      if 0 < y:
         if l[y-1][x] != "
            visited[y-1][x]+=node+1
            que.append((x,y-1))
      if x < W-1:
         if l[y][x+1] != "
            visited[y][x+1]+=node+1
            que.append((x+1,y))
      if y < H-1:
         if l[y+1][x] != "
            visited[y+1][x]+=node+1
            que.append((x,y+1))
      if x==W-1 and y==H-1:
         return visited[H-1][W-1]
   return -1
H,W=list(map(int,input().split()))
l=[]
tmp2=0
for i in range(H):
   tmp=list(input())
   tmp2+=tmp.count("
   l.append(tmp)
ans=BFS(0,0,l)
if ans != -1 and l[0][0] != "
   print(W*H-ans-tmp2)
else:
   print(-1)

Solution (Python):

from collections import deque

def main():
    H, W = map(int, input().split())
    grid = [None] * H
    white = 0
    for i in range(H):
        grid[i] = input()
        white += grid[i].count('.')

    q = deque()
    q.append([0, 0, 1])
    opt = ((0, 1), (0, -1), (1, 0), (-1, 0))
    visited = set()

    while q:
        y, x, dist = q.popleft()
        if grid[y][x] == '
            continue
        if (y, x) in visited:
            continue
        visited.add((y, x))
        if y == H-1 and x == W-1:
            print(white - dist)
            exit()
        for dy, dx in opt:
            if 0 <= y+dy < H and 0 <= x+dx < W:
                q.append([y+dy, x+dx, dist+1])
    print(-1)

if __name__ == '__main__':
    main()

Solution (Python):
def main():
    from sys import setrecursionlimit, stdin
    from os import environ
    from collections import defaultdict, deque, Counter
    from math import ceil, floor
    from itertools import accumulate, combinations, combinations_with_replacement
    setrecursionlimit(10**6)
    dbg = (lambda *something: print(*something)) if 'TERM_PROGRAM' in environ else lambda *x: 0
    input = lambda: stdin.readline().rstrip()
    LMIIS = lambda: list(map(int,input().split()))
    II = lambda: int(input())
    P = 10**9+7
    INF = 10**9+10

    
    H,W = LMIIS()
    grid = []
    num_black = 0
    for i in range(H):
        line = list(input())
        grid.append(line)
        num_black += line.count('

    
    
    target_queue = deque()
    
    visited = []
    for i in range(H):
        visited.append([-1]*W)
    visited[0][0] = 0
    target_queue.append((0,0))

    while target_queue:
        y,x = target_queue.popleft()
        if y == H-1 and x == W-1:
            break
        next_distance = visited[y][x] + 1
        if y > 0 and grid[y-1][x] != '
            visited[y-1][x] = next_distance
            target_queue.append((y-1,x))
        if y + 1 < H and grid[y+1][x] != '
            visited[y+1][x] = next_distance
            target_queue.append((y+1,x))
        if x > 0 and grid[y][x-1]!= '
            visited[y][x-1] = next_distance
            target_queue.append((y,x-1))
        if x+1 < W and grid[y][x+1]!='
            
            visited[y][x+1] = next_distance
            target_queue.append((y,x+1))
    
    if visited[H-1][W-1] == -1:
        print(-1)
    else:
        print(H*W - num_black - visited[H-1][W-1] -1)
    





        
    
main()

Solution (Python):
from collections import deque

h, w = map(int, input().split())
s = []
for _ in range(h):
    s.append(list(input()))
q = deque([(0, 0)])
s[0][0] = 0
dy = (1, 0, -1, 0)
dx = (0, 1, 0, -1)
blacks = 0
for y in range(h):
    blacks += s[y].count("
while q:
    y, x = q.popleft()
    dist = s[y][x]
    if (y, x) == (h - 1, w - 1):
        break
    for k in range(4):
        ny, nx = y + dy[k], x + dx[k]
        if 0 <= ny < h and 0 <= nx < w:
            if s[ny][nx] == ".":
                s[ny][nx] = dist + 1
                q.append((ny, nx))
if s[h - 1][w - 1] == ".":
    print(-1)
else:
    print(h * w - s[h - 1][w - 1] - blacks - 1)

Solution (Python):
from collections import deque
def main():
    
    
    
    H,W = map(int, input().split())
    sx,sy = 0,0
    road = [[False]*W for _ in range(H)]
    origWhite = 0
    for i in range(H):
        c = input()
        for j in range(W):
            if c[j]=='.':
                road[i][j] = True
                origWhite += 1

    
    
    gx,gy = (H-1),(W-1)
    directions = [(1,0),(0,1),(-1,0),(0,-1)] 
    depth = [[0]*W for _ in range(H)]
    arrived = [[False]*W for _ in range(H)]
    arrived[sx][sy] = True
    que = deque([(sx,sy)]) 
    while que:
        x1,y1 = que.pop()
        for dx,dy in directions:
            x2,y2 = x1+dx,y1+dy
            
            if x2<0 or H<=x2 or y2<0 or W<=y2:
                continue
            
            if not road[x2][y2]:
                continue
            
            if arrived[x2][y2]:
                continue
            que.appendleft((x2,y2))
            arrived[x2][y2] = True
            depth[x2][y2] = depth[x1][y1]+1
            if (x2,y2)==(gx,gy):
                print(origWhite-(depth[x2][y2]+1))
                return
    print(-1)


main()

Solution (Python):
from collections import deque
h,w = map(int,input().split())
maze = []
visited = [[0]*(w) for _ in range(h)]
mx = 0
for _ in range(h):
    s = input()
    mx += s.count('.')
    maze.append(list(s))
sy,sx = 0, 0
gy, gx = h-1, w-1
que = deque([(sy,sx,1)])

while que:
    y,x,c = que.popleft()
    if visited[y][x] != 0:
        continue
    visited[y][x] = c
    for dy,dx in zip((1,-1,0,0), (0,0,1,-1)):
        ny,nx = y+dy, x+dx
        if 0<=ny<h and 0<=nx<w:
            if maze[ny][nx]=='.':
                que.append((ny,nx,c+1))

print(mx-visited[gy][gx] if visited[gy][gx]!=0 else -1)

Solution (Python):
from collections import deque
import sys
H, W = [int(x) for x in input().split()]
s = [list(input()) for _ in range(H)]

white = sum([s[i].count('.') for i in range(H)])
que = deque([(0, 0, 0)])
s[0][0] = '
while que:
    y, x, d = que.popleft()
    if (y, x) == (H - 1, W - 1):
        break
    for dy, dx in [(-1, 0), (1, 0), (0, -1), (0, 1)]:
        ny = y + dy
        nx = x + dx
        if ny < 0 or ny > H - 1 or nx < 0 or nx > W - 1:
            continue
        if s[ny][nx] == '
            continue
        s[ny][nx] = '
        que.append((ny, nx, d + 1))
else:
    print(-1)
    sys.exit()

print(white - d - 1)

Solution (Python):
import sys
import queue

input_methods=['clipboard','file','key']
using_method=0
input_method=input_methods[using_method]

tin=lambda : map(int, input().split())
lin=lambda : list(tin())
mod=1000000007



def main():
	
	h, w = tin()
	
	ol = queue.Queue()
	m=[input() for _ in range(h)]
	b = [[-1]*w for _ in range(h)]
	b[0][0]=1
	ol.put(0)
	while not ol.empty():
		p = ol.get()
		x, y = p//1000, p%1000
		for dx,dy in [(1,0),(-1,0),(0,1),(0,-1)]:
			if x+dx<0 or x+dx>=h or y + dy <0 or y+dy >= w:
				continue
			if m[x+dx][y+dy]=='
				continue
			if b[x+dx][y+dy]>=0:
				continue
			b[x+dx][y+dy]=b[x][y]+1
			ol.put((x+dx)*1000+(y+dy))
	
	if b[-1][-1]==-1:
		return -1
	return sum([s.count('.') for s in m])- b[-1][-1]
		
	
	

isTest=False

def pa(v):
	if isTest:
		print(v)
		
def input_clipboard():
	import clipboard
	input_text=clipboard.get()
	input_l=input_text.splitlines()
	for l in input_l:
		yield l

if __name__ == "__main__":
	if sys.platform =='ios':
		if input_method==input_methods[0]:
			ic=input_clipboard()
			input = lambda : ic.__next__()
		elif input_method==input_methods[1]:
			sys.stdin=open('inputFile.txt')
		else:
			pass
		isTest=True
	else:
		pass
		
			
	ret = main()
	if ret is not None:
		print(ret)

Solution (Python):


import sys
from collections import deque

H, W = map(int, sys.stdin.readline().strip().split())
S = []
start_counter = 0  
for _ in range(H):
    s = list(map(str, sys.stdin.readline()))
    S.append(s)
    for i in s:
        if i == '
            start_counter += 1



fp = [[True] * W for _ in range(H)]  
q = deque()
q.append((0, 0, 1))
fp[0][0] = False

ans_counter = -1
while q:
    ux, uy, counter = q.popleft()
    

    if (ux == W - 1) and (uy == H - 1):
        ans_counter = counter
        break

    for i in [[-1, 0], [1, 0], [0, -1], [0, 1]]:
        vx = ux + i[0]
        vy = uy + i[1]

        if (vx < 0) or (vx >= W):
            continue
        if (vy < 0) or (vy >= H):
            continue
        if fp[vy][vx] is False:
            continue
        if S[vy][vx] == '
            continue

        q.append((vx, vy, counter + 1))
        fp[vy][vx] = False

if ans_counter == -1:
    print(-1)
else:
    print(H * W - start_counter - ans_counter)

Solution (Python):
from collections import deque

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


d=deque()
d.append([0,0,0])
s[0][0]="0"
mx=[1,0,-1,0]
my=[0,1,0,-1]
ans=0

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

while len(d)>0:
    t,y,x=d.popleft()
    if [y,x]==[H-1,W-1]:
        break
    for m in range(4):
        if 0<=y+my[m]<H and 0<=x+mx[m]<W and s[y+my[m]][x+mx[m]]==".":
            d.append([t+1,y+my[m],x+mx[m]])
            s[y+my[m]][x+mx[m]]=str(t+1)

if s[-1][-1]==".":
    print(-1)
else:
    print(white-int(s[-1][-1]))

Solution (Python):
from collections import deque
h, w = map(int, input().split())
s = []
sharp = 0
for i in range(h):
	t = input()
	sharp += t.count("
	s.append(t)

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

visited = [[-1 for i in range(w)] for j in range(h)]
visited[0][0] = 0
d = [(1,0),(0,1),(-1,0),(0,-1)]
while queue:
	i, j = queue.popleft()
	for n, m in d:
		x = i+n
		y = j+m
		if x < 0 or x >= h or y < 0 or y >= w or s[x][y] == "
			continue
		visited[x][y] = visited[i][j] + 1
		queue.append([x,y])
if visited[h-1][w-1] == -1:
	print (-1)
else:
	ans = h*w-visited[h-1][w-1]-1-sharp
	print (ans)

Solution (Python):
R,C = map(int,input().split())
sy,sx = 1,1
gy,gx = R,C
maze = [list(input()) for _ in range(R)]
mx = 0
for m in maze:
  mx += m.count('.')


sx,sy = sx-1, sy-1
gx,gy = gx-1, gy-1

def bfs(R,C,sy,sx,gy,gx,maze):
    from collections import deque
    import numpy as np
    INF = np.inf
    visited = [[INF]*C for _ in range(R)]
    visited[sy][sx] = 0
    que = deque([(sy,sx)])
    while que:
        y,x = que.popleft()
        for i,j in ((1,0),(0,1),(-1,0),(0,-1)):
            ny,nx = y+i, x+j
            if 0<=ny<R and 0<=nx<C:
                if (maze[ny][nx]!='
                    visited[ny][nx] = visited[y][x] + 1
                    que.append((ny,nx))
    if visited[gy][gx]!=INF:
      return visited[gy][gx]
    else:
      return -1

ans = bfs(R,C,sy,sx,gy,gx,maze)
print(mx-ans-1 if ans!=-1 else -1)

Solution (Python):
import sys
from collections import deque
import numpy as np


def main():
    H, W = map(int, input().split())
    s_x = 1
    s_y = 1
    g_x = H
    g_y = W
    dp = - np.ones((H+2, W+2))
    black = 0
    for i in range(1, H+1):
        line = input()
        for j in range(1, W+1):
            if line[j - 1] == '.':
                dp[i][j] = 0
            else:
                black += 1
    queue = deque()
    queue.append((s_x, s_y))
    dp[s_x][s_y] = 1
    while len(queue) != 0:
        now_x, now_y = queue.popleft()
        for x in range(-1, 2):
            for y in range(-1, 2):
                if (x + y) % 2 == 0:
                    continue
                next_x = now_x + x
                next_y = now_y + y
                if dp[next_x][next_y] == 0:
                    dp[next_x][next_y] = dp[now_x][now_y] + 1
                    queue.append((next_x, next_y))
    if dp[g_x][g_y] == -1 or dp[g_x][g_y] == 0:
        print(-1)
    else:
        print(int(H * W - black - dp[g_x][g_y]))




if __name__ == '__main__':
    main()

Solution (Python):
from collections import deque
import sys

sys.setrecursionlimit(10 ** 7)  


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

grid = ['
for _ in range(H):
    grid += ['
grid += ['

cnt = grid.count(".")

move = [1,-1,W+2,-(W+2)]    


start = W+2
goal = (H+1)*(W+2)-2
flg = False
visit = set([start]) 

next_set = deque()
next_set.append((start, 1))

while next_set:    
    x, t = next_set.popleft()     
    for dx in move:
        y = x+dx
        if grid[y] == '
            continue
        if y in visit:
            continue
        if y == goal:
            flg = True
            break
        visit.add(y)   
        next_set.append((y, t + 1))     
    if flg:
        break
if not flg:
    print(-1)
else:
    print(cnt - t )

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

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

inf = 100000
smap = [[inf]*w for _ in range(h)]
smap[0][0] = 1
visited = [[0]*w for _ in range(h)]
visited[0][0] = 1

q = deque()
q.append(0)
q.append(0)

while q:
    y = q.popleft()
    x = q.popleft()
    if x != 0 and s[y][x-1] == "." and visited[y][x-1] == 0:
        lx = x-1
        q.append(y)
        q.append(lx)
        visited[y][lx] = 1
        smap[y][lx] = min(smap[y][lx], smap[y][x] + 1)

    if x != w-1 and s[y][x+1] == "." and visited[y][x+1] == 0:
        rx = x+1
        q.append(y)
        q.append(rx)
        visited[y][rx] = 1
        smap[y][rx] = min(smap[y][rx], smap[y][x] + 1)

    if y != 0 and s[y-1][x] == "." and visited[y-1][x] == 0:
        uy = y-1
        q.append(uy)
        q.append(x)
        visited[uy][x] = 1
        smap[uy][x] = min(smap[uy][x], smap[y][x] + 1)

    if y != h-1 and s[y+1][x] == "." and visited[y+1][x] == 0:
        dy = y+1
        q.append(dy)
        q.append(x)
        visited[dy][x] = 1
        smap[dy][x] = min(smap[dy][x], smap[y][x] + 1)


if smap[h-1][w-1] == inf:
    print(-1)
else:
    print(white-smap[h-1][w-1])

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

sx,sy = 0,0
gx,gy = w-1,h-1

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

mx = [0,0,1,-1]
my = [1,-1,0,0]

queue = deque([[sx,sy]])
visited = [[0]*w for i in range(h)]
visited[sy][sx] = 1

def bfs(queue,visited):
    while queue:
        x,y = queue.popleft()
        for i in range(4):
            nx = x+mx[i]
            ny = y+my[i]
            if 0<=nx<w and 0<=ny<h:
                if visited[ny][nx]!=0:
                    continue
                if map_input[ny][nx]=='
                    continue
                if nx==gx and ny==gy:
                    return visited[y][x]+1
                visited[ny][nx]=visited[y][x]+1
                queue.append([nx,ny])
    return -1

tmp = bfs(queue,visited)
if tmp==-1:
    print(-1)
else:
    ans = h*w-tmp-black
    print(ans)

Solution (Python):
from collections import deque

H, W = map(int, input().split())
score = H * W
S = [[] for i in range(H)]
for i in range(H):
    for s in input():
        if s == "
            score -= 1
        S[i].append(s)


ls = deque([[0, 0]])
dir = [[1,0], [-1,0], [0,1], [0,-1]]
dp = [[float("inf") for i in range(W)] for j in range(H)]
dp[0][0] = 0
while len(ls) > 0:
    x, y = ls.popleft()

    if x == H-1 and y == W-1:
        print(score-dp[H-1][W-1]-1)
        break

    for dx, dy in dir:
        if (x+dx < 0) or (x+dx > H-1) or (y+dy < 0) or (y+dy > W-1):
            continue
        else:
            if S[x+dx][y+dy] == "." and dp[x][y]+1 < dp[x+dx][y+dy]:
                dp[x+dx][y+dy] = dp[x][y] + 1
                ls.append([x+dx, y+dy])

else:
    print(-1)

Solution (Python):
from collections import deque

Y,X=map(int,input().split())

cs=[list(input()) for i in range(Y)]

q=deque()
dist=[[-1 for i in range(X)] for j in range(Y)]
dist[0][0]=0
q.append([0,0])
dx=[-1,1,0,0]
dy=[0,0,-1,1]
while(len(q)!=0):
    v=q.popleft()
    for i in range(4):
        nv =[v[0]+dy[i], v[1]+dx[i]]
        if nv[0] < 0 or nv[0] > Y-1 or nv[1] < 0 or nv[1] > X-1:
            continue
        if dist[nv[0]][nv[1]]!=-1 or cs[nv[0]][nv[1]] == "
            continue
        dist[nv[0]][nv[1]] = dist[v[0]][v[1]]+1
        q.append(nv)
        
black=0
res=dist[Y-1][X-1]
for i in range(Y):
    for j in range(X):
        if cs[i][j]=="
            black+=1
            

if res ==-1:
    print(-1)
else:
    print(Y*X-res-1-black)

Solution (Python):


import sys
readline = sys.stdin.readline

H,W = map(int,readline().split())
grid = [None] * H
white = 0
for i in range(H):
  grid[i] = readline().rstrip()
  white += grid[i].count(".")

from collections import deque
q = deque()

q.append([0,0,1])
visited = set()
cases = ((0,1),(0,-1),(1,0),(-1,0))
while q:
  y,x,dist = q.popleft()
  if grid[y][x] == "
    continue
  if (y,x) in visited:
    continue
  visited.add((y,x))
  if y == H - 1 and x == W - 1:
    print(white - dist)
    break
  for c in cases:
    if 0 <= y + c[0] < H and 0 <= x + c[1] < W:
      q.append([y + c[0],x + c[1],dist + 1])
else:
  print(-1)

Solution (Python):


import heapq as hp
import numpy as np

H,W = map(int,input().split())
S = np.array([list(input()) for _ in range(H)])
S = np.pad(S,1,'constant')
visited = np.zeros_like(S,dtype=np.bool)

dist = np.inf

h = []
hp.heappush(h,(0,1,1))

while h:
  d,x,y = hp.heappop(h)
  if x == H and y == W:
    dist = d
    break
  for dx,dy in [[0,1],[1,0],[-1,0],[0,-1]]:
    nx = x+dx
    ny = y+dy
    if S[nx,ny] == '.' and not visited[nx,ny]:
      visited[nx,ny] = True
      hp.heappush(h,(d+1,nx,ny))
      
if dist == np.inf:
  print(-1)
else:
  print((S == '.').sum() - dist - 1)

Solution (Python):
import sys
from collections import deque

read = sys.stdin.read
readline = sys.stdin.readline
readlines = sys.stdin.readlines
sys.setrecursionlimit(10 ** 9)
INF = 1 << 60


def main():
    H, W = map(int, readline().split())
    G = [0] * H
    for i in range(H):
        G[i] = readline().strip()
    dxdy4 = ((-1, 0), (0, -1), (0, 1), (1, 0))

    dist = [[-1] * W for _ in range(H)]
    dist[0][0] = 1
    queue = deque([(0, 0)])
    while queue:
        x, y = queue.popleft()
        if x == H - 1 and y == W - 1:
            break
        for dx, dy in dxdy4:
            nx, ny = x + dx, y + dy
            if 0 <= nx < H and 0 <= ny < W and G[nx][ny] == '.' and dist[nx][ny] == -1:
                queue.append((nx, ny))
                dist[nx][ny] = dist[x][y] + 1

    if dist[H - 1][W - 1] == -1:
        print(-1)
    else:
        ans = sum(row.count('.') for row in G) - dist[H - 1][W - 1]
        print(ans)

    return


if __name__ == '__main__':
    main()

Solution (Python):
import sys
from collections import deque

read = sys.stdin.read
readline = sys.stdin.readline
readlines = sys.stdin.readlines
sys.setrecursionlimit(10 ** 9)
INF = 1 << 60


def main():
    H, W = map(int, readline().split())
    G = [0] * H
    for i in range(H):
        G[i] = readline().strip()
    dxdy4 = ((-1, 0), (0, -1), (0, 1), (1, 0))

    dist = [[-1] * W for _ in range(H)]
    dist[0][0] = 1
    queue = deque([(0, 0)])
    while queue:
        x, y = queue.popleft()
        if x == H - 1 and y == W - 1:
            break
        for dx, dy in dxdy4:
            nx, ny = x + dx, y + dy
            if 0 <= nx < H and 0 <= ny < W and G[nx][ny] == '.' and dist[nx][ny] == -1:
                queue.append((nx, ny))
                dist[nx][ny] = dist[x][y] + 1

    if dist[H - 1][W - 1] == -1:
        print(-1)
    else:
        blacks = sum(row.count('
        print(H * W - dist[H - 1][W - 1] - blacks)

    return


if __name__ == '__main__':
    main()