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:
mod = 10 ** 9 + 7
mod2 = 2 ** 61 + 1
from collections import deque
import heapq
import time
from bisect import bisect_left, insort_left, bisect_right
import sys
import random
import itertools

input = sys.stdin.readline
_NUMINT_ALL = list(range(10))
_START_TIME = time.time()
INDEX_KETA = 10**12

def main():
    ans = solve()

    if ans is True or ans is False:
        YesNo(ans)
    elif ans is None:
        return

    if isinstance(ans, tuple):
        split_print_space(ans)
    else:
        print(ans)


def solve():

    H, W = iip()
    maze = []
    for y in range(H):
        maze.append([0 if i == "." else 1 for i in input().strip()])

    num_white = W*H - sum(flatten(maze))

    que = deque()
    que.append((0, 0, 1))

    while que:
        x, y, depth = que.popleft()
        #print(x, y)

        for xx, yy in [(x+1, y), (x-1, y), (x, y+1), (x, y-1)]:
            if xx == -1 or xx == W or yy == -1 or yy == H:
                continue
            if maze[yy][xx] == 1:
                continue
            #print("a", xx, yy)
            if (xx, yy) == (W-1, H-1):
                #print("i")
                #print(num_white)
                #print(depth)
                return num_white - depth - 1

            maze[yy][xx] = 1
            que.append((xx, yy, depth+1))

    return -1







#####################################################ライブラリ集ここから



def kiriage_warizan(a, b):
    return -(-a//b)


def iip(listed=False):  # 数字のinputをlistで受け取る
    d = input().rstrip("\n").split()
    try:
        ret = [int(i) for i in d]
    except:
        ret = [int(i) if i in _NUMINT_ALL else i for i in d]
        if len(ret) == 1 and listed is False:
            return ret[0]

    if len(ret) == 1 and not listed:
        return ret[0]
    return ret

def iipt(l, listed=True, num_only=True):  # 縦向きに並んでいるデータをリストに落とし込む(iip利用)
    if isinstance(l, list):
        l = l[0] # 間違って要素１個のタプルを渡されても受け取る
    ret = []
    for i in range(l):
        ret.append(iip(listed=listed))
    return ret


def saidai_kouyakusuu(A):  # 最大公約数
    l = len(A)
    while True:
        m = min(A)
        mx = max(A)
        if m == mx:
            return m

        for i in range(l):
            if A[i] % m == 0:
                A[i] = m
            else:
                A[i] %= m


def flatten(l):
    return list(itertools.chain.from_iterable(l))


def index_sorted(sorted_list, target):
    idx = bisect_left(sorted_list, target)
    if idx != len(sorted_list) and sorted_list[idx] == target:
        return idx
    else:
        return False


def time_debug_10percent():
    a = random.randint(0, 9)
    if a == 9:
        sys.exit()

def time_debug(t):
    time.sleep(_START_TIME + t - time.time())
    sys.exit()


def make_graph_edge_flat(N):  # グラフ作成のための辺をリストで返す
    ret = []
    for i in range(N-1):
        a, b, c = iip()
        a -= 1
        b -= 1
        ret[a].append((b, c))
        ret[b].append((a, c))
    return ret


def sort_tuples(l, index):  # タプルのリストを特定のインデックスでソートする
    if isinstance(l, list):
        l.sort(key=lambda x: x[index])
        return l
    else:
        l = list(l)
        return sorted(l, key=lambda x: x[index])


def count_elements(l):  # リストの中身の個数を種類分けして辞書で返す
    d = {}
    for i in l:
        if i in d:
            d[i] += 1
        else:
            d[i] = 1
    return d


def safeget(l, index, default="exception"):  # listの中身を取り出す時、listからはみ出たり
    if index >= len(l):                      # マイナスインデックスになったりするのを防ぐ
        if default == "exception":
            raise Exception("".join(["safegetに不正な値 ", index, "が渡されました。配列の長さは", len(l), "です"]))
        else:
            return default
    elif index < 0:
        if default == "exception":
            raise Exception("".join(["safegetに不正な値 ", index, "が渡されました。負の値は許可されていません"]))
        else:
            return default
    else:
        return l[index]


def sortstr(s):  # 文字列をソートする
    return "".join(sorted(s))


def iip_ord(startcode="a"):  # 文字列を数字の列に変換する(数字と文字は1:1対応)
    if isinstance(startcode, str):
        startcode = ord(startcode)
    return [ord(i) - startcode for i in input()]


def YesNo(s):  # TrueFalseや1, 0をYesNoに変換する
    if s:
        print("Yes")
    else:
        print("No")


def fprint(s):  # リストを平たくしてprintする(二次元リストを見やすくしたりとか)
    for i in s:
        print(i)


def bitall(N):  # ビット全探索用のインデックスを出力
    ret = []
    for i in range(2 ** N):
        a = []
        for j in range(N):
            a.append(i % 2)
            i //= 2
        ret.append(a)
    return ret

def split_print_space(s):  # リストの中身をスペース区切りで出力する
    print(" ".join([str(i) for i in s]))


def split_print_enter(s):  # リストの中身を改行区切りで出力する
    print("\n".join([str(i) for i in s]))


def soinsuu_bunkai(n):  # 素因数分解
    ret = []
    for i in range(2, int(n ** 0.5) + 1):
        while n % i == 0:
            n //= i
            ret.append(i)
        if i > n:
            break
    if n != 1:
        ret.append(n)
    return ret


def conbination(n, r, mod, test=False):  # nCrをmodを使って計算する
    if n <= 0:
        return 0
    if r == 0:
        return 1
    if r < 0:
        return 0
    if r == 1:
        return n
    ret = 1
    for i in range(n - r + 1, n + 1):
        ret *= i
        ret = ret % mod

    bunbo = 1
    for i in range(1, r + 1):
        bunbo *= i
        bunbo = bunbo % mod

    ret = (ret * inv(bunbo, mod)) % mod
    if test:
        # print(f"{n}C{r} = {ret}")
        pass
    return ret


def inv(n, mod):  #  modnにおける逆元を計算
    return power(n, mod - 2)


def power(n, p, mod_=mod):  # 繰り返し二乗法でn**p % modを計算
    if p == 0:
        return 1
    if p % 2 == 0:
        return (power(n, p // 2, mod_) ** 2) % mod_
    if p % 2 == 1:
        return (n * power(n, p - 1, mod_)) % mod_


def nibutan_func(func, target, left, right, side="left", seido = 1): # 関数を二分探索
    l = left
    r = right
    if seido == 1:
        x = (l + r) // 2
    else:
        x = (l + r) / 2
    while r-l > seido:
        #print(x)
        if seido == 1:
            x = (l + r) // 2
        else:
            x = (l + r) / 2
        if func(x) == target:
            if side == "left":
                r=x
            else:
                l=x


        elif func(x) > target:
            r = x
        else:
            #print(r, l)
            l = x

    #print(l, r)
    if side == "left" and func(r) == target:
        return r
    elif side != "left" and func(l) == target:
        return l
    elif side == "left":
        return l
    else:
        return r


def nibutan_list(list_, target, side="left"):  # リストを二分探索
    if not isinstance(list_, list):
        list_ = list(list_)

    l = 0
    r = len(list_)
    x = (l + r) // 2
    while r-l > 1:
        x = (l+r)//2
        if list_[x] == target:
            return x
        elif list_[x] > target:
            r = x
        else:
            l = x

    if side == "left" or list_[x] == target:
        return l
    else:
        return r


class UfTree():
    def __init__(self, maxnum):
        self.parent = list(range(maxnum))
        self._size = [1] * maxnum
        self.rank = [0] * maxnum

    def size(self, a):
        return self._size[self.root(a)]

    def root(self, a):
        rank = 0
        cur = a
        while True:
            if self.parent[cur] == cur:
                #for i in path: # 経路圧縮
                #    self.parent[i] = cur
                return cur
            else:
                self.parent[cur] = self.parent[self.parent[cur]]
                cur = self.parent[cur]
                rank += 1

    def unite(self, a, b):
        ra = self.root(a)
        rb = self.root(b)
        if ra == rb:
            return self

        self._size[ra] += self._size[rb]
        self.parent[rb] = ra
        return self

if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
#ABC088-D-Greid Repainting
from collections import deque

h,w = map(int,input().split())
grid = ["" for _ in range(h)]

#'#'の個数-> cnt
cnt = 0
for i in range(h):
    grid[i] = input()
    cnt += grid[i].count('#')
        
dist = [[float('inf') for _ in range(w)] for _ in range(h)]

dist[0][0] = 0

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

while P:
    p = P.popleft()
    x,y = p[0],p[1]
    for dx,dy in ((1,0),(0,1),(-1,0),(0,-1)):
        nx,ny = x + dx, y+dy
        if 0 <= nx and 0 <= ny and nx <= h-1 and ny <= w-1 and grid[nx][ny] == '.' and dist[nx][ny] == float('inf'):
            dist[nx][ny] = dist[x][y] + 1
            P.append((nx,ny))
            
if dist[h-1][w-1] == float('inf'):
    print(-1)
    
else:
    print(h*w - dist[h-1][w-1] - cnt -1)

Submission status: Accepted

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

maze=[]
maze.append(["#" for i in range(2+w)])

for i in range(h):
    x=list(input())
    x.insert(0,"#")
    x.append("#")
    maze.append(x)
    
maze.append(["#" for i in range(2+w)])
#(1,1)から(h,w)に最短距離でどのくらいでいけるのかどうか調べる
visited=[[False for i in range(w+2)] for j in range(h+2)]
for i in range(h+2):
    for j in range(w+2):
        if (i==0 or i==h+1) or (j==0 or j==w+1):
            visited[i][j]=True
#visited[u][v]=(u,v)にすでに訪れたことがあるのかどうか
from collections import deque
visited[1][1]=True
d=deque()
e=deque()
d.append((1,1))
distance=0

capable=False

while (not capable) and d:
    distance+=1
    while d:
        X=d.popleft()
        x,y=X[0],X[1]
        if visited[x][y+1]==False and maze[x][1+y]==".":
            visited[x][y+1]=True
            e.append((x,1+y))
        if visited[x][y-1]==False and maze[x][y-1]==".":
            visited[x][y-1]=True
            e.append((x,y-1))
        if visited[x-1][y]==False and maze[x-1][y]==".":
            visited[x-1][y]=True
            e.append((x-1,y))
        if visited[x+1][y]==False and maze[x+1][y]==".":
            visited[x+1][y]=True
            e.append((x+1,y))
    if e:
        d=e
        e=deque()
    if visited[h][w]==True:
        capable=True
cnt=0

for i in range(h+2):
    for j in range(w+2):
        if maze[i][j]==".":
            cnt+=1
if capable:
    print(cnt-distance-1)
else:
    print(-1)

Submission status: Accepted

Solution code:
from collections import deque
h, w = map(int, input().split())
maze = ["#"*(w+2)]
white_cnt = 0
for _ in range(h):
    row = input()
    white_cnt += row.count('.')
    maze.append("#"+row+"#")
else:
    maze.append("#"*(w+2))

w += 2
h += 2
INF = 10**9
dist = [[INF]*w for _ in range(h)]
dist[1][1] = 0
next_block = deque([(1, 1)])
dirc = [(-1, 0), (0, 1), (1, 0), (0, -1)]
cnt = 0
while next_block:
    i, j = next_block.popleft()
    for x, y in dirc:
        if maze[i+x][j+y] == '#':
            continue
        if dist[i+x][j+y] <= dist[i][j]+1:
            continue
        dist[i+x][j+y] = dist[i][j]+1
        next_block.append((i+x, j+y))


if dist[-2][-2] == INF:
    print(-1)
else:
    print(white_cnt-dist[-2][-2]-1)

Submission status: Accepted

Solution code:
from collections import deque
h, w = map(int, input().split())
maze = ["#"*(w+2)]
white_cnt = 0
for _ in range(h):
    row = input()
    white_cnt += row.count('.')
    maze.append("#"+row+"#")
else:
    maze.append("#"*(w+2))

w += 2
h += 2
INF = 10**9
dist = [[INF]*w for _ in range(h)]
dist[1][1] = 0
next_block = deque([(1, 1)])
dirc = [(-1, 0), (0, 1), (1, 0), (0, -1)]
cnt = 0
while next_block:
    i, j = next_block.popleft()
    for x, y in dirc:
        if maze[i+x][j+y] == '#':
            continue
        if dist[i+x][j+y] != INF:
            continue
        next_block.append((i+x, j+y))
        dist[i+x][j+y] = min(dist[i+x+v][j+y+w] for v, w in dirc)+1

if dist[-2][-2] == INF:
    print(-1)
else:
    print(white_cnt-dist[-2][-2]-1)

Submission status: Accepted

Solution code:
from collections import deque

def bfs():
    d = [[float("inf")] * w for i in range(h)]

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

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

    while que:
        p = que.popleft()
        if p[0] == gx and p[1] == gy:
            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 maze[nx][ny] != "#" and d[nx][ny] == float("inf"):
                que.append((nx, ny))
                d[nx][ny] = d[p[0]][p[1]] + 1
    
    return d[gx][gy]

h, w = map(int, input().split())
maze = [list(input()) for _ in range(h)]
sx, sy = 0, 0
gx, gy = h-1, w-1

white = 0
for i in range(h):
    for j in range(w):
        if maze[i][j] == ".":
            white += 1

res = bfs()

if 0 < res < float("inf"):
    print(white-res-1)
else:
    print(-1)

Submission status: Accepted

Solution code:
import math
import copy
import sys
import fractions
# import numpy as np
# import statistics
import decimal
import heapq
import collections
import itertools
import bisect

# from operator import mul

sys.setrecursionlimit(100001)


# input = sys.stdin.readline
# sys.setrecursionlimit(10**6)

# ===FUNCTION===

def getInputIntList():
    outputDataList = []
    inputData = input().split()
    outputDataList = [int(n) for n in inputData]

    return outputDataList


def getSomeInputInt(n):
    outputDataList = []
    for i in range(n):
        inputData = int(input())
        outputDataList.append(inputData)

    return outputDataList


def getSomeInputListInt(n):
    inputDataList = []
    outputDataList = []
    for i in range(n):
        inputData = input().split()
        inputDataList = [int(n) for n in inputData]
        outputDataList.append(inputDataList)

    return outputDataList


# ===CODE===

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

table = [[1 for _ in range(w)] for _ in range(h)]
d_table = [[-1 for _ in range(w)] for _ in range(h)]

for i in range(h):
    s = input()
    tmp = list(s)
    for j, ts in enumerate(tmp):
        if ts == ".":
            table[i][j] = 0

ans = -1
search_table = [[-1, 0], [1, 0], [0, -1], [0, 1]]

q = collections.deque([])
q.append([0,0])
table[0][0]=1
d_table[0][0]=0

gy, gx = [h-1, w-1]

while len(q) > 0:
    qy, qx = q.popleft()

    for y, x in search_table:
        cy = qy + y
        cx = qx + x

        if cy < 0 or cy > h - 1 or cx < 0 or cx > w - 1:
            continue

        if table[cy][cx] == 0 and d_table[cy][cx] == -1:
            table[cy][cx] = 1
            d_table[cy][cx] = d_table[qy][qx] + 1
            q.append([cy, cx])

            if cy == gy and cx == gx:
                ans = d_table[cy][cx]

if ans == -1:
    print(-1)
    exit(0)

cnt = 0

for i in range(h):
    for j in range(w):
        tmp = d_table[i][j]
        if tmp > -1:
            cnt+=1
        elif tmp == -1 and table[i][j]==0:
            cnt+=1

res = cnt -ans -1



print(res)

Submission status: Accepted

Solution code:
import queue

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

def bfs():
    start=[0,0]
    goal=[W-1,H-1]
    distance=[[-1]*H for j in range(W)]
    li_x=[1,-1,0,0]
    li_y=[0,0,1,-1]
    q = queue.Queue()
    q.put(start)
    distance[start[0]][start[1]]=1

    while not q.empty():
        hoge=q.get()
        x=hoge[0]
        y=hoge[1]
        dis=distance[x][y]

        for i in range(4):
            x1=x+li_x[i]
            y1=y+li_y[i]
            if (0 <=x1 < W and 0 <= y1 < H):
                if distance[x1][y1] == -1:
                    if S[y1][x1]=='.':
                        q.put([x1,y1])
                        distance[x1][y1]=dis+1
    m=''
    for i in range(H):
        m+=S[i]
    
    if distance[W-1][H-1]==-1:
        ans=-1 
    else:
        ans=m.count('.')-distance[W-1][H-1]
    return ans

ans=bfs()
print(ans)

Submission status: Accepted

Solution code:
from heapq import heappush, heappop, heapify
from collections import deque, defaultdict, Counter
import itertools
from itertools import permutations, combinations, accumulate
import sys
import bisect
import string
import math
import time


def I(): return int(input())


def MI(): return map(int, input().split())


def S(): return input()


def MS(): return map(str, input().split())


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


def LI_(): return [int(i)-1 for i in input().split()]


def StoI(): return [ord(i)-97 for i in input()]


def ItoS(nn): return chr(nn+97)


def input(): return sys.stdin.readline().rstrip()


def show(*inp, end='\n'):
    if show_flg:
        print(*inp, end=end)


def print_matrix(mat):
    for i in range(len(mat)):
        print(*mat[i])


YNL = {False: 'No', True: 'Yes'}
YNU = {False: 'NO', True: 'YES'}
MOD = 10**9+7
inf = float('inf')
IINF = 10**10
l_alp = string.ascii_lowercase
u_alp = string.ascii_uppercase
ts = time.time()
# sys.setrecursionlimit(10**6)
nums = ['1', '2', '3', '4', '5', '6', '7', '8', '9', '10']


# show_flg = True
show_flg = False

BLOCK = '#'
ROAD = '.'


def bfs(graph, initial, goal, H, W):
    options = [(-1, 0), (0, 1), (1, 0), (0, -1)]
    q = deque([initial])
    visited = [[False for i in range(W)] for i in range(H)]
    dist = [[-1 for i in range(W)] for i in range(H)]
    visited[initial[0]][initial[1]] = True
    dist[initial[0]][initial[1]] = 0

    while len(q) != 0:
        p = q.popleft()

        for d in options:
            i = p[0] + d[0]
            j = p[1] + d[1]

            if i >= 0 and i < H and j >= 0 and j < W and not visited[i][j] and graph[i][j] != BLOCK:
                visited[i][j] = True
                q.append((i, j))
                dist[i][j] = dist[p[0]][p[1]] + 1

    return dist


def main():
    H, W = MI()
    graph = [None] * H

    for i in range(H):
        graph[i] = list(S())

    dist = bfs(graph, (0, 0), (H-1, W-1), H, W)

    if dist[H-1][W-1] == -1:
        print(-1)
        return

    ans = H * W
    # print_matrix(dist)
    for i in range(H):
        for j in range(W):
            if graph[i][j] == '#':
                ans -= 1

    ans -= dist[H-1][W-1] + 1
    print(ans)


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
sys.setrecursionlimit(10 ** 7)

h, w = map(int, readline().split())
s = [input() for i in range(h)]
q = [(0, 0)]
g = (h - 1, w - 1)
test = [(0, 1), (0, -1), (1, 0), (-1, 0)]
inf = float('inf')
dist = [[inf] * w for _ in range(h)]
dist[0][0] = 0
cnt = 0
while 1:
    qq = []
    cnt += 1
    for y, x in q:
        for dy, dx in test:
            yy, xx = y + dy, x + dx
            if xx < 0 or yy < 0 or xx > w - 1 or yy > h - 1:
                continue
            if s[yy][xx] == '#' or dist[yy][xx] != inf:
                continue
            dist[yy][xx] = cnt
            qq.append((yy, xx))
    q = qq
    if g in q:
        break
    if q:
        continue
    else:
        print(-1)
        exit()
for i in range(h):
    for j in range(w):
        if s[i][j] == '#':
            cnt += 1
print(h * w - cnt - 1)

Submission status: Accepted

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

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

d = [[-1]*w for _ in range(h)]
d[0][0] = 1
que = deque([[0, 0]])
while que:
    x, y = que.popleft()
    for i, j in [[1,0],[0,1],[-1,0],[0,-1]]:
        nx, ny = x+i, y+j
        if 0<=nx<w and 0<=ny<h and c[ny][nx]=="." and d[ny][nx]==-1:
            d[ny][nx] = d[y][x]+1
            que.append([nx, ny])
if d[h-1][w-1] == -1:
    print(-1)
else:
    print(ans-d[h-1][w-1])

Submission status: Accepted

Solution code:
from heapq import heappop, heappush
H, W = map(int,input().split())
dire = [(1, 0), (0, 1), (-1, 0), (0, -1)]
mp = [[0] * (W + 2)]
cnt = 0
for i in range(H):
    S = [0]
    for ch in input():
        S.append(ch)
        if ch == ".":
            cnt += 1
    S.append(0)
    mp.append(S)
mp.append([0] * (W + 2))
leng = [[float("inf")] * (W + 2) for _ in range(H + 2)]
leng[1][1] = 1
que = [(1, 1, 1)]
while que:
    cost, i, j = heappop(que)
    if cost != leng[i][j]:
        continue
    for di, dj in dire:
        if mp[i + di][j + dj] == ".":
            if leng[i + di][j + dj] > cost + 1:
                leng[i + di][j + dj] = cost + 1
                heappush(que, (leng[i + di][j + dj], i + di, j + dj))
if leng[H][W] == float("inf"):
    print(-1)
else:
    print(cnt - leng[H][W])

Submission status: Accepted

Solution code:
from collections import deque


def bfs(si, sj, gi, gj):
    q = deque()
    q.append([si, sj, 0])
    used = [[False for _ in range(W)] for _ in range(H)]
    used[si][sj] = True

    while len(q) > 0:
        prvi, prvj, cost = q.popleft()
        for i, j in [[prvi - 1, prvj], [prvi + 1, prvj], [prvi, prvj - 1], [prvi, prvj + 1]]:
            if i == gi and j == gj:
                return cost + 1

            if i < 0 or j < 0 or i >= H or j >= W:
                continue

            if used[i][j] or C[i][j] == '#':
                continue

            q.append([i, j, cost + 1])
            used[i][j] = True
    return -1


if __name__ == '__main__':
    H, W = map(int, input().split())
    C = [input() for _ in range(H)]
    min_cost = bfs(0, 0, H - 1, W - 1)
    if min_cost == -1:
        print(-1)
    else:
        black_num = sum([row.count('#') for row in C])
        print(H * W - black_num - min_cost - 1)

Submission status: Accepted

Solution code:
from collections import deque

H, W = map(int, input().split())
start = [1, 1]
goal  = [H, W]

maps = [[-1]*(W+2)] + [([-1] + list(input()) + [-1]) for _ in range(H)] + [[-1]*(W+2)]
seen = [[-1]*(W+2) for _ in range(H+2)]
dxy = ((-1, 0), (1, 0), (0, -1), (0, 1))
todo = deque()

blacknum = 0
for i in maps:
    blacknum += i.count('#')


def bfs(x, y):
    for i in dxy:
        new_x = x+i[0]
        new_y = y+i[1]
        if seen[new_x][new_y] == -1:
            if maps[new_x][new_y] == '.':
                seen[new_x][new_y] = seen[x][y] + 1
                todo.append([new_x, new_y])
            else:
                seen[new_x][new_y] = -2


todo.append([start[0], start[1]])
seen[start[0]][start[1]] = 1

while len(todo) > 0:
    tmp = todo.popleft()
    bfs(tmp[0], tmp[1])

if seen[H][W] < 0:
    print(-1)
else:
    print(H*W-blacknum-seen[H][W])

Submission status: Accepted

Solution code:
from collections import deque
h, w = map(int, input().split())
map = [ list(input()) for _ in range(h) ]
ans = 0
for i in range(h):
    l = map[i]
    ans += l.count(".")

def bfs(x, y):
    for (next_x, next_y) in [(x + 1, y), (x - 1, y), (x, y + 1), (x, y - 1)]:
        if 0 <= next_x < h and 0 <= next_y < w and map[next_x][next_y] == ".":
            map[next_x][next_y] = 1 + map[x][y]
            q.append([next_x, next_y])

map[0][0] = 1
q = deque([[0, 0]])
while True:
    if len(q) == 0:
        break
    x, y = q.popleft()
    bfs(x, y)

if map[h-1][w-1] == ".":
    ans = -1
else:
    ans -= map[h-1][w-1]

print(ans)

Submission status: Accepted

Solution code:
h,w=map(int, input().split())
m=[input() for _ in range(h)] 
#m = Input.split()
from collections import deque
cnt_black = 0
for y in range(h):
    for x in range(w):
        if(m[y][x]=='#'):
            cnt_black += 1
cnt_white =h*w-cnt_black

sy,sx = 0,0
#q: 次に訪れる予定の座標
q = deque([(sy,sx)])
#print(q)

#カウンタ
cnt = [[-1]*w for _ in range(h)]
cnt[sy][sx]=0
while q:
    cy,cx = q.popleft() #popleftで幅、popで深さ
    for dy,dx in ([1,0],[-1,0],[0,1],[0,-1]):
        ny, nx = cy + dy, cx + dx
        if(0<=ny<h and 0<=nx<w and cnt[ny][nx]==-1 and m[ny][nx]!='#'):
            #print(cy,cx,ny,nx)
            cnt[ny][nx] = cnt[cy][cx]+1
            q.append((ny,nx))
            #print(q)
            #pprint(cnt)
if(cnt[h-1][w-1]==-1):
    ans = -1
else:
    ans = cnt_white-1-cnt[h-1][w-1]
print(ans)

Submission status: Accepted

Solution code:
from collections import deque
H, W = map(int, input().split())
grid = []
for _ in range(H):
    array = input()
    grid.append(array)
# print(grid)
#もともとの黒いマス目の数をカウント
count = 0
for i in range(H):
    for j in range(W):
        if grid[i][j] == '#':
            count+=1
# print(count)

dist = [[-1]*W for _ in range(H)]
# print(dist)

dist[0][0] = 0
dy = [0,0,1,-1]
dx = [-1,1,0,0]
que = deque()
que.append([0,0])

while que:
    y,x = que.popleft()
    for i in range(4):
        vy = y + dy[i] 
        vx = x + dx[i] 
        if vy < 0 or H <= vy or vx < 0 or W <= vx:
            continue
        if dist[vy][vx] != -1 or grid[vy][vx] == '#':
            continue
        dist[vy][vx] = dist[y][x] + 1
        que.append([vy,vx])

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

Submission status: Accepted

Solution code:
from collections import deque

h, w = map(int, input().split())
mapping = [0]*h
#入力の受け取り
for i in range(h):
    mapping[i] = input()

#壁の検出
wall = 0
yet = [[False]*w for i in range(h)]
for i in range(h):
    for j in range(w):
        if mapping[i][j] == "#":
            yet[i][j] = True
            wall += 1

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

not_yet = deque([[0, 0]])
yet[0][0] = True

#本番   
while len(not_yet) > 0:
    key = not_yet.popleft()
    a, b = key[0], key[1]
        
    if a != 0 and not yet[a-1][b]:
        not_yet.append([a-1, b])
        yet[a-1][b] = True
        depth[a-1][b] = depth[a][b]+1
            
    if a != h-1 and not yet[a+1][b]:
        not_yet.append([a+1, b])
        yet[a+1][b] = True
        depth[a+1][b] = depth[a][b]+1
            
    if b != 0 and not yet[a][b-1]:
        not_yet.append([a, b-1])
        yet[a][b-1] = True
        depth[a][b-1] = depth[a][b]+1
            
    if b != w-1 and not yet[a][b+1]:
        not_yet.append([a, b+1])
        yet[a][b+1] = True
        depth[a][b+1] = depth[a][b]+1
if depth[h-1][w-1]:
  print(h*w-depth[h-1][w-1]-1-wall)
else:
  print(-1)

Submission status: Accepted

Solution code:
from collections import deque
h,w = list(map(int, input().split()))
s = ['#'*(w+2)]
[s.append('#'+input()+'#') for _ in range(h)]
s.append('#'*(w+2))
whitecount = 0
for i in s:
    whitecount += i.count('.')

ans = 0
queue = deque([[1,1]])
cost = [[1]*(w+2) for _ in range(h+2)]
visited = [[False]*(w+2) for _ in range(h+2)]
while queue:
    x,y = queue.popleft()
    visited[y][x] = True
    hjkl = [[x-1,y], [x,y-1], [x+1,y], [x,y+1]]
    for dx,dy in hjkl:
        if (s[dy][dx]=='.') and (visited[dy][dx]==False) and ([dx,dy] not in queue):
            queue.append([dx,dy])
            cost[dy][dx] = cost[y][x] + 1

if visited[h][w]:
    print(whitecount - cost[h][w])
else:
    print(-1)

Submission status: Accepted

Solution code:
from collections import deque

def dfs(sx, sy):
  stack = deque()
  stack.append([sx, sy])
  visited[sy][sx] = 1
  while stack:
    x, y = stack.popleft()
    if x == w - 1 and y == h - 1:
      break
    for dx, dy in [(1, 0), (-1, 0), (0, 1), (0, -1)]:
      if 0 <= x + dx < w and 0 <= y + dy < h:
        if S[y + dy][x + dx] != "#" and visited[y + dy][x + dx] == -1:
          visited[y + dy][x + dx] = visited[y][x] + 1
          stack.append([x + dx, y + dy])

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

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

dfs(0, 0)

whites = sum([s.count(".") for s in S])

if visited[h - 1][w - 1] != -1:
  ans = whites - visited[h - 1][w - 1]
else:
  ans = -1
  
print(ans)

Submission status: Accepted

Solution code:
import sys
from collections import deque
MAX_INT = int(10e10)
MIN_INT = -MAX_INT
mod = 1000000007
sys.setrecursionlimit(1000000)
def IL(): return list(map(int,input().split()))
def SL(): return input().split()
def I(): return int(sys.stdin.readline())
def S(): return input()

H,W = IL()
grid = [list(S()) for i in range(H)]

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

data = [[MAX_INT]*W for i in range(H)]

d = deque()
d.append((1, 0, 0)) # (cnt, h, w)
while d:
  cnt, h, w = d.popleft()
  if data[h][w] > cnt:
    data[h][w] = cnt
    for i,j in ((-1,0), (0,-1),(1,0),(0,1)):
      if 0 <= h+i < H and 0 <= w+j < W:
        if grid[h+i][w+j] == ".":
          d.append((cnt+1, h+i, w+j))
if data[-1][-1] == MAX_INT:
  print(-1)
else:
  print(ans - data[-1][-1])

Submission status: Accepted

Solution code:
from collections import deque

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

count_w = 0
for i in range(H):
    for j in range(W):
        if M[i][j] == ".":
            count_w += 1
            
def bfs():
    que = deque()
    que.append((0,0))
    dx = [0,1,0,-1]
    dy = [-1,0,1,0]
    d = [[float("Inf")]*W for i in range(H)]
    d[0][0] = 0
    while que :
        p = que.popleft()
        for i in range(4):
            nx = p[0] + dx[i]
            ny = p[1] + dy[i]
            if 0 <=nx <H and 0 <= ny <W and M[nx][ny] != "#" and d[nx][ny] == float("Inf"): 
                que.append((nx,ny))
                d[nx][ny] = d[p[0]][p[1]]+1
    if d[H-1][W-1] != float("Inf"):
        return d[H-1][W-1]
    else:
        return -1

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