commit bf1a8409bf56b56a8d44ddfe5934a39e9d9ef339
parent b3e8f9306953f5cb89c50fd9ee4b344f68fc2388
Author: Jack Sangdahl <jack@pngu.org>
Date: Thu, 2 Jul 2026 22:01:40 -0600
3286. find a safe walk through a grid
Diffstat:
2 files changed, 159 insertions(+), 0 deletions(-)
diff --git a/find_safe_walk_through_grid.c b/find_safe_walk_through_grid.c
@@ -0,0 +1,101 @@
+// 3286. Find a Safe Walk Through a Grid
+#include "leetcode.h"
+
+/*
+ * you are given an 'm x n' binary matrix 'grid' and an integer 'health'. you
+ * start on the upper left corner and would like to get to the lower right
+ * corner. you can move up, down, left, or right from one cell to another
+ * adjacent cell as long as your health remains positive. cells '(i, j)' with
+ * grid 'grid[i][j] == 1' are considered unsafe and reduce your health by 1.
+ * return true if you can reach the final cell with a health of value 1 or more,
+ * and false otherwise.
+ */
+
+struct pair {
+ int x;
+ int y;
+};
+
+bool findSafeWalk(int **grid, int gridSize, int *gridColSize, int health) {
+ int row = gridSize, col = gridColSize[0];
+ int **dist = (int **)malloc(row * sizeof(int *));
+ for (int i = 0; i < row; i++) {
+ dist[i] = (int *)malloc(col * sizeof(int));
+ for (int j = 0; j < col; j++)
+ dist[i][j] = -2;
+ }
+ int max_size = row * col * 2 + 5;
+ struct pair *q = (struct pair *)malloc(max_size * sizeof(struct pair));
+ int front = max_size / 2, back = max_size / 2;
+ q[back++] = (struct pair){0, 0};
+ if (grid[0][0]) {
+ dist[0][0] = health - 1;
+ if (dist[0][0] <= 0) {
+ for (int i = 0; i < row; i++)
+ free(dist[i]);
+ free(dist);
+ free(q);
+ return false;
+ }
+ } else
+ dist[0][0] = health;
+ int dirs[4][2] = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}};
+ while (front < back) {
+ struct pair curr = q[front++];
+ int i = curr.x, j = curr.y;
+ if (i == row - 1 && j == col - 1) {
+ for (int k = 0; k < row; k++)
+ free(dist[k]);
+ free(dist);
+ free(q);
+ return true;
+ }
+ for (int d = 0; d < 4; d++) {
+ int x = i + dirs[d][0];
+ int y = j + dirs[d][1];
+ if (x >= 0 && x < row && y >= 0 && y < col && dist[x][y] == -2) {
+ int cost = grid[x][y] == 1 ? 1 : 0;
+ int new_health = dist[i][j] - cost;
+ if (new_health > 0 && new_health > dist[x][y]) {
+ dist[x][y] = new_health;
+ if (!cost)
+ q[--front] = (struct pair){x, y};
+ else
+ q[back++] = (struct pair){x, y};
+ }
+ }
+ }
+ }
+ for (int i = 0; i < row; i++)
+ free(dist[i]);
+ free(dist);
+ free(q);
+ return false;
+}
+
+int main() {
+ int g1i[3][5] = {{0, 1, 0, 0, 0}, {0, 1, 0, 1, 0}, {0, 0, 0, 1, 0}};
+ int g2i[4][6] = {{0, 1, 1, 0, 0, 0},
+ {1, 0, 1, 0, 0, 0},
+ {0, 1, 1, 1, 0, 1},
+ {0, 0, 1, 0, 1, 0}};
+ int g3i[3][3] = {{1, 1, 1}, {1, 0, 1}, {1, 1, 1}};
+ struct two_d_arr *g1 =
+ two_d_arr_init(ARRAY_SIZE(g1i), ARRAY_SIZE(g1i[0]), g1i);
+ struct two_d_arr *g2 =
+ two_d_arr_init(ARRAY_SIZE(g2i), ARRAY_SIZE(g2i[0]), g2i);
+ struct two_d_arr *g3 =
+ two_d_arr_init(ARRAY_SIZE(g3i), ARRAY_SIZE(g3i[0]), g3i);
+ bool r1 = findSafeWalk(g1->arr, g1->row_size, g1->col_size, 1);
+ bool r2 = findSafeWalk(g2->arr, g2->row_size, g2->col_size, 3);
+ bool r3 = findSafeWalk(g3->arr, g3->row_size, g3->col_size, 5);
+ printf("%d\n", r1);
+ assert(r1 == true);
+ printf("%d\n", r2);
+ assert(r2 == false);
+ printf("%d\n", r3);
+ assert(r3 == true);
+ two_d_arr_free(g1);
+ two_d_arr_free(g2);
+ two_d_arr_free(g3);
+}
diff --git a/find_safe_walk_through_grid.py b/find_safe_walk_through_grid.py
@@ -0,0 +1,58 @@
+# 3286. Find a Safe Walk Through a Grid
+from functools import lru_cache
+from itertools import product
+
+"""
+you are given an 'm x n' binary matrix 'grid' and an integer 'health'. you
+start on the upper left corner and would like to get to the lower right
+corner. you can move up, down, left, or right from one cell to another
+adjacent cell as long as your health remains positive. cells '(i, j)' with
+grid 'grid[i][j] == 1' are considered unsafe and reduce your health by 1.
+return true if you can reach the final cell with a health of value 1 or more,
+and false otherwise.
+"""
+
+
+class Solution:
+ def findSafeWalk(self, grid: List[List[int]], health: int) -> bool:
+ @lru_cache(None)
+ def dp(x, y, health_used):
+ if health_used == health or (x, y) not in eligible:
+ return float("inf")
+ cnt = health_used + grid[x][y]
+ if (x, y) == (m - 1, n - 1):
+ return cnt
+ eligible.discard((x, y))
+ res = min(
+ dp(x + 1, y, cnt),
+ dp(x, y + 1, cnt),
+ dp(x - 1, y, cnt),
+ dp(x, y - 1, cnt),
+ )
+ eligible.add((x, y))
+ return res
+
+ m, n = len(grid), len(grid[0])
+ eligible = set(product(range(m), range(n)))
+ return dp(0, 0, 0) < health
+
+
+if __name__ == "__main__":
+ obj = Solution()
+ print(
+ obj.findSafeWalk(
+ grid=[[0, 1, 0, 0, 0], [0, 1, 0, 1, 0], [0, 0, 0, 1, 0]], health=1
+ )
+ )
+ print(
+ obj.findSafeWalk(
+ grid=[
+ [0, 1, 1, 0, 0, 0],
+ [1, 0, 1, 0, 0, 0],
+ [0, 1, 1, 1, 0, 1],
+ [0, 0, 1, 0, 1, 0],
+ ],
+ health=3,
+ )
+ )
+ print(obj.findSafeWalk(grid=[[1, 1, 1], [1, 0, 1], [1, 1, 1]], health=5))
