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:
from queue import Queue
import itertools
import numpy as np

R, C = map(int, input().split())
sy, sx = 1, 1
gy, gx = R, C

field = [["#"] * (C + 2)] + \
        [list("#" + input() + "#") for i in range(R)] + \
        [["#"] * (C + 2)]
field = np.array(field)
dxy = [(0,1), (0,-1), (1,0), (-1,0)]
flg = False
cnt = 0

field_1d = list(itertools.chain.from_iterable(field))
field01 = [1 if i == '.' else 0 for i in field_1d]
dot_num = np.array(field01).sum()

q = Queue()
q.put([sy, sx])
field[sy][sx] = 0

while flg == False:
    yx = q.get()
    cnt = field[yx[0]][yx[1]]
    for dy, dx in dxy:
        y_n, x_n = yx[0] + dy, yx[1] + dx
        if y_n == gy and x_n == gx:
            field[y_n][x_n] = cnt + 1
            flg = True
            print(dot_num - (cnt+2))
        if field[y_n][x_n] == '#':
            continue
        if field[y_n][x_n] == '.':
            q.put([y_n, x_n])
            field[y_n][x_n] = cnt + 1
if flg == False:
    print(-1)

Submission status: Runtime Error

Solution code:
'''


'''
## import
from collections import deque # キュー、スタックに利用
import itertools
# import math # 数学的計算に利用
# import numpy as np # 行列計算などに利用
import sys

## 初期設定
input = sys.stdin.readline # 標準入力の高速化に利用
sys.setrecursionlimit(10**7) # 再帰関数の呼び出し上限を増やす
inf = float('inf')

is_debug = False


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

M = [list(input().rstrip()) for _ in range(h)]

## ステータス管理2次元配列
# 訪問状態をWHITE, GRAY, BLACKのいずれかで表す
M_color = [['WHITE']*w for _ in range(h)]

## 距離
# 初期値は-1（到達不能）を入れ、到達できたら実際の距離を代入する
M_distance = [[-1]*w for _ in range(h)]

route_str = '.'
# start, goal設定
sy=0
sx=0
gy=h-1
gx=w-1

def breadth_first_search():
    """

    """
    # 開始頂点sのステータスを探索中へ変更、距離は0を代入
    M_color[sy][sx] = 'GRAY'
    M_distance[sy][sx] = 0
    # キューを初期化し、開始頂点をキューへ代入
    q = deque()
    q.append([sy,sx])

    # 探索時の移動方向（上右下左） # delta y, delta x
    deltas = [[-1,0], [0,1], [1,0], [0,-1]]

    # qが空になるまでwhileループ処理
    while len(q) > 0:
        # 探索する頂点を取り出し
        y, x = q.popleft()

        # ゴールに辿り着いたら距離をreturn
        if x == gx and y == gy:
            return M_distance[y][x]

        ## uに隣接する全ての頂点について、未探索の場合は探索
        for delta in deltas:
            # 移動後の位置を算出
            after_y = y+delta[0]
            after_x = x+delta[1]
            # r,cの範囲に収まっていなければスキップ
            if after_x < 0 or after_x > w-1 or after_y < 0 or after_y > h-1:
                continue
            
            # 移動先が陸かつ未探索なら
            if M[after_y][after_x] == route_str and M_color[after_y][after_x] == 'WHITE':
                M_color[after_y][after_x] = 'GRAY'
                # 距離は、現在キューにある頂点u + 1となる（隣接しているので）
                M_distance[after_y][after_x] = M_distance[y][x] + 1
                # キューに追加
                q.append([after_y,after_x]) # キューに追加
                            
            M_color[y][x] = 'BLACK'


def main():
    '''メイン処理'''
    g_distance = breadth_first_search()
    # 塗りつぶせる'.'の数 = 全ての'.'の数 - ゴールまでの距離 - 1(スタート地点の.)
    if is_debug:
        print(g_distance)
    
    # 2次元配列Mの中の、.の数をカウント
    all_dot = len([s for s in list(itertools.chain.from_iterable(M)) if '.' in s])
    ans = all_dot - g_distance -1
    print(ans)
    
    


if __name__ == "__main__":
    # ファイル実行時に、main()関数を実行
    main()

Submission status: Runtime Error

Solution code:
from collections import deque

H,W = map(int,input().split())
maze = [[] for i in range(H)]
con = 0
inf = 10 ** 9
distance = [[inf] * W for i in range(H)]

for i in range(H):
  m = list(input())
  maze[i] = m
  con += m.count("#")

def bfs(maze, disrance, sh, sw):
  queue = deque([[sh, sw]])
  distance[sh][sw] = 0
  while queue:
    h,w = queue.popleft()
    if h == H - 1 and w == W - 1:
      return distance[h][w]
    for j, k in ([1, 0], [-1, 0], [0, 1], [0, -1]):
      new_h, new_w = h + j, w + k
      if new_h < 0 or new_h >= H or \
        new_w < 0 or new_w >= W:
          continue
      elif maze[new_h][new_w] != "#" and \
        distance[new_h][new_w] > distance[h][w] + 1:
        distance[new_h][new_w] = distance[h][w] + 1

        queue.append([new_h, new_w])
        
minpath = bfs(maze,distance,0,0)

print(H * W - con - minpath - 1)

Submission status: Runtime Error

Solution code:
from collections import deque

H,W = map(int,input().split())
maze = [[] for i in range(H)]
con = 0
inf = 10 ** 9
distance = [[inf] * W for i in range(H)]

for i in range(H):
  m = list(input())
  maze[i] = m
  con += m.count("#")

def bfs(maze, disrance, sh, sw):
  queue = deque([[sh, sw]])
  distance[sh][sw] = 0
  while queue:
    h,w = queue.popleft()

    if h == H - 1 and w == W - 1:
      return distance[h][w] - 1
    for j, k in ([1, 0], [-1, 0], [0, 1], [0, -1]):
      new_h, new_w = h + j, w + k
      if new_h < 0 or new_h >= H or \
        new_w < 0 or new_w >= W:
          continue
      elif maze[new_h][new_w] != "#" and \
        distance[new_h][new_w] == inf:
        distance[new_h][new_w] = distance[h][w] + 1

        queue.append([new_h, new_w])
        
minpath = bfs(maze,distance,0,0)

print(H * W - con - minpath)

Submission status: Runtime Error

Solution code:
from collections import deque
sx, sy = 0, 0
# h, w = 3, 3
# maze_ori = [["..#"],
#                ["#.."],
#                ["..."]]

# maze_ori = [list(i[0]) for i in maze]
h, w = map(int, input().split())
maze = [list(input()) for _ in range(h)]

def bfs():
    visited = [[-1]*w for _ in range(h)]
    queue = deque([[sx, sy]])
    visited[sy][sx] = 0
    while queue:
        y, x = queue.popleft()
        if [y, x] == [h-1,w-1]:
            return visited[y][x]
        
        for dy, dx in ([0,1], [1,0], [0, -1], [-1, 0]):
            ny, nx = y+dy, x+dx
            if 0<=ny<h and 0<=nx<w:
                if maze[ny][nx] == '.' and visited[ny][nx] == -1:
                    visited[ny][nx] = visited[y][x] + 1
                    queue.append([ny, nx])
                    
black_num = 0
for i in maze:
    black_num += i.count("#")

print(h*w - bfs() -1 -black_num)

Submission status: Runtime Error

Solution code:
from collections import deque
sx, sy = 0, 0

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

def bfs():
    visited = [[-1]*w for _ in range(h)]
    queue = deque([[sx, sy]])
    visited[sy][sx] = 0
    while queue:
        y, x = queue.popleft()
        if [y, x] == [h-1,w-1]:
            return visited[y][x]
        
        for dy, dx in ([0,1], [1,0], [0, -1], [-1, 0]):
            ny, nx = y+dy, x+dx
            if 0<=ny<h and 0<=nx<w:
                if maze[ny][nx] == '.' and visited[ny][nx] == -1:
                    visited[ny][nx] = visited[y][x] + 1
                    queue.append([ny, nx])
                    
black_num = 0
for i in maze:
    black_num += i.count("#")

print(h*w - bfs() -1 -black_num)

Submission status: Runtime Error

Solution code:
import collections
INF = 10**18
h,w = map(int,input().split())
li = [list(input()) for i in range(h)]
sx,sy,gx,gy = 0,0,h-1,w-1

def bfs(sy,sx):
    #頂点をINFで初期化
    d = [[INF]*w for i in range(h)]
    #移動４方向のベクトル
    dx = [1,0,-1,0]
    dy = [0,1,0,-1]
    #スタート地点をキューにいれ、頂点を０にする
    que = collections.deque([])
    que.append((sy,sx))
    d[sy][sx] = 0
    #キューが空になるまでループ（行ける要素がなくなるまで）
    while que:
        # キューの先頭を取り出す
        p = que.popleft()
        # 取り出してきた状態がゴールなら探索をやめる
        # 移動4方向をループ
        for i in range(4):
            nx = p[1] + dx[i]
            ny = p[0] + dy[i]

            #壁との判定とすでに訪れたかどうかをチェック
            if 0<=nx and nx < w and 0 <= ny and ny < h:
                if li[ny][nx] != "#" and d[ny][nx] == INF:
                    #移動できる点なのでキューについか
                    que.append((ny,nx))
                    #前の点+1で移動できる
                    d[ny][nx] = d[p[0]][p[1]] + 1
    return d[-1][-1]
a = bfs(0,0)-1
if a + 1 == INF:
    print(-1)
    sys.exit()
maxgrid = h*w
cnt = 0
for i in range(h):
    for j in range(w):
        if li[i][j] == "#":
            cnt+=1
ans = maxgrid - cnt - a -2
print(ans)

Submission status: Runtime Error

Solution code:
H, W = map(int, input().split())

Ss = []
white_count = 0
for i in range(H):
    s = list(input())
    for masu in s:
        if masu == '.':
            white_count += 1
    Ss.append(s)

# print('white_count', white_count)


def search():
    global Ss_hosu
    #global min_hosu
    Ss_hosu[0][0] = 1
    que = [[0, 0]]
    while len(que) > 0:
        x, y = que.pop(0)
        my_value = Ss_hosu[y][x]
        for dx, dy in [[1, 0], [-1, 0], [0, 1], [0, -1]]:
            if 0 <= x + dx <= W - 1 and 0 <= y + dy <= H - 1:
                if Ss[y + dy][x + dx] == '.' and Ss_hosu[y + dy][x + dx] is None:
                    Ss_hosu[y+dy][x+dx] = my_value + 1
                    que.append([x + dx, y + dy])

    # Ss_hosu[y][x] = value
    # if x == W-1 and y == H-1:
    #     min_hosu = value
    # for dx, dy in [[1,0], [-1,0], [0,1], [0,-1]]:
    #     if 0 <= x+dx <= W-1 and 0 <= y+dy <= H-1:
    #         if Ss[y+dy][x+dx] == '.' and Ss_hosu[y+dy][x+dx] is None:
    #             search(x+dx, y+dy, value=value+1)


Ss_hosu = [[None for _ in range(W)] for _ in range(H)]
search()
min_hosu = Ss_hosu[H-1][W-1]

# for s in Ss_hosu:
#     print(s)

# print('min_hosu', min_hosu)

print(white_count - min_hosu)

Submission status: Runtime Error

Solution code:
from collections import deque
def bfs():
  d=[[float("inf")]*m for _ in range(n)]
  dx=[1,0,-1,0]
  dy=[0,1,0,-1]
  
  que=deque([])
  que.append((0,0))
  d[0][0]=0

  while que:
    p = que.popleft()
    if p[0]==n and p[1]==m:
      break
    for i in range(4):
      nx=p[0]+dx[i]
      ny=p[1]+dy[i]
      if 0 <= nx < n and 0 <= ny < m and c[nx][ny] != "#" and d[nx][ny] == float("inf"):
                # 移動できるならキューに入れ、その点の距離を p からの距離 +1 で確定する
                que.append((nx, ny))
                d[nx][ny] = d[p[0]][p[1]] + 1
  return d[gx][gy]

n, m = map(int, input().split())
c = [list(input()) for i in range(n)]

count=0
for i in range(n):
  for j in range(m):
    if c[i][j]=="#":
      count+=1

print(n*m-bfs()-1-count)

Submission status: Runtime Error

Solution code:
import sys

def main(*args, **kwargs):
    # Initialize data
    H, W = map(int, input().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()
    movement = 0

    while len(queue) > 0:
        movement += 1
        for i in range(len(queue)):  # Process same level
            coodinate = queue.popleft()
            visited.add(coodinate)
            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)
    print(-1)
    return
main()

Submission status: Runtime Error

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

Submission status: Runtime Error

Solution code:
from collections import deque
a,b=map(int,input().split())
List=[]
sumup=0
for i in range(a):
  l=list(input())
  p=l.count(".")
  sumup+=p
  List.append(l)
List[0][0]=1
q=deque([[0,0]])
while List[a-1][b-1]==".":
  h,w=q.popleft()
  aaa=[[0,1],[0,-1],[1,0],[-1,0]]
  for x,y in aaa:
    if 0<=h+x<a and 0<=w+y<b:
      if List[h+x][w+y]==".":
        List[h+x][w+y]=List[h][w]+1
        q.append([h+x,w+y])
print(sumup-List[a-1][b-1])

Submission status: Runtime Error

Solution code:
# -*- coding: utf-8 -*-
from collections import Counter
from collections import deque

H,W = list(map(int, input().rstrip().split()))
S_list = [list(input().rstrip()) for i in range(H)]
#-----

def checkRoute(matrix):
    # queue = [ ( (row, column),step ) ]
    # deque = [ ( (int, int   ),int ) ]
    queue = deque([  ( (1,1),1 )  ])

    delta = [(1,0),(-1,0),(0,1),(0,-1)]
    visited = set()
    
    while queue:
        (r,c),step = queue.popleft()
        
        for d in delta:
            next_r = r + d[0]
            next_c = c + d[1]
            
            if (next_r == H) and (next_c == W):
                return step+1
            
            if (1 <= next_r <= H) and (1 <= next_c <= W) and \
               (next_r, next_c) not in visited  and \
               matrix[next_r][next_c] == ".":
            
                queue.append( ( (next_r, next_c), step+1 ) )
                visited.add( (next_r, next_c) )


#-----
# add dummy node(Black area) around the original data
for i in range(len(S_list)):
    S_list[i] = ["#"] + S_list[i][:] + ["#"]
    
S_list = [["#"]*(W+2)] + S_list[:] + [["#"]*(W+2)]
#-----

cnt_dic = Counter( sum(S_list,[]) )
min_step = checkRoute(S_list)
print( cnt_dic["."] - min_step )

Submission status: Runtime Error

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

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

que = [[0, 0]]
distance = 0
while True:
    h, w = que.pop(0)
    if h == H - 1 and w == W - 1:
        distance = dist[h][w]
        break
    for a, b in [[0, 1], [0, -1], [1, 0], [-1, 0]]:
        ht, wt = h + a, w + b
        if 0 <= ht < H and 0 <= wt < W and graph[ht][wt] == "." and dist[ht][wt] == 0:
            dist[ht][wt] = dist[h][w] + 1
            que.append([ht, wt])

total = W * H - 1
for g in graph:
    total -= g.count("#")
print(total - distance)

Submission status: Runtime Error

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

Submission status: Runtime Error

Solution code:
from collections import deque 

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

Submission status: Runtime Error

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

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

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

def dfs(y,x,cnt,H,W,s):
  node_to_visit=search(y,x,H,W,s)
  flag=True
  
  while flag:
    cnt += 1
    tmp=[]
    tmp2=[]
    for next_point in node_to_visit:
      t=next_point[0]
      u=next_point[1]
      if t!= y or u!=x:
        tmp=search(u,t,H,W,s)
      tmp2 += tmp
    node_to_visit=tmp2
    if [H-1,W-1] in node_to_visit:
      white=cnt
      flag=False
      break
      
  ans=H*W-white-black-2
  print(white,black,ans)

  
dfs(0,0,0,H,W,s)

Submission status: Runtime Error

Solution code:
from collections import deque

def bfs():
  queue = deque([[0, 0]])
  visited[0][0] = 0
  while queue:
    y, x = queue.popleft()
    if [y, x] == [h-1, w-1]:
      return visited[y][x]
    for j, k in ([1, 0], [-1, 0], [0, 1], [0, -1]):
      new_y, new_x = y+j, x+k
      if (0 <= new_y < h) and (0 <= new_x < w):
        if maze[new_y][new_x] == "." and visited[new_y][new_x] == -1:
          visited[new_y][new_x] = visited[y][x] + 1
          queue.append([new_y, new_x])
          
h,w = map(int, input().split())

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

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

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

Submission status: Runtime Error

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

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

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

def bfs():
  queue = deque([[0, 0]])
  visited[0][0] = 0
  while queue:
    y, x = queue.popleft()
    if [y, x] == [h-1, w-1]:
      return visited[y][x]
    for j, k in ([1, 0], [-1, 0], [0, 1], [0, -1]):
      new_y, new_x = y+j, x+k
      if 0 <= new_y <= h-1 and 0 <= new_x <= w-1:
        if maze[new_y][new_x] == "." and visited[new_y][new_x] == -1:
          visited[new_y][new_x] = visited[y][x] + 1
          queue.append([new_y, new_x])

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

Submission status: Runtime Error

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

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

Submission status: Runtime Error

Solution code:
from collections import deque
def gridbfs(grid,sy,sx):
    INF = 10**18
 
    gridy = len(grid)
    gridx = len(grid[0])
 
    dist = [[INF]*gridx for _ in range(gridy)]
    dist[sy][sx] = 0
    q = deque([(sy,sx)])
 
    while q:
        y,x = q.popleft()
        for dy,dx in [(-1,0),(1,0),(0,-1),(0,1)]:
            ny,nx = y+dy, x+dx
            if not (0 <= ny < gridy and 0 <= nx < gridx):
                continue
            if grid[ny][nx] == 'X':
                continue
            if dist[ny][nx] != INF:
                continue
            dist[ny][nx] = dist[y][x] + 1
            q.append((ny,nx))
 
    return dist
 
H,W = map(int,input().split())
 
Grid = [input() for _ in range(H)]
 
cnt = 0
 
for i in range(H):
    cnt += Grid[i].count('.')
 
d = gridbfs(Grid,0,0)
 
print(max(-1, cnt - d[H-1][W-1] -1))
from collections import deque
def gridbfs(grid,sy,sx):
    INF = 10**18

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

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

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

    return dist

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

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

cnt = 0

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

d = gridbfs(Grid,0,0)

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

Submission status: Runtime Error

Solution code:
# coding:utf-8

import sys
import math
import time
#import numpy as np
import collections
from collections import deque
from collections import Counter
import queue
import copy
import bisect
import heapq
import itertools

# 幅優先探索(BFS)でスタート座標(x, y)からの最大距離返す
def bfs(SS, x, y, H, W):#入力(座標系(迷路), x, y, xの端, yの端)
  x_next = [0, 0, -1, 1]
  y_next = [1, -1, 0, 0]
  tempx = x
  tempy = y
  mlength = 0
  q = deque()
  xytuple = (x, y, 0)
  q.append(xytuple)


  while q:
    xytuple = q.popleft()
    SS[xytuple[0]][xytuple[1]] = xytuple[2] +1 #探索した場所は探索できないようにする
    for i in range(4): #このforで上下左右を調べてる
      tempx = xytuple[0] + x_next[i]
      tempy = xytuple[1] + y_next[i]
      #print(tempx, tempy, xytuple[2])
      #print(S)
      if(0 <= tempx and tempx < H and 0 <= tempy and tempy < W and SS[tempx][tempy] == "."):
        temptuple = (tempx, tempy, xytuple[2]+1)
        SS[temptuple[0]][temptuple[1]] = xytuple[2] +1 #探索した場所は探索できないようにする
        q.append(temptuple)
      #print(q)
  return mlength


#sys.setrecursionlimit(10**7)
#N, Q = map(int, input().split())
#G = [list(input()) for i in range(H)]
#INF = V * 10001
#A = [int(i) for i in input().split()]
#AB = [list(map(int, input().split())) for _ in range(K)]

H,W = map(int,input().split())
S = [list(map(str, input())) for i in range(H)]
ans = 0
n = 0

#print(S)

for i in range(H):
    for j in range(W):
        if(S[i][j]=="."):
            n += 1
#print(n)
bfs(S,0,0,H,W)
#print(S)
ans = n - S[H-1][W-1]

if(type(S[H-2][W-2]) is str and type(S[H-2][W-1]) is str and type(S[H-1][W-2]) is str):
    ans = -1



print(ans)

Submission status: Runtime Error

Solution code:
H,W=map(int,input().split())
G=[input() for i in range(H)]
F=[[0]*W for i in range(H)]

def judge(p0,p1,res):
  F[p0][p1]=1
  if p0==H-1 and p1==W-1:
    return res
  
  a=float("inf")
  if p0<H-1 and F[p0+1][p1]==0 and G[p0+1][p1]==".":
    m=judge(p0+1,p1,res+1)
    if m!=False:
      a=min(a,m)
  
  if p1<W-1 and F[p0][p1+1]==0 and G[p0][p1+1]==".":
    m=judge(p0,p1+1,res+1)
    if m!=False:
      a=min(a,m)
      
  if p0>0 and F[p0-1][p1]==0 and G[p0-1][p1]==".":
    m=judge(p0-1,p1,res+1)
    if m!=False:
      a=min(a,m)
   
  if p1>0 and F[p0][p1-1]==0 and G[p0][p1-1]==".":
    m=judge(p0,p1-1,res+1)
    if m!=False:
      a=min(a,m)
    
  if a!=float("inf"):
    return a
    
  return False
k=judge(0,0,0)
if k!=False:
  ans=W*H-(k+1)
  for i in range(H):
    ans-=G[i].count("#")
  print(ans)
else:
  print(-1)

Submission status: Runtime Error

Solution code:
H,W=map(int,input().split())
G=[input() for i in range(H)]
F=[[0]*W for i in range(H)]

def judge(p0,p1,res):
  if p0==H-1 and p1==W-1:
    return res
  
  a=float("inf")
  if p0<H-1 and F[p0+1][p1]==0 and G[p0+1][p1]==".":
    F[p0+1][p1]=1
    m=judge(p0+1,p1,res+1)
    if m!=False:
      a=min(a,m)
  
  if p1<W-1 and F[p0][p1+1]==0 and G[p0][p1+1]==".":
    F[p0][p1+1]=1
    m=judge(p0,p1+1,res+1)
    if m!=False:
      a=min(a,m)
      
  if p0>0 and F[p0-1][p1]==0 and G[p0-1][p1]==".":
    F[p0-1][p1]=1
    m=judge(p0-1,p1,res+1)
    if m!=False:
      a=min(a,m)
   
  if p1>0 and F[p0][p1-1]==0 and G[p0][p1-1]==".":
    F[p0][p1-1]=1
    m=judge(p0,p1-1,res+1)
    if m!=False:
      a=min(a,m)
    
  if a!=float("inf"):
    return a
    
  return False
k=judge(0,0,0)
if k!=False:
  ans=W*H-(k+1)
  for i in range(H):
    ans-=G[i].count("#")
  print(ans)
else:
  print(-1)

Submission status: Runtime Error

Solution code:
H,W=map(int,input().split())
G=[input() for i in range(H)]
F=[[0]*W for i in range(H)]

def judge(p0,p1,res):
  if p0==H-1 and p1==W-1:
    return res
  
  a=float("inf")
  if p0<H-1 and F[p0+1][p1]==0 and G[p0+1][p1]==".":
    F[p0+1][p1]=1
    m=judge(p0+1,p1,res+1)
    if m!=False:
      a=min(a,m)
  
  if p1<W-1 and F[p0][p1+1]==0 and G[p0][p1+1]==".":
    F[p0][p1+1]=1
    m=judge(p0,p1+1,res+1)
    if m!=False:
      a=min(a,m)
      
  if p0>0 and F[p0-1][p1]==0 and G[p0-1][p1]==".":
    F[p0-1][p1]=1
    m=judge(p0-1,p1,res+1)
    if m!=False:
      a=min(a,m)
   
  if p1>0 and F[p0][p1-1]==0 and G[p0][p1-1]==".":
    F[p0][p1-1]=1
    m=judge(p0,p1-1,res+1)
    if m!=False:
      a=min(a,m)
    
  if a!=float("inf"):
    return a
    
  return False
k=judge(0,0,0)
if k:
  ans=W*H-(k+1)
  for i in range(H):
    ans-=G[i].count("#")
  print(ans)
else:
  print(-1)

Submission status: Runtime Error

Solution code:
from collections import deque

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

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

cnt = 1

for i in range(H):
    cnt += maze[i].count("#")

if d[H-1][W-1] == float("inf"):
    print(-1)
else:
    print(H*W-bfs()-cnt)

Submission status: Runtime Error

Solution code:
import sys
from collections import deque

readline = sys.stdin.readline
H, W = map(int, readline().split())
S = [['#'] * (W+2)] + [['#'] + list(readline().rstrip()) + ['#'] for _ in range(H)] + [['#'] * (W+2)] 
black = sum(row.count('#') for row in S) - 2*(W+2) - 2*H

# bfs
q = deque([(1, 1)])
S[1][1] = 1
direction = ((0, 1), (1, 0), (0, -1), (-1, 0))
while q:
    x, y = q.popleft()
    d = S[x][y]
    for dx, dy in direction:
        # print(x+dx, y+dy, S[x+dx][y+dy])
        if S[x+dx][y+dy] == '.':
            S[x+dx][y+dy] = d + 1
            q.append((x+dx, y+dy))
ans = -1
if S[H][W] != '#':
    ans = H*W - S[H][W] - black
print(ans)