思路1:
最短路问题变种。
实现1:
1 class Solution 2 { 3 public: 4 const int INF = 0x3f3f3f3f; 5 const int dx[4] = {0, -1, 0, 1}; 6 const int dy[4] = {1, 0, -1, 0}; 7 int minimumEffortPath(vector<vector<int>>& heights) 8 { 9 int n = heights.size(), m = heights[0].size(); 10 using pii = pair<int, int>; 11 priority_queue<pii, vector<pii>, greater<pii>> q; 12 vector<vector<bool>> vis(n, vector<bool>(m, false)); 13 vector<vector<int>> res(n, vector<int>(m, INF)); 14 q.push(make_pair(0, 0)); 15 while (!q.empty()) 16 { 17 pii tmp = q.top(); q.pop(); 18 int dis = tmp.first, x = tmp.second / m, y = tmp.second % m; 19 if (vis[x][y]) continue; 20 vis[x][y] = true; 21 res[x][y] = dis; 22 if (x == n - 1 && y == m - 1) break; 23 for (int i = 0; i < 4; i++) 24 { 25 int nx = x + dx[i], ny = y + dy[i]; 26 if (nx >= 0 && nx < n && ny >= 0 && ny < m && !vis[nx][ny]) 27 { 28 int tmp_dis = max(dis, abs(heights[x][y] - heights[nx][ny])); 29 q.push(make_pair(tmp_dis, nx * m + ny)); 30 } 31 } 32 } 33 return res[n - 1][m - 1]; 34 } 35 }
思路2:
二分+dfs（或bfs）。
实现2:
1 class Solution 2 { 3 public: 4 const int INF = 0x3f3f3f3f; 5 const int dx[4] = {0, -1, 0, 1}; 6 const int dy[4] = {1, 0, -1, 0}; 7 void dfs(int x, int y, vector<vector<int>>& h, int threshold, vector<vector<bool>>& vis) 8 { 9 vis[x][y] = true; 10 int n = h.size(), m = h[0].size(); 11 for (int i = 0; i < 4; i++) 12 { 13 int nx = x + dx[i], ny = y + dy[i]; 14 if (nx < 0 || nx >= n || ny < 0 || ny >= m) continue; 15 int gap = abs(h[x][y] - h[nx][ny]); 16 if (gap > threshold || vis[nx][ny]) continue; 17 dfs(nx, ny, h, threshold, vis); 18 } 19 } 20 bool check(vector<vector<int>>& h, int threshold) 21 { 22 int n = h.size(), m = h[0].size(); 23 vector<vector<bool>> vis(n, vector<bool>(m, false)); 24 dfs(0, 0, h, threshold, vis); 25 return vis[n - 1][m - 1]; 26 } 27 int minimumEffortPath(vector<vector<int>>& heights) 28 { 29 int l = 0, r = 1e6, res = INF; 30 while (l <= r) 31 { 32 int mid = l + r >> 1; 33 if (check(heights, mid)) 34 { 35 res = mid; 36 r = mid - 1; 37 } 38 else l = mid + 1; 39 } 40 return res; 41 } 42 }
思路3:
并查集。
实现3:
1 class Solution 2 { 3 public: 4 int find(int x, vector<int>& p) 5 { 6 if (p[x] == x) return x; 7 return p[x] = find(p[x], p); 8 } 9 void uni(int x, int y, vector<int>& p) 10 { 11 x = find(x, p), y = find(y, p); 12 if (x != y) p[x] = y; 13 } 14 int minimumEffortPath(vector<vector<int>>& heights) 15 { 16 using tiii = tuple<int, int, int>; 17 int n = heights.size(), m = heights[0].size(); 18 vector<int> p(n * m); 19 for (int i = 0; i < n * m; i++) p[i] = i; 20 vector<tiii> v; 21 for (int i = 0; i < n; i++) 22 { 23 for (int j = 0; j < m; j++) 24 { 25 int id = i * m + j; 26 if (i + 1 <= n - 1) 27 { 28 int nid = (i + 1) * m + j; 29 int gap = abs(heights[i][j] - heights[i + 1][j]); 30 v.push_back(make_tuple(gap, id, nid)); 31 } 32 if (j + 1 <= m - 1) 33 { 34 int nid = i * m + j + 1; 35 int gap = abs(heights[i][j] - heights[i][j + 1]); 36 v.push_back(make_tuple(gap, id, nid)); 37 } 38 } 39 } 40 sort(v.begin(), v.end()); 41 int i = 0; 42 for ( ; i < v.size(); i++) 43 { 44 int a = find(0, p), b = find(n * m - 1, p); 45 if (a == b) break; 46 int x = get<1>(v[i]), y = get<2>(v[i]); 47 uni(x, y, p); 48 } 49 return i == 0 ? 0 : get<0>(v[i - 1]); 50 } 51 }