题目描述
你准备参加一场远足活动。给你一个二维 rows x columns
的地图 heights
,其中 heights[row][col]
表示格子 (row, col)
的高度。一开始你在最左上角的格子 (0, 0)
,且你希望去最右下角的格子 (rows-1, columns-1)
(注意下标从 0 开始编号)。你每次可以往 上,下,左,右 四个方向之一移动,你想要找到耗费 体力 最小的一条路径。
一条路径耗费的 体力值 是路径上相邻格子之间 高度差绝对值 的 最大值 决定的。
请你返回从左上角走到右下角的最小 体力消耗值 。
样例
输入:heights = [[1,2,2],[3,8,2],[5,3,5]]
输出:2
解释:路径 [1,3,5,3,5] 连续格子的差值绝对值最大为 2 。
这条路径比路径 [1,2,2,2,5] 更优,因为另一条路劲差值最大值为 3 。
输入:heights = [[1,2,3],[3,8,4],[5,3,5]]
输出:1
解释:路径 [1,2,3,4,5] 的相邻格子差值绝对值最大为 1 ,比路径 [1,3,5,3,5] 更优。
输入:heights = [[1,2,1,1,1],[1,2,1,2,1],[1,2,1,2,1],[1,2,1,2,1],[1,1,1,2,1]]
输出:0
解释:上图所示路径不需要消耗任何体力。
提示:
rows == heights.length
columns == heights[i].length
1 <= rows, columns <= 100
1 <= heights[i][j] <= 10^6
算法分析
二分 + bfs
求所有路径上相邻格子之间 高度差绝对值 的 最大值 的最小值,可以往二分方面想
- 1、通过二分取到某个特定的值
x
表示,在任意一条路径中,若相邻格子的高度差绝对值 小于等于x
,则表示这两个格子是连通状态 - 2、使用
st[][]
数组记录某个点是否被遍历过,从(0, 0)
开始进行bfs
,观察能否到达(n - 1, m - 1)
- 3、若该特定值
x
能从(0, 0)
到达(n - 1, m - 1)
则把该x
值取小,否则取大
时间复杂度 $O(n^2logn)$
Java 代码
class Solution {
static int N = 110;
static boolean[][] st = new boolean[N][N];
static int n, m;
static int[] dx = new int[]{0, -1, 0, 1};
static int[] dy = new int[]{-1, 0, 1, 0};
static boolean check(int x, int[][] heights)
{
for(int i = 0;i < n;i ++) Arrays.fill(st[i], false);
Queue<Pair> q = new LinkedList<Pair>();
q.add(new Pair(0, 0));
st[0][0] = true;
while(!q.isEmpty())
{
Pair t = q.poll();
for(int i = 0;i < 4;i ++)
{
int a = t.x + dx[i], b = t.y + dy[i];
if(a < 0 || a >= n || b < 0 || b >= m) continue;
if(st[a][b]) continue;
if(Math.abs(heights[a][b] - heights[t.x][t.y]) > x) continue;
q.add(new Pair(a, b));
st[a][b] = true;
}
}
return st[n - 1][m - 1];
}
public int minimumEffortPath(int[][] heights) {
n = heights.length;
m = heights[0].length;
int l = 0, r = 1000000;
while(l < r)
{
int mid = l + r >> 1;
if(check(mid, heights)) r = mid;
else l = mid + 1;
}
return l;
}
}
class Pair
{
int x, y;
Pair(int x, int y)
{
this.x = x;
this.y = y;
}
}