diff options
Diffstat (limited to 'min_obstacle_removal_corner.c')
-rw-r--r-- | min_obstacle_removal_corner.c | 128 |
1 files changed, 128 insertions, 0 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); +} |