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
Darabaneanu Liviu Eugen (Darabaneanu_Liviu_Eugen) Insule 22 August 2019, 15:38 Evaluare finalizată 100
Darabaneanu Liviu Eugen (Darabaneanu_Liviu_Eugen) Insule 22 August 2019, 15:27 Evaluare finalizată 94
Darabaneanu Liviu Eugen (Darabaneanu_Liviu_Eugen) Insule 22 August 2019, 15:23 Evaluare finalizată 32
Darabaneanu Liviu Eugen (Darabaneanu_Liviu_Eugen) Insule 22 August 2019, 15:20 Evaluare finalizată 30
Darabaneanu Liviu Eugen (Darabaneanu_Liviu_Eugen) Insule 22 August 2019, 15:19 Evaluare finalizată 30
Darabaneanu Liviu Eugen (Darabaneanu_Liviu_Eugen) Insule 22 August 2019, 15:16 Evaluare finalizată 34
Darabaneanu Liviu Eugen (Darabaneanu_Liviu_Eugen) Insule 22 August 2019, 15:15 Evaluare finalizată 34
Darabaneanu Liviu Eugen (Darabaneanu_Liviu_Eugen) Insule 22 August 2019, 14:33 Evaluare finalizată 40
Camilla Camilla (camilla) Insule 19 August 2019, 14:26 Evaluare finalizată 100
Vamanu Petru Gabriel (petrisorvmy) Insule 16 August 2019, 15:57 Evaluare finalizată 100
lazar vlad (vvvlll50) Insule 09 August 2019, 19:26 Evaluare finalizată 100
lazar vlad (vvvlll50) Insule 09 August 2019, 19:14 Evaluare finalizată 0
lazar vlad (vvvlll50) Insule 09 August 2019, 19:12 Evaluare finalizată 6
Turbatu Miruna Teodora (Myra) Insule 06 August 2019, 17:50 Evaluare finalizată 100
Chipuc Valentin (valentin23) Insule 31 Iulie 2019, 01:24 Evaluare finalizată 88
Chipuc Valentin (valentin23) Insule 28 Iulie 2019, 23:32 Evaluare finalizată 88
Chipuc Valentin (valentin23) Insule 28 Iulie 2019, 23:25 Evaluare finalizată 100
Chipuc Valentin (valentin23) Insule 28 Iulie 2019, 23:25 Evaluare finalizată 100
Chipuc Valentin (valentin23) Insule 28 Iulie 2019, 23:21 Evaluare finalizată 100
Grincea Raluca (rikka) Insule 26 Iulie 2019, 19:35 Evaluare finalizată 100
Grincea Raluca (rikka) Insule 26 Iulie 2019, 19:34 Evaluare finalizată E.C
Grincea Raluca (rikka) Insule 26 Iulie 2019, 19:06 Evaluare finalizată 40
Cioara David (david_darius) Insule 23 Iulie 2019, 20:00 Evaluare finalizată 100
Cioara David (david_darius) Insule 23 Iulie 2019, 19:49 Evaluare finalizată 60
Cioara David (david_darius) Insule 23 Iulie 2019, 15:07 Evaluare finalizată 0
Slanina Iulia (Iulia0305) Insule 21 Iulie 2019, 14:03 Evaluare finalizată 100
Arsenoiu Iulian George (iulianarsenoiu) Insule 17 Iulie 2019, 12:51 Evaluare finalizată 100
Zavadovschi Bogdan (zaBogdan) Insule 13 Iulie 2019, 23:19 Evaluare finalizată 100
Zavadovschi Bogdan (zaBogdan) Insule 13 Iulie 2019, 22:29 Evaluare finalizată 40
Răduță Lavinia-Elena (RadutaLaviniaElena) Insule 13 Iulie 2019, 11:39 Evaluare finalizată 100
Răduță Lavinia-Elena (RadutaLaviniaElena) Insule 13 Iulie 2019, 11:13 Evaluare finalizată 0
Răduță Lavinia-Elena (RadutaLaviniaElena) Insule 13 Iulie 2019, 11:13 Evaluare finalizată E.C
Nicu Pavel (NNNNN) Insule 13 Iulie 2019, 01:59 Evaluare finalizată E.C
Hurjui Alexandru (hurjui_alexandru12) Insule 11 Iulie 2019, 00:19 Evaluare finalizată 100
R Adia (39_2003_Adia) Insule 08 Iulie 2019, 12:41 Evaluare finalizată 100
R Adia (39_2003_Adia) Insule 08 Iulie 2019, 12:19 Evaluare finalizată 16
Mesota Ioan (MESOTRIST_2) Insule 06 Iulie 2019, 12:27 Evaluare finalizată 100
Mesota Ioan (MESOTRIST_1) Insule 04 Iulie 2019, 19:41 Evaluare finalizată 100
Hosu Iulia (Iulia3) Insule 03 Iulie 2019, 11:21 Evaluare finalizată 100
Hosu Iulia (Iulia3) Insule 03 Iulie 2019, 10:59 Evaluare finalizată 82
Hosu Iulia (Iulia3) Insule 02 Iulie 2019, 16:56 Evaluare finalizată 32
Stancu Sergiu (SergiuS2003) Insule 29 Iunie 2019, 22:05 Evaluare finalizată 100
Cristian Benghe (_Cristi) Insule 28 Iunie 2019, 09:41 Evaluare finalizată 100
Cristian Benghe (_Cristi) Insule 28 Iunie 2019, 09:41 Evaluare finalizată 100
Cristian Benghe (_Cristi) Insule 28 Iunie 2019, 09:38 Evaluare finalizată 46
Arkham Knighty (ArkhamKnighty) Insule 26 Iunie 2019, 19:27 Evaluare finalizată 78
Arkham Knighty (ArkhamKnighty) Insule 26 Iunie 2019, 19:27 Evaluare finalizată 84
Popescu Stefan (PopescuStefan) Insule 25 Iunie 2019, 00:01 Evaluare finalizată 100
Popescu Stefan (PopescuStefan) Insule 24 Iunie 2019, 23:10 Evaluare finalizată 40
Popescu Stefan (PopescuStefan) Insule 24 Iunie 2019, 23:07 Evaluare finalizată 40