Clase 18 de 52 • Curso de Algoritmos Avanzados: Grafos y Árboles
Contenido del curso
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).
Platzi Team
Nicolas Lopez
Nicolas Lopez
Carlos Raúl Romero Martínez
Santiago García Rincón
class FloodFillService def initialize(image, sr, sc, new_color) @image = image @sr = sr @sc = sc @new_color = new_color @original_color = image[sr][sc] @rows = image.length @cols = image[0].length end def call return @image if @original_color == @new_color dfs(@sr, @sc) @image end # 🎨 Conversión a pixel Unicode def pixel(val) case val.to_i when 0 then "🟦" when 1 then "⬜" when 2 then "🟥" else "⬛" end end # 🖼 Mostrar imagen pixelada def print_image puts "\nImagen pixelada:\n\n" @image.each do |row| puts row.map { |v| pixel(v) }.join end puts "\n" end private def dfs(i, j) return if i < 0 || i >= @rows || j < 0 || j >= @cols return unless @image[i][j] == @original_color @image[i][j] = @new_color dfs(i + 1, j) dfs(i - 1, j) dfs(i, j + 1) dfs(i, j - 1) end end
Mi solucion para Batalla Naval en Java:
package practice; /** * 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 */ public class NavyBattleFindBoats { public static void main(String[] args) { char [][] sea = {{'X','.','X'}, {'.','.','X'}, {'.','.','X'}}; int boatCounter = 0; displaySea(sea); for (int row = 0; row < sea.length; row++) { for (int col = 0; col < sea[row].length; col++) { if(sea[row][col] == 'X'){ boatCounter++; findBoats(sea, row, col); } } } System.out.println(" "); System.out.println("Boats found in "+boatCounter+" boats"); } public static void findBoats(char [][] sea, int row, int col){ int seaTotalRows = sea.length; int seaTotalCols = sea[0].length; //return for the base case that row or col are out of bounded. if (row < 0 || col < 0 || row >= seaTotalRows || col >= seaTotalCols || sea[row][col] == '.') { return; } //Change the value on the sea[row][col] to '.' to don't re-count the boat. sea[row][col] = '.'; //Explore with findBoats with recursion all sides to find the boat. findBoats(sea, row + 1, col); findBoats(sea, row - 1, col); findBoats(sea, row, col + 1); findBoats(sea, row, col - 1); } public static void displaySea(char[][] 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] + " "); } } } }
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] + " "); } } } }
Pasen los links de leetcode para probar las soluciones que hagamos
Si, deberían de mejor pasar los links JAJAJAJA
