¿Puedo incrementar una variable, inicializada como 0, como argumento en una función recursiva y al final simplemente agregar este número a un array?

Se me proporciona una matriz que contiene solo 1’s y 0’s, donde los 1’s adyacentes (horizontal o verticalmente, NO diagonalmente) forman ríos. Se me pide que devuelva una matriz de todos los tamaños de ríos en la matriz.

Por ejemplo:

(Tengan en cuenta que el orden de los tamaños de los ríos no importa, ¡pueden estar en cualquier orden!) es una solución válida.

Estoy escribiendo la parte recursiva del código, donde al explorar la matriz, si nos encontramos con un 1, ejecutaremos una recursión para explorar sus adyacentes izquierda, derecha, arriba y abajo en busca de otros 1’s.
El código es bastante largo y no creo que sea necesario para mi pregunta. Mi pregunta es, a medida que llamo a la función recursiva y actualizo currentRiverSize +1 (inicializado como 0) en el argumento de la función recursiva a medida que encontramos más 1’s, ¿puedo simplemente agregar esto al final a la matriz?

¡Siento que la recursión no está estructurada correctamente!

def findAllRiverSizes(matrix): riverSizes = [] exploreRiver(matrix, row, col, entryExplored, riverSizes, 0): def exploreRiver(matrix, row, col, entryExplored, riverSizes, currentRiverSize): # buscar a la derecha: if col < len(matrix[0])-1 and not entryExplored[row][col+1] and matrix[row][col+1] == 1: entryExplored[row][col+1] = True exploreRiver(matrix, row, col+1, entryExplored, riverSizes, currentRiverSize+1) # buscar a la izquierda if col > 0 and not entryExplored[row][col-1] and matrix[row][col-1] == 1: entryExplored[row][col-1] = True exploreRiver(matrix, row, col-1, entryExplored, riverSizes, currentRiverSize+1) # buscar arriba if row > 0 and not entryExplored[row-1][col] and matrix[row-1][col] == 1: entryExplored[row-1][col] = True exploreRiver(matrix, row-1, col, entryExplored, riverSizes, currentRiverSize+1) # buscar abajo if row < len(matrix)-1 and not entryExplored[row+1][col] and matrix[row+1][col] == 1: entryExplored[row+1][col] = True exploreRiver(matrix, row+1, col, entryExplored, riverSizes, currentRiverSize+1) riverSizes.append(currentRiverSize) return riverSizes

davy.ai

July 28, 2023 at 3:28 pm

Sí, puedes actualizar currentRiverSize +1 en el argumento de la función recursiva a medida que encuentres más 1’s, y luego agregarlo al array riverSizes. Sin embargo, la posición en la que estás agregando currentRiverSize actualmente es incorrecta.

En tu código, estás agregando currentRiverSize a riverSizes al final de cada llamada recursiva. Esto significa que agregarás currentRiverSize varias veces para cada río.

Para solucionar esto, debes agregar currentRiverSize a riverSizes solo una vez que hayas terminado de explorar todo el río. Esto significa que debes mover la línea riverSizes.append(currentRiverSize) fuera de las llamadas recursivas y ejecutarla solo cuando la recursión haya terminado de explorar el río.

Aquí está el código corregido:

def findAllRiverSizes(matrix): 
    riverSizes = []
    entryExplored = [[False for val in row] for row in matrix] # inicializa los elementos explorados como falsos
    for row in range(len(matrix)):
        for col in range(len(matrix[row])):
            if not entryExplored[row][col]: # solo explora los 1's no explorados
                exploreRiver(matrix,row,col,entryExplored,riverSizes,0)
    return riverSizes

def exploreRiver(matrix,row,col,entryExplored,riverSizes,currentRiverSize): 
    if row<0 or col<0 or row>=len(matrix) or col>=len(matrix[0]): # verifica si está fuera de los límites de la matriz
        return 
    if entryExplored[row][col] or matrix[row][col] == 0: # verifica si ya ha sido explorado o no es un 1
        return 

    entryExplored[row][col] = True # marcar como explorado y continuar explorando vecinos
    currentRiverSize += 1
    exploreRiver(matrix,row+1,col,entryExplored,riverSizes,currentRiverSize) # mirar hacia abajo
    exploreRiver(matrix,row-1,col,entryExplored,riverSizes,currentRiverSize) # mirar hacia arriba
    exploreRiver(matrix,row,col+1,entryExplored,riverSizes,currentRiverSize) # mirar hacia la derecha
    exploreRiver(matrix,row,col-1,entryExplored,riverSizes,currentRiverSize) # mirar hacia la izquierda
    riverSizes.append(currentRiverSize) # agregar a riverSizes una vez que se haya terminado de explorar todo el río

En este código, también he incluido algunas comprobaciones adicionales para asegurarnos de no intentar explorar elementos fuera de los límites de la matriz o elementos que ya han sido explorados. Esto mejora la eficiencia del código.

es.davy.ai

¿Tienes una pregunta?

¿Puedo incrementar una variable, inicializada como 0, como argumento en una función recursiva y al final simplemente agregar este número a un array?

Answer

davy.ai