Placid subsets P68087


Statement
 

pdf   zip

thehtml

You are planning a trip for the n members of a club. However, some of the members dislike other members. Therefore, you decide to choose a subset S of members such that:

  • Inside S, noone dislikes anyone.
  • There is no S′ such that SS′ and such that S′ fulfils the first property. In other words, S must be maximal.

Given the information about who dislikes who, can you count the number of such subsets?

Input

Input consists of several cases, each one with n followed by n lines with n characters each. For ij, the j-th character of the i-th line is ‘L’ or ‘D’ depending on whether i likes or dislikes ‍j. The diagonal has only dots. Assume 1 ≤ n ≤ 20.

Output

For every case, print the number of maximal placid subsets.

Public test cases
  • Input

    2
    .D
    L.
    
    5
    .LDDL
    D.LDL
    DL.LL
    LDD.D
    LLLL.
    
    6
    .LLLLL
    L.LLLL
    LL.LLL
    DLL.LL
    LLDL.L
    LLLDD.
    

    Output

    2
    3
    4
    
  • Information
    Author
    Salvador Roura
    Language
    English
    Official solutions
    C++
    User solutions
    C++