Leetcode 1663 Solution

This article provides solution to leetcode question 1663 (detect-cycles-in-2d-grid)
Categories:
Tags:
Access this page by simply typing in "lcs 1663" in your browser address bar if you have bunnylol configured.

https://leetcode.com/problems/detect-cycles-in-2d-grid

Solution

class Solution:
    def findLoop(self, m, n, i, j, ch, v, visited, grid, step=0):
        if visited[i][j][0] == v:
            return step - visited[i][j][1] >= 4
        elif visited[i][j][0] != -1:
            return False

        neighs = [
            (i - 1, j),
            (i + 1, j),
            (i, j - 1),
            (i, j + 1),
        ]

        visited[i][j] = (v, step)

        for i, j in neighs:
            if not 0 <= i < m or not 0 <= j < n:
                continue

            if grid[i][j] != ch:
                continue

            if self.findLoop(m, n, i, j, ch, v, visited, grid, step + 1):
                return True

        return False

    def containsCycle(self, grid: List[List[str]]) -> bool:
        m = len(grid)
        n = len(grid[0])

        visited = [[(-1, 0) for _ in range(n)] for _ in range(m)]

        for i in range(m):
            for j in range(n):
                if self.findLoop(m, n, i, j, grid[i][j], i * n + j, visited, grid):
                    return True

        return False