Ant in a Hexagonal Web
Time limit1sMemory limit1024 MB
On an infinite hexagonal web, count the ant walks that make exactly N turns before first revisiting a vertex, where the first step is fixed north.
- Level
Medium7 of 10
- Topics
- DFS, Backtracking, Combinatorics, Simulation
- Solved
- No attempts yet
Problem
There is an ant web made of infinitely many regular hexagons tiled so that they touch each other. It has the shape shown below, and the ant can walk only along the white edges.
The ant web.
Yui, whose hobby is observing insects, placed one ant on a point where three regular hexagons meet. The ant placed on the web began exploring the web, which is unknown territory to it, while spraying pheromone. At first the ant starts moving toward one of the three edges connected to the point; for convenience, we rotate the view so that this first move points north.
If the ant arrives at a point where three edges branch off, it chooses one of the two edges other than the one it came from and turns in that direction to continue exploring.
Light green is the starting point, green is the path along which the ant sprayed pheromone while exploring. Black is the ant, orange shows the two edges it can choose for the next move.
When the ant arrives at a point it has visited before, that is, a point where pheromone has been sprayed, it falls under the illusion that this area is already familiar and stops exploring. Find the number of cases in which, when the ant stops exploring this way, the number of times it turned is exactly N.
Two paths that turn 7 times. Even if the pheromone trail is the same, paths are distinguished by the ant's direction of movement.
Input
The first line gives a single integer N (1 ≤ N ≤ 22).
Output
On the first line, print the number of cases in which the ant turns N times and then stops.