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?

You don't have access to this class

Keep learning! Join and start boosting your career

If you already have an account,

Contributions 4

Questions 0

Sort by:

Want to see more contributions, questions and answers from the community?

Andres Silva Vega

16 days ago

```python def numeroDeIslas(mapa): # Tu código aquí 👇 numero_islas = 0 for i, row in enumerate(mapa): for j, item in enumerate(row): if item == "1": numero_islas += dfs(i, j, mapa) return numero_islas def dfs(i, j, mapa) : mapa[i][j] = "2" if j+1 < len(mapa[i]) and mapa[i][j+1] == "1": dfs(i, j+1, mapa) if i+1 < len(mapa) and mapa[i+1][j] == "1": dfs(i+1, j, mapa) if j-1 >= 0 and mapa[i][j-1] == "1": dfs(i, j-1, mapa) if i-1 >= 0 and mapa[i-1][j] == "1": dfs(i-1, j, mapa) return 1 ```

Miguel Ángel Reyes Moreno

7 months ago

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

a year ago

```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

2 years ago

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