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:
import math
import fractions
import bisect
import collections
import itertools
import heapq
import string
import sys
import copy
from collections import deque
sys.setrecursionlimit(10**7)
MOD = 10**9+7
def gcd(a,b):return fractions.gcd(a,b) #最大公約数
def lcm(a,b):return (a*b) // fractions.gcd(a,b) #最小公倍数
def iin(): return int(input()) #整数読み込み
def ifn(): return float(input()) #浮動小数点読み込み
def isn(): return input().split() #文字列読み込み
def imn(): return map(int, input().split()) #整数map取得
def fmn(): return map(float, input().split()) #浮動小数点map取得
def iln(): return list(map(int, input().split())) #整数リスト取得
def iln_s(): return sorted(iln()) # 昇順の整数リスト取得
def iln_r(): return sorted(iln(), reverse=True) # 降順の整数リスト取得
def fln(): return list(map(float, input().split())) # 浮動小数点リスト取得
def join(l, s=''): return s.join(l) #リストを文字列に変換
def perm(l, n): return itertools.permutations(l, n) # 順列取得
def perm_count(n, r): return math.factorial(n) // math.factorial(n-r) # 順列の総数
def comb(l, n): return itertools.combinations(l, n) # 組み合わせ取得
def comb_count(n, r): return math.factorial(n) // (math.factorial(n-r) * math.factorial(r)) #組み合わせの総数
def two_distance(a, b, c, d): return ((c-a)**2 + (d-b)**2)**.5 # 2点間の距離
def m_add(a,b): return (a+b) % MOD

H,W = map(lambda x: int(x)-1, input().split())
s = [input() for _ in range(H+1)]

d = [[-1 for _ in range(W+1)] for _ in range(H+1)]
d[0][0] = 0

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

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

while len(queue) > 0:
    point = queue.popleft()

    if point[1] == H and point[0] == W: break 
    for i in range(4):
        x = point[0] + dx[i]
        y = point[1] + dy[i]

        if x < 0 or y < 0 or x > W or y > H or s[y][x] == '#': continue
        if d[y][x] != -1: continue
        d[y][x] = d[point[1]][point[0]] + 1
        queue.append((x,y))

if d[H][W] == -1:
    print(-1)
else:
    white_count = 0
    for i in range(H+1):
        for j in range(W+1):
            if s[i][j] == '.':
                white_count += 1
    print(white_count - (d[H][W]+1))

Submission status: Accepted

Solution code:
from collections import deque
import sys

h, w = map(int, input().split())
map_size = h * w
maze = [list(input()) for _ in range(h)]
goal = (h - 1, w - 1)


def shortest_path(start, goal):
    que = deque()
    que.append(start)
    visited = [[-1] * w for _ in range(h)]
    visited[start[0]][start[1]] = 0
    while que:
        now = que.popleft()
        for iy, ix in [(0, 1), (0, -1), (1, 0), (-1, 0)]:
            ny = now[0] + iy
            nx = now[1] + ix
            if (0 <= ny < h) and (0 <= nx < w):
                if ny == goal[0] and nx == goal[1]:
                    visited[ny][nx] = visited[now[0]][now[1]] + 1
                    return visited[ny][nx]
                # if not maze[nx][ny] == '.':
                #    continue
                if maze[ny][nx] != '#' and visited[ny][nx] == -1:
                    visited[ny][nx] = visited[now[0]][now[1]] + 1
                    que.append((ny, nx))
    return -1


# def restore_path(visited):
#     path = [(h - 1, w - 1)]
#     cnt = visited[h - 1][w - 1]
#     x = w - 1
#     y = h - 1
#     while cnt > 0:
#         for iy, ix in [(0, 1), (0, -1), (1, 0), (-1, 0)]:
#             ny = y + iy
#             nx = x + ix
#             if (0 <= ny < h) and (0 <= nx < w):
#                 if visited[ny][nx] != (cnt - 1):
#                     continue
#                 y = ny
#                 x = nx
#                 cnt -= 1
#                 path.append((y, x))
#                 break
#     return path


move_cnt = shortest_path((0, 0), goal)
if move_cnt == -1:
    print(-1)
    sys.exit()

cnt = 0
for y in range(h):
    for x in range(w):
        if maze[y][x] == '#':
            cnt += 1

print(map_size - cnt - move_cnt - 1)

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(10**9)
H,W = map(int,input().split())
move_x = [1,-1,0,0]
move_y = [0,0,1,-1]
Field = [[c for c in input()] for _ in range(H)]
seen = [[False for _ in range(W)] for _ in range(H)]
queue = []
black = 0
for i in range(H):
    for j in range(W):
        if Field[i][j] == '#':
            black += 1
dist = [[0 for _ in range(W)] for _ in range(H)]
res = -1 
def bfs(start_x,start_y,Field,seen,queue,dist):
    global res
    seen[start_x][start_y] = True
    for i in range(0,4):
        x = start_x + move_x[i]
        y = start_y + move_y[i]
        if x < 0 or y < 0 or x >= H or y >= W:
            continue #out of range
        if Field[x][y] == '#':
            continue #we don't visit black square.
        if seen[x][y]:
            continue #already visited
        if Field[x][y] in queue:
            continue #already in queue.
        dist[x][y] = dist[start_x][start_y] + 1
        if x == (H-1) and y == (W-1):
            res = H*W - dist[x][y] - black #H*W - counting(seen) - black 
        queue.append((x,y))
    for element in queue:
        x,y = element
        if seen[x][y]:
            continue
        seen[x][y] = True
        queue.remove(element)
        bfs(x,y,Field,seen,queue,dist)    
bfs(0,0,Field,seen,queue,dist)
if res != -1:
	print(res-1)
else:
  print(-1)

Submission status: Accepted

Solution code:
from sys import stdin
from collections import deque
inf = 10**10
h,w = [int(x) for x in stdin.readline().rstrip().split()]
li = [["" for i in range(w)]for j in range(h)]
point = 0
for i in range(h):
    s = stdin.readline().rstrip()
    point += s.count(".")
    for j in range(w):
        li[i][j] = s[j]
dx = [1,0,-1,0]
dy = [0,1,0,-1]
que = deque()
lin = [[inf for i in range(w)]for j in range(h)]
lin[0][0] = 0
que.append([0,0])
while que:
    k = que.popleft()
    x = k[0]
    y = k[1]
    for i,j in zip(dx,dy):
        nx = x + i
        ny = y + j
        if nx < 0 or nx >= h or ny < 0 or ny >= w:
            continue
        elif li[nx][ny] == "#" :
            continue
        elif lin[nx][ny] == inf:
            que.append([nx,ny])
            lin[nx][ny] = lin[x][y]+1
kotae = lin[h-1][w-1]
if kotae == inf:
    print(-1)
    exit()
print(point-kotae-1)

Submission status: Accepted

Solution code:
H,W = [int(i) for i in input().split()]
maze = ['0'] * H
for i in range(H):
    maze[i] = list(input())
dx = [1,0,-1,0]
dy = [0,1,0,-1]
import collections
from collections import deque
que = deque()
dic = [[-1] * (W) for _ in range(H)]
dic[0][0] = 0
que.append([0,0])
while (len(que) != 0):
    k = que.popleft()
    x = k[0]
    y = k[1]
    for i in range(4):
        nx = x + dx[i]
        ny = y + dy[i]
        if nx < 0 or nx >= H or ny < 0 or ny >= W:
            continue
        if maze[nx][ny] == "#" :
            continue
        if dic[nx][ny] == -1:
            que.append([nx,ny])
            dic[nx][ny] = dic[x][y] +1
ml = dic[H-1][W-1]
count = 0
for i in range(H):
    for j in range(W):
        if maze[i][j] == '.':
            count+=1
if ml == -1:
    print(-1)
else :
    print(count - ml - 1)

Submission status: Accepted

Solution code:
from collections import deque, defaultdict
H, W = map(int, input().split())
sheet = [[0]*(W+2) for i in range(H+2)]
dist = defaultdict(int)
cnt = 0
for i in range(1,H+1):
  inf = input()
  for j in range(1, W+1):
    if inf[j-1]=='.':
      sheet[i][j]=1
      cnt += 1
deq = deque([(1,1,1)])
dist[(1,1)] = 1
while deq:
  x,y,d = deq.popleft()
  flag = False
  for dx,dy in [(-1,0),(1,0),(0,-1),(0,1)]:
    nx = x+dx
    ny = y+dy
    if sheet[ny][nx]==1 and dist[(nx,ny)]==0:
      deq += [(nx,ny,d+1)]
      dist[(nx,ny)]=d+1
      if nx==W and ny==H:
        flag= True
        break
  if flag:
    print(cnt-dist[(W,H)])
    break
else:
  print(-1)

Submission status: Accepted

Solution code:
import sys
import collections

input = sys.stdin.readline


def main():
    H, W = [int(x) for x in input().split()]
    S = [input().strip() for _ in range(H)]

    dj = [1, 0, -1, 0]
    di = [0, 1, 0, -1]

    d = [[-1 for i in range(W)] for j in range(H)]
    q = collections.deque([])
    q.append((0, 0))
    d[0][0] = 0

    while q:
        p = q.popleft()
        for i in range(4):
            nj = p[0] + dj[i]
            ni = p[1] + di[i]

            if 0 <= nj < H and 0 <= ni < W and S[nj][ni] != "#" and d[nj][ni] == -1:
                q.append((nj, ni))
                d[nj][ni] = d[p[0]][p[1]] + 1

    if d[H - 1][W - 1] == -1:
        print(-1)
    else:
        bnum = 0
        for s in S:
            bnum += s.count(".")
        print(bnum - 1 - d[H - 1][W - 1])


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
INF = 1e10

H, W = list(map(int, input().split()))
c = []
cnt = 0
for y in range(H):
    c.append(input())
    for s in c[-1]:
        if s=='.':
            cnt+=1
    
def search(syx, gyx):
    sy,sx = syx
    gy,gx = gyx
    visited = [[INF]*W for _ in range(H)]
    q = [[sy,sx]]
    visited[sy][sx]=0
    while len(q)>0:
        tmp_q = []
        for one in q:
            cy,cx = one
            for dy, dx in ((1, 0), (-1, 0), (0, 1), (0, -1)):
                ny, nx = cy+dy, cx+dx
                if 0 <= nx < W and 0 <= ny < H and c[ny][nx] == '.' and visited[ny][nx]> visited[cy][cx]+1:
                    visited[ny][nx] = visited[cy][cx]+1
                    tmp_q.append([ny,nx])
        q = tmp_q
        if visited[gy][gx]!=INF:
            break
    return visited[gy][gx]

ans = search([0,0],[H-1,W-1])
if ans==INF:
    print(-1)
else:
    print(cnt-ans-1)

Submission status: Accepted

Solution code:
def main():
    H, W = (int(i) for i in input().split())
    c = [input() for j in range(H)]
    from collections import deque
    dist = [[-1]*W for i in range(H)]

    def bfs(sy, sx):
        que = deque()
        dist[sy][sx] = 0
        que.append((sy, sx))
        d = ((1, 0), (0, 1), (-1, 0), (0, -1))
        while que:
            uy, ux = que.popleft()
            for dy, dx in d:
                next_y = uy + dy
                next_x = ux + dx
                if not(0 <= next_y < H and 0 <= next_x < W):
                    continue
                if dist[next_y][next_x] != -1:
                    continue
                if c[next_y][next_x] == '#':
                    continue
                dist[next_y][next_x] = dist[uy][ux] + 1
                que.append((next_y, next_x))

    bfs(0, 0)
    if dist[H-1][W-1] == -1:
        return print(-1)
    ans = H*W - (dist[H-1][W-1] + 1)
    for h in range(H):
        for w in range(W):
            if c[h][w] == "#":
                ans -= 1
    print(ans)


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import queue

h, w = list(map(int, input().split()))
s = [input() for _ in range(h)]
white = 0
for i in range(h):
    white += s[i].count('.')
q = queue.Queue()
q.put(0)
kyori = [0] * (h*w)
kyori[0] = 1
while not q.empty():
    p = q.get()
    kyo = kyori[p]
    x = p%w
    y = p//w
    if x >= 1 and s[y][x-1] == '.' and kyori[p-1] == 0:
        q.put(p-1)
        kyori[p-1] = kyo+1
    if x < w-1 and s[y][x+1] == '.' and kyori[p+1] == 0:
        q.put(p+1)
        kyori[p+1] = kyo+1
    if y >= 1 and s[y-1][x] == '.' and kyori[p-w] == 0:
        q.put(p-w)
        kyori[p-w] = kyo+1
    if y < h-1 and s[y+1][x] == '.' and kyori[p+w] == 0:
        q.put(p+w)
        kyori[p+w] = kyo+1
if kyori[-1] == 0:
    print(-1)
else:
    print(white - kyori[-1])

Submission status: Accepted

Solution code:
from _collections import deque


def bfs(field, field_info, starting_y, starting_x, goal_y, goal_x):
    queue = deque([[starting_y, starting_x]])
    field_info[starting_y][starting_x] = 1

    while queue:
        y, x = queue.popleft()
        for dy, dx in ([1, 0], [-1, 0], [0, 1], [0, -1]):
            new_y, new_x = y + dy, x + dx
            if 0 <= new_y <= goal_y and 0 <= new_x <= goal_x and field[new_y][new_x] == "." and field_info[new_y][new_x] == -1:
                field_info[new_y][new_x] = field_info[y][x] + 1
                queue.append([new_y, new_x])


def solve():
    number_of_rows, number_of_columns = list(map(int, input().split()))  # Row, Column数
    field = [input() for _ in range(number_of_rows)]
    field_info = [[-1] * number_of_columns for _ in range(number_of_rows)]
    starting_y, starting_x = 0, 0
    goal_y, goal_x = number_of_rows - 1, number_of_columns - 1
    bfs(field, field_info, starting_y, starting_x, goal_y, goal_x)

    # # BFSの結果をチェック
    # for field_info_line in field_info:
    #     print(field_info_line)

    if field_info[goal_y][goal_x] == -1:
        print(-1)
        return
    else:   # 到達できる場合
        number_of_black_cell = 0
        for row_i in range(number_of_rows):
            for column_i in range(number_of_columns):
                if field[row_i][column_i] == "#":
                    number_of_black_cell += 1
        point = number_of_columns * number_of_rows - field_info[goal_y][goal_x] - number_of_black_cell
        print(point)

solve()

Submission status: Accepted

Solution code:
from _collections import deque


def bfs(field, field_info, starting_y, starting_x, goal_y, goal_x):
    queue = deque([[starting_y, starting_x]])
    field_info[starting_y][starting_x] = 1

    while queue:
        y, x = queue.popleft()
        if [y, x] == [goal_y, goal_x]:
            return field_info[y][x]
        for dy, dx in ([1, 0], [-1, 0], [0, 1], [0, -1]):
            new_y, new_x = y + dy, x + dx
            if 0 <= new_y <= goal_y and 0 <= new_x <= goal_x and field[new_y][new_x] == "." and field_info[new_y][new_x] == -1:
                field_info[new_y][new_x] = field_info[y][x] + 1
                queue.append([new_y, new_x])


def solve():
    number_of_rows, number_of_columns = list(map(int, input().split()))  # Row, Column数
    field = [input() for _ in range(number_of_rows)]
    field_info = [[-1] * number_of_columns for _ in range(number_of_rows)]
    starting_y, starting_x = 0, 0
    goal_y, goal_x = number_of_rows - 1, number_of_columns - 1
    bfs(field, field_info, starting_y, starting_x, goal_y, goal_x)

    # # BFSの結果をチェック
    # for field_info_line in field_info:
    #     print(field_info_line)

    if field_info[goal_y][goal_x] == -1:
        print(-1)
        return
    else:   # 到達できる場合
        number_of_black_cell = 0
        for row_i in range(number_of_rows):
            for column_i in range(number_of_columns):
                if field[row_i][column_i] == "#":
                    number_of_black_cell += 1
        point = number_of_columns * number_of_rows - field_info[goal_y][goal_x] - number_of_black_cell
        print(point)

# ここで必要なチェックを行う
solve()

Submission status: Accepted

Solution code:
from collections import deque


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


def bfs(sx, sy):
    dist = [[-1 for _ in range(W)] for _ in range(H)]
    q = deque()
    q.append((sx, sy))
    dist[sy][sx] = 0

    while q:
        x, y = q.popleft()
        for dx, dy in [(-1, 0), (1, 0), (0, 1), (0, -1)]:
            newx, newy = x+dx, y+dy
            if not (0 <= newx < W):
                continue
            if not (0 <= newy < H):
                continue
            if M[newy][newx] == '#':
                continue
            if dist[newy][newx] != -1:
                continue
            q.append((newx, newy))
            dist[newy][newx] = dist[y][x] + 1
    return dist[H-1][W-1]


step = bfs(0, 0)

if step == -1:
    print(-1)
    exit()

black_after = H * W - step - 1
print(black_after - black_before)

Submission status: Accepted

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

ans = 0
for i in range(h): ans += s[i].count(".")
dist = [[-1 for _ in range(w)] for _ in range(h)]
dist[0][0] = 1
queue = deque()
queue.append((0,0))
while len(queue) != 0:
    cx,cy = queue.popleft()
    if cx == h-1 and cy == w-1: 
        ans -= dist[cx][cy]
        break
    for dx,dy in ((1,0),(-1,0),(0,1),(0,-1)):
        nx,ny = cx+dx,cy+dy
        if 0 <= nx < h and 0 <= ny < w and s[nx][ny] == "." and dist[nx][ny] == -1:
            queue.append((nx,ny))
            dist[nx][ny] = dist[cx][cy] + 1
else:
    ans = -1

print(ans)

Submission status: Accepted

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

inf = float('inf')
G = [[inf] * H * W for _ in range(H * W)]

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

for h in range(H):
    for w in range(W):
        for x, y in zip(dx, dy):
            nx = w + x
            ny = h + y
            if 0 <= nx < W and 0 <= ny < H and S[ny][nx] != '#':
                G[W * h + w][W * ny + nx] = 1

from scipy.sparse.csgraph import dijkstra

d = dijkstra(G, indices=0)
if d[-1] == inf:
    print(-1)
else:
    print(int(ans - d[-1] - 1))

Submission status: Accepted

Solution code:
from collections import deque


H,W = map(int, input().split())
S = [""] * H
b = 0

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

cost = [[0 for _ in range(W)] for _ in range(H)]
cost[0][0] = 1




q = deque()
q.append((0,0))
while q:
    y,x = q.popleft()

    if 0 <= x - 1 <= W - 1 and cost[y][x-1] == 0 and S[y][x-1] == ".":
        cost[y][x-1] = cost[y][x] + 1
        q.append((y, x-1))
    if 0 <= x + 1 <= W - 1 and cost[y][x+1] == 0 and S[y][x+1] == ".":
        cost[y][x+1] = cost[y][x] + 1
        q.append((y, x+1))

    if 0 <= y - 1 <= H - 1 and cost[y-1][x] == 0 and S[y-1][x] == ".":
        cost[y-1][x] = cost[y][x] + 1
        q.append((y-1, x))

    if 0 <= y + 1 <= H - 1 and cost[y+1][x] == 0 and S[y+1][x] == ".":
        cost[y+1][x] = cost[y][x] + 1
        q.append((y+1, x))

if cost[H-1][W-1] == 0:
    print(-1)
else:
    print(H*W - b - cost[H-1][W-1])

Submission status: Accepted

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

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

directions = [[1, 0], [-1, 0], [0, 1], [0, -1]]

from collections import deque
que = deque([])
# スタート地点を追加する
que.append((0, 0))
d[0][0] = 0

while que:
    x, y = que.popleft()
    if x == h-1 and y == w-1:
        break
    for i in range(4):
        dx, dy = directions[i]
        nx = x + dx
        ny = y + dy
        if 0 <= nx < h and 0 <= ny < w and field[nx][ny] =='.' and d[nx][ny] == -1:
            que.append((nx, ny))
            d[nx][ny] = d[x][y] + 1   
            

if d[h-1][w-1] == -1:
    print(-1)
else:
    white = sum(field, []).count('.')
    print(white - (d[h-1][w-1] + 1))

Submission status: Accepted

Solution code:
from collections import deque

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

q= deque([[0,0]])
f=[[-1 for j in range(W)]for i in range(H)]
f[0][0] = 0
dxy=[[1,0],[-1,0],[0,1],[0,-1]]

while q:
    x,y =q.popleft() 
    for dx,dy in dxy:
        dx += x
        dy += y
        if dx >=0 and dy >= 0 and dx<H and dy<W:
            if s[dx][dy] == "." and f[dx][dy]==-1:
                f[dx][dy] = f[x][y]+1
                q.append([dx,dy])

res = 0
for i in range(H):
    res += s[i].count(".")
if f[H-1][W-1]==-1:
    print(-1)
else:
    print(res - f[H-1][W-1] -1)

Submission status: Accepted

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

def calcDist(startIdx, area):
     que = [startIdx]
     dist = [[-1 for i in range(W)] for i in range(H)]
     dist[startIdx[0]][startIdx[1]] = 0
     
     while len(que) != 0:
         idx = que.pop(0)
         
         if idx[0]-1 >= 0 and area[idx[0]-1][idx[1]] != '#' and dist[idx[0]-1][idx[1]] == -1:
             que.append([idx[0]-1, idx[1]])
             dist[idx[0]-1][idx[1]] = dist[idx[0]][idx[1]] + 1
         
         if idx[0]+1 < H and area[idx[0]+1][idx[1]] != '#' and dist[idx[0]+1][idx[1]] == -1:
             que.append([idx[0]+1, idx[1]])
             dist[idx[0]+1][idx[1]] = dist[idx[0]][idx[1]] + 1
             
         if idx[1]-1 >= 0 and area[idx[0]][idx[1]-1] != '#' and dist[idx[0]][idx[1]-1] == -1:
             que.append([idx[0], idx[1]-1])
             dist[idx[0]][idx[1]-1] = dist[idx[0]][idx[1]] + 1
             
         if idx[1]+1 < W and area[idx[0]][idx[1]+1] != '#' and dist[idx[0]][idx[1]+1] == -1:
             que.append([idx[0], idx[1]+1])
             dist[idx[0]][idx[1]+1] = dist[idx[0]][idx[1]] + 1
     
     return dist
     
def searchWhiteNum(area):
    ans = 0
    for i in range(H):
        for j in range(W):
            if area[i][j] == '.':
                ans += 1
    
    return ans

dist = calcDist([0,0], area)
neededWhiteNum = dist[H-1][W-1] + 1
ans = searchWhiteNum(area)
if neededWhiteNum == 0:
    print(-1)
else:
    print(ans-neededWhiteNum)

Submission status: Accepted

Solution code:
from collections import deque

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

count = 0
g = []
g.append(['#'] * (W + 2))
for _ in range(H):
    lst = ['#'] + list(input()) + ['#']
    count += lst.count('.')
    g.append(lst)

g.append(['#'] * (W + 2))
check = [[-1] * (W + 2) for _ in range(H + 2)]

move = [[1, 0], [-1, 0], [0, 1], [0, -1]]


# for G in g:
#     print (G)
x = 1
y = 1
que = deque()
que.append([x, y])
# stack = [[x, y]]
flag = True
check[1][1] = 1
while que:
    tmp = que.popleft()
    x = tmp[0]
    y = tmp[1]
    # print (x, y)
    for dx, dy in move:
        nx = x + dx
        ny = y + dy
        # print (nx, ny)
        if g[nx][ny] == '.' and check[nx][ny] == -1:
            check[nx][ny] = check[x][y] + 1
            que.append([nx, ny])
            # print ('OK')

# for c in check:
#     print (c)

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

print (count - check[H][W])

Submission status: Accepted

Solution code:
import queue

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

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

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

q = queue.Queue()

q.put([0,0])
goal = [h-1,w-1]
visited = [[float('inf') for i in range(w)] for j in range(h)]
visited[0][0]=0

move = [[0,1],[0,-1],[1,0],[-1,0]]

while not q.empty():
    a,b = q.get()
    for y,x in move:
        if 0<=a+y<h and 0<=x+b<w:
            if s[a+y][x+b]=='.' and visited[a+y][x+b]==float('inf'):
                q.put([a+y,x+b])
                visited[a+y][x+b]=visited[a][b]+1

print(white-visited[-1][-1]-1if visited[-1][-1]!=float('inf')else -1)

Submission status: Accepted

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

from collections import deque
dxy = [(0,1),(1,0),(0,-1),(-1,0)]
dist = [[0]*W for i in range(H)]
visited = [[0]*W for i in range(H)]
visited[0][0] = 1
q = deque([(0,0)])
while q:
    x,y = q.popleft()
    for dx,dy in dxy:
        nx,ny = x+dx,y+dy
        if not 0 <= nx < W: continue
        if not 0 <= ny < H: continue
        if visited[ny][nx]: continue
        if S[ny][nx] == '#': continue
        visited[ny][nx] = 1
        dist[ny][nx] = dist[y][x] + 1
        q.append((nx,ny))

dots = sum(row.count('.') for row in S)
print(dots - dist[-1][-1] - 1 if dist[-1][-1] else -1)

Submission status: Accepted

Solution code:
from collections import deque
import sys
sys.setrecursionlimit(1000000)
h, w = map(int, input().split())
start_y = 0
start_x = 0
goal_y = h - 1
goal_x = w - 1
field = []
for _ in range(h):
    field.append(list(input()))

# '#'の数を数える
black_count = 0
for i in range(h):
    for j in range(w):
        if field[i][j] == '.':
            black_count += 1

dy = [1, -1, 0, 0]
dx = [0, 0, 1, -1]
distance = [[-1] * w for i in range(h)]
que = deque([])
que.append([start_y, start_x])
distance[start_y][start_x] = 0

while que:
    q = que.popleft()
    if q[0] == goal_y and q[1] == goal_x:
        break
    for i in range(4):
        now_y = q[0] + dy[i]
        now_x = q[1] + dx[i]
        if now_y < 0 or now_y >= h or now_x < 0 or now_x >= w or field[now_y][now_x] == '#':
            continue
        if distance[now_y][now_x] != -1:
            continue
        que.append([now_y, now_x])
        distance[now_y][now_x] = distance[q[0]][q[1]] + 1

if distance[goal_y][goal_x] == -1:
    result = -1
else:
    result = black_count - (distance[goal_y][goal_x] + 1)
print(result)

Submission status: Accepted

Solution code:
from collections import deque

def solve(h, w, S):
    cands = ((0, 1), (0, -1), (1, 0), (-1, 0))
    q = deque(maxlen = h * w)
    q.append((1, 1, 1))
    s = {(1, 1)}
    min_len = -1
    while len(q) > 0:
        x, y, d = q.popleft()
        for dx, dy in cands:
            if x + dx == w and y + dy == h:
                min_len = d + 1
                q.clear()
                break
            if  1 <= x + dx <= w \
                and 1 <= y + dy <= h \
                and S[y + dy - 1][x + dx - 1] == '.' \
                and (x + dx, y + dy) not in s:
                q.append((x + dx, y + dy, d + 1))
                s.add((x + dx, y + dy))
    return (sum(l == '.' for s in S for l in s) - min_len) if min_len >= 0 else -1

_h, _w = map(int, input().split())
_S = [input() for _ in range(_h)]
print(solve(_h, _w, _S))

Submission status: Accepted

Solution code:
H, W = map(int, input().split())
G = [list(input()) for _ in range(H)]
que = [[0,0]]
dist = [[-1]*W for _ in range(H)]
direction = [[0,1], [0,-1], [1,0], [-1,0]]

dist[0][0] = 0
while que:
  h, w = que.pop(0) 
  for dh, dw in direction:
    if h+dh <0 or h+dh >= H or w+dw <0 or w+dw >= W:
      continue
    if G[h+dh][w+dw] == '#':
      continue
    if dist[h+dh][w+dw] != -1:
      continue
    dist[h+dh][w+dw] = dist[h][w] +1 
    que.append([h+dh, w+dw])

if dist[H-1][W-1] == -1:
  print(-1)
else:
  num = 0
  for i in range(H):
    num += G[i].count('#')
  print(H*W-num-dist[H-1][W-1]-1)

Submission status: Accepted

Solution code:
from collections import deque

h, w = map(int, input().split())
maze = [list(input()) for a in range(h)]
visited = [[0]*w for a in range(h)]

dy = [0,1,0,-1]
dx = [1,0,-1,0]
def bfs():
    que = deque([])
    que.append((0,0))
    visited[0][0]=0

    while que:
        p = que.popleft()

        if p[0]==h-1 and p[1]==w-1:
            break

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

            if 0<=ny<h and 0 <=nx<w and maze[ny][nx]=='.' and visited[ny][nx]==0:
                visited[ny][nx]=visited[p[0]][p[1]]+1
                que.append((ny,nx))

    return visited[h-1][w-1]

ans = bfs()
if ans == 0:
    print(-1)
else:
    cnt = 0
    for i in range(h):
        for j in range(w):
            if maze[i][j]=='#':
                cnt +=1

    print(h*w-cnt-ans-1)

Submission status: Accepted

Solution code:
import sys
import numpy as np
H, W = map(int, input().split())
grid = np.array([list(map(str, input())) for _ in range(H)])

X = np.where(grid == '#')
A = np.zeros([H,W])
A[X] = 1
orig_black = np.count_nonzero(grid=='#')

q = [[0,0,0]]
while q:
	cx,cy,cd = q.pop(0)
	if cx == H-1 and cy == W-1:
		shortest = cd
		break
	elif A[cx,cy] == -1:
		continue

	A[cx,cy] = -1

	for nx,ny in [[cx+1,cy],[cx-1,cy],[cx,cy+1],[cx,cy-1]]:
		if 0 <= nx < H and 0 <= ny < W:
			if A[nx][ny] == 0:
				q.append([nx,ny,cd+1])

	if q == []:
		print(-1)
		sys.exit()

print((H*W)-shortest-orig_black-1)

Submission status: Accepted

Solution code:
from collections import deque
H, W = list(map(int, input().split()))
A = []
for _ in range(H):
  A.append(input())
  
#blank count
bcount = 0
for i in range(H):
  for j in range(W):
    if A[i][j] == ".":
      bcount += 1
      
d = deque()
dist = [[-1 for j in range(W)] for i in range(H)]
visited = [[False for j in range(W)] for i in range(H)]
willsearch = [[False for j in range(W)] for i in range(H)]

d.append([0,0])
dist[0][0] = 0

while len(d) > 0:
  x,y = d.popleft()
  visited[x][y] = True
  for a,b in [[x+1,y], [x-1,y], [x,y+1], [x,y-1]]:
    if not (0 <= a and a < H and 0 <= b and b < W) :
      continue
    if A[a][b] == '#':
      continue
    if visited[a][b] or willsearch[a][b]:
      continue
    willsearch[a][b] = True
    d.append([a,b])
    dist[a][b] = dist[x][y] + 1
    
if not visited[H-1][W-1]:
  print(-1)
else:
  print(bcount - dist[H-1][W-1]-1)
  
#print(dist)