I have to build a cycle with fixed length $n$ that includes exactly $k$ corners inside $w$ x $h$ rectangle.
$w = 5\\h=3$
$n = 12\\k = 6$
I have already found out that I need at least $4$ corners and number of corners and number of non-corner elements needs to be even number.
Then I write an recursive algorithm that runs in exponential time complexity, but I have a strong feeling that this thing can be done much faster.
Problem is that I do not know which square will definitely be in the cycle so I run my algorithm on first $\frac w2$ fields to cover all chances, but I am aware that I search some branches multiple time.
I have also discovered that if the cycle exist it will start with corner in (0, 0) or corner in (0, 1)
Does anybody have an idea on how to speed this thing up?
Have a nice day!