zone

Time limit: 0.15s Memory limit: 16MB Input: zone.in Output: zone.out

Scooby-Doo, celebrul personaj de desene animate, a intrat iar în bucluc. Acesta se găseşte acum într-o cameră dreptunghiulară de dimensiuni nmn \cdot m alcătuită din celule pătratice de latură 11, divers colorate.

Se definesc:

  • Zonă - ca fiind un grup cu număr maxim de celule de aceeaşi culoare, adiacente pe linie sau pe coloană.
  • SUPERZONA - ca fiind o mulţime AA de zone, cu proprietatea că fiecare are cel puţin kk zone vecine aflate în aceeaşi mulţime AA.

Pentru a fi în siguranţă, Scooby-Doo trebuie să se adăpostească într-o SUPERZONĂ cu număr maxim de celule din matrice.

Cerinţă

Părăsit de prietenii săi, Scooby-Doo nu se descurcă de unul singur şi vă roagă pe voi să rezolvaţi misterul şi să calculaţi numărul de celule al celei mai mari SUPERZONE din matrice.

Date de intrare

Fişierul de intrare zone.in conţine pe prima linie numerele naturale n,mn,m şi kk separate prin câte un spaţiu. Pe următoarele nn linii se află câte m caractere, fără spaţii între ele, reprezentând culoarea respectivei celule din matrice.

Date de ieşire

Fişierul de ieşire zone.out va conţine pe prima linie un număr natural ce reprezintă numărul de celule al celei mai mari SUPERZONE din matrice.

Restricţii şi precizări

  • 2n,m,k3002 \leq n, m, k \leq 300
  • Culorile sunt reprezentate prin litere mici ale alfabetului englez (a - z)
  • Două celule se consideră adiacente dacă au o latură comună
  • Două zone se consideră vecine dacă au cel puţin câte o celulă adiacentă

Exemplu

zone.in

4 3 2
aaa
bad
baa
cda

zone.out

11

Explicație

Este selectată toată matricea fără zona formată din litera d de pe ultima coloană.

Log in or sign up to be able to send submissions!