Given a 2D array of characters grid of size m x n, you need 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 (up, down, left, or right), if it has the same value of the current cell.

Also, you cannot move to the cell that you visited in your last move. For example, the cycle (1, 1) -&gt; (1, 2) -&gt; (1, 1) is invalid because from (1, 2) we visited (1, 1) which was the last visited cell.

Return true if any cycle of the same value exists in grid, otherwise, return false.

&nbsp;
Example 1:



Input: grid = [["a","a","a","a"],["a","b","b","a"],["a","b","b","a"],["a","a","a","a"]]
Output: true
Explanation: There are two valid cycles shown in different colors in the image below:



Example 2:



Input: grid = [["c","c","c","a"],["c","d","c","c"],["c","c","e","c"],["f","c","c","c"]]
Output: true
Explanation: There is only one valid cycle highlighted in the image below:



Example 3:



Input: grid = [["a","b","b"],["b","z","b"],["b","b","a"]]
Output: false


&nbsp;
Constraints:


	m == grid.length
	n == grid[i].length
	1 &lt;= m, n &lt;= 500
	grid consists only of lowercase English letters.


class Solution:
    def containsCycle(self, grid: List[List[str]]) -> bool:
        
        def getNeighbours(row,col,char):
            neighbours = []
            if row > 0 and grid[row-1][col] == char and not visited[row-1][col]:
                neighbours.append([row-1,col])
            if col > 0 and grid[row][col-1] == char and not visited[row][col-1]:
                neighbours.append([row,col-1])
            if row < len(grid)-1 and grid[row+1][col] == char and not visited[row+1][col]:
                neighbours.append([row+1,col])
            if col < len(grid[0])-1 and grid[row][col+1] == char and not visited[row][col+1]:
                neighbours.append([row,col+1])
            return neighbours
        
        def dfs(row,col,char,cyclePresent):
            if visited[row][col] or cyclePresent:
                cyclePresent = True
                return cyclePresent
            visited[row][col] = True
            neighbours = getNeighbours(row,col,char)
            for r,c in neighbours:
                cyclePresent = dfs(r,c,char,cyclePresent)
            return cyclePresent
        
        visited = [[False for _ in range(len(grid[0]))] for _ in range(len(grid))]
        cyclePresent = False
        for row in range(len(grid)):
            for col in range(len(grid[0])):
                if cyclePresent:
                    return True
                if visited[row][col]:
                    continue
                cyclePresent = dfs(row,col,grid[row][col],cyclePresent)
        
        return cyclePresent
class Solution {
    public boolean containsCycle(char[][] grid) {
        int rows = grid.length, cols = grid[0].length;

		// Create a boolean array of same dimensions to keep track of visited cells
        boolean[][] visited = new boolean[rows][cols];
        
        for (int i = 0; i < rows; i++) {
            for (int j = 0; j < cols; j++) {
                if (!visited[i][j] && dfs(grid, visited, i, j, 0, 0, grid[i][j])) {
                    return true;
                }
            }
        }

        return false;
    }
    
    public boolean dfs(
        char[][] grid,
        boolean[][] visited,
        int i,
        int j,
        int prevI,
        int prevJ,
        char c
    ) {
		// Check for out of bounds
        if (i < 0 || i >= grid.length || j < 0 || j >= grid[0].length) return false;

		// Check whether the current char matches the previous char
        if (grid[i][j] != c) return false;
		
		// If we stumble upon the same cell, we're guaranteed to have found a cycle!
        if (visited[i][j]) {
            return true;
        }
        
		// Mark the cell as visited
        visited[i][j] = true;
        
		// We want to search in the south direction ONLY IF we didn't come from north
		// Do the same for all four directions
        boolean south = i - prevI != -1;
        boolean north = i - prevI != 1;
        boolean east = j - prevJ != -1;
        boolean west = j - prevJ != 1;
        return
            (south && dfs(grid, visited, i + 1, j, i, j, c)) ||
            (north && dfs(grid, visited, i - 1, j, i, j, c)) ||
            (east && dfs(grid, visited, i, j + 1, i, j, c)) ||
            (west && dfs(grid, visited, i, j - 1, i, j, c));
    }
}
class Solution {
public:
    int dx[4]={-1,1,0,0};
    int dy[4]={0,0,1,-1};
    bool solve(vector<vector<char>>& grid,int i,int j,int m,int n,int x,int y,vector<vector<int>>&vis,char startChar){
        vis[i][j]=1;
        for(int k=0;k<4;k++){
            int xx=i+dx[k];
            int yy=j+dy[k];
            if(xx>=0 && yy>=0 && xx<m && yy<n && grid[xx][yy]==startChar && !(x == xx && y == yy)){
              if(vis[xx][yy] || solve(grid, xx , yy , m , n, i, j,vis,startChar))
                    return true;
            }
        }
        return false;
    }

    bool containsCycle(vector<vector<char>>& grid) {
     int m=grid.size();
     int n=grid[0].size();
     vector<vector<int>>vis(m,vector<int>(n,0));
     for(int i=0;i<m;i++){
         for(int j=0;j<n;j++){
             if(!vis[i][j] && solve(grid,i,j,m,n,-1,-1,vis,grid[i][j])){
                 return true;
             }
         }
     }
        return false;
    }
};
/**
 * @param {character[][]} grid
 * @return {boolean}
 */
var containsCycle = function(grid) {
    const m = grid.length;
    const n = grid[0].length;
    const visited = [...Array(m)].map(i => Array(n).fill(0));
    const dir = [[-1,0],[1,0],[0,-1],[0,1]];
    
    const dfs = (x,y,lx,ly) => {        
        visited[x][y] = 1;
        for (const [a, b] of dir) {
            const nx = x + a;
            const ny = y + b;
            
            if (nx < 0 || nx > m - 1 || ny < 0 || ny > n - 1)
                continue;
            
            if (visited[nx][ny] === 1 && (nx !== lx || ny !== ly) && grid[x][y] === grid[nx][ny]) { // !!! grid[nx][ny] === grid[x][y]
                return true;
            }
            
            if (visited[nx][ny] === 0 && grid[x][y] === grid[nx][ny]) {
                if (dfs(nx,ny,x,y))
                    return true;
            }
        }
        return false;
    }
    
    for (let i = 0; i < m; i++) {
        for (let j = 0; j < n; j++) {
            if (visited[i][j] === 0 && dfs(i,j,-1,-1)) // !!!
                return true;
        }
    }
    
    return false;
};
Detect Cycles in 2D Grid