Clase 16 de 52 • Curso de Algoritmos Avanzados: Grafos y Árboles
Contenido del curso
Platzi Team
John Eduard Meneses González
Hans Uriel Diaz Aguilar
Andres Silva Vega
Miguel Angel Reyes Moreno
Daniel Barreto
Ivan Scaglioni
def numeroDeIslas(mapa): if not mapa: return 0 filas = len(mapa) columnas = len(mapa[0]) visitado = [[False] * columnas for _ in range(filas)] # 4 direcciones → estándar del problema direcciones = [ (1, 0), # abajo (-1, 0), # arriba (0, 1), # derecha (0, -1), # izquierda ] def dfs(i, j): # fuera de rango if i < 0 or i >= filas or j < 0 or j >= columnas: return # agua o ya visitado if mapa[i][j] == "0" or visitado[i][j]: return visitado[i][j] = True for dx, dy in direcciones: dfs(i + dx, j + dy) # contador de islas numero_islas = 0 for i in range(filas): for j in range(columnas): if mapa[i][j] == "1" and not visitado[i][j]: dfs(i, j) numero_islas += 1 return numero_islas mapa = [ ["1","1","0","0","0"], ["1","1","0","0","0"], ["0","0","1","0","0"], ["0","0","0","1","1"], ] response = numeroDeIslas(mapa) print(response) mapa = [ ["1","1","0","0","1"], ["1","1","1","0","1"], ["0","0","1","0","1"], ["0","0","0","0","1"], ["0","0","0","0","1"], ] response = numeroDeIslas(mapa) print(response)
My solution!!
def numeroDeIslas(m): visited = set() def dfs(r: int,c: int): if r < 0 or r >= len(m) or c < 0 or c >= len(m[0]): return 0 # Nos protegemos de los bordes if (r,c) in visited or m[r][c] == "0": return 0 # Evitamos la repetición visited.add((r,c)) dfs(r + 1, c) # Derecha dfs(r - 1, c) # Izquierda dfs(r, c - 1) # Arriba dfs(r, c + 1) # Abajo return 1 # Ya revisamos los 4 lados total_islas = 0 for r in range(len(m)): for c in range(len(m[0])): total_islas += dfs(r, c) return total_islas
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
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))
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 :)
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
