aboutsummaryrefslogtreecommitdiff
path: root/other/path_min_effort1.cpp
diff options
context:
space:
mode:
Diffstat (limited to 'other/path_min_effort1.cpp')
-rw-r--r--other/path_min_effort1.cpp42
1 files changed, 0 insertions, 42 deletions
diff --git a/other/path_min_effort1.cpp b/other/path_min_effort1.cpp
deleted file mode 100644
index d9066cd..0000000
--- a/other/path_min_effort1.cpp
+++ /dev/null
@@ -1,42 +0,0 @@
-#include "leetcode.h"
-#include <algorithm>
-#include <climits>
-#include <cmath>
-#include <functional>
-#include <utility>
-#include <vector>
-
-class Solution {
- const int d4x[4] = {-1, 0, 1, 0}, d4y[4] = {0, 1, 0, -1};
-
-public:
- int minimumEffortPath(vector<vector<int>> &heights) {
- int n = heights.size(), m = heights[0].size();
- priority_queue<pair<int, int>, vector<pair<int, int>>,
- greater<pair<int, int>>>
- pq;
- vector<vector<int>> dis(n, vector<int>(m, INT_MAX));
- dis[0][0] = 0;
- pq.push({0, {0, 0}});
- while (!pq.empty()) {
- pair<int, pair<int, int>> curr = pq.top();
- pq.pop();
- int d = curr.first, r = curr.second.first, c = curr.second.second;
- if (r == n - 1 && c == m - 1)
- return d;
- for (int i = 0; i < 4; ++i) {
- int nX = r + d4x[i], nY = x + d4y[i];
- if (nX < 0 || nX >= n || nY < 0 || nY >= m)
- continue;
- int nD = max(d, abs(h[nX][nY] - h[r][c]));
- if (nD < dis[nX][nY]) {
- dis[nX][nY] = nD;
- pq.push({nD, {nX, nY}});
- }
- }
- }
- return 0;
- }
-};
-
-int main() {}