【数据结构与算法面试宝典】19 最小体力消耗路径：如何突破经典题型，掌握解题模板？
(持续更新中，欢迎关注！)
文章目录
- 【数据结构与算法面试宝典】19 最小体力消耗路径：如何突破经典题型，掌握解题模板？
- 题目
- 预处理
- 点的处理
- 边的处理
- 特点 1：连通性
- 特点 2：最小值
- 四步法
- f 函数
- 特点 3：再看最小值
- 特点 4: 又看最小值
- 总结
- 思考题
- 附录：题目出处和代码汇总
今天继续从多个角度去求解一个题目，尝试运用丰富的解题工具，比如的“老熟人”BFS/DFS/Dijkstra 算法，帮助你巩固和应用已经学习过的知识点。除此之外，本讲还会重点介绍一些在“一题多解”中尚未覆盖到的算法：
并查集
二分搜索
动态规划（Bellman-Ford 算法）
通过“一题多解”的训练，拓展的思维，一起去探索“五彩缤纷”的解题技巧。让马上开始。
题目
你准备参加一场远足活动。给你一个二维 rows x columns 的地图 heights ，其中 heights[row][col] 表示格子 (row, col) 的高度。
一开始你在最左上角的格子 (0, 0) ，且你希望去最右下角的格子 (rows-1, columns-1) （注意下标从 0 开始编号）。
你每次可以往 上、下、左、右四个方向之一移动，你想要找到耗费体力最小的一条路径。
一条路径耗费的体力值是由路径上相邻格子之间高度差绝对值的最大值决定的。请你返回从左上角走到右下角的最小体力消耗值 。矩阵中最大值不超过 106。
例如给定如下地图：
