Ejercicios Prácticos de Búsqueda en Profundidad (DFS)

Curso de Algoritmos Avanzados: Grafos y Árboles

Contenido del curso

Introducción

DFS

BFS

Backtrack

Próximos pasos

Tomar examen

Ejercicios recomendados de DFS

Reemplazar un Color en una Sección de la Imagen Una imagen está representada por una cuadrícula de enteros m x n donde image[i][j] representa el valor de los píxeles de la imagen. También se le dan tres enteros sr, sc y color. Debe realizar un relleno en la imagen comenzando por el píxel image[sr][sc].

Para realizar un relleno, considere el píxel inicial, más cualquier píxel conectado en 4 direcciones al píxel inicial del mismo color que el píxel inicial, más cualquier píxel conectado en 4 direcciones a esos píxeles (también con el mismo color), y así sucesivamente. Reemplazar el color de todos los píxeles mencionados por el color.

Devuelve la imagen modificada después de realizar el relleno.

Ejemplo 1: Entrada: imagen = [[1,1,1],[1,1,0],[1,0,1]], sr = 1, sc = 1, color = 2 Salida: [[2,2,2],[2,2,0],[2,0,1]] Explicación: Desde el centro de la imagen con posición (sr, sc) = (1, 1) (es decir, el píxel rojo), todos los píxeles conectados por un camino del mismo color que el píxel inicial (es decir, los píxeles azules) se colorean con el nuevo color. Observe que la esquina inferior no se colorea con el color 2, porque no está conectada en 4 direcciones al píxel inicial.

Ejemplo 2: Entrada: imagen = [[0,0,0],[0,0,0]], sr = 0, sc = 0, color = 0 Salida: [[0,0,0],[0,0,0]] Explicación: El píxel inicial ya tiene el color 0, por lo que no se realizan cambios en la imagen.

Construir una cadena a partir de un árbol binario Dada la raíz de un árbol binario, construya una cadena formada por paréntesis y enteros a partir de un árbol binario con el modo de recorrido de preorden, y devuélvala. Omita todos los pares de paréntesis vacíos que no afecten a la relación de mapeo uno a uno entre la cadena y el árbol binario original.

Ejemplo 1 Entrada: raíz = [1,2,3,4] Salida: "1(2(4))(3)" Explicación: Originalmente, tiene que ser "1(2(4)())(3()())", pero hay que omitir todos los pares de paréntesis vacíos innecesarios. Y será "1(2(4))(3)"

Ejemplo 2: Entrada: raíz = [1,2,3,null,4] Salida: "1(2()(4))(3)" Explicación: Casi lo mismo que el primer ejemplo, excepto que no podemos omitir el primer par de paréntesis para romper la relación de mapeo uno a uno entre la entrada y la salida.

Batalla Naval - Contar Barcos Dado un tablero de m x n donde cada celda es un acorazado 'X' o un vacío '.', devuelva el número de los barcos en el tablero. Los barcos sólo pueden colocarse horizontal o verticalmente en el tablero. En otras palabras, sólo pueden tener la forma 1 x k (1 fila, k columnas) o k x 1 (k filas, 1 columna), donde k puede ser de cualquier tamaño. Al menos una celda horizontal o vertical separa dos barcos (es decir, no hay barcos adyacentes).

Ejemplo 1: Entrada: tablero = [["X",".",".", "X"],[".",".", "X"],[".",".", "X"] Salida: 2

Ejemplo 2: Entrada: tablero = [["."]] Salida: 0

Número de Islas Cerradas Dada una cuadrícula 2D formada por 0s (tierra) y 1s (agua). Una isla es un grupo máximo de 0s conectado en 4 direcciones y una isla cerrada es una isla totalmente (toda a la izquierda, arriba, derecha, abajo) rodeada de 1s. Devuelve el número de islas cerradas.

Ejemplo 1: Input: grid = [[1,1,1,1,1,1,1,0],[1,0,0,0,0,1,1,0],[1,0,1,0,1,1,1,0],[1,0,0,0,0,1,0,1],[1,1,1,1,1,1,1,0]] Salida: 2 Explicación: Las islas en gris están cerradas porque están completamente rodeadas de agua (grupo de 1s).

Ejercicios Prácticos de Búsqueda en Profundidad (DFS)

Todos los cursos GRATIS

Se acaba en:

02díasd:06hrsh:51minm:52segs

Nicolas Lopez

Estudiante

Hace un año

Mi solucion en Java para Reemplazar un Color en una Sección de la Imagen.

package practice;

/**
 * Una imagen está representada por una cuadrícula de enteros m x n donde image[i][j] representa el valor de los píxeles
 * de la imagen. También se le dan tres enteros sr, sc y color. Debe realizar un relleno en la imagen comenzando
 * por el píxel image[sr][sc].
 *
 * Para realizar un relleno, considere el píxel inicial, más cualquier píxel conectado en 4 direcciones al píxel inicial
 * del mismo color que el píxel inicial, más cualquier píxel conectado en 4 direcciones a esos píxeles
 * (también con el mismo color), y así sucesivamente. Reemplazar el color de todos los píxeles mencionados por el color.
 *
 * Devuelve la imagen modificada después de realizar el relleno.
 *
 * Ejemplo 1: Entrada: imagen = [[1,1,1],[1,1,0],[1,0,1]], sr = 1, sc = 1, color = 2 Salida: [[2,2,2],[2,2,0],[2,0,1]]
 * Explicación: Desde el centro de la imagen con posición (sr, sc) = (1, 1) (es decir, el píxel rojo),
 * todos los píxeles conectados por un camino del mismo color que el píxel inicial (es decir, los píxeles azules)
 * se colorean con el nuevo color. Observe que la esquina inferior no se colorea con el color 2,
 * porque no está conectada en 4 direcciones al píxel inicial.
 *
 * Ejemplo 2: Entrada: imagen = [[0,0,0],[0,0,0]], sr = 0, sc = 0, color = 0 Salida: [[0,0,0],[0,0,0]]
 * Explicación: El píxel inicial ya tiene el color 0, por lo que no se realizan cambios en la imagen.
 */


public class ReplaceColorInASectionImage {

    public static void main(String[] args) {
        int [][] image = {{1,1,1}, {1,1,0}, {1,0,1}};
        //int [][] image = {{0,0,0}, {0,0,0}, {0,0,0}};
        int sr = 1;
        int sc = 1;
        int color = 2;

        replaceColorInASectionImage(image, sr, sc, color);
        displayImage(image);
    }

    public static void replaceColorInASectionImage(int[][] image, int sr, int sc, int color) {
        int imageTotalRows = image.length;
        int imageTotalColumns = image[0].length;

        if (sr >= imageTotalRows || sc >= imageTotalColumns || sr < 0 || sc < 0 || image[sr][sc] == color) {
            return;
        }

        if (image[sr][sc] != 0){
            image[sr][sc] = color;
            replaceColorInASectionImage(image, sr + 1, sc, color);
            replaceColorInASectionImage(image, sr - 1, sc, color);
            replaceColorInASectionImage(image, sr, sc + 1, color);
            replaceColorInASectionImage(image, sr, sc - 1, color);
        }
    }

    public static void displayImage(int[][] image) {
        for(int row = 0; row < image.length; row++){
            System.out.println('\n');
            for(int col = 0; col < image[row].length; col++){
                System.out.print(image[row][col] + " ");
            }
        }
    }
}

Ejercicios Prácticos de Búsqueda en Profundidad (DFS)

Introducción

Qué son los grafos y cómo modelan el mundo

Qué es un árbol en estructuras de datos

Qué es la recursión en programación

Grafos en el mundo real que ya conoces

Representación de Grafos: Matriz y Lista de Adyacencia

DFS

Cómo recorre nodos el algoritmo DFS

Implementación de DFS recursivo para búsqueda en árboles

Búsqueda en Profundidad (DFS) para Grafos: Enfoque Iterativo y Recursivo

Inorder, Preorder y Postorder en árboles

Suma de caminos raíz a hoja en árboles

Suma de caminos raíz a hoja con DFS

Playground: Sum Root to Leaf Numbers

Implementación de Algoritmo DFS en Árboles Binarios con Golang

Número de islas con DFS en matrices

Problema de islas resuelto con DFS

Playground: Number of Islands

Número de islas con DFS recursivo en Python

Ejercicios Prácticos de Búsqueda en Profundidad (DFS)

Algoritmos de Búsqueda en Profundidad (DFS) en Problemas Comunes

BFS

Cómo BFS recorre grafos por niveles

Implementación de BFS con colas en Python

Mínimos movimientos del caballo en ajedrez

Minimum Knight's Move con BFS

Playground: Minimum Knights Moves

Resolución de Problemas de Caballos de Ajedrez con BFS en Python

Propagación BFS en Rotting Oranges

Resolución de Rotting Oranges usando BFS

Playground: Rotting Oranges

Implementación de BFS para naranjas podridas

Puente más corto entre islas con BFS

Shortest Bridge: combina DFS y BFS

Playground: Shortest Bridge Between Islands

Shortest Bridge con DFS y BFS en Python

Búsqueda en anchura: Ejercicios prácticos y aplicaciones

Ejercicios avanzados de búsqueda en anchura (BFS) en programación

Backtrack

Backtracking para encontrar soluciones válidas

Combinaciones de letras en teclado telefónico

Combinaciones de teclado con backtracking

Generación de combinaciones de letras con teclados numéricos en C++

Playground: Letter Combinations of a Phone Number

Generación de Direcciones IP Válidas a partir de Cadenas Numéricas

Backtracking para generar IPs válidas

Playground: Restore IP Addresses

Búsqueda de Palabras en Matrices: Solución y Complejidad

Word Search con DFS y backtracking

Playgrund: Word Search

Búsqueda de palabras en matrices con DFS

Resolución del problema de las n reinas en ajedrez

Ejercicios de Backtracking: Combinaciones y Permutaciones

Combinaciones y Permutaciones con Backtracking

Próximos pasos

Dijkstra y topological sort en grafos

Qué sigue después de aprender grafos

Todos los cursos GRATIS