Sponsored
Sponsored
This approach uses a priority queue (or deque) to implement a modified Dijkstra's algorithm to explore the grid in a way similar to the 0-1 BFS (Breadth-First Search). Here, obstacles count as 'cost', and we try to find the minimum 'cost' path from the top-left corner to the bottom-right corner. We assign a priority based on the number of obstacles removed.
Time Complexity: O(m * n)
Space Complexity: O(m * n)
1#include <bits/stdc++.h>
2using namespace std;
3
4int minimumObstacles(vector<vector<int>>& grid) {
5 int m = grid.size(), n = grid[0].size();
6 vector<vector<int>> dist(m, vector<int>(n, INT_MAX));
7 deque<pair<int, int>> dq;
8 dist[0][0] = 0;
9 dq.push_front({0, 0});
10 vector<pair<int, int>> directions = {{0, 1}, {1, 0}, {0, -1}, {-1, 0}};
11
12 while (!dq.empty()) {
13 auto [x, y] = dq.front(); dq.pop_front();
14 for (auto& [dx, dy] : directions) {
15 int nx = x + dx, ny = y + dy;
16 if (nx >= 0 && nx < m && ny >= 0 && ny < n) {
17 int cost = dist[x][y] + grid[nx][ny];
18 if (cost < dist[nx][ny]) {
19 dist[nx][ny] = cost;
20 if (grid[nx][ny] == 0) {
21 dq.push_front({nx, ny});
22 } else {
23 dq.push_back({nx, ny});
24 }
25 }
26 }
27 }
28 }
29 return dist[m - 1][n - 1];
30}This C++ solution also employs a deque to perform a 0-1 BFS strategy over the grid. The grid cells to be visited next are chosen based on the cost associated, prioritizing unblocked paths, similar to the Python solution. Priority is managed efficiently using push_front and push_back, reflecting the move's cost.
In this approach, we utilize dynamic programming combined with a monotonic queue to solve the problem of reaching the bottom-right corner with minimal obstacle removal. This alternative method involves leveraging the properties of dynamic arrays to store and update minimal removal costs dynamically while using a queue to maintain an effective processing order based on current state values.
Time Complexity: O(m * n)
Space Complexity: O(m * n)
1from collections import deque
This dynamic programming version utilizes a monotonic queue to keep the process smooth, in essence maintaining timeline-line transitions amidst evolved states. Adjustments are made based on evaluated costs for obstacles, ensuring ultimately reaching the target state with minimal burdensome path choices.