diff options
Diffstat (limited to 'other/shortest_path_grid_obstacle.cpp')
-rw-r--r-- | other/shortest_path_grid_obstacle.cpp | 48 |
1 files changed, 48 insertions, 0 deletions
diff --git a/other/shortest_path_grid_obstacle.cpp b/other/shortest_path_grid_obstacle.cpp new file mode 100644 index 0000000..daaa361 --- /dev/null +++ b/other/shortest_path_grid_obstacle.cpp @@ -0,0 +1,48 @@ +#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); +} |