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

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

G = []
black = 0
for i in range(H):
    line = list(input())
    G.append(line)
    black += line.count("#")
    
ls = deque([[0, 0, 0]])
D = [[float("inf")] * W for i in range(H)]
direction = [[1,0], [-1,0], [0,1], [0,-1]]
while len(ls) > 0:
    h, w, depth = ls.popleft()
    
    if h == H-1 and w == W-1:
        route = depth + 1
        break
        
    for dh, dw in direction:
        if h + dh < 0 or H-1 < h + dh: continue
        if w + dw < 0 or W-1 < w + dw: continue
        if depth + 1 < D[h+dh][w+dw] and G[h+dh][w+dw] != "#":
            ls.append([h+dh, w+dw, depth+1])
            D[h+dh][w+dw] = depth + 1
            
ans = (H * W) - black - route
print(ans)

Submission status: Runtime Error

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

h, w = map(int, input().split())
maze = [list("#" * (w + 2))]
white = 0
for _ in [0] * h:
    line = "#" + input().strip() + "#"
    maze.append(list(line))
    white += line.count(".")

maze += [list("#" * (w + 2))]

q = deque()
q.append([1, 1])
maze[1][1] = 0
maze[-2][-2] = "goal"
#print(maze)

dir = [[1, 0], [0, 1], [-1, 0], [0, -1]]
dis = 0
while q:
    x, y = q.pop()
    dis += 1

    for dx, dy in dir:
        next_x, next_y = x + dx, y + dy
        if maze[next_y][next_x] == ".":
            #print(next_y, next_x)
            q.append([next_y, next_x])
            maze[next_y][next_x] = dis
            
        if maze[next_y][next_x] == "goal":
            print(white - dis - 1)
            exit()
print(-1)

Submission status: Runtime Error

Solution code:
import sys
from collections import deque

input = sys.stdin.readline
digtmp = [(1, 0), (0, 1), (-1, 0), (0, -1)]

def main():
    H, W = map(int, input().split())
    grid = []; cnt = 0
    grid.append(['#'] * (W+2))
    for _ in range(H):
        tmp = list(input())
        cnt += sum([1 for x in tmp if x == '#' ])
        grid.append(['#'] + tmp + ['#'])
    grid.append(['#'] * (W+2))

    que = deque([(1, 1)])
    grid[1][1] = 1
    for _ in range(10000):
        a, b = que.popleft()
        for dx, dy in digtmp:
            x, y = (a + dx, b + dy)
            if grid[x][y] == '.':
                grid[x][y] = grid[a][b] + 1
                que.append((x, y))
        if len(que) == 0:
            break
    if grid[H][W] == '#':
        print(-1)
        return
    ans = H*W - grid[H][W] - cnt
    print(ans)

if __name__ == "__main__":
    main()

Submission status: Runtime Error

Solution code:
from sys import stdin
def S(): return stdin.readline().rstrip()
def LI(): return list(map(int,stdin.readline().rstrip().split()))

def BFS(table,s,step,next,w,h):
    if table[h-1][w-1] != -2:
        return
    dx = [1,0,-1,0]
    dy = [0,1,0,-1]
    nnext = []
    for rep in next:
        for j in range(4):
            nx = rep[0] + dx[j]
            ny = rep[1] + dy[j]
            if nx<0  or ny<0 or w<=nx or h<=ny:
                continue
            else:
                if s[ny][nx]=='#':
                    continue
                if table[ny][nx]==-2 or step+1<table[ny][nx]:
                    table[ny][nx] = step+1
                    nnext.append([nx,ny])
    BFS(table,s,step+1,nnext,w,h)

def main():
    tmp = LI()
    w,h = tmp.pop(),tmp.pop()
    s = [S() for _ in range(h)]
    table = [[-2]*w for _ in range(h)]
    BFS(table,s,0,[[0,0]],w,h)
    step = table[h-1][w-1]
    c = 0
    for rep in s:
        c += rep.count('#')
    ans = w*h-step-c-1
    print(ans)
    return

if __name__=='__main__':
    main()

Submission status: Runtime Error

Solution code:
from sys import stdin
def S(): return stdin.readline().rstrip()
def LI(): return list(map(int,stdin.readline().rstrip().split()))

def BFS(table,s,step,next,w,h):
    if table[h-1][w-1] != -2:
        return
    dx = [1,0,-1,0]
    dy = [0,1,0,-1]
    nnext = []
    for i in range(len(next)):
        tmp = next[i]
        for j in range(4):
            nx = tmp[0] + dx[j]
            ny = tmp[1] + dy[j]
            if  nx<0  or ny<0 or w<=nx or h<=ny:
                continue
            else:
                if s[ny][nx]=='#':
                    continue
                if table[ny][nx]==-2 or step+1<table[ny][nx]:
                    table[ny][nx] = step+1
                    nnext.append([nx,ny])
    BFS(table,s,step+1,nnext,w,h)
    

if __name__=='__main__':
    tmp = LI()
    w,h = tmp.pop(),tmp.pop()
    s = [S() for _ in range(h)]
    table = [[-2]*w for _ in range(h)]
    table[0][0] = 0
    BFS(table,s,0,[[0,0]],w,h)
    step = table[h-1][w-1]
    c = 0
    for rep in s:
        c += rep.count('#')
    ans = w*h-step-c-1
    print(ans)

Submission status: Runtime Error

Solution code:
from sys import stdin
def S(): return stdin.readline().rstrip()
def LI(): return list(map(int,stdin.readline().rstrip().split()))

def BFS(table,s,step,next,w,h):
    if table[h-1][w-1] != -2:
        return
    dx = [1,0,-1,0]
    dy = [0,1,0,-1]
    nnext = []
    for i in range(len(next)):
        tmp = next[i]
        for j in range(4):
            nx = tmp[0] + dx[j]
            ny = tmp[1] + dy[j]
            if  nx<0  or ny<0 or w<=nx or h<=ny:
                continue
            else:
                if s[ny][nx]=='#':
                    continue
                if table[ny][nx]==-2 or step+1<table[ny][nx]:
                    table[ny][nx] = step+1
                    nnext.append([nx,ny])
    BFS(table,s,step+1,nnext,w,h)

def main():
    tmp = LI()
    w,h = tmp.pop(),tmp.pop()
    s = [S() for _ in range(h)]
    table = [[-2]*w for _ in range(h)]
    table[0][0] = 0
    BFS(table,s,0,[[0,0]],w,h)
    step = table[h-1][w-1]
    c = 0
    for rep in s:
        c += rep.count('#')
    ans = w*h-step-c-1
    print(ans)
    return

if __name__=='__main__':
    main()

Submission status: Runtime Error

Solution code:
from collections import deque
h,w = map(int,input().split())
d = [input() for i in range(h)]
count = 0
for i in range(h):
    for j in range(w):
        if d[i][j] == '#':
            count+=1
visited = [[0 for i in range(w)] for i in range(h)]
def bfs(sy,sx,gy,gx):
    que = deque()
    que.append((sy,sx))
    visited[sy][sx] = 0
    while que:
        y,x = que.popleft()
        if y == gy and x == gx:
            return visited[y][x]
        for dy,dx in [(-1,0),(1,0),(0,-1),(0,1)]:
            ny,nx = y+dy, x+dx
            if ny < 0 or nx < 0 or ny >= h or nx >= w:
                continue
            elif d[ny][nx] == '#':
                continue
            elif visited[ny][nx] != 0:
                continue
            else:
                visited[ny][nx] = visited[y][x] + 1
                que.append((ny,nx))
    return visited[gy][gx]
ans = bfs(0,0,h-1,w-1)
if ans = 0:
    print(-1)
    exit()
print(h*w - ans - count - 1)

Submission status: Runtime Error

Solution code:
from collections import deque
h,w = map(int,input().split())
map = [list(input()) for _ in range(h)]
dx = (1, 0, -1, 0)
dy = (0, 1, 0, -1)

def bfs():
    q = deque([])
    q.append((0,0))
    d = [([-1]*m)for _ in range(n)]

    d[0][0] = 0

    while q:
        x,y = q.popleft()
        if (x,y) == (h-1,w-1):
            break
        for i in range(4):
            nx = x+dx[i]
            ny = y+dy[i]
            if 0<=nx<h and 0<=ny<w and d[nx][ny]==-1 and map[nx][ny]!="#":
                q.append((nx,ny))
                d[nx][ny]= d[x][y]+1
    if map[h-1][w-1]:
        return h*w - d[h-1][w-1] - 1 - sum(1 for i in range(h) for j in range(w) if map[i][j] == "#")
    else:
        return -1

print(bfs())

Submission status: Runtime Error

Solution code:
from collections import deque
h,w = map(int,input().split())
map_input = [list(input()) for i in range(h)]

sx,sy = 0,0
gx,gy = w-1,h-1
#bfsで最短経路を求めて、それ以外のマスを塗りつぶせばよい
black = 0
for i in range(h):
    for j in range(w):
        if map_input[i][j]=='#':
            black+=1

mx = [0,0,1,-1]
my = [1,-1,0,0]

queue = deque([[sx,sy]])
visited = [[0]*w for i in range(h)]
visited[sy][sx] = 1

def bfs(queue,visited):
    while queue:
        x,y = queue.popleft()
        for i in range(4):
            nx = x+mx[i]
            ny = y+my[i]
            if 0<=nx<w and 0<=ny<h:
                if visited[ny][nx]!=0:
                    continue
                if map_input[ny][nx]=='#':
                    continue
                if nx==gx and ny==gy:
                    return visited[y][x]+1
                visited[ny][nx]=visited[y][x]+1
                queue.append([nx,ny])

ans = h*w-bfs(queue,visited)-black
print(ans)

Submission status: Runtime Error

Solution code:
from collections import deque

H, W = map(int, input().split())
score = H * W
S = [[] for i in range(W)]
for i in range(H):
    for s in input():
        if s == "#":
            score -= 1
        S[i].append(s)


ls = deque([[0, 0, 0]])
dir = [[1,0], [-1,0], [0,1], [0,-1]]
while len(ls) > 0:
    x, y, depth = ls.popleft()

    if x == H-1 and y == W-1:
        print(score-depth-1)
        break
    
    S[x][y] = "#"

    for dx, dy in dir:
        if (x+dx < 0) or (x+dx > H-1) or (y+dy < 0) or (y+dy > W-1):
            continue
        else:
            if S[x+dx][y+dy] == ".":
                ls.append([x+dx, y+dy, depth+1])

else:
    print(-1)

Submission status: Runtime Error

Solution code:
from collections import deque

H, W = map(int, input().split())
score = H * W
S = [[] for i in range(W)]
for i in range(H):
    for s in input():
        if s == "#":
            score -= 1
        S[i].append(s)


ls = deque([[0, 0, 0]])
while len(ls) > 0:
    x, y, depth = ls.popleft()

    if x == H-1 and y == W-1:
        print(score-depth-1)
        break
    
    S[x][y] = "#"

    if 0 <= x+1 <= H-1 and 0 <= y <= W-1:
        if S[x+1][y] == ".":
            ls.append([x+1, y, depth+1])
    if 0 <= x <= H-1 and 0 <= y+1 <= W-1:
        if S[x][y+1] == ".":
            ls.append([x, y+1, depth+1])
    if 0 <= x <= H-1 and 0 <= y-1 <= W-1:
        if S[x][y-1] == ".":
            ls.append([x, y-1, depth+1])
    if 0 <= x-1 <= H-1 and 0 <= y <= W-1:
        if S[x-1][y] == ".":
            ls.append([x-1, y, depth+1])

else:
    print(-1)

Submission status: Runtime Error

Solution code:
def main():
  h,w = map(int,input().split())
  s = [input() for _ in range(h)]
  c = [[10**5]*w for _ in range(h)]
  #print(sum([i.count(".") for i in s]))
  
  def func(dh,dw,step):
    if dh<0 or dw<0 or dh>=h or dw>=w:
      return
    step += 1
    if s[dh][dw] == ".":
      if c[dh][dw] > step:
        c[dh][dw] = step
        for i,j in ((1,0),(0,1),(-1,0),(0,-1)):
          func(dh+i,dw+j,step)
  
  func(0,0,0)
  if c[h-1][w-1] == 10**5:
    return -1
  else:
    return sum([i.count(".") for i in s])-c[h-1][w-1]

print(main())

Submission status: Runtime Error

Solution code:
from collections import deque

H,W = list(map(int, input().split()))
S = [input() for _ in range(H)]
dist = [[0] * W for i in range(H)]
dist[0][0] = 1

whites = 0
for s in S:
    for w in s:
        if w == ".":
            whites += 1

# Pythonの再帰はおっっそい. 再帰が今回のケースだと使いにくい(探索打ち切り)
def BFS(cur):
    #global dist
    x_path = [-1,0,1,0]
    y_path = [0,-1,0,1]

    q = deque()
    q.append(cur)
    while True:
        cur = q.popleft()
        if cur == (H,W):
            break

        for x,y in zip(x_path, y_path):
            nex = (cur[0] + x, cur[1] + y)
            if nex[0] < 1 or nex[0] > H or nex[1] < 1 or nex[1] > W:
                continue
            if S[nex[0]-1][nex[1]-1] == "#":
                continue
            if dist[nex[0]-1][nex[1]-1] > 0:
                continue

            dist[nex[0]-1][nex[1]-1] = dist[cur[0]-1][cur[1]-1] + 1 
            q.append(nex)


BFS((1,1))

print(whites - dist[H-1][W-1])

Submission status: Runtime Error

Solution code:
import sys
from collections import deque
H,W=map(int,input().split())
map = [[i for i in map(str,sys.stdin.readline().rstrip())] for _ in range(H)]
count_dot = 0
dist = [[0]*W for _ in range(H)]
for i in range(H):
  for j in range(W):
    if map[i][j] == '.':
      count_dot +=1
def bfs():
  while True:
    x,y = q.popleft()
    if x == H-1 and y ==W-1:
      break
    dx = [0,1,0,-1]
    dy = [1,0,-1,0]
    for i in range(4):
      nx = x + dx[i]
      ny = y + dy[i]
      if 0 <= nx < H and 0 <= ny < W and map[nx][ny]=='.' and dist[nx][ny] == 0:
        q.append((nx,ny))
        dist[nx][ny] = dist[x][y] + 1
q = deque()
q.append((0,0))
bfs()
dist_min = dist[H-1][W-1]
if dist_min ==0:
  print(-1)
else:
  print(count_dot-dist_min-1)

Submission status: Runtime Error

Solution code:
import sys
from collections import deque
H,W=map(int,input().split())
map = [[i for i in map(str,sys.stdin.readline().rstrip())] for _ in range(H)]
count_dot = 0
dist = [[0]*W for _ in range(H)]
for i in range(H):
  for j in range(W):
    if map[i][j] == '.':
      count_dot +=1
def bfs():
  while True:
    x,y = q.popleft()
    if x == H-1 and y ==W-1:
      break
    dx = [0,1,0,-1]
    dy = [1,0,-1,0]
    for i in range(4):
      nx = x + dx[i]
      ny = y + dy[i]
      if 0 <= nx < H and 0 <= ny < W and map[nx][ny]=='.' and dist[nx][ny] == 0:
        q.append((nx,ny))
        dist[nx][ny] = dist[x][y] + 1
q = deque()
q.append((0,0))
bfs()
dist_min = dist[H-1][W-1]
print(count_dot-dist_min-1)

Submission status: Runtime Error

Solution code:
import sys
sys.setrecursionlimit(10 ** 9)

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

from collections import deque
b = 0
INF = float("inf")
checked = [[INF]*w for i in range(h)]

q = deque([])
q.append((0,0))
checked[0][0] = 1
while len(q)>0:
    pos = q.popleft()
    if pos == (w-1,h-1):
        b = (checked[w-1][h-1])
        break
    if pos[0] > 0:
        if not maze[pos[0] - 1][pos[1]] == '#' and checked[pos[0] - 1][pos[1]] == INF:
            checked[pos[0] - 1][pos[1]] = checked[pos[0]][pos[1]] + 1
            q.append((pos[0] - 1, pos[1]))

    if pos[0] < w - 1:
        if not maze[pos[0] + 1][pos[1]] == '#' and checked[pos[0] + 1][pos[1]] == INF:
            checked[pos[0] + 1][pos[1]] = checked[pos[0]][pos[1]] + 1
            q.append((pos[0] + 1, pos[1]))

    if pos[1] > 0:
        if not maze[pos[0]][pos[1] - 1] == '#' and checked[pos[0]][pos[1] - 1] == INF:
            checked[pos[0]][pos[1] - 1] = checked[pos[0]][pos[1]] + 1
            q.append((pos[0], pos[1] - 1))

    if pos[1] < h - 1:
        if not maze[pos[0]][pos[1] + 1] == '#' and checked[pos[0]][pos[1] + 1] == INF:
            checked[pos[0]][pos[1] + 1] = checked[pos[0]][pos[1]] + 1
            q.append((pos[0], pos[1] + 1))
a = []
for i in range(h):
    a.append(maze[i].count("."))
if not b == 0:
    print(sum(a)-b)
else:
    print(-1)

Submission status: Runtime Error

Solution code:
import sys
sys.setrecursionlimit(10 ** 9)

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

from collections import deque
b = 0
INF = float("inf")
checked = [[INF]*w for i in range(h)]

q = deque([])
q.append((0,0))
checked[0][0] = 1
while len(q)>0:
    pos = q.popleft()
    if pos == (w-1,h-1):
        b = (checked[w-1][h-1])
        break
    if pos[0] > 0:
        if not maze[pos[0] - 1][pos[1]] == '#' and checked[pos[0] - 1][pos[1]] == INF:
            checked[pos[0] - 1][pos[1]] = checked[pos[0]][pos[1]] + 1
            q.append((pos[0] - 1, pos[1]))

    if pos[0] < w - 1:
        if not maze[pos[0] + 1][pos[1]] == '#' and checked[pos[0] + 1][pos[1]] == INF:
            checked[pos[0] + 1][pos[1]] = checked[pos[0]][pos[1]] + 1
            q.append((pos[0] + 1, pos[1]))

    if pos[1] > 0:
        if not maze[pos[0]][pos[1] - 1] == '#' and checked[pos[0]][pos[1] - 1] == INF:
            checked[pos[0]][pos[1] - 1] = checked[pos[0]][pos[1]] + 1
            q.append((pos[0], pos[1] - 1))

    if pos[1] < h - 1:
        if not maze[pos[0]][pos[1] + 1] == '#' and checked[pos[0]][pos[1] + 1] == INF:
            checked[pos[0]][pos[1] + 1] = checked[pos[0]][pos[1]] + 1
            q.append((pos[0], pos[1] + 1))
a = []
for i in range(h):
    a.append(maze[i].count("."))
print(sum(a)-b)

Submission status: Runtime Error

Solution code:
import sys
import queue
sys.setrecursionlimit(10 ** 9)

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

from collections import deque
b = 0
INF = float("inf")
checked = [[INF]*w for i in range(h)]

q = queue.Queue()
q.put((0, 0))
checked[0][0] = 1
while len(q)>0:
    pos = q.get()
    if pos == (w-1,h-1):
        b = (checked[w-1][h-1])
        break
    if pos[0] > 0:
        if not maze[pos[0] - 1][pos[1]] == '#' and checked[pos[0] - 1][pos[1]] == INF:
            checked[pos[0] - 1][pos[1]] = checked[pos[0]][pos[1]] + 1
            q.put((pos[0] - 1, pos[1]))

    if pos[0] < w - 1:
        if not maze[pos[0] + 1][pos[1]] == '#' and checked[pos[0] + 1][pos[1]] == INF:
            checked[pos[0] + 1][pos[1]] = checked[pos[0]][pos[1]] + 1
            q.put((pos[0] + 1, pos[1]))

    if pos[1] > 0:
        if not maze[pos[0]][pos[1] - 1] == '#' and checked[pos[0]][pos[1] - 1] == INF:
            checked[pos[0]][pos[1] - 1] = checked[pos[0]][pos[1]] + 1
            q.put((pos[0], pos[1] - 1))

    if pos[1] < h - 1:
        if not maze[pos[0]][pos[1] + 1] == '#' and checked[pos[0]][pos[1] + 1] == INF:
            checked[pos[0]][pos[1] + 1] = checked[pos[0]][pos[1]] + 1
            q.put((pos[0], pos[1] + 1))
a = []
for i in range(h):
    a.append(maze[i].count("."))
print(sum(a)-b)

Submission status: Runtime Error

Solution code:
from collections import deque

def bfs(s_l, visited, sy, sx, gy, gx, h, w):
    q = deque([[sy,sx]])
    visited[0][0] = 0
    while q:
        y, x = q.popleft()
        if [y, x] == [gy, gx]:
            return visited[gy][gx]
        for j, k in ([1, 0], [-1, 0], [0, 1], [0, -1]):
            n_y, n_x = y+j, x+k
            if n_y >= h or n_x >= w or n_y < 0 or n_x < 0:
                continue
            if s_l[n_y][n_x] == '.' and visited[n_y][n_x] == -1:
                visited[n_y][n_x] = visited[y][x] + 1
                q.append([n_y,n_x])

def main():
    h, w = map(int, input().split()) 
    s_l = []
    all_dot_cnt = 0
    for i in range(h):
        row = list(input())
        s_l.append(row)
        all_dot_cnt += row.count('.')
    
    visited = [ [-1]*w for i in range(h)]
    res = bfs(s_l, visited, 0, 0, h-1, w-1, h, w)
    # print(res)
    # print(all_dot_cnt)
    print(all_dot_cnt-res-1)

if __name__ == "__main__":
    main()

Submission status: Runtime Error

Solution code:
import numpy as np

h , w = map(int, input().split())
visited = np.zeros((h,w))

for y in range(h):
    _in = input()
    for x, value in enumerate(_in):
        if value == '.':
            visited[y][x] = 10**9
for i in range(1,h):
    visited[i,:] = np.minimum(visited[i,:],visited[i-1,:]+1)
for i in reversed(range(h-1)):
    visited[i,:] = np.minimum(visited[i,:],visited[i+1,:]+1)
for j in range(1,h):
    visited[:,j] = np.minimum(visited[:,j],visited[:,j-1]+1)
for j in reversed(range(h-1)):
    visited[:,j] = np.minimum(visited[:,j],visited[:,j+1]+1)
print(np.max(visited))

Submission status: Runtime Error

Solution code:
from collections import deque

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

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


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

Submission status: Runtime Error

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

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

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

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

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

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


def solve():
    print(bfs())

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

Submission status: Runtime Error

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

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

count=0
def search():
    while (q):
        x,y,count=q.popleft()
        
        if check(x,y)==False or (x,y) in finished or c[x][y]=='#':
            continue
        else:
            q.append([x,y-1,count+1])
            q.append([x,y+1,count+1])
            q.append([x+1,y,count+1])
            q.append([x-1,y,count+1])
            finished.add((x,y))
            c[x][y]=count
            if x==ex-1 and y==ey-1:
                return c[x][y]+1 #通った道の合計を返す

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

print(h*w-black_count-search())#全体からもともと黒の#の数と通った白い道を削除

Submission status: Runtime Error

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

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

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

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

Submission status: Runtime Error

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

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

Submission status: Runtime Error

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

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

Submission status: Runtime Error

Solution code:
from collections import deque
import sys

def my_bfs(field, R, C):
    sy, sx = 1, 1
    gy, gx = R, C
    dxy = [(0,1), (0,-1), (1,0), (-1,0)]
    flg = False
    cnt = 0
    dot_num = sum(r.count('.') for r in field)

    q = deque()
    q.append([sy, sx])
    field[sy][sx] = 0
    while flg == False:
        yx = q.popleft()
        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
                return(dot_num - (cnt+2))
                break
            if field[y_n][x_n] == '#':
                continue
            if field[y_n][x_n] == '.':
                q.append([y_n, x_n])
                field[y_n][x_n] = cnt + 1
        if flg:
            break
    else:
        return(-1)

sys.setrecursionlimit(10**6)

R, C = map(int, input().split())
field = [["#"] * (C + 2)] + \
        [list("#" + input() + "#") for i in range(R)] + \
        [["#"] * (C + 2)]

out = my_bfs(field, R, C)
print(out)

Submission status: Runtime Error

Solution code:
from collections import deque
import sys

sys.setrecursionlimit(10**6)

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)]
dxy = [(0,1), (0,-1), (1,0), (-1,0)]
flg = False
cnt = 0

dot_num = sum(r.count('.') for r in field)

q = deque()
q.append([sy, sx])
field[sy][sx] = 0

while flg == False:
    yx = q.popleft()
    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))
            break
        if field[y_n][x_n] == '#':
            continue
        if field[y_n][x_n] == '.':
            q.append([y_n, x_n])
            field[y_n][x_n] = cnt + 1
    if flg:
        break
if flg == False:
    print(-1)

Submission status: Runtime Error

Solution code:
from collections import deque

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)]
dxy = [(0,1), (0,-1), (1,0), (-1,0)]
flg = False
cnt = 0

dot_num = sum(r.count('.') for r in field)

q = deque()
q.append([sy, sx])
field[sy][sx] = 0

while flg == False:
    yx = q.popleft()
    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))
            break
        if field[y_n][x_n] == '#':
            continue
        if field[y_n][x_n] == '.':
            q.append([y_n, x_n])
            field[y_n][x_n] = cnt + 1
    if flg:
        break
if flg == False:
    print(-1)

Submission status: Runtime Error

Solution code:
from collections import deque
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)]
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 = deque()
q.append([sy, sx])
field[sy][sx] = 0

while flg == False:
    yx = q.popleft()
    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))
            break
        if field[y_n][x_n] == '#':
            continue
        if field[y_n][x_n] == '.':
            q.append([y_n, x_n])
            field[y_n][x_n] = cnt + 1
    if flg:
        break
if flg == False:
    print(-1)