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



Sample input:
3 3
..#
#..
...


Sample output:
2

Submission status: Accepted

Solution code:
from collections import deque

def bfs(maze, visited, sy, sx, gy, gx):
    H, W = len(maze), len(maze[0])
    queue = deque([[sy, sx]])
    visited[sy][sx] = 0
    while queue:
        y, x = queue.popleft()
        if [y, x] == [gy, gx]:
            return visited[y][x]
        for j, k in ([1, 0], [-1, 0], [0, 1], [0, -1]):
            new_y, new_x = y+j, x+k
            if 0<=new_y<=H-1 and 0<=new_x<=W-1:
                if maze[new_y][new_x] == "." and                 visited[new_y][new_x] == -1:
                    visited[new_y][new_x] = visited[y][x] + 1
                    queue.append([new_y, new_x])
    return False

if __name__ == "__main__":
    H, W = map(int, input().split())
    sy, sx = 0, 0
    gy, gx = H-1, W-1

    maze = [input() for _ in range(H)]
    visited = [[-1]*W for _ in range(H)]
    min_root = bfs(maze, visited, sy, sx, gy, gx)
    
    if min_root:
    	white = 0
    	for raw in maze:
    		white += raw.count('.')
    	print(white-min_root-1)
    else:
    	print(-1)

Submission status: Accepted

Solution code:
H, W = map(int, input().split())
Map = ['' for i in range(H)]
default = 0
for i in range(H):
  Map[i] = input()
  default += Map[i].count('#')
D = [[H * W + 1 for j in range(W)] for i in range(H)]
D[0][0] = 0
Q = [[0, 0]]
while Q:
  x, y = Q[0]
  Q = Q[1:]
  if x > 0 and Map[x - 1][y] == '.' and D[x][y] + 1 < D[x - 1][y]:
    D[x - 1][y] = D[x][y] + 1
    Q += [[x - 1, y]]
  if x < H - 1 and Map[x + 1][y] == '.' and D[x][y] + 1 < D[x + 1][y]:
    D[x + 1][y] = D[x][y] + 1
    Q += [[x + 1, y]]
  if y > 0 and Map[x][y - 1] == '.' and D[x][y] + 1 < D[x][y - 1]:
    D[x][y - 1] = D[x][y] + 1
    Q += [[x, y - 1]]
  if y < W - 1 and Map[x][y + 1] == '.' and D[x][y] + 1 < D[x][y + 1]:
    D[x][y + 1] = D[x][y] + 1
    Q += [[x, y + 1]]
if D[H - 1][W - 1] < H * W - 1:
  print(H * W - D[H - 1][W - 1] - default - 1)
else:
  print(-1)

Submission status: Accepted

Solution code:
from collections import deque
H,W = list(map(int,input().split()))
L = [list(input()) for _ in range(H)]  #L[H][W]
s = sum(l.count('.') for l in L)
dd = [(0,1),(0,-1),(1,0),(-1,0)]

res = None
que = deque([(0,0,0)])
used = {(0,0)}
while que:
    i,j,cost = que.popleft()
    if i == H-1 and j == W-1:
        res = cost
        break
    for di,dj in dd:
        ni = i+di; nj = j+dj
        if not(0<=ni<H) or not (0<=nj<W) or L[ni][nj]=='#' or (ni,nj) in used:
            continue
        que.append((ni,nj,cost+1))
        used.add((ni,nj))
if res:
    print(s-res-1)
else:
    print(-1)

Submission status: Accepted

Solution code:
import sys
import queue

H,W = map(int,input().split())
white = 0
maze = [['#']*(W+2)]
for y in range(H):
	li = list(input())
	white += li.count('.')
	maze.append(['#'] + li + ['#'])
maze.append(['#']*(W+2))



def check(x,y,n):
	if x == W and y == H:
		print (white - n - 1)
		sys.exit()
	elif maze[y][x] == '.':
		maze[y][x] = n
		q.put([x-1,y,n+1])
		q.put([x+1,y,n+1])
		q.put([x,y-1,n+1])
		q.put([x,y+1,n+1])
	else:
		return

q = queue.Queue()
q.put([1,1,0])
while not q.empty():
	x,y,n = q.get()
	check(x,y,n)

print(-1)

Submission status: Accepted

Solution code:
import sys
import queue

H,W = map(int,input().split())
white = 0
maze = [['#']*(W+2)]
for y in range(H):
	li = list(input())
	white += li.count('.')
	maze.append(['#'] + li + ['#'])
maze.append(['#']*(W+2))



def check(x,y,n):
	if 1 <= x < W+1 and 1 <= y < H+1:
		if x == W and y == H:
			print (white - n - 1)
			sys.exit()
		elif maze[y][x] == '.':
			maze[y][x] = n
			q.put([x-1,y,n+1])
			q.put([x+1,y,n+1])
			q.put([x,y-1,n+1])
			q.put([x,y+1,n+1])
		else:
			return
	else:
		return

q = queue.Queue()
q.put([1,1,0])
while not q.empty():
	x,y,n = q.get()
	check(x,y,n)

print(-1)

Submission status: Accepted

Solution code:
import sys
import queue

H,W = map(int,input().split())
white = 0
maze = []
for y in range(H):
	li = list(input())
	white += li.count('.')
	maze.append(li)

def check(x,y,n):
	if 0 <= x < W and 0 <= y < H:
		if x == W-1 and y == H-1:
			print (white - n - 1)
			sys.exit()
		elif maze[y][x] == '.':
			maze[y][x] = n
			q.put([x-1,y,n+1])
			q.put([x+1,y,n+1])
			q.put([x,y-1,n+1])
			q.put([x,y+1,n+1])
		else:
			return
	else:
		return

q = queue.Queue()
q.put([0,0,0])
while not q.empty():
	x,y,n = q.get()
	check(x,y,n)

print(-1)

Submission status: Accepted

Solution code:
import sys
import queue

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


white = 0
	
maze = []

for y in range(H):
	li = list(input())
	white += li.count('.')
	maze.append(li)

if maze[0][0] == '#' or maze[H-1][W-1] == '#':
	print (-1)
	sys.exit()

	
maze[H-1][W-1] = 'g'
	
q = queue.Queue()
q.put([0,0,0])

def check(x,y,n):
	if 0 <= x < W and 0 <= y < H:
		if maze[y][x] == 'g':
			print (white - n - 1)
			sys.exit()
		elif maze[y][x] == '.':
			maze[y][x] = n
			q.put([x-1,y,n+1])
			q.put([x+1,y,n+1])
			q.put([x,y-1,n+1])
			q.put([x,y+1,n+1])
		else:
			return
	else:
		return


while not q.empty():
	x,y,n = q.get()
	check(x,y,n)
	
print(-1)

Submission status: Accepted

Solution code:
from collections import deque
h,w=map(int,input().split())
l=[]
v=0

for _ in range(h):
  b=[0 if i=="." else 1 for i in input()]
  v+=b.count(1)
  l.extend([b])

dq=deque([])
dq.append((0,0,1))

while dq:
  x,y,d=dq.popleft()
  if x==w-1 and y==h-1:break
  for (dx,dy) in zip([-1,1,0,0],[0,0,-1,1]):
    nx=x+dx
    ny=y+dy
    if 0<=nx<w and 0<=ny<h and not l[ny][nx]:
      l[ny][nx]=2
      dq.append((nx,ny,d+1))

if x==w-1 and y==h-1:
  print(h*w-v-d)
else:
  print(-1)

Submission status: Accepted

Solution code:
R, C = list(map(int, input().split()))
sy, sx = 2, 2
gy, gx = R, C

meiro = ["#" + input() + "#" for _ in range(R)]
meiro = ["#"*(C+2)] + meiro + ["#"*(C+2)]

kyori = [[int(0) for x in range(C+2)] for _ in range(R+2)]
kyori[sy-1][sx-1] = 0

visited = [[sy-1,sx-1]]
que = [[sy-1,sx-1]]

while True:
    x = que[0][1]
    y = que[0][0]
    que.pop(0)
    try:
        if meiro[y][x+1] == "." and [y,x+1] not in visited:
            que.append([y,x+1])
            visited.append([y,x+1])
            kyori[y][x+1] = kyori[y][x] + 1
        if meiro[y+1][x] == "." and [y+1,x] not in visited:
            que.append([y+1,x])
            visited.append([y+1,x])
            kyori[y+1][x] = kyori[y][x] + 1
        if meiro[y][x-1] == "." and [y,x-1] not in visited:
            que.append([y,x-1])
            visited.append([y,x-1])
            kyori[y][x-1] = kyori[y][x] + 1
        if meiro[y-1][x] == "." and [y-1,x] not in visited:
            que.append([y-1,x])
            visited.append([y-1,x])
            kyori[y-1][x] = kyori[y][x] + 1
    except:
        IndexError
    if que == []:
        break

if kyori[R][C] == 0:
    print(-1)
    exit(0)

t = 0
for k in range(1,R+1):
    t += meiro[k].count("#")-2

print(R*C-kyori[R][C]-t-1)

Submission status: Accepted

Solution code:
import heapq
import itertools
inf = 10 * 18

H, W = map(int, input().split())
map = [input() for _ in range(H)]
heuristic = {(i, j): int(((H - i) ** 2 + (W - j) ** 2) ** 0.5) for j in range(W) for i in range(H)}
count_white = sum([s.count(".") for s in map])

def astar(init_pos, goal):
    passed_list = [init_pos]
    init_score = distance(passed_list) + heuristic.setdefault(init_pos, inf)
    checked = {init_pos: init_score}
    searching_heap = []
    heapq.heappush(searching_heap, (init_score, passed_list))
    while len(searching_heap) > 0:

        score, passed_list = heapq.heappop(searching_heap)
        last_passed_pos = passed_list[-1]
        if last_passed_pos == goal:
            return passed_list
        for pos in nexts(last_passed_pos):
            new_passed_list = passed_list + [pos]
            pos_score = distance(new_passed_list) +  heuristic.setdefault(pos, inf)
            if pos in checked and checked[pos] <= pos_score:
                continue

            checked[pos] = pos_score
            heapq.heappush(searching_heap, (pos_score, new_passed_list))

    return []

def distance(path):
    return len(path)

def nexts(pos):
    i = pos[0]
    j = pos[1]
    res = []
    
    for p in [(i + 1, j), (i - 1, j), (i, j - 1), (i, j + 1)]:
        if 0<=p[0]<=H-1 and 0<=p[1]<=W-1 and map[p[0]][p[1]] != "#":
            res.append(p)

    return res
    
path = astar((0,0), (H-1,W-1))

if len(path) == 0:
    print(-1)
else:
    print(count_white - len(path))

Submission status: Accepted

Solution code:
from collections import deque

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

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

def bfs():
    visited = [[False for _ in range(W)] for _ in range(H)]
    dist = [[0 for _ in range(W)] for _ in range(H)]
    routes = deque()
    routes.append((0, 0))
    visited[0][0] = True

    while len(routes) > 0:
        x, y = routes.popleft()
        for move in moves:
            cx, cy = x + move[0], y + move[1]
            if cx < 0 or cy < 0 or cx >= W or cy >= H or c[cy][cx] == '#' or visited[cy][cx]:
                continue
            if cx == W-1 and cy == H-1:
                return sum([line.count('.')for line in c]) - dist[y][x] - 2
            visited[cy][cx] = True
            routes.append((cx, cy))
            dist[cy][cx] = dist[y][x] + 1
    return -1

print(bfs())

Submission status: Accepted

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

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

def bfs():
    visited = [[False for _ in range(W)] for _ in range(H)]
    dist = [[0 for _ in range(W)] for _ in range(H)]
    routes = [(0, 0)]
    visited[0][0] = True

    while len(routes) > 0:
        x, y = routes.pop(0)
        for move in moves:
            cx, cy = x + move[0], y + move[1]
            if cx < 0 or cy < 0 or cx >= W or cy >= H or c[cy][cx] == '#' or visited[cy][cx]:
                continue
            if cx == W-1 and cy == H-1:
                return sum([line.count('.')for line in c]) - dist[y][x] - 2
            visited[cy][cx] = True
            routes.append((cx, cy))
            dist[cy][cx] = dist[y][x] + 1
    return -1

print(bfs())

Submission status: Accepted

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

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

def bfs():
    visited = [[False for _ in range(W)] for _ in range(H)]
    dist = [[[] for _ in range(W)] for _ in range(H)]
    routes = [(0, 0)]
    visited[0][0] = True

    hop_count = 0
    while len(routes) > 0:
        x, y = routes.pop(0)
        for move in moves:
            cx, cy = x + move[0], y + move[1]
            if cx < 0 or cy < 0 or cx >= W or cy >= H or c[cy][cx] == '#' or visited[cy][cx]:
                continue
            if cx == W-1 and cy == H-1:
                return sum([line.count('.')for line in c]) - len(dist[y][x]) - 2
            visited[cy][cx] = True
            routes.append((cx, cy))
            dist[cy][cx] += dist[y][x] + [(x, y)]
    return -1

print(bfs())

Submission status: Accepted

Solution code:
#!/usr/bin/python3

from collections import defaultdict, Counter
from itertools import product, groupby, count, permutations, combinations
from math import pi, sqrt
from collections import deque
from bisect import bisect, bisect_left, bisect_right
from string import ascii_lowercase
from functools import lru_cache
import sys
sys.setrecursionlimit(10000)
INF = float("inf")
YES, Yes, yes, NO, No, no = "YES", "Yes", "yes", "NO", "No", "no"
dy4, dx4 = [0, 1, 0, -1], [1, 0, -1, 0]


def inside(y, x, H, W):
    return 0 <= y < H and 0 <= x < W


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

    white = 0
    for _ in range(H):
        line = input()
        field.append(line)
        white += line.count(".")

    cost = [[INF] * W for _ in range(H)]
    cost[0][0] = 1
    q = deque()
    q.append((0, 0))
    while len(q) != 0:
        y, x = q.popleft()

        for i in range(4):
            ny, nx = y + dy4[i], x + dx4[i]

            if inside(ny, nx, H, W) and cost[ny][nx] == INF and field[ny][nx] == ".":
                cost[ny][nx] = cost[y][x] + 1
                q.append((ny, nx))

    if cost[-1][-1] == INF:
        print(-1)
    else:
        print(white - cost[-1][-1])


if __name__ == '__main__':
    main()

Submission status: Accepted

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

def bfs(maze,sy,sx,w,h):
    arrival = [[0 for i in range(w+2)]for k in range(h+2)]
    q = [[sy,sx]]
    arrival[q[0][0]][q[0][1]] = 1
	

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


h,w = map(int,input().split())
s = []
add = ["#" for i in range(w+2)]
s.append(add)
counter = 0
for i in range(h):
    stemp = list(input())
    for k in range(w):
        if stemp[k] == "#":
            counter += 1
    stemp.append("#")
    stemp.insert(0,"#")
    s.append(stemp)
s.append(add)


arrival = bfs(s,1,1,w,h)

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

Submission status: Accepted

Solution code:
from collections import Counter, deque
from itertools import product

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


def bfs():
    dist = [[float('inf') for _ in range(W)] for _ in range(H)]
    mx = [1, 0, -1, 0]
    my = [0, 1, 0, -1]

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

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

    while que:
        x, y = que.popleft()
        if x == gx and y == gy:
            break

        for dx, dy in zip(mx, my):
            nx = x + dx
            ny = y + dy
            if 0 <= nx < W and 0 <= ny < H:
                if maze[ny][nx] != '#' and dist[ny][nx] == float('inf'):
                    que.append((nx, ny))
                    dist[ny][nx] = dist[y][x] + 1

    return dist[gy][gx]


res = bfs()
if res == float('inf'):
    ans = -1
else:
    white = 0
    for i, j in product(range(H), range(W)):
        if maze[i][j] == '.':
            white += 1
    ans = white - res - 1
print(ans)

Submission status: Accepted

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

# re = max(-1, H * W - (H + W - 1) - black)

queue = [[0,0,1]] # h,w,深さ
check = [[0,0]]
root = 0
hCurrent, wCurrent = 0, 0
while True:
    root += 1
#    print(queue)
    if hCurrent == H - 1 and wCurrent == W - 1:
        break
    if len(queue) == 0:
        root = -1
        break

    hCurrent, wCurrent, depth = queue[0]
    queue.pop(0)

    if hCurrent < H - 1:
        if s[hCurrent + 1][wCurrent] != "#" and [hCurrent + 1, wCurrent] not in check:
            queue.append([hCurrent + 1, wCurrent, depth+1])
            check.append([hCurrent + 1, wCurrent])
    if wCurrent < W - 1:
        if s[hCurrent][wCurrent+1] != "#" and [hCurrent, wCurrent + 1] not in check:
            queue.append([hCurrent, wCurrent + 1,depth+1])
            check.append([hCurrent, wCurrent + 1])
    if hCurrent > 0:
        if s[hCurrent - 1][wCurrent] != "#" and [hCurrent - 1, wCurrent] not in check:
            queue.append([hCurrent - 1, wCurrent,depth+1])
            check.append([hCurrent - 1, wCurrent])
    if wCurrent > 0:
        if s[hCurrent][wCurrent - 1] != "#" and [hCurrent, wCurrent - 1] not in check:
            queue.append([hCurrent, wCurrent-1,depth+1])
            check.append([hCurrent, wCurrent-1])

if root == -1:
    re = -1
else:
    re = max(-1, H * W - depth - black)
    #re = H * W - black - root

print(re)

Submission status: Accepted

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

import heapq
def dijkstra(adj, n, st=1):
    dj = [2**64] * (n)
    dj[st] = 0
    q = []
    heapq.heappush(q, (0, st))
    while q:
        fc, fn = heapq.heappop(q)
        if dj[fn] < fc: continue
        for tn, lc in adj[fn]:
            if dj[fn] + lc < dj[tn]:
                dj[tn] = dj[fn] + lc
                heapq.heappush(q, (dj[tn], tn))
    return dj

def cid(x):
    return x[0] * W + x[1]

def cl(adj, x, y):
    xid = cid(x)
    yid = cid(y)
    adj[xid].append((yid, 1))
    adj[yid].append((xid, 1))

adj = dict([(x, []) for x in range(H*W)])
for i in range(H):
    for j in range(W):
        if S[i][j] == "#": continue
        ni = i + 1
        if ni < H and S[ni][j] == ".":
            cl(adj, (i, j), (ni, j))
        nj = j + 1
        if nj < W and S[i][nj] == ".":
            cl(adj, (i, j), (i, nj))

c = dijkstra(adj, H*W, cid((0,0)))
hwc = c[cid((H-1,W-1))]
print(-1 if hwc == 2**64 else H * W - sum(s.count("#") for s in S) - hwc - 1)

Submission status: Accepted

Solution code:
from collections import deque
H,W = map(int, input().split())
S = [list(input()) for _ in range(H)] # S[H][W]なのに注意
# 黒を白に変えられないので最短経路算出後に差っ引けばOK
# 早い話が迷路なので幅優先探索
whites = sum([i.count('#') for i in S])
S[0][0] = 0
goal = [H-1, W-1]
move = ((-1,0), (1,0), (0,-1), (0,1))
queue = deque()
queue.append((0,0))

while queue:
    now = queue.popleft()
    cnt = S[now[0]][now[1]] + 1
    for h,w in move:
        x,y = now[0]+h,now[1]+w
        if x < 0 or x >= H or y < 0 or y >= W:
            continue
        if S[x][y] == '.':
            S[x][y] = cnt
            queue.append((x,y))
if S[H-1][W-1] == '.':
    print(-1)
else:
    print(W*H - 1 - S[H-1][W-1] - whites)
exit(0)

Submission status: Accepted

Solution code:
H, W = map(int, raw_input().split())
s = []
w = 0
for i in range(H):
  l = raw_input()
  s.append(l)
  w += l.count(".")
C = []
for i in range(H):
  C.append([10000]*W)
C[0][0]=1
q = [(0,0)]
while q:
  i, j = q.pop(0)
  for d in [(+1,0),(-1,0),(0,+1),(0,-1)]:
    ni = i+d[0]
    nj = j+d[1]
    if 0<=ni<H and 0<=nj<W and s[ni][nj]=="." and C[i][j]+1<C[ni][nj]:
      C[ni][nj] = C[i][j]+1
      q.append((ni,nj))
if C[H-1][W-1]==10000:
  print -1
else:
  print w-C[H-1][W-1]

Submission status: Accepted

Solution code:
class BFS():
    def __init__(self, H, W, maze):
        self.H = H
        self.W = W
        self.maze = maze
        self.distance = [[0 for i in range(self.W)] for j in range(self.H)]
        self.sx = 0
        self.sy = 0
        self.gx = W-1
        self.gy = H-1

    def bfs(self):
        queue = []
        queue.insert(0, (self.sx, self.sy))

        self.distance[self.sx][self.sy] = 0

        while len(queue):
            x, y = queue.pop()

            if x == self.gx and y == self.gy:
                break

            for i in range(0, 4):
                nx, ny = x + [1, 0, -1, 0][i], y + [0, 1, 0, -1][i]

                if (0 <= nx and nx < self.W and 0 <= ny and ny < self.H and self.maze[ny][nx] != '#' and self.distance[ny][nx] == 0):
                    queue.insert(0, (nx, ny))
                    self.distance[ny][nx] = self.distance[y][x] + 1
        return self.distance[self.gy][self.gx]

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

bfs=BFS(H, W, sw)
distance=bfs.bfs()

init_white=0
for i in range(H):
    init_white+=sw[i].count('.')
print(init_white-(distance+1) if distance!=0 else -1)

Submission status: Accepted

Solution code:
from queue import Queue

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

dcount = -1
for h in range(H):
    for w in range(W):
        if C[h][w] == '.':
            dcount += 1

INF = 10 ** 6
D = [[INF] * W for i in range(H)]
D[0][0] = 0
q = Queue()
q.put((0, 0))

while q.qsize() > 0:
    h, w = q.get()
    if (h, w) == (H-1, W-1):
        break
    for dh, dw in zip((-1, 1, 0, 0), (0, 0, -1, 1)):
        if 0 <= h+dh < H and 0 <= w+dw < W and C[h+dh][w+dw] == '.' and D[h+dh][w+dw] == INF:
            D[h+dh][w+dw] = D[h][w] + 1
            q.put((h+dh, w+dw))

print(dcount - D[H-1][W-1] if D[H-1][W-1] != INF else -1)

Submission status: Accepted

Solution code:
MAX = 9999999
def m():
    h, w = map(int, input().split())
    s = []
    s.append(list(('#'*(w+2))))
    for j in range(h):
        s.append(list('#'+input()+'#'))
    s.append(list(('#' * (w + 2))))

    g = [[[] for _ in range(w+2)] for _ in range(h+2)]
    cnt = 0
    for i in range(1, h+1):
        for j in range(1, w+1):
            if s[i][j] == '#':
                cnt +=1
                continue
            if s[i][j+1] == '.':
                g[i][j].append((i, j+1))
            if s[i+1][j] == '.':
                g[i][j].append((i+1, j))
            if s[i][j-1] == '.':
                g[i][j].append((i, j-1))
            if s[i-1][j] == '.':
                g[i][j].append((i-1, j))

    def dijkstra():
        d = [[MAX for _ in range(w + 2)] for _ in range(h + 2)]
        p = [[MAX for _ in range(w + 2)] for _ in range(h + 2)]
        visited = [[-1 for _ in range(w + 2)] for _ in range(h + 2)]
        d[1][1] = 0
        p[1][1] = -1
        while True:
            mincost = MAX
            for i in range(1, h + 1):
                for j in range(1, w + 1):
                    if visited[i][j] != 1 and d[i][j] < mincost:
                        mincost = d[i][j]
                        u = (i,j)
            if mincost == MAX:
                break
            visited[u[0]][u[1]] = 1

            for i in range(1, h + 1):
                for j in range(1, w + 1):
                    if visited[i][j] != 1 and u in g[i][j]:
                        if d[u[0]][u[1]] +1 < d[i][j]:
                            d[i][j] = d[u[0]][u[1]] + 1
                            p[i][j] = u
                            visited[i][j] = 0
        return d
    ans = dijkstra()
    if ans[h][w] == MAX:
        return -1
    return (w*h) - ans[h][w] - cnt -1

print(m())

Submission status: Accepted

Solution code:
h, w = map(int, input().split())

white = 0
a = [[] for _ in range(h + 2)]
a[0] = [ '#' for _ in range(w + 2)]
a[h + 1] = [ '#' for _ in range(w + 2)]
for i in range(h):
    a[i + 1] = ['#'] + list(input()) + ['#']
    white += a[i + 1].count('.')

a[1][1] = '.'
a[h][w] = '.'

res = [[1,1]]
ans = 1
while 1:
    ans += 1
    temp = []
    for i, j in res:
        if a[i + 1][j] == '.':
            temp.append([i + 1, j])
        if a[i][j + 1] == '.':
            temp.append([i, j + 1])
        if a[i - 1][j] == '.':
            temp.append([i - 1, j])
        if a[i][j - 1] == '.':
            temp.append([i, j - 1])
        a[i][j] = '#'
    if len(temp) == 0:
        print('-1')
        exit()
    res = list(map(list, set(map(tuple, temp))))
    if [h, w] in res:
        break

print(white - ans)

Submission status: Accepted

Solution code:
class BFS():
    def __init__(self, H, W, maze):
        self.H = H
        self.W = W
        self.maze = maze
        self.distance = [[0 for i in range(self.W)] for j in range(self.H)]
        self.sx = 0
        self.sy = 0
        self.gx = W-1
        self.gy = H-1


    def bfs(self):
        queue = []
        queue.insert(0, (self.sx, self.sy))

        self.distance[self.sx][self.sy] = 0

        while len(queue):
            x, y = queue.pop()

            if x == self.gx and y == self.gy:
                break

            for i in range(0, 4):
                nx, ny = x + [1, 0, -1, 0][i], y + [0, 1, 0, -1][i]

                if (0 <= nx and nx < self.W and 0 <= ny and ny < self.H and self.maze[ny][nx] != '#' and self.distance[ny][nx] == 0):
                    queue.insert(0, (nx, ny))
                    self.distance[ny][nx] = self.distance[y][x] + 1
        return self.distance[self.gy][self.gx]

H, W = map(int, input().split())
maze = [list(input()) for _ in range(H)]
bfs = BFS(H,W,maze)
distance = bfs.bfs()
black = 0
for i in range(H):
    black += maze[i].count('#')

if distance == 0:
    print(-1)
else:
    print(H*W - (distance+1)-black)

Submission status: Accepted

Solution code:
 # time complexity: O(HW)
# space complexity: O(HW)

from collections import deque


H, W = [int(elem) for elem in input().split(' ')]
s_list = [tuple(input()) for _ in range(H)]
assert len(s_list) == H
assert len(s_list[0]) == W


def calc_num_white(s_list):
    num_white = sum([sum([1 if elem == "." else 0 for elem in row]) for row in s_list])
    return num_white


# BFS
visited = [[False] * W for _ in range(H)]
queue = deque([[[0, 0], [[0, 0]]]])
visited[0][0] = True
direction = ((-1, 0), (1, 0), (0, -1), (0, 1))
while queue:
    position, path = queue.popleft()
    y, x = position
    for dy, dx in direction:
        next_position = [y+dy, x+dx]
        if next_position[0] < 0 or next_position[0] >= H or next_position[1] < 0 or next_position[1] >= W:
            continue
        elif s_list[next_position[0]][next_position[1]] == "#":
            continue
        elif visited[next_position[0]][next_position[1]] == True:
            continue
        elif next_position == [H-1, W-1]:
            len_min_path = len(path) + 1
            num_white = calc_num_white(s_list)
            score = num_white - len_min_path
            print(score)
            exit(0)
        else:
            visited[next_position[0]][next_position[1]] = True
            queue.append([next_position, path+[next_position]])
print(-1)

Submission status: Accepted

Solution code:
from collections import deque

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

inp = []
for h in range(H):
    inp.append(input())

field = []
field.append(["#" for _ in range(W+2)])
for h in range(H):
    field.append(["#"] + list(inp[h]) + ["#"])    
field.append(["#" for _ in range(W+2)])


def bfs():
    que = deque([])
    next_h = [1,0,-1, 0]
    next_w = [0,1, 0,-1]
    
    que.append([0,1,1])
    
    while len(que) != 0:
        dist,h,w = que.popleft()
        if field[h][w] != ".":
            continue
        
        field[h][w] = str(dist)
        
        for i in range(4):
            if field[h+next_h[i]][w+next_w[i]] == ".":
                que.append([dist+1, h+next_h[i], w+next_w[i]])
            
    return field[H][W]
    

points = 0
for field_row in field:
    for point in field_row:
        if point == ".":
            points += 1


min_dist = bfs()

if min_dist == '.':
    print(-1)
else:
    print(points - int(min_dist) - 1)

Submission status: Accepted

Solution code:
from collections import Counter, deque
H, W = map( int, input().split())
S = [list(input()) for x in range(H)]
white = 0
for i in range(H):
    white += Counter(S[i])['.']
Goal = False
Able = True

path = 1
Sunuke = [[0,0]]
S[0][0] = '#'
while Goal == False and len(Sunuke) != 0:
    Sunuke_temp = Sunuke
    Sunuke = []
    path += 1
    for x in Sunuke_temp:
        i = x[0]
        j = x[1]
        if (min(i+1,H-1) == H-1 and j == W-1) or (min(j+1,W-1) == W-1 and i == H-1):
            Goal = True
            Sunuke.append([1,1])
            break
        if S[max(i-1,0)][j] == '.':
            Sunuke.append([i-1,j])
            S[i-1][j] = '#'
        if S[min(i+1,H-1)][j] == '.':
            Sunuke.append([i+1,j])
            S[i+1][j] = '#'
        if S[i][max(j-1,0)] == '.':
            Sunuke.append([i,j-1])
            S[i][j-1] = '#'
        if S[i][min(j+1,W-1)] == '.':
            Sunuke.append([i,j+1])
            S[i][j+1] = '#'

print(-1 if len(Sunuke) == 0 else white - path)

Submission status: Accepted

Solution code:
from collections import deque

class Map_input():

    def __init__(self):
        line = input().split(" ")
        self.H = int(line[0])
        self.W = int(line[1])
        Map = [[] for i in range(self.H)]
        for i in range(self.H):
            line = input()
            for j in range(self.W):
                if line[j] == ".":
                    Map[i].append(0)
                else:
                    Map[i].append(1)
        self.Map = Map

class Maze_min():
    dx = [1, 0, -1, 0]
    dy = [0, 1, 0, -1]
    def __init__(self, H, W, Map, start, goal):
        self.H = H
        self.W = W
        self.Map = Map
        self.goal = goal
        self.queue = deque([start])
        self.dist = [[-1]*W for i in range(H)]
        self.dist[start[0]][start[1]] = 0

    def min_step(self):
        while len(self.queue) > 0:
            p = self.queue.popleft()
            if p == self.goal:
                break
            else:
                for i in range(len(Maze_min.dx)):
                    (nx, ny) = (p[0] + Maze_min.dx[i], p[1] + Maze_min.dy[i])
                    if nx in range(self.H) and ny in range(self.W) and self.Map[nx][ny] == 0 and self.dist[nx][ny] == -1:
                        self.queue.append((nx, ny))
                        self.dist[nx][ny] = self.dist[p[0]][p[1]] + 1
        return self.dist[self.goal[0]][self.goal[1]]

M = Map_input()
maze = Maze_min(M.H, M.W, M.Map, (0, 0), (M.H-1, M.W-1))
black_num = (sum(list(map(sum, M.Map))))
d = maze.min_step()
if d == -1:
    print(-1)
else:
    print(M.H*M.W - maze.min_step() - black_num -1)