Kvadrat črk

Osnovne informacije

Omejitve
  • Čas: 5 s
  • Spomin: 256 MB
Avtor:
  • UPM

Pošlji rešitev

Opozorilo: Ta naloga je v pripravi. Oddane rešitve morda ne bodo smiselno ocenjene.



Tvoji rezultati.
Nisi poslal še nobene rešitve.
Več »

Dana je pravokotna tabela T s h vrsticami in w stolpci. V vsaki celici mreže je zapisana neka mala črka angleške abecede. V tej tabeli bi radi našli dve čim večji kvadratni območji s popolnoma enako vsebino (pri tem se lahko oba kvadrata tudi prekrivata, ne smeta pa čisto sovpadati). Z drugimi besedami, iščemo takšne x_{1}, y_{1}, x_{2}, y_{2} in k, da bo veljalo

  • x_{1} ≠ x_{2},
  • y_{1} ≠ y_{2},
  • T[x_{1} + i, y_{1} + j] = T[x_{2} + i, y_{2} + j]

za vsak i = 0, …, k − 1, in vsak j = 0, …, k − 1,

pri tem pa naj bo k največji možni.

Vhodni podatki

V prvi vrstici sta dve celi števili, najprej h in nato w, ločeni z enim presledkom. Veljalo bo 1 ≤ w ≤ 500 in 1 ≤ h ≤ 500. Sledi h vrstic, ki podajajo vsebino tabele; v vsaki od teh vrstic je w znakov, vsi ti znaki pa so male črke angleške abecede.

Izhodni podatki

V prvo vrstico izpiši k, v drugo vrstico izpiši najprej y_{1} in nato x_{1}, v tretjo pa najprej y_{2} in nato x_{2}. (Koordinate se štejejo od 1 naprej; zgornji levi kot tabele ima koordinati (1, 1).) Če je možnih več enako dobrih rešitev, je vseeno, katero izpišeš. Če je k = 0, potem druge in tretje vrstice ne izpiši.

Primer

Vhod

6 9
qoioioqio
ooqioioik
oioikikio
oikioqioi
iqioiiioq
kioooooio

Izhod

4
1 6
2 2
Tip: Log in to
  • submit and test your solution
  • post or read questions and answers about this task