Skip to content

Instantly share code, notes, and snippets.

@ytakashina
Created February 28, 2018 16:04
Show Gist options
  • Star 1 You must be signed in to star a gist
  • Fork 2 You must be signed in to fork a gist
  • Save ytakashina/cb6ba499af0bc03a7e224b1af8150c77 to your computer and use it in GitHub Desktop.
Save ytakashina/cb6ba499af0bc03a7e224b1af8150c77 to your computer and use it in GitHub Desktop.
H, W = map(int, input().split())
maze = []
distances = []
n_aisle = 0
for i in range(H):
row = input()
maze.append(row)
distances.append([100000000 for i in range(W)])
n_aisle += row.count('.')
distances[0][0] = 0
directions = [(1, 0), (-1, 0), (0, 1), (0, -1)]
visited = [(0, 0)]
queue = [(0, 0)]
while len(queue) > 0:
y, x = queue.pop(0)
for dy, dx in directions:
y2, x2 = y + dy, x + dx
if y2 < 0 or y2 >= H or x2 < 0 or x2 >= W:
continue
if (y2, x2) in visited:
continue
if maze[y2][x2] == '.':
distances[y2][x2] = distances[y][x] + 1
visited.append((y2, x2))
queue.append((y2, x2))
if distances[H - 1][W - 1] == 100000000:
print(-1)
else:
print(n_aisle - distances[H - 1][W - 1] - 1)
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment