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:
#!/usr/bin/env python3
#ABC88 D

import sys
import math
import bisect
sys.setrecursionlimit(1000000000)
from heapq import heappush, heappop,heappushpop
from collections import defaultdict
from itertools import accumulate
from collections import Counter
from collections import deque
from operator import itemgetter
from itertools import permutations
mod = 10**9 + 7
inf = float('inf')
def I(): return int(sys.stdin.readline())
def LI(): return list(map(int,sys.stdin.readline().split()))

h,w = LI()
dx = [1,0,-1,0]
dy = [0,1,0,-1]
maze = [list(input()) for _ in range(h)]
d = [[inf]*w for _ in range(h)]
d[0][0] = 1
que = deque()
que.append((0,0))
while que:
    x,y = que.popleft()
    for i in range(4):
        nx,ny = x + dx[i], y + dy[i]
        if 0 <= nx < w and 0 <= ny < h:
            if maze[ny][nx] != '#' and d[ny][nx] == inf:
                d[ny][nx] = d[y][x] + 1
                que.append((nx,ny))

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

Submission status: Accepted

Solution code:
from collections import deque
import copy

H, W = map(int, input().split())
s=(0,0)
g=(H-1,W-1)
maze = [list(input()) for line in range(H)]
copied_maze = copy.deepcopy(maze)

def search(x, y):
  dq = deque()
  dq.append([x, y])
  copied_maze[x][y] = 0
  while len(dq) > 0:
    x,y = dq.popleft()
    if x==g[0] and y==g[1]:
      break
    for dx, dy in [[1,0], [0,1], [-1,0], [0,-1]]:
      nx,ny=[x+dx,y+dy]
      if 0 <= nx < H and 0 <= ny < W and copied_maze[nx][ny] != '#' and type(copied_maze[nx][ny]) is str:
        dq.append([nx,ny])
        copied_maze[nx][ny] = copied_maze[x][y]+1
search(s[0],s[1])
x,y=g
cost = copied_maze[g[0]][g[1]]
if type(cost) is str:
  print(-1)
  exit()
path = {s, g}
for i in range(copied_maze[g[0]][g[1]]):
  for dx, dy in [[1,0], [0,1], [-1,0], [0,-1]]:
    nx,ny=[x+dx,y+dy]
    if 0 <= nx < H and 0 <= ny < W and copied_maze[nx][ny] == cost - 1:
      path.add((nx,ny))
      x,y=nx,ny
      cost -= 1
      break
count = 0
for i in range(H):
  for j in range(W):
    if maze[i][j] == '.' and (i, j) not in path:
      count += 1
print(count)

Submission status: Accepted

Solution code:
from collections import deque

R,C = list(map(int,input().split()))
Sx,Sy = 0,0
Gx,Gy = R-1,C-1
Mize = [input() for _ in range(R)]
dd = [[1, 0], [-1, 0], [0, 1], [0, -1]]

def bfs():
    d = [[float('inf')] * C for i in range(R)]
    q = deque([])
    d[Sx][Sy] = 0
    q.append((Sx,Sy))
    while(len(q) != 0):
        x,y = q.popleft()
        if x == Gx and y == Gy:
            break
        for dx,dy in dd:
            
            if -1<x+dx<R and -1<y+dy<C and Mize[x+dx][y+dy]=='.' and d[x+dx][y+dy] == float('inf'):
                q.append([x+dx,y+dy])
                d[x+dx][y+dy] = d[x][y] + 1
    return d[Gx][Gy]

white = sum([m.count('#') for m in Mize])
need = bfs()
if need == float('inf'):
    print(-1)
else:
    print(R*C-white-need-1)

Submission status: Accepted

Solution code:
from collections import deque


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

min_dist = -1
seen = set()
q = deque()
q.append((0, 0, 0))  # (i, j, dist)
while len(q) > 0:
    i, j, dist = q.popleft()
    if i == H - 1 and j == W - 1:
        min_dist = dist
        break
    if i > 0 and S[i - 1][j] == '.' and (i - 1, j) not in seen:
        seen.add((i - 1, j))
        q.append((i - 1, j, dist + 1))
    if j > 0 and S[i][j - 1] == '.' and (i, j - 1) not in seen:
        seen.add((i, j - 1))
        q.append((i, j - 1, dist + 1))
    if i < H - 1 and S[i + 1][j] == '.' and (i + 1, j) not in seen:
        seen.add((i + 1, j))
        q.append((i + 1, j, dist + 1))
    if j < W - 1 and S[i][j + 1] == '.' and (i, j + 1) not in seen:
        seen.add((i, j + 1))
        q.append((i, j + 1, dist + 1))

if min_dist == -1:
    print(-1)
else:
    b = 0
    for r in S:
        for c in r:
            if c == '#':
                b += 1
    print(H * W - min_dist - b - 1)

Submission status: Accepted

Solution code:
from collections import deque


def bfs(sx, sy, gx, gy):
    q = deque([(sx, sy)])
    cost[sx][sy] = 1
    while q:
        x, y = q.popleft()
        for dx, dy in nb:
            nx = x + dx
            ny = y + dy
            if 0 <= nx and nx < h and 0 <= ny and ny < w and grid[nx][ny] == "." and cost[nx][ny] == float("inf"):
                q.append((nx, ny))
                cost[nx][ny] = cost[x][y] + 1
                if nx == gx and ny == gy:
                    return cost[nx][ny]
    return -1


h, w = map(int, input().split())
grid = [list(input()) for _ in range(h)]
cost = [[float("inf")] * w for _ in range(h)]
nb = [(-1, 0), (0, -1), (1, 0), (0, 1)]
black_cnt = 0
ans = 0

for i in range(h):
    black_cnt += str(grid[i]).count("#")

can_reach = bfs(0, 0, h - 1, w - 1)
if can_reach > 0:
    print(h * w - can_reach - black_cnt)
else:
    print(can_reach)

Submission status: Accepted

Solution code:
H, W = map(int, input().split())
state = [[0 if s == '.' else 1 for s in list(input())] for _ in range(H)]

checked = [[False for _ in range(W)] for _ in range(H)]
qs = [(0, 0)]
checked[0][0] = True
goal = False
d = 0
while qs:
    qqs = []
    for qx, qy in qs:
        nexts = [(qx, qy+1), (qx, qy-1), (qx+1, qy), (qx-1, qy)]
        for nx, ny in nexts:
            if 0 <= nx <= W-1 and 0 <= ny <= H-1:
                if checked[ny][nx] or state[ny][nx] == 1:
                    continue
                qqs.append((nx, ny))
                checked[ny][nx] = True
            if nx == W-1 and ny == H-1:
                goal = True
                break
    d += 1
    if goal:
        break
    qs = qqs

black = 0
for h in range(H):
    for w in range(W):
        if state[h][w] == 1:
            black += 1

if goal:
    ans = H*W - black - d - 1
else:
    ans = -1

print(ans)

Submission status: Accepted

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

grid_array = [[0] * (W+2) for _ in range(H+2)]


white_count = 0
for i in range(1, H+1):
    grid = input()
    for j, x in enumerate(grid):
        if x == ".":
            grid_array[i][j+1] = 1
            white_count += 1

used_array = [[0] * (W+2) for _ in range(H+2)]

INF = 10 ** 5

distance_array = [[INF] * (W+2) for _ in range(H+2)]

tile_deque = deque()
tile_deque.append((1, 1))
used_array[1][1] = 1
distance_array[1][1] = 1
while len(tile_deque):
    i, j = tile_deque.popleft()
    # print(i,j)
    if used_array[i-1][j] == 0 and grid_array[i-1][j] == 1:
        used_array[i-1][j] = 1
        tile_deque.append((i-1, j))
        distance_array[i-1][j] = min(distance_array[i-1]
                                     [j], distance_array[i][j]+1)
    if used_array[i+1][j] == 0 and grid_array[i+1][j] == 1:
        used_array[i+1][j] = 1
        tile_deque.append((i+1, j))
        distance_array[i+1][j] = min(distance_array[i+1]
                                     [j], distance_array[i][j]+1)
    if used_array[i][j-1] == 0 and grid_array[i][j-1] == 1:
        used_array[i][j-1] = 1
        tile_deque.append((i, j-1))
        distance_array[i][j-1] = min(distance_array[i]
                                     [j-1], distance_array[i][j]+1)
    if used_array[i][j+1] == 0 and grid_array[i][j+1] == 1:
        used_array[i][j+1] = 1
        tile_deque.append((i, j+1))
        distance_array[i][j+1] = min(distance_array[i]
                                     [j+1], distance_array[i][j]+1)
# print(distance_array)
if distance_array[H][W] == INF:
    print(-1)
else:
    print(white_count-distance_array[H][W])

Submission status: Accepted

Solution code:
from collections import deque

h, w = map(int, input().split())
field = [input() for i in range(h)]
todo = deque([[0, 0]])
seen = [[-1]*w for _ in range(h)]
seen[0][0] = 0
dy = [1, -1, 0, 0]
dx = [0, 0, 1, -1]

count_black = 0
for line in field:
    count_black += line.count('#')

while todo:
    y, x = todo.popleft()

    for i in range(4):
        ny, nx = y + dy[i], x + dx[i]

        if ny < 0 or h <= ny or nx < 0 or w <= nx:
            continue
        elif field[ny][nx] == '#' or seen[ny][nx] >= 0:
            continue
        else:
            seen[ny][nx] = seen[y][x] + 1
            todo.append([ny, nx])

goal = seen[h-1][w-1]

if goal == -1:
    print(-1)
else:
    ans = h * w - count_black - goal - 1
    print(ans)

Submission status: Accepted

Solution code:
h , w = map(int, input().split())
field = [["#"] * (w+2)]
for i in range(h):
  temp = input()
  field.append("#" + temp + "#")
field.append(["#"] * (w+2))
now = [[1, 1]]
dots_count = 0
for i in field:
  dots_count += i.count(".")
move = [[0,1], [1, 0], [0,-1], [-1, 0]]
s_field = [[None for _ in range(w+2)] for _ in range(h+2)]
s_field[1][1] = 1
while now:
  x , y = now.pop(0)
  for v, u in move:
    if field[y+u][x+v] == "." and s_field[y+u][x+v] ==None:
      s_field[y+u][x+v] = s_field[y][x]+1
      if y+u == h and x+v == w:
        print(dots_count-s_field[y+u][x+v])
        break
      now.append([x+v, y+u])
  else:
    if not now:
      print(-1)
      break
    continue
  break

Submission status: Accepted

Solution code:

import sys
from collections import deque, defaultdict
import copy
import bisect
#input=sys.stdin.readline
#sys.setrecursionlimit(10 ** 9)
import math
import heapq

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

que = deque()
dist = [[-1 for i in range(W)] for j in range(H)]
que.append([0,0])
dist[0][0] = 0
while len(que) > 0:
	loc = que.popleft()
	if loc[0] < H - 1 and s[loc[0] + 1][loc[1]] == '.' and dist[loc[0] + 1][loc[1]] == -1:
		dist[loc[0] + 1][loc[1]] = dist[loc[0]][loc[1]] + 1
		que.append([loc[0] + 1, loc[1]])
	if loc[0] > 0 and s[loc[0] - 1][loc[1]] == '.' and dist[loc[0] - 1][loc[1]] == -1:
		dist[loc[0] - 1][loc[1]] = dist[loc[0]][loc[1]] + 1
		que.append([loc[0] - 1, loc[1]])
	if loc[1] < W - 1 and s[loc[0]][loc[1] + 1] == '.' and dist[loc[0]][loc[1] + 1] == -1:
		dist[loc[0]][loc[1] + 1] = dist[loc[0]][loc[1]] + 1
		que.append([loc[0], loc[1] + 1])
	if loc[1] > 0 and s[loc[0]][loc[1] - 1] == '.' and dist[loc[0]][loc[1] - 1] == -1:
		dist[loc[0]][loc[1] - 1] = dist[loc[0]][loc[1]] + 1
		que.append([loc[0], loc[1] - 1])


distance = dist[H - 1][W - 1]
if distance == -1:
	print(-1)
	exit()
num = H*W
for i in range(H):
	for j in range(W):
		if s[i][j] == '#':
			num -= 1
num -= 1 + distance
print(num)

Submission status: Accepted

Solution code:
import queue

H,W = map(int, input().split())
#world = [[c for c in input()] for _ in range(H)]
whiteCount = 0

world = []
for i in range(H):
    row = [c for c in input()]
    world.append(row) 
    whiteCount += len([c for c in row if c == '.'])

minRoot = whiteCount + 1

def bfs(x, y, depth):
    if x == W - 1 and y == H - 1:
        return min(minRoot, depth)

    depth = depth + 1
    appendPosition(x + 1, y, depth)
    appendPosition(x - 1, y, depth)
    appendPosition(x, y + 1, depth)
    appendPosition(x, y - 1, depth)

    return minRoot

def appendPosition(newX, newY, depth):
    if newX < 0 or newY < 0 or newX >= W or newY >= H or world[newY][newX] == '#':
        return

    newPosition = (newX,newY)
    if newPosition in visitedPosition:
        return

    q.put((newX, newY, depth))
    visitedPosition.add(newPosition)

q = queue.Queue()
q.put((0,0,1))
visitedPosition = set()
visitedPosition.add((0,0))

while q.empty() == False:
    position = q.get()
    minRoot = min(minRoot, bfs(*position))

if whiteCount < minRoot:
    print(-1)
else:
    print(whiteCount - minRoot)

Submission status: Accepted

Solution code:
from collections import deque
H,W = map(int,input().split())
s = list(input() for i in range(H))
board = [[1]*(W+2) for i in range(H+2)]
white = 0
for i in range(H):
    for j in range(W):
        if s[i][j] == '.':
            white += 1
            board[i+1][j+1] = 0
queue = deque([[1,1]])
v = [[1,0],[-1,0],[0,-1],[0,1]]
while queue != deque([]):
    x,y = queue.popleft()

    for a,b in v:
        if board[x+a][y+b] == 0:
            board[x+a][y+b] = board[x][y]+1
            queue.append([x+a,y+b])

if board[H][W] != 0:
    print(white-board[H][W]-1)
else:
    print(-1)

Submission status: Accepted

Solution code:
from collections import deque
H,W = list(map(int, input().split()))
s = [input().split() for i in range(H)]
for i in range(H):
    s[i] = list(s[i][0])
black = 0
for i in range(H):
    for j in range(W):
        if s[i][j] == "#":
            black += 1
queue = deque([])
dist = [[-1 for i in range(W)] for j in range(H)]
dist[0][0] = 0
queue.append([0,0])
place_w = [0, 1, 0, -1]
place_h = [1, 0, -1, 0]
Flag = False
while len(queue) > 0:
    vh,vw = queue.popleft()
    for m in range(4):
        nvh = vh+place_h[m]
        nvw = vw+place_w[m]
        if 0<=nvh<H and 0<=nvw<W and dist[nvh][nvw] == -1 and s[nvh][nvw] == ".":
            queue.append([nvh,nvw])
            dist[nvh][nvw] = dist[vh][vw]+1
if dist[H-1][W-1] == -1:
    print(-1)
else:
    print(W*H-dist[H-1][W-1]-black-1)

Submission status: Accepted

Solution code:
from collections import deque

h, w = map(int, input().split())
INF = 10000000000
b = 0
maze = [[] for _ in range(h)]
for i in range(h):
  l = list(input())
  b += l.count("#")
  maze[i] = l

dist = [[INF for _ in range(w)] for _ in range(h)]
dx = [0, 1, 0, -1]
dy = [1, 0, -1, 0]

q = deque()
q.append((0,0))
dist[0][0] = 0

while q:
  x, y = q.popleft()
  if (x == w-1) and (y == h-1): break
  for i in range(len(dx)):
    nx = x + dx[i]
    ny = y + dy[i]
    if (nx >= 0) and (nx < w) and (ny >= 0) and (ny < h) and (maze[ny][nx] != "#") and (dist[ny][nx] == INF):
      q.append((nx, ny))
      dist[ny][nx] = dist[y][x] + 1
      
if dist[h-1][w-1] == INF:
  print(-1)
else:
  print((h*w) - (dist[h-1][w-1]+1) - b)

Submission status: Accepted

Solution code:
import sys
def input():
    return sys.stdin.readline()[:-1]

"""
H Wの後に
#.#.
###.
みたいな文字列を受け取る
"""
H,W = map(int,input().split(' '))
MAP = [['#']*(W+1)] + [None]*H

for i in range(1,H+1):
    MAP[i] = ['#'] + list(map(str,input()))
import queue
q = queue.Queue()


MAP[H][W] = 'G'
visited = [None]*(H+1)
for i in range(H+1):
    visited[i] = [False]*(W+1)

d_num = 0
for i in range(1,H+1):
    for j in range(1,W+1):
        if MAP[i][j]=='#':
            d_num += 1

def is_okay(x,y):
    if not (0<x<W+1) or not (0<y<H+1):
        return False
    if visited[y][x] or MAP[y][x]=='#':
        return False
    return True

n = 0
q.put([1,1,n])
ans = 10**7 + 7
delta = [[1,0],[-1,0],[0,1],[0,-1]]
while not q.empty():
    x,y,n = q.get()
    k = MAP[y][x]

    n += 1
    if k=='G':
        ans = min(ans,n)
        break
    for d in delta:
        dx = x+d[0]
        dy = y+d[1]
        if is_okay(dx,dy):
            q.put([dx,dy,n])
            visited[dy][dx] = True

if not ans==10**7 + 7:
    ANS = H*W - ans - d_num
else:
    ANS = -1

print(ANS)

Submission status: Accepted

Solution code:
import sys
def input():
    return sys.stdin.readline()[:-1]

"""
H Wの後に
#.#.
###.
みたいな文字列を受け取る
"""
H,W = map(int,input().split(' '))
MAP = [['#']*(W+1)] + [None]*H

for i in range(1,H+1):
    MAP[i] = ['#'] + list(map(str,input()))
import queue
q = queue.Queue()


MAP[H][W] = 'G'
visited = [None]*(H+1)
for i in range(H+1):
    visited[i] = [False]*(W+1)

d_num = 0
for i in range(1,H+1):
    for j in range(1,W+1):
        if MAP[i][j]=='#':
            d_num += 1

def is_okay(x,y):
    if not (0<x<W+1) or not (0<y<H+1):
        return False
    if visited[y][x] or MAP[y][x]=='#':
        return False
    return True

n = 0
q.put([1,1,n])
ans = 10**7 + 7

while not q.empty():
    x,y,n = q.get()
    k = MAP[y][x]

    n += 1
    if k=='G':
        ans = min(ans,n)
        break

    if is_okay(x+1,y):
        q.put([x+1,y,n])
        visited[y][x+1] = True
    if is_okay(x-1,y):
        q.put([x-1,y,n])
        visited[y][x-1] = True
    if is_okay(x,y+1):
        q.put([x,y+1,n])
        visited[y+1][x] = True
    if is_okay(x,y-1):
        q.put([x,y-1,n])
        visited[y-1][x] = True


if not ans==10**7 + 7:
    ANS = H*W - ans - d_num
else:
    ANS = -1

print(ANS)

Submission status: Accepted

Solution code:
# https://atcoder.jp/contests/abc088/tasks/abc088_d

from collections import deque

def solve(R, C, sy, sx, gy, gx, mz):
  queue = deque()
  checked = set( )
  queue.append((sx, sy, 0))
  while queue:
    x, y, n = queue.popleft()
    if x == gx and y == gy:
      return n
    if x < 1 or x > C or y < 1 or y > R or mz[y-1][x-1] == '#':
      continue
    if (x, y) in checked:
      continue
    checked.add((x, y))
    queue.append((x+1, y, n+1))
    queue.append((x-1, y, n+1))
    queue.append((x, y+1, n+1))
    queue.append((x, y-1, n+1))
  return -1


if __name__ == '__main__':
  R, C = map(int, input().split(' '))
  sy, sx = 1, 1
  gy, gx = R, C
  mz = []
  whites = 0
  for r in range(R):
    tmp = input()
    mz.append(tmp)
    whites += tmp.count('.')
  n = solve(R, C, sy, sx, gy, gx, mz)
  if n < 0:
    print(-1)
  else:
    print(whites - n - 1)

Submission status: Accepted

Solution code:
# coding: utf-8
# Your code here!

from collections import deque


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


ls = eval("input(),"*h)

kuro = 0
for i in range(h):
    kuro += ls[i].count("#")


done = [[0]*w for _ in range(h)]

s = deque()
yone =(0,0,1,-1)
xone =(1,-1,0,0)

s.append((0,0))
while s:
    y, x = s.popleft()
    for i,j in zip(yone,xone):
        ny = y+i
        nx = x+j
        if (0 <= ny < h) and (0 <= nx < w):
            if (ls[ny][nx]==".") and (done[ny][nx]==0):
                s.append([ny,nx])
                done[ny][nx] = done[y][x] + 1
               
 
if done[h-1][w-1]:
    print(h*w -kuro -done[h-1][w-1]-1)
else:
    print(-1)

Submission status: Accepted

Solution code:
from queue import Queue

def bfs(point):
    global visit, s
    while point.qsize() > 0:
        hh, ww = point.get()
        h_w_list = [[1, 0], [- 1, 0], [0, 1], [0, - 1]]
        for h_, w_ in h_w_list:
            h_ = h_ + hh
            w_ = w_ + ww
            if (h_ in range(h)) & (w_ in range(w)):
                if s[h_][w_] == ".":
                    if visit[h_][w_] == inf:                    
                        point.put([h_, w_])
                        visit[h_][w_] = visit[hh][ww] + 1
        
    
inf = 10 ** 9    
h, w = map(int, input().split())
s = []
point_num = 0
for _ in range(h):
    k = input()
    point_num += k.count(".")
    s.append(list(k))
visit = [[inf for _ in range(w)] for _ in range(h)]
point = Queue()
point.put([0, 0])
visit[0][0] = 0
bfs(point)
ans = point_num - visit[-1][-1] - 1
if ans < 0:
    ans = -1
print(ans)

Submission status: Accepted

Solution code:
from collections import deque

H, W = map(int, input().split())
maze = [list(input()) for _ in range(H)]
d = [[10**9 for _ in range(W)] for _ in range(H)]

w_count = -2
for i in range(H):
  for j in range(W):
    if maze[i][j] == ".":
      w_count += 1

que = deque()
que.append([0, 0])
d[0][0] = 0
dxy = [[-1, 0], [1, 0], [0, -1], [0, 1]]
while len(que) != 0:
  p = que.popleft()
  for i in dxy:
    nx = p[0] + i[0]
    ny = p[1] + i[1]
    if 0 <= nx < H and 0 <= ny < W and d[nx][ny] == 10**9 and maze[nx][ny] == ".":
      d[nx][ny] = d[p[0]][p[1]] + 1
      que.append([nx, ny])
if d[H-1][W-1] == 10**9:
  print(-1)
else:
  print(w_count - d[H-1][W-1] + 1)

Submission status: Accepted

Solution code:
# ABC 088 D

from collections import deque

def resolve():
    WALL = -1
    UNVISITED = -2

    H, W = map(int, input().split())
    sy, sx = 0, 0
    gy, gx = H-1, W-1

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

    num_aile = 0

    for i in range(H):
        tmp = input()
        for j in range(W):
            if tmp[j] == '.':
                c[i][j] = UNVISITED
                num_aile += 1
            else:
                c[i][j] = WALL

    que = deque([[sy, sx]])
    c[sy][sx] = 0

    def BFS(x, y):
        for i, j in [[x-1, y], [x+1, y], [x, y-1], [x, y+1]]:
            if i < 0 or H <= i or j < 0 or W <= j:
                continue
            if c[i][j] == UNVISITED:
                que.append([i, j])
                c[i][j] = c[x][y] + 1

    while len(que) > 0:
        p = que.popleft()
        BFS(p[0], p[1])

    if c[gy][gx] == -2:
        print(-1)
    else:
        print(num_aile - c[gy][gx] - 1)


if __name__ == "__main__":
    resolve()

Submission status: Accepted

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

ans = H * W
for si in s:
    ans -= si.count("#")

visited = [[False] * W for _ in range(H)]
q = deque()
q.append((1, 0, 0))
visited[0][0] = True

while len(q):
    n, i, j = q.popleft()
    if (i, j) == (H - 1, W - 1):
        ans -= n
        break
    for x, y in ((i-1, j), (i+1, j), (i, j-1), (i, j+1)):
        if not 0 <= x < H or not 0 <= y < W:
            continue
        if visited[x][y] or s[x][y] == "#":
            continue
        q.append((n+1, x, y))
        visited[x][y] = True
else:
    print(-1)
    exit()

print(ans)

Submission status: Accepted

Solution code:
#!/usr/bin/env python
# coding: utf-8

import queue

def ri():
    return int(input())

def rl():
    return list(input().split())

def rli():
    return list(map(int, input().split()))

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

class BFS:
    def __init__(self, h, w, board):
        self.h = h
        self.w = w
        self.board = board
        self.num_empty = 0
        for x in range(1, w+1):
            for y in range(1, h+1):
                if self.board[y][x] == '.':
                    self.num_empty += 1
        self.cost = [[-1 for _ in range(w+2)] for _ in range(h+2)]

    def search(self):
        q = queue.Queue()
        q.put((1, 1))
        self.cost[1][1] = 1
        while not q.empty():
            p = q.get()
            x, y = p[0], p[1]
            for i in range(4):
                nx = x+dx[i]
                ny = y+dy[i]
                if self.board[ny][nx] == '#':
                    continue
                if self.cost[ny][nx] >= 0:
                    continue
                q.put((nx, ny))
                self.cost[ny][nx] = self.cost[y][x]+1
        c = self.cost[self.h][self.w]
        if c == -1:
            return -1
        else:
            return self.num_empty - c

def main():
    h, w = rli()
    board = []
    board.append('#'*(w+2))
    for _ in range(h):
        board.append('#'+input()+'#')
    board.append('#'*(w+2))
    bfs = BFS(h, w, board)
    ans = bfs.search()
    print(ans)



if __name__ == '__main__':
    main()

Submission status: Accepted

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

# bfs 
C[0][0] = 0
pre_list = [(0,0)]
count = 0
 
while C[H-1][W-1] == '.' and len(pre_list) > 0:
    count += 1
    next_list = []
    for y,x in pre_list:
        for i,j in ((1,0),(0,-1),(0,1),(-1,0)):
            if y+i < 0 or x+j < 0 or y+i >= H or x+j >= W:
                continue
            if C[y+i][x+j] == '.':
                C[y+i][x+j] = count
                next_list.append((y+i,x+j))
    pre_list = next_list

if C[H-1][W-1] == '.':
    print(-1)
else:
    black = 0
    for h in C:
        for v in h:
            if v == "#":
                black += 1
    print(H*W-black-count-1)

Submission status: Accepted

Solution code:
H,W = map(int,input().split())
s = [[c=="." for c in input()] for _ in [0]*H]

def bsf_dist_grid(grid,start):
    H = len(grid)
    W = len(grid[0])
    d = [[-1]*W for _ in [0]*H]
    d[start[0]][start[1]] = 0
    q = [start]
    while q:
        qq = []
        for xy in q:
            x,y = xy
            d0 = d[y][x]
            for dx,dy in ((1,0),(-1,0),(0,1),(0,-1)):
                if (not 0<=x+dx<W) or (not 0<=y+dy<H): continue
                if d[y+dy][x+dx] != -1: continue
                if not grid[y+dy][x+dx]: continue
                d[y+dy][x+dx] = d0+1
                qq.append((x+dx,y+dy))
        q = qq
    return d

d = bsf_dist_grid(s,(0,0))[-1][-1]
print((sum(sum(a) for a in s)-d-1) if d>=0 else -1)

Submission status: Accepted

Solution code:
from collections import deque
import time, sys


H, W = map(int, input().split())
fields = [""]*(H + 2)
fields[0] = ["#"] * (W + 2)
fields[H + 1] = ["#"] * (W + 2)
sx, sy = 1, 1
gx, gy = W, H
for i in range(1, H + 1):
    fields[i] = ["#"] + list(input()) + ["#"]

    
p = deque()
p.appendleft([sx, sy])

dist = [[None] * (W + 2) for _ in range(0, H + 2)] 
dist[sy][sx] = 0
delta = [[0, 1], [1, 0], [0, -1], [-1, 0]]
while p:
    x, y = p.pop()
    
    # goal チェック
    if (x == gx) & (y == gy):
        break
    
    # 次のマスへ
    for dx, dy in delta:
        nx = x + dx
        ny = y + dy
        
        if fields[ny][nx] == "#":
            continue
        
        if dist[ny][nx] is not None:
            continue
        
        # 未踏の場合
        p.appendleft([nx, ny])
        dist[ny][nx] = dist[y][x] + 1
        
if dist[gy][gx] is None:
    print(-1)
    sys.exit()
        
# 白塗のマスを数える
white_cnt = 0

for line in fields:
    for j in line:
        if j == ".":
            white_cnt += 1

# スタートとゴールは白かつ塗れない
white_cnt = white_cnt - 2

# 必要な移動数分だけ残す
white_cnt = white_cnt - dist[gy][gx] + 1

print(white_cnt)

Submission status: Accepted

Solution code:
import math
import copy
from operator import mul
from functools import reduce
from collections import defaultdict
from collections import Counter
from collections import deque
# 直積 A={a, b, c}, B={d, e}:のとき，A×B={(a,d),(a,e),(b,d),(b,e),(c,d),(c,e)}: product(A, B)
from itertools import product
# 階乗 P!: permutations(seq), 順列 {}_len(seq) P_n: permutations(seq, n)
from itertools import permutations
# 組み合わせ {}_len(seq) C_n: combinations(seq, n)
from itertools import combinations
# 一次元累積和
from itertools import accumulate
from bisect import bisect_left, bisect_right

import re
# import numpy as np
# from scipy.misc import perm
# from scipy.misc import comb

def inside(y, x, H, W):
    return 0 <= y < H and 0 <= x < W

# 四方向: 右, 下, 左, 上
dy = [0, -1, 0, 1]
dx = [1, 0, -1, 0]
 
def i_inpl(): return int(input())
def l_inpl(): return list(map(int, input().split()))
def line_inpl(x): return [i_inpl() for _ in range(x)]

INF = int(1e18)
MOD = int(1e9)+7 # 10^9 + 7

########

H, W = l_inpl()
field = [ input() for _ in range(H) ]
sy, sx = 0, 0
gy, gx = H-1, W-1
def bfs(field, number_of_moves, sy, sx):
    queue = deque([[sy, sx]])
    number_of_moves[sy][sx] = 0
    while queue:
        y, x = queue.popleft()
        current_number_of_move = number_of_moves[y][x]
        for i in range(4):
            ny, nx = y + dy[i], x + dx[i]
            if inside(ny, nx, H, W) and \
                field[ny][nx] == "." and \
                number_of_moves[ny][nx] == -1:
                number_of_moves[ny][nx] = current_number_of_move + 1
                queue.append([ny, nx])
    return number_of_moves

number_of_moves = [ [-1] * W for _ in range(H) ]
number_of_moves = bfs(field, number_of_moves, sy, sx)
b_cnt = sum([ f.count("#") for f in field])

if number_of_moves[gy][gx] == -1:
    print(-1)
else:
    print(H*W-b_cnt-number_of_moves[gy][gx]-1)

Submission status: Accepted

Solution code:
import numpy as np

h,w = map(int,input().split())
f = []
bk = 0
f.append(["#" for i in range(w+2)])
for i in range(h):
    l = list(input())
    for c in l:
        if c=="#":
            bk += 1
    f.append(["#"]+l+["#"])
f.append(["#" for i in range(w+2)])
visited = {"1,1":0}

now = [[1,1]]
next = []

def to_key(l):
    return str(l[0])+","+str(l[1])

flag = True
count = 1
while 1:
    if len(now) == 0:
        flag = False
        break
    for state in now:
        x = state[0]
        y = state[1]

        if x==h and y == w:
            break

        if f[x+1][y]=="." and to_key([x+1,y]) not in visited:
            next.append([x+1,y])
            visited[to_key([x+1,y])] = count
        if f[x][y+1]=="." and to_key([x,y+1]) not in visited:
            next.append([x,y+1])
            visited[to_key([x,y+1])] = count
        if f[x-1][y]=="." and to_key([x-1,y]) not in visited:
            next.append([x-1,y])
            visited[to_key([x-1,y])] = count
        if f[x][y-1] == "." and to_key([x,y-1]) not in visited:
            next.append([x, y-1])
            visited[to_key([x,y-1])] = count
    count += 1
    now = next
    next = []
    # print(visited)

if flag:
    print(h*w-visited[to_key([h,w])]-bk-1)
else:
    if to_key([h,w]) in visited:
        print(h * w - visited[to_key([h, w])] - bk-1)
    else:
        print(-1)

Submission status: Accepted

Solution code:
h,w=map(int,input().split())
state=[]
for i in range(h):
    state.append(input())
count=0
for i in range(h):
    for j in range(w):
        if state[i][j]=='.':
            count+=1
def bfs():
    dist=[[-1]*w for i in range(h)]
    dist[0][0]=0
    stack=[]
    stack.append([0,0])

    while(stack):
        #print(dist)
        node=stack.pop(0)
        for i,j in zip([1,-1,0,0],[0,0,1,-1]):
            if 0<=node[0]+i<h and 0<= node[1]+j<w:
                if dist[node[0]+i][node[1]+j]==-1 and state[node[0]+i][node[1]+j]=='.':
                    dist[node[0]+i][node[1]+j]=dist[node[0]][node[1]]+1
                    if [node[0]+i,node[1]+j]==[h-1,w-1]:
                        break
                    stack.append([node[0]+i,node[1]+j])
    if dist[h-1][w-1]==-1:
        print(-1)
    else:
        print(count-1-dist[h-1][w-1])

bfs()