Por favor alguien que me ayude con este programa necesito la parte de programacion en la que detecte cuando las islas son diagonales y no se puede hacer los puentes
Se quiere construir puentes y se quiere hacerlo con la mayor brevedad posible y de la forma más económica, el país está compuesto de una matriz de islas de N por M, donde cada isla (celda) está separada de su adyacente por un rio que corre entre ellas. Se quiere calcular cuánto dinero necesita para construir puentes suficientes para conectar TODAS las islas.
Cada una de las celdas puede ser de tres tipos:
• Bosque (B)
• Terreno vacío (T)
• Lago (L)
Un ejemplo de matriz sería así:
BTLT
LLTT
BBBB
Los costos para la construcción de los puentes son:
Entre Terreno Vacío y Terreno Vacío $ 5
Entre Bosque y Terreno Vacío $ 10
Entre Bosque y Bosque $ 15
FACULTAD DE INGENIERÍA
2
Si para hacer uno de los puentes descritos en las alternativas anteriores, se tiene que pasar un lago se carga un monto adicional de $ 20.
Condiciones:
• La esquina superior izquierda siempre será un Bosque y servirá de inicio de la construcción de todos los puentes.
• Un puente sólo puede ser construido entre dos islas si son adyacentes vertical u horizontalmente (pudiendo estar separadas por un lago), no existen puentes diagonales.
• Para construir un puente se debe poder llegar al lugar por puentes que ya han sido previamente construidos.
• Todas las soluciones deben cumplir la condición de unir TODAS las islas.
• No siempre será posible la conexión de todas las islas a través de puentes, como se puede ver en el siguiente ejemplo de entrada:
BLLL
LLTL
LLLB
Solución al problema:
• Se considera el desarrollo de un programa visualmente atractivo (donde B, T y L se ilustren gráficamente) e intuitivo para el usuario que:
o Dado un mapa de las islas, permita a diferentes ingenieros construir alternativas para conectar TODAS las islas, cada ingeniero planteará una alternativa y el sistema mostrará también una alternativa para conectar TODAS las islas.
o En todos los casos el sistema calculará la cantidad de dinero necesario para construir la solución propuesta y el tiempo empleado en el planteamiento de la solución.
o Finalmente el sistema indicará a través de un/unos listado(s) ordenado(s) cuál es la mas rapida
