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 collections import deque

def make_wall(maze,h,w):
    maze=deque(maze)
    for i in range(h):
        maze[i]="#"+maze[i]+"#"
    maze.appendleft("#"*(w+2))
    maze.append("#"*(w+2))
    return list(maze)

def bfs(maze, visited, sy, sx, gy, gx):
    queue = deque([[sy, sx]])
    visited[sy][sx] = 0
    while queue:
        y, x = queue.popleft()
        if [y, x] == [gy, gx]:
            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 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=[input() for _ in range(h)]
kabe=0
for i in range(h):
    kabe+=maze[i].count("#")
maze=make_wall(maze,h,w)
visited=[[-1]*(w+2) for _ in range(h+2)]
sy,sx=1,1
gy,gx=h,w
d=1+bfs(maze, visited, sy, sx, gy, gx)
print(h*w-kabe-d)

Submission status: Runtime Error

Solution code:
from collections import deque

def bfs():
    d = [[float("inf")] * w for _ in range(h)]

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

    que = deque([])
    que.append((sx, sy))
    d[sx][sy] = 0

    while que:
        p = que.popleft()
        if p[0] == gx and p[1] == gy:
            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[nx][ny] != "#" and d[nx][ny] == float("inf"):
                que.append((nx, ny))
                d[nx][ny] = d[p[0]][p[1]] + 1
    
    return d[gx][gy]

h, w = map(int, input().split())
maze = [list(input()) for _ in range(h)]
sx, sy = 0, 0
gx, gy = h-1, w-1

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

res = bfs()

if 0 < res < float("inf"):
    print(white-res-1)
else:
    print(-1)

Submission status: Runtime Error

Solution code:
from collections import deque

def bfs():
    d = [[float("inf")] * w for _ in range(h)]

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

    que = deque([])
    que.append((sx,sy))
    d[sx][sy] = 0

    while que:
        p = que.popleft()
        if p[0] == gx and p[1] == gy:
            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[nx][ny] != "#" and d[nx][ny] == float("inf"):
                que.append((nx,ny))
                d[nx][ny] = d[p[0]][p[1]] + 1
    
    return d[gy][gx]

h, w = map(int, input().split())
maze = [list(input()) for _ in range(h)]
sx, sy = 0, 0
gx, gy = h-1, w-1

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

res = bfs()

if 0 < res < float("inf"):
    print(white-res-1)
else:
    print(-1)

Submission status: Runtime Error

Solution code:
import math
import copy
import sys
import fractions
# import numpy as np
# import statistics
import decimal
import heapq
import collections
import itertools
import bisect

# from operator import mul

sys.setrecursionlimit(100001)


# input = sys.stdin.readline
# sys.setrecursionlimit(10**6)

# ===FUNCTION===

def getInputIntList():
    outputDataList = []
    inputData = input().split()
    outputDataList = [int(n) for n in inputData]

    return outputDataList


def getSomeInputInt(n):
    outputDataList = []
    for i in range(n):
        inputData = int(input())
        outputDataList.append(inputData)

    return outputDataList


def getSomeInputListInt(n):
    inputDataList = []
    outputDataList = []
    for i in range(n):
        inputData = input().split()
        inputDataList = [int(n) for n in inputData]
        outputDataList.append(inputDataList)

    return outputDataList


# ===CODE===

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

table = [[1 for _ in range(w)] for _ in range(h)]
d_table = [[-1 for _ in range(w)] for _ in range(h)]

for i in range(h):
    s = input()
    tmp = list(s)
    for j, ts in enumerate(tmp):
        if ts == ".":
            table[i][j] = 0

ans = -1
search_table = [[-1, 0], [1, 0], [0, -1], [0, 1]]

q = collections.deque([])
q.append([0,0])
table[0][0]=1
d_table[0][0]=0

gy, gx = [h-1, w-1]

while len(q) > 0:
    qy, qx = q.popleft()

    for y, x in search_table:
        cy = qy + y
        cx = qx + x

        if cy < 0 or cy > h - 1 or cx < 0 or cx > w - 1:
            continue

        if table[cy][cx] == 0 and d_table[cy][cx] == -1:
            table[cy][cx] = 1
            d_table[cy][cx] = d_table[qy][qx] + 1
            q.append([cy, cx])

            if cy == gy and cx == gx:
                ans = d_table[cy][cx]

if ans == -1:
    print(-1)
    exit(0)

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

for i in range(h):
    for j in range(w):
        tmp = d_table[i][j]
        if tmp > -1
            cnt[tmp]+=1

res = 0
for c in cnt:
    res += max(0, c)
print(res)

Submission status: Runtime Error

Solution code:
IN = iter(Input.split('\n')).__next__
def input():
    return IN()

# 入力
from collections import deque
h, w = map(int, input().split())
c = []
for _ in range(h):
    c.append(input())

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

d = [[-1]*w for _ in range(h)]
d[0][0] = 1
que = deque([[0, 0]])
while que:
    x, y = que.popleft()
    for i, j in [[1,0],[0,1],[-1,0],[0,-1]]:
        nx, ny = x+i, y+j
        if 0<=nx<w and 0<=ny<h and c[ny][nx]=="." and d[ny][nx]==-1:
            d[ny][nx] = d[y][x]+1
            que.append([nx, ny])
if d[h-1][w-1] == -1:
    print(-1)
else:
    print(ans-d[h-1][w-1])

Submission status: Runtime Error

Solution code:
from functools import reduce
from fractions import gcd
import heapq
import queue
import math
import bisect
import itertools
import sys
sys.setrecursionlimit(10**7)
input = sys.stdin.readline
INF = float("inf")


def main():
    H, W = map(int, input().split())
    G = []
    for _ in range(H):
        G.append(list(input()[:-1]))
    
    C = [[INF] * W for _ in range(H)]
    C[0][0] = 1
    cnt = 0
    for i in range(H):
        for j in range(W):
            if G[i][j] == "#":
                cnt += 1
                continue
            if i + 1 < H:
                C[i+1][j] = min(C[i+1][j], C[i][j] + 1)
            if j + 1 < W:
                C[i][j+1] = min(C[i][j+1], C[i][j] + 1)

    if C[H-1][W-1] == INF or G[H-1][G-1] == "#":
        print(-1)
    else:
        print(H * W - (C[H-1][W-1] + cnt))


if __name__ == '__main__':
    main()

Submission status: Runtime Error

Solution code:
from collections import deque
H,W=map(int,input().split(' '))
S=[list(input()) for i in range(H)]
S[0][0]=1
next  = deque([[0,0]])
ans = H*W
while next:
    x,y =next.popleft()
    s = S[x][y]
    for i,j in [[1,0],[0,1],[-1,0],[0,-1]]:
        if 0<=x+i<H and 0<=y+j<W and S[x+i][y+j]=='.':
            S[x+i][y+j]=s+1
            next.append([x+i,y+j])
for i in S:
    ans -=i.count('#')
print(ans-S[H-1][W-1])

Submission status: Runtime Error

Solution code:
from collections import deque
h,w=map(int,input().split())
s=[ input() for _ in range(h)]
dist=[ [float('inf') for _ in range(w)] for _ in range(h)]
#print(s)
#do a bfs 
dq=deque()
dist[0][0]=0
dq.append([0,0])
white=0
for i in s:
    white+=i.count('.')
#print(white)
while dq!=[]:
    xx,yy=dq.popleft()
    if xx==h-1 and yy==w-1:
        break
    for i,j in zip([-1,0,1,0], [0,1,0,-1]):
            x=xx+i
            y=yy+j
            def valid(x,y):
                if not(x>=0 and x<h and y>=0 and y<w):
                    return False
                if s[x][y]=='.':
                    return True
                else:
                    return False
            if valid(x,y):
                if dist[x][y]>dist[xx][yy]+1:
                    dist[x][y]=1+dist[xx][yy]
                    dq.append([x,y])
#print(dist[h-1][w-1])
if dist[h-1][w-1]!=float('inf'):
    print(white-1-dist[h-1][w-1])
else:
    print(-1)

Submission status: Runtime Error

Solution code:
from collections import deque
h,w=map(int,input().split())
s=[ input() for _ in range(h)]
dist=[ [float('inf') for _ in range(w)] for _ in range(h)]
#print(s)
#do a bfs 
dq=deque()
dist[0][0]=0
dq.append([0,0])
white=0
for i in s:
    white+=i.count('.')
#print(white)
while dq!=[]:
    xx,yy=dq.popleft()
    if xx==h-1 and yy==w-1:
        break
    for i,j in zip([-1,0,1,0], [0,1,0,-1]):
            x=xx+i
            y=yy+j
            def valid(x,y):
                if x>=0 and x<h and y>=0 and y<w and s[x][y]=='.':
                    return True
                return False
            if valid(x,y):
                if dist[x][y]>dist[xx][yy]+1:
                    dist[x][y]=1+dist[xx][yy]
                    dq.append([x,y])
#print(dist[h-1][w-1])
if dist[h-1][w-1]!=float('inf'):
    print(white-1-dist[h-1][w-1])
else:
    print(-1)

Submission status: Runtime Error

Solution code:
def calc_distance(maze):
    sx,sy,gx,gy = 0,0,w-1,h-1
    #maze = maze.split()
    INF = 10000000000
    field_x_length = w
    field_y_length = h
        
    distance = []
    for i in range(field_y_length):
        distance.append([])
        for j in range(field_x_length):
            distance[i].append(INF)
        
    queue = []
    queue.insert(0, (sy,sx))
    distance[sy][sx] = 0
        
    while True:
        y, x = queue.pop()
        if(x == gx and y == gy):
            break
                
        for i in range(0,4):
            nx, ny = x +[1,0,-1,0][i], y +[0,1,0,-1][i]
                
            if(0 <= nx and nx < field_x_length and 0 <= ny and ny < field_y_length and maze[ny][nx] != '#' and distance[ny][nx] == INF):
                queue.insert(0,(ny, nx))
                distance[ny][nx] = distance[y][x] + 1
    return distance[gy][gx]
    
h,w = map(int, input().split())
maze = [input() for _ in range(h)]

import collections
count = 0
for i in range(0,h):
    c = collections.Counter(maze[i])
    count += c["#"]


print(w*h - count - calc_distance(maze) -1)

Submission status: Runtime Error

Solution code:
from collections import deque
import sys
sys.setrecursionlimit(10 ** 6)
def input():
    return sys.stdin.readline()[:-1]

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

ans = 10**9

visited_list = [[10**9]*W for _ in range(H)]
stack = deque([[0, 0, 0]])
visited_list[0][0] = 0

w_cnt=0
for c in C: w_cnt += c.count(".")

def seek(, visited_list, stack):
    global ans
    flag = 0
    while len(stack) > 0:
        h, w, cnt = stack.pop()
        if h == H-1 and w == W-1 and ans > cnt:
            ans = cnt
            flag = 1
            continue
        for j, k in ([1, 0], [0, 1], [-1, 0], [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
            if  [new_h][new_w] != "#" and visited_list[new_h][new_w] > cnt + 1:
                visited_list[new_h][new_w] = cnt + 1
                stack.append([new_h, new_w, cnt+1])
    if flag: 
        ans = w_cnt-(ans+1)
        return ans
    else: return -1

print(seek(C, visited_list, stack))

Submission status: Runtime Error

Solution code:
H, W = map(int, input().split())
s=[]
for row in range(H):
    s.append(input())
#print(s)



waiting=[]
dx=[1,0,-1,0]
dy=[0,1,0,-1]
def func(xy):
    x, y = xy
    for i in range(4):
        if 0<=y+dy[i]<H and 0<=x+dx[i]<W:
            if walker[y+dy[i]][x+dx[i]] == None and s[y+dy[i]][x+dx[i]]=='.':
                walker[y + dy[i]][x + dx[i]]=walker[y][x]+1
                waiting.append((x+dx[i], y+dy[i]))
    if waiting:
        func(waiting.pop(0))
    else:
        return None

walker=[]
for row in range(H):
    walker.append([None]*W)
#print(walker)
walker[0][0]=0
func((0,0))
#print(walker)
if walker[H-1][W-1] != None:
    minimum=walker[H-1][W-1]

    white_count=0
    for row in range(H):
        white_count += s[row].count('.')
    #print(white_count)
    print(white_count-minimum-1)
else:
    print(-1)

Submission status: Runtime Error

Solution code:
H, W = map(int, input().split())
s=[]
for row in range(H):
    s.append(input())
#print(s)



waiting=[]
dx=[1,0,-1,0]
dy=[0,1,0,-1]
def func(xy):
    x, y = xy
    for i in range(4):
        if 0<=y+dy[i]<H and 0<=x+dx[i]<W:
            if walker[y+dy[i]][x+dx[i]] == None and s[y+dy[i]][x+dx[i]]=='.':
                walker[y + dy[i]][x + dx[i]]=walker[y][x]+1
                waiting.append((x+dx[i], y+dy[i]))
    if waiting:
        func(waiting.pop(0))
    else:
        return None

walker=[]
for row in range(H):
    walker.append([None]*W)
#print(walker)
walker[0][0]=0
func((0,0))
#print(walker)
minimum=walker[H-1][W-1]

white_count=0
for row in range(H):
    white_count += s[row].count('.')
#print(white_count)
print(white_count-minimum-1)

Submission status: Runtime Error

Solution code:
import sys
#大きすぎるとダメ
h,w=map(int,input().split())
sys.setrecursionlimit(h*w+1)
s=[list(input()) for i in range(h)]
inf=1000000000000000
d=[[inf]*w for i in range(h)]


def dfs(i,j):
    global h,w,s
    nex=[(0,-1),(0,1),(-1,0),(1,0)]
    for k in range(4):
        l,m=i+nex[k][0],j+nex[k][1]
        if 0<=i+nex[k][0]<h and 0<=j+nex[k][1]<w:
            if s[l][m]=="." and d[l][m]>d[i][j]+1:
                d[l][m]=d[i][j]+1
                dfs(l,m)
d[0][0]=0
dfs(0,0)
ans=0
for i in range(h):
    for j in range(w):
        if s[i][j]==".":
            ans+=1
if d[h-1][w-1]==inf:
    print(-1)
else:
    print(ans-d[h-1][w-1]-1)

Submission status: Runtime Error

Solution code:
import sys
#大きすぎるとダメ
sys.setrecursionlimit(2502)
h,w=map(int,input().split())
s=[list(input()) for i in range(h)]
inf=1000000000000000
d=[[inf]*w for i in range(h)]


def dfs(i,j):
    global h,w,s
    nex=[(0,-1),(0,1),(-1,0),(1,0)]
    for k in range(4):
        l,m=i+nex[k][0],j+nex[k][1]
        if 0<=i+nex[k][0]<h and 0<=j+nex[k][1]<w:
            if s[l][m]=="." and d[l][m]>d[i][j]+1:
                d[l][m]=d[i][j]+1
                dfs(l,m)
d[0][0]=0
dfs(0,0)
ans=0
for i in range(h):
    for j in range(w):
        if s[i][j]==".":
            ans+=1
if d[h-1][w-1]==inf:
    print(-1)
else:
    print(ans-d[h-1][w-1]-1)

Submission status: Runtime Error

Solution code:
import sys
#大きすぎるとダメ
sys.setrecursionlimit(2501)
h,w=map(int,input().split())
s=[list(input()) for i in range(h)]
inf=1000000000000000
d=[[inf]*w for i in range(h)]


def dfs(i,j):
    global h,w,s
    nex=[(0,-1),(0,1),(-1,0),(1,0)]
    for k in range(4):
        l,m=i+nex[k][0],j+nex[k][1]
        if 0<=i+nex[k][0]<h and 0<=j+nex[k][1]<w:
            if s[l][m]=="." and d[l][m]>d[i][j]+1:
                d[l][m]=d[i][j]+1
                dfs(l,m)
d[0][0]=0
dfs(0,0)
ans=0
for i in range(h):
    for j in range(w):
        if s[i][j]==".":
            ans+=1
if d[h-1][w-1]==inf:
    print(-1)
else:
    print(ans-d[h-1][w-1]-1)

Submission status: Runtime Error

Solution code:
import sys
#大きすぎるとダメ
sys.setrecursionlimit(2000)
h,w=map(int,input().split())
s=[list(input()) for i in range(h)]
inf=1000000000000000
d=[[inf]*w for i in range(h)]


def dfs(i,j):
    global h,w,s
    nex=[(0,-1),(0,1),(-1,0),(1,0)]
    for k in range(4):
        l,m=i+nex[k][0],j+nex[k][1]
        if 0<=i+nex[k][0]<h and 0<=j+nex[k][1]<w:
            if s[l][m]=="." and d[l][m]>d[i][j]+1:
                d[l][m]=d[i][j]+1
                dfs(l,m)
d[0][0]=0
dfs(0,0)
ans=0
for i in range(h):
    for j in range(w):
        if s[i][j]==".":
            ans+=1
if d[h-1][w-1]==inf:
    print(-1)
else:
    print(ans-d[h-1][w-1]-1)

Submission status: Runtime Error

Solution code:
import sys
#大きすぎるとダメ
sys.setrecursionlimit(1000)
h,w=map(int,input().split())
s=[list(input()) for i in range(h)]
inf=1000000000000000
d=[[inf]*w for i in range(h)]


def dfs(i,j):
    global h,w,s
    nex=[(0,-1),(0,1),(-1,0),(1,0)]
    for k in range(4):
        l,m=i+nex[k][0],j+nex[k][1]
        if 0<=i+nex[k][0]<h and 0<=j+nex[k][1]<w:
            if s[l][m]=="." and d[l][m]>d[i][j]+1:
                d[l][m]=d[i][j]+1
                dfs(l,m)
d[0][0]=0
dfs(0,0)
ans=0
for i in range(h):
    for j in range(w):
        if s[i][j]==".":
            ans+=1
if d[h-1][w-1]==inf:
    print(-1)
else:
    print(ans-d[h-1][w-1]-1)

Submission status: Runtime Error

Solution code:
import sys
sys.setrecursionlimit(10000000000)
h,w=map(int,input().split())
s=[list(input()) for i in range(h)]
inf=1000000000000000
d=[[inf]*w for i in range(h)]


def dfs(i,j):
    global h,w,s
    nex=[(0,-1),(0,1),(-1,0),(1,0)]
    for k in range(4):
        l,m=i+nex[k][0],j+nex[k][1]
        if 0<=i+nex[k][0]<h and 0<=j+nex[k][1]<w:
            if s[l][m]=="." and d[l][m]>d[i][j]+1:
                d[l][m]=d[i][j]+1
                dfs(l,m)
d[0][0]=0
dfs(0,0)
ans=0
for i in range(h):
    for j in range(w):
        if s[i][j]==".":
            ans+=1

print(ans-d[h-1][w-1]-1)

Submission status: Runtime Error

Solution code:
if field[0][0] == '#':
    print(-1)
elif dist[(H - 1, W - 1)] == -1:
    print(-1)
else:
    steps_min = dist[(H - 1, W - 1)] + 1
    n_white = W * H - n_black
    ans = n_white - steps_min
    print(ans)

Submission status: Runtime Error

Solution code:
from collections import deque

import numpy as np
import sys
#input = sys.stdin.readline

sys.setrecursionlimit(5000)

def bfs(point, field, target, H, W):
    visited = [[-1 for _ in range(W+2)] for _ in range(H+2)]
    visited[point[0]][point[1]] = 1
    que = deque()
    que.append(point)

    while True:
        v = que.popleft()
        depth = visited[v[0]][v[1]]
        for a in [(v[0]-1, v[1]), (v[0]+1, v[1]), (v[0], v[1]-1), (v[0], v[1]+1)]:
            if field[a[0]][a[1]] == 0 and visited[a[0]][a[1]] == -1:
                visited[a[0]][a[1]] = 1 + depth
                if a == target:
                    return visited[a[0]][a[1]]
                else:
                    que.append(a)
        if len(que) == 0:
            return 0

def main()
    H, W = list(map(int, input().split()))
    target = (H, W)
    field = [[-1] * (W+2)]
    number_of_whites = 0
    for _ in range(H):
        s = input()
        number_of_whites += s.count('.')
        field.append([-1] + [0 if c=='.' else -1 for c in s] + [-1])
    field += [[-1] * (W+2)]

    shortest_path = bfs((1, 1), field, target, H, W)
    if shortest_path > 0:
        print(number_of_whites - shortest_path)
    else:
        print(-1)
        
if __name__ == '__main__':
    main()

Submission status: Runtime Error

Solution code:
    H, W = list(map(int, input().split()))
    M = [[-1]*(W+2)]
    ans = 0
    for _ in range(H):
        s = input()
        ans += s.count('.')
        M.append([-1]+[0 if c=='.' else -1 for c in s]+[-1])
    M += [[-1]*(W+2)]
     
    queue = [(1,1)]
    M[1][1] = 1
    dr = [(+1,0),(-1,0),(0,+1),(0,-1)]
    turn = 1
    while len(queue)>0:
        turn += 1
        queue_new = []
        for qx, qy in queue:
            for dx, dy in dr:
                x, y = qx+dx, qy+dy
                if M[y][x]==0:
                    M[y][x] = turn
                    queue_new.append((x,y))
        queue = queue_new
     
    print(ans-M[H][W] if M[H][W]>0 else -1)

Submission status: Runtime Error

Solution code:
H, W = list(map(int, input().split()))
M = [[-1]*(W+2)]
ans = 0
for _ in range(H):
  s = input()
  ans += s.count('.')
  M.append([-1]+[0 if c=='.' else -1 for c in s]+[-1])
  M += [[-1]*(W+2)]

  queue = [(1,1)]
  M[1][1] = 1
  dr = [(+1,0),(-1,0),(0,+1),(0,-1)]
  turn = 1
  while len(queue)>0:
    turn += 1
    queue_new = []
    for qx, qy in queue:
      for dx, dy in dr:
        x, y = qx+dx, qy+dy
        if M[y][x]==0:
          M[y][x] = turn
          queue_new.append((x,y))
          queue = queue_new

          print(ans-M[H][W] if M[H][W]>0 else -1)

Submission status: Runtime Error

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

sys.setrecursionlimit(5000)

def get_adj_tiles(v):
    i, j = v
    res = [(i-1, j), (i+1, j), (i, j-1), (i, j+1)]
    return res

def bfs(point):
    visited = []
    que = deque()
    que.append((point, 1))
    
    while True:
        v, depth = que.popleft()
        visited.append(v)
        adjs = get_adj_tiles(v)
        for a in adjs:
            if field[a[0]][a[1]] == '.' and a not in visited:
                if a == (H, W):
                    return depth + 1
                else:
                    que.append((a, depth+1))
        if len(que) == 0:
            return 0

def main():
    H, W = list(map(int, input().split()))
    field = [['#'] * (W + 2) for _ in range(H + 2)]
    for i in range(H):
        values = list(input())
        field[i+1][1:-1] = values

    number_of_whites = 0
    for i in range(H+2):
        for j in range(W+2):
            if field[i][j] == '.':
                number_of_whites += 1
    shortest_path = bfs((1, 1))
    if shortest_path > 0:
        print(number_of_whites - shortest_path)
    else:
        print(-1)
        
if __name__ == '__main__':
    main()

Submission status: Runtime Error

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

sys.setrecursionlimit(5000)

def get_adj_tiles(v):
  i, j = v
  res = [(i-1, j), (i+1, j), (i, j-1), (i, j+1)]
  return res

def bfs(point):
  visited = []
  que = deque()
  que.append((point, 1))

  while len(que) > 0:
    v, depth = que.popleft()
    visited.append(v)
    adjs = get_adj_tiles(v)
    for a in adjs:
      if field[a[0]][a[1]] == '.' and a not in visited:
        if a == (H, W):
          return depth + 1
        else:
          que.append((a, depth+1))
          if len(que) == 0:
            return 0

          H, W = list(map(int, input().split()))
          field = [['#'] * (W + 2) for _ in range(H + 2)]
          for i in range(H):
            values = list(input())
            field[i+1][1:-1] = values

            number_of_whites = 0
            for i in range(H+2):
              for j in range(W+2):
                if field[i][j] == '.':
                  number_of_whites += 1
                  shortest_path = bfs((1, 1))
                  if shortest_path > 0:
                    print(number_of_whites - shortest_path)
                    else:
                      print(-1)

Submission status: Runtime Error

Solution code:
from collections import deque

import numpy as np
import sys
#input = sys.stdin.readline

sys.setrecursionlimit(5000)

def get_adj_tiles(v):
  i, j = v
  res = [(i-1, j), (i+1, j), (i, j-1), (i, j+1)]
  return res

def bfs(point):
  visited = []
  que = deque()
  que.append((point, 1))

  while len(que) > 0:
    v, depth = que.popleft()
    visited.append(v)
    adjs = get_adj_tiles(v)
    for a in adjs:
      if field[a[0]][a[1]] == '.' and a not in visited:
        if a == (H, W):
          return depth + 1
        else:
          que.append((a, depth+1))
          if len(que) == 0:
            return 0

          H, W = list(map(int, input().split()))
          field = [['#'] * (W + 2) for _ in range(H + 2)]
          for i in range(H):
            values = list(input())
            field[i+1][1:-1] = values

            number_of_whites = 0
            for i in range(H+2):
              for j in range(W+2):
                if field[i][j] == '.':
                  number_of_whites += 1
                  shortest_path = bfs((1, 1))
                  if shortest_path > 0:
                    print(number_of_whites - shortest_path)
                    else:
                      print(-1)

Submission status: Runtime Error

Solution code:
from collections import deque

import numpy as np
import sys
#input = sys.stdin.readline

sys.setrecursionlimit(5000)

def get_adj_tiles(v):
    i, j = v
    res = [(i-1, j), (i+1, j), (i, j-1), (i, j+1)]
    return res

def bfs(point):
    visited = []
    que = deque()
    que.append((point, 1))
    
    while True:
        v, depth = que.popleft()
        visited.append(v)
        adjs = get_adj_tiles(v)
        for a in adjs:
            if field[a[0]][a[1]] == '.' and a not in visited:
                if a == (H, W):
                    return depth + 1
                else:
                    que.append((a, depth+1))
        if len(que) == 0:
            return 0

H, W = list(map(int, input().split()))
field = [['#'] * (W + 2) for _ in range(H + 2)]
for i in range(H):
    values = list(input())
    field[i+1][1:-1] = values
    
number_of_whites = 0
for i in range(H+2):
    for j in range(W+2):
        if field[i][j] == '.':
            number_of_whites += 1
shortest_path = bfs((1, 1))
if shortest_path > 0:
    print(number_of_whites - shortest_path)
else:
    print(-1)

Submission status: Runtime Error

Solution code:
from collections import deque

def bfs():
    d = [[inf]*(w+1) for _ in range(h+1)]
    que = deque()
    que.append((0,0))
    d[0][0] = 0

    while que:
        cx,cy = que.popleft()
        if cx == w and cy == h:
            break
        for dx,dy in [[1,0],[-1,0],[0,1],[0,-1]]:
            nx, ny = cx+dx, cy+dy
            if 0 <= nx <= w and 0 <= ny <= h and s[nx][ny] != "#" and d[nx][ny] == inf:
                que.append((nx,ny))
                d[nx][ny] = d[cx][cy] + 1
    return d[w][h]

h,w = map(int,input().split())
s = [list(input()) for _ in range(h)]
inf = float("inf")
h,w = h-1,w-1
cnt = bfs()
dot = 0
for i in s:
    dot += i.count(".")
if 0 < cnt < inf:
  print(dot-cnt-1)
else:
  print(-1)

Submission status: Runtime Error

Solution code:
from collections import deque

def bfs():
    d = [[inf]*(w+1) for _ in range(h+1)]
    que = deque()
    que.append((0,0))
    d[0][0] = 0

    while que:
        cx,cy = que.popleft()
        if cx == w and cy == h:
            break
        for dx,dy in [[1,0],[-1,0],[0,1],[0,-1]]:
            nx, ny = cx+dx, cy+dy
            if 0 <= nx <= w and 0 <= ny <= h and s[nx][ny] != "#" and d[nx][ny] == inf:
                que.append((nx,ny))
                d[nx][ny] = d[cx][cy] + 1
    return d[w][h]

h,w = map(int,input().split())
s = [list(input()) for _ in range(h)]
inf = float("inf")
h,w = h-1,w-1
cnt = bfs()
sharp = 0
for i in s:
    sharp += i.count("#")
print((h+1)*(w+1)-sharp-cnt)

Submission status: Runtime Error

Solution code:
from collections import deque

import numpy as np
import sys
#input = sys.stdin.readline

def get_adj_tiles(v):
    i, j = v
    res = [(i-1, j), (i+1, j), (i, j-1), (i, j+1)]
    return res

def bfs(point):
    visited = []
    que = deque()
    que.append((point, 1))
    
    while len(que) > 0:
        v, depth = que.popleft()
        visited.append(v)
        adjs = get_adj_tiles(v)
        for a in adjs:
            if field[a[0]][a[1]] == '.' and a not in visited:
                if a == (H, W):
                    return depth + 1
                else:
                    que.append((a, depth+1))

H, W = list(map(int, input().split()))
field = [['#'] * (W + 2) for _ in range(H + 2)]
for i in range(H):
    values = list(input())
    field[i+1][1:-1] = values
    
number_of_whites = 0
for i in range(H+2):
    for j in range(W+2):
        if field[i][j] == '.':
            number_of_whites += 1
shortest_path = bfs((1, 1))
print(number_of_whites - shortest_path)

Submission status: Runtime Error

Solution code:
import numpy as np
import sys
#input = sys.stdin.readline

def get_adj_tiles(v):
    i, j = v
    res = [(i-1, j), (i+1, j), (i, j-1), (i, j+1)]
    return res

def bfs(point):
    visited = []
    que = deque()
    que.append((point, 1))
    
    while len(que) > 0:
        v, depth = que.popleft()
        visited.append(v)
        adjs = get_adj_tiles(v)
        for a in adjs:
            if field[a[0]][a[1]] == '.' and a not in visited:
                if a == (H, W):
                    return depth + 1
                else:
                    que.append((a, depth+1))

H, W = list(map(int, input().split()))
field = [['#'] * (W + 2) for _ in range(H + 2)]
for i in range(H):
    values = list(input())
    field[i+1][1:-1] = values
    
shortest_path = bfs((1, 1))
print(number_of_whites - shortest_path)

Submission status: Runtime Error

Solution code:
rom collections import deque
def bfs():
    #sからそのマスまでの最短距離を保存する配列
    d = [[float("inf")]*m for _ in range(n)]
    dx = [1,0,-1,0]
    dy = [0,1,0,-1]
    #s,gの座標を得る
    sx,sy = 0,0
    gx,gy = n-1,m-1
    #キューにs座標をセットしてsのマスを0にする
    q = deque([])
    q.append((sx,sy))
    d[sx][sy] = 0
    
    #全部の行けるところをqueに入れてsからの距離を＋1ずつしていく
    while q:
        p = q.popleft()
        #gでbreakしなければ行ける全てのマスまでの最短距離を求める事になる
        if p[0] == gx and p[1] == gy:
            break
        #上下左右のマスを調べる
        for k in range(4):
            xi,yi = p[0]+dx[k],p[1]+dy[k]
            #そのマスにいけて行ったことないなら、そこを起点に再起＋そこまでの距離を求める
            if 0 <= xi < n and 0 <= yi < m and maze[xi][yi] != "#" and d[xi][yi] == float("inf"):
                q.append((xi,yi))
                d[xi][yi] = d[p[0]][p[1]] + 1

    #gまでの最短距離を返す
    return d[gx][gy]

n,m = map(int, input().split())
maze = [list(input()) for _ in range(n)]
c = 0
for i in range(n):
    for j in range(m):
        if maze[i][j] == ".":
            c += 1
res = bfs()
#到達できるなら
if 0 < res < float("inf"):
    print(c - res -1)
else:
    print(-1)