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())
s = [list(input()) for _ in range(H)]

block_count = 0
for i in range(H):
    for j in range(W):
        if s[i][j] == '#':
            block_count += 1

d = [[0] * W for _ in range(H)]

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

que = deque([])
que.append((0, 0))
d[0][0] = 1
while que:
    x, y = que.popleft()
    
    for dx, dy in dxdy:
        nx = x + dx
        ny = y + dy
        if 0 <= nx < W and 0 <= ny < H and d[ny][nx] == 0 and s[ny][nx] == '.':
            que.append((nx, ny))
            d[ny][nx] = d[y][x] + 1

if d[H-1][W-1]:
    print(H * W - d[H-1][W-1] - block_count)
else:
    print(-1)

Submission status: Accepted

Solution code:
import sys
import heapq
import re
from itertools import permutations
from bisect import bisect_left, bisect_right
from collections import Counter, deque
from fractions import gcd
from math import factorial, sqrt, ceil
from functools import lru_cache, reduce
INF = 1 << 60
MOD = 1000000007
sys.setrecursionlimit(10 ** 7)

# UnionFind
class UnionFind():
    def __init__(self, n):
        self.n = n
        self.parents = [-1] * n

    def find(self, x):
        if self.parents[x] < 0:
            return x
        else:
            self.parents[x] = self.find(self.parents[x])
            return self.parents[x]

    def union(self, x, y):
        x = self.find(x)
        y = self.find(y)

        if x == y:
            return

        if self.parents[x] > self.parents[y]:
            x, y = y, x

        self.parents[x] += self.parents[y]
        self.parents[y] = x

    def size(self, x):
        return -self.parents[self.find(x)]

    def same(self, x, y):
        return self.find(x) == self.find(y)

    def members(self, x):
        root = self.find(x)
        return [i for i in range(self.n) if self.find(i) == root]

    def roots(self):
        return [i for i, x in enumerate(self.parents) if x < 0]

    def group_count(self):
        return len(self.roots())

    def all_group_members(self):
        return {r: self.members(r) for r in self.roots()}

    def __str__(self):
        return '\n'.join('{}: {}'.format(r, self.members(r)) for r in self.roots())

def is_prime(n):
    if n == 1:
        return False
    for i in range(2,int(n**0.5)+1):
        if n % i == 0:
            return False
    return True


# ワーシャルフロイド (任意の2頂点の対に対して最短経路を求める)
# 計算量n^3 (nは頂点の数)
def warshall_floyd(d, n):
    #d[i][j]: iからjへの最短距離
    for k in range(n):
        for i in range(n):
            for j in range(n):
                d[i][j] = min(d[i][j],d[i][k] + d[k][j])
    return d


# ダイクストラ
def dijkstra_heap(s, edge, n):
    #始点sから各頂点への最短距離
    d = [10**20] * n
    used = [True] * n #True:未確定
    d[s] = 0
    used[s] = False
    edgelist = []
    for a,b in edge[s]:
        heapq.heappush(edgelist,a*(10**6)+b)
    while len(edgelist):
        minedge = heapq.heappop(edgelist)
        #まだ使われてない頂点の中から最小の距離のものを探す
        if not used[minedge%(10**6)]:
            continue
        v = minedge%(10**6)
        d[v] = minedge//(10**6)
        used[v] = False
        for e in edge[v]:
            if used[e[1]]:
                heapq.heappush(edgelist,(e[0]+d[v])*(10**6)+e[1])
    return d

# 素因数分解
def factorization(n):
    arr = []
    temp = n
    for i in range(2, int(-(-n**0.5//1))+1):
        if temp%i==0:
            cnt=0
            while temp%i==0:
                cnt+=1
                temp //= i
            arr.append([i, cnt])

    if temp!=1:
        arr.append([temp, 1])

    if arr==[]:
        arr.append([n, 1])

    return arr

# 2数の最小公倍数
def lcm(x, y):
    return (x * y) // gcd(x, y)

# リストの要素の最小公倍数
def lcm_list(numbers):
    return reduce(lcm, numbers, 1)

# リストの要素の最大公約数
def gcd_list(numbers):
    return reduce(gcd, numbers)

# 素数判定



# limit以下の素数を列挙
def eratosthenes(limit):
    A = [i for i in range(2, limit+1)]
    P = []

    while True:
        prime = min(A)
        
        if prime > sqrt(limit):
            break
            
        P.append(prime)
            
        i = 0
        while i < len(A):
            if A[i] % prime == 0:
                A.pop(i)
                continue
            i += 1
            
    for a in A:
        P.append(a)
            
    return P

# 同じものを含む順列
def permutation_with_duplicates(L):

    if L == []:
        return [[]]

    else:
        ret = []

        # set（集合）型で重複を削除、ソート
        S = sorted(set(L))

        for i in S:

            data = L[:]
            data.remove(i)

            for j in permutation_with_duplicates(data):
                ret.append([i] + j)

        return ret


# ここから書き始める
h, w = map(int, input().split())
s = [[j for j in input()] for i in range(h)]
# print(s)

queue = deque([])
queue.append([0, 0, 0])
visited = [[0 for j in range(w)] for i in range(h)]
saitan = -1
while queue:
    y, x, cnt = queue.popleft()
    if visited[y][x] == 1 or s[y][x] == "#":
        continue
    visited[y][x] = 1
    if y == h - 1 and x == w - 1:
        saitan = cnt
        break
    for i in [[1, 0], [-1, 0], [0, 1], [0, -1]]:
        y2 = y + i[0]
        x2 = x + i[1]
        if 0 <= y2 < h and 0 <= x2 < w:
            queue.append([y2, x2, cnt + 1])
if saitan == -1:
    print(-1)
else:
    cnt2 = 0
    for i in range(h):
        for j in range(w):
            if s[i][j] == ".":
                cnt2 += 1
    # print("cnt2 =", cnt2)
    print(cnt2 - saitan - 1)

Submission status: Accepted

Solution code:
from collections import deque
H,W=map(int,input().split())
G=[input() for i in range(H)]

b_n= [G[i].count("#") for i in range(H)]

root_min=float("inf")
root=deque([[0,0,1]])
F=[[0]*W for i in range(H)]
while len(root)!=0:
  p=root.popleft()
  if p[:2]==[H-1,W-1]:
    print(H*W-p[2]-sum(b_n))
    exit()
  F[p[0]][p[1]]=1
  for i in range(4):
    if i==0:
      n=[max(0,p[0]-1),p[1],p[2]+1]
    elif i==1:
      n=[min(H-1,p[0]+1),p[1],p[2]+1]
    elif i==2:
      n=[p[0],max(0,p[1]-1),p[2]+1]
    else:
      n=[p[0],min(W-1,p[1]+1),p[2]+1]
      
    if G[n[0]][n[1]]=="#":
      continue
    if F[n[0]][n[1]]==1:
      continue
    if n in root:
      continue
    root.append(n)
print(-1)

Submission status: Accepted

Solution code:
import collections,itertools,sys
def S(): return sys.stdin.readline().rstrip()
def LI(): return list(map(int,sys.stdin.readline().rstrip().split()))
H,W = LI()
s = [S() for _ in range(H)]
black_count = 0
for i,j in itertools.product(range(H),range(W)):
    if s[i][j]=='#':
        black_count += 1
dhdw = [[-1,0],[1,0],[0,-1],[0,1]]
min_dist = [[-1]*W for _ in range(H)]
seen = [[0]*W for _ in range(H)]
queue = collections.deque() #位置[行,列]を入れておく
def bfs():
    seen[0][0] = 1
    queue.append([0,0])
    min_dist[0][0] = 1
    while queue:
        qh,qw = queue.popleft()
        for dh,dw in dhdw:
            nh,nw = qh+dh,qw+dw
            if not(0<=nh<=H-1) or not(0<=nw<=W-1) or seen[nh][nw] or s[nh][nw]=='#':
                continue
            if [nh,nw]==[H-1,W-1]:
                return min_dist[qh][qw]+1
            seen[nh][nw] = 1
            queue.append([nh,nw])
            min_dist[nh][nw] = min_dist[qh][qw]+1
    else:
        return -1
min_dist = bfs()
print(H*W-black_count-min_dist if min_dist!=-1 else -1)

Submission status: Accepted

Solution code:
import collections,itertools,sys
def S(): return sys.stdin.readline().rstrip()
def LI(): return list(map(int,sys.stdin.readline().rstrip().split()))
H,W = LI()
s = [S() for _ in range(H)]
black_count = 0
for i,j in itertools.product(range(H),range(W)):
    if s[i][j]=='#':
        black_count += 1
dhdw = [[-1,0],[1,0],[0,-1],[0,1]]
min_dist = [[-1]*W for _ in range(H)]
seen = [[0]*W for _ in range(H)]
queue = collections.deque() #位置[行,列]を入れておく
def bfs():
    seen[0][0] = 1
    queue.append([0,0])
    min_dist[0][0] = 1
    while queue:
        qh,qw = queue.popleft()
        for dh,dw in dhdw:
            nh,nw = qh+dh,qw+dw
            if not(0<=nh<=H-1) or not(0<=nw<=W-1) or seen[nh][nw] or s[nh][nw]=='#':
                continue
            seen[nh][nw] = 1
            queue.append([nh,nw])
            min_dist[nh][nw] = min_dist[qh][qw]+1
bfs()
if min_dist[H-1][W-1]!=-1:
    print(H*W-black_count-min_dist[H-1][W-1])
else:
    print(-1)

Submission status: Accepted

Solution code:
from collections import deque
H, W = map(int, input().split())
area = [['#']*(W+2)]
space = 0
for i in range(H):
    temp = ['#']+list(input())+['#']
    for t in temp:
        if t=='.': space+=1 
    area.append(temp)
area.append(['#']*(W+2))
move = ((1, 0), (-1, 0), (0, 1), (0, -1))

dq = deque([(1,1)])
dist = [[-1]*(W+2) for _ in range(H+2)]
dist[1][1] = 1

while dq:
    nowx, nowy = dq.popleft()
    # if (nowx, nowy) == (W, H): break
    for dx, dy in move:
        nxtx, nxty = nowx+dx, nowy+dy
        if not 0<=nxtx<W+2 and 0<=nxty<H+2: continue
        if dist[nxty][nxtx]>=0 or area[nxty][nxtx]=='#': continue
        dist[nxty][nxtx] = dist[nowy][nowx]+1
        dq.append((nxtx, nxty))
if dist[H][W]==-1: print(-1)
else: print(space-dist[H][W])

Submission status: Accepted

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

city = [list(input()) for i in range(h)]
count = [[-1]*w for i in range(h)]
dx = [0,1,0,-1]
dy = [1,0,-1,0]
que = queue.Queue()

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

def short():
  que.put([0,0])
  count[0][0] = 0
  while not que.empty():
    p = que.get()
    if p[0] == h-1 and p[1] == w-1:
      exit
    for i in range(4):
      ny = p[0] + dy[i]
      nx = p[1] + dx[i]
      if 0 <= nx < w and 0 <= ny < h and city[ny][nx] != "#" and count[ny][nx] == -1:
        que.put([ny,nx])
        count[ny][nx] = count[p[0]][p[1]] + 1    
  return count[h-1][w-1]

if short() >= 0:
  print(white - short() - 1)
else:
  print(short())

Submission status: Accepted

Solution code:
h,w = map(int,input().split())
mapl = [list(input()) for i in range(h)]
searched = [[0 for i in range(w)] for j in range(h)]
s_queue = []
move = ((0,1),(1,0),(-1,0),(0,-1))
def bfs():
    cnt=1
    s_queue.append([0,0,cnt])
    searched[0][0] = 1
    while(len(s_queue)>0):
        y,x,cnt=s_queue.pop(0)
        for a,b in move:
            ny = y+a
            nx = x+b
            if(ny<0 or ny>=h or nx<0 or nx>=w or mapl[ny][nx]=='#'):
                continue
            if(searched[ny][nx]==1):
                continue
            s_queue.append([ny,nx,cnt+1])
            searched[ny][nx]=1
            if(ny==(h-1) and nx==(w-1)):
                return cnt+1
    return -1

cnt = bfs()
if(cnt==(-1)):
    print(cnt)
else:
    dot_c = sum(map(lambda x:x.count('.'),mapl))
    print(dot_c-cnt)

Submission status: Accepted

Solution code:
from collections import deque
h,w=map(int,input().split())
s=[input() for _ in range(h)]
d=[[1,0],[-1,0],[0,1],[0,-1]]
bcnt=0
for i in range(h):
    bcnt+=s[i].count('#')
dist=[[-1]*w for _ in range(h)]
r=deque()
r.append([0,0])
dist[0][0]=0
while r:
    x,y=r.popleft()
    for dx,dy in d:
        nx=x+dx
        ny=y+dy
        nd=dist[y][x]
        if nx>=0 and nx<=w-1 and ny>=0 and ny<=h-1:
            if dist[ny][nx]>-1 or s[ny][nx]=='#':
                continue
            dist[ny][nx]=nd+1
            r.append([nx,ny])
if dist[h-1][w-1]==-1:
    print(-1)
else:
    print(h*w-dist[h-1][w-1]-1-bcnt)

Submission status: Accepted

Solution code:
import queue

h, w = map(int, input().split())
s = '#'*(w+2)
for _ in range(h):
    s += '#' + input() + '#'
s += '#'*(w+2)

def bfs():
    step = [0]*(w+2)*(h+2)
    step[w+2+1] = 1
    q = queue.Queue()
    q.put(w+3)
    while not q.empty():
        x = q.get()
        for i in (1, -1, w+2, -w-2):
            if s[x+i] == '#':
                continue
            if x+i == (w+2)*(h+1) - 2:
                step[x+i] = step[x] + 1
                return step[x+i]
            if step[x+i] == 0:
                step[x+i] = step[x] + 1
                q.put(x+i)
    print(-1)
    exit()

count = 0
for j in range((w+2)*(h+2)):
    if s[j] == '.':
        count += 1

print(count - bfs())

Submission status: Accepted

Solution code:
from sys import stdin, setrecursionlimit
from collections import deque

setrecursionlimit(10 ** 9)


def input():
    return stdin.readline().strip()


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

    gx, gy = H - 1, W - 1
    q = deque([(0, 0)])
    dist = [[-1] * W for _ in range(H)]
    dist[0][0] = 1

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

        for dx, dy in ((-1, 0), (1, 0), (0, -1), (0, 1)):
            nx, ny = x + dx, y + dy
            if 0 <= nx < H and 0 <= ny < W and dist[nx][ny] == -1 and s[nx][ny] == '.':
                q.append((nx, ny))
                dist[nx][ny] = dist[x][y] + 1

    if dist[gx][gy] == -1:
        print(-1)
    else:
        ans = sum(row.count('.') for row in s) - dist[gx][gy]
        print(ans)

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
from sys import stdin, setrecursionlimit
from collections import deque

setrecursionlimit(10 ** 9)


def input():
    return stdin.readline().strip()


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

gx, gy = H - 1, W - 1
q = deque([(0, 0)])
dist = [[-1] * W for _ in range(H)]
dist[0][0] = 1

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

    for dx, dy in ((-1, 0), (1, 0), (0, -1), (0, 1)):
        nx, ny = x + dx, y + dy
        if 0 <= nx < H and 0 <= ny < W and dist[nx][ny] == -1 and s[nx][ny] == '.':
            q.append((nx, ny))
            dist[nx][ny] = dist[x][y] + 1

if dist[gx][gy] == -1:
    print(-1)
else:
    ans = sum(row.count('.') for row in s) - dist[gx][gy]
    print(ans)

Submission status: Accepted

Solution code:
m,n=map(int,input().split())
l=[]
ans=[]
for i in range(m):
  l.append(input())
  ans.append([-1]*n)
ans[0][0]=0
memo=[[-1,0],[1,0],[0,1],[0,-1]]
from collections import deque
d = deque([[0,0]])
while d:
  no=d.popleft()
  for me in memo:
    now=[0,0]
    for i in range(2):
      now[i]=no[i]+me[i]
    if min(now)<0 or now[0]>m-1 or now[1]>n-1 or l[now[0]][now[1]]=='#' or ans[now[0]][now[1]]>-1:
      pass
    else:
      d.append(now)
      ans[now[0]][now[1]]=ans[no[0]][no[1]]+1
if ans[-1][-1]<0:
  print(-1)
else:
  a=n*m-ans[-1][-1]-1
  for i in range(m):
    for j in range(n):
      if l[i][j]=='#':
        a-=1
  print(a)

Submission status: Accepted

Solution code:
from collections import deque

INF = float("inf")

# 入力
H, W = map(int, input().split())

maze = [input() for i in range(H)]

# 移動4方向のベクトル
dx = [1,0,-1,0]
dy = [0,1,0,-1]

# (sx,sy)から(gx,gy)への最短距離を求める
# たどりつけないとINF

def bfs():
    que = deque([])
    # 全ての点をINFで初期化
    d = [[INF]*W for i in range(H)]

    # スタート地点をキューに入れ、その点の距離を0にする
    que.append([0,0])
    d[0][0]= 0

    # キューが空になるまでループ
    while que:
        # キューの先頭を取り出す
        p = que.popleft()
        #取り出してきた状態がゴールなら探索をやめる
        if p[0] == H-1 and p[1] == W-1:
            break
        # 移動4方向をループ
        for i in range(4):
            nx = p[0] + dx[i]
            ny = p[1] + dy[i]

            # 移動が可能化の判定とすでに訪れたことがあるかの判定
            if 0<=nx and nx<H and 0<=ny and ny<W and maze[nx][ny] != '#' and d[nx][ny] == INF:
                # 移動できるならキューに入れ、その点の距離をpからの距離+1で確定する
                que.append([nx,ny])
                d[nx][ny] = d[p[0]][p[1]] + 1
    
    return d[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 < INF:
    print(white - bfs() - 1)
else:
    print(-1)

Submission status: Accepted

Solution code:
h, w = map(int, input().split())
s = [list(input()) for _ in range(h)]
ans = 0
dist = [[0] * w for _ in range(h)]
dist[0][0] = 1
queue = [(0, 0)]
cnt = 0
while len(queue) > 0:
    n_h, n_w = queue.pop(0)
    for i, j in ([0, 1], [1, 0], [0, -1], [-1, 0]):
        y, x = n_h + i, n_w + j
        if 0 <= x < w and 0 <= y < h:
            if s[y][x] == "." and dist[y][x] == 0:
                dist[y][x] = dist[n_h][n_w] + 1
                queue.append([y, x])

if dist[-1][-1] == 0:
    print(-1)
    exit()
for i in range(h):
    for j in range(w):
        if s[i][j] == ".":
            ans += 1
    
print(ans - dist[h - 1][w - 1])

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
from collections import deque


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


def bfs():
    moves = ((1, 0), (0, 1), (-1, 0), (0, -1))
    dists = [[-1] * W for _ in range(H)]
    dists[0][0] = 0
    que = deque()
    que.append((0, 0))
    while len(que):
        ch, cw = que.popleft()
        for dh, dw in moves:
            nh, nw = ch + dh, cw + dw
            if (    0 <= nh < H 
                and 0 <= nw < W 
                and S[nh][nw] == '.' 
                and dists[nh][nw] == -1):
                dists[nh][nw] = dists[ch][cw] + 1
                que.append((nh, nw))

    return dists[-1][-1]


def solve():
    dist = bfs()
    if dist == -1:
        print(-1)
        exit()
    white = sum([1 for row in S for i in row if i == '.'])
    print(white - dist - 1)


solve()

Submission status: Accepted

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

allcnt = 0
for i in range(w):
    for j in range(h):
        if block[j][i] == '.':
            allcnt += 1
import sys
sys.setrecursionlimit(10**6)
# BFSで最短経路を求める。allcnt - (cnt + 1)
INF = float('inf')
AR = [[INF] * w for _ in range(h)]
from collections import deque
# cnt = 0
dy = [1,0,0,-1]
dx = [0,-1,1,0]
def bfs():
    d = deque()
    d.append([0,0])
    while d:
        y,x = d.popleft()
        if y == 0 and x == 0:
            AR[y][x] = 0
        for i in range(4):
            ny = y + dy[i]
            nx = x + dx[i]
            if (not 0 <= ny < h) or (not 0 <= nx < w):
                continue
            if AR[ny][nx] == INF and block[ny][nx] != '#':
                AR[ny][nx] = AR[y][x] + 1
                d.append([ny,nx])
bfs()
if AR[h-1][w-1] == INF:
    print(-1)
else:
    print(allcnt - (AR[h-1][w-1]+1))

Submission status: Accepted

Solution code:
from collections import deque 

def main():
    H, W = map(int, input().split())
    s = []
    num = 0
    for i in range(H):
        s.append(list(input()))
        num += s[i].count("#")
    ans = -1    
    cnt = [[0 for _ in range(W)] for _ in range(H)]
    queue = deque()
    queue.append((0, 0))
    while queue:
        x, y = queue.popleft()
        if(s[x][y] == "#"):
            continue
        if(x == H-1 and y == W-1):
            ans = cnt[x][y]
        s[x][y] = "#"
        
        d = [(-1, 0), (1, 0), (0, 1), (0, -1)]
        for dx, dy in d:
            nx = x + dx
            ny = y + dy
            if(nx < 0 or nx >= H or ny < 0 or ny >= W):
                continue
            queue.append((nx, ny))
            if(s[nx][ny] != "#"):
                cnt[nx][ny] = cnt[x][y]+1
    if(ans == -1):
        print(-1)
    else:
        print(H*W-ans-num-1)
    
main()

Submission status: Accepted

Solution code:
from collections import deque
INF = 10**10
h, w = map(int, input().split())
s = [[s for s in input()] for _ in range(h)]
sx, sy = 0, 0
gx, gy = w-1, h-1

d = [[INF for _ in range(w)] for _ in range(h)]
d[0][0] = 0
que = deque([])
que.append([sx, sy])

x_ = [1, 0, -1, 0]
y_ = [0, 1, 0, -1]

while que:
    x, y = que.popleft()
    if x == gx and y == gy: break
    for dx, dy in zip(x_, y_):
        cx, cy = x + dx, y + dy
        if cx != -1 and cy != -1 and cx != w and cy != h and s[cy][cx] != "#" and d[cy][cx] == INF:
            que.append([cx, cy])
            d[cy][cx] = d[y][x] + 1
if d[h-1][w-1] == INF:
    print(-1)
    exit()
cnt = 0
for hi in range(h):
    for wi in range(w):
        if s[hi][wi] == "#":
            cnt += 1
print(h*w - d[h-1][w-1] - 1 - cnt)

Submission status: Accepted

Solution code:
from collections import deque

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

black=0
for tate in s:
  for yoko in tate:
    if yoko=="#":
      black += 1

def search(y,x,H,W,c,i):
  child=[]      
  if y<H-1:
    if s[y+1][x]=="." and c[y+1][x]==-1:
      c[y+1][x]=i
      child.append([y+1,x])
  if 0<y:
    if s[y-1][x]=="." and c[y-1][x]==-1:
      c[y-1][x]=i
      child.append([y-1,x])
  if 0<x:
    if s[y][x-1]=="." and c[y][x-1]==-1:
      c[y][x-1]=i
      child.append([y,x-1])
  if x<W-1:
    if s[y][x+1]=="." and c[y][x+1]==-1:
      c[y][x+1]=i
      child.append([y,x+1])
  return child

def dfs(y,x,c):
  visited=[[y,x]]
  c[y][x]=0
  i=1
  
  while visited:
    tmp=[]
    for a in visited:
      p=search(a[0],a[1],H,W,c,i)  #listが戻る
      tmp += p
    visited=tmp
    i += 1

dfs(0,0,c)
a=c[-1][-1]
if a==-1:
  print(-1)
else:
  print(H*W-black-a-1)

Submission status: Accepted

Solution code:
from collections import deque
h,w=map(int,input().split())
s=[input() for _ in range(h)]
def bfs(i,j):
  seen=[[-1]*w for _ in range(h)]
  todo=deque([(i,j)])
  seen[i][j]=0
  while len(todo)>0:
    (i,j)=todo.popleft()
    if i>0 and seen[i-1][j]==-1 and s[i-1][j]=='.':
      seen[i-1][j]=seen[i][j]+1
      todo.append((i-1,j))
    if i>0 and seen[i-1][j]==-1 and s[i-1][j]=='#':
      seen[i-1][j]=0
    if i<h-1 and seen[i+1][j]==-1 and s[i+1][j]=='.':
      seen[i+1][j]=seen[i][j]+1
      todo.append((i+1,j))
    if i<h-1 and seen[i+1][j]==-1 and s[i+1][j]=='#':
      seen[i+1][j]=0
    if j>0 and seen[i][j-1]==-1 and s[i][j-1]=='.':
      seen[i][j-1]=seen[i][j]+1
      todo.append((i,j-1))
    if j>0 and seen[i][j-1]==-1 and s[i][j-1]=='#':
      seen[i][j-1]=0
    if j<w-1 and seen[i][j+1]==-1 and s[i][j+1]=='.':
      seen[i][j+1]=seen[i][j]+1
      todo.append((i,j+1))
    if j<w-1 and seen[i][j+1]==-1 and s[i][j+1]=='#':
      seen[i][j+1]=0
  return seen[-1][-1]
b=bfs(0,0)
if b==-1:
  print(-1)
  exit()
c=0
for si in s:
  c+=si.count('.')
print(c-b-1)

Submission status: Accepted

Solution code:
from collections import deque
H, W=map(int, input().split(" "))
field=[list(input()) for _ in range(H)]
dist=[[-1]*W for _ in range(H)]
que=deque([[0,0]])
dist[0][0]=0
dx=[1,0,-1,0]
dy=[0,1,0,-1]
cnt=0
#BFS
while que:
    y, x=que.popleft()
    if [y, x]==[H-1, W-1]:
        break
    for i in range(4):
        nx = x + dx[i]
        ny = y + dy[i]
        if (0<=nx<W and 0<=ny<H and field[ny][nx]=="." and dist[ny][nx]==-1):
            dist[ny][nx]=dist[y][x]+1
            que.append([ny, nx])

if dist[H-1][W-1]!=-1:
    for j in range(H):
        for k in range(W):
            if field[j][k]=="#":
                cnt+=1
    print(H*W-dist[H-1][W-1]-cnt-2+1)
else:
    print("-1")

Submission status: Accepted

Solution code:
from collections import deque

def bfs():
  queue = deque([[0, 0]])
  visited[0][0] = 0
  while queue:
    y, x = queue.popleft()
    if [y, x] == [h-1, w-1]:
      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 not (0 <= new_y < h) or not (0 <= new_x < w):
        continue

      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])

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

maze=[]
w_space=0
for _ in range(h):
  t=input()
  maze.append(t)
  w_space += t.count(".")
visited = [[-1]*w for _ in range(h)]

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

Submission status: Accepted

Solution code:
#BFS
from collections import deque
def bfs(i):
    q=deque()
    q.append((0, 0))

    d = ((1, 0), (0, 1), (-1, 0), (0, -1))
    log = [[0] * w for i in range(h)]
    log[0][0] = 1

    while q:
        #qの先頭を取り出す
        x, y=q.popleft()
        for dx, dy in d:
            nx = x + dx
            ny = y + dy
            if not(0 <= nx < h and 0 <= ny <w):continue
            if s[nx][ny] == '#':continue
            if log[nx][ny] != 0:continue
            log[nx][ny] = log[x][y] + 1
            if (nx + 1, ny + 1) == (h, w):
                return h * w - i - log[nx][ny]

            q.append((nx, ny))

    return -1

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

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

Submission status: Accepted

Solution code:
from collections import deque, Counter

h, w = map(int, input().split())
s = []
c = Counter()
for i in range(h):
    s_ = input().rstrip()
    s.append(s_)
    c.update(list(s_))

searched = [[False] * w for i in range(h)]

d = deque([(0, 0, 1)])
clear_step = -1

while d:
    i, j, step = d.popleft()

    if searched[i][j]:
        continue
    else:
        searched[i][j] = True

    if i == h-1 and j == w-1:
        clear_step = step
        break

    if i > 0 and s[i-1][j] == '.':
        d.append((i-1, j, step+1))
    if i < h-1 and s[i+1][j] == '.':
        d.append((i+1, j, step+1))
    if j > 0 and s[i][j-1] == '.':
        d.append((i, j-1, step+1))
    if j < w-1 and s[i][j+1] == '.':
        d.append((i, j+1, step+1))

if clear_step >= 0:
    print(c['.']-clear_step)
else:
    print(-1)

Submission status: Accepted

Solution code:
"""
最高得点＝初期状態の白タイルの数 - ゴールまでの最短経路上の白タイルの数

まず、白タイルの数を全部数える。
次に、BFSで探索を行い、最短経路を求める。
"""
from collections import deque
H,W = map(int,input().split())
maze = [list(input()) for _ in range(H)]
default = 0
for i in range(H):
    for j in range(W):
        if maze[i][j] == ".":
            default += 1

que = deque()
que.append((0,0,1))
patterns = [(1,0),(-1,0),(0,1),(0,-1)]
count = 0
while que:
    y,x,cost = que.popleft()
    if y == H-1 and x == W-1:
        count = cost
        break
    for a,b in patterns:
        if 0<=y+a<H and 0<=x+b<W and maze[y+a][x+b]==".":
            maze[y+a][x+b] = "o"
            que.append((y+a,x+b,cost+1))


if count == 0:
    print(-1)
else:
    print(default-count)

Submission status: Accepted

Solution code:
from collections import deque 
H, W = map(int, input().split())
graph = [list(input()) for _ in range(H)]
dist = [[-1] * W for _ in range(H)]
q = deque([(0,0)])
dist[0][0] = 1
while q:
  x, y = q.popleft()
  if(x >= 1):
    if(dist[x-1][y] < 0 and graph[x-1][y] == '.'):
      dist[x-1][y] = dist[x][y] + 1
      q.append((x-1, y))
  if(x <= H-2):
    if(dist[x+1][y] < 0 and graph[x+1][y] == '.'):
      dist[x+1][y] = dist[x][y] + 1
      q.append((x+1, y))
  if(y >= 1):
    if(dist[x][y-1] < 0 and graph[x][y-1] == '.'):
      dist[x][y-1] = dist[x][y] + 1
      q.append((x, y-1))
  if(y <= W-2):
    if(dist[x][y+1] < 0 and graph[x][y+1] == '.'):
      dist[x][y+1] = dist[x][y] + 1
      q.append((x, y+1))
      
cnt = 0
if(dist[H-1][W-1] == -1):
  print(-1)
else:
  for i in range(H):
    for j in range(W):
      if(graph[i][j] == '#'):
        cnt += 1
  print(H*W-cnt-dist[H-1][W-1])

Submission status: Accepted

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

G[1][1] = 1
que = deque([[1,1]])
while que:
    y,x = que.popleft()
    d = G[y][x]
    for dy,dx in ((1,0),(-1,0),(0,1),(0,-1)):
        ny = y+dy
        nx = x+dx
        if G[ny][nx] == '.':
            G[ny][nx] = d+1
            que.append((ny,nx))
if G[h][w] == '.':
    print('-1')
else:
    ans = white - G[h][w]
    print(ans)

Submission status: Accepted

Solution code:
from collections import deque
H,W=map(int,input().split())
s=[['#']*(W+2)for _ in range(H+2)]
count=0
for i in range(1,H+1):
  S=list(input())
  s[i]=['#']+S+['#']
  count+=S.count('.')
move=[(1,0),(-1,0),(0,1),(0,-1)]
que=deque([(1,1)])
s[1][1]=1
while que:
  a,b=que.popleft()
  if (a,b)==(H,W):
    break
  for my,mx in move:
    ny=my+a
    nx=mx+b
    if s[ny][nx]=='#':
      continue
    elif s[ny][nx]=='.':
      que.append((ny,nx))
      s[ny][nx]=s[a][b]+1
ans=-1
if s[H][W]!='.':
  ans=count-s[H][W]
print(ans)

Submission status: Accepted

Solution code:
from collections import deque
def gridbfs(grid,sy,sx):
    INF = 10**18

    gridy = len(grid)
    gridx = len(grid[0])

    dist = [[INF]*gridx for _ in range(gridy)]
    dist[sy][sx] = 0
    q = deque([(sy,sx)])

    while q:
        y,x = q.popleft()
        for dy,dx in [(-1,0),(1,0),(0,-1),(0,1)]:
            ny,nx = y+dy, x+dx
            if not (0 <= ny < gridy and 0 <= nx < gridx):
                continue
            if grid[ny][nx] == '#':
                continue
            if dist[ny][nx] != INF:
                continue
            dist[ny][nx] = dist[y][x] + 1
            q.append((ny,nx))

    return dist

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

Grid = [input() for _ in range(H)]

cnt = 0
for i in range(H):
    cnt += Grid[i].count('.')

d = gridbfs(Grid,0,0)

print(max(-1, cnt - d[H-1][W-1] -1))