Submission #4044309

---

Source Code Expand

from queue import Queue

inf = 10 ** 20

def bfs(H, W, s):
    d = [[inf for i in range(W)] for j in range(H)]
    q = Queue()

    d[0][0] = 1
    q.put([0, 0])

    dx = (0, -1, 1, 0)
    dy = (-1, 0, 0, 1)

    while not q.empty():
        p = q.get()
        x = p[0]
        y = p[1]
        for i in range(4):
            nx = x + dx[i]
            ny = y + dy[i]
            if(nx >= 0 and nx < H and ny >= 0 and ny < W):
                if(s[nx][ny] == '.' and d[x][y] + 1 < d[nx][ny]):
                    d[nx][ny] = d[x][y] + 1
                    q.put([nx, ny])

    return d[H-1][W-1]

H, W = map(int, input().split())
s = []
wnum = 0
for i in range(H):
    s.append(input())
    for j in range(W):
        if(s[i][j] == "."):
            wnum += 1
d = bfs(H, W, s)
if(d == inf):
    print("-1")
else:
    print(wnum - d)

Submission Info

Judge Result