It took me too long to read the prompt and see that without the shortcuts, it’s a single path. I wasted too much time on search algorithms.

P1: Here’s what I did: Walk the path. Every time you hit a new grid, check if the two shortcuts you can take will save you 100 ps.

To calculate the shortcut saving:

If you index every grid position on the main path from 0, then it takes X ps to reach position X, The time it takes to travel from start to X, then a shortcut to Y, then from Y to the end, is X + 1 + (main path length - Y). The time saved is then just Y - X - 1, modulo maybe like 5 fence post errors.

P2. The prompt wasn’t really clear about whether or not cheating meant you can only travel through one set of walls before your cheat ends, or if it meant you could just move through walls for 20ps to wherever you could reach. Turns out, it’s the latter.

The above formula is then a special case of Y - X - manhattan distance(X, Y).