Solution: Problem Challenge 3

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 ne

'''
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

class Solution: def containsCycle(self, grid: List[List[str]]) -> bool:

BFS

row_num = len(grid) col_num = len(grid[0]) visited = set()

def findCycleBFS(i, j, value): neighbors = deque() neighbors.append((i, j, None, None))

while neighbors: (i, j, i_prev, j_prev) = neighbors.popleft() grid[i][j] = "1" # original value is a letter, setting a number to signify visited for row_increment, col_increment in [(1, 0), (-1, 0), (0, 1), (0, -1)]: i_next, j_next = i + row_increment, j + col_increment

if i_next == i_prev and j_next == j_prev: continue # do not go back to previous cell, skipping this path if i_next < 0 or i_next >= row_num or j_next < 0 or j_next >= col_num: continue if grid[i_next][j_next] != value: continue if (i_next, j_next) in visited: #cell with the same value visited bef