Pathfinding
SRM 345 · 2007-04-21 · by rusolis
Problem Statement
Recently you have been working on the pathfinding module for your AI system. Your objective is to find the shortest path for an agent that wants to travel between two points on a plane. The agent will start at the point (0,0), and travel to the point (x,y). You decided that the agent will move either on horizontal of vertical lines such that, at every moment, at least one coordinate of the agent is an integer.
There is yet another restriction however. Each line will only allow movement in one direction. All horizontal lines with odd y-coordinates will be directed toward decreasing values of x, and all other horizontal lines toward increasing values of x. Similarly, all vertical lines with odd x-coordinates will be directed toward decreasing values of y, and all other vertical lines toward increasing values of y.
Given x and y, return the distance that the agent must travel.
Constraints
- x and y will both be between -10^6 and 10^6, inclusive.
0 -4 Returns: 8
A possible path from (0,0) to (0,-4) is through the points (1,0), (1,-3), (-1,-3) and (-1,-4).
5 -4 Returns: 9
5 4 Returns: 9
-1 -4 Returns: 7
-100 -100 Returns: 204
Submissions are judged against all 141 archived test cases, of which 5 are shown here. Case numbers match the judge’s.
Language: C++17 · define a public class Pathfinding with a public method int getDirections(int x, int y) · 141 test cases · 2 s / 256 MB per case