Swim in Rising Water
2018-02-14 本文已影响30人
gattonero
问题
题意不去过多比喻和解释了，就是求方阵中两点之间的路径中最大值的最小值（比如2x2矩阵一共有两条路径，第一条路径中最大值为3，第二天路径中最大值为2，那么结果就是2）
解决方案
- 想到用dp去解决这个问题，但是路径的选择其实是不具备dp条件的，即出了不能重复外，可以随便选择方向
- 思考路径的选择方法，发现可以在经过的路径的所有相邻点中，选择深度差最小的下一步，也就是使用一种类似贪心的方法
- 数据结构上，我们使用优先队列和集合，优先队列用于寻找贪心的下一个点，集合用于判断下一个点是否经过（其实也可以用布尔数组）
- 另一个方法思路很简单，就是二分猜测+DFS验证，时间复杂度也在O(N^2logN)这个数量级上
