aboutsummaryrefslogtreecommitdiff
diff options
context:
space:
mode:
authorJack Sangdahl <[email protected]>2025-01-07 16:30:51 +0100
committerJack Sangdahl <[email protected]>2025-01-07 16:30:51 +0100
commitf456a519266258e8f392e183bc9e1bc399942dca (patch)
tree21a9d233e252496c560008d5f129ab02c625a42f
parentceb33bb2e9b3bcc6abe83a7aaa8f103c4bbace17 (diff)
downloadleetcode-f456a519266258e8f392e183bc9e1bc399942dca.tar.gz
leetcode-f456a519266258e8f392e183bc9e1bc399942dca.zip
1091. shortest path in binary matrix
-rw-r--r--shortest_path_binary_matrix.c158
-rw-r--r--shortest_path_binary_matrix.cpp45
-rw-r--r--shortest_path_binary_matrix.py49
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]]))