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
toader paul (paul444) Insule 08 Noiembrie 2024, 21:44 Evaluare finalizată 100
toader paul (paul444) Insule 08 Noiembrie 2024, 20:35 Evaluare finalizată 40
Grecu Rareș (grecuconstantinrares) Insule 08 Noiembrie 2024, 13:32 Evaluare finalizată 100
Terchea David-Cristian (davidterchea) Insule 06 Noiembrie 2024, 09:25 Evaluare finalizată 100
Onet Ioana (OnetIoana) Insule 04 Noiembrie 2024, 22:08 Evaluare finalizată 100
Selagea Romina (MadalinaSelagea) Insule 04 Noiembrie 2024, 22:08 Evaluare finalizată 100
Onet Ioana (OnetIoana) Insule 04 Noiembrie 2024, 20:50 Evaluare finalizată E.C
Badau Andrei (andreibadau) Insule 04 Noiembrie 2024, 19:46 Evaluare finalizată 40
Badau Andrei (andreibadau) Insule 04 Noiembrie 2024, 18:02 Evaluare finalizată 40
Badau Andrei (andreibadau) Insule 04 Noiembrie 2024, 17:52 Evaluare finalizată 4
Badau Andrei (andreibadau) Insule 03 Noiembrie 2024, 13:26 Evaluare finalizată 0
Floroiu Marius (Marius_Cristian) Insule 01 Noiembrie 2024, 17:50 Evaluare finalizată 100
Badau Andrei (andreibadau) Insule 01 Noiembrie 2024, 13:29 Evaluare finalizată 0
Badau Andrei (andreibadau) Insule 01 Noiembrie 2024, 00:19 Evaluare finalizată 0
Badau Andrei (andreibadau) Insule 31 Octombrie 2024, 22:28 Evaluare finalizată 0
Badau Andrei (andreibadau) Insule 31 Octombrie 2024, 22:25 Evaluare finalizată 0
Dumitru Anca (Dumitru_Anca28) Insule 31 Octombrie 2024, 19:17 Evaluare finalizată 52
Badau Andrei (andreibadau) Insule 31 Octombrie 2024, 14:57 Evaluare finalizată 0
Badau Andrei (andreibadau) Insule 31 Octombrie 2024, 14:56 Evaluare finalizată 0
Ionescu Mihail (Mihail_117) Insule 31 Octombrie 2024, 12:57 Evaluare finalizată 100
Badau Andrei (andreibadau) Insule 31 Octombrie 2024, 11:04 Evaluare finalizată 0
Anea Rares Florin (Rares132) Insule 29 Octombrie 2024, 21:01 Evaluare finalizată 100
Anea Rares Florin (Rares132) Insule 29 Octombrie 2024, 20:38 Evaluare finalizată 94
Anea Rares Florin (Rares132) Insule 29 Octombrie 2024, 20:01 Evaluare finalizată 88
Anea Rares Florin (Rares132) Insule 29 Octombrie 2024, 19:18 Evaluare finalizată 40
Anea Rares Florin (Rares132) Insule 29 Octombrie 2024, 19:04 Evaluare finalizată 22
Anea Rares Florin (Rares132) Insule 29 Octombrie 2024, 19:02 Evaluare finalizată 22
Anea Rares Florin (Rares132) Insule 29 Octombrie 2024, 19:02 Evaluare finalizată 0
Anea Rares Florin (Rares132) Insule 29 Octombrie 2024, 18:58 Evaluare finalizată 22
Anea Rares Florin (Rares132) Insule 29 Octombrie 2024, 18:58 Evaluare finalizată 0
Bogdan Paula (Paula08) Insule 29 Octombrie 2024, 16:38 Evaluare finalizată 100
Sbora Ioan-David (Sbora_Ioan_David) Insule 29 Octombrie 2024, 16:07 Evaluare finalizată 100
Anonymous Anonymous (Hacker_1) Insule 29 Octombrie 2024, 16:05 Evaluare finalizată 100
Capraroiu Antonio (Antonio6356) Insule 29 Octombrie 2024, 14:10 Evaluare finalizată 88
Capraroiu Antonio (Antonio6356) Insule 29 Octombrie 2024, 14:08 Evaluare finalizată 8
Capraroiu Antonio (Antonio6356) Insule 29 Octombrie 2024, 13:15 Evaluare finalizată 40
Capraroiu Antonio (Antonio6356) Insule 29 Octombrie 2024, 13:07 Evaluare finalizată 100
Capraroiu Antonio (Antonio6356) Insule 29 Octombrie 2024, 13:05 Evaluare finalizată 0
Cocu Tudor (っ◔◡◔)っ (TudorCocu) Insule 27 Octombrie 2024, 14:11 Evaluare finalizată 100
Georgescu Mihai (31mihai) Insule 25 Octombrie 2024, 17:35 Evaluare finalizată 100
Anderco Nora (NoraAnderco) Insule 25 Octombrie 2024, 14:50 Evaluare finalizată E.C
Anderco Nora (NoraAnderco) Insule 25 Octombrie 2024, 14:48 Evaluare finalizată E.C
Georgescu Mihai (31mihai) Insule 25 Octombrie 2024, 10:37 Evaluare finalizată 100
Onet Ioana (OnetIoana) Insule 25 Octombrie 2024, 08:49 Evaluare finalizată 0
Bogdan Paula (Paula08) Insule 25 Octombrie 2024, 08:20 Evaluare finalizată 40
Onet Ioana (OnetIoana) Insule 25 Octombrie 2024, 08:17 Evaluare finalizată 40
Selagea Romina (MadalinaSelagea) Insule 25 Octombrie 2024, 08:15 Evaluare finalizată 40
Onet Ioana (OnetIoana) Insule 25 Octombrie 2024, 08:14 Evaluare finalizată 40
Onet Ioana (OnetIoana) Insule 25 Octombrie 2024, 08:14 Evaluare finalizată 32
Selagea Romina (MadalinaSelagea) Insule 25 Octombrie 2024, 00:36 Evaluare finalizată 32