Resolver el problema shortest bridge en Python combina dos algoritmos clásicos: DFS para identificar la primera isla y BFS para construir el puente más corto hacia la segunda. Aquí verás cómo implementar esa solución paso a paso, reutilizando código del problema number of islands y entendiendo por qué cada estructura de datos importa.

¿Qué hace la función shortest bridge y qué retorna?

La función recibe un mapa con dos islas y devuelve un entero que representa la mínima cantidad de casillas necesarias para conectarlas. Si no existe camino posible, retorna -1.

El punto de partida es el código de number of islands, pero con cambios clave: ya no contamos islas, sino que medimos la distancia mínima entre dos masas de tierra separadas por agua [00:24].

¿Por qué usar DFS y BFS juntos? DFS recorre y marca toda la primera isla en una sola pasada. BFS expande la búsqueda por niveles desde esa isla hasta tocar la segunda, garantizando que el primer contacto sea el camino más corto.

¿Cómo identificar la primera isla con DFS?

La idea es iterar el mapa con dos ciclos anidados hasta encontrar una celda con valor 1. Cuando aparece, se ejecuta DFS para recorrer toda esa isla y marcar sus celdas, evitando confundirlas con la segunda [02:00].

Para controlar el flujo se usa una bandera booleana llamada encontre_isla, inicializada en False. Cuando DFS termina de marcar la primera isla, la bandera pasa a True y los ciclos se rompen con break. No tiene sentido seguir buscando si ya tienes el punto de partida.

¿Qué hace la técnica de las migajitas?

Durante el recorrido, cada celda visitada cambia su valor de 1 a 2. Esa marca funciona como una migaja que evita volver a pasar por la misma posición y previene ciclos infinitos. Es el mismo truco que se usa en number of islands.

¿Cómo construir el puente con BFS por niveles?

Desde las celdas de la primera isla se inicia un BFS que expande capas concéntricas hacia afuera. Cada capa representa un paso adicional en la construcción del puente, y la variable cantidad_de_material cuenta cuántos pasos llevas [04:30].

Los componentes esenciales son:

• Una cola que guarda las posiciones a explorar como pares (x, y).
• Una lista cola_nivel_actual que acumula las celdas del siguiente nivel.
• Una lista de direcciones con los pares (0,1), (0,-1), (1,0), (-1,0) para moverse a las cuatro adyacentes.
• La operación cola.pop(0) para extraer el primer elemento, respetando el orden FIFO de una cola en Python.

En cada iteración tomas una casilla, calculas nueva_x y nueva_y sumando la dirección y evalúas tres escenarios.

¿Qué condiciones evaluar en cada celda nueva?

Primero, si la celda está fuera del mapa o ya tiene una migajita (valor 2), la ignoras y continúas. Segundo, si el valor en esa posición es 1, encontraste la segunda isla y retornas cantidad_de_material inmediatamente [07:45].

Tercero, si es agua sin visitar, la agregas a cola_nivel_actual con append((nueva_x, nueva_y)) y marcas su valor como 2 para no repetirla.

¿Cuándo se incrementa la cantidad de material? Cada vez que la cola principal se vacía y se reemplaza por cola_nivel_actual, sumas uno. Eso significa que terminaste de explorar un nivel completo y avanzas al siguiente anillo del puente.

¿Cómo manejar el avance entre niveles del BFS?

Cuando el while interno termina porque la cola quedó vacía, asignas cola = cola_nivel_actual y reinicias cola_nivel_actual como lista vacía. Ese intercambio es lo que permite contar pasos de forma precisa: un nivel equivale a una unidad de material en el puente.

Si en algún momento la cola queda vacía sin haber tocado la segunda isla, sales del ciclo y retornas -1. En la práctica, el problema garantiza que existen exactamente dos islas, así que ese caso es el peor escenario teórico.

¿Por qué guardar pares (x, y) en la cola?

Cada elemento de la cola es una tupla con dos valores: la coordenada de fila y la de columna. Al hacer pop(0) recuperas la pareja completa, accedes a casilla_actual[0] para x y a casilla_actual[1] para y, y desde ahí calculas las cuatro adyacentes [06:20].

Esta estructura es lo que hace que BFS funcione sobre matrices: tratas cada celda como un nodo y cada movimiento válido como una arista hacia un vecino.

La solución completa combina la lógica de number of islands con una expansión por niveles que mide distancias mínimas. ¿Qué lenguaje elegirías tú para implementarla y qué complejidad calculaste? Cuéntalo en los comentarios.