Soluții trimise

Unul dintre cele mai influente regate din continentul Alaocs este regatul Ofni. Harta regatului poate fi redată ca o matrice cu n linii și m coloane. Regatul este format din munți (^), râuri și lacuri (~), locuri libere de teren (_) și orașe (x). Observăm că se pot forma zone delimitate de munți, ape sau marginile hărții. Numim zonă o porțiune maximă de teren care conține locuri libere de teren și orașe, delimitată de munți, ape și marginea hărții. De asemenea, mai multe orașe învecinate pe linie sau pe coloană formează o cetate.

Din cauza puterii tot mai mari a regatelor rivale Etam și Akizif regele regatului Ofni a decis să înceapă un proces de fortificare a orașelor și cetăților. Pentru a face asta este necesară construcția de drumuri. Regele dorește ca între fiecare oraș și fiecare cetate să existe cel puțin un drum care să le lege și ca între toate cetățile să existe cel puțin un drum. Costul construcției unui drum printr-un loc liber are costul 1, construcția unui pod peste apă are costul 2, iar al unui tunel prin munte are costul 3. Pentru a nu goli trezoreria regală, regele își dorește ca acest cost de construcție a drumurilor să fie minim.

Problema are două cerințe.
Pentru c = 1, se cere determinarea numărului de cetăți, a numărului de zone și a numărului minim și maxim de cetăți dintr-o zonă.
Pentru c = 2, se cere costul total, minim, de construcție a drumurilor care conectează cetățile și orașele.