LC 1559 [M] Detect Cycles in 2D Grid - ALawliet/algorithms GitHub Wiki
DIRS = [(0,1),(0,-1),(1,0),(-1,0)]
class Solution:
def containsCycle(self, grid: List[List[str]]) -> bool:
n_rows = len(grid)
n_cols = len(grid[0])
def dfs(node, parent): # hasCycle
if node in visited: return True
visited.add(node)
r, c = node
for dr, dc in DIRS:
nr = r + dr
nc = c + dc
# in bounds and streak and not back to parent
if 0 <= nr < n_rows and 0 <= nc < n_cols and grid[nr][nc] == grid[r][c] and (nr,nc) != parent:
if dfs((nr,nc), node): return True
return False
visited = set()
for r in range(n_rows):
for c in range(n_cols):
if (r, c) in visited: continue
if dfs((r,c), None): return True
return False