Soluții trimise

Rezumat problemă

#1099 Insule

Arhipelagul RGB este format din insule care aparţin ţărilor R, G şi B. Putem reprezenta harta arhipelagului ca o matrice cu n linii şi m coloane cu elemente din mulţimea {0, 1, 2, 3}. Un element egal cu 0 reprezintă o zonă acoperită de apă; un element egal cu 1 reprezintă o zonă de pământ aparţinând unei insule din ţara R, iar un element egal cu 2 reprezintă o zonă de pământ aparţinând unei insule din ţara G, iar un element egal cu 3 reprezintă o zonă de pământ aparţinând unei insule din ţara B.

Se consideră că două elemente ale matricei sunt vecine dacă ele au aceeaşi valoare şi fie sunt consecutive pe linie, fie sunt consecutive pe coloană. Două elemente aparţin aceleiaşi insule dacă ele sunt vecine sau dacă se poate ajunge de la un element la celălalt pe un drum de-a lungul căruia oricare două elemente consecutive sunt vecine.

Pentru a încuraja relaţiile de colaborare dintre ţările R şi G, se doreşte construirea unui pod care să unească o insulă aparţinând ţării R de o insulă aparţinând ţării G. Podul trebuie să respecte următoarele condiţii:

  • să înceapă pe o zonă cu apă consecutivă pe linie sau coloană cu o zonă aparţinând ţării R;
  • să se termine pe o zonă cu apă consecutivă pe linie sau coloană cu o zonă aparţinând ţării G;
  • să traverseze numai zone acoperite cu apă;
  • oricare două elemente consecutive ale podului trebuie să fie vecine;
  • lungimea podului să fie minimă (lungimea podului este egală cu numărul de elemente traversate de pod).

Dată fiind harta arhipelagului să se determine câte insule aparţin fiecărei ţări, precum şi lungimea minimă a unui pod care să satisfacă condiţiile din enunț.

ID   Utilizator Problema Data încărcării Stare
Carmen Dana (xdana) Insule 23 Ianuarie 2020, 18:51 Evaluare finalizată 100
C/C++ Java (Nirvana) Insule 22 Ianuarie 2020, 15:20 Evaluare finalizată 100
Andrei Galitianu (andreigali) Insule 21 Ianuarie 2020, 18:04 Evaluare finalizată 40
Andrei Galitianu (andreigali) Insule 21 Ianuarie 2020, 18:01 Evaluare finalizată 20
Andrei Galitianu (andreigali) Insule 21 Ianuarie 2020, 17:58 Evaluare finalizată 8
Popa Bianca Daniela (popabianca) Insule 21 Ianuarie 2020, 17:33 Evaluare finalizată 46
Popa Bianca Daniela (popabianca) Insule 21 Ianuarie 2020, 09:49 Evaluare finalizată 46
Pandele Horatiu (hatchiq) Insule 20 Ianuarie 2020, 20:32 Evaluare finalizată 100
Pandele Horatiu (hatchiq) Insule 20 Ianuarie 2020, 20:28 Evaluare finalizată 94
Pandele Horatiu (hatchiq) Insule 20 Ianuarie 2020, 20:05 Evaluare finalizată 58
Croitoriu Andrei (Andrei_Croitoriu) Insule 20 Ianuarie 2020, 18:52 Evaluare finalizată 100
Dragomir Robert (RobertsHomework) Insule 20 Ianuarie 2020, 18:39 Evaluare finalizată 100
Serban Marinel (marinelserban) Insule 20 Ianuarie 2020, 18:38 Evaluare finalizată 100
Dragomir Robert (RobertsHomework) Insule 20 Ianuarie 2020, 18:31 Evaluare finalizată 40
Mortu Marian (MortuJAVA) Insule 20 Ianuarie 2020, 18:01 Evaluare finalizată 40
Onut Daniela (Daniela10416) Insule 20 Ianuarie 2020, 17:37 Evaluare finalizată 100
Onut Daniela (Daniela10416) Insule 20 Ianuarie 2020, 17:29 Evaluare finalizată 88
Onut Daniela (Daniela10416) Insule 20 Ianuarie 2020, 16:47 Evaluare finalizată 40
Onut Daniela (Daniela10416) Insule 20 Ianuarie 2020, 16:47 Evaluare finalizată 0
Anca Alexandru (AncaAlexandru) Insule 19 Ianuarie 2020, 20:47 Evaluare finalizată 100
Anca Alexandru (AncaAlexandru) Insule 19 Ianuarie 2020, 20:44 Evaluare finalizată 70
Anca Alexandru (AncaAlexandru) Insule 19 Ianuarie 2020, 20:43 Evaluare finalizată E.C
Anca Alexandru (AncaAlexandru) Insule 19 Ianuarie 2020, 20:37 Evaluare finalizată 70
Anca Alexandru (AncaAlexandru) Insule 19 Ianuarie 2020, 20:31 Evaluare finalizată 10
Anca Alexandru (AncaAlexandru) Insule 19 Ianuarie 2020, 20:23 Evaluare finalizată 10
Udriste Mihai (Udriste_Mihai) Insule 19 Ianuarie 2020, 20:21 Evaluare finalizată 0
Udriste Mihai (Udriste_Mihai) Insule 19 Ianuarie 2020, 20:12 Evaluare finalizată 0
Udriste Mihai (Udriste_Mihai) Insule 19 Ianuarie 2020, 20:12 Evaluare finalizată 0
Onut Daniela (Daniela10416) Insule 19 Ianuarie 2020, 18:29 Evaluare finalizată 32
Onut Daniela (Daniela10416) Insule 19 Ianuarie 2020, 17:41 Evaluare finalizată 32
Popescu Alin (Popescu_Alin) Insule 19 Ianuarie 2020, 16:16 Evaluare finalizată 0
Lucaciuc Andrei (lucaciuc_andrei) Insule 19 Ianuarie 2020, 14:43 Evaluare finalizată 0
Popescu Alin (Popescu_Alin) Insule 19 Ianuarie 2020, 14:01 Evaluare finalizată 0
Popescu Adrian (popescu_adrian17) Insule 18 Ianuarie 2020, 16:10 Evaluare finalizată 100
Popescu Adrian (popescu_adrian17) Insule 18 Ianuarie 2020, 15:20 Evaluare finalizată 70
Onut Daniela (Daniela10416) Insule 17 Ianuarie 2020, 21:58 Evaluare finalizată 0
Onut Daniela (Daniela10416) Insule 17 Ianuarie 2020, 20:22 Evaluare finalizată 0
Andrei Galitianu (andreigali) Insule 15 Ianuarie 2020, 19:31 Evaluare finalizată 4
Bucur-Sabau Maria-Mirabela (MariaMirabella2) Insule 14 Ianuarie 2020, 13:48 Evaluare finalizată 100
Urieșu Iulius (Uriesu_Iulius) Insule 13 Ianuarie 2020, 20:05 Evaluare finalizată 100
Niţă Mihai-Daniel (nmdaniel) Insule 13 Ianuarie 2020, 08:47 Evaluare finalizată 100
Quintus Maximus (mquintus) Insule 12 Ianuarie 2020, 18:57 Evaluare finalizată 100
Quintus Maximus (mquintus) Insule 12 Ianuarie 2020, 18:52 Evaluare finalizată 74
Quintus Maximus (mquintus) Insule 12 Ianuarie 2020, 18:44 Evaluare finalizată 0
Quintus Maximus (mquintus) Insule 12 Ianuarie 2020, 17:42 Evaluare finalizată 0
Quintus Maximus (mquintus) Insule 12 Ianuarie 2020, 17:39 Evaluare finalizată 0
Quintus Maximus (mquintus) Insule 12 Ianuarie 2020, 17:39 Evaluare finalizată 0
scarlat marius (mariusOJI) Insule 12 Ianuarie 2020, 17:16 Evaluare finalizată 100
Bostan Matei-Calin (bostanmatei) Insule 10 Ianuarie 2020, 00:49 Evaluare finalizată 100
Higyed Erik (higyederik) Insule 06 Ianuarie 2020, 14:09 Evaluare finalizată 100