aboutsummaryrefslogtreecommitdiff
path: root/shortest_path_binary_matrix.c
diff options
context:
space:
mode:
Diffstat (limited to 'shortest_path_binary_matrix.c')
-rw-r--r--shortest_path_binary_matrix.c158
1 files changed, 75 insertions, 83 deletions
diff --git a/shortest_path_binary_matrix.c b/shortest_path_binary_matrix.c
index 28da729..20c8d97 100644
--- a/shortest_path_binary_matrix.c
+++ b/shortest_path_binary_matrix.c
@@ -1,9 +1,5 @@
// 1091. Shortest Path in Binary Matrix
-#include <assert.h>
-#include <stdbool.h>
-#include <stdio.h>
-#include <stdlib.h>
-#include <string.h>
+#include "leetcode.h"
/*
* given an n x n binary matrix 'grid', return the length of the shortest clear
@@ -16,100 +12,96 @@
* is the number of visited cells of this path
*/
-typedef struct pair {
- int x;
- int y;
-} pair_t;
+#define MAX_SIZE 100
-typedef pair_t queue_data_t;
+struct node {
+ int row;
+ int col;
+ int step;
+};
-typedef enum queue {
- QUEUE_OK,
- QUEUE_EMPTY,
- QUEUE_FULL,
- QUEUE_ERROR = 0xFF
-} queue_er_em;
+struct queue {
+ struct node n[MAX_SIZE * MAX_SIZE];
+ int front;
+ int rear;
+};
-typedef struct queue_t {
- queue_data_t *value;
- int buf_size;
- int offer_i;
- int poll_i;
- int cnt;
-} queue_t;
-
-queue_t *create_queue(int buf_size) {
- queue_t *q = malloc(sizeof(queue_t));
- memset(q, 0, sizeof(queue_t));
- q->buf_size = buf_size;
- q->value = malloc(buf_size * sizeof(queue_data_t));
- memset(q->value, 0, buf_size * sizeof(queue_data_t));
- return q;
+void queue_init(struct queue *q) {
+ q->front = -1;
+ q->rear = -1;
}
-queue_er_em offer_queue(queue_t *q, queue_data_t *data) {
- assert(q->cnt < q->buf_size);
- if (q->cnt >= q->buf_size)
- return QUEUE_ERROR;
- memcpy(&q->value[q->offer_i++], data, sizeof(queue_data_t));
- if (q->offer_i == q->buf_size)
- q->offer_i = 0;
- q->cnt++;
- return QUEUE_OK;
-}
+bool queue_empty(struct queue *q) { return q->front == -1; }
+
+bool queue_full(struct queue *q) { return q->rear == MAX_SIZE * MAX_SIZE - 1; }
-queue_er_em poll_queue(queue_t *q, queue_data_t *data) {
- assert(q->cnt);
- if (q->cnt < 1)
- return QUEUE_EMPTY;
- memcpy(data, &q->value[q->poll_i++], sizeof(queue_data_t));
- if (q->poll_i == q->buf_size)
- q->poll_i = 0;
- q->cnt--;
- return QUEUE_OK;
+void queue_push(struct queue *q, struct node n) {
+ if (queue_full(q))
+ return;
+ if (queue_empty(q))
+ q->front = 0;
+ q->n[++q->rear] = n;
}
-inline int get_data(queue_t *q) { return q->cnt; }
+struct node queue_pop(struct queue *q) {
+ struct node n = {0, 0, 0};
+ if (queue_empty(q))
+ return n;
+ n = q->n[q->front++];
+ if (q->front > q->rear) {
+ q->front = -1;
+ q->rear = -1;
+ }
+ return n;
+}
-bool empty(queue_t *q) { return (q->cnt); }
+bool valid(int row, int col, int n, int **grid) {
+ return row >= 0 && row < n && col >= 0 && col < n && grid[row][col] == 0;
+}
-int shortestPathBinaryMatrix(int **grid, int grid_size, int *grid_col_size) {
+int shortestPathBinaryMatrix(int **grid, int gridSize, int *gridColSize) {
if (grid[0][0] == 1)
return -1;
- queue_t *buf = create_queue(500);
- int dirr[8][2] = {{-1, -1}, {-1, 0}, {-1, 1}, {0, -1},
- {0, 1}, {1, -1}, {1, 0}, {1, 1}};
- pair_t p = {.x = 0, .y = 0};
- pair_t tmp;
- int cnt = 0;
- offer_queue(buf, &p);
- while (!empty(buf)) {
- int c = get_data(buf);
- cnt++;
- for (int i = 0; i < c; i++) {
- poll_queue(buf, &p);
- if (p.x == grid_size - 1 && p.y == grid_col_size[0] - 1)
- return cnt;
- for (int j = 0; j < 8; j++) {
- int tr = p.x + dirr[j][0];
- int tc = p.y + dirr[j][1];
- if (tr >= 0 && tr < grid_size && tc >= 0 && tc < grid_col_size[0] &&
- !grid[tr][tc]) {
- tmp.x = tr;
- tmp.y = tc;
- offer_queue(buf, &tmp);
- grid[tr][tc] = -1;
- }
+ int dir[8][2] = {{0, 1}, {1, 0}, {0, -1}, {-1, 0},
+ {-1, -1}, {-1, 1}, {1, -1}, {1, 1}};
+ int n = gridSize;
+ bool vis[MAX_SIZE][MAX_SIZE] = {false};
+ struct queue q;
+ queue_init(&q);
+ vis[0][0] = true;
+ struct node start = {0, 0, 1};
+ queue_push(&q, start);
+ while (!queue_empty(&q)) {
+ struct node curr = queue_pop(&q);
+ if (curr.row == n - 1 && curr.col == n - 1)
+ return curr.step;
+ for (int i = 0; i < 8; i++) {
+ int nr = curr.row + dir[i][0], nc = curr.col + dir[i][1];
+ if (valid(nr, nc, n, grid) && !vis[nr][nc]) {
+ vis[nr][nc] = true;
+ struct node next = {nr, nc, curr.step + 1};
+ queue_push(&q, next);
}
}
}
return -1;
}
-int main() int g1[2][2] = {{0, 1}, {1, 0}}, gs1 = 2, gcs1[] = { 2, 2 };
-int g2[3][3] = {{0, 0, 0}, {1, 1, 0}, {1, 1, 1}}, gs2 = 3, gcs[] = {3, 3, 3};
-int g3[3][3] = {{1, 0, 0}, {1, 1, 0}, {1, 1, 0}}, gs3 = 3, gc3[] = {3, 3, 3};
-printf("%d\n", shortestPathBinaryMatrix(g1, gs1, gc1)); // expect: 2
-printf("%d\n", shortestPathBinaryMatrix(g2, gs2, gc2)); // expect: 4
-printf("%d\n", shortestPathBinaryMatrix(g3, gs3, gc3)); // expect: -1
+int main() {
+ int g1i[2][2] = {{0, 1}, {1, 0}};
+ int g2i[3][3] = {{0, 0, 0}, {1, 1, 0}, {1, 1, 0}};
+ int g3i[3][3] = {{1, 0, 0}, {1, 1, 0}, {1, 1, 0}};
+ struct two_d_arr g1, g2, g3;
+ two_d_arr_init(&g1, 2, 2, g1i);
+ two_d_arr_init(&g2, 3, 3, g2i);
+ two_d_arr_init(&g3, 3, 3, g3i);
+ printf("%d\n", shortestPathBinaryMatrix(g1.arr, g1.row_size,
+ g1.col_size)); // expect: 2
+ printf("%d\n", shortestPathBinaryMatrix(g2.arr, g2.row_size,
+ g3.col_size)); // expect: 4
+ printf("%d\n", shortestPathBinaryMatrix(g3.arr, g3.row_size,
+ g3.col_size)); // expect: -1
+ two_d_arr_free(&g1);
+ two_d_arr_free(&g2);
+ two_d_arr_free(&g3);
}