Problem Statement
The city of Gridlock is a grid of cells with R rows and C columns. Each cell has up to four neighbours: the cells directly above, below, to the left, and to the right. A citizen of Gridlock can travel from a cell to any of its neighbours in one minute.
The citizens of Gridlock are upset that it takes too long to get around, so they have decided to build a teleporter. The teleporter will consist of two identical booths, each located in some cell. If a citizen enters either booth, he or she may choose to teleport to the other booth instantly. It is allowed to build both booths in the same cell.
We define the distance between two cells as the minimum number of minutes needed to get from one cell to another. Let D be the maximum distance between any two cells. Place the teleporter in such a way that D is minimized, and return this minimum value.
Definition
- Class:
- PublicTransit
- Method:
- minimumLongestDistance
- Parameters:
- int, int
- Returns:
- int
- Method signature:
- int minimumLongestDistance(int R, int C)
- (be sure your method is public)
Constraints
- R is between 1 and 10, inclusive.
- C is between 1 and 10, inclusive.
Examples
4
1
Returns: 1
The optimal solution is to connect cell (1, 1) to cell (4, 1). (All cell coordinates are 1-based.)
2
2
Returns: 1
5
3
Returns: 4
8
2
Returns: 4
1
1
Returns: 0
2
1
Returns: 0
1
3
Returns: 1
4
1
Returns: 1
1
5
Returns: 2
1
6
Returns: 2
7
1
Returns: 3
8
1
Returns: 3
9
1
Returns: 4
1
10
Returns: 4
2
2
Returns: 1
2
3
Returns: 2
4
2
Returns: 2
5
2
Returns: 3
6
2
Returns: 3
2
7
Returns: 4
2
8
Returns: 4
9
2
Returns: 5
2
10
Returns: 5
3
3
Returns: 3
4
3
Returns: 3
5
3
Returns: 4
6
3
Returns: 4
7
3
Returns: 5
3
8
Returns: 5
3
9
Returns: 6
10
3
Returns: 6
4
4
Returns: 4
4
5
Returns: 5
4
6
Returns: 5
4
7
Returns: 6
8
4
Returns: 6
4
9
Returns: 7
10
4
Returns: 7
5
5
Returns: 6
5
6
Returns: 6
5
7
Returns: 7
8
5
Returns: 7
5
9
Returns: 8
5
10
Returns: 8
6
6
Returns: 7
7
6
Returns: 8
8
6
Returns: 8
9
6
Returns: 9
10
6
Returns: 9
7
7
Returns: 9
7
8
Returns: 9
7
9
Returns: 10
10
7
Returns: 10
8
8
Returns: 10
8
9
Returns: 11
8
10
Returns: 11
9
9
Returns: 12
10
9
Returns: 12
10
10
Returns: 13
9
10
Returns: 12
3
5
Returns: 4
1
4
Returns: 1