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,input().split())
grid=[None]*H
white=0
for i in range(H):
  grid[i]=input()
  white+=grid[i].count(".")
  
from collections import deque
q=deque()
q.append([0,0,0])

seen=[[False for i in range(W)] for j in range(H)]

while q:
  v=q.popleft()
  y=v[0]
  x=v[1]
  p=v[2]
  if grid[y][x]=="
    continue
  if y==H-1 and x==W-1:
    print(white-(p+1))
    break
  seen[y][x]=True
  if y-1>=0:
    q.append([y-1,x,p+1])
  if y+1<H:
    q.append([y+1,x,p+1])
  if x-1>=0:
    q.append([y,x-1,p+1])
  if x+1<W:
    q.append([y,x+1,p+1])
else:
  print(-1)

Solution (Python):
import sys
import copy
input = sys.stdin.readline
H, W = [int(x) for x in input().strip().split()]
masu = [0 for h in range(H+2)]
masu[0] = ['
masu[H+1] = ['
init = 0
for h in range(1, H + 1):
    w = list(input().strip())
    init += w.count('
    masu[h] = ['

def bfs(Q, c, masu):
    nextq = []
    ans = 10 ** 9 +7
    for q in Q:
        h, w = q
        if w == W and h == H:
            return c
        ans = 10 ** 9 + 7
        for ww, hh in [(1, 0), (0, 1), (-1, 0), (0, -1)]:
            if masu[h+hh][w+ww] == '
                continue
            masu[h+hh][w+ww] = '
            nextq.append([h+hh, w+ww])

    if len(nextq):
        ans = min(ans, bfs(nextq, c+1, masu))

    return ans
masu[1][1] = '
ans = bfs([(1, 1)], 1, masu)
if ans == 10 ** 9 + 7:
    print(-1)
else:
    print(H*W-ans-init)

Solution (Python):
from collections import deque

H,W=map(int,input().split())
s=[]

cnt=0
for i in range(H):
    temp=list(input())
    cnt+=temp.count(".")
    s.append(temp)

d=deque([[0,0]])
c=[[10000]*W for i in range(H)]
step=[[-1,0],[0,-1],[1,0],[0,1]]
c[0][0]=1

while d:
    h0,w0=d.popleft()
    for h1,w1 in step:
        h = h0 + h1
        w = w0 + w1
        if h<0 or h>=H or w<0 or w>=W or s[h][w]=="
            continue
        if h==H-1 and w==W-1:
            ans = cnt - c[h0][w0]-1
            print(ans)
            exit()
        c[h][w]=c[h0][w0]+1
        d.append([h,w])
print(-1)

Solution (Python):
import sys
import numpy as np
from heapq import heappop, heappush


def main():
    H, W = map(int, sys.stdin.readline().split())

    grid = np.array([list(sys.stdin.readline().rstrip()) for _ in range(H)])
    grid = np.pad(grid, 1, 'constant')
    
    q = []
    heappush(q, (0, 1, 1))
    visited = set()
    cost = np.full((H + 1, W + 1), np.inf)
    cost[1][1] = 0
    while q:
        c, i, j = heappop(q)
        if (i, j) in visited:
            continue
        visited.add((i, j))
        cost[i][j] = c
        if i == H and j == W:
            break
        for dy, dx in [(1, 0), (0, 1), (-1, 0), (0, -1)]:
            y = i + dy
            x = j + dx
            if grid[y][x] == '.' and not (y, x) in visited:
                heappush(q, (c + 1, y, x))
    

    if cost[H][W] != np.inf:
        ans = int(np.sum(grid == '.') - (cost[H][W] + 1))
    else:
        ans = -1

    print(ans)  

if __name__ == "__main__":
    main()

Solution (Python):
import sys
import numpy as np
from heapq import heappop, heappush


def main():
    H, W = map(int, sys.stdin.readline().split())

    grid = np.array([list(sys.stdin.readline().rstrip()) for _ in range(H)])
    grid = np.pad(grid, 1, 'constant')
    
    q = []
    heappush(q, (0, 1, 1))
    visited = set()
    can_go = False
    while q:
        cost, i, j = heappop(q)
        if (i, j) in visited:
            continue
        visited.add((i, j))
        if i == H and j == W:
            can_go = True
            break
        for dy, dx in [(1, 0), (0, 1), (-1, 0), (0, -1)]:
            y = i + dy
            x = j + dx
            if grid[y][x] == '.' and not (y, x) in visited:
                heappush(q, (cost + 1, y, x))
    
    if can_go:
        ans = np.sum(grid == '.') - (cost + 1)
    else:
        ans = -1

    print(ans)  
if __name__ == "__main__":
    main()

Solution (Python):
import sys
import numpy as np
from heapq import heappop, heappush





def main():
    H, W = map(int, sys.stdin.readline().split())

    grid = np.array([list(sys.stdin.readline().rstrip()) for _ in range(H)], dtype='U')
    grid = np.pad(grid, 1, mode='constant')
    

    
    i = j = 1             
    c = 0                 
    h = (H - 1) + (W - 1) 
    s = c + h             
    q = []                
    heappush(q, (s, c, i, j))
    visited = set()       
    
    
    parent = [[None] * (W + 1) for _ in range(H+1)]

    can_go = False
    while q:
        s, c, i, j = heappop(q)
        if (i, j) in visited:
            continue
        visited.add((i, j))
        if c == s: 
            can_go = True
            break
        for dy, dx in [(1, 0), (0, 1), (-1, 0), (0, -1)]:
            y = i + dy
            x = j + dx
            if grid[y][x] == '.' and not (y, x) in visited:
                parent[y][x] = (i, j)
                h = (H - y) + (W - x)
                s = h + c + 1
                heappush(q, (s, c+1, y, x))
 
    if can_go:
        ans = np.sum(grid == '.') - (c + 1)
    else:
        ans = -1
    print(ans)

    
    
    
    
    
    
    
    
    

if __name__ == "__main__":
    main()

Solution (Python):
import sys
import numpy as np
from heapq import heappop, heappush





def main():
    H, W = map(int, sys.stdin.readline().split())

    grid = np.array([list(sys.stdin.readline().rstrip()) for _ in range(H)], dtype='U')
    grid = np.pad(grid, 1, mode='constant')
    

    
    i = j = 1             
    c = 0                 
    h = (H - 1) + (W - 1) 
    s = c + h             
    q = []                
    heappush(q, (s, c, i, j))
    visited = set()       
    
    
    parent = [[None] * (W + 1) for _ in range(H+1)]

    can_go = False
    while q:
        s, c, i, j = heappop(q)
        if (i, j) in visited:
            continue
        visited.add((i, j))
        if c == s: 
            can_go = True
            break
        for dy, dx in [(1, 0), (0, 1), (-1, 0), (0, -1)]:
            y = i + dy
            x = j + dx
            if grid[y][x] == '.' and not (y, x) in visited:
                parent[y][x] = (i, j)
                h = (H - y) + (W - x)
                s = h + c + 1
                heappush(q, (s, c+1, y, x))
 
    if can_go:
        ans = np.sum(grid == '.') - (c + 1)
    else:
        ans = -1
    print(ans)

    
    
    
    
    
    
    
    
    

if __name__ == "__main__":
    main()

Solution (Python):
import sys
import numpy as np
from heapq import heappop, heappush




def main():
    H, W = map(int, sys.stdin.readline().split())

    grid = np.array([list(sys.stdin.readline().rstrip()) for _ in range(H)], dtype='U')
    grid = np.pad(grid, 1, mode='constant')
    

    
    i = j = 1 
    c = 0     
    h = (H - 1) + (W - 1) 
    s = c + h 
    q = [] 
    heappush(q, (s, c, i, j))
    visited = set() 
    
    
    

    can_go = False
    while q:
        s, c, i, j = heappop(q)
        visited.add((i, j))
        if c == s: 
            can_go = True
            break
        for dy, dx in [(1, 0), (0, 1), (-1, 0), (0, -1)]:
            y = i + dy
            x = j + dx
            if grid[y][x] == '.' and not (y, x) in visited:
                visited.add((y, x))
                
                h = (H - y) + (W - x)
                s = h + c + 1
                heappush(q, (s, c+1, y, x))
 
    if can_go:
        ans = np.sum(grid == '.') - (c + 1)
    else:
        ans = -1
    print(ans)

    
    
    
    
    
    
    
    
    

if __name__ == "__main__":
    main()

Solution (Python):
import sys
import numpy as np
from heapq import heappop, heappush


def main():
    H, W = map(int, sys.stdin.readline().split())

    grid = np.array([list(sys.stdin.readline().rstrip()) for _ in range(H)], dtype='U')
    grid = np.pad(grid, 1, mode='constant')

    can_go = False
    i = j = 1 
    c = 0     
    h = max(H - i, W - j) 
    s = c + h 
    q = [] 
    heappush(q, (s, c, i, j))
    visited = set() 
    

    while q:
        s, c, i, j = heappop(q)
        visited.add((i, j))
        if c == s: 
            can_go = True
            break
        for dy, dx in [(1, 0), (0, 1), (-1, 0), (0, -1)]:
            y = i + dy
            x = j + dx
            if grid[y][x] == '.' and not (y, x) in visited:
                visited.add((y, x))
                h = max(H - y, W - x)
                s = h + c + 1
                heappush(q, (s, c+1, y, x))
 
    if can_go:
        ans = (grid == '.').sum() - (c + 1)
    else:
        ans = -1
    print(ans)


if __name__ == "__main__":
    main()

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


def bfs(graph: list):
    one_steps = ((1, 0), (-1, 0), (0, 1), (0, -1))
    seen = set()
    seen.add((0, 0))
    todo = [(0, 0)]
    cost = {(0, 0): 1}
    while todo:
        x, y = todo.pop(0)
        for dx, dy in one_steps:
            nx, ny = x + dx, y + dy
            if not (0 <= nx < H) or not (0 <= ny < W):
                continue
            if (nx, ny) in seen:
                continue
            if graph[nx][ny] == ".":
                todo.append((nx, ny))
                seen.add((nx, ny))
                cost[(nx, ny)] = cost[(x, y)] + 1
                if nx == H - 1 and ny == W - 1:
                    return cost[(nx, ny)]
    return -1


white = 0
for line in HW_graph:
    white += line.count(".")

cost = bfs(HW_graph)
if cost == -1:
    print(cost)
else:
    print(white - cost)

Solution (Python):
from collections import deque

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


INF = 10**7
memo = [[INF]*w for i in range(h)]


wcnt = 0
for i in p:
    for j in i:
        if j == '.':
            wcnt+=1


q = deque()
q.append((0, 0))
memo[0][0]  = 0


vx = (0, -1, 0, 1)
vy = (-1, 0, 1, 0)

ans = -1
for i in range(INF):
    
    if len(q) == 0:
        break
        
    
    x, y = map(int, q.pop())
    
    
    if x == w-1 and y == h-1:
        ans = memo[y][x]
        break
        
    
    for j in range(4):
        nx, ny = x+vx[j], y+vy[j]
        
        
        if nx < 0 or w <= nx or ny < 0 or h <= ny or memo[ny][nx] != INF or p[ny][nx] == '
            continue
            
        memo[ny][nx] = memo[y][x]+1
        q.appendleft((nx, ny))

if ans == -1:
    print(ans)
else:
    print(wcnt-ans-1)

Solution (Python):
import queue

def bfs(h, w, maps):
    distance = [[float("inf")] * w for _ in range(h)]
    dx, dy = [0, 1, 0, -1], [1, 0, -1, 0]

    distance[0][0] = 0
    pri_queue = queue.Queue()
    pri_queue.put((0, 0))
    while True:
        if pri_queue.empty():
            break
        p = pri_queue.get()
        if p[0] == h - 1 and p[1] == w - 1:
            break

        for i in range(4):
            nx, ny = p[0] + dx[i], p[1] + dy[i]
            if 0 <= nx < h and 0 <= ny < w and maps[nx][ny] != "
                pri_queue.put((nx, ny))
                distance[nx][ny] = distance[p[0]][p[1]] + 1

    if distance[h - 1][w - 1] != float('inf'):
        return distance[h - 1][w - 1]

    else:
        return -1

h, w = map(int, input().split())
maps = [list(input()) for _ in range(h)]
wall = 0

for i in maps:
    for j in range(w):
        if i[j] == "
            wall += 1

min_dis = bfs(h, w, maps)

print(-1 if min_dis == -1 else h * w - (wall + min_dis + 1))

Solution (Python):
from collections import deque
def bfs():
    d=[[float("inf")]*w for i in range(h)]
    dx=[1,0,-1,0]
    dy=[0,1,0,-1]
    que=deque([])
    que.append((0,0))
    d[0][0]=0
    cnt=0
    while que:
        p=que.popleft()
        if p[0]==h-1 and p[1]==w-1:
            break
        for i in range(4):
            nx=p[0]+dx[i]
            ny=p[1]+dy[i]
            if 0<=nx and nx<h and 0<=ny and ny<w and maze[nx][ny]!="
                que.append((nx,ny))
                d[nx][ny]=d[p[0]][p[1]]+1
    for i in range(h):
        for j in range(w):
            if maze[i][j]=="
                cnt+=1
    if d[h-1][w-1]!=float("inf"):
        return h*w-d[h-1][w-1]-1-cnt
    else:
        return -1

h,w=map(int,input().split())
maze=[list(input()) for i in range(h)]

print(bfs())

Solution (Python):
from collections import deque
import copy

h,w = map(int, input().split())
s = [["
black = -(h+w) * 2 - 4
for i in s:
  black += i.count("
s[1][1] = 1
q = deque([(1,1)])
white = 1
while True:
  q2 = deque([])
  white += 1
  while len(q):
    a,b = q.popleft()
    if s[a-1][b] == ".":
      s[a-1][b] = white
      q2.append((a-1,b))
    if s[a+1][b] == ".":
      s[a+1][b] = white
      q2.append((a+1,b))
    if s[a][b-1] == ".":
      s[a][b-1] = white
      q2.append((a,b-1))
    if s[a][b+1] == ".":
      s[a][b+1] = white
      q2.append((a,b+1))   
  if s[h][w] != ".":
    print(h*w - white - black)
    break
  if len(q2):
    q = copy.copy(q2)
  else:
    print(-1)
    break

Solution (Python):
H, W=map(int, input().split())
m=[[-1 for i in range(W+2)]]
mm=[[-1]+[0 for j in range(W)]+[-1] for i in range(H)]
m=m+mm+m
m[1][1]=1

counter0=0
for i in range(1, H+1):
  c=input()
  for j in range(1, W+1):
    if c[j-1]=='
      m[i][j]=-1
    else:
      counter0+=1
      
def f(math, kazu, h, w):
  cha=0
  for i in range(1, h+1):
    for j in range(1, w+1):
      if math[i][j]==kazu:
        if math[i-1][j]==0:
          math[i-1][j]=kazu+1
          cha=1
        if math[i+1][j]==0:
          math[i+1][j]=kazu+1
          cha=1
        if math[i][j-1]==0:
          math[i][j-1]=kazu+1
          cha=1
        if math[i][j+1]==0:
          math[i][j+1]=kazu+1
          cha=1
  return math, cha

cha=1
i=1
while cha==1:
  m, cha=f(m, i, H, W)
  i+=1
  
if m[H][W]==0:
  out=-1
else:
  out=counter0-m[H][W]
  
print(out)

Solution (Python):



from collections import deque

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

all_white = 0



c_array = [[0 for _ in range(W+1)]]  
visited_flag_array = [[1 for _ in range(W+1)]] 
distance_array = [[-1 for _ in range(W+1)]] 

for i in range(H):
    c = str(input())
    c_list = [0] + [c[i] for i in range(W)] + [0]   
    c_array.append(c_list)
    
    all_white += c_list.count(".")
    
    visited_list = [1] + [0 for _ in range(W)] + [1]
    visited_flag_array.append(visited_list)

    distance_list = [-1] + [-1 for _ in range(W)] + [-1]
    distance_array.append(distance_list)

c_array.append([0 for _ in range(W+1)])
visited_flag_array.append([1 for _ in range(W+1)])
distance_array.append([-1 for _ in range(W+1)])


def bfs(start_node_y,start_node_x):
    candidate_deque = deque() 
    
    
    visited_flag_array[start_node_y][start_node_x] = 1     
    candidate_deque.append((start_node_y,start_node_x,0))  
    distance_array[start_node_y][start_node_x] = 0         
    
    for _ in range(1,H*W*4):
        
        if len(candidate_deque) == 0:
            break
        else:
            visiting_node = candidate_deque.popleft()
            vn_y = visiting_node[0]
            vn_x = visiting_node[1]
            vn_d = visiting_node[2]
            
            
            
            
            
            
            connecting_node_list = [(vn_y+1,vn_x),(vn_y,vn_x+1),(vn_y-1,vn_x),(vn_y,vn_x-1)]
            
            for connecting_node in connecting_node_list:
                cn_y = connecting_node[0]
                cn_x = connecting_node[1]
                
                
                
                
                if visited_flag_array[cn_y][cn_x] != 1 and c_array[cn_y][cn_x] == ".":
                    
                    
                    visited_flag_array[cn_y][cn_x] = 1
                    candidate_deque.append((cn_y,cn_x,vn_d + 1))
                    distance_array[cn_y][cn_x] = vn_d + 1
                    
                    
                    
                    
                    if cn_y == H and cn_x == W:
                        break
                
                
                
                
                
                
                
                
                


bfs(1,1)
shortest_distance = distance_array[H][W] + 1 


if shortest_distance == 0: 
    print(-1)
else:
    print(all_white - shortest_distance)

Solution (Python):
import heapq
def main():

    H, W = map(int, input().split())
    A = []
    white = 0
    visited = set()
    visited.add((0, 0))
    for i in range(H):
        A.append(input())
        for j in range(W):
            if A[-1][j] == '.': white += 1
            else: visited.add((i, j))

    h = [[1, 0, 0]]
    goal = [H-1, W-1]
    mv = [[1,0],[-1,0],[0,1],[0,-1]]

    while h:
        n, i, j = heapq.heappop(h)
        if [i, j] == goal:
            return white - n
        for di, dj in mv:
            i1, j1 = i+di, j+dj
            if 0<=i1<H and 0<=j1<W and (i1, j1) not in visited:
                heapq.heappush(h, [n+1, i1, j1])
                visited.add((i1, j1))

    return -1

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

Solution (Python):
import sys
from collections import deque

if sys.platform =='ios':
	sys.stdin=open('Untitled.txt')
input = sys.stdin.readline
def MAP(): return [int(s) for s in input().split()]

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

Y, X = [int(s) for s in input().split()]
sy, sx = [0, 0]
gy, gx = [Y-1, X-1]

M = []

for i in range(Y):
	M.append([s for s in input().rstrip()]) 

dist = [[[-1,-1,-1] for _ in range(X)] for _ in range(Y)]
queue = deque()

dist[sy][sx] = [0,0,0]
queue.append([sy, sx])

while queue:
	y, x = queue.popleft()
	
	
	for i in range(4):
		ny = y+dy[i]
		nx = x+dx[i]
		
		if ny>=Y or ny<0 or nx>=X or nx<0: continue
		if dist[ny][nx][0] != -1: continue
		
		if M[ny][nx] == '.':
			dist[ny][nx] = [dist[y][x][0]+1,y,x]
			queue.append([ny, nx])



walls = 0
for i in range(Y):
	for j in range(X):
		if M[i][j] == '

if dist[gy][gx][0] != -1:
	print(Y*X-(dist[gy][gx][0]+1)-walls)
else:
	print(-1)

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

for i in range(h):
    s.append(input())



from collections import deque

Q = deque()

Q.append((0,0))
N = [(1,0),(-1,0),(0,1),(0,-1)]
D = [[-1]*w for _ in range(h)]
D[0][0]=1
cnt = 0

for u in range(h):
    for v in range(w):
        if s[u][v]=="
            cnt +=1

while Q:
    a,b = Q.popleft()
    for i,j in N:
        if 0<=a+i<h and 0<=b+j<w:
            if D[a+i][b+j]<0 and s[a+i][b+j]==".":
                    D[a+i][b+j] = D[a][b]+1
                    Q.append((a+i,b+j))
           

if D[h-1][w-1]>0:
    print(h*w-cnt-D[h-1][w-1])
else:
    print(-1)

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


kuro = 0
for i in range(h):
    for j in range(w):
        if sl[i][j] == "
            kuro += 1

from collections import deque
dist = [-1]*w*h
que = deque([0])
dist[0] = 0
while que:
    v = que.popleft()
    d = dist[v]
    for i in [v+1, v-1, v+w, v-w]:
        if v % w == 0 and i == v-1:
            continue
        if v % w == w-1 and i == v+1:
            continue
        if 0 <= i <= w * h - 1:
            if sl[i//w][i%w] == ".":
                if dist[i] > -1:
                    continue
                dist[i] = d + 1
                que.append(i)

if dist[-1] == -1:
    print(-1)
else:
    print(w*h - dist[-1] -1 - kuro)

Solution (Python):

from collections import deque
import copy

H, W = map(int, input().split())
field = [list(input()) for _ in range(H)]
field_original = copy.deepcopy(field)


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


dist = [[-1] * W for _ in range(H)]
que_x = deque()
que_y = deque()


prev_x = [[-1] * W for _ in range(H)]
prev_y = [[-1] * W for _ in range(H)]


dist[0][0] = 0
que_x.append(0)
que_y.append(0)


while que_x and que_y:
    x = que_x[0]
    y = que_y[0]
    que_x.popleft()
    que_y.popleft()
    for direct in range(4):
        nx = x + dx[direct]
        ny = y + dy[direct]
        if nx < 0 or H <= nx or ny < 0 or W <= ny:      
            continue
        if field[nx][ny] == "
            continue
        if dist[nx][ny] == -1:          
            que_x.append(nx)
            que_y.append(ny)
            dist[nx][ny] = dist[x][y] + 1   
            prev_x[nx][ny] = x      
            prev_y[nx][ny] = y      

x = H - 1
y = W - 1

if dist[x][y] == -1:        
    print(-1)
    exit()

while x != -1 and y != -1:
    field[x][y] = "o"

    
    px = prev_x[x][y]
    py = prev_y[x][y]
    x, y = px, py

ans = 0
for i in range(H):
    for k in range(W):
        if field[i][k] == field_original[i][k] == ".":
            ans += 1
print(ans)

Solution (Python):
H, W = list(map(int, input().split()))
M = [[-1]*(W+2)]
ans = 0
for _ in range(H):
    s = input()
    ans += s.count('.')
    M.append([-1]+[0 if c=='.' else -1 for c in s]+[-1])
M += [[-1]*(W+2)]

queue = [(1,1)]
M[1][1] = 1
dr = [(+1,0),(-1,0),(0,+1),(0,-1)]
turn = 1
while len(queue)>0:
    turn += 1
    queue_new = []
    for qx, qy in queue:
        for dx, dy in dr:
            x, y = qx+dx, qy+dy
            if M[y][x]==0:
                M[y][x] = turn
                queue_new.append((x,y))
    queue = queue_new

print(ans-M[H][W] if M[H][W]>0 else -1)

Solution (Python):
from collections import deque

H, W = map(int, input().split())
S = [0] * H
shortest_path = [[-1] * W for i in range(H)]
sharp_count = 0
for i in range(H):
    S[i] = input()
    sharp_count += S[i].count("

que_list = deque()
que_list.append((0, 0))
shortest_path[0][0] = 0
while que_list:
    q = que_list.popleft()
    if H > q[0]-1 >= 0 and W > q[1] >= 0:
        if S[q[0]-1][q[1]] != "
            que_list.append((q[0]-1,q[1]))
            shortest_path[q[0]-1][q[1]] = shortest_path[q[0]][q[1]]+1
    if H > q[0] >= 0 and W > q[1]+1 >= 0:
        if S[q[0]][q[1]+1] != "
            que_list.append((q[0],q[1]+1))
            shortest_path[q[0]][q[1]+1] = shortest_path[q[0]][q[1]]+1
    if H > q[0] >= 0 and W > q[1]-1 >= 0:
        if S[q[0]][q[1]-1] != "
            que_list.append((q[0],q[1]-1))
            shortest_path[q[0]][q[1]-1] = shortest_path[q[0]][q[1]]+1
    if H > q[0]+1 >= 0 and W > q[1] >= 0:
        if S[q[0]+1][q[1]] != "
            que_list.append((q[0]+1,q[1]))
            shortest_path[q[0]+1][q[1]] = shortest_path[q[0]][q[1]]+1

if shortest_path[H-1][W-1] == -1:
    print(-1)
else:
    print(H*W - (shortest_path[H-1][W-1]+1+sharp_count))

Solution (Python):
from collections import deque,defaultdict,Counter
from itertools import accumulate
import bisect
from heapq import heappop,heappush
from fractions import gcd
from copy import deepcopy
import math
import queue


Mod = 1000000007
import sys

sys.setrecursionlimit(100000) 
  
def sieve_of_eratosthenes(n):
    if not isinstance(n,int):
        raise TypeError("n is not int")
    if n<2:
        raise ValueError("n is not effective")
    prime = [1]*(n+1)
    for i in range(2,int(math.sqrt(n))+1):
        if prime[i] == 1:
            for j in range(2*i,n+1):
                if j%i == 0:
                    prime[j] = 0
    res = []
    for i in range(2,n+1):
        if prime[i] == 1:
            res.append(i)
    return res

def factorial(i):
    if i == 1:
        return 1
    else:
        return i*factorial(i-1)
 
class UnionFind:
    def __init__(self,n):
        self.parent = [i for i in range(n+1)]
        self.rank = [0 for i in range(n+1)]
    
    def findroot(self,x):
        if x == self.parent[x]:
            return x
        else:
            y = self.parent[x]
            y = self.findroot(self.parent[x])
            return y
    
    def union(self,x,y):
        px = self.findroot(x)
        py = self.findroot(y)
        if px < py:
            self.parent[py] = px
        else:
            self.parent[px] = py
 
    def same_group_or_no(self,x,y):
        return self.findroot(x) == self.findroot(y)




def main(): 
    H,W = map(int,input().split())
    s = [input() for i in range(H)]
    sy,sx = 0,0
    gy,gx = H-1,W-1
    cnt = 0
    for i in range(H):
        for j in range(W):
            if s[i][j] == "
                cnt += 1
    inf = float("inf")
    d = [[inf]*W for i in range(H)]
    q = queue.Queue()
    dx = [1,0,-1,0]
    dy = [0,1,0,-1]
    def bfs():
        for i in range(H):
            for j in range(W):
                d[i][j] = inf
        q.put([sy,sx])
        d[sy][sx]=0
        while not q.empty():
            p = q.get()
            if p[0] == gy and p[1] == gx:
                break
            for k in range(4):
                ny = p[0]+dy[k]
                nx = p[1]+dx[k]
                if 0 <= nx < W and 0 <= ny < H and s[ny][nx] != "
                    q.put([ny,nx])
                    d[ny][nx] = d[p[0]][p[1]]+1
        return d[gy][gx]
    res = bfs()
    print(-1 if res == inf else H*W-cnt-res-1)
if __name__ == "__main__":
    main()

Solution (Python):
import sys
sys.setrecursionlimit(2147483647)
INF=float("inf")
MOD=10**9+7
input=lambda :sys.stdin.readline().rstrip()
def resolve():
    h,w=map(int,input().split())
    grid=[None]*(h+2)
    grid[0]=['
    grid[-1]=['
    for i in range(1,h+1):
        grid[i]=list('

    
    dist=[[INF]*(w+1) for _ in range(h+1)]
    dist[1][1]=1
    from collections import deque
    from itertools import product

    
    Q=deque([(1,1)])
    while(Q):
        i,j=Q.popleft()
        
        for di,dj in [(-1,0),(1,0),(0,-1),(0,1)]:
            if(grid[i+di][j+dj]=='
            if(dist[i+di][j+dj]!=INF): continue
            dist[i+di][j+dj]=dist[i][j]+1
            Q.append((i+di,j+dj))

    if(dist[h][w]==INF):
        print(-1)
        return

    cnt=0
    for i in range(1,h+1):
        for j in range(1,w+1):
            cnt+=grid[i][j]=='.'
    print(cnt-dist[h][w])
resolve()

Solution (Python):
from collections import deque

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

d = [[-1] * w for _ in range(h)]


def bfs():
    sx, sy = 0, 0
    q = deque()
    q.append([sx, sy])
    d[sy][sx] = 0
    dxy = [[1, 0], [-1, 0], [0, 1], [0, -1]]

    while q:
        ux, uy = q.popleft()
        for dx, dy in dxy:
            vx = ux + dx
            vy = uy + dy

            if 0 <= vx <= w - 1 and 0 <= vy <= h - 1 \
                and s[vy][vx] == "." and d[vy][vx] == -1:
                q.append([vx, vy])
                d[vy][vx] = d[uy][ux] + 1


bfs()
mn = d[h-1][w-1]

if mn == -1:
    ans = -1
else:
    cnt = 0
    for i in range(h):
        for j in range(w):
            if s[i][j] == ".":
                cnt += 1

    ans = cnt - mn - 1

print(ans)

Solution (Python):
from collections import deque

H,W=map(int,input().split())
p={}
for i in range(H):    
    for j,c in enumerate(input()):
        p[(i,j)]=c=='.'
d={(i,j):-1 for i in range(H) for j in range(W)}
white=sum(p.values())
q=deque()
s=(0,0)
q.append(s);d[s]=1
while q:
    u=q.popleft()
    ui,uj=u
    for v in [(ui-1,uj),(ui+1,uj),(ui,uj-1),(ui,uj+1)]:
        vi,vj=v
        if 0<=vi<=H-1 and 0<=vj<=W-1 and p[v] and d[v]==-1:
            d[v]=d[u]+1
            q.append(v)
if d[(H-1,W-1)]==-1:
    ans=-1
else:
    ans=white-d[(H-1,W-1)]
print(ans)

Solution (Python):
import queue
h,w = map(int,input().split())
mas = []
black_num = 0
inf = 10 ** 7
for i in range(h):
    row = list(input())
    mas.append(row)
for i in range(h):
    for j in range(w):
        if mas[i][j] == "
            black_num += 1
dx = [0,0,1,-1]
dy = [1,-1,0,0]
def bfs():
    q = []
    q.append([0,0])
    step = []
    for i in range(h):
        step.append([-1] * w)
    for i in range(h):
        for j in range(w):
            step[i][j] = inf
    step[0][0] = 0
    while not len(q) == 0:
        s = q[0]
        q = q[1:]
        if s[0] == h-1 and s[1] == w-1:
            break
        for i in range(4):
            nx = s[0] + dx[i]
            ny = s[1] + dy[i]
            if(0 <= nx < h and 0 <= ny < w and mas[nx][ny] != '
                q.append([nx,ny])
                step[nx][ny] = step[s[0]][s[1]] + 1
    
    if(step[h-1][w-1] == inf):
        return -1
    else:
        return step[h-1][w-1]

least = bfs()
if(least == -1):
    print(-1)
else:
    print(h * w - black_num - least - 1)

Solution (Python):
from collections import deque
 
R, C = map(int, input().split())
sy, sx = 1, 1
gy, gx = R, C
F = [ input() for _ in range(R) ]
count = 0
for i in F:
  count += i.count(".")
dist = [ [-1]*(C+1) for _ in range(R+1) ]
dist[sy][sx] = 0
q = deque([[sy, sx]])
dy = [1, 0, -1, 0]
dx = [0, 1, 0, -1]
while len(q) != 0:
  h, w = q.popleft()
  for i in range(4):
    nh, nw = h+dy[i], w+dx[i]
    if nh>R or nh<=0 or nw>C or nw<=0:
      continue
    if F[nh-1][nw-1] == "
      continue
    if dist[nh][nw] != -1:
      continue
    dist[nh][nw] = dist[h][w] + 1
    if nh==gy and nw==gx:
      print(count - dist[nh][nw] - 1)
      exit()
    q.append([nh, nw])
print(-1)

Solution (Python):
import sys

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


m = []
m.append('
white = 0
for i in range(h):
  s = input()
  m.append(list('
  white += s.count('.')
m.append('

stack = set([(1, 1)])
dist = 0


while len(stack) > 0:
  
  
  dist += 1
  
  
  next_w = set()
  
  for y, x in stack:
    m[y][x] = dist
    
    
    if (y, x) == (h, w):
      print(white - dist)
      exit()
      
 	
    for dx,dy in [0,1],[0,-1],[1,0],[-1,0]:
      
      if m[y-dy][x-dx] == '.':
        next_w.add((y-dy,x-dx))
  stack = next_w

print('-1')