Creus gregues palíndromes P96612
La creu grega (o crux immissa quadrata)
és una creu formada per quatre braços de la mateixa mida que s’intersequen en angle recte.
Donada una matriu de caràcters de mida n × m,
compteu quantes creus gregues palíndromes s’hi formen de cada mida.
Una creu és palíndroma quan la paraula dels braços verticals
i la paraula dels braços horitzontals
són ambdues palíndromes,
tenen la mateixa mida, que és almenys tres i,
òbviament, es creuen a l’element central.
unit=0.25cm
(10,10)
linestyle=solid
linecolor=blue
(0,4)(10,6)
(4,0)(6,10)
Entrada
L’entrada consisteix en diversos casos. Cada cas comença amb n i m, seguides d’n línies amb m lletres minúscules cadascuna. Podeu suposar que n i m estan entre 3 i 100.
Sortida
Per a cada cas, escriviu quantes creus gregues palíndromes de cada mida (senar) hi ha. Només heu d’escriure aquelles mides en què hi hagi alguna creu. Escriviu una línia amb 10 guions al final de cada cas.
Observació
La vostra solució ha de ser raonablement eficient. Per exemple, la solució del jutge té cost O(n3) en el cas pitjor amb una matriu n × n. Penseu, per a cada possible centre, en la creu palíndroma de mida màxima centrada en aquella posició.
Public test cases
Input
3 4 abac bcbc cbad 3 3 abc aaa cac 5 5 zzzzz zzzzz zzzzz zzzzz zzzzz 7 10 abcdddrfgy abcdddsfgy abcdddtfgy dddddddddy abcdddtfgy abcdddsfgy abczzzrfgy
Output
3 : 2 ---------- ---------- 3 : 9 5 : 1 ---------- 3 : 10 5 : 5 ----------
Information
- Author
- Maria Blesa
- Language
- Catalan
- Official solutions
- C++
- User solutions
- C++