Categoría: BFS

Dado un número inicial x y dos operaciones que se dan a continuación:  Multiplica el número por 2. Resta 1 del número. La tarea es averiguar el número mínimo de operaciones requeridas para convertir el número x en y usando solo las dos operaciones anteriores. Podemos aplicar estas operaciones cualquier número de veces. Restricciones:  1 … Continue reading «Número mínimo de operaciones requeridas para convertir el número x en y»

Dada una array booleana 2D, encuentre el número de islas. Un grupo de unos conectados forma una isla. Por ejemplo, la siguiente array contiene 5 islas Ejemplo:   Input : mat[][] = {{1, 1, 0, 0, 0}, {0, 1, 0, 0, 1}, {1, 0, 0, 1, 1}, {0, 0, 0, 0, 0}, {1, 0, 1, 0, … Continue reading «Islas en un gráfico usando BFS»

Dado un diccionario y dos palabras ‘inicio’ y ‘objetivo’ (ambas de la misma longitud). Encuentre la longitud de la string más pequeña desde ‘inicio’ hasta ‘objetivo’ si existe, de modo que las palabras adyacentes en la string solo difieran en un carácter y cada palabra en la string sea una palabra válida, es decir, existe … Continue reading «Escalera de palabras (longitud de la string más corta para llegar a una palabra objetivo) – Part 1»

Recorrido de búsqueda primero en amplitud de un gráfico utilizando el algoritmo proporcionado en el libro CLRS . BFS es una de las formas de recorrer un gráfico. Se llama así porque expande la frontera entre los vértices descubiertos y no descubiertos uniformemente a lo largo de la frontera. Lo que significa es que el … Continue reading «BFS usando vectores y cola según el algoritmo de CLRS»