Introducción

1

¿Qué es un grafo?

2

¿Qué es un árbol?

3

¿Qué es recursión?

4

Aplicaciones reales de grafos y árboles

5

Formas de representar un grafo

DFS

6

Análisis de DFS: algoritmo de búsqueda en profundidad

7

Programando DFS de forma recursiva

8

Otras formas de programar DFS

9

Recorridos y profundidad de un Árbol

10

Sum Root to Leaf Numbers: análisis del problema

11

Solución de Sum Root to Leaf Numbers

12

Playground: Sum Root to Leaf Numbers

13

Programando Sum Root to Leaf Numbers en Golang

14

Number of Islands: análisis del problema

15

Solución de Number of Islands

16

Playground: Number of Islands

17

Programando Number of Islands en Python

18

Ejercicios recomendados de DFS

19

Ejercicios resueltos de DFS

BFS

20

Análisis de BFS: algoritmo de búsqueda en anchura

21

Programando BFS con Python

22

Minimum Knights Moves (movimientos de caballo en ajedrez): análisis del problema

23

Solución de Minimum Knights Moves

24

Playground: Minimum Knights Moves

25

Programando Minimum Knights Moves con Python

26

Rotting Oranges: análisis del problema

27

Solución de Rotting Oranges

28

Playground: Rotting Oranges

29

Rotting Oranges con Java

30

Shortest Bridge Between Islands: análisis del problema

31

Solución de Shortest Bridge Between Islands

32

Playground: Shortest Bridge Between Islands

33

Programando Shortest Bridge Between Islands con Python

34

Ejercicios recomendados de BFS

35

Ejercicios resueltos de BFS

Backtrack

36

Algoritmo de Backtrack

37

Letter Combinations of a Phone Number: análisis del problema

38

Solución de Letter Combinations of a Phone Number

39

Programando Letter Combinations of a Phone Number con C++

40

Playground: Letter Combinations of a Phone Number

41

Restore IP Addresses: análisis del problema

42

Programando Restore IP Addresses con C++

43

Playground: Restore IP Addresses

44

Word Search: análisis del problema

45

Solución de Word Search

46

Playgrund: Word Search

47

Programando Word Search JavaScript

48

Reto: N Queens Puzzle

49

Ejercicios recomendados de Backtrack

50

Ejercicios resueltos de Backtrack

Próximos pasos

51

¿Qué otros algoritmos y tipos de grafos puedes aprender?

52

¿Quieres más cursos avanzados de algoritmos?

No tienes acceso a esta clase

¡Continúa aprendiendo! Únete y comienza a potenciar tu carrera

Playground: Shortest Bridge Between Islands

32/52

Aportes 2

Preguntas 0

Ordenar por:

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

Mi solución: ```python import math def check_spot(islands, i, j): for index, islands_spots in islands.items(): if (i - 1, j) in islands_spots or (i, j-1) in islands_spots or (i + 1, j) in islands_spots or (i, j + 1) in islands_spots: return index return -1 def get_islands(input_map): islands = {} for i, row in enumerate(input_map): for j, column in enumerate(row): if column == "0": continue else: # Check contiguous spots found_index = check_spot(islands, i, j) # Clock-wise order starting from left if found_index == -1: next_index = len(islands.items()) islands[next_index] = [(i, j)] else: islands[found_index].append((i, j)) return islands def generate_next_steps(islands, i, j, destination): next_steps = [] if (i - 1) >= 0 and islands[i-1][j] == "0" or (i-1,j) == destination: next_steps.append((i-1, j)) if (j + 1) < len(islands[i]) and islands[i][j+1] == "0" or (i,j+1) == destination: next_steps.append((i, j+1)) if (i + 1) < len(islands) and islands[i+1][j] == "0" or (i+1,j) == destination: next_steps.append((i+1, j)) if (j - 1) >= 0 and islands[i][j-1] == "0" or (i,j-1) == destination: next_steps.append((i, j-1)) return next_steps def get_shortest_bridge_between_islands(input_map): islands = get_islands(input_map) shortest_path_data = { "spot_1" : None, "spot_2" : None, "distance": 1000000 } for i1, j1 in islands[0]: for i2, j2 in islands[1]: spots_distance = math.dist([i1, j1], [i2, j2]) if spots_distance < shortest_path_data["distance"]: shortest_path_data['spot_1'] = (i1, j1) shortest_path_data['spot_2'] = (i2, j2) shortest_path_data['distance'] = spots_distance origin, destination = shortest_path_data["spot_1"], shortest_path_data["spot_2"] print(origin, destination) bridge_amount = -1 steps = [origin] while steps: if destination in steps: break for _ in range(len(steps)): current_step = steps.pop(0) i, j = current_step next_steps = generate_next_steps(input_map, i, j, destination) for next_step in next_steps: if not next_step in steps: steps.append(next_step) bridge_amount += 1 print(steps) return bridge_amount input_map = [ ["1","1","1","1","1"], ["1","0","0","0","1"], ["1","0","1","0","1"], ["1","0","0","0","1"], ["1","1","1","1","1"], ] response = get_shortest_bridge_between_islands(input_map) print(response) ```
comparto una solución con algunos comentarios: ```python from typing import List from collections import deque class Solution: def shortestBridge(self, grid: List\[List\[int]]) -> int: \# Step 1: Find the first island and mark it, adding boundary cells to the queue found = False queue = deque() # Boundary of the first island for expansion for i in range(len(grid)): for j in range(len(grid\[i])): if grid\[i]\[j] == 1: self.mark\_first\_island(grid, i, j, queue) # Mark first island and add boundaries to queue found = True break if found: break \# Step 2: Expand BFS from the first island to reach the second island return self.expand(grid, queue) def mark\_first\_island(self, grid: List\[List\[int]], x: int, y: int, queue: deque): directions = \[(1, 0), (-1, 0), (0, 1), (0, -1)] grid\[x]\[y] = 2 # Mark the island as visited queue\_for\_marking = deque(\[(x, y)]) while queue\_for\_marking: x, y = queue\_for\_marking.popleft() for direction in directions: new\_x, new\_y = x + direction\[0], y + direction\[1] if 0 <= new\_x < len(grid) and 0 <= new\_y < len(grid\[0]): if grid\[new\_x]\[new\_y] == 1: grid\[new\_x]\[new\_y] = 2 # Mark connected land queue\_for\_marking.append((new\_x, new\_y)) elif grid\[new\_x]\[new\_y] == 0: \# Add boundary water cells to queue for BFS expansion queue.append((x, y)) def expand(self, grid: List\[List\[int]], queue: deque) -> int: directions = \[(1, 0), (-1, 0), (0, 1), (0, -1)] steps = 0 \# Start BFS to expand towards the second island while queue: for \_ in range(len(queue)): x, y = queue.popleft() for direction in directions: new\_x, new\_y = x + direction\[0], y + direction\[1] if 0 <= new\_x < len(grid) and 0 <= new\_y < len(grid\[0]): if grid\[new\_x]\[new\_y] == 1: # Found the second island return steps if grid\[new\_x]\[new\_y] == 0: # Expand to water, turn it into land grid\[new\_x]\[new\_y] = 2 queue.append((new\_x, new\_y)) steps += 1 # Increase the step count as we expand one layer outwards return -1 # Should never reach here if there are two islands ```
undefined