Created
February 28, 2018 16:04
-
-
Save ytakashina/cb6ba499af0bc03a7e224b1af8150c77 to your computer and use it in GitHub Desktop.
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
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