ABC 088 D Grid Repainting
続き。
ねむみ。
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()