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
H, W = map(int, input().split())
areas = []
blacks = 0
for _ in range(H):
    texts = list(input().rstrip())
    for char in texts:
        if char == '#':
            blacks += 1
    areas.append(texts)

# start は 0,0
# goal はH-1,W-1
# .を#に変更できる
# たくさん変更すればするほどポイントは高い
# 全部のマス - 元から#だった数 - 最短距離

inf = float('inf')


def bfs(start_point, goal_point):
    scores = [[inf for _ in range(W)] for _ in range(H)]
    queue = deque([start_point])
    scores[0][0] = 0
    move_positions = [[-1, 0], [0, -1], [1, 0], [0, 1]]
    while queue:
        now_point = queue.popleft()
        for move_position in move_positions:
            next_point = [now_point[0] + move_position[0],
                          now_point[1] + move_position[1]]
            if 0 <= next_point[0] < H and 0 <= next_point[1] < W:
                if areas[next_point[0]][next_point[1]] == '.':
                    if scores[next_point[0]][next_point[1]] > scores[now_point[0]][now_point[1]] + 1:
                        scores[next_point[0]][next_point[1]
                                              ] = scores[now_point[0]][now_point[1]] + 1
                        queue.append(next_point)
    return scores[H - 1][W - 1]


cost = bfs([0, 0], [H - 1, W - 1]) + 1
if cost == inf:
    print(-1)
else:
    print(H * W - blacks - cost)

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(10**8)
def ii(): return int(sys.stdin.readline())
def mi(): return map(int, sys.stdin.readline().split())
def li(): return list(map(int, sys.stdin.readline().split()))
def li2(N): return [list(map(int, sys.stdin.readline().split())) for _ in range(N)]
def dp2(ini, i, j): return [[ini]*i for _ in range(j)]
def dp3(ini, i, j, k): return [[[ini]*i for _ in range(j)] for _ in range(k)]
#import bisect #bisect.bisect_left(B, a)
#from collections import defaultdict #d = defaultdict(int) d[key] += value
#from itertools import accumulate #list(accumulate(A))

from collections import deque

H, W = mi()
S = [input() for _ in range(H)]

d = dp2(-1, W, H)
d[0][0] = 1
que = deque([[0, 0]])

h = [1, 0, -1, 0]
v = [0, -1, 0, 1]

while que != deque():
    i, j = que.popleft()
    for x in range(4):
        di, dj = h[x], v[x]
        if 0 <= i+di < H and 0 <= j+dj < W:
            if S[i+di][j+dj] !='#' and d[i+di][j+dj] == -1:
                d[i+di][j+dj] = d[i][j] + 1
                que.append([i+di, j+dj])

if d[H-1][W-1] == -1:
    print('-1')
else:
    ans = H*W - d[H-1][W-1] - sum([S[i].count('#') for i in range(H)])
    print(ans)

Submission status: Accepted

Solution code:
h,w=map(int,input().split())
sx,sy=0,0
gx,gy=w-1,h-1

maze=[]
white=0
for _ in range(h):
    temp=input()
    t=[]
    for s in temp:
        t.append(s)
        if s==".":
            white+=1
    maze.append(t)

maze[sy][sx]=1

from collections import deque
fifo = deque()
fifo.append([sy,sx])

result=-1

while len(fifo)>0:
    temp=fifo.popleft()
    y,x=temp[0],temp[1]

    if y==gy and x==gx:
        result=maze[y][x]

    if y>0:
        if maze[y-1][x]==".":
            fifo.append([y-1,x])
            maze[y-1][x]=maze[y][x]+1
    if y<h-1:
        if maze[y+1][x]==".":
            fifo.append([y+1,x])
            maze[y+1][x]=maze[y][x]+1
    if x>0:
        if maze[y][x-1]==".":
            fifo.append([y,x-1])
            maze[y][x-1]=maze[y][x]+1
    if x<w-1:
        if maze[y][x+1]==".":
            fifo.append([y,x+1])
            maze[y][x+1]=maze[y][x]+1



if result==-1:
    print(result)
else:
    print(white-result)

Submission status: Accepted

Solution code:
import sys
from collections import deque
H,W=map(int,input().split())
s=[[c for c in l.strip()] for l in sys.stdin]
maze=[[-1]*W for i in range(H)]
dy=[1,0,-1,0]
dx=[0,1,0,-1]
q=deque([])
q.append((0,0))
maze[0][0]=0
kabe=0
while(q):
  c=q.popleft()
  for i in range(4):
    if(c[0]+dy[i]>=0 and c[0]+dy[i]<H and c[1]+dx[i]>=0 and c[1]+dx[i]<W):
      if(s[c[0]+dy[i]][c[1]+dx[i]]=="." and maze[c[0]+dy[i]][c[1]+dx[i]]==-1):
        q.append((c[0]+dy[i],c[1]+dx[i]))
        maze[c[0]+dy[i]][c[1]+dx[i]]=maze[c[0]][c[1]]+1
        
for i in range(H):
  kabe+=s[i].count("#")
if(maze[H-1][W-1]==-1):
  print(-1)
else:
  print(H*W-kabe-1-maze[H-1][W-1])

Submission status: Accepted

Solution code:
import sys
input = lambda: sys.stdin.readline().rstrip() 
from collections import deque

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

    dir = ((0, 1), (1, 0), (0, -1), (-1, 0))
    dist = [[-1]*W for _ in range(H)]
    que = deque()
    que.append((0, 0))
    dist[0][0] = 0

    while len(que)>0:
        now_y, now_x = que.popleft()
        if now_y==H-1 and now_x==W-1:
            break
        for dy, dx in dir:
            next_y = now_y+dy
            next_x = now_x+dx
            if 0<=next_y<H and 0<=next_x<W and s[next_y][next_x]=='.' and dist[next_y][next_x]==-1:
                que.append((next_y, next_x))
                dist[next_y][next_x] = dist[now_y][now_x] + 1

    if dist[H-1][W-1]==-1:
        print(-1)
    else:
        print(white_num-(dist[H-1][W-1]+1))

if __name__ == '__main__':
    resolve()

Submission status: Accepted

Solution code:
import sys
IS = lambda: sys.stdin.readline().rstrip()
II = lambda: int(IS())
MII = lambda: list(map(int, IS().split()))
MIIZ = lambda: list(map(lambda x: x-1, MII()))
from collections import deque, Counter

def main():

    h, w = MII()
    h += 2; w += 2
    grid = '#' * w
    for _ in range(h-2):
        grid += '#' + IS() + '#'
    grid += '#' * w

    if grid[1+w] == '#' or grid[(h-1)*w-2] == '#': print(-1); exit(0)

    c = Counter(grid)
    dot = c['.']

    def bfs(start, goal):
        INF = 10**9
        dist = [INF] * (h*w)
        dist[start] = 1
        q = deque([start])
        while q:
            v = q.popleft()
            if v == goal: return dist[v]
            dv = dist[v]
            for mv in (-1,1,w,-w):
                x = v + mv
                if grid[x] == '#': continue
                dw = dv + 1
                if dw >= dist[x]: continue
                dist[x] = dw
                q.append(x)
        return -1
    res = bfs(1+w, (h-1)*w-2)
    if res == -1: print(-1); exit(0)
    print(dot-res)


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
from collections import deque

h,w = map(int,input().split())
s = ["#"*(w+1)] + ["#" + input() + "#" for _ in range(h)] + ["#"*(w+1)]

shortest_path = [[float('inf')] * (w+1) for _ in range(h+1)]

shortest_path[1][1] = 1
q = deque([(1,1)])

while q:
    x,y = q.popleft()
    cost = shortest_path[y][x]
    for j,i in [(x-1,y),(x+1,y),(x,y-1),(x,y+1)]:
        if s[i][j] == "#":
            continue
        else:
            if shortest_path[i][j] > cost+1:
                q.append((j,i))
                shortest_path[i][j] = cost+1

if shortest_path[h][w] == float('inf'):
    print(-1)
else:
    print(sum( st.count(".") for st in s) - shortest_path[h][w])

Submission status: Accepted

Solution code:
# coding: utf-8

# https://atcoder.jp/contests/abc088/tasks/abc088_d
# 19:01-20:04 chudan
# 20:17-20:53 done


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

    INF = 10**10
    n_white = 0
    s = [[-1] * (W+2) for _ in range(H+2)]
    for i in range(H):
        for j, x in enumerate(input()):
            # white => 1, black => -1
            s[i+1][j+1] = INF if x == "." else -1
            n_white += 1 if x == "." else 0
    s[1][1] = 0

    queue = [(1, 1)]
    queue_size = 1
    queue_idx = 0
    while True:
        # 最短から貪欲に伸ばして行く
        if queue_idx == queue_size:
            # cannot arrive
            return -1
        
        x, y = queue[queue_idx]
        queue_idx += 1
        
        if x == H and y == W:
            shortest = s[x][y]
            break

        if s[x][y-1] != -1 and s[x][y-1] > s[x][y]+1:
            s[x][y-1] = s[x][y]+1
            queue.append((x, y-1))
            queue_size += 1
        if s[x][y+1] != -1 and s[x][y+1] > s[x][y]+1:
            s[x][y+1] = s[x][y]+1
            queue.append((x, y+1))
            queue_size += 1
        if s[x-1][y] != -1 and s[x-1][y] > s[x][y]+1:
            s[x-1][y] = s[x][y]+1
            queue.append((x-1, y))
            queue_size += 1
        if s[x+1][y] != -1 and s[x+1][y] > s[x][y]+1:
            s[x+1][y] = s[x][y]+1
            queue.append((x+1, y))
            queue_size += 1
    
    return n_white - (shortest + 1)


print(main())

Submission status: Accepted

Solution code:
from collections import deque
import itertools

h,w=map(int, input().split())
d=[list(input()) for i in range(h)]
inf=10**7

def bfs():
    for i, j in itertools.product([i for i in range(h)], [j for j in range(w)]):
        if d[i][j]=='.':
            d[i][j]=inf
    que=deque([[0,0]])
    d[0][0]=0

    while que:
        y,x=que.popleft()
        for i,j in [(1,0),(0,1),(-1,0),(0,-1)]:
            ny,nx=y+i,x+j
            if nx>=0 and nx<w and ny>=0 and ny<h:
                dist=d[ny][nx]
                if dist!='#':
                    if dist>d[y][x]+1:
                        d[ny][nx]=d[y][x]+1
                        que.append([ny,nx])

bfs()
ans=h*w-d[h-1][w-1]-1
for i, j in itertools.product([i for i in range(h)], [j for j in range(w)]):
    if d[i][j]=='#': 
        ans-=1
if ans>=0:
    print(ans)
else:
    print('-1')

Submission status: Accepted

Solution code:
import queue
INF = 10**8

def bfs():
    q = queue.Queue()
    q.put((sx, sy))
    d[sx][sy] = 0

    while q.empty() == False:
        now = q.get()
        if now[0] == gx and now[1] == gy:
            break

        for i in range(4):
            nx = now[0] + dx[i]
            ny = now[1] + dy[i]

            if 0 <= nx < h and 0 <= ny < w and s[nx][ny] == "." and d[nx][ny] == INF:
                q.put((nx, ny))
                d[nx][ny] = d[now[0]][now[1]] + 1

h, w = map(int, input().split())
count = 0
s = [[] for i in range(h)]
for i in range(h):
    s[i] = list(input())
    for j in range(w):
        if s[i][j] == "#":
            count += 1

sx, sy = 0, 0
gx, gy = h - 1, w - 1
dx = [1, 0, -1, 0]
dy = [0, 1, 0, -1]
d = [[INF]*w for i in range(h)]

bfs()
if d[gx][gy] == INF:
    print(-1)
else:
    ans = h * w - (d[gx][gy] + 1 + count)
    print(ans)

Submission status: Accepted

Solution code:
from collections import deque
h, w = map(int, input().split())

grid = []
for _ in range(h):
    row = list(input())
    grid.append(row)

def bfs(grid, sy, sx, gy, gx, h, w):
    visited = [[float('inf')] * w for _ in range(h)]
    visited[sy][sx] = 1
    que = deque([(sy, sx)])
    # up, right, down, left
    dy = [-1, 0, 1, 0]
    dx = [0, 1, 0, -1]
    while que:
        y, x = que.popleft()
        for i in range(4):
            next_y = y + dy[i]
            next_x = x + dx[i]
            if 0 <= next_y < h and 0 <= next_x < w and grid[next_y][next_x] == '.' and visited[next_y][next_x] == float('inf'):
                visited[next_y][next_x] = visited[y][x] + 1
                que.append([next_y, next_x])
                if next_y == gy and next_x == gx:
                    return visited[gy][gx]
    return -1

r = bfs(grid, 0, 0, h - 1, w - 1, h, w)
if r == -1:
    print(r)
else:
    white = 0
    for i in range(h):
        for j in range(w):
            if grid[i][j] == '.':
                white += 1
    print(white - r)

Submission status: Accepted

Solution code:
from collections import deque

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

T = [[None] * W for _ in range(H)]
T[0][0] = 1
D = deque([(0, 0)])
while D:
    h, w = D.popleft()
    for dh, dw in ((1, 0), (0, 1), (-1, 0), (0, -1)):
        if 0 <= h + dh < H and 0 <= w + dw < W and S[h + dh][w + dw] == '.' and T[h + dh][w + dw] is None:
            T[h + dh][w + dw] = T[h][w] + 1
            D.append((h + dh, w + dw))

if T[H - 1][W - 1] is None:
    print(-1)
else:
    print(sum(s.count('.') for s in S) - T[H - 1][W - 1])

Submission status: Accepted

Solution code:
#!/usr/bin/env python3

from collections import deque
try:
    from typing import Deque, Tuple
except ImportError:
    pass


def main():
    H, W = [int(x) for x in input().split()]
    s = [input() for _ in range(H)]
    q = deque()  # type: Deque[Tuple[int, int]]
    dist = {
        (0, 0): 1,
    }
    q.append((0, 0))
    while q:
        sy, sx = q.popleft()
        for dy, dx in ((0, 1), (1, 0), (0, -1), (-1, 0)):
            ty = sy + dy
            tx = sx + dx
            if not (0 <= ty < H and 0 <= tx < W):
                continue
            if s[ty][tx] == "#":
                continue
            if (ty, tx) in dist:
                continue
            dist[ty, tx] = dist[sy, sx] + 1
            q.append((ty, tx))
    if (H - 1, W - 1) not in dist:
        print(-1)
        return
    print(sum(si.count(".") for si in s) - dist[H - 1, W - 1])


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
from collections import deque
h,w = map(int,input().split())
s = []
s.append(["#"]*(w+2))
for i in range(h):
    s.append(["#"]+list(input())+["#"])
s.append(["#"]*(w+2))
dx = [1,0,-1,0]
dy = [0,-1,0,1]
q = deque([(1,1)])
dis = [[-1]*(w+2) for _ in range(h+2)]
dis[1][1] = 0
while q:
    x,y = q.popleft()
    for i in range(4):
        if s[x+dx[i]][y+dy[i]] == "." and dis[x+dx[i]][y+dy[i]] == -1:
                dis[x+dx[i]][y+dy[i]] = dis[x][y] +1
                q.append((x+dx[i],y+dy[i]))
count = 0
if dis[h][w] == -1:
    print(-1)
else:
    for i in range(h+2):
        for j in range(w+2):
            if s[i][j] == ".":
                count += 1
    print(count-dis[h][w]-1)

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline
#input = sys.stdin.buffer.readline

#sys.setrecursionlimit(10**9)

def RD(): return sys.stdin.read()
def II(): return int(input())
def MI(): return map(int,input().split())
def LI(): return list(map(int,input().split()))
def TI(): return tuple(map(int,input().split()))
# rstrip().decode('utf-8')
#import numpy as np

from collections import deque

def main():
	h,w=MI()
	G=["#"]*(w+2)
	for i in range(h):
		G+=["#"]+list(input().rstrip())+["#"]
	G+=["#"]*(w+2)
	ans=0
	#print(G)
	for i in range((h+2)*(w+2)):
		if G[i]==".":
			ans+=1

	Q=deque()
	Q.append((w+3,1))
	G[w+3]="#"
	f=0
	while Q:
		#print(Q)
		x,d=Q.popleft()
		if x==(w+2)*(h+2)-(w+2)-2:
			f=1
			break
		for dx in [-1,1,-w-2,w+2]:
			if G[x+dx]==".":
				Q.append((x+dx,d+1))
				G[x+dx]="#"

	if f==1:
		print(ans-d)
	else:
		print(-1)


























































if __name__ == "__main__":
	main()

Submission status: Accepted

Solution code:
# Python3 (3.4.3)
import sys
input = sys.stdin.readline

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

def BFS(dq):
    while dq:
        e = dq.popleft()
        y,x = e
        for i in range(4):
            yi = y+dy[i]
            xi = x+dx[i]
            if 0<=yi<Y and 0<=xi<X:
                if A[yi][xi] != "#" and A[yi][xi] == ".":
                    A[yi][xi] = A[y][x] + 1 
                    dq.append((yi,xi))


# -------------------------------------------------------------
# main
# -------------------------------------------------------------
H,W = map(int,input().split())
S = [list(input().rstrip()) for _ in range(H)]

Y,X = H,W
A = S

A[0][0] = 1
from collections import deque
dq = deque([(0,0)])
BFS(dq)

if A[Y-1][X-1] == ".":
    print(-1)
else:
    cnt = 0
    for a in A:
        cnt += a.count("#")
    print(X*Y - cnt - A[Y-1][X-1])

Submission status: Accepted

Solution code:
from sys import stdin
import collections
from sys import  setrecursionlimit
setrecursionlimit(30000)

[H, W] = [int(x) for x in stdin.readline().rstrip().split()]
data = []
for line in range(H):
    temp = stdin.readline().rstrip()
    temp_arr = []
    for j in range(len(temp)):
        temp_arr.append(temp[j])
    data.append(temp_arr)


#幅優先探索で最短経路を探す

visited = []
candidates = collections.deque()

def wfs(data, start_pos, visited, candidates):
    index = start_pos[2]
    visited.append([start_pos[0],start_pos[1]])

    #goal
    if start_pos[0] == H-1 and start_pos[1] == W-1:
        return start_pos[2]
    
    #candidates
    for i in range(-1,2):
        for j in range(-1,2):
            if abs(i)+ abs(j)!=1:
                continue
            new_pos = [start_pos[0]+i, start_pos[1]+j,index+1]
            if new_pos[0]<0 or new_pos[0]>=H or new_pos[1]<0 or new_pos[1]>=W:
                continue
            if new_pos[:2] in visited:
                continue
            if data[new_pos[0]][new_pos[1]]==".":
#            if True:
                candidates.append(new_pos)
    
    while(True):
        if len(candidates)==0:
            return -1
        next_pos = candidates.popleft()
        if next_pos[:2] not in visited:
            break
        
    result = wfs(data, next_pos, visited,candidates)

    return result

def check_number(data):
    count = 0
    for i in range(H):
        for j in range(W):
            if data[i][j]==".":
                count+=1
    return count


result = wfs(data,[0,0,0],visited, candidates)
if result==-1:
    print(-1)
else:
    print(check_number(data)-result-1)

Submission status: Accepted

Solution code:
import scipy.sparse
H,W = (int(x) for x in input().split())
lines = [input() for i in range(H)]
lil = scipy.sparse.lil_matrix((H*W, H*W), dtype = int)
for i in range(H):
    for j in range(W):
        if i == j == 0: continue
        elif i == 0 and j > 0:
            if lines[0][j] == lines[0][j-1] == ".":
                lil[i*W+j, i*W+j-1] = 1
                lil[i*W+j-1, i*W+j] = 1
        elif i > 0 and j == 0:
            if lines[i][0] == lines[i-1][0] == ".":
                lil[i*W+j, (i-1)*W+j] = 1
                lil[(i-1)*W+j, i*W+j] = 1
        else:
            if lines[i][j] == lines[i][j-1] == ".":
                lil[i*W+j, i*W+j-1] = 1
                lil[i*W+j-1, i*W+j] = 1
            if lines[i][j] == lines[i-1][j] == ".":
                lil[i*W+j, (i-1)*W+j] = 1
                lil[(i-1)*W+j, i*W+j] = 1
lil2 = scipy.sparse.csgraph.dijkstra(lil, directed = False, indices=[0,H*W-1]).astype(int)
a = lil2[0][H*W-1]
if a <= 0:
    print("-1")
else:
    b = "".join(lines).count(".")
    print(b-a-1)

Submission status: Accepted

Solution code:
from collections import deque
H,W=map(int,input().split())
s=[list('X'+input()+'X') for i in range(H)]
s.append('X'*(W+2))
s.insert(0,'X'*(W+2))

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

sd=[[-1 for i in range(W+2)] for j in range(H+2)]
d=[[0,1],[0,-1],[1,0],[-1,0]]
que=deque([[1,1]])
sd[1][1]=1
while len(que)>0:
    p=que.popleft()
    if p==[H,W]:
        break
    for v in d:
        ny=p[0]+v[0]
        nx=p[1]+v[1]
        if s[ny][nx]=='.' and sd[ny][nx]==-1:
            sd[ny][nx]=sd[p[0]][p[1]]+1
            que.append([ny,nx])

if sd[H][W]==-1:
    print(-1)
    exit()

print(wnum-sd[H][W])

Submission status: Accepted

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

numdot = 0
for i in s:
    numdot += i.count('.')

from collections import deque

#WFS(幅優先探索)
seen = [[0 for _ in range(w)] for __ in range(h)]
seen[0][0] = 1
todo = deque([(0, 0)])
d = [(1,0,0,h-1), (0,1,1,w-1), (-1,0,0,0), (0,-1,1,0)]

while todo != deque([]):
    a = todo.popleft()
    for i in d:
        if a[i[2]] != i[3]:
            x = a[0] + i[0]
            y = a[1] + i[1]
            if s[x][y] == '.' and seen[x][y] == 0:
                todo.append((x, y))
                seen[x][y] = seen[a[0]][a[1]] + 1

    if seen[h-1][w-1] != 0:
        print(numdot - seen[h-1][w-1])
        exit()

print(-1)

Submission status: Accepted

Solution code:
from collections import deque

Height, Width = map(int, input().split())
Map = [input() for _ in range(Height)]

y_start, x_start = 0, 0
y_goal, x_goal = Height-1, Width-1

min_step_map = [[-1]*Width for _ in range(Height)]
min_step_map[y_start][x_start] = 0
reserch_point = deque()
reserch_point.append([y_start, x_start])
while len(reserch_point) > 0:
    y_now, x_now = reserch_point.popleft()

    for dy, dx in [(-1,0), (0,-1), (1,0), (0,1)]:
        y_next, x_next = y_now+dy, x_now+dx
        if (y_next <= -1 or Height <= y_next) or \
                                              (x_next <= -1 or Width <= x_next):
            continue

        if y_next == y_goal and x_next == x_goal:
            min_step_map[y_goal][x_goal] = min_step_map[y_now][x_now] + 1
            break

        if Map[y_next][x_next] == '.' and min_step_map[y_next][x_next] == -1:
            min_step_map[y_next][x_next] = min_step_map[y_now][x_now] + 1
            reserch_point.append([y_next, x_next])
        
    else:
        continue
    break

else:
    print(-1)
    exit()

min_step = min_step_map[y_goal][x_goal]
count_black = 0
for y in range(Height):
    for x in range(Width):
        if Map[y][x] == '#':
            count_black += 1

# Since the starting point is not included in 'min_step',
# it is excluded from the total number of maps.
total_point = Height * Width - 1

score = total_point - count_black - min_step
print(score)

Submission status: Accepted

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

gh = h-1
gw = w-1
def bfs():
  que = deque([])
  ch = 0
  cw = 0
  d[ch][cw] = 0

  dh = [1,0,-1,0]
  dw = [0,1,0,-1]
  
  que.append([ch,cw])
  while que:
    p = que.popleft()
    if p[0] == gh and p[1] == gw:
      return
    for i in range(4):
      nh = p[0] + dh[i]
      nw = p[1] + dw[i]
      
      if nh >= 0 and nh < h and nw >=0 and nw < w and \
          d[nh][nw] == float('inf') and s[nh][nw] != '#':
        d[nh][nw] = d[p[0]][p[1]] + 1
        que.append([nh, nw])

d = [[float('inf') for _ in range(w)] for _ in range(h)]
bfs()
if d[gh][gw] == float('inf'):
  print(-1)
  exit()

white = 0
root = d[gh][gw]

for i in range(h):
  for j in range(w):
    if s[i][j] == '.':
      white += 1
print(white-root-1)

Submission status: Accepted

Solution code:
from collections import deque 
h,w=map(int,input().split())
s=[list(input()) for i in range(h)]
ans=0
for i in range(h):
    for j in range(w):
        if s[i][j]==".":
            ans+=1
q=deque([[0,0]])
dx=[1,0,-1,0]
dy=[0,1,0,-1]
s[0][0]=0
while q:
    p=q.popleft()
    if p[0]==h-1 and p[1]==w-1:
        break
    for i in range(4):
        x=p[0]+dx[i]
        y=p[1]+dy[i]
        if 0<=x<h and 0<=y<w and s[x][y]==".":
            s[x][y]=s[p[0]][p[1]]+1
            q.append([x,y])
print(-1 if s[-1][-1]=="." else ans-s[-1][-1]-1)

Submission status: Accepted

Solution code:
import numpy as np
H, W=map(int, input().split())
F=[]
for i in range(H):
  F.append(list(input()))
count=0
for i in range(H):
  count+=F[i].count("#")
INF=100000000  
F=np.array(F)
def bfs():
    #dx, dy 四方向に対応したベクトルのリスト
    dx=[1,0,-1,0]
    dy=[0,1,0,-1]
    #P: (x, y)のキュー
    P=[]
    #d: スタートから各点までの最小距離の配列
    d=np.ones((H, W))*INF
    #スタート地点をキューに入れ、その点の距離を0にする
    sx,sy=0,0
    gx,gy=H-1,W-1
    P.append([sx, sy])
    d[sx,sy]=0
    
    #キューがからになるまでループ
    while len(P)>0:
        #キューの先頭を取り出す
        p=P.pop(0)
        #取り出してきた状態がゴールなら探索をやめる
        if (p[0]==gx and p[1]==gy):
            break
        
        #移動四方向をループ
        for i in range(4):
            #移動した後の点をnx, nyとする
            nx=p[0]+dx[i]
            ny=p[1]+dy[i]
            
            #移動が可能かどうかの判定とすでに訪れたことがあるかどうかの判定（d[nx, ny]!=INFならおtpずれたことがある）
            if 0<=nx and nx<H and 0<=ny and ny<W and F[nx, ny]!="#" and d[nx, ny]==INF:
                #移動できるならキューに入れ、その点の距離をpからの距離＋１で確定する
                P.append([nx, ny])
                d[nx, ny]=d[p[0], p[1]]+1
    #print(d)
    return d[gx, gy]
ans=bfs()
if ans==INF:
  print(-1)
else:
  print(int((H*W-count)-ans-1))

Submission status: Accepted

Solution code:
from collections import deque

def make_wall(maze,h,w):
    maze=deque(maze)
    for i in range(h):
        maze[i]="#"+maze[i]+"#"
    maze.appendleft("#"*(w+2))
    maze.append("#"*(w+2))
    return list(maze)

def bfs(maze, visited, sy, sx, gy, gx):
    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 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 -1

h,w=map(int,input().split())
maze=[input() for _ in range(h)]
kabe=0
for i in range(h):
    kabe+=maze[i].count("#")
maze=make_wall(maze,h,w)
visited=[[-1]*(w+2) for _ in range(h+2)]
sy,sx=1,1
gy,gx=h,w
d=1+bfs(maze, visited, sy, sx, gy, gx)
if d==0:
    print(-1)
else:
    print(h*w-kabe-d)

Submission status: Accepted

Solution code:
from collections import deque

H, W = map(int, input().split())
s = [None] * H
count = 0

for i in range(H):
  s[i] = input()
  count += s[i].count('#')

adj = [[] for _ in range(W*H)]
  
dx = [-1,1,0,0]
dy = [0,0,-1,1]
  
for i in range(H):
  for j in range(W):
    if s[i][j] == '.':
      for k in range(4):
        y = i + dy[k]
        x = j + dx[k]
        if 0<=x<W and 0<=y<H:
          if s[y][x] == '.':
            adj[W*i+j].append(W*y+x)
  
queue = deque([0])
visit = [-1] * (W*H)
visit[0] = 1
  
while queue:
  now = queue.popleft()
  for u in adj[now]:
    if visit[u] < 0:
      queue.append(u)
      visit[u] = visit[now] + 1

if visit[W*H-1] == -1:
  print(-1)
else:
  print(W*H - visit[W*H-1] - count)