Atenție! Aceasta este o versiune veche a paginii., scrisă la 2014-03-27 15:23:01.
Revizia anterioară   Revizia următoare  

Fișierul intrare/ieșire enclave.in, enclave.out Sursă ad-hoc
Autor Cătălin Frâncu Adăugată de avatar Catalin.Francu Cătălin Frâncu Catalin.Francu
Timp de execuție pe test 0.6 sec Limită de memorie 8192 KB
Scorul tău N/A Dificultate stea de rating de tip fullstea de rating de tip emptystea de rating de tip emptystea de rating de tip emptystea de rating de tip empty
open book Poți vedea testele pentru această problemă accesând atașamentele .

Enclave

Un continent are formă dreptunghiulară și este împărțit în M x N parcele pătrate cu latura de 1 km. Pe continent se află K țări. Fiecare țară constă doar din parcele întregi și este conexă, adică între oricare două parcele dintr-o țară se poate circula direct fără a părăsi țara. Între două parcele se poate circula dacă au o latură comună. Continentul este înconjurat de ocean.

O enclavă este o țară care se învecinează cu o singură altă țară și care nu are ieșire la ocean.

Să se determine numărul de enclave și perimetrul celei mai mari enclave.

Date de intrare

Fișierul de intrare enclave.in conține pe prima linie numerele M și N. Pe următoarele M linii se află câte N numere. Fiecare număr este cuprins între 1 și K și indică țara căreia îi aparține parcela respectivă.

Date de ieșire

În fișierul de ieșire enclave.out se va scrie o singură linie conținând două numere separate printr-un spațiu: numărul de enclave și perimetrul celei mai mari enclave.

Restricții

  • 1 ≤ M, N ≤ 1.000
  • 1 ≤ K ≤ 100
  • aria oricărei țări este de cel mult 100.000 km2
  • se garantează că există cel puțin o enclavă

Exemplu

enclave.in enclave.out
7 8
1 1 1 1 1 1 1 1
1 1 2 2 1 1 4 1
1 2 2 3 2 1 1 1
1 2 3 3 2 1 1 1
1 2 2 2 2 2 2 1
1 1 1 1 1 1 1 1
1 1 1 1 1 5 5 1
2 8

Explicație

Cele două enclave sunt țările 3 și 4. Dintre ele, enclava 3 are perimetrul maxim de 8 km (lungimea liniei portocalii).

Țara 5 nu este o enclavă, deoarece are ieșire la ocean.

Trebuie să te autentifici pentru a trimite soluții. Click aici

Indicii de rezolvare

Arată 3 categorii