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:
H, W = map(int, input().split())
S = [input() for _ in range(H)]
M = [(0, 0)]


def dfs(x, y, c):
    cc = float('inf')
    for xx, yy in [(x + 1, y), (x, y + 1), (x - 1, y), (x, y - 1)]:
        if (H, W) == (yy + 1, xx + 1):
            return c + 1
        if 0 <= yy < H and 0 <= xx < W and S[yy][xx] == '.' and \
                (xx, yy) not in M:
            M.append((xx, yy))
            cc = min(cc, dfs(xx, yy, c + 1))
    return cc


def main():
    ans = 0
    for i in range(H):
        ans += S[i].count('.')
    c = dfs(0, 0, 1)
    if c == float('inf'):
        print(-1)
    else:
        print(ans - c)


main()

Submission status: Runtime Error

Solution code:
import math


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


def dfs(x, y, c):
    cc = float('inf')
    for xx, yy in [(x + 1, y), (x, y + 1), (x - 1, y), (x, y - 1)]:
        if (H, W) == (yy + 1, xx + 1):
            return c + 1
        if 0 <= yy < H and 0 <= xx < W and S[yy][xx] == '.' and \
                (xx, yy) not in M:
            M.append((xx, yy))
            cc = min(cc, dfs(xx, yy, c + 1))
    return cc


def main():
    ans = 0
    for i in range(H):
        ans += S[i].count('.')
    c = dfs(0, 0, 1)
    if c == math.inf:
        print(-1)
    else:
        print(ans - c)


main()

Submission status: Runtime Error

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


def dfs(x, y, c):
    cc = float('inf')
    for xx, yy in [(x + 1, y), (x, y + 1), (x - 1, y), (x, y - 1)]:
        if (H, W) == (yy + 1, xx + 1):
            return c + 1
        if 0 <= yy < H and 0 <= xx < W and S[yy][xx] == '.' and \
                (xx, yy) not in M:
            M.append((xx, yy))
            cc = min(cc, dfs(xx, yy, c + 1))
    return cc


def main():
    ans = 0
    for i in range(H):
        ans += S[i].count('.')
    print(ans - dfs(0, 0, 1))


main()

Submission status: Runtime Error

Solution code:
from collections import deque

def bfs(board, visited, gh, gw):
    turn = 0
    queue = deque([[0, 0, turn]])
    while queue:
        h, w, turn = queue.popleft()
        if h == gh-1 and w == gw-1:
            return turn
        for i, j in ([1,0],[-1,0],[0,1],[0,-1]):
            new_h, new_w = h+i, w+j
            if new_h >= gh or new_h < 0 or new_w >= gw or new_w < 0:
                continue
            elif board[new_h][new_w] != "#" and visited[new_h][new_w] == "x":
                visited[new_h][new_w] = "o"
                queue.append([new_h, new_w, turn+1])

def main():
    H, W = map(int,input().split())
    board = []
    for _ in range(H):
        board.append(list(input()))
    black = 0
    for i in range(H):
        for j in range(W):
            if board[i][j] == "#":
                black += 1
    visited = [["x"]*W for _ in range(H)]
    path_area = bfs(board, visited, H, W) + 1
    print(H*W-path_area-black)
                
    
    
if __name__ == "__main__":
    main()

Submission status: Runtime Error

Solution code:
from collections import deque

def bfs(board, visited, gh, gw):
    turn = 0
    queue = deque([[0, 0, turn]])
    while queue:
        h, w, turn = queue.popleft()
        if h == gh-1 and w == gw-1:
            return turn
        for i, j in ([1,0],[-1,0],[0,1],[0,-1]):
            new_h, new_w = h+i, w+j
            if new_h >= gh or new_h < 0 or new_w >= gw or new_w < 0:
                continue
            elif board[new_h][new_w] != "#" and visited[new_h][new_w] == "x":
                visited[new_h][new_w] = "o"
                queue.append([new_h, new_w, turn+1])
    
    

def main():
    H, W = map(int,input().split())
    board = []
    for _ in range(H):
        board.append(list(input()))
    black = 0
    for i in range(H):
        for j in range(W):
            if board[i][j] == "#":
                black += 1
    visited = [["x"]*W for _ in range(H)]
    path_area = bfs(board, visited, H, W) + 1
    print(H*W-path_area-black)
                
    
    
if __name__ == "__main__":
    main()

Submission status: Runtime Error

Solution code:
import queue

q = queue.Queue()
H,W = map(int, input().split())
memo = [[-1]*W for _ in range(H)]
board = [input() for _ in range(H)]
wall=0
direction = [(1, 0), (-1, 0), (0, 1), (0, -1)]


def bfs():
    memo[0][0] = 0
    q.put((0, 0))
    while not q.empty():
        y,x= q.get()
        for (dy, dx) in direction:
            if 0<=y+dy<=H-1 and 0<=x+dx<=W-1 and board[y+dy][x+dx] == '.' and memo[y+dy][x+dx] == -1:
                q.put((y + dy, x + dx))
                memo[y + dy][x + dx] = memo[y][x] + 1
                if (y+dy, x+dx) == (H-1, W-1):
                    return memo[H-1][W-1]

for s in board:
    wall+=s.count('#')

print(H*W-wall-(bfs()+1))

Submission status: Runtime Error

Solution code:
h, w = [int(s) for s in input().split(' ')]
 
s = []
for i in range(h):
    s.append([s == '.' for s in input()])
 
inf = 10000
dx = [1, 0, -1, 0]
dy = [0, 1, 0, -1]

queue = [(0, 0)]
p = []
for i in range(h):
    p.append([inf] * w)
p[0][0] = 1
 
while len(queue) > 0:
    x, y = queue.pop()
    for i in range(4):
        xx = x + dx[i]
        yy = y + dy[i]
        if 0 <= xx and xx < w and 0 <= yy and yy < h:
        	if s[yy][xx] and p[yy][xx] > p[y][x] + 1:
            	p[yy][xx] = p[y][x] + 1
           		queue.insert(0, (xx, yy))
           
if p[h-1][w-1] == inf:
    print('-1')
else:
    print(sum(sum(x) for x in s) - p[h-1][w-1])

Submission status: Runtime Error

Solution code:
h, w = [int(s) for s in input().split(' ')]
 
s = []
for i in range(h):
    s.append(input())
 
inf = 10000
dx = [1, 0, -1, 0]
dy = [0, 1, 0, -1]
queue = [(0, 0)]
d = []
for i in range(h):
    d.append([inf] * w)
d[0][0] = 1
 
while len(queue) > 0:
    x, y = queue.pop()
    for i in range(4):
        xx = x + dx[i]
        yy = y + dy[i]
        if 0 <= xx and xx < w and 0 <= yy and yy < h and s[yy][xx] == '.' and d[yy][xx] > d[y][x] + 1:
           d[yy][xx] = d[y][x] + 1
           queue.insert(0, (xx, yy))
if d[h-1][w-1] == inf:
    print('-1')
else:
    print(sum(sum(x) for x in s) - d[h-1][w-1])

Submission status: Runtime Error

Solution code:
from collections import deque
h,w=map(int,input().split())
maze=[['#' for i in range(w+2)]]+[['#']+[x=='#' for x in input()]+['#'] for i in range(h)]+[['#' for i in range(w+2)]]
f=0
for i in range(1,h+1):
  for j in range(1,w+1):
    if maze[i][j]:
	    f+=1

pos=deque([(1,1,0)])
while pos:
    x,y,c=pos.popleft()
    if (x,y)==(h,w):
        z=c
        break
    elif maze[x][y]:
        continue    
    pos.append((x-1, y, c+1))
    pos.append((x+1, y, c+1))
    pos.append((x, y-1, c+1))
    pos.append((x, y+1, c+1))
    maze[x][y] = True
    
print(h*w-f-z-1)

Submission status: Runtime Error

Solution code:
import sys

def wfs(queue, S, step, goal):
    next_queue = []
    for q in queue:
        if q == goal:
            return step+1

        i, j = q[0], q[1]
        S[i][j] = '#'

        if S[i+1][j] == '.':
            next_queue.append([i+1, j])
        if S[i-1][j] == '.':
            next_queue.append([i-1, j])
        if S[i][j+1] == '.':
            next_queue.append([i, j+1])
        if S[i][j-1] == '.':
            next_queue.append([i, j-1])

    if len(next_queue) == 0:
        return -1
    else:
        next_queue = list(set(next_queue))
        return wfs(next_queue, S, step+1, goal)


def main():
    input = sys.stdin.readline
    H, W = map(int, input().split())
    S = []
    init = 0
    for _ in range(H):
        s = [c for c in input().strip()]
        init += sum([c == '#' for c in s])
        S.append(['#'] + s + ['#'])
    S = [['#'] * (W+2)] + S + [['#'] * (W+2)]
    minstep = wfs([[1,1]], S, 0, [H, W])
    if minstep == -1:
        print(-1)
    else:
        print(H*W - minstep - init)


if __name__ == '__main__':
    main()

Submission status: Runtime Error

Solution code:
import sys

def wfs(queue, S, step, goal):
    next_queue = []
    for q in queue:
        if q == goal:
            return step+1

        i, j = q[0], q[1]
        S[i][j] = '#'

        if S[i+1][j] == '.':
            next_queue.append([i+1, j])
        if S[i-1][j] == '.':
            next_queue.append([i-1, j])
        if S[i][j+1] == '.':
            next_queue.append([i, j+1])
        if S[i][j-1] == '.':
            next_queue.append([i, j-1])

    if len(next_queue) == 0:
        return -1
    else:
        return wfs(next_queue, S, step+1, goal)


def main():
    input = sys.stdin.readline
    H, W = map(int, input().split())
    S = []
    init = 0
    for _ in range(H):
        s = input().strip()
        init += s.count('#')
        S.append('#' + s + '#')
    S = ['#' * (W+2)] + S + ['#' * (W+2)]
    minstep = wfs([[1,1]], S, 0, [H, W])
    if minstep == -1:
        print(-1)
    else:
        print(H*W - minstep - init)


if __name__ == '__main__':
    main()

Submission status: Runtime Error

Solution code:
import sys

def f(pos, S, step, R, goal):
    i, j = pos[0], pos[1]
    if i >= goal[0]+1 or i < 0 or j >= goal[1]+1 or j < 0:
        return 10**5
    if S[i][j]:
        return 10**5
    if pos == goal:
        return step

    if step > R[i][j]:
        return 10**5
    else:
        R[i][j] = step
        return min(f([i+1, j], S, step+1, R, goal),
                   f([i-1, j], S, step+1, R, goal),
                   f([i, j+1], S, step+1, R, goal),
                   f([i, j-1], S, step+1, R, goal))

def main():
    input = sys.stdin.readline
    H, W = map(int, input().split())
    S = []
    init = 0
    for _ in range(H):
        s = [c == '#' for c in input().strip()]
        init += sum(s)
        S.append(s)
    R = [[10**5 for _ in range(W)] for _ in range(H)]
    R[0][0] = 1
    minstep = f([0,0], S, 1, R, [H-1, W-1])
    if minstep == 10**5:
        print(-1)
    else:
        print(H*W - minstep - init)


if __name__ == '__main__':
    main()

Submission status: Runtime Error

Solution code:
import copy
n,hp=map(int,input().split(" "))
la=[0 for i in range(n)]
lb=[0 for i in range(n)]
for i in range(n):
    la[i],lb[i]=map(int,input().split(" "))
cnt=0
ma=max(la)
lma=[i for i ,x in enumerate(la)  if x==ma]
mib=10**9
for i in lma:
    if lb[i]<mib:
        mib=lb[i]
        k=i
tmp=copy.deepcopy(lb)
while max(tmp)>ma:
    hp-=max(tmp)
    tmp.remove(max(tmp))
    cnt+=1
    if hp<0:
        print(cnt)
        exit(0)
if lb[k]>ma:
    hp+=lb[k]
if lb[k]>ma:
    hp-=lb[k]
    cnt+=1
if hp%ma==0:
    print(cnt+int(hp/ma))
else:
    print(cnt+int(hp/ma)+1)

Submission status: Runtime Error

Solution code:
from collections import deque

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

sy,sx = 0,0
gy,gx = H-1,W-1

queue = deque([(sy,sx)])

dyx=((1,0),(-1,0),(0,1),(0,-1))

counted_map = [[-1]*W for _ in range(H)]
counted_map[sy][sx] = 0

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

    if (y,x) == (gy,gx):
        break

    for dy,dx in dyx:
        ny = y + dy
        nx = x + dx

        if ny < 0 or nx < 0 or ny >= H or nx >= W:
            continue

        # 空きマスかつ未訪問
        if _input[ny][nx] == '.' and counted_map[ny][nx] == -1:
            counted_map[ny][nx] = counted_map[y][x] + 1
            queue.append((ny,nx))

y,x = gy,gx
move_num = counted_map[gy][gx]
while move_num != 0:
    _input[y][x] = 'o'
    for dy,dx in dyx:
        ny = y + dy
        nx = x + dx

        if ny < 0 or nx < 0 or ny >= H or nx >= W:
            continue
        
        if _input[ny][nx] == '.':
            tmp_dist = counted_map[ny][nx]
            if tmp_dist < move_num:
                move_num = tmp_dist
                next_y,next_x = ny,nx
    
    y,x = next_y,next_x

_input[sy][sx] = 'o'

res = 0

for raw in _input:
    for i in raw:
        if i == '.':
            res += 1

print(res)

Submission status: Runtime Error

Solution code:
H, W = [int(i) for i in input().split()]
sy, sx = [0,0]
gy, gx = [H-1, W-1]
c_ls = list()
yet_ls = [(sy,sx)]
dist_dict = {(sy, sx): 0}
road_len = 0
for i in range(H):
    c_ls.append([i for i in list(input())])
    road_len += len([i for i in c_ls[-1] if i == "."])


def dfs():
    ind = 0
    while len(yet_ls) > ind:
        y, x = yet_ls[ind]
        for move_y, move_x in [(1,0),(-1,0),(0,1),(0,-1)]:
            next_y = y + move_y
            next_x = x + move_x
            if 0 <= next_y < H and 0 <= next_x < W:
                pass
            else:
                continue
            if c_ls[next_y][next_x] == "#":
                continue
            c_ls[next_y][next_x] = "#"
            if (next_y, next_x) not in dist_dict:
                dist_dict[(next_y, next_x)] = dist_dict[(y,x)] + 1
                yet_ls.append((next_y,next_x))
            if (next_y, next_x) == (gy, gx):
                return dist_dict[(next_y, next_x)]
        ind += 1

print(road_len - dfs() - 1)

Submission status: Runtime Error

Solution code:
R, C = map(int, input().split())
c = [list(input()) for _ in range(R)]
d = {}
q = [(0, 0, 0)]
d[0, 0] = 0
while q != []:
    (y, x, z) = q.pop(0)
    for v, w in [(-1, 0), (1, 0), (0, -1), (0, 1)]:
        t = x + v
        u = y + w
        if t < 0 or t >= C or u < 0 or u >= R:
            continue
        if c[u][t] == '.' and (u, t) not in d:
            q.append((u, t, z + 1))
            d[u, t] = z + 1
ans = R * C - d[R - 1, C - 1] - 1
for i in c:
    for j in i:
        if j == '#':
            ans -= 1
print(ans)

Submission status: Runtime Error

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

H, W = map(int, input().split())
s = [input() for _ in range(H)]
d = [[-1] * W for _ in range(W)]

# 0,0 to h-1, w-1
d[0][0] = 0

queue = []
queue.append([0, 0])
#
# while len(queue) > 0:
#     p = queue.pop(0)
#     y, x = p[0], p[1]
#
#     dx4 = [0, 0, 1, -1]
#     dy4 = [1, -1, 0, 0]
#
#     for dx, dy in zip(dx4, dy4):
#         next_y = y + dy
#         next_x = x + dx
#         if 0 <= next_y < H and 0 <= next_x < W and s[next_y][next_x] != "#" and d[next_y][next_x] == -1:
#             d[next_y][next_x] = d[y][x] + 1
#             queue.append([next_y, next_x])

count = 0
for l in s:
    for c in l:
        if c == ".":
            count += 1

if d[H-1][W-1] == -1:
    print(-1)
else:
    print(count - d[H-1][W-1] - 1)

# [print(l) for l in s]
# [print(l) for l in d]

Submission status: Runtime Error

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

H, W = map(int, input().split())
s = [input() for _ in range(H)]
d = [[-1] * W for _ in range(W)]

# 0,0 to h-1, w-1
d[0][0] = 0

queue = []
queue.append([0, 0])

while len(queue) > 0:
    p = queue.pop(0)
    y, x = p[0], p[1]

    dx4 = [0, 0, 1, -1]
    dy4 = [1, -1, 0, 0]

    for dx, dy in zip(dx4, dy4):
        next_y = y + dy
        next_x = x + dx
        if 0 <= next_y < H and 0 <= next_x < W and s[next_y][next_x] != "#" and d[next_y][next_x] == -1:
            d[next_y][next_x] = d[y][x] + 1
            queue.append([next_y, next_x])
#
# count = 0
# for l in s:
#     for c in l:
#         if c == ".":
#             count += 1
#
# if d[H-1][W-1] == -1:
#     print(-1)
# else:
#     print(count - d[H-1][W-1] - 1)

# [print(l) for l in s]
# [print(l) for l in d]

Submission status: Runtime Error

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

H, W = map(int, input().split())
s = [input() for _ in range(H)]
d = [[-1] * W for _ in range(W)]

# 0,0 to h-1, w-1
d[0][0] = 0

queue = []
queue.append([0, 0])

while len(queue) > 0:
    p = queue.pop(0)
    y, x = p[0], p[1]

    dx4 = [0, 0, 1, -1]
    dy4 = [1, -1, 0, 0]

    for dx, dy in zip(dx4, dy4):
        next_y = y + dy
        next_x = x + dx
        if 0 <= next_y < H and 0 <= next_x < W and s[next_y][next_x] != "#" and d[next_y][next_x] == -1:
            d[next_y][next_x] = d[y][x] + 1
            queue.append([next_y, next_x])

count = 0
for l in s:
    for c in l:
        if c == ".":
            count += 1

if d[H-1][W-1] == -1:
    print(-1)
else:
    print(-1)
    # print(count - d[H-1][W-1] - 1)

# [print(l) for l in s]
# [print(l) for l in d]

Submission status: Runtime Error

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

H, W = map(int, input().split())
s = [input() for _ in range(H)]
d = [[-1] * W for _ in range(W)]

# 0,0 to h-1, w-1
d[0][0] = 0

queue = []
queue.append([0, 0])

while len(queue) > 0:
    p = queue.pop(0)
    y, x = p[0], p[1]

    dx4 = [0, 0, 1, -1]
    dy4 = [1, -1, 0, 0]

    for dx, dy in zip(dx4, dy4):
        next_y = y + dy
        next_x = x + dx
        if 0 <= next_y < H and 0 <= next_x < W and s[next_y][next_x] != "#" and d[next_y][next_x] == -1:
            d[next_y][next_x] = d[y][x] + 1
            queue.append([next_y, next_x])

count = 0
for l in s:
    for c in l:
        if c == ".":
            count += 1

if d[H-1][W-1] == -1:
    print(-1)
else:
    print(count - d[H-1][W-1] - 1)

# [print(l) for l in s]
# [print(l) for l in d]

Submission status: Runtime Error

Solution code:
# https://atcoder.jp/contests/abc088/tasks/abc088_d
from collections import deque

H, W = map(int, input().split())
s = [input() for _ in range(H)]
d = [[-1] * W for _ in range(W)]

# 0,0 to h-1, w-1
d[0][0] = 0

queue = deque()
queue.append([0, 0])

while len(queue) > 0:
    p = queue.popleft()
    y, x = p[0], p[1]

    dx4 = [0, 0, 1, -1]
    dy4 = [1, -1, 0, 0]

    for dx, dy in zip(dx4, dy4):
        next_y = y + dy
        next_x = x + dx
        if 0 <= next_y < H and 0 <= next_x < W and s[next_y][next_x] != "#" and d[next_y][next_x] == -1:
            d[next_y][next_x] = d[y][x] + 1
            queue.append([next_y, next_x])

count = 0
for l in s:
    count += l.count(".")

if d[H-1][W-1] == -1:
    print(-1)
else:
    print(count - d[H-1][W-1] - 1)

# [print(l) for l in s]
# [print(l) for l in d]

Submission status: Runtime Error

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

H, W = map(int, input().split())
s = [input() for _ in range(H)]
d = [[-1] * W for _ in range(W)]

# 0,0 to h-1, w-1
d[0][0] = 0

queue = []
queue.append([0, 0])

while len(queue) > 0:
    p = queue.pop(0)
    y, x = p[0], p[1]

    dx4 = [0, 0, 1, -1]
    dy4 = [1, -1, 0, 0]

    for dx, dy in zip(dx4, dy4):
        next_y = y + dy
        next_x = x + dx
        # if 0 <= next_y < H and 0 <= next_x < W and s[next_y][next_x] != "#" and d[next_y][next_x] == -1:
        #     d[next_y][next_x] = d[y][x] + 1
        #     queue.append([next_y, next_x])

count = 0
for l in s:
    count += l.count(".")

if d[H-1][W-1] == -1:
    print(-1)
else:
    print(count - d[H-1][W-1] - 1)

# [print(l) for l in s]
# [print(l) for l in d]

Submission status: Runtime Error

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

H, W = map(int, input().split())
s = [input() for _ in range(H)]
d = [[-1 for _ in range(W)] for _ in range(W)]

# 0,0 to h-1, w-1
d[0][0] = 0

queue = []
queue.append((0, 0))

while len(queue) > 0:
    p = queue.pop(0)
    y, x = p[0], p[1]

    dx4 = [0, 0, 1, -1]
    dy4 = [1, -1, 0, 0]

    for dx, dy in zip(dx4, dy4):
        next_y = y + dy
        next_x = x + dx
        if 0 <= next_y < H and 0 <= next_x < W and s[next_y][next_x] != "#" and d[next_y][next_x] == -1:
            d[next_y][next_x] = d[y][x] + 1
            queue.append((next_y, next_x))

count = 0
for l in s:
    count += l.count(".")

if d[H-1][W-1] == -1:
    print(-1)
else:
    print(count - d[H-1][W-1] - 1)

# [print(l) for l in s]
# [print(l) for l in d]

Submission status: Runtime Error

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

H, W = map(int, input().split())
s = [input() for _ in range(H)]
d = [[-1 for _ in range(W)] for _ in range(W)]

# 0,0 to h-1, w-1
d[0][0] = 0

queue = []
queue.append((0, 0))

while len(queue) > 0:
    p = queue.pop(0)
    y, x = p[0], p[1]

    dx4 = [0, 0, 1, -1]
    dy4 = [1, -1, 0, 0]

    for dx, dy in zip(dx4, dy4):
        next_y = y + dy
        next_x = x + dx
        if 0 <= next_y < H and 0 <= next_x < W and s[next_y][next_x] != "#" and d[next_y][next_x] == -1:
            d[next_y][next_x] = d[y][x] + 1
            queue.append((next_y, next_x))

count = 0
for l in s:
    count += l.count(".")

print(count - d[H-1][W-1] - 1)

# [print(l) for l in s]
# [print(l) for l in d]

Submission status: Runtime Error

Solution code:
from collections import deque

h,w = map(int,input().split())
s = [input() for i in range(h)]
visited = [[-1]*w for i in range(h)]
que = deque()

def bfs(i,j):
  que.append([i,j])
  visited[i][j]=0
  
  while True:
    if not que:
      return "答えなし"
    
    [current_i,current_j] = que.popleft()
    
    if  current_i == h-1 and current_j == w-1:
      return visited[current_i][current_j]
  
    for next in [[-1,0],[+1,0],[0,-1],[0,+1]]:
      next_i = current_i + next[0]
      next_j = current_j + next[1]
      if 0<=next_i<h and 0<=next_j<w:
        if visited[next_i][next_j] == -1 and s[next_i][next_j]==".":
          visited[next_i][next_j] = visited[current_i][current_j]+1
          que.append([next_i,next_j])

count_point=0
for i in range(h):
  for j in range(w):
    if s[i][j] == ".":
      count_point += 1 
  
print(count_point-bfs(0,0)-1)

Submission status: Runtime Error

Solution code:
h,w = map(int,input().split())
a = [list(input()) for _ in range(h)]

def check(x):
    if x == 'U':
        y = i-1
        z = j
    elif x == 'D':
        y = i+1
        z = j
    elif x == 'L':
        y = i
        z = j-1
    else:
        y = i
        z = j+1
        
    if a[y][z] != '.':
        return
    else:
        a[y][z] = a[i][j]+1
        


cnt = 0
for i in range(h):
    for j in range(w):
        if a[i][j] == '#':
            cnt += 1
            
        if i == j == 0:
            a[i][j] = 0
            check('R')
            check('D')
        elif i == h-1 and j == w-1:
            break
        elif a[i][j] != '.' and a[i][j] != '#':
            if i == h-1 and j == 0:
                check('U')
                check('R')
            elif i == 0 and j == w-1:
                check('L')
                check('D')
            elif 0 < i < h-1 and j == 0:
                check('U')
                check('D')
                check('R')
            elif 0 < i < h-1 and j == w-1:
                check('U')
                check('D')
                check('L')
            elif i == 0 and 0 < j < w-1:
                check('L')
                check('R')
                check('D')
            elif i == h-1 and 0 < j < w-1:
                check('L')
                check('R')
                check('U')
            else:
                check('U')
                check('D')
                check('L')
                check('R')

print(h*w - cnt - (a[h-1][w-1]+1))

Submission status: Runtime Error

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

water=[[0]*w for _ in range(w)]
water[0][0]=1
a_index=[]
a_column=[]
a_index.append(0)
a_column.append(0)
b=[]
count=0

for i in range(h):
    for j in range(w):
        if s[i][j] == '#':
            water[i][j]=3000
            count+=1
while water[h-1][w-1]==0:
    for i,j in zip(a_index,a_column):
        if water[i][j]==1:
            if i>0:
                if water[i-1][j]==0:
                    water[i-1][j]+=1
                    b.insert(0,[i-1,j])
            if i<h-1:
                if water[i+1][j]==0:
                    water[i+1][j]+=1
                    b.insert(0,[i+1,j])
            if j>0:
                if water[i][j-1]==0:
                    water[i][j-1]+=1
                    b.insert(0,[i,j-1])
            if j<w-1:
                if water[i][j+1]==0:
                    water[i][j+1]+=1
                    b.insert(0,[i,j+1])
        water[i][j]+=1
    a_index+=[x[0] for x in b]
    a_column+=[x[1] for x in b]

    if not b:
        print(-1)
        exit()
    b=[]

print(h*w-water[0][0]-count)

Submission status: Runtime Error

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

water=[[0]*w for _ in range(w)]
water[0][0]=1
a_index=[]
a_column=[]
a_index.append(0)
a_column.append(0)
b=[]
count=0
flag=True
for i in range(h):
    for j in range(w):
        if s[i][j] == '#':
            water[i][j]=3000
            count+=1
while water[h-1][w-1]==0:
    for i,j in zip(a_index,a_column):
        if water[i][j]==1:
            if i>0:
                if water[i-1][j]==0:
                    water[i-1][j]+=1
                    b.insert(0,[i-1,j])
            if i<h-1:
                if water[i+1][j]==0:
                    water[i+1][j]+=1
                    b.insert(0,[i+1,j])
            if j>0:
                if water[i][j-1]==0:
                    water[i][j-1]+=1
                    b.insert(0,[i,j-1])
            if j<w-1:
                if water[i][j+1]==0:
                    water[i][j+1]+=1
                    b.insert(0,[i,j+1])
        water[i][j]+=1
    a_index+=[x[0] for x in b]
    a_column+=[x[1] for x in b]

    if not b:
        flag=False
        break
    b=[]

if flag:
    print(h*w-water[0][0]-count)
else:
    print(-1)

Submission status: Runtime Error

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

water=[[0]*w for _ in range(w)]
water[0][0]=1
a_index=[]
a_column=[]
a_index.append(0)
a_column.append(0)
b=[]
count=0
flag=True
for i in range(h):
    for j in range(w):
        if s[j][i] == '#':
            water[i][j]=3000
            count+=1
while water[h-1][w-1]==0:
    for i,j in zip(a_index,a_column):
        if water[i][j]==1:
            if i>0:
                if water[i-1][j]==0:
                    water[i-1][j]+=1
                    b.insert(0,[i-1,j])
            if i<h-1:
                if water[i+1][j]==0:
                    water[i+1][j]+=1
                    b.insert(0,[i+1,j])
            if j>0:
                if water[i][j-1]==0:
                    water[i][j-1]+=1
                    b.insert(0,[i,j-1])
            if j<w-1:
                if water[i][j+1]==0:
                    water[i][j+1]+=1
                    b.insert(0,[i,j+1])
        water[i][j]+=1
    a_index+=[x[0] for x in b]
    a_column+=[x[1] for x in b]

    if not b:
        flag=False
        break
    b=[]

if flag:
    print(h*w-water[0][0]-count)
else:
    print(-1)

Submission status: Runtime Error

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

water=[[0]*w for _ in range(w)]
water[0][0]=0
a_index=[]
a_column=[]
a_index.append(0)
a_column.append(0)
b=[]
count=0
flag=True
for i in range(h):
    for j in range(w):
        if s[i][j] == '#':
            water[i][j]=3000
            count+=1
while water[h-1][w-1]==0:
    for i,j in zip(a_index,a_column):
        if water[i][j]==1:
            if i>0:
                if water[i-1][j]==0:
                    water[i-1][j]+=1
                    b.insert(0,[i-1,j])
            if i<h-1:
                if water[i+1][j]==0:
                    water[i+1][j]+=1
                    b.insert(0,[i+1,j])
            if j>0:
                if water[i][j-1]==0:
                    water[i][j-1]+=1
                    b.insert(0,[i,j-1])
            if j<w-1:
                if water[i][j+1]==0:
                    water[i][j+1]+=1
                    b.insert(0,[i,j+1])
        water[i][j]+=1
    a_index+=[x[0] for x in b]
    a_column+=[x[1] for x in b]
    if not b:
        flag=False
        break
    b=[]
if flag:
    print(h*w-water[0][0]-count)
else:
    print(-1)

Submission status: Runtime Error

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

water=[[0]*w for _ in range(w)]
water[0][0]=0
a_index=[]
a_column=[]
a_index.append(0)
a_column.append(0)
b=[]
count=0
for i in range(h):
    for j in range(w):
        if s[i][j] == '#':
            water[i][j]=3000
            count+=1
while water[h-1][w-1]==0:
    for i,j in zip(a_index,a_column):
        if water[i][j]==1:
            if i>0:
                if water[i-1][j]==0:
                    water[i-1][j]+=1
                    b.insert(0,[i-1,j])
            if i<h-1:
                if water[i+1][j]==0:
                    water[i+1][j]+=1
                    b.insert(0,[i+1,j])
            if j>0:
                if water[i][j-1]==0:
                    water[i][j-1]+=1
                    b.insert(0,[i,j-1])
            if j<w-1:
                if water[i][j+1]==0:
                    water[i][j+1]+=1
                    b.insert(0,[i,j+1])
        water[i][j]+=1
    a_index+=[x[0] for x in b]
    a_column+=[x[1] for x in b]
    b=[]

print(h*w-water[0][0]-count)