There is a plot (grid-like land) with each spot having a specified elevation.
Within this plot there are two villages that need water delivered to them.
Which spot is the best place to build a water tower so that both villages get water?
Water can flow to a spot with the same or lower elevation.
The input will be an NxM dimensional matrix and the coordinates or indices for the two villages.
Return the best spot to build the water tower if there is one.
To keep construction cost as low as possible, the best spot is the spot that is closest to both villages.
In the examples below the villages are identified by () and the best spot(s) are identified by []
[4 9 7 6 5]
[2 [6] 5 5 (3) ]
[6 5 1 2 8]
[3 (4) 7 2 5 ]
Returns (1, 1)[2 (7) (7) (7) 5 ]
[6 5 2 (4) 1 ]
[(3) 4 5 2 8 ]
Returns: (0, 1), (0, 2), or (0, 3)Possible method headers:
int[] getWaterTowerPosition(int[][] grid, int[] village1, int[] village2)
Pair<Integer, Integer> getWaterTowerPosition(int[][] grid, Pair<Integer, Integer> village1, Pair<Integer, Integer> village2)
any other definition if you want to make your own object.This problem asks for a location in an elevation grid where a water tower can supply two villages under the rule that water flows to the same or lower elevation. A clean way to solve it is to run a reverse search from each village, expanding only to cells with equal or higher elevation, which gives the set of tower positions that can reach that village. The answer is the intersection of the two reachable sets, and among those candidates, choose the position with the smallest combined distance to both villages. If multiple positions tie, any valid one can be returned.
