TrappingRabbit
Member SRM 461 · 2009-12-03 · by dolphinigle
Member SRM 461 · 2009-12-03 · by dolphinigle · Simple Search, Iteration
Problem Statement
Problem Statement
There is a grass field that is represented by a 1000 by 1000 grid. Initially, a rabbit is present on the square located at coordinates (1,1) (1-based). The rabbit can move to a horizontally or vertically adjacent square in one second and can only move that way.
You are going to trap the rabbit. To do so, you have set some traps. The i-th trap is located on a square given by trapX[i] and trapY[i] as its X and Y coordinates (1-based) respectively.
Return the minimum number of seconds so that after this time has passed there is a non-zero chance that the rabbit has fallen into one of your traps (the rabbit falls into one of your traps if it is in the same square as one of your traps).
You are going to trap the rabbit. To do so, you have set some traps. The i-th trap is located on a square given by trapX[i] and trapY[i] as its X and Y coordinates (1-based) respectively.
Return the minimum number of seconds so that after this time has passed there is a non-zero chance that the rabbit has fallen into one of your traps (the rabbit falls into one of your traps if it is in the same square as one of your traps).
Constraints
- trapX will contain between 1 and 50 elements, inclusive.
- trapY will contain between 1 and 50 elements, inclusive.
- trapX and trapY will contain the same number of elements.
- Each element of trapX and trapY will be between 1 and 1000, inclusive.
- All traps will have distinct locations.
- No trap will be located at coordinates (1,1).
Examples
0)
{4,6,8}
{1,2,1}
Returns: 3
If the rabbit goes 3 squares in the positive X direction it will fall to your first trap. Going 3 squares requires 3 seconds.
1)
{5,4,3}
{5,4,3}
Returns: 4
The rabbit will be trapped within 4 seconds if it moves 2 squares in the positive X direction and 2 squares in the positive Y direction.
2)
{1000}
{1000}
Returns: 1998
3)
{358,585,940,750,736,913,873,565,513,856,289,583,882,135,841,198,707,352,634,526,534,868,983,802,329,606,969,383,456,509,694,247,833,845,253,816,798,622,188,106,302,708,883,821,196,885,742,689,311,719}
{145,262,496,305,629,607,229,198,995,517,310,535,506,801,219,703,376,178,948,301,235,816,251,460,248,39,845,803,559,155,324,29,901,110,16,370,841,587,385,685,207,943,87,788,296,403,723,667,256,123}
Returns: 267
4)
{711,443,169,871,409,895,792,235,686,792,911,529,34,394,590,694,173,217,158,520,893,567,102,323,58,250,817,72,945,988,293,90,602,625,222,695,609,436,641,709,8,522,305,282,876,541,149,59,747,907}
{155,929,487,810,225,354,681,740,189,851,950,34,86,817,522,177,749,819,294,643,59,227,21,677,997,240,528,111,551,871,554,272,879,925,925,983,797,23,123,507,58,787,350,900,646,36,521,143,247,330}
Returns: 64
Submissions are judged against all 69 archived test cases, of which 5 are shown here. Case numbers match the judge’s.
Coding Area
Language: C++17 · define a public class TrappingRabbit with a public method int findMinimumTime(vector<int> trapX, vector<int> trapY) · 69 test cases · 2 s / 256 MB per case