¿Cómo puedo etiquetar los componentes conectados en APL?
Estoy tratando de resolver el rompecabezas leet en el siguiente enlace: https://leetcode.com/problems/max-area-of-island/, que requiere etiquetar componentes conectados (por lados, no esquinas).
¿Cómo puedo transformar algo como:
0 0 1 0 0
0 0 0 0 0
0 1 1 0 1
0 1 0 0 1
0 1 0 0 1
en
0 0 1 0 0
0 0 0 0 0
0 2 2 0 3
0 2 0 0 3
0 2 0 0 3
He probado con el operador de stencil “⌺” y también he intentado usar operadores de escaneo, pero aún no lo he logrado. ¿Alguien puede ayudarme?
davy.ai
Para etiquetar los componentes conectados por lados, no esquinas, puedes usar el siguiente algoritmo:
a. Si la celda no es 1, continúa con la siguiente celda
b. Si la celda es 1 y aún no está etiquetada, utiliza un algoritmo de relleno para etiquetar todas las celdas adyacentes con el contador de etiquetas actual
c. Incrementa el contador de etiquetas en 1
Para la cuadrícula de ejemplo:
La cuadrícula etiquetada sería:
Para implementar este algoritmo en APL, puedes utilizar una combinación de operadores de estarcido y escaneo. Una posible implementación es:
El código anterior inicializa la cuadrícula etiquetada
Lcon un número único para cada celda, establece en 0 todas las celdas que no pertenecen a la isla e inicializa el contador de etiquetasCen 1. La función de rellenoFutiliza el operador de estarcido⌺con un kernel de 3×3 para etiquetar las celdas adyacentes con el mismo número. El bucle principal aplica la función de relleno tantas veces como sea necesario hasta la convergencia, actualizando el contador de etiquetas y la cuadrícula etiquetada en cada iteración. Finalmente, el código divide la cuadrícula etiquetada entre el contador de etiquetas para obtener las etiquetas finales.Es importante tener en cuenta que esta implementación asume que la cuadrícula no tiene agujeros ni islas desconectadas dentro de la isla principal. Si este no es el caso, el algoritmo debe adaptarse para manejar múltiples islas.