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 | 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 |
Vezi soluțiile trimise | Statistici
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 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
Exemplu
enclave.in | enclave.out |
---|---|
7 8 1 1 1 1 1 1 1 1 1 1 2 2 1 1 1 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 4 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.