Swim in Rising Water

Swim in Rising Water

问题

假设方阵中每个点都标有权值，问题是求方阵中两点之间的路径中所有点权值最大值的最小值

比如2x2矩阵一共有两条路径，第一条路径中两个点权值是1,3,2最大值为3，第二条路径中两个点权值1,2,2是最大值为2，那么结果就是2

解决

• 想到用dp去解决这个问题，但是路径的选择其实是不具备dp条件的，即出了不能重复外，可以随便选择方向
• 思考路径的选择方法，发现可以在经过的路径的所有相邻点中，选择深度差最小的下一步，也就是使用一种类似贪心的方法
• 数据结构上，我们使用优先队列和集合，优先队列用于寻找贪心的下一个点，集合用于判断下一个点是否经过（其实也可以用布尔数组）
• 另一个方法思路很简单，就是二分猜测+DFS验证，时间复杂度也在O(N^2logN)这个数量级上

Tips

• 凡是答案是在给定的数组之内选择的，都可以尝试排序加二分的思路