Dungeon Escape
Time limit1sMemory limit128 MB
Find the shortest path from room 1 to room N in an infinite square spiral graph, using standard passages plus given extra shortcut edges derived from spiral geometry.
- Level
Hard8 of 10
- Topics
- Shortest path, BFS, Math, Graph
- Solved
- No attempts yet
Problem
Brave Sir Robin has been imprisoned in a dungeon by an evil king. The dungeon has infinitely many cube-shaped rooms separated by thick stone walls. Consecutive rooms are connected by passages, and when viewed from above the rooms form the following square spiral.
After a large earthquake, some walls collapsed and additional passages opened between adjacent rooms that had previously been separated by a wall.
Sir Robin starts in room 1. The dungeon exit is in room N. Because a dragon guards the dungeon, Sir Robin wants to leave using as few passages as possible.
Given N and the list of newly opened passages, determine the minimum number of passages Sir Robin must traverse to reach the exit.
Input
The first line contains an integer N (1 <= N <= 10^15), the room containing the exit.
The second line contains an integer K (1 <= K <= 100000), the number of newly opened passages.
Each of the next K lines contains an integer B (4 <= B <= 10^15). This means that a new passage connects two adjacent rooms A and B, where A < B. The value A is not given, but it is uniquely determined by B. For instance, if B is 20, then A is 7. Some rooms, such as 2, 3, 5, 7, 10, and 13, can never appear as B.
Output
Print one integer: the minimum number of passages Sir Robin must traverse to reach the exit.
Explanation
For the first visible test, the dungeon after the earthquake looks like this.
One shortest route is 1-4-15-14-13-30-31, which uses 6 passages.