Some Hamiltonian paths P90225


Statement
 

pdf   zip

thehtml

Consider a directed graph with n vertices and all the n(n − 1) possible arcs, some of which are painted. How many Hamiltonian paths are in the graph starting at vertex 0, ending at vertex n−1, and such that they do not traverse two consecutive painted arcs?

Input

Input consists of several cases. Every case begins with n, followed by an n × n matrix, where the position (i, j) has the color of the arc from vertex i to vertex j. A one indicates a painted arc, and a zero a non-painted arc. The diagonal (which is useless) only has zeroes. You can assume n ≥ 2.

Output

For every case, print the number of permutations of the n vertices that start at 0, end at n − 1, and do not have three consecutive vertices x, y and z such that the two arcs xy and yz are both painted. The test cases are such that the answer is smaller than 106.

Public test cases
  • Input

    2
    0 1
    1 0
    
    3
    0 1 1
    1 0 0
    1 1 0
    
    3
    0 1 0
    0 0 1
    0 0 0
    
    5
    0 1 0 0 0
    1 0 1 0 0
    0 0 0 0 1
    1 0 0 0 1
    0 1 0 0 0
    

    Output

    1
    1
    0
    4
    
  • Information
    Author
    Salvador Roura
    Language
    English
    Translator
    Salvador Roura
    Original language
    Catalan
    Other languages
    Catalan
    Official solutions
    C++
    User solutions
    C++