dfs_match3_algo

def find_lines(grid):
    lines = []
    rows = len(grid)
    cols = len(grid[0])

    # Check horizontal lines
    for r in range(rows):
        count = 1
        for c in range(1, cols):
            if grid[r][c] == grid[r][c - 1] and grid[r][c] in ('b', 'c'):
                count += 1
            else:
                if count >= 2:
                    lines.append([(r, c - i) for i in range(count)])
                count = 1
        if count >= 2:
            lines.append([(r, cols - i - 1) for i in range(count)])

    # Check vertical lines
    for c in range(cols):
        count = 1
        for r in range(1, rows):
            if grid[r][c] == grid[r - 1][c] and grid[r][c] in ('b', 'c'):
                count += 1
            else:
                if count >= 2:
                    lines.append([(r - i, c) for i in range(count)])
                count = 1
        if count >= 2:
            lines.append([(rows - i - 1, c) for i in range(count)])

    return lines

#Check Adjacency -- NOT USING
def is_adjacent(d_pos, a_pos):
    return (abs(d_pos[0] - a_pos[0]) <= 1 and abs(d_pos[1] - a_pos[1]) <= 1)


#Path Traversal:
def traverse_lines(grid, d_pos, lines):
    visited = set()
    stack = [d_pos]

    while stack:
        current = stack.pop()
        if current in visited:
            continue
        visited.add(current)

        # Check if current position is part of any line
        for line in lines:
            if current in line:
                # Mark the line as visited
                for pos in line:
                    visited.add(pos)
                # Add adjacent positions to stack
                for pos in line:
                    for adj in get_adjacent_positions(pos):
                        if adj not in visited:
                            stack.append(adj)


# Return all adjacent positions (up, down, left, right)
def get_adjacent_positions(pos):
    return [(pos[0] + dx, pos[1] + dy) for dx, dy in [(-1, 0), (1, 0), (0, -1), (0, 1)]]


def main(grid):
    d_pos = None
    a_pos = None
    for r in range(len(grid)):
        for c in range(len(grid[0])):
            #print(r, "   ", c)
            if grid[r][c] == 'd':
                d_pos = (r, c)
            elif grid[r][c] == 'a':
                a_pos = (r, c)

    lines = find_lines(grid)
    print("lines:   ", lines)
    traverse_lines(grid, d_pos, lines)
    print("Traversal complete.")

# Example grid
grid = [
    ['a', 'a', 'b', 'a', 'a'],
    ['a', 'a', 'b', 'a', 'a'],
    ['a', 'a', 'b', 'b', 'd'],
    ['c', 'c', 'c', 'c', 'c'],
    ['a', 'a', 'c', 'a', 'a'],
    ['a', 'a', 'c', 'a', 'a']
]

if __name__ == '__main__':
    main(grid)