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: Runtime Error

Solution code:
import sys
sys.setrecursionlimit(1000000000)
from collections import deque
def bfs(Y,X,count):
    # print("now",Y+1,X+1)
    # print(count,"手目")
    reached[Y][X]=True

    if Y==goalY and X==goalX:
        result=0
        for i in range(H):
            for j in range(W):
                if F[i][j]=="#":
                    result+=1
        print(H*W - result - count -1)
        exit()

    if Y < H-1 :
        if F[Y+1][X]=="." and reached[Y+1][X]==False:
            # print(Y+1+1,X+1,"を積みます")
            yQUE.appendleft(Y+1)
            xQUE.appendleft(X)
            cQUE.appendleft(count+1)
            reached[Y+1][X]=True
    if X < W-1 :
        if F[Y][X+1]=="." and reached[Y][X+1]==False:
            # print(Y+1,X+1+1,"を積みます")
            yQUE.appendleft(Y)
            xQUE.appendleft(X+1)
            cQUE.appendleft(count+1)
            reached[Y][X+1]=True
    if 0 < Y :
        if F[Y-1][X]=="." and reached[Y-1][X]==False:
            # print(Y-1+1,X+1,"を積みます")
            yQUE.appendleft(Y-1)
            xQUE.appendleft(X)
            cQUE.appendleft(count+1)
            reached[Y-1][X]=True
    if 0 < X :
        if F[Y][X-1]=="." and reached[Y][X-1]==False:
            # print(Y+1,X-1+1,"を積みます")
            yQUE.appendleft(Y)
            xQUE.appendleft(X-1)
            cQUE.appendleft(count+1)
            reached[Y][X-1]=True    
    bfs(yQUE.pop(),xQUE.pop(),cQUE.pop())

H,W = map(int,input().split())
# R,C=7,8
# startY,startX = map(int,input().split())
startY=0
startX=0
# startY,startX = 1,1
# goalY,goalX = map(int,input().split())
goalX=W-1
goalY=H-1
# goalY,goalX = 3,4
F = list(list(input()) for _ in range(H))
# F = [
# '########',
# '#......#',
# '#.######',
# '#..#...#',
# '#..##..#',
# '##.....#',
# '########']
reached = [[False for i in range(W)] for i in range(H)]
count=0
# for i in range (R):
#     print("".join(F[i]))
xQUE =  deque(maxlen=1000000000)
yQUE =  deque(maxlen=1000000000)
cQUE =  deque()
# result=0
# for i in range(H):
#     for j in range(W):
#         if F[i][j]=="#":
#             result+=1
# print(result)
bfs(startY,startX,count)
# print(QUE)
print("-1")

Submission status: Runtime Error

Solution code:
import sys
sys.setrecursionlimit(1000000000)
from collections import deque
def bfs(Y,X,count):
    # print("now",Y+1,X+1)
    # print(count,"手目")
    reached[Y][X]=True

    if Y==goalY and X==goalX:
        result=0
        for i in range(H):
            for j in range(W):
                if F[i][j]=="#":
                    result+=1
        print(H*W - result - count -1)
        exit()

    if Y < H-1 :
        if F[Y+1][X]=="." and reached[Y+1][X]==False:
            # print(Y+1+1,X+1,"を積みます")
            yQUE.appendleft(Y+1)
            xQUE.appendleft(X)
            cQUE.appendleft(count+1)
            reached[Y+1][X]=True
    if X < W-1 :
        if F[Y][X+1]=="." and reached[Y][X+1]==False:
            # print(Y+1,X+1+1,"を積みます")
            yQUE.appendleft(Y)
            xQUE.appendleft(X+1)
            cQUE.appendleft(count+1)
            reached[Y][X+1]=True
    if 0 < Y :
        if F[Y-1][X]=="." and reached[Y-1][X]==False:
            # print(Y-1+1,X+1,"を積みます")
            yQUE.appendleft(Y-1)
            xQUE.appendleft(X)
            cQUE.appendleft(count+1)
            reached[Y-1][X]=True
    if 0 < X :
        if F[Y][X-1]=="." and reached[Y][X-1]==False:
            # print(Y+1,X-1+1,"を積みます")
            yQUE.appendleft(Y)
            xQUE.appendleft(X-1)
            cQUE.appendleft(count+1)
            reached[Y][X-1]=True    
    bfs(yQUE.pop(),xQUE.pop(),cQUE.pop())

H,W = map(int,input().split())
# R,C=7,8
# startY,startX = map(int,input().split())
startY=0
startX=0
# startY,startX = 1,1
# goalY,goalX = map(int,input().split())
goalX=W-1
goalY=H-1
# goalY,goalX = 3,4
F = list(list(input()) for _ in range(H))
# F = [
# '########',
# '#......#',
# '#.######',
# '#..#...#',
# '#..##..#',
# '##.....#',
# '########']
reached = [[False for i in range(W)] for i in range(H)]
count=0
# for i in range (R):
#     print("".join(F[i]))
xQUE =  deque(maxlen=1000000000)
yQUE =  deque(maxlen=1000000000)
cQUE =  deque()
# result=0
# for i in range(H):
#     for j in range(W):
#         if F[i][j]=="#":
#             result+=1
# print(result)
bfs(startY,startX,count)
# print(QUE)

Submission status: Runtime Error

Solution code:
H, W = map(int, input().split())
s = np.array([list(input()) for _ in range(H)])
s = np.pad(s, 1, "constant")
white = (s == ".").sum()
q = [(0, 1, 1)]

goal = False
s[1][1] = '#'
while q:
    d, x, y = q.pop(0)
    if x ==H and y == W :
        print(white - (d + 1))
        goal = True
    for dx, dy in [[0,1], [0, -1], [1,0], [-1,0]]:
        x = x + dx
        y = y + dy
        if s[x][y] == '.':
            s[x][y] = '#'
            q.append((d+1, x, y))
if not goal:
    print(-1)

Submission status: Runtime Error

Solution code:
H, W = map(int, input().split())
s = np.array([list(input()) for _ in range(H)])
s = np.pad(s, 1, "constant")
white = (s == ".").sum()
q = [(0, 1, 1)]

while q:
    d, x, y = q.pop(0)
    if x ==H and y == W :
        print(white - (d + 1))
        exit()
    for dx, dy in [[0,1], [0, -1], [1,0], [-1,0]]:
        x = x + dx
        y = y + dy
        if s[x][y] == '.':
            s[x][y] = '#'
            q.append((d+1, x, y))
print(-1)

Submission status: Runtime Error

Solution code:
from collections import deque

dd = [[1, 0], [-1, 0], [0, 1], [0, -1]]
H, W = list(map(int, input().split()))
field = [input() for _ in range(H)]
def bfs():
  dist = [[float('inf')] * W for _ in range(W)]
  que = deque()
  que.append((0, 0))
  dist[0][0] = 0
  while len(que) > 0:
    y, x = que.popleft()
    if y == H - 1 and x == W - 1:
      break
    for dx, dy in dd:
      ny, nx = y + dy, x + dx
      if 0<=nx<W and 0<=ny<H and field[ny][nx]=='.' and dist[ny][nx]==float('inf'):
        dist[ny][nx] = dist[y][x] + 1
        que.append((ny, nx))
  return dist[H - 1][W - 1]
    
count = sum([f.count('#') for f in field])
need = bfs()
      
if need == float('inf'):
  print(-1)
else:
  print(H * W - count - need - 1)

Submission status: Runtime Error

Solution code:
from collections import deque

dd = [[1, 0], [-1, 0], [0, 1], [0, -1]]
H, W = list(map(int, input().split()))
field = [input() for _ in range(H)]
dist = [[float('inf')] * W for _ in range(W)]
que = deque()
que.append((0, 0))
dist[0][0] = 0

while len(que) > 0:
  y, x = que.popleft()
  if y == H - 1 and x == W - 1:
    break
  for dx, dy in dd:
    ny, nx = y + dy, x + dx
    if 0<=nx<W and 0<=ny<H and field[ny][nx]=='.' and dist[ny][nx]==float('inf'):
      dist[ny][nx] = dist[y][x] + 1
      que.append((ny, nx))
    
count = sum([f.count('#') for f in field])
      
if dist[H - 1][W - 1] != -1:
  print(H * W - count - dist[H - 1][W - 1] - 1)
else:
  print(-1)

Submission status: Runtime Error

Solution code:
from collections import deque

dx = [1, 0, -1, 0]
dy = [0, 1, 0, -1]
H, W = list(map(int, input().split()))
field = [input() for _ in range(H)]

dist = [[float('inf')] * W for _ in range(W)]
que = deque()
que.append((0, 0))
dist[0][0] = 0

while len(que) > 0:
  y, x = que.popleft()
  if y == H - 1 and x == W - 1:
    break
  for i in range(4):
    ny, nx = y + dy[i], x + dx[i]
    if 0<=nx<W and 0<=ny<H and field[ny][nx]=='.' and dist[ny][nx]==float('inf'):
      dist[ny][nx] = dist[y][x] + 1
      que.append((ny, nx))
    
count = sum([f.count('#') for f in field])
      
if dist[H - 1][W - 1] != -1:
  print(H * W - count - dist[H - 1][W - 1] - 1)
else:
  print(-1)

Submission status: Runtime Error

Solution code:
from collections import deque

dx = [1, 0, -1, 0]
dy = [0, 1, 0, -1]
H, W = map(int, input().split())
field = [input() for _ in range(H)]

dist = [[-1] * W for _ in range(W)]
que = deque()
que.append((0, 0))
dist[0][0] = 0

while len(que) > 0:
  y, x = que.popleft()
  if y == H - 1 and x == W - 1:
    break
  for i in range(4):
    ny, nx = y + dy[i], x + dx[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))
    
count = sum([f.count('#') for f in field])
      
if dist[H - 1][W - 1] != -1:
  print(H * W - count - dist[H - 1][W - 1] - 1)
else:
  print(-1)

Submission status: Runtime Error

Solution code:
from collections import deque

dx = [1, 0, -1, 0]
dy = [0, 1, 0, -1]
H, W = map(int, input().split())
field = [input() for _ in range(H)]

dist = [[-1] * W for _ in range(W)]
que = deque()
que.append((0, 0))
dist[0][0] = 0

while len(que) > 0:
  y, x = que.popleft()
  if y == H - 1 and x == W - 1:
    break
  for i in range(4):
    ny, nx = y + dy[i], x + dx[i]
    if nx < 0 or nx >= W or ny < 0 or ny >= H:
      continue
    if field[ny][nx] == '#':
      continue
    if dist[ny][nx] != -1:
      continue
    dist[ny][nx] = dist[y][x] + 1
    que.append((ny, nx))
    
count = sum([f.count('#') for f in field])
      
if dist[H - 1][W - 1] != -1:
  print(H * W - count - dist[H - 1][W - 1] - 1)
else:
  print(-1)

Submission status: Runtime Error

Solution code:
from collections import deque

dx = [1, 0, -1, 0]
dy = [0, 1, 0, -1]
H, W = map(int, input().split())
field = [input() for _ in range(H)]

dist = [[-1] * W for _ in range(W)]
que = deque()
que.append((0, 0))
dist[0][0] = 0

while not que.empty():
  y, x = que.popleft()
  if y == H - 1 and x == W - 1:
    break
  for i in range(4):
    ny, nx = y + dy[i], x + dx[i]
    if nx < 0 or nx >= W or ny < 0 or ny >= H:
      continue
    if field[ny][nx] == '#':
      continue
    if dist[ny][nx] != -1:
      continue
    dist[ny][nx] = dist[y][x] + 1
    que.append((ny, nx))
    
count = sum([f.count('#') for f in field])
      
if dist[H - 1][W - 1] != -1:
  print(H * W - count - dist[H - 1][W - 1] - 1)
else:
  print(-1)

Submission status: Runtime Error

Solution code:
import queue

dx = [1, 0, -1, 0]
dy = [0, 1, 0, -1]
H, W = map(int, input().split())
field = [input() for _ in range(H)]

dist = [[-1] * W for _ in range(W)]
que = queue.Queue()
que.put((0, 0))
dist[0][0] = 0

while not que.empty():
  y, x = que.get()
  if y == H - 1 and x == W - 1:
    break
  for i in range(4):
    ny, nx = y + dy[i], x + dx[i]
    if nx < 0 or nx >= W or ny < 0 or ny >= H:
      continue
    if field[ny][nx] == '#':
      continue
    if dist[ny][nx] != -1:
      continue
    dist[ny][nx] = dist[y][x] + 1
    que.put((ny, nx))
    
count = sum([f.count('#') for f in field])
      
if dist[H - 1][W - 1] != -1:
  print(H * W - count - dist[H - 1][W - 1] - 1)
else:
  print(-1)

Submission status: Runtime Error

Solution code:
import queue

dx = [1, 0, -1, 0]
dy = [0, 1, 0, -1]
H, W = map(int, input().split())
field = [input() for _ in range(H)]

dist = [[-1] * W for _ in range(W)]
que = queue.Queue()
que.put((0, 0))
dist[0][0] = 0

while not que.empty():
  y, x = que.get()
  for i in range(4):
    ny, nx = y + dy[i], x + dx[i]
    if nx < 0 or nx >= W or ny < 0 or ny >= H:
      continue
    if field[ny][nx] == '#':
      continue
    if dist[ny][nx] != -1:
      continue
    dist[ny][nx] = dist[y][x] + 1
    que.put((ny, nx))
    
count = sum([f.count('#') for f in field])
      
if dist[H - 1][W - 1] != -1:
  print(H * W - count - dist[H - 1][W - 1] - 1)
else:
  print(-1)

Submission status: Runtime Error

Solution code:
import sys
sys.setrecursionlimit(3000)
import queue

dx = [1, 0, -1, 0]
dy = [0, 1, 0, -1]
H, W = map(int, input().split())
field = [input() for _ in range(H)]

dist = [[-1] * W for _ in range(W)]
que = queue.Queue()
que.put((0, 0))
dist[0][0] = 0

while not que.empty():
  y, x = que.get()
  for i in range(4):
    ny, nx = y + dy[i], x + dx[i]
    if nx < 0 or nx >= W or ny < 0 or ny >= H:
      continue
    if field[ny][nx] == '#':
      continue
    if dist[ny][nx] != -1:
      continue
    dist[ny][nx] = dist[y][x] + 1
    que.put((ny, nx))
    
count = 0
for y in range(H):
  for x in range(W):
    if field[y][x] == '#':
      count += 1
      
if dist[H - 1][W - 1] != -1:
  print(H * W - count - dist[H - 1][W - 1] - 1)
else:
  print(-1)

Submission status: Runtime Error

Solution code:
import queue

dx = [1, 0, -1, 0]
dy = [0, 1, 0, -1]
H, W = map(int, input().split())
field = [input() for _ in range(H)]

dist = [[-1] * W for _ in range(W)]
que = queue.Queue()
que.put((0, 0))
dist[0][0] = 0

while not que.empty():
  y, x = que.get()
  for i in range(4):
    ny, nx = y + dy[i], x + dx[i]
    if nx < 0 or nx >= W or ny < 0 or ny >= H:
      continue
    if field[ny][nx] == '#':
      continue
    if dist[ny][nx] != -1:
      continue
    dist[ny][nx] = dist[y][x] + 1
    que.put((ny, nx))
    
count = 0
for y in range(H):
  for x in range(W):
    if field[y][x] == '#':
      count += 1
      
if dist[H - 1][W - 1] != -1:
  print(H * W - count - dist[H - 1][W - 1] - 1)
else:
  print(-1)

Submission status: Runtime Error

Solution code:
import queue

dx = [1, 0, -1, 0]
dy = [0, 1, 0, -1]
H, W = map(int, input().split())
field = [input() for _ in range(H)]

dist = [[-1] * W for _ in range(W)]
que = queue.Queue()
que.put((0, 0))
dist[0][0] = 0

while not que.empty():
  y, x = que.get()
  for i in range(4):
    ny, nx = y + dy[i], x + dx[i]
    if nx < 0 or nx >= W or ny < 0 or ny >= H:
      continue
    if field[ny][nx] == '#':
      continue
    if dist[ny][nx] != -1:
      continue
    dist[ny][nx] = dist[y][x] + 1
    que.put((ny, nx))
    
count = 0
for y in range(H):
  for x in range(W):
    if field[y][x] == '#':
      count += 1
      
if dist[H - 1][W - 1] != -1:
  print(H * W - count - dist[H - 1][W - 1])
else:
  print(-1)

Submission status: Runtime Error

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]]
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: Runtime Error

Solution code:
import sys
sys.setrecursionlimit(2000)
h,w=map(int,input().split())
s=['#'*(w+2)]+['#'+input()+'#' for _ in [0]*h]+['#'*(w+2)]
l=[[0]*(w+2) for _ in [0]*(h+2)]
for i in range(h+2):
    for j in range(w+2):
        if s[i][j]=='#':
            l[i][j]=-1
def sol(m,n):
    global l
    if l[m][n]>=0:
        for [i,j] in [[m-1,n],[m+1,n],[m,n-1],[m,n+1]]:
            if l[i][j]==0 and [i,j]!=[1,1]:
                l[i][j]=l[m][n]+1
                sol(i,j)
            elif l[i][j]>l[m][n]+1:
                l[i][j]=l[m][n]+1
                sol(i,j)
sol(1,1)
if l[h][w]==0:print(-1)
else:print(h*w-l[h][w]-(sum(x.count('#') for x in s)-2*h-2*w-4)-1)

Submission status: Runtime Error

Solution code:
h,w=map(int,input().split())
s=['#'*(w+2)]+['#'+input()+'#' for _ in [0]*h]+['#'*(w+2)]
l=[[0]*(w+2) for _ in [0]*(h+2)]
for i in range(h+2):
    for j in range(w+2):
        if s[i][j]=='#':
            l[i][j]=-1
def sol(m,n):
    global l
    if l[m][n]>=0:
        for [i,j] in [[m-1,n],[m+1,n],[m,n-1],[m,n+1]]:
            if l[i][j]==0 and [i,j]!=[1,1]:
                l[i][j]=l[m][n]+1
                sol(i,j)
            elif l[i][j]>l[m][n]+1:
                l[i][j]=l[m][n]+1
                sol(i,j)
sol(1,1)
if l[h][w]==0:print(-1)
else:print(h*w-l[h][w]-(sum(x.count('#') for x in s)-2*h-2*w-4)-1)

Submission status: Runtime Error

Solution code:
h,w=map(int,input().split())
s=['#'*(w+2)]+['#'+input()+'#' for _ in [0]*h]+['#'*(w+2)]
l=[[0]*(w+2) for _ in [0]*(h+2)]
for i in range(h+2):
    for j in range(w+2):
        if s[i][j]=='#':
            l[i][j]=-1
def sol(m,n):
    global l
    if l[m][n]>=0:
        for [i,j] in [[m-1,n],[m+1,n],[m,n-1],[m,n+1]]:
            if l[i][j]==0 and [i,j]!=[1,1]:
                l[i][j]=l[m][n]+1
                sol(i,j)
            elif l[i][j]>l[m][n]+1:
                l[i][j]=l[m][n]+1
                sol(i,j)
sol(1,1)
print(h*w-l[h][w]-(sum(x.count('#') for x in s)-2*h-2*w-4)-1)

Submission status: Runtime Error

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("#")

print(h * w - bfs(0, 0, h - 1, w - 1) - black_cnt)

Submission status: Runtime Error

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 True:
    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 nvh == H-1 and nvw == W-1:
                Flag = True
                break
    if Flag:
        break
print(W*H-dist[H-1][W-1]-black-1)

Submission status: Runtime Error

Solution code:
import numpy as np
h,w=map(int,input().split())
box=[list(input()) for i in range(h)]
count=h*w-(w+h-1)
for i in range(h):
    for j in range(w):
        if box[i][j]=="#":
            count -=1

another_box=[["#"]+box[i]+["#"] for i in range(h)]
another_box.insert(0,["#"]*(w+2))
another_box.append(["#"]*(w+2))
another_box[h][w]="G"

def maper(another_box,strat_x,strat_y):
    another_box[strat_x][strat_y]="#"
    for xx,yy in [[0,1],[0,-1],[1,0],[-1,0]]:
        n_x,n_y=strat_x+xx,strat_y+yy
        if another_box[n_x][n_y]==".":
            maper(another_box,n_x,n_y)
        elif another_box[n_x][n_y]=="G":
            another_box[n_x][n_y]="C"
    return another_box

flag=0
answer_box=maper(another_box,1,1)
for i in range(h+2):
    for j in range(w+2):
        if answer_box[i][j]=="C":
            flag=1

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

Submission status: Runtime Error

Solution code:
import numpy as np
h,w=map(int,input().split())
box=[list(input()) for i in range(h)]
count=h*w-(w+h-1)
for i in range(h):
    for j in range(w):
        if box[i][j]=="#":
            count -=1

another_box=[["#"]+box[i]+["#"] for i in range(h)]
another_box.insert(0,["#"]*(w+2))
another_box.append(["#"]*(w+2))
another_box[h][w]="G"
print(np.array(another_box))
def maper(another_box,strat_x,strat_y):
    another_box[strat_x][strat_y]="#"
    for xx,yy in [[0,1],[0,-1],[1,0],[-1,0]]:
        n_x,n_y=strat_x+xx,strat_y+yy
        if another_box[n_x][n_y]==".":
            maper(another_box,n_x,n_y)
        elif another_box[n_x][n_y]=="G":
            another_box[n_x][n_y]="C"
    return another_box

flag=0
answer_box=maper(another_box,1,1)
for i in range(h+2):
    for j in range(w+2):
        if answer_box[i][j]=="C":
            flag=1

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

Submission status: Runtime Error

Solution code:
h,w=map(int,input().split())
box=[list(input()) for i in range(h)]
count=h*w-(w+h-1)
for i in range(h):
    for j in range(w):
        if box[i][j]=="#":
            count -=1

another_box=[["#"]+box[i]+["#"] for i in range(h)]
another_box.insert(0,["#"]*(w+2))
another_box.append(["#"]*(w+2))
another_box[h][w]="G"

def maper(another_box,strat_x,strat_y):
    another_box[strat_x][strat_y]="#"
    for xx,yy in [[0,1],[0,-1],[1,0],[-1,0]]:
        n_x,n_y=strat_x+xx,strat_y+yy
        if another_box[n_x][n_y]==".":
            maper(another_box,n_x,n_y)
        elif another_box[n_x][n_y]=="G":
            another_box[n_x][n_y]="C"
    return another_box

flag=0
answer_box=maper(another_box,1,1)
for i in range(h+2):
    for j in range(w+2):
        if answer_box[i][j]=="C":
            flag=1

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

Submission status: Runtime Error

Solution code:
h,w=map(int,input().split())
box=[list(input()) for i in range(h)]
count=h*w-(w+h-1)
for i in range(h):
    for j in range(w):
        if box[i][j]=="#":
            count -=1

another_box=[["#"]+box[i]+["#"] for i in range(h)]
another_box.insert(0,["#"]*(w+2))
another_box.append(["#"]*(w+2))
another_box[h][w]="G"

def maper(another_box,strat_x,strat_y):
    another_box[strat_x][strat_y]="#"
    for xx,yy in [[0,1],[0,-1],[1,0],[-1,0]]:
        n_x,n_y=strat_x+xx,strat_y+yy
        if another_box[n_x][n_y]==".":
            maper(another_box,n_x,n_y)
        elif another_box[n_x][n_y]=="G":
            another_box[n_x][n_y]="C"
    return another_box

flag=0
answer_box=maper(another_box,1,1)
for i in range(h+2):
    for j in range(w+2):
        if answer_box[i][j]=="C":
            flag=1

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

Submission status: Runtime Error

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: Runtime Error

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


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)
  print(whites - n - 1)

Submission status: Runtime Error

Solution code:
from queue import Queue

def bfs(point):
    global visit, s
    while point.qsize() > 0:
        hh, ww = point.get()
        h_w_list = [[hh + 1, ww], [hh - 1, ww], [hh, ww + 1], [hh, ww - 1]]
        min_num = inf
        for h_, w_ in h_w_list:
            if (h_ in range(h)) & (w_ in range(w)):
                min_num = min(min_num, visit_num[h_][w_])
                if s[h_][w_] == ".":
                    if visit[h_][w_] == inf:                    
                        point.put([h_, w_])
        if visit[hh][ww] == inf:
            visit[hh][ww] = min_num

    
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: Runtime Error

Solution code:
from queue import Queue

def bfs(point):
    global visit, s
    while point.qsize() > 0:
        hh, ww = point.get()
        h_w_list = [[hh + 1, ww], [hh - 1, ww], [hh, ww + 1], [hh, ww - 1]]
        min_num = inf
        for h_, w_ in h_w_list:
            if (h_ in range(h)) & (w_ in range(w)):
                min_num = min(min_num, visit_num[h_][w_])
                if s[h_][w_] == ".":
                    if visit[h_][w_] == inf:                    
                        point.put([h_, w_])
        if visit[hh][ww] == inf:
            visit[hh][ww] = calc_min(hh, ww)

    
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: Runtime Error

Solution code:
# #の数を数えておいて、x*y-(最短距離+最初の#の数）
# 最短経路なので幅優先でやる
from collections import deque

h, w = map(int, input().split())
table =[]
default_dot = 0
for _ in range(h):
  line = list(input())
  default_dot+=line.count(".")
  table.append(line)

default_dot-=2  # スタートとゴール
table[0][0] = 0

cur = [0, 0]   # x, y
queue = deque()
queue.append(cur)
steps = [0, 1, 0, -1, 0]

minimum_step = 0

while True:
  now = queue.popleft()
  if now[0] == w-1 and now[1] == h-1:
    minimum_step = table[now[1]][now[0]]-1
    break
  for i in range(4):
    next_y, next_x = now[1]+steps[i], now[0]+steps[i+1]
    if 0<=next_y<h and 0<=next_x<w and table[next_y][next_x] == ".":
      table[next_y][next_x] = table[now[1]][now[0]]+1
      queue.append([next_x, next_y])


print(default_dot-minimum_step)

Submission status: Runtime Error

Solution code:
from collections import deque

def bfs(maze, goal_x, goal_y):
    count = 0
    Q = deque([(0, 0, 0)])
    while Q:
        x, y, level = Q.popleft()
        if [x, y] == [goal_x-1, goal_y-1]:
            for j in range(10):
                count += maze[j].count('#')
            print(goal_x*goal_y - count - (level+1))
            exit()
        elif maze[x][y] == '.':
            maze[x][y] = level
            if x+1 < goal_x:
                Q += [(x+1, y, level+1)]
            if y+1 < goal_y:
                Q += [(x, y+1, level+1)]
            if 0 < x-1 < goal_x:
                Q += [(x-1, y, level+1)]
            if 0 < y-1 < goal_y:
                Q += [(x, y-1, level+1)]
    print('-1')
        
            
goal_x, goal_y = map(int, input().split())
maze = []
for i in range(goal_x):
    maze.append(list(input()))


bfs(maze, goal_x, goal_y)

Submission status: Runtime Error

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

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

S[0][0] = 0
for i in range(H):
  for j in range(W):
    if S[i][j] != "#":     
      for k in [[0,1],[1,0],[-1,0],[0,-1]]:
        if not(0 <= i + k[0] < H):
          continue
        elif not(0 <= j + k[1] < W):
          continue
        elif S[i+k[0]][j+k[1]] != ".":
          continue
        else:
          S[i+k[0]][j+k[1]] = S[i][j]+1
        
if S[H-1][W-1] == ".":
  print(-1)
  exit()
  
ans = C - S[H-1][W-1] -1
print(ans)