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


def input():
    return sys.stdin.readline()[:-1]


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

sy = 0
sx = 0
gy = H-1
gx = W-1

board = [list(input().strip()) for _ in range(H)]
visited = [[0 for i in range(W)] for j in range(H)]

q = deque([])
q.append([sy, sx, 0])
is_reach = False

while q:
    y, x, z = q.popleft()
    if y == gy and x == gx:
        is_reach = True
        break
    if (not 0 <= y < H) or (not 0 <= x < W):
        continue
    if board[y][x] == "." and visited[y][x] == 0:
        q.append([y+1, x, z+1])
        q.append([y, x+1, z+1])
        q.append([y-1, x, z+1])
        q.append([y, x-1, z+1])
        visited[y][x] = 1

if is_reach:
    num_white = 0
    for i in range(H):
        for j in range(W):
            if board[i][j] == ".":
                num_white += 1
    print(num_white-z-1)
else:
    print(-1)

Solution (Python):

from queue import Queue


def main(h, w, a):
    visited = [[False] * w for _ in range(h)]
    visited[0][0] = True
    
    cur = [[0, 0]]
    dx = [0, 1, 0, -1]
    dy = [1, 0, -1, 0]
    cnt = 0
    dis = -1
    while len(cur) > 0:
        cnt += 1
        nex = []
        for pos in cur:
            for i in range(4):
                tx = pos[0] + dx[i]
                ty = pos[1] + dy[i]
                
                if 0 <= tx < w and 0 <= ty < h and a[ty][tx] != '
                    if tx == w - 1 and ty == h - 1:
                        dis = cnt
                    nex.append([tx, ty])
                    visited[ty][tx] = True
        
        
        cur = nex
    if dis < 0:
        print(-1)
        return
    tmp = 0
    for R in a:
        for c in R:
            if c == '
                tmp += 1
    ret = h * w - tmp - dis - 1
    print(ret)
    return

if __name__ == '__main__':
    h, w = map(int, input().split())
    a = []
    for i in range(h):
        a.append(input())
    main(h, w, a)

Solution (Python):
H, W = map(int, input().split())
g = [input() for _ in range(H)]
white = 0
black = 0
for i in range(H):
    for j in range(W):
        if g[i][j] == '
            black += 1
        else:
            white += 1
start = (0, 0)
goal = (H-1, W-1)
S = [start]
T = {start: 1}
while S and goal not in T:
    S2 = []
    for x, y in S:
        for pos in [(x+1, y), (x-1, y), (x, y+1), (x, y-1)]:
            x2, y2 = pos
            if 0<= x2 <= H-1 and 0<= y2 <= W-1:
                if g[x2][y2] != '
                    T[pos] = T[(x, y)] + 1
                    S2.append(pos)
    S = S2
if goal not in T:
    print(-1)
else:
    print(white - T[goal])

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

start = (0, 0)
goal = (h-1, w-1)

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

d = [[0 for i in range(w)] for i in range(h)] 

from queue import Queue

q = Queue()


for i in range(h):
    for j in range(w):
        d[i][j] = float('inf')

q.put((0, 0))
d[start[0]][start[1]] = 0


while q.qsize():
    
    p = q.get()

    
    if p[0] == goal[0] and [1] == goal[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:
            if s[nx][ny] == '.' and d[nx][ny] == float('inf'):

                q.put((nx, ny))
                d[nx][ny] = d[p[0]][p[1]] + 1

dist = d[goal[0]][goal[1]]
if dist == float('inf'):
    print(-1)
else:
    count_w = 0
    for i in range(h):
        for j in range(w):
            if s[i][j] == '.':
                count_w += 1
    print(count_w - dist - 1)

Solution (Python):



import sys
from collections import deque

input = sys.stdin.readline

def main():
    H, W = [int(e) for e in input().split()]
    S = [0 for _ in range(H)]
    for i in range(H):
        S[i] = list(input())[:W]

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

    dp = [[0 for _ in range(W)] for _ in range(H)]
    enc = [[False for _ in range(W)] for _ in range(H)]

    i = 0
    j = 1

    q = deque([[0, 0]])
    enc[0][0] = True
    dp[0][0] = 1
    while len(q) != 0:
        pos = q.popleft()

        x = pos[0]
        y = pos[1]

        if x+1 != H and S[x+1][y] == "." and not enc[x+1][y]:
            dp[x+1][y] = dp[x][y] + 1
            enc[x+1][y] = True
            q.append([x+1, y])
        if y+1 != W and S[x][y+1] == "." and not enc[x][y+1]:
            dp[x][y+1] = dp[x][y] + 1
            enc[x][y+1] = True
            q.append([x, y+1])
        if x-1 != -1 and S[x-1][y] == "." and not enc[x-1][y]:
            dp[x-1][y] = dp[x][y] + 1
            enc[x-1][y] = True
            q.append([x-1, y])
        if y-1 != -1 and S[x][y-1] == "." and not enc[x][y-1]:
            dp[x][y-1] = dp[x][y] + 1
            enc[x][y-1] = True
            q.append([x, y-1])

    res = w - dp[H-1][W-1]
    print(res if dp[H-1][W-1] != 0 else -1)


main()

Solution (Python):
from copy import deepcopy
from collections import deque
from itertools import chain

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

H, W = map(int, input().split())
S = []
for _ in range(H):
    S.append(list(input()))
S_initial = deepcopy(S)

    
def bfs():
    S[0][0] = "
    dq = deque() 
    dq.append((0,0,0))
    while dq:
        y,x,d = dq.popleft()
        if d > H*W:
          break
        for dy,dx in dire:
            ny = y + dy; nx = x + dx
            if ny < 0 or ny > H-1 or nx < 0 or nx > W-1:
                continue
            if (ny,nx) == (H-1,W-1):
                return d+1
            if S[ny][nx] == ".":
                dq.append((ny,nx,d+1))
                S[ny][nx] = "
    return -1

dist = bfs()
if dist == -1:
  print(-1)
else:
  S_flatten = list(chain.from_iterable(S_initial))
  cnt_dot = S_flatten.count('.') - (dist+1)
  print(cnt_dot)

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

WHITE = '.'
BLACK = '

num_white = 0
for x in range(H):
    for y in range(W):
        if S[x][y] == WHITE:
            num_white += 1

is_reached = False
positions = [(0, 0)]
delta_positions = [(1, 0), (-1, 0), (0, 1), (0, -1)]
S[0][0] = 1

while positions:
    new_positions = []
    for x, y in positions:
        for dx, dy in delta_positions:
            new_x = x + dx
            new_y = y + dy
            if 0 <= new_x and new_x < H and 0 <= new_y and new_y < W:
                if S[new_x][new_y] == WHITE:
                    new_positions.append((new_x, new_y))
                    S[new_x][new_y] = S[x][y] + 1
                    if new_x == H - 1 and new_y == W - 1:
                        is_reached = True
                        break
    positions = new_positions

if is_reached:
    print(num_white - S[H-1][W-1])
else:
    print(-1)

Solution (Python):
from collections import deque

H, W = map(int, input().split())
matrix = [input() for _ in range(H)]
(sy, sx) = (0, 0)
(gy, gx) = (H - 1, W - 1)

dist = [[None for _ in range(W)] for _ in range(H)]

q = deque([(sy, sx)])
dist[sy][sx] = 1

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

while q:
    cy, cx = q.popleft()
    if (cy, cx) == (gy, gx):
        break

    for (dy, dx) in ((0, 1), (1, 0), (0, -1), (-1, 0)):
        ny, nx = cy + dy, cx + dx

        if 0 <= nx < W and 0 <= ny < H and matrix[ny][nx] == ".":
            if dist[ny][nx] is None:
                q.append((ny, nx))
                dist[ny][nx] = dist[cy][cx] + 1

if dist[gy][gx] is None:
    print(-1)
    exit()

print(count_dots - dist[gy][gx])

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):
H, W = map(int, input().split())
T = [[] for i in range(H)]
b = 0
for i in range(H):
    T[i] = list(input())
    for j in range(W):
        if T[i][j] == '
            b += 1

que = [(0, 0, 1)]
while que:
    x, y, k = que.pop(0)
    if x == H - 1 and y == W - 1:
        print(H * W - b - k)
        exit()

    for dx, dy in [(0, 1), (1, 0), (-1, 0), (0, -1)]:
        nx, ny = x + dx, y + dy
        if 0 <= nx < H and 0 <= ny < W and T[nx][ny] == '.':
            T[nx][ny] = '
            que.append((nx, ny, k + 1))
print(-1)

Solution (Python):


from sys import stdout
from bisect import bisect_left as binl
from copy import copy, deepcopy
from collections import defaultdict


mod = 1


def intin():
    input_tuple = input().split()
    if len(input_tuple) <= 1:
        return int(input_tuple[0])
    return tuple(map(int, input_tuple))


def intina():
    return [int(i) for i in input().split()]


def intinl(count):
    return [intin() for _ in range(count)]


def modadd(x, y):
    global mod
    return (x + y) % mod


def modmlt(x, y):
    global mod
    return (x * y) % mod


def lcm(x, y):
    while y != 0:
        z = x % y
        x = y
        y = z
    return x


def combination(x, y):
    assert(x >= y)

    if y > x // 2:
        y = x - y

    ret = 1

    for i in range(0, y):
        j = x - i
        i = i + 1

        ret = ret * j
        ret = ret // i

    return ret


def get_divisors(x):
    retlist = []
    for i in range(1, int(x**0.5) + 3):
        if x % i == 0:
            retlist.append(i)
            retlist.append(x // i)
    return retlist


def get_factors(x):
    retlist = []
    for i in range(2, int(x**0.5) + 3):
        while x % i == 0:
            retlist.append(i)
            x = x // i
    retlist.append(x)
    return retlist


def make_linklist(xylist):
    linklist = {}
    for a, b in xylist:
        linklist.setdefault(a, [])
        linklist.setdefault(b, [])
        linklist[a].append(b)
        linklist[b].append(a)
    return linklist


def calc_longest_distance(linklist, v=1):
    distance_list = {}
    distance_count = 0
    distance = 0
    vlist_previous = []
    vlist = [v]
    nodecount = len(linklist)

    while distance_count < nodecount:
        vlist_next = []
        for v in vlist:
            distance_list[v] = distance
            distance_count += 1
            vlist_next.extend(linklist[v])
        distance += 1
        vlist_to_del = vlist_previous
        vlist_previous = vlist
        vlist = list(set(vlist_next) - set(vlist_to_del))

    max_distance = -1
    max_v = None
    for v, distance in distance_list.items():
        if distance > max_distance:
            max_distance = distance
            max_v = v

    return (max_distance, max_v)


def calc_tree_diameter(linklist, v=1):
    _, u = calc_longest_distance(linklist, v)
    distance, _ = calc_longest_distance(linklist, u)
    return distance


class UnionFind:

    def __init__(self, n):
        self.parent = [i for i in range(n)]

    def root(self, i):
        if self.parent[i] == i:
            return i
        self.parent[i] = self.root(self.parent[i])
        return self.parent[i]

    def unite(self, i, j):
        rooti = self.root(i)
        rootj = self.root(j)
        if rooti == rootj:
            return
        if rooti < rootj:
            self.parent[rootj] = rooti
        else:
            self.parent[rooti] = rootj

    def same(self, i, j):
        return self.root(i) == self.root(j)





def main():
    h, w = intin()
    slistlist = ['
    slistlist.extend(['
    slistlist.append('

    clistlist = []
    for i in range(h + 2):
        clistlist.append([False] * (w + 2))

    white_count = 0
    for slist in slistlist:
        for s in slist:
            if s == '.':
                white_count += 1

    paths = {(1, 1): 1}

    while paths:
        next_paths = defaultdict(lambda: float('inf'))

        for p, c in paths.items():
            if slistlist[p[0]+1][p[1]] == '.' and not clistlist[p[0]+1][p[1]]:
                next_paths[(p[0]+1, p[1])] = min(c + 1, next_paths[(p[0]+1, p[1])])
                clistlist[p[0]+1][p[1]] = True
            if slistlist[p[0]-1][p[1]] == '.' and not clistlist[p[0]-1][p[1]]:
                next_paths[(p[0]-1, p[1])] = min(c + 1, next_paths[(p[0]-1, p[1])])
                clistlist[p[0]-1][p[1]] = True
            if slistlist[p[0]][p[1]+1] == '.' and not clistlist[p[0]][p[1]+1]:
                next_paths[(p[0], p[1]+1)] = min(c + 1, next_paths[(p[0], p[1]+1)])
                clistlist[p[0]][p[1]+1] = True
            if slistlist[p[0]][p[1]-1] == '.' and not clistlist[p[0]][p[1]-1]:
                next_paths[(p[0], p[1]-1)] = min(c + 1, next_paths[(p[0], p[1]-1)])
                clistlist[p[0]][p[1]-1] = True

        paths = next_paths
        if (h, w) in paths:
            print(white_count - paths[(h, w)])
            return

    print(-1)


if __name__ == '__main__':
    main()

Solution (Python):
from collections import deque

H, W = map(int,input().split())
S = []
wall = 0
for i in range(H):
    s = list(input())
    wall += s.count("
    S.append(s)
q = deque()
q.append([0, 0, 0])
S[0][0] = "
while q:
    y, x, cnt = q.popleft()
    if y == H-1 and x == W-1:
        break
    for dy, dx in [[1, 0], [-1, 0], [0, 1], [0, -1]]:
        if 0 <= y + dy < H and 0 <= x + dx < W and S[y + dy][x + dx] == ".":
            q.append([y + dy, x + dx, cnt + 1])
            S[y + dy][x + dx] = "

if S[H-1][W-1] == ".":
    print(-1)
else:
    score = H * W - (cnt + 1) - wall
    print(score)

Solution (Python):
R,C = map(int,input().split())

maze = []
for i in range(R):
    maze.append(input())

def bfs(sx,sy,gx,gy):
    queue = []
    queue.append([sx,sy])

    visited = [ [ float("inf") for i in range(C)] for j in range(R)]
    visited[sx][sy] = 0

    while queue:
        p = queue.pop(0)

        if gx == p[0] and gy == p[1]:
            break

        for d in [[1,0],[0,1],[-1,0],[0,-1]]:
            nx = p[0] + d[0]
            ny = p[1] + d[1]

            if 0 <= nx and 0 <= ny and nx < R and ny < C and maze[nx][ny] == "." and visited[nx][ny] == float("inf"):
                queue.append([nx,ny])
                visited[nx][ny] = visited[p[0]][p[1]] + 1
    return visited[gx][gy]

k = bfs(0,0,R-1,C-1)
if k == float("inf"):
    print(-1)
    exit()
c = 0
for i in range(R):
    for j in range(C):
        if maze[i][j] == ".":
            c += 1
print(c - k - 1)

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

H,W = [int(i) for i in input().split()]
l = [list(input()) for _ in range(H)]
check = [[False]*W for _ in range(H)]
ans = [[0]*W for _ in range(H)]

q = deque()
q.append([0,0])
check[0][0] = True

while q:
    i,j = q.popleft()
    for next_i, next_j in [[i+1,j], [i-1,j], [i,j+1], [i,j-1]]:
        if 0 <= next_i < H and 0 <= next_j < W:
            if not check[next_i][next_j] and l[next_i][next_j] != '
                q.append([next_i,next_j])
                check[next_i][next_j] = True
                ans[next_i][next_j] = ans[i][j]+1

cnt = 0
for i in range(H):
    for j in range(W):
        if l[i][j] == '.':
            cnt += 1

if ans[H-1][W-1]:
    print(cnt-ans[H-1][W-1]-1)
else:
    print(-1)

Solution (Python):


def main():
    high, width = map(int, input().split())
    data = [list(input()) for i in range(high)]

    start, goal = (0, 0), (high - 1, width - 1)

    now_data = set()
    now_data.add(start)
    next_data = set()
    pre_data = set()
    pre_data.add(start)

    move_tada = [[-1, 0], [1, 0], [0, 1], [0, -1]]

    count = 1
    while len(now_data) > 0:
        if goal in pre_data:
            break
        count += 1
        for now_x, now_y in now_data:
            for add_x, add_y in move_tada:
                move_x, move_y = now_x + add_x, now_y + add_y
                if 0 <= move_x < high and 0 <= move_y < width:
                    if data[move_x][move_y] == '.' and (move_x, move_y) not in pre_data:
                        ok_data = (move_x, move_y)
                        pre_data.add(ok_data)
                        next_data.add(ok_data)
        now_data = next_data
        next_data = set()

    if goal in pre_data:
        white_data = 0
        for i in range(high):
            white_data += data[i].count('.')
        print(white_data - count)
    else:
        print(-1)


if __name__ == '__main__':
    main()

Solution (Python):


def main():
    high, width = map(int, input().split())
    data = [list(input()) for i in range(high)]

    start, goal = (0, 0), (high - 1, width - 1)

    now_data = set()
    now_data.add(start)
    next_data = set()
    pre_data = set()
    pre_data.add(start)

    move_tada = [[-1, 0], [1, 0], [0, 1], [0, -1]]

    count = 1
    while len(now_data) > 0:
        if goal in pre_data:
            break
        count += 1
        for now_x, now_y in now_data:
            for add_x, add_y in move_tada:
                move_x, move_y = now_x + add_x, now_y + add_y
                if 0 <= move_x < high and 0 <= move_y < width:
                    if data[move_x][move_y] == '.' and (move_x, move_y) not in pre_data:
                        ok_data = (move_x, move_y)
                        pre_data.add(ok_data)
                        next_data.add(ok_data)
        now_data = next_data
        next_data = set()

    if goal in pre_data:
        white_data = 0
        for i in range(high):
            white_data += data[i].count('.')
        print(white_data - count)
    else:
        print(-1)


if __name__ == '__main__':
    main()

Solution (Python):
h,w=map(int,input().split())
inf=10**3
T=[[] for _ in range(h+2)]
T[0]=["
T[h+1]=["
for i in range(h):
  T[i+1]=["
count=0
for t in T:
  count+=t.count("
count-=(2*(h+2)+2*w)
T[1][1]=0
Chk=[[1,1]]
while len(Chk)>0:
  c=Chk.pop(0)
  x,y=c[0],c[1]
  if T[x-1][y]!="
    T[x-1][y]=T[x][y]+1
    Chk.append([x-1,y])
  if T[x][y-1]!="
    T[x][y-1]=T[x][y]+1
    Chk.append([x,y-1])
  if T[x+1][y]!="
    T[x+1][y]=T[x][y]+1
    Chk.append([x+1,y])
  if T[x][y+1]!="
    T[x][y+1]=T[x][y]+1
    Chk.append([x,y+1])
print(-1 if T[h][w]==10**3 else h*w-count-T[h][w]-1)

Solution (Python):
from collections import deque
H,W=map(int,input().split())
stack=deque()
c=[input() for i in range(H)]
ans=0
for ci in c:
    for j in ci:
        if j==".":
            ans+=1
reached=[[0]*W for i in range(H)]
stack.append((0,0))
dydx=[(1,0),(-1,0),(0,1),(0,-1)]
while(stack):
    Y,X=stack.popleft()
    for dy,dx in dydx:
        y=Y+dy
        x=X+dx
        if y<0 or y>=H or x<0 or x>=W or c[y][x]=="
            continue
        if reached[y][x]!=0:
            continue
        stack.append((y,x))
        reached[y][x]=reached[Y][X]+1
if reached[H-1][W-1]==0:
    print(-1)
else:
    print(ans-(reached[H-1][W-1]+1))

Solution (Python):
h,w = map(int,input().split())
maze = [input() for x in range(h)]
idou = ([1,0],[0,1],[-1,0],[0,-1])
min_step = [[0 for x in range(w)] for i in range(h)]
next_node = [(0,0)]
past_node = []
min_step[next_node[0][0]][next_node[0][1]] = 1
while next_node:
    for a in idou:
        hei = next_node[0][0] + a[0]
        wei = next_node[0][1] + a[1]
        try:
            if (maze[hei][wei] == "
                continue
            else:
                past_node.append((hei,wei))
                if min_step[hei][wei] != 0:
                    continue
                else:
                    min_step[hei][wei] = min_step[next_node[0][0]][next_node[0][1]]+1
                next_node.append((hei,wei))
        except IndexError:
            continue
    next_node.pop(0)
count = 0
for x in range(h):
    for y in range(w):
        if maze[x][y] == "
            count+=1
if min_step[h-1][w-1] == 0:
  print(-1)
else:
  print(h*w-min_step[h-1][w-1]-count)

Solution (Python):
import numpy as np
H,W = [ int(it) for it in input().split() ]
x = np.array([ [0 if v == "." else 1 for v in input() ] for i in range(H)]).astype(np.int32)
Close = np.zeros(x.shape).astype(np.int32)
fcost = np.zeros(x.shape).astype(np.int32)+10000
fcost[0,0]=0


gx,gy=(x.shape[0]-1,x.shape[1]-1  )

Open=[(0,0,-1)]
dw=[[0,1],[0,-1],[1,0],[-1,0]]


FLAG_END = False
BREAK = False

Open.sort(key=lambda x:-x[2])
nx,ny,_ =  Open.pop()
for i in range(100000):
    while ( Close[nx,ny]==1 ):
        if ( len(Open)==0):
            print (-1)
            BREAK=True
            break
        Open.sort(key=lambda x:-x[2])
        nx,ny,_ =  Open.pop()
    if BREAK:
        break
    Close[nx,ny]=1
    for dx,dy in dw:
        mx,my=nx+dx,ny+dy
        if ( 0<=mx and mx<x.shape[0] and  0<=my and my<x.shape[1] ):
            if ( Close[mx,my] == 0 and x[mx,my]==0 ):
                fcost[mx,my]=min(fcost[mx,my],fcost[nx,ny]+1)
                Open.append( (mx,my,abs(mx-gx)+abs(my-gy)+fcost[mx,my])  )   
                if (mx==gx and my==gy):
                    FLAG_END = True
                    break
    if (FLAG_END):
        break
if (FLAG_END):
    print (x.shape[0]*x.shape[1]-np.sum(x)-fcost[gx,gy]-1 )

Solution (Python):

def IL(): return list(map(int,input().split()))
def SL(): return input().split()
def I(): return int(input())
def S(): return list(input())
h,w=IL()
G=[S() for i in range(h)]
used=[[False for i in range(w)] for j in range(h)]
q=[[0,0,1]]
pos=False
while len(q)>0:
    gy,gx,dis=q.pop(0)
    if gy==h-1 and gx==w-1:
        pos=True
        break
    if not used[gy][gx]:
        if gy!=0:
            if G[gy-1][gx]=="." and not used[gy-1][gx]:
                q.append([gy-1,gx,dis+1])
        if gx!=0:
            if G[gy][gx-1]=="." and not used[gy][gx-1]:
                q.append([gy,gx-1,dis+1])
        if gy!=h-1:
            if G[gy+1][gx]=="." and not used[gy+1][gx]:
                q.append([gy+1,gx,dis+1])
        if gx!=w-1:
            if G[gy][gx+1]=="." and not used[gy][gx+1]:
                q.append([gy,gx+1,dis+1])
    used[gy][gx]=True
if pos:
    ans=0
    for i in range(h):
        ans+=G[i].count(".")
    print(ans-dis)
else:
    print(-1)

Solution (Python):
H,W=map(int, input().split())
S=[input() for i in range(H)]
s=[[0]*W for h in range(H)]
b=0
for h in range(H):
    for w in range(W):
        if S[h][w]=='
            s[h][w]=-1
            b+=1
q=[]
i=1
q.append((0,0))
s[0][0]=1
while (H-1,W-1) not in q:
    q2=[]
    i+=1
    for h,w in q:
        if h>0 and s[h-1][w]==0:
            q2.append((h-1,w))
            s[h-1][w]=i
        if h<H-1 and s[h+1][w]==0:
            q2.append((h+1,w))
            s[h+1][w]=i
        if w>0 and s[h][w-1]==0:
            q2.append((h,w-1))
            s[h][w-1]=i
        if w<W-1 and s[h][w+1]==0:
            q2.append((h,w+1))
            s[h][w+1]=i
    q=q2
    if len(q)==0:
        break
if len(q)==0:
    print(-1)
else:
    print(H*W-i-b)

Solution (Python):
import queue

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

q = queue.Queue()
s[0][0] = 1
q.put((0,0))

while not q.empty():
    i, j = q.get()
    for x, y in [(i+1,j), (i-1,j), (i,j+1), (i,j-1)]:
        if s[x][y] == '.':
            s[x][y] = s[i][j]+1
            q.put((x, y))

if s[H-1][W-1] in ['.', '
    print(-1)
else:
    print(white-s[H-1][W-1])

Solution (Python):
H, W = map(int, input().split())
S = []
for _ in range(H):
    s = input()
    S.append(s)
    
import copy
maze = copy.deepcopy(S)

import queue

INT_MAX = 2**63-1
stayed = [[INT_MAX] * W for _ in range(H)]

def bfs():
    gole = (W-1, H-1)
    q = queue.Queue()
    q.put((
        0, 
        0, 
        0, 
    ))

    while not q.empty():
        cur_x, cur_y, cnt = q.get()
        if (cur_x, cur_y) == gole:
            return cnt
        next_pos = [
            (cur_x, cur_y-1),
            (cur_x, cur_y+1),
            (cur_x-1, cur_y),
            (cur_x+1, cur_y)
        ]
        
        for x, y in next_pos:
            if x == -1 or y == -1 or x == W or y == H:
                continue
            if S[y][x] == '
                continue
            if stayed[y][x] > cnt+1:
                stayed[y][x] = cnt+1
                q.put((x, y, cnt+1))
                
        
    return -1
            

shortest_path_len = bfs()

if shortest_path_len != -1:
    cnt_dot = sum([s.count('.') for s in maze])


    ans = cnt_dot - shortest_path_len - 1
    print(ans)
else:
    print(-1)

Solution (Python):

from collections import deque
H,W=map(int,input().split())

s = [list(input().strip()) for _ in range(H)]
d = [[ 0 for i in range(W)] for j in range(H)]
q = deque([])
q.append([0,0,0])
y,x,z=q.popleft()

H = H-1
W = W-1
ans2=0
while y!=H or x!=W:
  if s[y][x]=="." and d[y][x]==0:
    if y<H:
      q.append([y+1,x,z+1])
    if x<W:
      q.append([y,x+1,z+1])
    if y>0:
      q.append([y-1,x,z+1])
    if x>0:
      q.append([y,x-1,z+1])
    d[y][x]=1
  if q==deque([]):
    ans2 = -1
    break
  y,x,z=q.popleft()
  

ans1=0
for i in range(H+1):
  for j in range(W+1):
    if s[i][j]=="
      ans1 +=1
      
ans = (H+1)*(W+1)-ans1-z-1
if ans2==-1:
  print(ans2)
else:
  print(ans)

Solution (Python):
from collections import Counter
from collections import deque
from functools import reduce


import bisect
import copy
import fractions
import math
import random
import sys
import time
sys.setrecursionlimit(10**7)
INF = 10 ** 18
MOD = 10 ** 9 + 7
def MI(): return map(int, sys.stdin.readline().split())
def IS(): return input()

h, w = MI()
s = [IS() for _ in range(h)]
q = deque()
x_diff = [-1, 0, 1, 0]
y_diff = [0, 1, 0, -1]
require = [[0 for i in range(w)] for j in range(h)]
check = [[0 for i in range(w)] for j in range(h)]

all_grid = h * w
sharp_count = 0
for i in range(h):
    sharp_count += s[i].count('

q.append([0, 0])
check[0][0] = 1

while len(q) != 0:
    tmp_y, tmp_x = q.popleft()
    for i in range(4):
        next_y = tmp_y + y_diff[i]
        next_x = tmp_x + x_diff[i]
        if ( 0 <= next_x <= w-1
            and 0 <= next_y <= h-1
            and check[next_y][next_x] == 0
            and s[next_y][next_x] != '
                check[next_y][next_x] = 1
                require[next_y][next_x] = require[tmp_y][tmp_x] + 1
                q.append([next_y, next_x])

hosuu = require[h-1][w-1]



if hosuu == 0:
    print(-1)
else:
    print(all_grid - sharp_count - hosuu -1)

Solution (Python):
def d_grid_repainting(H, W, S, INF=float('inf')):
    def bfs():
        from collections import deque
        queue = deque([(0, 0)])  
        dist = [[INF for _ in range(W)] for _ in range(H)]  
        dist[0][0] = 1  
        while queue:
            h, w = queue.pop()
            if h == H - 1 and w == W - 1:
                break  
            for dh, dw in ((-1, 0), (0, 1), (1, 0), (0, -1)):
                nh, nw = h + dh, w + dw  
                if 0 <= nh < H and 0 <= nw < W and S[nh][nw] != '
                    
                    queue.appendleft((nh, nw))  
                    dist[nh][nw] = dist[h][w] + 1
        return dist[H - 1][W - 1]

    
    
    
    
    num_white_square = sum([row.count('.') for row in S])
    reach_white_square_min = bfs()
    return num_white_square - reach_white_square_min if reach_white_square_min != INF else -1

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

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

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

def bfs():
    global H,W,maze,goal,start
    
    count = 0
    visited = [[False for _ in range(W)] for _ in range(H)]
    queue = [start]
    
    visited[start[0]][start[1]] = True
    while len(queue) > 0:
        next_queue = []
        for q in queue:
            if q == goal:
                return count
            x,y = q
            for nx,ny in [(x-1,y), (x+1,y),(x,y-1),(x,y+1)]:
                if 0<=nx<H and 0<=ny<W and not visited[nx][ny] and maze[nx][ny] == '.':
                    next_queue.append((nx, ny))
                    visited[nx][ny] = True
            
        queue = next_queue
        count+=1

    return -1

min_step = bfs()

if min_step == -1:
    print(-1)
else:
    count = 0
    for i in range(H):
        for j in range(W):
            if maze[i][j] == '.':
                count += 1
    answer = count - 1 - min_step
    print(answer)

Solution (Python):
from queue import Queue


def main():
    H, W = map(int, input().split())

    white = 0

    grid = [[-1 for _ in range(W + 2)]]
    for _ in range(H):
        line = input()
        white += line.count(".")
        grid.append([-1] + [-1 if char == "
    grid.append([-1 for _ in range(W + 2)])

    grid[1][1] = 0

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

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

    while not tosearch.empty():
        y, x = tosearch.get()

        if (y, x) == (H, W):
            print(white - (grid[H][W] + 1))
            break

        for move in movement:
            ny, nx = y + move[0], x + move[1]

            if grid[ny][nx] == -2:
                grid[ny][nx] = grid[y][x] + 1
                tosearch.put((ny, nx))
    else:
        print(-1)



if __name__ == '__main__':
    main()