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
H, W = map(int, input().split())
G = [list(input()) for i in range(H)]


first_black = sum([row.count('
que = deque([(0, 0)])
dist = [[-1] * W for i in range(H)]
dist[0][0] = 0
direction = [(0, 1), (0, -1), (1, 0), (-1, 0)]

while que:
    nh, nw = que.pop()
    for dh, dw in direction:
        if not ((0 <= nh + dh < H) & (0 <= nw + dw < W)):
            continue
        if G[nh + dh][nw + dw] == '
            continue
        if dist[nh + dh][nw + dw] > 0:
            continue

        dist[nh + dh][nw + dw] = dist[nh][nw] + 1
        que.appendleft((nh + dh, nw + dw))


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

Solution (Python):





from collections import deque

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

white_panel_cnt = 0
for y in range(H):
    for x in range(W):
        if maze[y][x] == '.':
            white_panel_cnt += 1
que = deque()


sx,sy,gx,gy = (0,0,W-1,H-1)
que.append((sx,sy))
distance_from_start = [[-1]*W for _ in range(H)]
distance_from_start[sy][sx] = 0
move = [[1,0],[-1,0],[0,1],[0,-1]]

def minimum_distance():
    while len(que) != 0:
        x,y = que.popleft()
        
            
        if x == gx and y == gy:
            return distance_from_start[y][x]
        for i in range(4):
            next_x = x + move[i][0]
            next_y = y + move[i][1]
            
            if next_x < 0 or next_x >= W or next_y < 0 or next_y >= H or distance_from_start[next_y][next_x] != -1 or maze[next_y][next_x] == '
                continue
            
            distance_from_start[next_y][next_x] = distance_from_start[y][x] + 1
            que.append((next_x,next_y))
        
            

distance = minimum_distance()

if distance == None:
    score = -1
else :
    score = white_panel_cnt-(distance+1)

print(score)

Solution (Python):

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

M=[]

w_count=0

for i in range(H):
    s=input()
    m=[]
    for j in range(W):
        if s[j]=='.':
            m.append(0)
            w_count+=1
        else:
            m.append(1)
    M.append(m)

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

for i in range(H):
    for j in range(W):
        if M[i][j]==0:
            if i!=H-1:
                if M[i+1][j]==0:
                    path[i][j].append([i+1,j])
                    path[i+1][j].append([i,j])
            if j!=W-1:
                if M[i][j+1]==0:
                    path[i][j].append([i,j+1])
                    path[i][j+1].append([i,j])

M_path = [[10**27 for j in range(W)] for i in range(H)]
M_checked = [[False for j in range(W)] for i in range(H)]
M_path[0][0]=0

from collections import deque

Q=deque([[0,0]])
M_checked[0][0]=True
while len(Q)>0:
    i,j=Q.pop()
    mp = M_path[i][j]
    for p in path[i][j]:
        if not M_checked[p[0]][p[1]]:
            M_checked[p[0]][p[1]]=True
            Q.appendleft(p)
            if mp+1 < M_path[p[0]][p[1]]:
                M_path[p[0]][p[1]] = mp+1

if M_path[H-1][W-1]<10**27:
    print(w_count-(M_path[H-1][W-1]+1))
else:
    print(-1)

Solution (Python):
import Queue
def main():
    H,W=map(int,raw_input().split())
    s=[raw_input() for i in range(H)]
    q=Queue.Queue()
    visited=[[False]*W for _ in range(H)]
    dist=[[1145141919810]*W for _ in range(H)]
    visited[0][0]=True
    dist[0][0]=0
    dx=[1,0,-1,0]
    dy=[0,1,0,-1]
    q.put((0,0))

    while not q.empty():
        x,y=q.get()
        for i in range(4):  
            xx=x+dx[i]
            yy=y+dy[i]
            if (not 0<=xx<H) or (not 0<=yy<W): continue
            if s[xx][yy] == "
            if visited[xx][yy]:continue
            visited[xx][yy]=True
            dist[xx][yy]=dist[x][y]+1
            q.put((xx,yy))
    if not visited[H-1][W-1]:
        print(-1)
        return
    use=[[False]*W for _ in range(H)]
    use[H-1][W-1]=True
    use[0][0]=True
    (x,y)=(H-1, W-1)
    while (x,y) != (0,0):
        use[x][y]=True
        mpos=(-1,-1)
        mval=1145141919
        for i in range(4):
            xx=x+dx[i]
            yy=y+dy[i]
            if (not 0<=xx<H) or (not 0<=yy<W): continue     
            if dist[xx][yy] < mval:
                mpos=(xx,yy)
                mval=dist[xx][yy]
        x,y=mpos
    cnt=0
    for x in range(H):
        for y in range(W):
            if s[x][y] == "." and not use[x][y]: cnt+=1
    print(cnt)
main()

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


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

is_visit = [[False for _ in range(W)] for _ in range(H)]

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


def get_shortest_step():
    shortest_step = -1
    while len(next_search) > 0:
        nowx, nowy, now_step = next_search.pop()
        if is_visit[nowx][nowy]:
            continue
        is_visit[nowx][nowy] = True

        for stepx, stepy in [(1, 0), (0, 1), (-1, 0), (0, -1)]:
            nextx = nowx + stepx
            nexty = nowy + stepy
            if nextx == H-1 and nexty == W-1:
                shortest_step = now_step + 1
                return shortest_step
            if 0 <= nextx < H and 0 <= nexty < W:
                if is_visit[nextx][nexty] or area_info[nextx][nexty] == "
                    continue
                next_search.appendleft([nextx, nexty, now_step+1])
    return shortest_step


shortest_step = get_shortest_step()
c = Counter("".join(area_info))
if shortest_step == -1:
    print("-1")
else:
    print(c['.'] - shortest_step - 1)

Solution (Python):


from queue import Queue

h,w = map(int,input().split())
black, white = 0,0
s = [[0] * w for _ in range(h)]
for i in range(h):
    s[i] = list(input())
    for j in range(w):
        if s[i][j] == ".":
            white += 1
        else:
            black += 1

def bfs():
    global ans,checked
    while not que.empty():
        xy = que.get()
        if xy[0] == w - 1 and xy[1] == h - 1:
            ans = checked[xy[1]][xy[0]]
            return
        for i in range(-1,2):
            for j in range(-1,2):
                if i == j or i == -j:
                    continue
                if 0 <= xy[0] + i < w and 0 <= xy[1] + j < h:
                    if checked[xy[1] + j][xy[0] + i] == -1 and s[xy[1] + j][xy[0] + i] == ".":
                        checked[xy[1] + j][xy[0] + i] = checked[xy[1]][xy[0]] + 1
                        que.put([xy[0] + i,xy[1] + j])

que = Queue()
ans = -1
checked = [[-1] * w for _ in range(h)]
checked[0][0] = 0
que.put([0,0])

bfs()
if ans != -1:
    print(white - ans - 1)
else:
    print(-1)

Solution (Python):
xy=[(1,0),(-1,0),(0,1),(0,-1)]
ans=chk=0
h,w=map(int,input().split())
d=[[0]*w for i in range(h)]
l=[]
for i in range(h):
    a=input()
    chk+=a.count("
    l.append(a)
p=set([(0,0)])
while len(p):
    a,b=p.pop()
    for y,x in xy:
        y+=a
        x+=b
        if 0<=y<h and 0<=x<w and l[y][x]!="
            if d[y][x]==0 or d[y][x]>d[a][b]+1:
                d[y][x]=d[a][b]+1
                p.add((y,x))

print(-1 if d[h-1][w-1]==0 else h*w-1-chk-d[h-1][w-1])

Solution (Python):
import queue

h, w = [int(i) for i in input().split(" ")]
s = ["" for i in range(0, h)]

for i in range(0, h):
    s[i] = input()

b = [[False for j in range(0, w)] for i in range(0, h)]

c = 0
for i in range(0, h):
    for j in range(0, w):
        if s[i][j] == ".":
            c += 1

q = queue.Queue()
q.put([0, 0, 0])
b[0][0] = True

def addq(i, j, d):
    global b
    global q
    if 0 <= i and i < h and 0 <= j and j < w and not b[i][j] and s[i][j] == ".":
        b[i][j] = True
        q.put([i, j, d])

f = False
while not q.empty():
    qi = q.get()
    if qi[0] == h - 1 and qi[1] == w - 1:
        f = True
        print(c - qi[2] - 1)
        break
    i = qi[0]
    j = qi[1]
    addq(i + 1, j, qi[2] + 1)
    addq(i, j + 1, qi[2] + 1)
    addq(i - 1, j, qi[2] + 1)
    addq(i, j - 1, qi[2] + 1)

if not f:
    print(-1)

Solution (Python):
import queue
h, w = map(int, input().split())
d=[(0, 1), (1, 0), (0, -1), (-1, 0)]
s=[list(input()) for i in range(h)]
m=[[-1]*w for i in range(h)]
m[0][0]=1
q = queue.Queue()
q.put((0, 0))
while not q.empty():
    p=q.get()
    for i in range(4):
        x=p[0]+d[i][0]
        y=p[1]+d[i][1]
        if 0<=x<h and 0<=y<w and m[x][y]<0 and s[x][y]=='.':
            q.put((x, y))
            m[x][y]=m[p[0]][p[1]]+1
dis=m[h-1][w-1]
c=sum(si.count('.') for si in s)
print(c-dis if dis>0 else -1)

Solution (Python):
import queue

H, W = list(map(int, input().split()))
ans = H * W
L = []
for i in range(H):
	s = list(input())
	ans -= s.count("
	L.append(s)

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

def breadth(H, W, q, L, length, goal):
	while not q.empty():
		m = q.get()
		x = m[0]
		y = m[1]
		if [x, y] == goal:
			break

		if y - 1 >= 0:
			if length[y - 1][x] > length[y][x] + 1:
				if L[y - 1][x] == ".":
					length[y - 1][x] = length[y][x] + 1
					q.put([x, y - 1])
		if y + 1 <= H - 1:
			if length[y + 1][x] > length[y][x] + 1:
				if L[y + 1][x] == ".":
					length[y + 1][x] = length[y][x] + 1
					q.put([x, y + 1])
		if x - 1 >= 0:
			if length[y][x - 1] > length[y][x] + 1:
				if L[y][x - 1] == ".":
					length[y][x - 1] = length[y][x] + 1
					q.put([x - 1, y])
		if x + 1 <= W - 1:
			if length[y][x + 1] > length[y][x] + 1:
				if L[y][x + 1] == ".":
					length[y][x + 1] = length[y][x] + 1
					q.put([x + 1, y])
	return length[-1][-1]

q = queue.Queue()
q.put([0, 0])
goal = [W - 1, H - 1]
goal_len = breadth(H, W, q, L, length, goal)

if length[H - 1][W - 1] == float("inf"):
	print(-1)
else:
	print(ans - goal_len - 1)

Solution (Python):
from collections import deque

h, w = [int(item) for item in input().split()]
s = [input() for _ in range(h)]
dist = [[-1] * w for _ in range(h)]

black = 0
for line in s:
  black += line.count("

que = deque()
que.append([0,0])
dist[0][0] = 1
while que:
  x, y = que.popleft()
  for i, j in [(1,0), (-1,0), (0,1), (0,-1)]:
    nx = x + i
    ny = y + j
    if nx < 0 or nx >= h or ny < 0 or ny >= w:
      continue
    if s[nx][ny] == "
      continue
    if dist[nx][ny] == -1:
      dist[nx][ny] = dist[x][y] + 1
      que.append([nx, ny])

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

Solution (Python):
def serch(x,y,p):
    if x<0 or W<=y or y<0 or H<=x or meiro[x][y] =="
        return
    if memo[x][y]:
        p = [x,y]
        return
    memo[x][y] = 1
    kyo[x][y] = kyo[p[0]][p[1]] + 1
    p = [x,y]
    serch(x+1,y,p)
    serch(x-1,y,p)
    serch(x,y+1,p)
    serch(x,y-1,p)
H,W = list(map(int,input().split()))
sx,sy = 0,0
gx,gy = H-1,W-1
meiro = [list(input()) for l in range(H)]
counter = 0
for a in range(H):
    for b in range(W):
        n = 1 if meiro[a][b] =="." else 0
        counter += n
dx = [1,0,-1,0]
dy = [0,1,0,-1]
stk = [(sx,sy)]

memo =[[0 for i in range(W)] for l in range(H)]
memo[sx][sy]=1
dis =[[0 for i in range(W)] for l in range(H)]
while stk:
    x,y = stk.pop(0)
    for i in range(4):
        xx,yy = x+dx[i],y+dy[i]
        if xx<0 or W<=yy or yy<0 or H<=xx or meiro[xx][yy] =="
            continue
        dis[xx][yy] = dis[x][y]+1
        stk.append((xx,yy))
        memo[xx][yy] = 1
if dis[gx][gy]==0:
    print(-1)
else:
    print(counter-dis[gx][gy]-1)

Solution (Python):
from queue import Queue

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

D = [[0] * W for _ in range(H)]
num = 0
for i in range(H):
  for j in range(W):
    if s[i][j] == y:
      num += 1
    else:
      D[i][j] = -1

def setWall(D, x):
  H = len(D)
  W = len(D[0]) + 2
  D = [[x] * W] + [[x] + [i for i in j] + [x] for j in D] + [[x] * W] 
  return D

D = setWall(D, -1)

D[1][1] = 1
Q = Queue()
Q.put([1, 1])
while Q.empty() != True:
  x, y = Q.get()
  t = D[x][y]
  for i in (-1, 1):
    for j in (0, 1):
      a = j * i
      b = (1 - j) * i
      if D[x + a][y + b] > t + 1 or D[x + a][y + b] == 0:
        D[x + a][y + b] = t + 1
        Q.put([x + a, y + b])

if D[H][W] == 0:
  print(-1)
else:
  print(num - D[H][W])

Solution (Python):
import queue
h,w = map(int,input().split())
s = [list(input()) for i in range(h)]
q = queue.Queue()
ma = [[0]*w for i in range(h)]
dyx = [[0,1],[0,-1],[1,0],[-1,0]]
white = 0
black = 0
for i in range(h):
    white += s[i].count(".")
black = h*w - white
q.put([0,0])
s[0][0] = "
flag = True
while flag:
    newq = queue.Queue()
    while not q.empty():
        y,x = q.get()
        for dy,dx in dyx:
            if 0 <= y + dy< h and 0 <= x +dx <w and s[y+dy][x+dx] != "
                s[y+dy][x+dx] = "
                newq.put([y+dy,x+dx])
                ma[y+dy][x+dx] = ma[y][x] +1
            if y+dy == h-1 and x+dx == w-1:
                flag = False
    q = newq
    if q.empty():
        break
if ma[h-1][w-1] == 0:
    print(-1)
else:print(white - ma[h-1][w-1]-1)

Solution (Python):



import sys


H,W = map(int, input().split())
num_w = -1
srch = []
for i in range(H):
  h = list(str(sys.stdin.readline().rstrip()))
  for j in range(W):
    if h[j] == ".":
      srch.append([i+1,j+1])
      num_w += 1

Cn = [[sys.maxsize for j in range(W+2)] for i in range(H+2)]
Cn[1][1] = 0
for _ in range(num_w):
  for i,j in srch[1:]:
    Cn[i][j] = min(Cn[i-1][j],Cn[i][j-1],Cn[i+1][j],Cn[i][j+1])+1

if Cn[H][W] < sys.maxsize:
  print(num_w - Cn[H][W])
else:
  print(-1)

Solution (Python):
import itertools
import math
from collections import deque
from collections import defaultdict
from itertools import permutations
import heapq
INF = float("inf")

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

dist = [[INF]*W for i in range(H)]
dist[0][0] = 0

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

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

while q:
    x,y = q.popleft()
    for dx,dy in dxy:
        nx,ny = x+dx ,y+dy
        if nx < 0 or ny <0 or nx >=W or ny >= H:
            continue
        if grid[ny][nx] == "
            continue
        if dist[ny][nx] < INF:
            continue
        q.append((nx,ny))
        dist[ny][nx] = dist[y][x] + 1
ans = 0
for i in range(H):
    ans += grid[i].count(".")
if dist[H-1][W-1] == INF:
    print(-1)
else:
    print(ans-dist[H-1][W-1]-1)

Solution (Python):
H, W=map(int, input().split())
graph=[]
road=0
for i in range(H):
    s=list(input())
    road=road+s.count(".")
    graph.append(s)

not_visited=[]
not_visited=[[True for i in range(W)] for j in range(H)]
need_visited=[]
need_visited=[[0 for i in range(W)] for j in range(H)]
need_visited[H-1][W-1]=True
queue=[]

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

start_point=[0, 0]
queue.append(start_point)
while len(queue)!=0:
    now_point=queue.pop(0)
    for i in range(4):
        search_point=[now_point[0]+dx[i], now_point[1]+dy[i]]
        if 0<=search_point[0]<H and 0<=search_point[1]<W:
            if graph[search_point[0]][search_point[1]]!="
                not_visited[search_point[0]][search_point[1]]=False
                queue.append(search_point)
                need_visited[search_point[0]][search_point[1]]=need_visited[now_point[0]][now_point[1]]+1

if need_visited[H-1][W-1]==True:
    print(-1)
else:
    print(road-need_visited[H-1][W-1]-1)

Solution (Python):
from collections import deque

H, W = map(int, input().split())
maze = [input() for i in range(H)]
reached = [[0] * W for i in range(H)]
score = -1
count = 0

for i in range(H):
    count += maze[i].count('

que = deque([])
que.append([0, 0])

flag = False
while que:
    py, px = que.popleft()
    dy = (0, 1, 0, -1)
    dx = (1, 0, -1, 0)
    for j, i in zip(dy, dx):
        ny = py + j
        nx = px + i
        if ny < 0 or ny >= H or nx < 0 or nx >= W:
            continue
        if maze[ny][nx] == '
            continue
        if reached[ny][nx]:
            continue

        que.append([ny, nx])
        reached[ny][nx] += reached[py][px] + 1
        if ny == H-1 and nx == W-1:
            score = reached[ny][nx]
            flag = True
            break
    if flag:
        break

if flag:
    score = H * W - score - count - 1
    print(score)
else:
    print(score)

Solution (Python):
h,w=map(int,input().split())
s=[["
p=[[1,1]]
d=0
for i in range(1,h+1):
    for j in range(1,w+1):
        if s[i][j]==".":
            d+=1
s[1][1]="
k=0
while [h,w] not in p:
    k+=1
    g=[]
    for i in range(len(p)):
        x,y=p[i][0],p[i][1]
        if s[x-1][y]==".":
            s[x-1][y]="Q"
            g.append([x-1,y])
        if s[x+1][y]==".":
            s[x+1][y]="Q"
            g.append([x+1,y])
        if s[x][y+1]==".":
            s[x][y+1]="Q"
            g.append([x,y+1])
        if s[x][y-1]==".":
            s[x][y-1]="Q"
            g.append([x,y-1])
    else:
        p=g
        if len(p)==0:
            print(-1)
            break
else:
    print(d-k-1)

Solution (Python):
from collections import deque

H,W = map(int,input().split())
s = [['
black = 0
for h in range(H):
    S = input()
    for w in range(W):
        s[h+1][w+1] = S[w]
        if S[w] == '
            black += 1

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

def bfs(gh,gw):
    st = deque()
    sts = deque()
    push,pop = st.append, st.pop
    pushs,pops = sts.append, sts.pop
    cnt = 1
    push([-1,-1])
    pushs([-1,-1])
    push([1,1])
    g = 0
    while g < 1:
        t = 0
        for i in range(999999):
            now = pop()
            if now == [-1,-1]:
                push([-1,-1])
                break
            pushs(now)
        cnt += 1
        c = 0
        while t < 1:
            now = pops()
            
            if now == [-1,-1]:
                if c == 0:
                    return -1
                    break
                pushs([-1,-1])
                t = 1
                break
            c = 1

            
            for dx,dy in dxy:
                if s[now[0]+dx][now[1]+dy] == '
                    continue
                if [now[0]+dx,now[1]+dy] == [gh,gw]:
                    g = 1
                    
                    return H*W-black-cnt
                if s[now[0]+dx][now[1]+dy] == '.':
                    push([now[0]+dx,now[1]+dy])
                    s[now[0]+dx][now[1]+dy] = '

print(bfs(H,W))

Solution (Python):
from collections import deque

H,W = map(int,input().split())
s = [['
black = 0
for h in range(H):
    S = input()
    for w in range(W):
        s[h+1][w+1] = S[w]
        if S[w] == '
            black += 1

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

def bfs(gh,gw):
    st = deque()
    sts = deque()
    push,pop = st.append, st.pop
    pushs,pops = sts.append, sts.pop
    cnt = 1
    push([-1,-1])
    pushs([-1,-1])
    push([1,1])
    g = 0
    while g < 1:
        t = 0
        for i in range(999999):
            now = pop()
            if now == [-1,-1]:
                push([-1,-1])
                break
            pushs(now)
        cnt += 1
        c = 0
        while t < 1:
            now = pops()
            
            if now == [-1,-1]:
                if c == 0:
                    return -1
                    break
                pushs([-1,-1])
                t = 1
                break
            c = 1

            
            for dx,dy in dxy:
                if s[now[0]+dx][now[1]+dy] == '
                    continue
                if [now[0]+dx,now[1]+dy] == [gh,gw]:
                    g = 1
                    
                    return H*W-black-cnt
                if s[now[0]+dx][now[1]+dy] == '.':
                    push([now[0]+dx,now[1]+dy])
                    s[now[0]+dx][now[1]+dy] = '

print(bfs(H,W))

Solution (Python):

from queue import Queue
h,w = map(int, input().split())
d = []
for _ in range(h):
    d.append(input())
cost = [[0]*w for _ in range(h)]

q = Queue()
q.put((0,0))
while not q.empty():
    hi,wi = q.get()
    if hi==h-1 and wi==w-1:
        break

    for dh,dw in [[0,1],[1,0],[0,-1],[-1,0]]:
        if h>dh+hi>=0 and w>dw+wi>=0 and d[dh+hi][dw+wi]==".":
            if cost[dh+hi][dw+wi]==0 or cost[dh+hi][dw+wi]>cost[hi][wi]+1:
                cost[dh+hi][dw+wi] = cost[hi][wi]+1
                q.put((dh+hi, dw+wi))

if cost[h-1][w-1]==0:
    print(-1)
    exit()

res = 0
for hi in range(h):
    for wi in range(w):
        if (hi==0 and wi==0) or (hi==h-1 and wi==-1):
            continue
        if d[hi][wi]==".":
            res += 1

print(res - cost[h-1][w-1])

Solution (Python):
import collections

H,W=map(int,input().split())
s=[]
for i in range(H):
    s.append(input())
ans=0
for i in range(H):
    ans+=s[i].count('.')

inf=1<<60
c=[[inf for j in range(W)] for i in range(H)]
c[0][0]=1

q=collections.deque()
q.append((0,0))
try:
    while True:
        y,x=q.popleft()
        if x>0 and s[y][x-1]=='.' and c[y][x-1]>c[y][x]+1:
            c[y][x-1]=c[y][x]+1
            q.append((y,x-1))
        if x<W-1 and s[y][x+1]=='.' and c[y][x+1]>c[y][x]+1:
            c[y][x+1]=c[y][x]+1
            q.append((y,x+1))
        if y>0 and s[y-1][x]=='.' and c[y-1][x]>c[y][x]+1:
            c[y-1][x]=c[y][x]+1
            q.append((y-1,x))
        if y<H-1 and s[y+1][x]=='.' and c[y+1][x]>c[y][x]+1:
            c[y+1][x]=c[y][x]+1
            q.append((y+1,x))
except IndexError:
    pass
if c[H-1][W-1]==inf:
    print(-1)
else:
    print(ans-c[H-1][W-1])

Solution (Python):
H, W = map(int, input().split())

LARGE_VALUE = 100000
Mij = [[0] * W for _ in range(H)]
space_count = 0
for i in range(H):
    s = input()
    for j in range(W):
        if s[j] == ".":
            space_count += 1
            Mij[i][j] = LARGE_VALUE
        else:
            Mij[i][j] = -1

dirs = [[1, 0], [0, 1], [-1, 0], [0, -1]]

queue = [[0, 0]]

def search():
    while len(queue):
        p = queue[0]
        del queue[0]
        i = p[0]
        j = p[1]
        step = Mij[i][j]

        for d in dirs:
            i2 = i + d[0]
            j2 = j + d[1]
            if 0 <= i2 < H and 0 <= j2 < W:
                if step + 1 < Mij[i2][j2]:
                    Mij[i2][j2] = step + 1
                    queue.append([i2, j2])

Mij[0][0] = 1
search()
total_steps = Mij[H - 1][W - 1]
if total_steps == LARGE_VALUE:
    print(-1)
else:
    print(space_count - total_steps)

Solution (Python):

from collections import defaultdict
from collections import deque
from heapq import heappush, heappop
import sys
import math
import bisect
import random
def LI(): return list(map(int, sys.stdin.readline().split()))
def I(): return int(sys.stdin.readline())
def LS():return list(map(list, sys.stdin.readline().split()))
def S(): return list(sys.stdin.readline())[:-1]
def IR(n):
    l = [None for i in range(n)]
    for i in range(n):l[i] = I()
    return l
def LIR(n):
    l = [None for i in range(n)]
    for i in range(n):l[i] = LI()
    return l
def SR(n):
    l = [None for i in range(n)]
    for i in range(n):l[i] = S()
    return l
def LSR(n):
    l = [None for i in range(n)]
    for i in range(n):l[i] = SR()
    return l
sys.setrecursionlimit(1000000)
mod = 1000000007



def A():
    return


def B():
    return


def C():
    return


def D():
    h,w = LI()
    s = SR(h)
    white = 0
    for i in range(h):
        white += s[i].count(".")
    bfs_map = [[-1 for i in range(w)] for j in range(h)]
    d = [[0,1],[0,-1],[1,0],[-1,0]]
    bfs_map[0][0] = 0
    q = deque()
    q.append([0,0])
    while q:
        y,x = q.popleft()
        for dy,dx in d:
            y_ = y+dy
            x_ = x+dx
            if 0 <= y_ < h and 0 <= x_ < w:
                if s[y_][x_] == "." and bfs_map[y_][x_] < 0:
                    bfs_map[y_][x_] = bfs_map[y][x]+1
                    q.append([y_,x_])
    if bfs_map[h-1][w-1] < 0:
        print(-1)
        quit()
    print(white-1-bfs_map[h-1][w-1])

def E():
    return


def F():
    return


def G():
    return


def H():
    return


if __name__ == "__main__":
    D()

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


def bfs():
    q = [(0, 0, 1)]
    m = [[0 for _ in range(W)] for _ in range(H)]
    while len(q) > 0:
        x, y, c = q.pop(0)
        for xx, yy in [(x + 1, y), (x, y + 1), (x - 1, y), (x, y - 1)]:
            if (H, W) == (yy + 1, xx + 1):
                return c + 1
            if 0 <= yy < H and 0 <= xx < W and S[yy][xx] == '.' and \
                    m[yy][xx] == 0:
                q.append((xx, yy, c + 1))
                m[yy][xx] = 1
    return -1


def main():
    dc = 0
    for i in range(H):
        dc += S[i].count('.')
    c = bfs()
    if c == -1:
        print(-1)
    else:
        print(dc - c)


main()

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


def bfs():
    q = [(0, 0, 1)]
    m = []
    while len(q) > 0:
        x, y, c = q.pop(0)
        for xx, yy in [(x + 1, y), (x, y + 1), (x - 1, y), (x, y - 1)]:
            if (H, W) == (yy + 1, xx + 1):
                return c + 1
            if 0 <= yy < H and 0 <= xx < W and S[yy][xx] == '.' and \
                    (xx, yy) not in m:
                m.append((xx, yy))
                q.append((xx, yy, c + 1))
    return -1


def main():
    dc = 0
    for i in range(H):
        for j in range(W):
            if S[i][j] == '.':
                dc += 1
    c = bfs()
    if c == -1:
        print(-1)
    else:
        print(dc - c)


main()

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


def bfs():
    q = [(0, 0, 1)]
    m = []
    while len(q) > 0:
        x, y, c = q.pop(0)
        for xx, yy in [(x + 1, y), (x, y + 1), (x - 1, y), (x, y - 1)]:
            if (H, W) == (yy + 1, xx + 1):
                return c + 1
            if 0 <= yy < H and 0 <= xx < W and S[yy][xx] == '.' and \
                    (xx, yy) not in m:
                m.append((xx, yy))
                q.append((xx, yy, c + 1))
    return -1


def main():
    ans = 0
    for i in range(H):
        ans += S[i].count('.')
    c = bfs()
    if c == -1:
        print(-1)
    else:
        print(ans - c)


main()

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


def bfs():
    q = [(0, 0)]
    nq = []
    m = []
    c = 1
    while len(q) > 0:
        while len(q) > 0:
            x, y = q.pop(0)
            for xx, yy in [(x + 1, y), (x, y + 1), (x - 1, y), (x, y - 1)]:
                if (H, W) == (yy + 1, xx + 1):
                    return c + 1
                if 0 <= yy < H and 0 <= xx < W and S[yy][xx] == '.' and \
                        (xx, yy) not in m:
                    m.append((xx, yy))
                    nq.append((xx, yy))
        q = nq
        nq = []
        c += 1
    return -1


def main():
    ans = 0
    for i in range(H):
        ans += S[i].count('.')
    c = bfs()
    if c == -1:
        print(-1)
    else:
        print(ans - c)


main()

Solution (Python):
from queue import Queue


def bfs(s):
    q = Queue()
    q.put(((0,0), 0))
    found = set()
    while q.qsize() > 0:
        x, nsteps = q.get()
        if x in found:
            continue
        found.add(x)
        for d in [(1, 0), (0, 1), (-1, 0), (0, -1)]:
            y = (x[0]+d[0], x[1]+d[1])
            if y[0] < 0 or y[0] >= H or y[1] < 0 or y[1] >= W:
                continue
            if s[y[0]][y[1]] == '
                continue
            if y == (H-1, W-1):
                return nsteps+1
            if y in found:
                continue
            q.put((y, nsteps+1))
    return -1




H, W = list(map(int, input().split(' ')))
s = []
nwhites = 0
for i in range(H):
    s.append([c for c in input()])

for i in range(H):
    for j in range(W):
        if s[i][j] == '.':
            nwhites += 1

nsteps = bfs(s)

if nsteps == -1:
    print(-1)
else:
    print(nwhites - nsteps - 1)

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

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

D = [[-1] * W for i in range(H)]
dx = [1, 0, -1, 0]
dy = [0, 1, 0, -1]

def bfs():
    Q = []
    Q.append([0, 0])
    D[0][0] = 0
    
    while Q != []:
        p = Q.pop(0)
        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 < H and 0 <= ny < W and S[nx][ny] != '
                Q.append([nx, ny])
                D[nx][ny] = D[p[0]][p[1]] + 1
                
    return D[H - 1][W - 1]

x = bfs()

if x == -1:
    print(-1)
else:
    print(cnt - x - 1)

Solution (Python):
from collections import deque

def bfs(board, visited, gh, gw):
    turn = 0
    queue = deque([[0, 0, turn]])
    while queue:
        h, w, turn = queue.popleft()
        if h == gh-1 and w == gw-1:
            return turn
        for i, j in ([1,0],[-1,0],[0,1],[0,-1]):
            new_h, new_w = h+i, w+j
            if new_h >= gh or new_h < 0 or new_w >= gw or new_w < 0:
                continue
            elif board[new_h][new_w] != "
                visited[new_h][new_w] = "o"
                queue.append([new_h, new_w, turn+1])
    return -1

def main():
    H, W = map(int,input().split())
    board = []
    for _ in range(H):
        board.append(list(input()))
    black = 0
    for i in range(H):
        for j in range(W):
            if board[i][j] == "
                black += 1
    visited = [["x"]*W for _ in range(H)]
    path_area = bfs(board, visited, H, W) + 1
    if path_area:
        print(H*W-path_area-black)
    else:
        print(-1)
                
    
    
if __name__ == "__main__":
    main()