diff options
author | Jack Sangdahl <[email protected]> | 2025-01-07 16:30:51 +0100 |
---|---|---|
committer | Jack Sangdahl <[email protected]> | 2025-01-07 16:30:51 +0100 |
commit | f456a519266258e8f392e183bc9e1bc399942dca (patch) | |
tree | 21a9d233e252496c560008d5f129ab02c625a42f | |
parent | ceb33bb2e9b3bcc6abe83a7aaa8f103c4bbace17 (diff) | |
download | leetcode-f456a519266258e8f392e183bc9e1bc399942dca.tar.gz leetcode-f456a519266258e8f392e183bc9e1bc399942dca.zip |
1091. shortest path in binary matrix
-rw-r--r-- | shortest_path_binary_matrix.c | 158 | ||||
-rw-r--r-- | shortest_path_binary_matrix.cpp | 45 | ||||
-rw-r--r-- | shortest_path_binary_matrix.py | 49 |
3 files changed, 154 insertions, 98 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); } diff --git a/shortest_path_binary_matrix.cpp b/shortest_path_binary_matrix.cpp index 67cd095..cbdccdc 100644 --- a/shortest_path_binary_matrix.cpp +++ b/shortest_path_binary_matrix.cpp @@ -1,40 +1,55 @@ +// 1091. Shortest Path in Binary Matrix #include "leetcode.h" -#include <algorithm> -#include <queue> -#include <utility> -#include <vector> + +/* + * given an n x n binary matrix 'grid', return the length of the shortest clear + * path in the matrix. if there is no clear path, return -1. a clear path in a + * binary matrix is a path from the top-left cell (ie. 0,0) to the bottom-right + * cell (ie. n - 1, n - 1) such thatyt + * - all the visited cells are of the path 0 + * - all the adjacent cells of the path are 8-directionally connected (ie. they + * are different and they share an edge of a corner) the length of a clear path + * is the number of visited cells of this path + */ class Solution { public: int shortestPathBinaryMatrix(vector<vector<int>> &grid) { if (grid[0][0] || grid.back().back()) return -1; - int ans = 2, len = 1, nX = grid[0].size() - 1, nY = grid.size() - 1; + int ans = 2, n = 1, nr = grid[0].size() - 1, nc = grid.size() - 1; queue<pair<int, int>> qp; - if (!nX && !nY) + if (!nr && !nc) return 1 - (grid[0][0] << 1); qp.push({0, 0}); grid[0][0] = -1; - while (len) { - while (len--) { - auto [cX, cY] = qp.front(); + while (n) { + while (n--) { + auto [cx, cy] = qp.front(); qp.pop(); - for (int i = max(0, cX - 1), lmtX = min(cX + 1, nX); i <= lmtX; i++) { - for (int j = max(0, cY - 1), lmtY = min(cY + 1, nY); j <= lmtY; j++) { - if (i == nX && j == nY) + for (int i = max(0, cx - 1), lmtx = min(cx + 1, nr); i <= lmtx; i++) + for (int j = max(0, cy - 1), lmty = min(cy + 1, nc); j <= lmty; j++) { + if (i == nr && j == nc) return ans; if (!grid[j][i]) { grid[j][i] = -1; qp.push({i, j}); } } - } } ans++; - len = qp.size(); + n = qp.size(); } return -1; } }; -int main() {} +int main() { + Solution obj; + vvd(int) g1 = {{0, 1}, {1, 0}}; + vvd(int) g2 = {{0, 0, 0}, {1, 1, 0}, {1, 1, 0}}; + vvd(int) g3 = {{1, 0, 0}, {1, 1, 0}, {1, 1, 0}}; + printf("%d\n", obj.shortestPathBinaryMatrix(g1)); // expect: 2 + printf("%d\n", obj.shortestPathBinaryMatrix(g2)); // expect: 4 + printf("%d\n", obj.shortestPathBinaryMatrix(g3)); // expect: -1 +} diff --git a/shortest_path_binary_matrix.py b/shortest_path_binary_matrix.py new file mode 100644 index 0000000..ee95833 --- /dev/null +++ b/shortest_path_binary_matrix.py @@ -0,0 +1,49 @@ +# 1091. Shortest Path in Binary Matrix + +""" +given an n x n binary matrix 'grid', return the length of the shortest clear +path in the matrix. if there is no clear path, return -1. a clear path in a +binary matrix is a path from the top-left cell (ie. 0,0) to the bottom-right +cell (ie. n - 1, n - 1) such thatyt +- all the visited cells are of the path 0 +- all the adjacent cells of the path are 8-directionally connected (ie. they +are different and they share an edge of a corner) the length of a clear path +is the number of visited cells of this path +""" + + +class Solution(object): + def shortestPathBinaryMatrix(self, grid): + """ + :type grid: List[List[int]] + :rtype: int + """ + n = len(grid) + if grid[0][0] or grid[n - 1][n - 1]: + return -1 + q = [(0, 0, 1)] + grid[0][0] = 1 + for i, j, d in q: + if i == n - 1 and j == n - 1: + return d + for x, y in ( + (i - 1, j - 1), + (i - 1, j), + (i - 1, j + 1), + (i, j - 1), + (i, j + 1), + (i + 1, j - 1), + (i + 1, j), + (i + 1, j + 1), + ): + if 0 <= x < n and 0 <= y < n and not grid[x][y]: + grid[x][y] = 1 + q.append((x, y, d + 1)) + return -1 + + +if __name__ == "__main__": + obj = Solution() + print(obj.shortestPathBinaryMatrix(grid=[[0, 1], [1, 0]])) + print(obj.shortestPathBinaryMatrix(grid=[[0, 0, 0], [1, 1, 0], [1, 1, 0]])) + print(obj.shortestPathBinaryMatrix(grid=[[1, 0, 0], [1, 1, 0], [1, 1, 0]])) |