| 12345678910111213141516171819202122232425262728293031323334353637383940414243444546474849505152535455565758 |
- #!/usr/bin/env python3
- import sys
- from queue import PriorityQueue
- from dataclasses import dataclass
- class Bounds:
- width = 0
- height = 0
- @dataclass(order=True)
- class Pos:
- x: int
- y: int
- def bound(pos):
- return pos.x >= 0 and pos.y >= 0 and pos.x < Bounds.width and pos.y < Bounds.height
- def adjacent(pos):
- adjacents = []
- for i in range(-1, 2):
- for j in range(-1, 2):
- if i == j or i == -j: continue
- if bound(Pos(pos.x + j, pos.y + i)):
- adjacents.append(Pos(pos.x + j, pos.y + i))
- return adjacents
- risks = []
- costs = []
- visited = []
- for line in sys.stdin:
- risks.append([int(r) for r in line.rstrip('\n')])
- costs.append([sys.maxsize for r in line.rstrip('\n')])
- visited.append([False for r in line.rstrip('\n')])
- l = len(line.rstrip('\n'))
- if l > Bounds.width: Bounds.width = l
- h = len(risks)
- if h > Bounds.height: Bounds.height = h
- q = PriorityQueue()
- costs[0][0] = 0
- risks[0][0] = 0
- q.put((risks[0][0], Pos(0, 0)))
- while not q.empty():
- cost, pos = q.get()
- visited[pos.y][pos.x] = True
- for a in adjacent(pos):
- new_cost = cost + risks[a.y][a.x]
- if new_cost < costs[a.y][a.x]: costs[a.y][a.x] = new_cost
- if not visited[a.y][a.x]:
- q.put((new_cost, a))
- # results
- print(f'risk (cost so far)')
- print('\n'.join(['\t'.join([f'{c}({risks[y][x]})' for x, c in enumerate(row)]) for y, row in enumerate(costs)]))
- print(f'{costs[Bounds.height - 1][Bounds.width - 1]} is the lowest total risk of any path from top left (0, 0) to bottom right ({Bounds.height - 1}, {Bounds.width - 1})')
|
