ABC 088 D Grid Repainting

qiita.com

続き。

atcoder.jp

ねむみ。

from collections import deque


def main():
    h, w = [int(i) for i in input().split()]
    f = []
    c_of_sharp = 0
    for i in range(h):
        line = list(input())
        for c in line:
            if c == '#':
                c_of_sharp += 1
        f.append(line)
    sy, sx = (0, 0)
    q = deque([[sy, sx]])
    BIG = 100000
    f2 = [[BIG for i in range(w)] for j in range(h)]
    f2[0][0] = 0
    s = True

    while q:
        y, x = q.pop()
        if (y, x) == (h-1, w-1):
            break
        for dy, dx in [[-1, 0], [1, 0], [0, -1], [0, 1]]:
            if 0 <= y+dy < h and 0 <= x+dx < w and f2[y+dy][x+dx] == BIG and \
                f[y+dy][x+dx] != '#':
                f2[y+dy][x+dx] = f2[y][x]+1
                q.appendleft([y+dy, x+dx])
    else:
        s = False
        print(-1)

    if s:
        print(h*w-f2[h-1][w-1]-c_of_sharp-1)


if __name__ == '__main__':
    main()