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
Onut Onu (OnuOnut) Insule 28 Martie 2024, 10:15 Evaluare finalizată 100
Loghin Antonia (anto_0124) Insule 24 Martie 2024, 12:20 Evaluare finalizată 100
Pop Ionut (Ionut44) Insule 18 Martie 2024, 16:37 Evaluare finalizată 100
Ciocan Radu (RaduCIOCAN) Insule 17 Martie 2024, 18:57 Evaluare finalizată 100
Fodor Rares-Costin (FRD233) Insule 15 Martie 2024, 17:23 Evaluare finalizată 100
Fodor Rares-Costin (FRD233) Insule 15 Martie 2024, 17:22 Evaluare finalizată 42
Fodor Rares-Costin (FRD233) Insule 15 Martie 2024, 17:21 Evaluare finalizată 40
Fodor Rares-Costin (FRD233) Insule 15 Martie 2024, 17:20 Evaluare finalizată 40
Fodor Rares-Costin (FRD233) Insule 15 Martie 2024, 17:20 Evaluare finalizată 36
Fodor Rares-Costin (FRD233) Insule 15 Martie 2024, 17:00 Evaluare finalizată 48
Fodor Rares-Costin (FRD233) Insule 15 Martie 2024, 16:58 Evaluare finalizată 40
Cornea Radu (CorneaRadu) Insule 15 Martie 2024, 15:42 Evaluare finalizată 100
Dobrin Raul Andrei (Dobrin_Raul_Andrei) Insule 15 Martie 2024, 15:21 Evaluare finalizată 76
Pop Ionut (Ionut4428) Insule 15 Martie 2024, 13:19 Evaluare finalizată 100
Pintea Andrei (andreipintea0777) Insule 14 Martie 2024, 20:13 Evaluare finalizată 100
Pintea Andrei (andreipintea0777) Insule 14 Martie 2024, 20:12 Evaluare finalizată E.C
Gardos Rafael (rafael_xyz) Insule 14 Martie 2024, 19:14 Evaluare finalizată 40
Otlacan Fabian (Otlacan_Fabian) Insule 14 Martie 2024, 09:19 Evaluare finalizată 100
Otlacan Fabian (Otlacan_Fabian) Insule 14 Martie 2024, 09:03 Evaluare finalizată 46
Otlacan Fabian (Otlacan_Fabian) Insule 14 Martie 2024, 08:57 Evaluare finalizată 46
Dobrin Raul Andrei (Dobrin_Raul_Andrei) Insule 14 Martie 2024, 08:39 Evaluare finalizată E.C
Otlacan Fabian (Otlacan_Fabian) Insule 14 Martie 2024, 08:30 Evaluare finalizată 40
Crisan Bogdan (bogdan_crisan) Insule 13 Martie 2024, 18:13 Evaluare finalizată 100
Crisan Bogdan (bogdan_crisan) Insule 13 Martie 2024, 18:13 Evaluare finalizată 100
Crisan Bogdan (bogdan_crisan) Insule 13 Martie 2024, 18:12 Evaluare finalizată 0
Crisan Bogdan (bogdan_crisan) Insule 13 Martie 2024, 18:10 Evaluare finalizată 100
Crisan Bogdan (bogdan_crisan) Insule 13 Martie 2024, 18:09 Evaluare finalizată E.C
Crisan Bogdan (bogdan_crisan) Insule 13 Martie 2024, 18:09 Evaluare finalizată 40
Crisan Bogdan (bogdan_crisan) Insule 13 Martie 2024, 18:08 Evaluare finalizată E.C
Crisan Bogdan (bogdan_crisan) Insule 13 Martie 2024, 18:07 Evaluare finalizată 40
Crisan Bogdan (bogdan_crisan) Insule 13 Martie 2024, 18:06 Evaluare finalizată E.C
Crisan Bogdan (bogdan_crisan) Insule 13 Martie 2024, 18:04 Evaluare finalizată 40
Crisan Bogdan (bogdan_crisan) Insule 13 Martie 2024, 18:03 Evaluare finalizată 0
Crisan Bogdan (bogdan_crisan) Insule 13 Martie 2024, 18:02 Evaluare finalizată 0
Crisan Bogdan (bogdan_crisan) Insule 13 Martie 2024, 18:01 Evaluare finalizată 0
Crisan Bogdan (bogdan_crisan) Insule 13 Martie 2024, 17:59 Evaluare finalizată 0
Crisan Bogdan (bogdan_crisan) Insule 13 Martie 2024, 17:53 Evaluare finalizată 100
Crisan Bogdan (bogdan_crisan) Insule 13 Martie 2024, 17:51 Evaluare finalizată 0
Crisan Bogdan (bogdan_crisan) Insule 13 Martie 2024, 17:49 Evaluare finalizată 0
Crisan Bogdan (bogdan_crisan) Insule 13 Martie 2024, 17:40 Evaluare finalizată 0
Panait Petru (Petru_77) Insule 13 Martie 2024, 16:47 Evaluare finalizată 100
Pyramidal Society (But_Andrei) Insule 13 Martie 2024, 16:09 Evaluare finalizată 100
cuc sergiu (sergiu2010) Insule 13 Martie 2024, 15:48 Evaluare finalizată 100
slavnic valentino (Valentino22) Insule 13 Martie 2024, 11:28 Evaluare finalizată 60
slavnic valentino (Valentino22) Insule 13 Martie 2024, 11:27 Evaluare finalizată 60
slavnic valentino (Valentino22) Insule 13 Martie 2024, 11:26 Evaluare finalizată 64
slavnic valentino (Valentino22) Insule 13 Martie 2024, 11:24 Evaluare finalizată 64
slavnic valentino (Valentino22) Insule 13 Martie 2024, 11:23 Evaluare finalizată 64
slavnic valentino (Valentino22) Insule 13 Martie 2024, 11:22 Evaluare finalizată 64
slavnic valentino (Valentino22) Insule 13 Martie 2024, 11:21 Evaluare finalizată 64