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 before

Note without the visited set/matrix this would not work. Because without the visited set/matrix, we have to override the grid value to something like "1", which means that when we look at a previously visited cell of another "value", the code will mistakenly think it has hit a cycle. e.g. It has no way of distinguishing between a visited cell of value "a" or a visited cell of value "b".

return True

grid[i_next][j_next] is equal to "value" and we have not visited this cell before

visited.add((i_next, j_next)) neighbors.append((i_next, j_next, i, j))

return False

any_cycle = False for i in range(row_num): for j in range(col_num): if (i, j) not in visited: any_cycle |= findCycleBFS(i, j, grid[i][j])

return any_cycle