Detect Cycles in 2D Grid
Given a 2D array of characters grid of size m x n, determine whether 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 an adjacent cell in one of the four directions: up, down, left, or right, if it has the same value as the current cell.
You cannot move to the cell that you visited in your last move. For example, the cycle (1, 1) -> (1, 2) -> (1, 1) is invalid because from (1, 2) you would move back to (1, 1), which was the last visited cell.
Return true if any cycle of the same value exists in grid; otherwise, return false.
Example 1
a a a a a b b a a b b a a a a a
Input
grid = [["a","a","a","a"],["a","b","b","a"],["a","b","b","a"],["a","a","a","a"]]Output
trueThere are two valid cycles of the same value in the grid.
Example 2
c c c a c d c c c c e c f c c c
Input
grid = [["c","c","c","a"],["c","d","c","c"],["c","c","e","c"],["f","c","c","c"]]Output
trueThere is one valid cycle of the same value in the grid.
Constraints
- m == grid.length
- n == grid[i].length
- 1 <= m, n <= 500
- grid consists only of lowercase English letters.