'''
A00|A01|A02|V03
---|---|---|---
A10|V11|A12|A13
---|---|---|---
A20|A21|A22|V23

NULL -> 00 -> 01 -> 02 -> 12 -> 13 
         ^             -> 22 -> 22 -> 21 -> 20 -> 20 -> 10
         |                                               |
         |-----------<-------------------<-------------<-|                 

if N is the curren node and: 
   1- has been seen already and
   2- has a parent NULL
      we found the cycle 

if N is the curren and: 
   1- Has been seen already and
   2- Has a parent that is not NULL 
     Exit = "it has been visted in the previouse step"

if N is the curren node and: 
    1- Has not been seen
       - mark the neighbor as seen and set the paren to prviouse node
       - go deeper in the matrix and repeat the process
'''
class Solution:

  def get_neigbors(self, matrix, i, j):
    neigbors = []
    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]):
        neigbors.append((x, y))
    return neigbors

  def dfs(self, matrix, i, j, p_x, p_y, seen, ch):
    if (i, j) in seen and seen[(i, j)] == (None, None):
      return True
    if (i, j) in seen and seen[(i, j)] != (None, None):
      return False
    
    seen[(i, j)] = (p_x, p_y)

    result = False

    for x, y in self.get_neigbors(matrix, i, j):
        if matrix[x][y] == ch and (x, y) != (p_x, p_y): # avoid going back
          result |= self.dfs(matrix, x, y, i, j, seen, ch)
          
    return result

  def hasCycle(self, matrix):
    for i in range(len(matrix)):
      for j in range(len(matrix[i])):
        seen = {}
        if self.dfs(matrix, i, j, None, None, seen, matrix[i][j]):
          return True
    return False