Este es probelma con el que se eseña bfs, en la uva hay un problema para ponerlo en practica 11094 - Continents
Introducción
¿Qué es un grafo?
¿Qué es un árbol?
¿Qué es recursión?
Aplicaciones reales de grafos y árboles
Formas de representar un grafo
DFS
Análisis de DFS: algoritmo de búsqueda en profundidad
Programando DFS de forma recursiva
Otras formas de programar DFS
Recorridos y profundidad de un Árbol
Sum Root to Leaf Numbers: análisis del problema
Solución de Sum Root to Leaf Numbers
Playground: Sum Root to Leaf Numbers
Programando Sum Root to Leaf Numbers en Golang
Number of Islands: análisis del problema
Solución de Number of Islands
Playground: Number of Islands
Programando Number of Islands en Python
Ejercicios recomendados de DFS
Ejercicios resueltos de DFS
BFS
Análisis de BFS: algoritmo de búsqueda en anchura
Programando BFS con Python
Minimum Knights Moves (movimientos de caballo en ajedrez): análisis del problema
Solución de Minimum Knights Moves
Playground: Minimum Knights Moves
Programando Minimum Knights Moves con Python
Rotting Oranges: análisis del problema
Solución de Rotting Oranges
Playground: Rotting Oranges
Rotting Oranges con Java
Shortest Bridge Between Islands: análisis del problema
Solución de Shortest Bridge Between Islands
Playground: Shortest Bridge Between Islands
Programando Shortest Bridge Between Islands con Python
Ejercicios recomendados de BFS
Ejercicios resueltos de BFS
Backtrack
Algoritmo de Backtrack
Letter Combinations of a Phone Number: análisis del problema
Solución de Letter Combinations of a Phone Number
Programando Letter Combinations of a Phone Number con C++
Playground: Letter Combinations of a Phone Number
Restore IP Addresses: análisis del problema
Programando Restore IP Addresses con C++
Playground: Restore IP Addresses
Word Search: análisis del problema
Solución de Word Search
Playgrund: Word Search
Programando Word Search JavaScript
Reto: N Queens Puzzle
Ejercicios recomendados de Backtrack
Ejercicios resueltos de Backtrack
Próximos pasos
¿Qué otros algoritmos y tipos de grafos puedes aprender?
¿Quieres más cursos avanzados de algoritmos?
No tienes acceso a esta clase
¡Continúa aprendiendo! Únete y comienza a potenciar tu carrera
Si ya tienes una cuenta,
Iniciar sesión
Number of Islands: análisis del problema
14/52Recursos
Aportes 3
Preguntas 0
Ordenar por:
Mi solución
def scan_for_near_islands(row, column, matrix, checked_stack):
for pos in [(row-1, column),(row,column+1),(row+1, column),(row, column-1)]:
if pos not in checked_stack:
checked_stack.append(pos)
try:
if matrix[pos[0]][pos[1]] == 1:
scan_for_near_islands(pos[0], pos[1], matrix, checked_stack)
except IndexError:
pass
def find_islands_in_matrix(matrix, checked_stack = []):
total_island_sum = 0
for row, column in zip(range(len(matrix)),range(len(matrix[0]))):
if (row, column) not in checked_stack:
checked_stack.append((row, column))
if matrix[row][column] == 1:
scan_for_near_islands(row, column, matrix, checked_stack)
total_island_sum += 1
return total_island_sum
Hola 😄, podría empezar a hacer una búsqueda recursiva de la siguiente manera:
.
.
Entrar en una casilla, lo primero que hago es marcar la casilla con un # y luego buscar en las 4 direcciones recursivamente.
.
Si la casilla es 0 o # significa que hay agua o ya he pasado por ahí. Si es 1 sigo buscando.
.
Cuando encuentre que las cuatro direcciones son 0 significa que hay una isla, entonces aumento mi contador de islas, que por comodidad lo tendría global.
.
.
Al final mi matriz quedaría de la siguiente manera:
.
.
Significaría que ya he terminado de buscar islas.
¿Quieres ver más aportes, preguntas y respuestas de la comunidad?
o inicia sesión.