ABC088 D - Grid Repainting - 競プロ

ABC088 D - Grid Repainting

https://atcoder.jp/contests/abc088/tasks/abc088_d

提出

code: python

from collections import deque

h, w = map(int, input().split())

s = list(input()) for _ in range(h)

visited = list(False for _ in range(w)) for _ in range(h)

que = deque(0, 0)

while (len(que)):

now = que.popleft()

for i, j in -1, 0], 0, 1, 0, -1, [1 ,0:

go = [now0 + i, now1 + j]

if go == h-1, w-1:

break

if go0 < 0 or go0 >= h or go1 < 0 or go1 >= w:

continue

if s[go0][go1] == '#':

continue

if visited[go0][go1] == False:

que.append([go0, go1])

visited[go0][go1] = True

ans = 0

for i in range(h):

for j in range(w):

if (sij == "." and visitedij == False):

ans += 1

print(ans)

解答

code: python

from collections import deque

INF = 10**5

H, W = map(int,input().split())

S = input() for _ in range(H)

cntSharp = 0

for i in range(H):

cntSharp += Si.count("#")

dis = [INF*W for _ in range(H)]

dis00 = 0

P = deque([])

P.append((0,0))

while P:

p = P.popleft()

x,y = p0, p1

for i in range(4):

nx,ny = x + dxi, y + dyi

if 0 <= nx and 0 <= ny and nx <= H-1 and ny <= W-1 and Snxny =="." and disnxny == INF:

disnxny = disxy + 1

P.append((nx,ny))

if disH-1W-1 == INF:

print(-1)

else:

print(H*W - disH-1W-1 - cntSharp - 1)

テーマ

蟻本 2-1 迷路の最短路