Imagina que tienes un mapa con dos islas y necesitas construir un puente entre ellas usando la menor cantidad de material posible. Ese es el reto del problema Shortest bridge between islands, una variación clásica de algoritmos sobre matrices binarias que pone a prueba tu capacidad de combinar búsqueda en grafos con razonamiento geométrico.

¿En qué consiste el problema del puente más corto entre islas?

El planteamiento parte de una matriz binaria, igual que en el ejercicio de número de islas. Aquí los unos representan tierra y los ceros representan agua. La diferencia es que ya no debes contar cuántas islas hay: el enunciado garantiza que existen exactamente dos.

Tu tarea es construir un puente entre ambas usando la mínima cantidad de celdas posibles. Cada celda de agua que conviertas en puente cuenta como una unidad de material, y debes encontrar la ruta más corta entre los puntos donde las dos islas están más cerca.

¿Qué es una isla en una matriz binaria? Es un grupo de celdas adyacentes con valor uno, conectadas horizontal o verticalmente, y rodeada de agua por todos sus lados. Las diagonales no cuentan como adyacencia.

¿Por qué importa encontrar la mínima distancia entre dos islas?

La clave está en que una isla puede tener cualquier forma: un anillo, una L, un bloque irregular. Eso significa que no basta con medir desde el centro o desde una esquina arbitraria. Tienes que recorrer los bordes de ambas islas y detectar los puntos donde se acercan más entre sí.

Mira este caso particular del [01:30]: una isla con forma de anillo rodea por dentro a otra isla pequeña. Como el anillo encierra a la segunda isla, la distancia es la misma en cualquier dirección que mires. La respuesta correcta es uno, porque basta una sola celda de agua para unirlas.

Pero cuando las formas son irregulares, el puente óptimo solo aparece en ciertos puntos específicos. Y ahí es donde el problema se vuelve interesante.

¿Cómo se mide el material del puente? Cuenta cuántas celdas de agua necesitas atravesar para llegar de una isla a la otra siguiendo el camino más corto. Cada celda equivale a una unidad de material.

¿Cómo reutilizar el código de número de islas para este reto?

Aquí viene lo interesante: gran parte del trabajo ya lo tienes resuelto. El algoritmo que usaste para identificar islas con DFS o BFS sirve como punto de partida para aislar la primera isla y marcar todas sus celdas.

Una estrategia común sigue estos pasos:

1. Recorre la matriz hasta encontrar la primera celda con valor uno.
2. Aplica DFS o BFS para marcar todas las celdas de esa primera isla con un identificador distinto, por ejemplo un dos.
3. Desde los bordes de esa isla marcada, lanza un BFS por niveles que avance celda por celda sobre el agua.
4. Cuenta cuántos niveles de expansión necesitas hasta tocar la segunda isla. Ese número es tu respuesta.

La idea de fondo es que el BFS por niveles garantiza siempre encontrar la distancia mínima en un grafo no ponderado, porque expande en ondas concéntricas desde el origen. La primera vez que toca una celda de la otra isla, ese nivel es la respuesta.

Habilidades y conceptos clave para resolver el problema

Dominar este ejercicio implica integrar varias herramientas de pensamiento algorítmico que conviene tener claras antes de escribir código.

• Matriz binaria: estructura de datos donde solo existen dos valores posibles, en este caso uno y cero, usada para modelar mapas, grillas o estados booleanos.
• Adyacencia ortogonal: dos celdas son vecinas si comparten un lado, no una esquina. Es la regla que define qué celdas pertenecen a la misma isla.
• DFS (Depth First Search): técnica ideal para marcar componentes conectados, como hiciste al identificar islas en el problema anterior.
• BFS (Breadth First Search): el corazón de este reto, porque expande por niveles y encuentra la distancia mínima en grafos no ponderados.
• Reutilización de soluciones: reconocer cuándo un problema nuevo es una extensión de uno conocido te ahorra tiempo y reduce errores.

Una vez tengas claros estos elementos, intenta escribir tu propia implementación antes de ver la solución. Comparte en los comentarios cómo adaptarías el código de número de islas y qué enfoque usarías para construir el puente.