Playground: Number of Islands

Curso de Algoritmos Avanzados: Grafos y Árboles

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,

Aportes 3

Preguntas 0

Ordenar por:

¿Quieres ver más aportes, preguntas y respuestas de la comunidad?

Miguel Ángel Reyes Moreno

hace 3 meses

Comparto mi solución en Python: ``` from typing import List class Solution: def numIslands(self, grid: List\[List\[str]]) -> int: islands\_counter = 0 def DFS(i, j): if grid\[i]\[j] == '0': return grid\[i]\[j] = '0' # go up if i -1 >= 0: DFS(i-1, j) # go down if i + 1 < len(grid): DFS(i+1, j) # go left if j - 1 >= 0: DFS(i, j-1) # go right if j + 1 < len(grid\[i]): DFS(i, j+1) if grid is None or not grid: return 0 for i in range(len(grid)): for j in range(len(grid\[i])): if grid\[i]\[j] == '1': DFS(i,j) islands\_counter += 1 return islands\_counter if \_\_name\_\_ == "\_\_main\_\_": solution = Solution() # Instantiate the Solution class \# Example 1 grid1 = \[ \["1","1","1","1","0"], \["1","1","0","1","0"], \["1","1","0","0","0"], \["0","0","0","0","0"] ] print("Number of islands in grid1: ", solution.numIslands(grid1)) \# Example 2 grid2 = \[ \["1","1","0","0","0"], \["1","1","0","0","0"], \["0","0","1","0","0"], \["0","0","0","1","1"] ] print("Number of islands in grid2: ", solution.numIslands(grid2)) \# Example 3 - Edge case (empty grid) grid3 = \[] print("Number of islands in grid3: ", solution.numIslands(grid3)) \# Example 4 - Edge case (all water) grid4 = \[ \["0","0","0","0"], \["0","0","0","0"] ] print("Number of islands in grid4: ", solution.numIslands(grid4)) ```

Daniel Barreto

hace 8 meses

```js def map_island(island_pos, mapa, searched): stack = [island_pos] while stack: current_pos = stack.pop() if(not current_pos in searched): searched.append(current_pos) adjeisent = [ [current_pos[0] + 1, current_pos[1]], [current_pos[0] - 1, current_pos[1]], [current_pos[0], current_pos[1] + 1], [current_pos[0], current_pos[1] - 1] ] for position in adjeisent: if(not position in searched and position[0] < len(mapa) and position[0] > -1 and position[1] < len(mapa[0]) and position[1] > -1 and mapa[position[0]][position[1]] == "1" ): stack.append(position) def numeroDeIslas(mapa): # Tu código aquí 👇 islands = 0 stack = [[0,0]] searched = [] for i in range(0, len(mapa)): for j in range(0, len(mapa[0])): current_pos = [i, j] if(mapa[current_pos[0]][current_pos[1]] == "1" and not current_pos in searched ): islands += 1 map_island(current_pos, mapa, searched) searched.append(current_pos) return islands ```Mi solución, sin usar recursión :)

Ivan Scaglioni

hace un año

Mi solución:


def numeroDeIslas(mapa):
   # Tu código aquí 👇
   filas = len(mapa)
   if filas > 0:
        columnas = len(mapa[0]) 

   """ Primera parte encontrar las cooedernas de todos los "1" en el mapa """
   coordenadas=[(1,1)]
   coordenadas.pop()
   index_x = 0
   for x in mapa:
      index_y =0
      for y in x:
         if y == "1":
            coordenadas.append((index_x, index_y))
         index_y += 1
      index_x += 1

   """ segunda parte encontrar la cantidad de islas en el mapa"""

   count_islands = 0



   for island in coordenadas:
      current_island = [island]
      x = island[0]
      y = island[1]
      if mapa[x][y] == "0":
         continue
      else:
         print(x,y)
         count_islands += 1
      for  here   in current_island:
         x  = here[0]
         y = here[1] 
         mapa[x][y] = "0"

         """up"""
         if  y+1 < columnas:
            if mapa[x][y+1] == "1":
               current_island.append((x,y+1))


         """rigth"""
         if x+1 < filas:
            if mapa[x+1][y] == "1":
               current_island.append((x+1,y))


         """down"""
         if y-1 >= 0:
            if mapa[x][y-1] == "1":
               current_island.append((x,y-1))


         """left"""
         if x-1 >= 0:
            if mapa[x-1][y] == "1":
               current_island.append((x-1,y))


   return count_islands