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.这道题给出一个二维地形网格，每个格子代表海拔，两个村庄需要通过“水往低处流”的规则获得供水。核心是判断哪些位置既能让水流到两个村庄，又要尽量靠近两村以降低建塔成本。通常做法是从两个村庄分别反向搜索可达区域：因为正常水流只能从高到低或相同高度流动，所以反向时要沿着“相同或更高”的方向扩展，分别得到两个村庄都能到达的格子集合，最后在交集里选择离两个村庄综合距离最小的位置；如果有多个最优解，返回任意一个即可。
