1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
|
def get_neighbors(grid, current):
neighbors = []
y, x = current
cur_height = ord(grid[y][x])
if (grid[y][x] == "S"):
cur_height = ord("a")
for i in range(-1, 2):
for j in range(-1, 2):
if i == 0 and j == 0 or (i != 0 and j != 0):
continue
if (y + i) < 0 or (y + i) >= len(grid):
continue
if (x + j) < 0 or (x + j) >= len(grid[y + i]):
continue
new_height = ord(grid[y + i][x + j])
if (grid[y + i][x + j] == "E"):
new_height = ord("z")
if abs(new_height - cur_height) <= 1 or new_height <= cur_height:
neighbors.append((y + i, x + j))
return neighbors
def bfs(grid, start, end):
queue = []
queue.append(start)
visited = {}
visited[start] = 0
while queue:
current = queue.pop(0)
if current == end:
return visited[current]
for neighbor in get_neighbors(grid, current):
if neighbor not in visited:
queue.append(neighbor)
visited[neighbor] = visited[current] + 1
return False
def main():
file = open("input", "r")
grid = file.readlines()
file.close()
start = (0, 0)
end = (0, 0)
for i in range(len(grid)):
for j in range(len(grid[i])):
if grid[i][j] == "S":
start = (i, j)
elif grid[i][j] == "E":
end = (i, j)
best = bfs(grid, start, end)
print(best)
for i in range(len(grid)):
for j in range(len(grid[i])):
if grid[i][j] == "a":
this_as_start = bfs(grid, (i, j), end)
if this_as_start and this_as_start < best:
best = this_as_start
print(best)
if __name__ == "__main__":
main()
|
