aboutsummaryrefslogtreecommitdiff
path: root/shortest_path_grid_obstacle.cpp
diff options
context:
space:
mode:
Diffstat (limited to 'shortest_path_grid_obstacle.cpp')
-rw-r--r--shortest_path_grid_obstacle.cpp48
1 files changed, 0 insertions, 48 deletions
diff --git a/shortest_path_grid_obstacle.cpp b/shortest_path_grid_obstacle.cpp
deleted file mode 100644
index daaa361..0000000
--- a/shortest_path_grid_obstacle.cpp
+++ /dev/null
@@ -1,48 +0,0 @@
-#include "leetcode.h"
-
-class Solution {
-public:
- int shortestPath(vvd & grid, int k) {
- int rows = grid.size(), cols = grid[0].size();
- int minStep = max(0, rows + cols - 2), obstacles = minStep - 1,
- minStepNext = minStep;
- if (obstacles <= k)
- return minStep;
- vvd dirs = {{1, 0}, {0, 1}, {-1, 0}, {0, -1}};
- list<vector<int>> togo;
- togo.push_back({0, 0, k});
- vector<int> visited(rows * cols, -1);
- visited[0] = k;
- int steps = 0;
- while (togo.size()) {
- steps++;
- minStep = minStepNext;
- for (int i = togo.size(); i > 0; i--) {
- int a = togo.front()[0], b = togo.front()[1], c = togo.front()[2];
- togo.pop_front();
- for (auto &d : dirs) {
- int aa = a + d[0], bb = b + d[1];
- if (aa < 0 || aa >= rows || bb < 0 || bb >= cols)
- continue;
- int cc = c - grid[aa][bb];
- if (visited[aa * cols + bb] >= cc)
- continue;
- int stepsToTarget = rows - aa - 1 + cols - bb - 1;
- if (stepsToTarget - 1 <= cc && stepsToTarget == minStep - 1)
- return steps + stepsToTarget;
- togo.push_back({aa, bb, cc});
- visited[aa * cols + bb] = cc;
- minStepNext = min(minStepNext, stepsToTarget);
- }
- }
- }
- return -1;
- }
-};
-
-int main() {
- Solution obj;
- vvd grid = {{0, 0, 0}, {1, 1, 0}, {0, 0, 0}, {0, 1, 1}, {0, 0, 0}};
- int k = 1;
- cout << obj.shortestPath(grid, k);
-}