DWITE Online Computer Programming Contest

Pattern Lock

February 2013
Problem 5

A lot of phones nowadays are moving away from the standard number lock to using pattern locks. Given a 3-by-3 grid of dots, a pattern is defined to be a directed path among the 9 points of length at least 1. (Note: A path visits each point at most once.) However, there’s an extra condition: The path can’t cross an unvisited vertex (e.g. you can’t go from the top-left dot to the bottom-right dot unless the center dot has already been visited). For example, the following picture depicts one possible pattern for a 3-by-3 grid:

One day you decide to find out exactly how secure this lock is by determining the number of possible patterns you can make for a 3-by-3 grid of up to a particular length.

The input file DATA5.txt will contain 5 test cases. The first line of each test case contains a number N (1 ≤ N ≤ 8) representing the maximum length the pattern can be.

The output file OUT5.txt will contain 5 lines. Each line is an integer representing the total possible number of patterns you can have for the 3-by-3 grid lock, up to the length given by the input.

Sample Input (only two test cases shown):
1
2
Sample Output (only two shown):
56
376