¿Cuál es el costo mínimo para conectar todas las islas?
Hay una cuadrícula de tamañoN x M. Algunas células sonislas denotado por '0' y los otros sonagua. Cada celda de agua tiene un número que indica el costo de un puente hecho en esa celda. Debe encontrar el costo mínimo por el cual se pueden conectar todas las islas. Una celda está conectada a otra celda si comparte un borde o un vértice.
¿Qué algoritmo se puede usar para resolver este problema?
Editar: ¿Qué se puede usar como un enfoque de fuerza bruta si los valores de N, M son muy pequeños, digamos NxM <= 100?
Ejemplo: En la imagen dada, las celdas verdes indican islas, las celdas azules indican agua y las celdas azules claras indican las celdas sobre las cuales se debe hacer un puente. Por lo tanto, para la siguiente imagen, la respuesta será17.
Inicialmente pensé en marcar todas las islas como nodos y conectar cada par de islas por un puente más corto. Entonces, el problema podría reducirse a un árbol de expansión mínimo, pero en este enfoque omití el caso en el que los bordes se superponen.Por ejemplo, en la siguiente imagen, la distancia más corta entre dos islas es7(marcado en amarillo), por lo que al usar Árboles de expansión mínima la respuesta sería14, pero la respuesta debería ser11 (marcado en azul claro).