MovingByPoints
TCO19 SRM 738 · 2018-09-29 · by wild_hamster
Problem Statement
You are given N points. The points are numbered from 0 to N-1. Point i has coordinates (X[i], Y[i]). Note that the given points are not necessarily distinct.
You have to move from point 0 to point N-1. You have to move in steps. In each step you can move by 1 unit of distance in one of the four cardinal directions. That is, if you are at coordinates (x,y), you can move to (x-1,y), (x+1,y), (x,y+1), or (x,y-1). Additionally, you can only step on points, you cannot enter coordinates that don't contain a point.
For the given N points it may be impossible to get from point 0 to point N-1 according to the above rules. Compute and return the smallest number of additional points that have to be added to the collection in order to be able to do that.
Constraints
- N will be between 1 and 500, inclusive.
- X and Y will each have exactly N elements.
- Each element of X and Y will be between 1 and 10^6, inclusive.
3
{1,2,3}
{1,2,3}
Returns: 2
You want to be able to walk from (1,1) to (3,3). In order to be able to do that, you need to add two more points. One of multiple optimal solutions is to add the points (2,1) and (2,3).
4
{1,1,1,3}
{1,2,3,3}
Returns: 1
10
{1,1,1,2,3,3,4,5,5,5}
{1,2,3,3,3,2,2,2,3,4}
Returns: 0
7
{2,3,4,5,6,6,5}
{2,1,1,1,2,3,4}
Returns: 3
2
{2,2}
{2,2}
Returns: 0
Here you want to travel from (2,2) to (2,2). That is trivially possible, without having to add more points. Note that the point (2,2) is given twice. This has exactly the same effect as if it were given only once.
Submissions are judged against all 98 archived test cases, of which 5 are shown here. Case numbers match the judge’s.
Language: C++17 · define a public class MovingByPoints with a public method int countMinimumPoints(int N, vector<int> X, vector<int> Y) · 98 test cases · 2 s / 256 MB per case