aboutsummaryrefslogtreecommitdiff
diff options
context:
space:
mode:
-rw-r--r--min_obstacle_removal_corner.c128
-rw-r--r--min_obstacle_removal_corner.py42
-rw-r--r--shortest_dist_road_addition1.py38
3 files changed, 197 insertions, 11 deletions
diff --git a/min_obstacle_removal_corner.c b/min_obstacle_removal_corner.c
new file mode 100644
index 0000000..df38cd4
--- /dev/null
+++ b/min_obstacle_removal_corner.c
@@ -0,0 +1,128 @@
+// 2290. Minimum Obstacle Removal to Reach Corner
+#include "leetcode.h"
+
+/*
+ * you are given a 0-indexed 2d integer array 'grid' of size 'm x n'. each cell
+ * has one of two values: 0 represents an empty cell, and 1 rperesents an
+ * obstacle that may be removed. you can move up, down, left, or right from and
+ * to an empty cell. return the minimum number of obstacles to remove so you can
+ * move from the upper left corner ('0, 0') to the lower right corner ('m -1, n
+ * - 1').
+ */
+
+static int dx[] = {-1, 0, 1, 0};
+static int dy[] = {0, 1, 0, -1};
+
+struct pair {
+ int x;
+ int y;
+};
+
+struct node {
+ struct pair data;
+ struct node *next;
+ struct node *prev;
+};
+
+struct deque {
+ struct node *front;
+ struct node *rear;
+};
+
+void deque_init(struct deque *obj) {
+ obj->front = NULL;
+ obj->rear = NULL;
+}
+
+void push_front(struct deque *obj, struct pair p) {
+ struct node *n = (struct node *)malloc(sizeof(struct node));
+ n->data = p;
+ n->next = obj->front;
+ n->prev = NULL;
+ if (obj->front)
+ obj->front->prev = n;
+ obj->front = n;
+ if (!obj->rear)
+ obj->rear = n;
+}
+
+void push_back(struct deque *obj, struct pair p) {
+ struct node *n = (struct node *)malloc(sizeof(struct node));
+ n->data = p;
+ n->next = NULL;
+ n->prev = obj->rear;
+ if (obj->rear)
+ obj->rear->next = n;
+ obj->rear = n;
+ if (!obj->front)
+ obj->front = n;
+}
+
+struct pair pop_front(struct deque *obj) {
+ struct pair data = obj->front->data;
+ struct node *tmp = obj->front;
+ obj->front = obj->front->next;
+ if (obj->front)
+ obj->front->prev = NULL;
+ else
+ obj->rear = NULL;
+ free(tmp);
+ return data;
+}
+
+bool deque_empty(struct deque *obj) { return !obj->front; }
+
+void deque_free(struct deque *obj) {
+ while (!deque_empty(obj))
+ pop_front(obj);
+}
+
+int minimumObstacles(int **grid, int gridSize, int *gridColSize) {
+ int m = gridSize, n = gridColSize[0];
+ int **dist = (int **)malloc(m * sizeof(int *));
+ for (int i = 0; i < m; i++) {
+ dist[i] = (int *)malloc(n * sizeof(int));
+ for (int j = 0; j < n; j++)
+ dist[i][j] = INT_MAX;
+ }
+ struct deque dq;
+ deque_init(&dq);
+ push_front(&dq, (struct pair){0, 0});
+ dist[0][0] = 0;
+ while (!deque_empty(&dq)) {
+ struct pair p = pop_front(&dq);
+ int x = p.x, y = p.y;
+ for (int i = 0; i < 4; i++) {
+ int nx = x + dx[i], ny = y + dy[i];
+ if (nx < 0 || ny < 0 || nx >= m || ny >= n)
+ continue;
+ int new_dist = dist[x][y] + grid[nx][ny];
+ if (new_dist < dist[nx][ny]) {
+ dist[nx][ny] = new_dist;
+ if (!grid[nx][ny])
+ push_front(&dq, (struct pair){nx, ny});
+ else
+ push_back(&dq, (struct pair){nx, ny});
+ }
+ }
+ }
+ int ans = dist[m - 1][n - 1];
+ for (int i = 0; i < m; i++)
+ free(dist[i]);
+ free(dist);
+ deque_free(&dq);
+ return ans;
+}
+
+int main() {
+ int g1i[3][3] = {{0, 1, 1}, {1, 1, 0}, {1, 1, 0}},
+ g2i[3][5] = {{0, 1, 0, 0, 0}, {0, 1, 0, 1, 0}, {0, 0, 0, 1, 0}};
+ struct two_d_arr g1, g2;
+ two_d_arr_init(&g1, 3, 3, g1i);
+ two_d_arr_init(&g2, 3, 5, g2i);
+ printf("%d\n",
+ minimumObstacles(g1.arr, g1.row_size, g1.col_size)); // expect: 2
+ printf("%d\n",
+ minimumObstacles(g2.arr, g2.row_size, g2.col_size)); // expect: 0
+ two_d_arr_free(&g1), two_d_arr_free(&g2);
+}
diff --git a/min_obstacle_removal_corner.py b/min_obstacle_removal_corner.py
new file mode 100644
index 0000000..1c8ad80
--- /dev/null
+++ b/min_obstacle_removal_corner.py
@@ -0,0 +1,42 @@
+# 2290. Minimum Obstacle Removal to Reach Corner
+from collections import deque
+
+"""
+you are given a 0-indexed 2d integer array 'grid' of size 'm x n'. each cell
+has one of two values: 0 represents an empty cell, and 1 rperesents an
+obstacle that may be removed. you can move up, down, left, or right from and
+to an empty cell. return the minimum number of obstacles to remove so you can
+move from the upper left corner ('0, 0') to the lower right corner ('m -1, n
+- 1').
+"""
+
+
+class Solution(object):
+ def minimumObstacles(self, grid):
+ """
+ :type grid: List[List[int]]
+ :rtype: int
+ """
+ m, n = map(len, (grid, grid[0]))
+ dist = [[float("inf")] * n for _ in range(m)]
+ dist[0][0] = 0
+ dq = deque([(0, 0, 0)])
+ while dq:
+ o, r, c = dq.popleft()
+ for i, j in (r + 1, c), (r - 1, c), (r, c + 1), (r, c - 1):
+ if m > i >= 0 <= j < n and dist[i][j] == float("inf"):
+ if grid[i][j] == 1:
+ dist[i][j] = o + 1
+ dq.append((o + 1, i, j))
+ else:
+ dist[i][j] = o
+ dq.append((o, i, j))
+ return dist[-1][-1]
+
+
+if __name__ == "__main__":
+ obj = Solution()
+ print(obj.minimumObstacles(grid=[[0, 1, 1], [1, 1, 0], [1, 1, 0]]))
+ print(
+ obj.minimumObstacles(grid=[[0, 1, 0, 0, 0], [0, 1, 0, 1, 0], [0, 0, 0, 1, 0]])
+ )
diff --git a/shortest_dist_road_addition1.py b/shortest_dist_road_addition1.py
index 0115c4a..ae40e56 100644
--- a/shortest_dist_road_addition1.py
+++ b/shortest_dist_road_addition1.py
@@ -20,20 +20,36 @@ class Solution(object):
:type queries: List[List[int]]
:rtype: List[int]
"""
- ans = []
- mp = {i: [i + 1] for i in range(n - 1)}
- for i in queries:
- mp[i[0]].append(i[1])
- dp = [float("inf")] * n
- dp[n - 1] = 0
- for j in range(n - 2, -1, -1):
- for next in mp[j]:
- dp[j] = min(dp[j], dp[next] + 1)
- ans.append(dp[0])
- return ans
+ # ans = []
+ # mp = {i: [i + 1] for i in range(n - 1)}
+ # for i in queries:
+ # mp[i[0]].append(i[1])
+ # dp = [float("inf")] * n
+ # dp[n - 1] = 0
+ # for j in range(n - 2, -1, -1):
+ # for next in mp[j]:
+ # dp[j] = min(dp[j], dp[next] + 1)
+ # ans.append(dp[0])
+ # return ans
+ sol = []
+ city_distances = {i: [-1] * i + list(range(n - i)) for i in range(n)}
+ for query in queries:
+ source, destination = query
+ city_distances[source][destination] = 1
+ for i in range(destination + 1, n):
+ city_distances[source][i] = min(
+ city_distances[destination][i] + 1, city_distances[source][i]
+ )
+ for i in range(source - 1, -1, -1):
+ city_distances[i][destination] = min(
+ city_distances[i][source] + 1, city_distances[i][destination]
+ )
+ sol.append(city_distances[0][-1])
+ return sol
if __name__ == "__main__":
obj = Solution()
print(obj.shortestDistanceAfterQueries(n=5, queries=[[2, 4], [0, 2], [0, 4]]))
print(obj.shortestDistanceAfterQueries(n=4, queries=[[0, 3], [0, 2]]))
+ print(obj.shortestDistanceAfterQueries(n=5, queries=[[1, 3], [0, 3]]))