from collections import deque

class Solution:
    def get_neighbors(self, matrix, i, j):
        neighbors = []
        rows = [-1, 0, 1, 0]
        cols = [0, 1, 0, -1]
        for k in range(len(rows)):
            x = rows[k] + i
            y = cols[k] + j
            if x >= 0 and x < len(matrix) and y >= 0 and y < len(matrix[0]):
                neighbors.append((x, y))
        return neighbors
   
    def bfs(self, matrix, row, col, ch):
        q = deque([(row, col)])
        visited = {(row, col): (None, None)} # we store the visted x,y : to parent x, y
        while q:
            x, y = q.popleft()
            for nx, ny in self.get_neighbors(matrix, x, y):
                if matrix[nx][ny] == ch:
                    # if the current cell was not visited by its neighbor 'that found visited'
                    if (nx, ny) in visited and (nx, ny) != visited[(x, y)] :
                        return True
                    elif (nx, ny) not in visited:
                        visited[(nx, ny)] = (x, y)
                        q.append((nx, ny))
        return False

    def hasCycle(self, matrix):
        visited = {}
        for i in range(len(matrix)):
            for j in range(len(matrix[i])):
                if (i, j) not in visited and self.bfs(matrix, i, j, matrix[i][j]):
                    return True
        return False