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:
H, W = map(int, input().split())
M = [list(input()) for _  in range(H)]
visited = [[0]*W for _ in range(H)]

from collections import deque
q = deque([[0, 0, 1]])
goal = False
while q:
    i, j, count = q.popleft()
    if i == H-1 and j == W-1:
        goal = True
        break
    
    for movei, movej in ((0, 1), (0, -1), (1, 0), (-1, 0)):
        ni = i + movei; nj = j + movej
        if ni < 0 or H <= ni or nj < 0 or W <= nj:
            continue
        if M[ni][nj] == '#':
            continue
        if visited[ni][nj] != 0:
            continue
        visited[ni][nj] = 1
        q.append([ni, nj, count+1])

if goal:
    numdots = 0
    for i in range(H):
        numdots += M[i].count('.')
    print(numdots - count)
else:
    print(-1)

Submission status: Accepted

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

from collections import deque
q = deque([[0, 0]])
while q:
    i, j = q.popleft()
    if i == H-1 and j == W-1:
        break
    
    for movei, movej in ((0, 1), (0, -1), (1, 0), (-1, 0)):
        ni = i + movei; nj = j + movej
        if ni < 0 or H <= ni or nj < 0 or W <= nj:
            continue
        if M[ni][nj] == '#':
            continue
        if visited[ni][nj] != 0:
            continue
        visited[ni][nj] = (i, j)
        q.append([ni, nj])
else:
    print(-1)
    exit()

si, sj = H-1, W-1
M[si][sj] = '*'
while si != 0 or sj != 0:
    si, sj = visited[si][sj]
    M[si][sj] = '*'
c = 0 
for i in range(H):
    c += M[i].count('.')
print(c)

Submission status: Accepted

Solution code:
from collections import deque
h, w = map(int, input().split())
maze = [[] for _ in range(h)]
seen = [[0 for i in range(w)] for _ in range(h)]
dx = deque()
dy = deque()
for i in range(h):
    l = input()
    for k in range(w):
        maze[i].append(l[k])
dx.append(0)
dy.append(0)
seen[0][0] = 1
while len(dx) != 0 and len(dy) != 0:
    nx = dx.popleft()
    ny = dy.popleft()
    if nx == w-1 and ny == h-1:
        black_all = 0
        for i in range(h):
            for k in range(w):
                if maze[i][k] == '#':
                    black_all += 1
        all_masu = h*w
        print(all_masu-black_all-seen[ny][nx])
        exit()
    for next_m in [(1,0), (-1, 0), (0, 1), (0, -1)]:
        next_x = nx + next_m[0]
        next_y = ny + next_m[1]
        if 0 <= next_x < w and 0 <= next_y < h:
            if maze[next_y][next_x] == '.' and seen[next_y][next_x] == 0:
                dx.append(next_x)
                dy.append(next_y)
                seen[next_y][next_x] = seen[ny][nx] + 1
print(-1)

Submission status: Accepted

Solution code:
from sys import stdin
from collections import deque
from collections import Counter


def grid2adj(arr_grid,direction=4):
    def cand(i,j,direction):
        if direction == 4:
            return [[i-1,j],[i+1,j],[i,j-1],[i,j+1]]
        elif direction == 8:
            return [[i-1,j],[i+1,j],[i,j-1],[i,j+1],
                    [i-1,j-1],[i-1,j+1],[i+1,j-1],[i+1,j+1]]
        else:
            print('Error')
    
    M,N = len(arr_grid),len(arr_grid[0])
    arr_con = [[] for i in range(M*N)]
    for i in range(M):
        for j in range(N):
            v = i*N+j
            for _cand in cand(i,j,direction):
                if 0<=_cand[0]<M and 0<=_cand[1]<N:
                    next_v = _cand[0]*N+_cand[1]
                    arr_con[v].append(next_v)
    arr_val = sum(arr_grid,[])

    return arr_con, arr_val


class BFS():
    def __init__(self, con, val=None):
        # 隣接リスト表現
        self.con = con
        self.val = val
        self.N = len(self.con)
        # 始点からの距離
        self.dist = [-1]*self.N
        self.que = deque()

    def bfs(self, start_v):
        # 初期条件(0-indexed)
        self.dist[start_v] = 0
        self.que.append(start_v)

        while len(self.que)>0:
            v = self.que.popleft()
            for next_v in self.con[v]:
                if self.dist[next_v] != -1:
                    continue
                if self.val[next_v] == '#':
                    continue
                self.dist[next_v] = self.dist[v] + 1
                self.que.append(next_v)


if __name__ == "__main__":
    _in = [_.rstrip() for _ in stdin.readlines()]
    H, W = list(map(int,_in[0].split(' ')))  # type:list(int)
    graph = []
    for i in range(H):
        _ = list(_in[i+1])  # type:list(str)
        graph.append(_)
    # vvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvv
    g_con, g_val = grid2adj(graph)
    bfs = BFS(g_con,g_val)

    cnt = 0
    bfs.bfs(0)
    if bfs.dist[-1] == -1:
        cnt = -1
    else:
        cnt = H*W-bfs.val.count('#')-(bfs.dist[-1]+1)
    # ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
    print(cnt)

Submission status: Accepted

Solution code:
import sys
from collections import deque
    
def main(*args, **kwargs):
    # Initialize data
    H, W = map(int, sys.stdin.readline().split())
    total_cells = H * W
    existing_black_cells = 0
 
    grid = []
    for i in range(H):
        line = sys.stdin.readline()
        existing_black_cells += line.count('#')
        grid.append(line)
 
    # Initialize Search
    queue = deque()
    queue.append((0, 0))  # start point
    visited = set()
    visited.add((0, 0))
    movement = 0
 
    while len(queue) > 0:
        movement += 1
        for i in range(len(queue)):  # Process same level
            coodinate = queue.popleft()
            y = coodinate[0]
            x = coodinate[1]
 
            # Terminate condition
            if y == H - 1 and x == W - 1:
                print(total_cells - movement - existing_black_cells)
                return
 
            for dx, dy in [(1, 0), (0, 1), (-1, 0), (0, -1)]:
                X = x + dx
                Y = y + dy
                adjacent = (Y, X)
                if 0 <= X < W and 0 <= Y < H and grid[Y][X] == '.' and adjacent not in visited:
                    queue.append(adjacent)
                    visited.add(adjacent)
    print(-1)
    return
main()

Submission status: Accepted

Solution code:
from collections import deque
 
 
def dfs(field):
    q = deque([(0, 0, 0)])
    visited = [[False] * w for _ in range(h)]
    while q:
        i, j, d = q.popleft()
        if i == h - 1 and j == w - 1:
            return d
        if visited[i][j]:
            continue
        visited[i][j] = True
        if i > 0 and field[i - 1][j] == '.':
            q.append((i - 1, j, d + 1))
        if i < h - 1 and field[i + 1][j] == '.':
            q.append((i + 1, j, d + 1))
        if j > 0 and field[i][j - 1] == '.':
            q.append((i, j - 1, d + 1))
        if j < w - 1 and field[i][j + 1] == '.':
            q.append((i, j + 1, d + 1))
    else:
        return -1
 
 
h, w = map(int, input().split())
field = [input() for _ in range(h)]
dot_cnt = sum(r.count('.') for r in field)
d = dfs(field)
if d == -1:
    print(-1)
else:
    print(dot_cnt - (d+1))

Submission status: Accepted

Solution code:
cin = open(0).read().strip().split('\n')
h,w = map(int, cin[0].split(' '))
s = [list(a) for a in cin[1:]]

from collections import deque
q = deque()

dist = [[-1 for _ in range(w)] for _ in range(h)]
dist[0][0]=0

q.append((0,0))
while q:
    ph, pw = q.popleft()
    for dyi, dxi in zip([0,-1,0,1],[1,0,-1,0]):
        if 0<=ph+dyi<h and 0<=pw+dxi<w:
            if dist[ph+dyi][pw+dxi] != -1: continue
            if s[ph+dyi][pw+dxi] == '#': continue
            q.append((ph+dyi, pw+dxi))
            dist[ph+dyi][pw+dxi] = dist[ph][pw]+1

last = dist[h-1][w-1]
if last == -1:
    print(-1)
else:
    print(sum(s, []).count('.')-last-1)

Submission status: Accepted

Solution code:
import math
import bisect
from queue import Queue
from collections import deque

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

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

q = deque()
q.append(0)
q.append(0)
table[0][0] = 1
flag = -1
while(len(q)):
    nowx = q.popleft()
    nowy = q.popleft()

    if((nowx == h-1) and (nowy == w-1)):
        flag = int(table[nowx][nowy])

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

    for i in range(4):
        tempx = nowx + dx[i]
        tempy = nowy + dy[i]
        if((0 <= tempx)and(tempx < h)and(0 <= tempy)and(tempy < w)):
            if(table[tempx][tempy] =="."):
                table[tempx][tempy] = table[nowx][nowy] + 1
                q.append(tempx)
                q.append(tempy)


if(flag == -1):
    print(flag)
else:
    print(count-flag)

Submission status: Accepted

Solution code:
import sys
 
h,w=[int(x) for x in input().rstrip().split()]
l=[]
black=0
for i in range(h):
  s=[x for x in input()]
  l.append(s)
  black+=sum(j.count("#") for j in s)
 
done=[[float('inf')]*w for i in range(h)]
def bfs():
  stack=[[0,0]]
  done[0][0]=0
  while(stack):
    x,y=stack.pop(0)
    move=[[x+1,y],[x-1,y],[x,y+1],[x,y-1]]
 
    for mx,my in move:
      if not(0<=my<=h-1) or not(0<=mx<=w-1) or l[my][mx]=="#" or done[my][mx]!=float('inf'):
        continue

      done[my][mx]=done[y][x]+1
      stack.append([mx,my])
      
      if my==h-1 and mx==w-1:
        print(h*w-done[my][mx]-black-1)
        sys.exit()
  print(-1)
 
if __name__=="__main__":
  bfs()

Submission status: Accepted

Solution code:
from collections import deque

h,w=map(int,input().split())
l=[list(input()) for i in range(h)]
visited=[[float('inf')]*w for i in range(h)]
def bfs():
  que =deque()
  visited[0][0]=0
  que.append([0,0])
  while que:
    p=que.popleft()
    if p[1]==w-1 and p[0]==h-1:
      break
    for dx,dy in ([0,1],[0,-1],[1,0],[-1,0]):
      ny=p[1]+dy
      nx=p[0]+dx
      if nx>=0 and ny>=0 and nx<h and ny<w and visited[nx][ny]==float('inf') and l[nx][ny]!='#':
        visited[nx][ny]=visited[p[0]][p[1]]+1
        que.append([nx,ny])

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


suml=0
for i in range(h):
  suml+=l[i].count('#')
  
if bfs()==float('inf'):
  print(-1)
else:
  print(h*w-suml-bfs()-1)

Submission status: Accepted

Solution code:
# import numpy as np
import sys
from collections import defaultdict
import math
import itertools
import bisect
from copy import deepcopy
from collections import deque
read = sys.stdin.buffer.read
readline = sys.stdin.readline
readlines = sys.stdin.buffer.readlines
sys.setrecursionlimit(10000)

H , W = map(int,readline().split())
board = ["#" for _ in range(W+2)]
for  _ in range(H):
    board += ["#"] + list(readline().rstrip()) + ["#"]
board += ["0" for _ in range(W+2)]
white = 0
for tile in board:
    if tile == ".":
        white += 1
H , W = H+2 , W+2
visit = [-1 for _ in range(W*H)]
D = [ [1,0] , [0,1] , [-1,0] , [0,-1] ]

def bfs():
    root = W + 1
    q = deque([root])
    visit[root] = 1
    while q :
        index = q.popleft()

        if index == (H-2)*W+W-2:
            break

        x =  index // W
        y =  index % W
        for d in D :
            dx , dy = d
            X , Y = x+dx , y+dy
            if 1<=X and X<= H-1 and 1<=Y and Y <= W-1:
                dot = X*W+Y
                if visit[dot] == -1 and board[dot] == ".":
                    visit[dot] = visit[index] + 1
                    q.append(dot)

    length = visit[(H-2)*W+W-2]
    if  length == -1:
        return -1
    else:
        return white - length


def solve():
    print(bfs())

if __name__ == "__main__":
    solve()
    # print(board)

Submission status: Accepted

Solution code:
# coding: utf-8
# hello worldと表示する
#dpでできないかな？
import sys
input = sys.stdin.readline
sys.setrecursionlimit(10**7)
from collections import Counter, deque
from collections import defaultdict
from itertools import combinations, permutations, accumulate, groupby, product
from bisect import bisect_left,bisect_right
from heapq import heapify, heappop, heappush
from math import floor, ceil,pi
from operator import itemgetter
def I(): return int(input())
def MI(): return map(int, input().split())
def LI(): return list(map(int, input().split()))
def LI2(): return [int(input()) for i in range(n)]
def MXI(): return [[LI()]for i in range(n)]
def SI(): return input().rstrip()
def printns(x): print('\n'.join(x))
def printni(x): print('\n'.join(list(map(str,x))))
inf = 10**17
mod = 10**9 + 7

h,w=MI()
lis=[[0]*(w+2) for i in range(h+2)]
for i in range(h):
    s=SI()
    for j in range(w):
        if s[j]==".":
            lis[i+1][j+1]=1
#print(lis)
step=[[1,0],[0,-1],[-1,0],[0,1]]
counter=[[-1]*(w+2) for i in range(h+2)]
counter[1][1]=0
q=deque([[1,1]])
while q:
    x,y=q.popleft()
    #print(x,y)
    for i,j in step:
        if counter[x+i][y+j]<0 and lis[x+i][y+j]==1:
            q.append([x+i,y+j])
            counter[x+i][y+j]=counter[x][y]+1
if counter[h][w]<0:
    print(-1)
    sys.exit()
white=0
for i in range(h+2):
    white+=sum(lis[i])
#print(white)
if lis[1][1]==1:
    white-=1
ans=white-counter[h][w]
print(ans)
#print(counter[h][w])

Submission status: Accepted

Solution code:
from collections import deque
q = deque()
h,w=map(int,input().split())
sx,sy=1,1#スタート位置
ex,ey=h,w#ゴール位置
q.append([sx-1,sy-1,0])
global finished 
finished = set()
c=[]
for i in range(h):
    c.append(list(map(str,input())))

def check(x,y):
    if 0<=x and x<h:
        if 0<=y and y<w:
            return True
    return False

count=0
def search():
    while (q):
        x,y,count=q.popleft()
        
        if check(x,y)==False or (x,y) in finished or c[x][y]=='#':
            continue
        else:
            q.append([x,y-1,count+1])
            q.append([x,y+1,count+1])
            q.append([x+1,y,count+1])
            q.append([x-1,y,count+1])
            finished.add((x,y))
            c[x][y]=count
            if x==ex-1 and y==ey-1:
                return c[x][y]+1 #通った道の合計を返す
    return -1
black_count=0
for i in range(h):
    black_count+=c[i].count("#")
path=search()#通る道
if path==-1:
    print(path)
else:
    print(h*w-black_count-path)#全体からもともと黒の#の数と通った白い道を削除

Submission status: Accepted

Solution code:
from collections import deque

h,w=map(int,input().split(' '))
maze=[0]*h
kuro=0
for y in range(h):
    line=input()
    kuro+=line.count('#')
    maze[y]=line
count=[[-1]*w for _ in range(h)]
count[0][0]=1

q=deque([[0,0]])
def BFS():
    while q:
        y,x=q.popleft()
        if (y,x)==(h-1,w-1):
            return h*w-kuro-count[h-1][w-1]
        for dy,dx in [[0,1],[1,0],[-1,0],[0,-1]]:
            ny,nx=y+dy,x+dx
            if not (0<=ny<h and 0<=nx<w):
                continue
            if maze[ny][nx]=='.' and count[ny][nx]==-1:
                q.append([ny,nx])
                count[ny][nx]=count[y][x]+1
    return -1

print(BFS())

Submission status: Accepted

Solution code:
H,W = map(int, input().split())
field = []
countd = 0
for _ in range(H):
    ls = []
    st = str(input())
    for ss in st:
        ls.append(ss)
        if ss =='.':
            countd += 1
    field.append(ls)
import heapq

def caldis(field):#ある点を黒にして計算できる距離の中で際異端のものを求める
    used = [[False]*50 for i in range(50)]
    dis = [[float('inf')]*51 for i in range(51)]
    dis[0][0] = 0
    que = []
    heapq.heappush(que,[0,0,0])
    while len(que)>0:
        pre = heapq.heappop(que)
        d = pre[0]
        px = pre[1]
        py = pre[2]
        if used[px][py] ==True:
            continue
        used[px][py] = True
        dis[px][py] = d
        for dx in [-1,1]:
            for dy in [-1,1]:
                if 0<=px+dx<=H-1:
                    if field[px+dx][py]=='.':
                        heapq.heappush(que,[d+1,px+dx,py])
                if 0<=py+dy<=W-1:
                    if field[px][py+dy]=='.':
                        heapq.heappush(que,[d+1,px,py+dy])
    res = dis[H-1][W-1]
    return res
an = caldis(field)
if an==float('inf'):
    print(-1)
else:
    print(countd-an-1)

Submission status: Accepted

Solution code:
from queue import Queue
import copy
import collections

R, C = map(int, input().split(' '))
M = [[s for s in input()] for _ in range(R)]
trial = 0


Sy = 1
Sx = 1
Gy = R
Gx = C

cnt  = 0
for i in range(R):
  cnt += M[i].count('#')

L = copy.deepcopy(M)

move = [(0, -1), (0, 1), (1, 0), (-1, 0)]
q = Queue()
ans = 0

q.put([(Sy, Sx)])
L[Sy-1][Sx-1] = '#'

while not q.empty():
  pos = q.get()
  valid_pos = []
  for p in pos:
      for m in move:
          y, x = p[0]+m[0], p[1]+m[1]
          if y == Gy and x == Gx:
            ans += 1
            print(R*C-ans-1-cnt)
            exit()            
          if 1<= y  <= R and 1<= x <= C:
            if L[y-1][x-1] == '.':
              L[y-1][x-1] = '#'
              valid_pos.append((y, x))
  if len(valid_pos) != 0:
      q.put(valid_pos)
  ans += 1
print(-1)

Submission status: Accepted

Solution code:
from collections import deque
if __name__ == "__main__":
    h, w = map(int, input().split())
    grid = []
    for _ in range(h):
        grid.append(input())
    
    white = 0
    for i in range(h):
        for j in range(w):
            if grid[i][j] == ".":
                white += 1
    
    qu = deque()
    qu.append(((0, 0), 0))
    
    visited = [[False] * w for _ in range(h)]
    visited[0][0] = True
    ans = -1

    while qu:
        now, dis = qu.pop()
        if now[0] == h-1 and now[1] == w-1:
            ans = white - dis - 1
            break

        if now[0] + 1 < h and grid[now[0] + 1][now[1]] != "#" and not visited[now[0] + 1][now[1]]:
            visited[now[0] + 1][now[1]] = True
            qu.appendleft(((now[0] + 1, now[1]), dis + 1))
        
        if now[0] - 1 >= 0 and grid[now[0] - 1][now[1]] != "#" and not visited[now[0] - 1][now[1]]:
            visited[now[0] - 1][now[1]] = True
            qu.appendleft(((now[0] - 1, now[1]), dis + 1))

        if now[1] + 1 < w and grid[now[0]][now[1] + 1] != "#" and not visited[now[0]][now[1] + 1]:
            visited[now[0]][now[1] + 1] = True
            qu.appendleft(((now[0], now[1] + 1), dis + 1))
        
        if now[1] - 1 >= 0 and grid[now[0]][now[1] - 1] != "#" and not visited[now[0]][now[1] - 1]:
            visited[now[0]][now[1] - 1] = True
            qu.appendleft(((now[0], now[1] - 1), dis + 1))
    print(ans)

Submission status: Accepted

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

def bfs(i0, j0):
    INF = 1000
    search = deque([(i0, j0)])
    d = [[INF] * w for i in range(h)]
    d[i0][j0] = 1
    while search:
        i, j = search.popleft()
        if (i, j) == (h - 1, w - 1):
            break
        for di, dj in ((1, 0), (0, 1), (-1, 0), (0, -1)):
            ni, nj = i + di, j + dj
            if 0 <= ni < h and 0 <= nj < w and s[ni][nj] == '.' and d[ni][nj] == INF:
                search.append((ni, nj))
                d[ni][nj] = d[i][j] + 1
    return d[i][j] if d[h - 1][w - 1] != INF else 0 
solvable = bfs(0, 0)
print(h*w - cnt_b - solvable if solvable else -1)

Submission status: Accepted

Solution code:
from collections import deque

def main():
    N,M = map(int,input().split())
    s = [list(str(input())) for _ in range(N)]
    count = 0
    for i in range(N):
        for j in range(M):
            if s[i][j] == ".":
                count += 1
    
    q = deque([(0,0)])
    dx,dy = [1,0,-1,0],[0,1,0,-1]
    dist = [[10**10 for _ in range(M)] for _ in range(N)]
    dist[0][0] = 1
    
    while q:
        x,y = q.pop()
        for _x,_y in zip(dx,dy):
            nx,ny = x+_x,y+_y
            if (0<=nx<N and 0<=ny<M and s[nx][ny] == "."):
                if dist[nx][ny] > dist[x][y]+1:
                    dist[nx][ny] = dist[x][y]+1
                    q.append((nx,ny))
    
    if dist[-1][-1] == 10**10:
        print(-1)
    else:
        print(count-dist[-1][-1])

if __name__ == "__main__":
    main()

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)]
blackcount=0
for i,j in itertools.product(range(h),range(w)):
    if s[i][j]=="#":
        blackcount+=1
dhdw=[[-1,0],[1,0],[0,-1],[0,1]]
mindist=[[-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])
    mindist[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 mindist[qh][qw]+1
            seen[nh][nw]=1
            queue.append([nh,nw])
            mindist[nh][nw]=mindist[qh][qw]+1
    else:
        return -1
mindist=bfs()
print(h*w-blackcount-mindist if mindist!=-1 else -1)

Submission status: Accepted

Solution code:
from collections import deque
import sys
input = sys.stdin.readline
H,W = map(int,input().split())
lst=[[] for f in range(H)]
for i in range(H):
 lst[i] = [d for d in input()]
stack = deque([[0,0]])
muki=[[1,0],[-1,0],[0,1],[0,-1]]
check=[[0 for e in range(W)] for f in range(H)] #チェック済みリスト
check[0][0]=1
t=0
while stack != deque([]) :
 a=stack.popleft()
 for i in muki:
  b0=a[0]+i[0]
  b1=a[1]+i[1]
  if b0<=H-1 and b0>=0 and b1<=W-1 and  b1>=0:
   if check[b0][b1]==0 and lst[b0][b1]==".":
    check[b0][b1]=check[a[0]][a[1]]+1
    stack.append([b0,b1])
if check[H-1][W-1]==0:
 print(-1)
else:
 ct=0
 for i in range(H):
  for j in range(W):
   if lst[i][j]==".":
    ct+=1
 print(ct-check[H-1][W-1])

Submission status: Accepted

Solution code:
from collections import deque
H, W = map(int, input().split())
s = [list(input()) for i in range(H)]
Q = deque()
Q.append([0, 0])
dist = [[-1] * W for i in range(H)]
dist[0][0] = 0
c = 0
for i in range(H):
    for j in range(W):
        if s[i][j] == '.':
            c += 1

yudrl = [0, 1, 0, -1]
xudrl = [1, 0, -1, 0]

while (len(Q) > 0):
    q = Q.popleft()

    for i in range(4):
        y = q[0] + yudrl[i]
        x = q[1] + xudrl[i]

        if y < 0 or y > H - 1 or x < 0 or x > W - 1:
            continue  
        if dist[y][x] != -1 or s[y][x] == '#':
            continue
        dist[y][x] = dist[q[0]][q[1]] + 1
        Q.append([y, x])
if dist[H - 1][W - 1] == -1:
    print('-1')
else:
    print(c - dist[H - 1][W - 1] - 1)

Submission status: Accepted

Solution code:
from collections import deque
H, W = map(int, input().split())
s = []
for _ in range(H):
    s.append(input())
queue = deque([[0,0]])
dist = [[-1 for j in range(W)] for i in range(H)]
dist[0][0] = 0
dh = [0, 0, 1, -1]
dw = [1, -1, 0, 0]
while len(queue) != 0:
    now = queue.popleft()
    h = now[0]
    w = now[1]
    for i in range(4):
        nh = h + dh[i]
        nw = w + dw[i]
        if nh < 0 or nw < 0 or nh >= H or nw >= W:
            continue
        elif dist[nh][nw] == -1 and s[nh][nw] == ".":
            queue.append([nh, nw])
            dist[nh][nw] = dist[h][w] + 1
ans = 0
if dist[H-1][W-1] == -1:
    print(-1)
    exit()

for i in range(H):
    for j in range(W):
        if s[i][j] == ".":
            ans += 1
ans = ans - dist[H-1][W-1] -1
print(ans)

Submission status: Accepted

Solution code:
H,W=map(int,input().split())
L=[]
for i in range(H):
    l=list(input())
    L.append(l)
T=[[0 for i in range(W)] for l in range(H)]
T[0][0]=1
S=[[0,0]]
SS=[[0,0]]
v=0
count=0
while 1:
    count+=1
    S=SS
    SS=[]
    while 1:
        x=S[0][1]
        y=S[0][0]
        if 0<=y and y<H-1:
            if L[y+1][x]=="." and T[y+1][x]==0:
                s=[y+1,x]
                T[y+1][x]=1
                SS.append(s)
                if y+1==H-1 and x==W-1:
                    v=1
                    break
        if 0<y and y<=H-1:
            if L[y-1][x]=="." and T[y-1][x]==0:
                s=[y-1,x]
                T[y-1][x]=1
                SS.append(s)
                if y-1==H-1 and x==W-1:
                    v=1
                    break
        if 0<=x and x<W-1:
            if L[y][x+1]=='.' and T[y][x+1]==0:
                s=[y,x+1]
                T[y][x+1]=1
                SS.append(s)
                if y==H-1 and x+1==W-1:
                    v=1
                    break
        if 0<x and x<=W-1:
            if L[y][x-1]=='.' and T[y][x-1]==0:
                s=[y,x-1]
                T[y][x-1]=1
                SS.append(s)
                if y==H-1 and x-1==W-1:
                    v=1
                    break
        S.pop(0)
        if len(S)==0:
            break
    if v==1:
        break
    if len(SS)==0:
        v=0
        break
x=0
if v==0:
    print(-1)
else:
    for i in range(H):
        for l in range(W):
            if L[i][l]=='#':
                x+=1
    print(W*H-x-count-1)

Submission status: Accepted

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

dist = [[-1]*(w+2) for i in range(h+2)]

dist[1][1] = 1
que = deque([(1,1)])

while que:
    v = que.popleft()
    compass = [(v[0],v[1]-1),(v[0]+1,v[1]),(v[0],v[1]+1),(v[0]-1,v[1])]
    for i in compass:
        if G[i[0]][i[1]] == '.' and dist[i[0]][i[1]] == -1:
            dist[i[0]][i[1]] = dist[v[0]][v[1]] + 1
            que.append(i)

if dist[h][w] == -1:
    print(-1)
    exit()

cnt = 0
for i in range(1,h+1):
    for j in range(1,w+1):
        if G[i][j] == '#':
            cnt += 1

print(h*w-cnt-dist[h][w])

Submission status: Accepted

Solution code:
#!/usr/bin python3
# -*- coding: utf-8 -*-

from collections import deque

INF = -1
H, W = map(int,input().split())
stpt = [1,1]
stpt[0]-=1
stpt[1]-=1
glpt = [H,W]
glpt[0]-=1
glpt[1]-=1
Gmap = [list(input()) for _ in range(H)]
Dist = [[INF]*W for _ in range(H)]
direc = [[1,0], [-1,0], [0,1], [0,-1]]

def dfs(start):
    Dist[start[0]][start[1]] = 1
    q = deque([])
    q.append(start)
    r = 0
    while len(q)!=0:
        #スタック取り出し(先頭)幅優先
        h,w = q.popleft()
        for d in direc:
            hs, ws = h + d[0], w + d[1]
            if not (0<=hs<H and 0<=ws<W):
                continue
            if Gmap[hs][ws]=='.' and Dist[hs][ws]==INF:
                q.append([hs,ws])
                Dist[hs][ws] = Dist[h][w] + 1

def main():
    dfs(stpt)
    white = Dist[glpt[0]][glpt[1]]
    if white == INF:
        print(-1)
    else:
        black = sum([Gmap[h].count('#') for h in range(H)])
        print(H*W-white-black)

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
from collections import deque

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

start_black_cnt = 0
for i in s:
    for j in i:
        if j == '#':
            start_black_cnt += 1

que = deque([[0, 0]])
y, x = 0, 0
s[0][0] = 1
flg = True
while not (y == h-1 and x == w-1):
    if len(que) == 0:
        flg = False
        break

    now = que.popleft()
    y, x = now[0], now[1]
    # UP
    if y != 0 and s[y-1][x] == '.':
        que.append([y-1, x])
        s[y-1][x] = s[y][x] + 1
    # DOWN
    if y != h-1 and s[y+1][x] == '.':
        que.append([y+1, x])
        s[y+1][x] = s[y][x] + 1
    # LEFT
    if x != 0 and s[y][x-1] == '.':
        que.append([y, x-1])
        s[y][x-1] = s[y][x] + 1
    # RIGHT
    if x != w-1 and s[y][x+1] == '.':
        que.append([y, x+1])
        s[y][x+1] = s[y][x] + 1

if flg:
    print(h*w - start_black_cnt - int(s[h-1][w-1]))
else:
    print(-1)

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline
from collections import Counter
from collections import deque

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

bc = 0
for h in range(H):
  n = Counter(s[h])
  bc += n['#']


def dfs():
  que = deque()
  que.append((0,0))
  di = [1, 0, -1, 0]
  dj = [0, 1, 0, -1]
  d = [[float('inf')]*W for h in range(H)]
  d[0][0] = 0
  while que:
    point = que.popleft()
    if point[0] == H-1 and point[1] == W-1:
      break
    for i in range(4):
      ni = point[0] + di[i]
      nj = point[1] + dj[i]
      if 0 <= ni < H and 0 <= nj < W and d[ni][nj] == float('inf') and s[ni][nj] != '#':
        que.append((ni, nj))
        d[ni][nj] = d[point[0]][point[1]] + 1
  return d[H-1][W-1]

    
score = H*W - bc - dfs() -1 
if dfs() == float('inf'):
  score = -1
print(score)

Submission status: Accepted

Solution code:
from collections import deque

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

s = []
cnt = 0
for _ in range(h):
    tmp = list(input())
    cnt += tmp.count("#")
    s.append(tmp)

pos = [0, 0]
ans = 1
direction = [[0, 1], [0, -1], [1, 0], [-1, 0]]
queue = deque()
queue.append(pos)
queue.append(ans)
check = [[False for _ in range(w)] for _ in range(h)]
check[0][0] = True
while queue:
    pos = queue.popleft()
    ans = queue.popleft()
    ans += 1
    for dy, dx in direction:
        y = pos[0] + dy
        x = pos[1] + dx
        if x == -1 or x == w or y == -1 or y == h:
            continue
        if check[y][x]:
            continue
        if s[y][x] == "#":
            check[y][x] = True
            continue
        if y == h - 1 and x == w - 1:
            print(h * w - cnt - ans)
            exit()
        check[y][x] = True
        queue.append([y, x])
        queue.append(ans)
    
else:
    print(-1)
    exit()