Introducción
Grafos y Árboles: Estructuras de Datos Avanzadas
Estructuras de Datos: Introducción a Árboles y Sus Propiedades
Recursión: Concepto y Aplicaciones Prácticas con Ejemplos
Aplicaciones Prácticas de Grafos en Tecnología e Industria
Representación de Grafos: Matriz y Lista de Adyacencia
DFS
Búsqueda en Profundidad (DFS) en Árboles y Grafos
Implementación de DFS recursivo para búsqueda en árboles
Búsqueda en Profundidad (DFS) para Grafos: Enfoque Iterativo y Recursivo
Recorridos y Profundidad en Árboles Binarios y Enearios
Suma de Caminos en Árboles Binarios
Suma de Números de Raíz a Hoja en Árboles
Playground: Sum Root to Leaf Numbers
Implementación de Algoritmo DFS en Árboles Binarios con Golang
Resolución del Problema de Número de Islas con DFS
Conteo de Islas en Matrices con DFS
Playground: Number of Islands
Implementación de "Número de Islas" con Recursión en Python
Ejercicios Prácticos de Búsqueda en Profundidad (DFS)
Algoritmos de Búsqueda en Profundidad (DFS) en Problemas Comunes
BFS
Algoritmo BFS: Recorrido en Anchura de Grafos y Árboles
Implementación de BFS en Árboles usando Python
Movimiento mínimo de caballo en ajedrez infinito
Resolviendo el Problema Mínimo de Movimiento del Caballo en Ajedrez
Playground: Minimum Knights Moves
Resolución de Problemas de Caballos de Ajedrez con BFS en Python
Propagación de Plagas en Cultivos: Cálculo de Días para Contagio Total
Resolución de Rotting Oranges usando BFS
Playground: Rotting Oranges
Propagación de Plagas en Matrices usando BFS en Java
Construcción de Puentes Cortos entre Islas en Matrices Binarias
Resolución del Problema Shortest Bridge con DFS y BFS
Playground: Shortest Bridge Between Islands
Búsqueda del camino más corto entre islas usando BFS en Python
Búsqueda en anchura: Ejercicios prácticos y aplicaciones
Ejercicios avanzados de búsqueda en anchura (BFS) en programación
Backtrack
Algoritmo Backtracking: Solución de Problemas Complejos
Combinaciones de Letras en Números Telefónicos
Combinaciones de Letras a partir de un Número de Teléfono
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
Generación de IPs válidas con backtracking en C++
Playground: Restore IP Addresses
Búsqueda de Palabras en Matrices: Solución y Complejidad
Búsqueda de Palabras en Matrices usando Backtracking y DFS
Playgrund: Word Search
Implementación de búsqueda de palabras en matrices con DFS en JavaScript
Resolución del problema de las n reinas en ajedrez
Ejercicios de Backtracking: Combinaciones y Permutaciones
Combinaciones y Permutaciones con Backtracking
Próximos pasos
Algoritmos de Grafos: MIN/MAX-HIP, TRI, Topological Sort y Dijkstra
Algoritmos y Estructuras de Datos en la Ingeniería
No tienes acceso a esta clase
¡Continúa aprendiendo! Únete y comienza a potenciar tu carrera
Para quienes buscan adentrarse en el mundo de algoritmos y estructuras de datos, Python ofrece una plataforma versátil para implementar soluciones efectivas. En este caso, vamos a desglosar un método para contar el número de islas en un mapa, usando la técnica de recursión y el lenguaje Python. Este ejercicio te permitirá fortalecer tus habilidades de programación, comprender mejor la recursión y aplicar algoritmos de búsqueda profunda (DFS).
El primer paso crucial es entender la estructura del problema: un mapa representado por una matriz en la que '1' indica tierra y '0' agua. La meta es identificar grupos conectados de '1' que formen islas. Comenzamos con la implementación de la función inicial que recorre el mapa.
def numero_de_islas(mapa):
cantidad_de_islas = 0
cantidad_de_islas
se establece en cero antes de revisitar el mapa, ya que al final se desea retornar esta cuenta.(i, j)
para determinar si el elemento es tierra o agua.Para detectar una isla, verificamos si la posición actual en la matriz contiene un '1', lo que indica tierra. Si es así, se descubre una nueva isla, pero debemos procurar no contar las mismas secciones de tierra más de una vez.
for i in range(len(mapa)):
for j in range(len(mapa[0])):
if mapa[i][j] == 1:
cantidad_de_islas += 1 # Nueva isla encontrada
dfs(mapa, i, j) # Llamado a DFS para explorar la isla entera
DFS nos permite explorar cada parte de la isla (cada '1' conectado) marcando el recorrido para evitar contar la misma isla repetidas veces. Utilizaremos una función recursiva adicional para esta tarea.
def dfs(mapa, i, j):
# Retorna si estamos fuera de los límites o si no es tierra
if i < 0 or j < 0 or i >= len(mapa) or j >= len(mapa[0]) or mapa[i][j] != 1:
return
mapa[i][j] = 2 # Marca como visitada la posición actual
# Explora las direcciones vecinas
dfs(mapa, i - 1, j) # Arriba
dfs(mapa, i + 1, j) # Abajo
dfs(mapa, i, j - 1) # Izquierda
dfs(mapa, i, j + 1) # Derecha
Este algoritmo recorre el mapa una sola vez, garantizando una eficiencia de O(n*m), donde n es el número de filas y m el número de columnas en el mapa.
La recursión, si bien elegante, puede no ser siempre la solución más eficiente en recursos, especialmente en escenarios donde el mapa es extenso y el stack de llamadas es profundo. Invitaría a los estudiantes a implementar la solución iterativa también, ayudándoles a cimentar el conocimiento desde diferentes perspectivas.
En conclusión, este ejercicio práctico no solo refuerza conceptos de programación, sino que también invita a la improvisación y experimentación para optimizar y encontrar soluciones novedosas a un problema clásico en el campo de la informática. ¡Anímate a ponerlo en práctica y sigue avanzando en el fascinante mundo de la tecnología!
Aportes 8
Preguntas 0
En Java
class Solution {
static int islandNumbers;
public int numIslands(char[][] grid) {
islandNumbers = 0;
for(int i = 0; i < grid.length; i++){
for(int j = 0; j < grid[0].length ; j++){
if(grid[i][j] == '1'){
dfs(i,j, grid);
islandNumbers++;
}
}
}
return islandNumbers;
}
public void dfs(int i, int j, char[][] grid){
if(i>=0 && i<grid.length && j>=0 && j<grid[0].length && grid[i][j] == '1'){
grid[i][j] = '2';
dfs(i, j+1, grid);
dfs(i, j-1, grid);
dfs(i+1, j, grid);
dfs(i-1, j, grid);
}
}
}
Esta es mi solución en Kotlin:
fun main() {
val map = listOf(
mutableListOf(1, 1, 0, 0, 0, 0, 1, 0),
mutableListOf(1, 0, 0, 1, 1, 0, 0, 0),
mutableListOf(0, 0, 0, 1, 1, 0, 0, 1),
mutableListOf(0, 0, 0, 0, 0, 1, 1, 1),
)
val count = countIslands(map);
println("The number of Island in the map is: $count")
}
fun countIslands(map: List<MutableList<Int>>): Int {
var count = 0
for (i in map.indices) {
for (j in map[i].indices) {
if (map[i][j] == 1) {
inspectIsland(map, i, j)
count++
}
}
}
return count
}
Jeje si leí el cuento de Hansel y Gretel.
¿Quieres ver más aportes, preguntas y respuestas de la comunidad?