Creus gregues palíndromes P96612

0.75 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 \times 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.

0.25

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(n^3)$ en el cas pitjor amb una matriu $n \times n$. Penseu, per a cada possible centre, en la creu palíndroma de mida màxima centrada en aquella posició.