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 <stdio.h>
2#include <limits.h>
3#include <stdlib.h>
4#include <stdbool.h>
5
6#define MAX 100000
7
8typedef struct {
9 int x, y, priority;
10} Node;
11
12Node queue[MAX];
13int front = 0, rear = -1;
14
15void enqueue(Node n) {
16 queue[++rear] = n;
17}
18
19Node dequeue() {
20 return queue[front++];
21}
22
23bool isEmpty() {
24 return front > rear;
25}
26
27int minimumObstacles(int** grid, int gridSize, int* gridColSize) {
28 int m = gridSize, n = gridColSize[0];
29 int directions[4][2] = {{0, 1}, {1, 0}, {0, -1}, {-1, 0}};
30 int dist[m][n];
31
32 for (int i = 0; i < m; ++i) {
33 for (int j = 0; j < n; ++j) {
34 dist[i][j] = INT_MAX;
35 }
36 }
37
38 dist[0][0] = 0;
39 enqueue((Node){0, 0, 0});
40
41 while (!isEmpty()) {
42 Node node = dequeue();
43 int x = node.x, y = node.y;
44
45 for (int i = 0; i < 4; ++i) {
46 int nx = x + directions[i][0];
47 int ny = y + directions[i][1];
48
49 if (nx >= 0 && nx < m && ny >= 0 && ny < n) {
50 int cost = dist[x][y] + grid[nx][ny];
51 if (cost < dist[nx][ny]) {
52 dist[nx][ny] = cost;
53 Node newNode = {nx, ny, cost};
54 if (grid[nx][ny] == 0) {
55 queue[--front] = newNode;
56 } else {
57 enqueue(newNode);
58 }
59 }
60 }
61 }
62 }
63 return dist[m - 1][n - 1];
64}The C solution implements a queue-based approach manually (following a deque structure-like logic) to manage 0-1 BFS in a zero-cost prioritized manner. The integer array captures the minimal path cost (number of removed obstacles) for each cell, ensuring efficient path exploration through structured queue operations that mimic deque behaviors with manual index adjustments.
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)
1import java.util
This Java solution implements a dynamic programming approach using Java's LinkedList as a deque, allowing it to maintain the necessary order of processing based on current grid dynamics efficiently and effectively transitioning from obstacle-heavy paths to minimally costed options.