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())
data = []
for _ in range(h):
    row = input()
    data.append(row)

all_black = 0
mark = [[0] * w for _ in range(h)]
short_step = [[9999] * w for _ in range(h)]

for i in range(h):
    for j in range(w):
        if data[i][j] == '#':
            all_black += 1
            mark[i][j] = 1

step = 0


def run(i, j):
    # print(i, j)
    global step
    # global res
    # if i - 1 < 0 or i + 1 > h - 1 or j - 1 < 0 or j + 1 > w - 1:
    #     return
    if 0 <= i < h and 0 <= j < w:
        if i < h - 1 and j == w - 1:
            return
        step += 1
        mark[i][j] = 1
        if short_step[i][j] > step:
            short_step[i][j] = step

        if i + 1 < h and mark[i + 1][j] == 0 and short_step[i][j] + 1 < short_step[i + 1][j]:
            # step += 1
            # mark[i + 1][j] = 1
            run(i + 1, j)
            # mark[i + 1][j] = 0
            # step -= 1

        if j + 1 < w and mark[i][j + 1] == 0 and short_step[i][j] + 1 < short_step[i][j + 1]:
            run(i, j + 1)
        if i - 1 >= 0 and mark[i - 1][j] == 0 and short_step[i][j] + 1 < short_step[i - 1][j]:
            run(i - 1, j)

        if j - 1 >= 0 and mark[i][j - 1] == 0 and short_step[i][j] + 1 < short_step[i][j - 1]:
            run(i, j - 1)

        step -= 1
        mark[i][j] = 0


if data[0][0] == '#' or data[h - 1][w - 1] == '#':
    print(-1)
else:
    run(0, 0)
    # if res == 9999:
    #     print(-1)
    # else:
    if short_step[h - 1][w - 1] == 9999:
        print(-1)
    else:
        print(h * w - all_black - short_step[h - 1][w - 1])

Submission status: Runtime Error

Solution code:

h, w = map(int, input().split())
data = []
for _ in range(h):
    row = input()
    data.append(row)

all_black = 0
mark = [[0] * w for _ in range(h)]
short_step = [[9999] * w for _ in range(h)]
# print(data)
# print(mark)
# print(all_black)
for i in range(h):
    for j in range(w):
        if data[i][j] == '#':
            all_black += 1
            mark[i][j] = 1

# print(data)
# print(mark)
# print(all_black)
step = 0
# res = 9999


def run(i, j):
    # print(i, j)
    global step
    # global res
    # if i - 1 < 0 or i + 1 > h - 1 or j - 1 < 0 or j + 1 > w - 1:
    #     return
    if i < h-1 and j == w-1:
        return
    step += 1
    mark[i][j] = 1
    if short_step[i][j] > step:
        short_step[i][j] = step
    # if i == h - 1 and j == w - 1:
    #     print(short_step[i][j])
    #     if res > step:
    #         res = step
    #         # print(res)
    #     step -= 1
    #     mark[i][j] = 0
    #     return

    if i + 1 < h and mark[i + 1][j] == 0 and short_step[i][j] + 1 < short_step[i + 1][j]:
        # step += 1
        # mark[i + 1][j] = 1
        run(i + 1, j)
        # mark[i + 1][j] = 0
        # step -= 1

    if j + 1 < w and mark[i][j + 1] == 0 and short_step[i][j] + 1 < short_step[i][j + 1]:
        # step += 1
        # mark[i][j + 1] = 1
        run(i, j + 1)
        # mark[i][j + 1] = 0
        # step -= 1

    if i - 1 >= 0 and mark[i - 1][j] == 0 and short_step[i][j] + 1 < short_step[i - 1][j]:
        # step += 1
        # mark[i - 1][j] = 1
        run(i - 1, j)
        # mark[i - 1][j] = 0
        # step -= 1

    if j - 1 >= 0 and mark[i][j - 1] == 0 and short_step[i][j] + 1 < short_step[i][j - 1]:
        #     step += 1
        # mark[i][j - 1] = 1
        run(i, j - 1)
        # mark[i][j - 1] = 0
        # step -= 1

    step -= 1
    mark[i][j] = 0

if data[0][0] == '#' or data[h -1][w-1] == '#':
    print(-1)
else:
    run(0, 0)
    # if res == 9999:
    #     print(-1)
    # else:
    if short_step[h-1][w-1] == 9999:
        print(-1)
    else:
        print(h * w - all_black - short_step[h-1][w-1])

Submission status: Runtime Error

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

all_black = 0
mark = [[0] * w for _ in range(h)]
short_step = [[9999] * w for _ in range(h)]
# print(data)
# print(mark)
# print(all_black)
for i in range(h):
    for j in range(w):
        if data[i][j] == '#':
            all_black += 1
            mark[i][j] = 1

# print(data)
# print(mark)
# print(all_black)
step = 0
res = 9999


def run(i, j):
    # print(i, j)
    global step
    global res
    # if i - 1 < 0 or i + 1 > h - 1 or j - 1 < 0 or j + 1 > w - 1:
    #     return
    if i < h-1 and j == w-1:
        return
    step += 1
    mark[i][j] = 1
    if short_step[i][j] > step:
        short_step[i][j] = step
    if i == h - 1 and j == w - 1:
        # print(step)
        if res > step:
            res = step
            # print(res)
        step -= 1
        mark[i][j] = 0
        return

    if i + 1 < h and mark[i + 1][j] == 0 and short_step[i][j] + 1 < short_step[i + 1][j]:
        # step += 1
        # mark[i + 1][j] = 1
        run(i + 1, j)
        # mark[i + 1][j] = 0
        # step -= 1

    if j + 1 < w and mark[i][j + 1] == 0 and short_step[i][j] + 1 < short_step[i][j + 1]:
        # step += 1
        # mark[i][j + 1] = 1
        run(i, j + 1)
        # mark[i][j + 1] = 0
        # step -= 1

    if i - 1 >= 0 and mark[i - 1][j] == 0 and short_step[i][j] + 1 < short_step[i - 1][j]:
        # step += 1
        # mark[i - 1][j] = 1
        run(i - 1, j)
        # mark[i - 1][j] = 0
        # step -= 1

    if j - 1 >= 0 and mark[i][j - 1] == 0 and short_step[i][j] + 1 < short_step[i][j - 1]:
        #     step += 1
        # mark[i][j - 1] = 1
        run(i, j - 1)
        # mark[i][j - 1] = 0
        # step -= 1

    step -= 1
    mark[i][j] = 0

if data[0][0] == '#' or data[h -1][w-1] == '#':
    print(-1)
else:
    run(0, 0)
    if res == 9999:
        print(-1)
    else:
        print(h * w - all_black - res)

Submission status: Runtime Error

Solution code:
try:
    h, w = map(int, input().split())
    data = []
    for _ in range(h):
        row = input()
        data.append(row)

    all_black = 0
    mark = [[0] * w for _ in range(h)]
    short_step = [[9999] * w for _ in range(h)]
    # print(data)
    # print(mark)
    # print(all_black)
    for i in range(h):
        for j in range(w):
            if data[i][j] == '#':
                all_black += 1
                mark[i][j] = 1

    # print(data)
    # print(mark)
    # print(all_black)
    step = 0
    res = 9999


    def run(i, j):
        # print(i, j)
        global step
        global res
        # if i - 1 < 0 or i + 1 > h - 1 or j - 1 < 0 or j + 1 > w - 1:
        #     return
        if i < h-1 and j == w-1:
            return
        step += 1
        mark[i][j] = 1
        if short_step[i][j] > step:
            short_step[i][j] = step
        if i == h - 1 and j == w - 1:
            # print(step)
            if res > step:
                res = step
                # print(res)
            step -= 1
            mark[i][j] = 0
            return

        if i + 1 < h and mark[i + 1][j] == 0 and short_step[i][j] + 1 < short_step[i + 1][j]:
            # step += 1
            # mark[i + 1][j] = 1
            run(i + 1, j)
            # mark[i + 1][j] = 0
            # step -= 1

        if j + 1 < w and mark[i][j + 1] == 0 and short_step[i][j] + 1 < short_step[i][j + 1]:
            # step += 1
            # mark[i][j + 1] = 1
            run(i, j + 1)
            # mark[i][j + 1] = 0
            # step -= 1

        if i - 1 >= 0 and mark[i - 1][j] == 0 and short_step[i][j] + 1 < short_step[i - 1][j]:
            # step += 1
            # mark[i - 1][j] = 1
            run(i - 1, j)
            # mark[i - 1][j] = 0
            # step -= 1

        if j - 1 >= 0 and mark[i][j - 1] == 0 and short_step[i][j] + 1 < short_step[i][j - 1]:
            #     step += 1
            # mark[i][j - 1] = 1
            run(i, j - 1)
            # mark[i][j - 1] = 0
            # step -= 1

        step -= 1
        mark[i][j] = 0

    if data[0][0] == '#' or data[h -1][w-1] == '#':
        print(-1)
        return
    else:
        run(0, 0)
    if res == 9999:
        print(-1)
    else:
        print(h * w - all_black - res)
except Exception as e:
    print(e)

Submission status: Runtime Error

Solution code:

h, w = map(int, input().split())
data = []
for _ in range(h):
    row = input()
    data.append(row)

all_black = 0
mark = [[0] * w for _ in range(h)]
short_step = [[9999] * w for _ in range(h)]
# print(data)
# print(mark)
# print(all_black)
for i in range(h):
    for j in range(w):
        if data[i][j] == '#':
            all_black += 1
            mark[i][j] = 1

# print(data)
# print(mark)
# print(all_black)
step = 0
res = 9999


def run(i, j):
    # print(i, j)
    global step
    global res
    # if i - 1 < 0 or i + 1 > h - 1 or j - 1 < 0 or j + 1 > w - 1:
    #     return
    if i < h-1 and j == w-1:
        return
    step += 1
    mark[i][j] = 1
    if short_step[i][j] > step:
        short_step[i][j] = step
    if i == h - 1 and j == w - 1:
        # print(step)
        if res > step:
            res = step
            # print(res)
        step -= 1
        mark[i][j] = 0
        return

    if i + 1 < h and mark[i + 1][j] == 0 and short_step[i][j] + 1 < short_step[i + 1][j]:
        # step += 1
        # mark[i + 1][j] = 1
        run(i + 1, j)
        # mark[i + 1][j] = 0
        # step -= 1

    if j + 1 < w and mark[i][j + 1] == 0 and short_step[i][j] + 1 < short_step[i][j + 1]:
        # step += 1
        # mark[i][j + 1] = 1
        run(i, j + 1)
        # mark[i][j + 1] = 0
        # step -= 1

    if i - 1 >= 0 and mark[i - 1][j] == 0 and short_step[i][j] + 1 < short_step[i - 1][j]:
        # step += 1
        # mark[i - 1][j] = 1
        run(i - 1, j)
        # mark[i - 1][j] = 0
        # step -= 1

    if j - 1 >= 0 and mark[i][j - 1] == 0 and short_step[i][j] + 1 < short_step[i][j - 1]:
        #     step += 1
        # mark[i][j - 1] = 1
        run(i, j - 1)
        # mark[i][j - 1] = 0
        # step -= 1

    step -= 1
    mark[i][j] = 0


run(0, 0)
if res == 9999:
    print(-1)
else:
    print(h * w - all_black - res)

Submission status: Runtime Error

Solution code:

h, w = map(int, input().split())
data = []
for _ in range(h):
    row = input()
    data.append(row)

all_black = 0
mark = [[0] * w for _ in range(h)]
short_step = [[999999999999999999] * w for _ in range(h)]
# print(data)
# print(mark)
# print(all_black)
for i in range(h):
    for j in range(w):
        if data[i][j] == '#':
            all_black += 1
            mark[i][j] = 1

# print(data)
# print(mark)
# print(all_black)
step = 0
res = 99999999999999999999999999999999


def run(i, j):
    # print(i, j)
    global step
    global res
    # if i - 1 < 0 or i + 1 > h - 1 or j - 1 < 0 or j + 1 > w - 1:
    #     return
    if i < h-1 and j == w-1:
        return
    step += 1
    mark[i][j] = 1
    if short_step[i][j] > step:
        short_step[i][j] = step
    if i == h - 1 and j == w - 1:
        # print(step)
        if res > step:
            res = step
            # print(res)
        step -= 1
        mark[i][j] = 0
        return

    if i + 1 < h and mark[i + 1][j] == 0 and short_step[i][j] + 1 < short_step[i + 1][j]:
        # step += 1
        # mark[i + 1][j] = 1
        run(i + 1, j)
        # mark[i + 1][j] = 0
        # step -= 1

    if j + 1 < w and mark[i][j + 1] == 0 and short_step[i][j] + 1 < short_step[i][j + 1]:
        # step += 1
        # mark[i][j + 1] = 1
        run(i, j + 1)
        # mark[i][j + 1] = 0
        # step -= 1

    if i - 1 >= 0 and mark[i - 1][j] == 0 and short_step[i][j] + 1 < short_step[i - 1][j]:
        # step += 1
        # mark[i - 1][j] = 1
        run(i - 1, j)
        # mark[i - 1][j] = 0
        # step -= 1

    if j - 1 >= 0 and mark[i][j - 1] == 0 and short_step[i][j] + 1 < short_step[i][j - 1]:
        #     step += 1
        # mark[i][j - 1] = 1
        run(i, j - 1)
        # mark[i][j - 1] = 0
        # step -= 1

    step -= 1
    mark[i][j] = 0


run(0, 0)
if res == 99999999999999999999999999999999:
    print(-1)
else:
    print(h * w - all_black - res)

Submission status: Runtime Error

Solution code:

h, w = map(int, input().split())
data = []
for _ in range(h):
    row = input()
    data.append(row)

all_black = 0
mark = [[0] * w for _ in range(h)]
short_step = [[999999999999999999] * w for _ in range(h)]
# print(data)
# print(mark)
# print(all_black)
for i in range(h):
    for j in range(w):
        if data[i][j] == '#':
            all_black += 1
            mark[i][j] = 1

# print(data)
# print(mark)
# print(all_black)
step = 0
res = 99999999999999999999999999999999


def run(i, j):
    # print(i, j)
    global step
    global res
    # if i - 1 < 0 or i + 1 > h - 1 or j - 1 < 0 or j + 1 > w - 1:
    #     return
    if i < h-1 and j == w-1:
        return
    step += 1
    mark[i][j] = 1
    if short_step[i][j] > step:
        short_step[i][j] = step
    if i == h - 1 and j == w - 1:
        # print(step)
        if res > step:
            res = step
            # print(res)
        step -= 1
        mark[i][j] = 0
        return

    if i + 1 < h and mark[i + 1][j] == 0 and short_step[i][j] + 1 < short_step[i + 1][j]:
        # step += 1
        # mark[i + 1][j] = 1
        run(i + 1, j)
        # mark[i + 1][j] = 0
        # step -= 1

    if j + 1 < w and mark[i][j + 1] == 0 and short_step[i][j] + 1 < short_step[i][j + 1]:
        # step += 1
        # mark[i][j + 1] = 1
        run(i, j + 1)
        # mark[i][j + 1] = 0
        # step -= 1

    if i - 1 >= 0 and mark[i - 1][j] == 0 and short_step[i][j] + 1 < short_step[i - 1][j]:
        # step += 1
        # mark[i - 1][j] = 1
        run(i - 1, j)
        # mark[i - 1][j] = 0
        # step -= 1

    if j - 1 >= 0 and mark[i][j - 1] == 0 and short_step[i][j] + 1 < short_step[i][j - 1]:
        #     step += 1
        # mark[i][j - 1] = 1
        run(i, j - 1)
        # mark[i][j - 1] = 0
        # step -= 1

    step -= 1
    mark[i][j] = 0


run(0, 0)
print(h * w - all_black - res)

Submission status: Runtime Error

Solution code:
#create date: 2020-07-03 14:46

import sys
stdin = sys.stdin
from collections import deque

def ns(): return stdin.readline().rstrip()
def ni(): return int(ns())
def na(): return list(map(int, stdin.readline().split()))

def main():
    h, w = na()
    g = [[1] * (w+2)]
    white = 0
    for i in range(h):
        r = ns()
        white += r.count(".")
        g.append([1] + [1 if s=="#" else 0 for s in r] + [1])
    g.append([1] * (w+2))
    q = deque([[1,1]])
    move = ((1, 0), (-1, 0), (0, 1), (1, 0))
    while q:
        x, y = q.popleft()
        for dx, dy in move:
            nx, ny = x + dx, y + dy
            if g[nx][ny] > 0:
                continue
            g[nx][ny] = g[x][y] + 1
            q.append((nx, ny))
    if g[h][w] = 0:
        print(-1)
    else:
        print(white - g[h][w] - 1)



if __name__ == "__main__":
    main()

Submission status: Runtime Error

Solution code:
from collections import deque
h, w = map(int, input().split())
chiz = [[] for _ in range(w)]
cnt = 0
for _ in range(h):
    tmp_list = input()
    for i in range(w):
        if tmp_list[i]=='.':
            cnt += 1
        chiz[i].append(tmp_list[i])
dq = deque([(0,0)])
chiz[0][0] = 0
while dq:
    i,j = dq.popleft()
    for e in [(1,0),(-1,0),(0,-1),(0,1)]:
        if i+e[0]>=0 and i+e[0]<w and j+e[1]>=0 and j+e[1]<h:
            if chiz[i+e[0]][j+e[1]] == '.':
                chiz[i+e[0]][j+e[1]] = chiz[i][j] + 1
                dq.append((i+e[0],j+e[1]))
print(cnt-chiz[w-1][h-1]-1)

Submission status: Runtime Error

Solution code:
from collections import deque


def bfs(sy, sx, gy, gx):
    # yが下方向，xが右方向
    d = [[float("inf")] * w for _ in range(h)]

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

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

    while que:

        p = que.popleft()

        if p[0] == gy and p[1] == gx:
            break

        for i in range(4):
            ny = p[0] + dy[i]
            nx = p[1] + dx[i]

            if 0 <= ny < h and 0 <= nx < w and maze[ny][nx] != "#" and d[ny][nx] == float("inf"):
                que.append((ny, nx))
                d[ny][nx] = d[p[0]][p[1]] + 1
 
    if d[gy][gx] == float("inf"):
        return -1
    else:
        return [gy][gx]


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

res = 0
for y in range(h):
    for x in range(w):
        if maze[y][x] == '#':
            res += 1

dis = bfs(0, 0, h - 1, w - 1)

if dis == -1:
    print(-1)
else:
    print(h * w - res - dis - 1)

Submission status: Runtime Error

Solution code:
from collections import deque
H,W=map(int,input().split())
S=[]
count=0
for _ in range (H):
    A=list(input())
    for a in A:
        if a=='.':
            count+=1
    S.append(A)

mas=deque([(0,0,0)])
while mas:
    y,x,n=mas.popleft()
    if 0<=y<=H-1 and 0<=x<=W-1:
        if S[y][x]=='.':
            S[y][x]=n
            mas.append((y+1,x,n+1))
            mas.append((y,x+1,n+1))
            mas.append((y-1,x,n+1))
            mas.append((y,x-1,n+1))
short=S[H-1][W-1]
print(count-(short+1))

Submission status: Runtime Error

Solution code:
import collections

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

z = [["b"] * W for _ in range(H)] #チェックしたマスはb(before)からa(after)にする
black = 0
for i in range(H):
    black += s[i].count("#") #最初の黒の数を数える
v = [[1,0] [0,1] [-1,0] [0,-1]] #動き方4パターン(↓ → ↑ ←)
que = collections.deque() #調べる候補リスト #調べ終わった要素は消す

#まず[0,0]
z[0][0] = "a"
s[0][0] = 1 #何歩で来れたかを代入していく #最初は1
que.append([0,0]) #最初の候補は[0,0]

#最短ルートを探す
while len(que) != 0: #候補がなくなるまで繰り返す
    i = que.popleft() #候補のうち1つを取り出し、リストから消す
    for dy, dx in v: #4パターンの動き方を考える
        y = i[0] + dy
        x = i[1] + dx
        if (0<=y<H and 0<=x<W and s[y][x]=="." and z[y][x]=="b"):
            z[y][x] == "a"
            s[y][x] == s[i[0]][i[1]] + 1
            que.append([y,x]) #進んだマスを新しく候補に入れる

if s[-1][-1] == ".": #[H,W]のマスに数字が入ってない→ゴールできない
    print(-1)
else: #「消せる白の最大数」=「全マス」-「黒マス」-「最短ルート」
    print(H*W - black - s[-1][-1])

Submission status: Runtime Error

Solution code:
#%%
W, H = [int(i) for i in input().split()]
maze = [[] for _ in range(H)]

num_black = 0
for i in range(H):
    temp = input()
    for j in temp:
        maze[i].append(j)
        if j == "#":
            num_black += 1

#%%
import copy, collections

maze_copy = copy.deepcopy(maze)
color = [["W"] * W for _ in range(H)]


def BFS(Y, X):
    vec = [[1, 0], [-1, 0], [0, 1], [0, -1]]
    color[Y][X] = "G"
    que = collections.deque()
    maze_copy[Y][X] = 1
    que.append([Y, X])

    while len(que) != 0:
        u = que.popleft()
        if u[0] == H - 1 and u[1] == W - 1:
            return maze_copy[u[0]][u[1]]
        for y, x in vec:
            temp_x = u[1] + x
            temp_y = u[0] + y
            if (0 <= temp_x < W and 0 <= temp_y < H
                    and maze_copy[temp_y][temp_x] == "." and color[temp_y][temp_x] == "W"):
                color[temp_y][temp_x] = "G"
                maze_copy[temp_y][temp_x] = maze_copy[u[0]][u[1]] + 1
                que.append([temp_y, temp_x])
    
    return  -1

ans = BFS(0, 0)
if ans == -1:
    print(-1)
else:
    print(W * H - num_black - ans)

Submission status: Runtime Error

Solution code:
#%%
W, H = [int(i) for i in input().split()]
maze = [[] for _ in range(H)]

num_black = 0
for i in range(H):
    temp = input()
    for j in temp:
        maze[i].append(j)
        if j == "#":
            num_black += 1

#%%
import copy, collections

maze_copy = copy.deepcopy(maze)
color = [["W"] * W for _ in range(H)]


def BFS(Y, X):
    vec = [[1, 0], [-1, 0], [0, 1], [0, -1]]
    color[Y][X] = "G"
    que = collections.deque()
    maze_copy[Y][X] = 1
    que.append([Y, X])

    while len(que) != 0:
        u = que.popleft()
        for y, x in vec:
            temp_x = u[1] + x
            temp_y = u[0] + y
            if (0 <= temp_x < W and 0 <= temp_y < H
                    and maze_copy[temp_y][temp_x] == "." and color[temp_y][temp_x] == "W"):
                color[temp_y][temp_x] = "G"
                maze_copy[temp_y][temp_x] = maze_copy[u[0]][u[1]] + 1
                que.append([temp_y, temp_x])


BFS(0, 0)
if maze_copy[-1][-1] == ".":
    print(-1)
else:
    print(W * H - num_black - maze_copy[-1][-1])

Submission status: Runtime Error

Solution code:
# %%
W, H = [int(i) for i in input().split()]
maze = [[] for _ in range(H)]

num_black = 0
for i in range(H):
    temp = input()
    for j in temp:
        maze[i].append(j)
        if j == "#":
            num_black += 1

# %%
import copy, collections

maze_copy = copy.deepcopy(maze)
maze_copy[-1][-1] = -1
color = [["W"] * W for _ in range(H)]


def BFS(Y, X):
    vec = [[1, 0], [-1, 0], [0, 1], [0, -1]]
    color[Y][X] = "G"
    que = collections.deque()
    maze_copy[Y][X] = 1
    que.append([Y, X])

    while len(que) != 0:
        u = que.popleft()
        for y, x in vec:
            temp_x = u[1] + x
            temp_y = u[0] + y
            if (0 <= temp_x < W and 0 <= temp_y < H
                    and maze_copy[temp_y][temp_x] == "." and color[temp_y][temp_x] == "W"):
                color[temp_y][temp_x] = "G"
                maze_copy[temp_y][temp_x] = maze_copy[u[0]][u[1]] + 1
                que.append([temp_y, temp_x])


BFS(0, 0)
if maze_copy[-1][-1] == -1:
    print(-1)
else:
    print(W * H - num_black - maze_copy[-1][-1])

Submission status: Runtime Error

Solution code:
# %%
W, H = [int(i) for i in input().split()]
maze = [[] for _ in range(H)]

num_black = 0
for i in range(H):
    temp = input()
    for j in temp:
        maze[i].append(j)
        if j == "#":
            num_black += 1

# %%
import copy, collections

maze_copy = copy.deepcopy(maze)
color = [["W"] * W for _ in range(H)]


def BFS(Y, X):
    vec = [[1, 0], [-1, 0], [0, 1], [0, -1]]
    color[Y][X] = "G"
    que = collections.deque()
    maze_copy[Y][X] = 1
    que.append([Y, X])

    while len(que) != 0:
        u = que.popleft()
        for y, x in vec:
            temp_x = u[1] + x
            temp_y = u[0] + y
            if (0 <= temp_x < W and 0 <= temp_y < H
                    and maze_copy[temp_y][temp_x] == "." and color[temp_y][temp_x] == "W"):
                color[temp_y][temp_x] = "G"
                maze_copy[temp_y][temp_x] = maze_copy[u[0]][u[1]] + 1
                que.append([temp_y, temp_x])


BFS(0, 0)
print(W * H - num_black - maze_copy[-1][-1])

Submission status: Runtime Error

Solution code:
h,w=map(int,input().split())
l=[list(map(int,input().split())) for _ in range(h)]
wcnt=0
for ll in l:
  wcnt+=ll.count('.')

visit=[[o]*w for _ in range(h)]
queue=[[0,0]]
g=[h-1,w-1]

while True:
  x,y=queue.pop(0)
  if [x,y]==g:
    print(wcnt-visit[x][y])
    exit()
  for i,j in [[1.0],[0,1],[-1,0],[0,-1]]:
    if 0<=x+i<h and 0<=y+j<w and visit[x+i][y+j]==0 and l[x+i][y+j]!='#':
      visit[x+i][y+j]=visit[x][y]+1
      queue.append([x+i,y+j])
print(-1)

Submission status: Runtime Error

Solution code:
import heapq as hp
import numpy as np

h, w = map(int, input().split())
s = np.array([list(input()) for _ in range(h)])
s = np.pad(s, 1, 'constant')
visited = np.zeros_like(s, dtype=np.bool)

judge = np.inf

q = []
hp.heappush(q, (0, 1, 1))

while h:
    cnt, y, x = hp.heappop(q)
    if y == h and x == w:
        judge = cnt
        break
    for dy, dx in [[0, 1], [1, 0], [-1, 0], [0, -1]]:
        ny, nx = y + dy, x + dx
        if s[ny, nx] == '.' and not visited[ny, nx]:
            visited[ny, nx] = True
            hp.heappush(q, (cnt + 1, ny, nx))

if judge == np.inf:
    print(-1)
else:
    print((s == '.').sum() - judge - 1)

Submission status: Runtime Error

Solution code:
from collections import deque
import itertools
def bfs(G,visited,sy,sx):
    queue=deque([[sy,sx]])
    visited[sy][sx]=0
    while queue:
        y,x=queue.popleft()
        if (y,x)== (H-1,W-1):
            return visited[y][x]
        for j,k in ([1,0],[0,1],[-1,0],[0,-1]):
            tmp_y,tmp_x = y+j,x+k
            if 0<=tmp_y<=H-1 and 0<=tmp_x<=W-1 and  G[tmp_y][tmp_x]!='#':
                if visited[tmp_y][tmp_x]==-1:
                    visited[tmp_y][tmp_x]=visited[y][x]+1
                    queue.append([tmp_y,tmp_x])
if __name__  =="__main__":
    H,W =map(int,input().split())
    G=[list(input()) for _ in range(H)]
    sy,sx =0,0
    dist=0
    tmp=0
    visited=[[-1]*W for _ in range(H)]
    dist=bfs(G,visited,sy,sx)
    print(list(itertools.chain.from_iterable(G)).count('.')-dist-1)

Submission status: Runtime Error

Solution code:
from collections import deque
H, W = map(int, input().split())
s = [list(input()) for _ in range(H)]
moves = ((1, 0), (0, 1), (0, -1), (-1, 0))

def bfs(sy, sx):
    q = deque([[sy, sx]])
    dist = [[float('inf')]*(W) for _ in range(H)]
    dist[sy][sx] = 0

    while q:
        y, x = q.popleft()
        for dy, dx in moves:
            ny = y + dy
            nx = x + dx
            if 0 <= ny < H and 0 <= nx < W and s[ny][nx] == '.' and dist[ny][nx] == float('inf'):
                dist[ny][nx] = dist[y][x] + 1
                q += [[ny, nx]]

    return dist

d = bfs(0, 0)

if d[-1][-1] == float('inf'):
    print(-1)
    exit()

ans = H*W 
for i in range(H):
    for j in range(W):
        if s[i][j] == '#':
            ans -= 1

ans -= d[-1][-1] + 1
print(ans

Submission status: Runtime Error

Solution code:
n,m = map(int,input().split())
from collections import deque
a = []
for _ in range(n):
    a.append(list(input()))

count = 0
for x in a:
    count += x.count("#")
#print(count)

b = [[100000 for i in range(m)] for i in range(n)]
#print(a)

x = [0, 0, -1, 1]
y = [-1, 1, 0, 0]

queue = deque([])
now = [0,0]
b[0][0] = 1
while now != [n-1, m-1]:
    for i in range(4):
        if now[0] + y[i] < 0 or now[0] + y[i] >= n or now[1] + x[i] < 0 or now[1] + x[i] >= m:
            continue
        if a[now[0]+y[i]][now[1]+x[i]] == '.':
            queue.append([now[0]+y[i],now[1]+x[i]])
        b[now[0]+y[i]][now[1]+x[i]] = min(b[now[0]][now[1]] + 1, b[now[0]+y[i]][now[1]+x[i]])
    a[now[0]][now[1]] = "#"
    now = queue.popleft()


ans = n * m - (b[n-1][m-1] + count)
print(ans)

Submission status: Runtime Error

Solution code:

H, W = map(int,input().split())
ARR = []

for i in range(H):
    ARR.append(input())


def calculate(h, w, arr):
    total = h * w
    distance = h + w - 1
    alreadyPaiting = 0

    for s in arr:
        a = Counter(list(s))
        b = a.get("#")

        if b != None:
            alreadyPaiting += b

    return total - distance - alreadyPaiting


result = calculate(H, W, ARR)

print(result)

Submission status: Runtime Error

Solution code:
from collections import deque


def bfs():
  d = [[float('inf')]* w for i 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 < h and 0 <= ny < w 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 i 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:

Submission status: Runtime Error

Solution code:
from collections import deque

def main():
    R,C= map(int,input().split())

    S = [0,0]

    mv = [[1,0],[-1,0],[0,-1],[0,1]]
    MAP = []
    flg = 0
    block = 0
    for _ in range(R):
        t = list(input())
        block += t.count('#')
        MAP.append(t)
    stack = deque([S])
    MAP_c = [[None]*C for _ in range(R)]
    MAP_c[0][0] = 1
    while stack:
        v = stack.popleft()
        for m in mv:
            u = [v[0]+m[0],v[1]+m[1]]
            if u[0] >=0 and u[0] < R and u[1] >= 0 and u[1] < C and MAP[u[0]][u[1]] == '.':
                MAP[u[0]][u[1]] = '#'
                MAP_c[u[0]][u[1]] = MAP_c[v[0]][v[1]] + 1
                stack.append(u)
                if u == [R-1,C-1]:
                    flg = 1

        if flg == 1:
            break

    a = MAP_c[R-1][C-1]
    print(R*C - a - block)


main()

Submission status: Runtime Error

Solution code:
from collections import deque

def main():
    R,C= map(int,input().split())

    S = [0,0]

    mv = [[1,0],[-1,0],[0,-1],[0,1]]
    MAP = []
    flg = 0
    block = 0
    for _ in range(R):
        t = list(input())
        block += t.count('#')
        MAP.append(t)
    stack = deque([S])
    MAP_c = [[None]*C for _ in range(R)]
    MAP_c[0][0] = 1
    while stack:
        v = stack.popleft()
        for m in mv:
            u = [v[0]+m[0],v[1]+m[1]]
            if u[0] >=0 and u[0] < R and u[1] > 0 and u[1] < C and MAP[u[0]][u[1]] == '.':
                MAP[u[0]][u[1]] = '#'
                MAP_c[u[0]][u[1]] = MAP_c[v[0]][v[1]] + 1
                stack.append(u)
                if u == [R-1,C-1]:
                    flg = 1

        if flg == 1:
            break

    a = MAP_c[R-1][C-1]
    print(R*C - a - block)


main()