diff options
Diffstat (limited to 'shortest_path_binary_matrix.c')
-rw-r--r-- | shortest_path_binary_matrix.c | 158 |
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); } |