Trap
Time limit2sMemory limit512 MB
Count the self-avoiding walks of n unit grid steps that start at (0,0) going right and are trapped: no further step can be added without self-intersection.
- Level
Medium7 of 10
- Topics
- Backtracking, DFS, Simulation, Implementation
- Solved
- No attempts yet
Problem
We form a sequence of points that are vertices with integer coordinates in a square grid. Each two consecutive points of the sequence define a single horizontal or vertical segment of length one. We call this sequence a walk.
Consider such walks composed of n segments that are self-avoiding, that is, the segments in the walk do not intersect themselves and do not touch each other, except any two consecutive segments. We also want the first segment in the walk to join the points with coordinates (0,0) and (1,0), and the first vertical segment to be going up.
Write a program that computes the number of all self-avoiding walks on a square grid that are trapped after n steps, that is, walks that cannot be continued because adding the next (n + 1) segment will cause self-intersection.
Input
An integer n.
Output
An integer equal to the requested number.
Constraints
- 0 < n < 27
Hint
The two walks are (0,0) (1,0) (2,0) (2,1) (2,2) (1,2) (0,2) (0,1) (1,1) and (0,0) (1,0) (1,1) (2,1) (3,1) (3,0) (3, -1) (2, -1) (2,0), and they are depicted in the figures:
