commit 6ae28ab4a88ede5b536e3f6625a08c249af4d562
parent e1a3b8039965502c833f0bac3e8b3ef92b5cff23
Author: Jack Sangdahl <jack@pngu.org>
Date: Sun, 26 Apr 2026 21:18:18 -0600
1391. check if there is a valid path in a grid
Diffstat:
2 files changed, 153 insertions(+), 0 deletions(-)
diff --git a/check_valid_path_grid.c b/check_valid_path_grid.c
@@ -0,0 +1,99 @@
+// 1391. Check if There is a Valid Path in a Grid
+#include "leetcode.h"
+
+/*
+ * you are given an 'm x n' 'grid'. each cell of 'grid' represents a street. the
+ * street of 'grid[i][j]' can be 1 .. 6, connecting to a left/upper/right cell
+ * and the right/lower/upper cell. you will initially start at the street of the
+ * upper left cell '(0, 0)'. a valid path in the grid is the path that starts
+ * from the upper left cell '(0, 0)' and ends at the bottom right cell '(m - 1,
+ * n - 1)'. the path should only follow the streets. notice that you are not
+ * allowed to change any street. return true if there is a valid path in the
+ * grid or 'false' otherwise.
+ */
+
+bool has_opening(int type, int dir) {
+ if (type == 1)
+ return dir == 0 || dir == 1;
+ if (type == 2)
+ return dir == 2 || dir == 3;
+ if (type == 3)
+ return dir == 0 || dir == 3;
+ if (type == 4)
+ return dir == 1 || dir == 3;
+ if (type == 5)
+ return dir == 0 || dir == 2;
+ if (type == 6)
+ return dir == 1 || dir == 2;
+ return false;
+}
+
+bool hasValidPath(int **grid, int gridSize, int *gridColSize) {
+ int m = gridSize, n = gridColSize[0];
+ if (m == 1 && n == 1)
+ return true;
+ static int dirs[4][2] = {{0, -1}, {0, 1}, {-1, 0}, {1, 0}};
+ static int next_step[7][4] = {{4, 4, 4, 4}, {1, 0, 4, 4}, {4, 4, 3, 2},
+ {3, 4, 4, 0}, {4, 3, 4, 1}, {2, 4, 0, 4},
+ {4, 2, 1, 4}};
+ int start_type = grid[0][0];
+ bool **vis = (bool **)calloc(m, sizeof(bool *));
+ for (int i = 0; i < m; i++)
+ vis[i] = (bool *)calloc(n, sizeof(bool));
+ for (int d = 0; d < 4; d++) {
+ if (!has_opening(start_type, d))
+ continue;
+ int r = 0, c = 0, out_dir = d;
+ vis[0][0] = true;
+ while (true) {
+ int nr = r + dirs[out_dir][0];
+ int nc = c + dirs[out_dir][1];
+ if (nr < 0 || nr >= m || nc < 0 || nc >= n || vis[nr][nc])
+ break;
+ int in_dir = !(out_dir % 2) ? out_dir + 1 : out_dir - 1;
+ int n_type = grid[nr][nc];
+ if (!has_opening(n_type, in_dir))
+ break;
+ if (nr == m - 1 && nc == n - 1) {
+ for (int i = 0; i < m; i++)
+ free(vis[i]);
+ free(vis);
+ return true;
+ }
+ vis[nr][nc] = true;
+ r = nr;
+ c = nc;
+ out_dir = next_step[n_type][in_dir];
+ if (out_dir == 4)
+ break;
+ }
+ }
+ for (int i = 0; i < m; i++)
+ free(vis[i]);
+ free(vis);
+ return false;
+}
+
+int main() {
+ int g1i[2][3] = {{2, 4, 3}, {6, 5, 2}};
+ int g2i[2][3] = {{1, 2, 1}, {1, 2, 1}};
+ int g3i[1][3] = {{1, 1, 2}};
+ 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 = hasValidPath(g1->arr, g1->row_size, g1->col_size);
+ bool r2 = hasValidPath(g2->arr, g2->row_size, g2->col_size);
+ bool r3 = hasValidPath(g3->arr, g3->row_size, g3->col_size);
+ printf("%d\n", r1);
+ assert(r1 == true);
+ printf("%d\n", r2);
+ assert(r2 == false);
+ printf("%d\n", r3);
+ assert(r3 == false);
+ two_d_arr_free(g1);
+ two_d_arr_free(g2);
+ two_d_arr_free(g3);
+}
diff --git a/check_valid_path_grid.py b/check_valid_path_grid.py
@@ -0,0 +1,54 @@
+# 1391. Check if There is a Valid Path in a Grid
+from typing import List
+
+"""
+you are given an 'm x n' 'grid'. each cell of 'grid' represents a street. the
+street of 'grid[i][j]' can be 1 .. 6, connecting to a left/upper/right cell
+and the right/lower/upper cell. you will initially start at the street of the
+upper left cell '(0, 0)'. a valid path in the grid is the path that starts
+from the upper left cell '(0, 0)' and ends at the bottom right cell '(m - 1,
+n - 1)'. the path should only follow the streets. notice that you are not
+allowed to change any street. return true if there is a valid path in the
+grid or 'false' otherwise.
+"""
+
+
+class Solution:
+ def hasValidPath(self, grid: List[List[int]]) -> bool:
+ if not grid:
+ return true
+ directions = {
+ 1: [(0, -1), (0, 1)],
+ 2: [(-1, 0), (1, 0)],
+ 3: [(0, -1), (1, 0)],
+ 4: [(0, 1), (1, 0)],
+ 5: [(0, -1), (-1, 0)],
+ 6: [(0, 1), (-1, 0)],
+ }
+ vis = set()
+ goal = (len(grid) - 1, len(grid[0]) - 1)
+
+ def dfs(i, j):
+ vis.add((i, j))
+ if (i, j) == goal:
+ return True
+ for d in directions[grid[i][j]]:
+ ni, nj = i + d[0], j + d[1]
+ if (
+ 0 <= ni < len(grid)
+ and 0 <= nj < len(grid[0])
+ and (ni, nj) not in vis
+ and (-d[0], -d[1]) in directions[grid[ni][nj]]
+ ):
+ if dfs(ni, nj):
+ return True
+ return False
+
+ return dfs(0, 0)
+
+
+if __name__ == "__main__":
+ obj = Solution()
+ print(obj.hasValidPath(grid=[[2, 4, 3], [6, 5, 2]]))
+ print(obj.hasValidPath(grid=[[1, 2, 1], [1, 2, 1]]))
+ print(obj.hasValidPath(grid=[[1, 1, 2]]))
