PAST2H
https://gyazo.com/d8cd95f94d454f735f18cfccd5356534
Thoughts.
Troublesome to go through the same squares over and over again, want to avoid getting stuck in an endless loop when it is unreachable.
Think of it as having a floor of 0-9, not two dimensions.
Move one step from floor i and there is a staircase going up the floor only when the destination is i+1
Shortest path problem from S on floor 0 to G on floor 9
That's not the official explanation.
Putting some time aside to think about it.
Dijkstra method, so the edge can have a cost, so instead of "move one step from floor i and there is a staircase going up the floor only when the destination is i+1", I made it "the number i on floor i has an edge with cost 0 that goes up from the floor below". Once the graph is constructed, just use the Dijkstra method to find the shortest distance.
AC
code:python
def solve(HEIGHT, WIDTH, data):
from collections import defaultdict
edges = defaultdict(dict)
W = WIDTH
H = HEIGHT
for level in range(10):
for y in range(HEIGHT):
for x in range(WIDTH):
pos = x + y * WIDTH + level * WIDTH * HEIGHT
if x < W - 1:
if x > 0:
if y < H - 1:
if y > 0:
if v == "S":
if level == 0:
start = pos
elif v == "G":
if level == 9:
goal = pos
else:
v = int(v)
if v == level:
return one_to_one(start, goal, 10 * W * H, edges)
The official explanation is required by dynamic programming.
Computationally, Dijkstra is lighter.
---
This page is auto-translated from /nishio/PAST2H. If you looks something interesting but the auto-translated English is not good enough to understand it, feel free to let me know at @nishio_en. I'm very happy to spread my thought to non-Japanese readers.