Fişierul intrare/ieşire:enclave.in, enclave.outSursăad-hoc
AutorCatalin FrancuAdăugată deCatalin.FrancuCatalin Francu Catalin.Francu
Timp execuţie pe test0.6 secLimită de memorie8192 kbytes
Scorul tăuN/ADificultatenormalnormalnormalnormalnormal

Vezi solutiile trimise

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 direct 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.inenclave.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 sa te autentifici pentru a trimite solutii. Click aici