Subconjunts tranquils P91562


Statement
 

pdf   zip

thehtml

Esteu planificant un viatge per als n membres d’un club. Tanmateix, a alguns dels membres no els agraden altres membres. Per tant, decidiu escollir un subconjunt S dels membres tal que, dins d’S, a ningú li desagradi ningú.

Donada tota la informació de a qui li desagrada qui, podeu comptar el nombre d’aquests subconjunts?

Entrada

L’entrada consisteix en diversos casos, cadascun amb n seguida d’n línies amb n caràcters cadascuna. Per a ij, el caràcter j-èsim de la i-èsima línia és ‘A’ o ‘D’ depenent de si a i li agrada o li desagrada j. La diagonal només té punts. Assumiu 1 ≤ n ≤ 20.

Sortida

Per a cada cas, escriviu el nombre de subconjunts tranquils que no siguin buits.

Public test cases
  • Input

    2
    .D
    A.
    
    5
    .ADDA
    D.ADA
    DA.AA
    ADD.D
    AAAA.
    
    6
    .AAAAA
    A.AAAA
    AA.AAA
    DAA.AA
    AADA.A
    AAADD.
    

    Output

    2
    10
    25
    
  • Information
    Author
    Salvador Roura
    Language
    Catalan
    Official solutions
    C++
    User solutions
    C++