While the Big Jarab was preparing the tasks for admission in the quest for the Sacred Ino, Talb found a shorter way. He is sure that the building in which the Sacred Ino is kept has a back door, and he also knows that he only has to pass through N distinct cities to get there from his initial position.
We can model Talb's world as an infinite grid, where each square represents a city and he can get from any city to the cities situated to the East, West, North or South of his current location. After he starts his journey, Talb will only pass through a neighbouring city if he hasn't passed through it before.
Now, Talb is wondering how many different ways there are to make such journeys. If we can perform a translation operation over a path (to either of the four possible directions) and get another possible path for the journey, then the paths will only be counted once. In other words, the paths: North, North, North and South, South, South are the same, as we can overlap the two paths performing a translation (either the first path to the south, either the second one to the north).
Input
N, the number of cities.
Output
The number of distinct possible paths.
Constraints
- 1 ≤ N ≤ 13
Sample
| Input | Output | Explanation |
|---|---|---|
| 2 | 2 | The only two possible paths from the initial position are: North and East. Other paths are translations of these. |
| 3 | 6 | The six paths are in shape of: a vertical bar, an horizontal line, and the four possible rotations of a L-shape, all made of three cubes. |
Solution by Gabriel-Robert Inelus
In order to solve the problem we must imagine that we are in the middle of an infinite grid at coordinates (0, 0). Hence, at any step we can move from the current position (i, j) to:
- (i+1, j)
- (i-1, j)
- (i, j+1)
- (i, j-1)
Thus, we will use a backtracking algorithm which generates all these solutions; however, there will be repetitions which must be taken care of.
The actual problem is to find a method to determine whether or not two paths have the same "shape" given that we are allowed to apply some translation operations to them.
The key idea is that we can find an extreme point on the border of the shapes. A good choice can be to find the element (x, y) of a path, which has the smallest x coordinate and, in case of equality, the smallest y coordinate. Then, we normalize the shape by translating it (originally centered at (x, y)) to (0, 0) by subtracting (x, y) (by components) from all the elements of the current path. After this, we will be left with a normalized path which can be stored in a hash map (for instance, we can use STL map to store some vectors, or unordered_map to store some strings).
The result is the size of the hash map.
