aoc 15 part 1
unknown
python
3 years ago
1.3 kB
7
Indexable
import sys import queue def main(input_file=sys.stdin, output_file=sys.stdout): risk_level = [] for row in input_file.readlines(): risk_level.append([int(x) for x in list(row.strip())]) n = len(risk_level) # print(risk_level) # Dijkstra # Holds pairs of total distance, coordinate q = queue.PriorityQueue() visited = set() q.put((0, (0, 0))) while not q.empty(): next_dist, next_co = q.get() # print(next_dist, next_co) if next_co in visited: continue visited.add(next_co) # print(next_dist, next_co) if next_co == (n-1, n-1): output_file.write(str(next_dist)) return children = [] next_x, next_y = next_co if next_x - 1 >= 0: children.append((next_x-1, next_y)) if next_x + 1 < n: children.append((next_x+1, next_y)) if next_y - 1 >= 0: children.append((next_x, next_y-1)) if next_y + 1 < n: children.append((next_x, next_y+1)) for child_co in children: if child_co not in visited: c_x, c_y = child_co q.put((risk_level[c_x][c_y] + next_dist, child_co)) if __name__ == "__main__": main()
Editor is loading...