Problem statement

https://binarysearch.com/problems/Cycle-Detection-in-a-Matrix/

Solution

Equal to Leetcode 1559. Detect Cycles in 2D Grid.

Complexity

Time and space is O(mn).

Code

class Solution:
    def solve(self, grid):
        m, n, v = len(grid), len(grid[0]), set()
        self.Found = False
        
        def dfs(xp, yp, x, y):
            if self.Found: return
            if (x, y) in v: self.Found = True
            v.add((x, y))
            for dx, dy in [[0,1], [0,-1], [1,0], [-1,0]]:
                if not 0 <= x + dx < n or not 0 <= y + dy < m: continue
                if (x + dx, y + dy) == (xp, yp) or grid[y][x] != grid[y+dy][x+dx]: continue
                dfs(x, y, x+dx, y+dy)
        
        for x, y in product(range(n), range(m)):
            if (x, y) not in v:
                dfs(-1, -1, x, y)
        
        return self.Found