Problem Statement |
| | Our world consists of rows and columns of identical square regions.
We have a list of regions that we want to visit, starting from the center
of the first region in the list and going in straight lines to the center of each
successive region. Every time we cross from one region into the interior of
another region (even if we have previously visited it) we will be charged a tax.
Create a class Regions that contains the method numTaxes that takes int[]s rows and
columns of the regions on our list and returns the number of taxes we will have to pay.
The i-th elements of rows and
columns give the location of the i-th region that we must visit.
If we must pay more than 2,000,000,000 taxes (!) then return -1.
|
| |
Definition |
| | | Class: | Regions | | Method: | numTaxes | | Parameters: | int[], int[] | | Returns: | int | | Method signature: | int numTaxes(int[] row, int[] col) | | (be sure your method is public) |
|
| |
|
| |
Notes |
| - | We are not charged a tax if we just touch the boundary of a region. |
| |
Constraints |
| - | rows has between 1 and 50 elements inclusive. |
| - | columns has the same number of elements as rows. |
| - | Each element of rows and or columns is between 0 and 1,000,000,000 inclusive. |
| |
Examples |
| 0) | |
| | | Returns: 7 | | Going from the center of 4,4 to the center of 2,2 we pay tax when we enter region
3,3 and when we enter region 2,2. Going from the center of 2,2 to the center of
3,6 we pay tax as we enter 2,3 then 2,4 then 3,4 then 3,5 then 3,6.
|
|
|
| 1) | |
| | {0,1000000000,0} | {0,1000000000,0} |
| Returns: 2000000000 | | We enter each region along the diagonal on the first leg, a total of 1,000,000,000 regions. On the way back we go back down the diagonal but we still have to pay taxes. |
|
|
| 2) | |
| | | Returns: 10 | | The first leg enters (1,0),(2,0),(3,1),(4,1),(5,1),(6,1),(7,1),(8,2),(9,2),(10,2). The second leg just stays within region (10,2), paying no additional taxes. |
|
|
| 3) | |
| | {0,1000000000,6} | {0,999999999,18} |
| Returns: -1 | | Each of the two legs enters almost 2 billion regions, so the sum of the taxes along this path is greater than 2 billion. |
|
|
| 4) | |
| | {999999999,1,999999999,999999999} | {1,1,1,6} |
| Returns: -1 | |
|