Creus gregues palíndromes P96612


Statement
 

pdf   zip

thehtml
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++