commit e1a3b8039965502c833f0bac3e8b3ef92b5cff23
parent 86003e3f3bdee99c26b48c7377b665715cd56cb2
Author: Jack Sangdahl <jack@pngu.org>
Date: Sat, 25 Apr 2026 21:18:45 -0600
1559. detect cycles in 2d grid
Diffstat:
2 files changed, 145 insertions(+), 0 deletions(-)
diff --git a/detect_cycles_2d_grid.c b/detect_cycles_2d_grid.c
@@ -0,0 +1,77 @@
+// 1559. Detect Cycles in 2D Grid
+#include "leetcode.h"
+
+/*
+ * given a 2d array of characters 'grid' of size 'm x n', you eed to find if
+ * there exists any cycle consisting of the same value in 'grid'. a cycle is a
+ * path of length 4 or more in the grid that starts and ends at the same cell.
+ * from a given cell, you can move to one of the cells adjacent to it - in one
+ * of the four directions, if it has the same value of the current cell. also,
+ * you cannot move to the cell that you visited in your last move. return true
+ * if any cycle of the same value exists in 'grid', otherwise return false.
+ */
+
+bool dfs(char **grid, int m, int n, bool **vis, int i, int j, int prev,
+ char key) {
+ if (i < 0 && i >= m || j < 0 || j >= n)
+ return false;
+ if (prev != 0 && grid[i][j] != key)
+ return false;
+ if (prev != 0 && vis[i][j])
+ return true;
+ vis[i][j] = true;
+ if (prev != 1)
+ return dfs(grid, m, n, vis, i - 1, j, 3, grid[i][j]);
+ if (prev != 1)
+ return dfs(grid, m, n, vis, i, j + 1, 4, grid[i][j]);
+ if (prev != 1)
+ return dfs(grid, m, n, vis, i + 1, j, 1, grid[i][j]);
+ if (prev != 1)
+ return dfs(grid, m, n, vis, i, j - 1, 2, grid[i][j]);
+ return false;
+}
+
+void free_vis(bool **vis, int n) {
+ for (int i = 0; i < n; i++)
+ free(vis[i]);
+ free(vis);
+}
+
+bool containsCycle(char **grid, int gridSize, int *gridColSize) {
+ bool **vis = (bool **)calloc(gridSize, sizeof(bool *));
+ for (int i = 0; i < gridSize; i++)
+ vis[i] = (bool *)calloc(*gridColSize, sizeof(bool));
+ for (int i = 0; i < gridSize; i++)
+ for (int j = 0; j < *gridColSize; j++)
+ if (!vis[i][j])
+ if (dfs(grid, gridSize, *gridColSize, vis, i, j, 0, '0')) {
+ free_vis(vis, gridSize);
+ return true;
+ }
+ free_vis(vis, gridSize);
+ return false;
+}
+
+int main() {
+ char g1[4][4] = {{'a', 'a', 'a', 'a'},
+ {'a', 'b', 'b', 'a'},
+ {'a', 'b', 'b', 'a'},
+ {'a', 'a', 'a', 'a'}};
+ char g2[4][4] = {{'c', 'c', 'c', 'a'},
+ {'c', 'd', 'c', 'c'},
+ {'c', 'c', 'e', 'c'},
+ {'f', 'c', 'c', 'c'}};
+ char g3[3][3] = {{'a', 'b', 'b'}, {'b', 'z', 'b'}, {'b', 'b', 'a'}};
+ bool r1 =
+ containsCycle((char **)g1, ARRAY_SIZE(g1), (int *)ARRAY_SIZE(g1[0]));
+ bool r2 =
+ containsCycle((char **)g2, ARRAY_SIZE(g2), (int *)ARRAY_SIZE(g2[0]));
+ bool r3 =
+ containsCycle((char **)g3, ARRAY_SIZE(g3), (int *)ARRAY_SIZE(g3[0]));
+ printf("%d\n", r1);
+ assert(r1 == true);
+ printf("%d\n", r2);
+ assert(r2 == true);
+ printf("%d\n", r3);
+ assert(r3 == false);
+}
diff --git a/detect_cycles_2d_grid.py b/detect_cycles_2d_grid.py
@@ -0,0 +1,68 @@
+# 1559. Detect Cycles in 2D Grid
+from typing import List
+
+"""
+given a 2d array of characters 'grid' of size 'm x n', you eed to find if
+there exists any cycle consisting of the same value in 'grid'. a cycle is a
+path of length 4 or more in the grid that starts and ends at the same cell.
+from a given cell, you can move to one of the cells adjacent to it - in one
+of the four directions, if it has the same value of the current cell. also,
+you cannot move to the cell that you visited in your last move. return true
+if any cycle of the same value exists in 'grid', otherwise return false.
+"""
+
+
+class Solution:
+ def containsCycle(self, grid: List[List[str]]) -> bool:
+ def dfs(node, parent):
+ if node in vis:
+ return True
+ vis.add(node)
+ nx, ny = node
+ childs = [
+ (cx, cy)
+ for cx, cy in [[nx + 1, ny], [nx - 1, ny], [nx, ny + 1], [nx, ny - 1]]
+ if 0 <= cx < m
+ and 0 <= cy < n
+ and grid[cx][cy] == grid[nx][ny]
+ and (cx, cy) != parent
+ ]
+ for x in childs:
+ if dfs(x, node):
+ return True
+ return False
+
+ m, n = len(grid), len(grid[0])
+ vis = set()
+ for i in range(m):
+ for j in range(n):
+ if (i, j) in vis:
+ continue
+ if dfs((i, j), None):
+ return True
+ return False
+
+
+if __name__ == "__main__":
+ obj = Solution()
+ print(
+ obj.containsCycle(
+ grid=[
+ ["a", "a", "a", "a"],
+ ["a", "b", "b", "a"],
+ ["a", "b", "b", "a"],
+ ["a", "a", "a", "a"],
+ ]
+ )
+ )
+ print(
+ obj.containsCycle(
+ grid=[
+ ["c", "c", "c", "a"],
+ ["c", "d", "c", "c"],
+ ["c", "c", "e", "c"],
+ ["f", "c", "c", "c"],
+ ]
+ )
+ )
+ print(obj.containsCycle(grid=[["a", "b", "b"], ["b", "z", "b"], ["b", "b", "a"]]))
