Firstly I had hypothesis that snake in optimal solution
has one circle and comes back having  maximum two  possible
visitings of some positions by it's head.
And It is right. Ac at last. This problem is on searching simple circles in graph. But not in all grid but on BFS created points only.

After I added program for bicomponents and began to skip edges during dfs searching  which have no another edges in the same component. This shorten time from 0.9c to 0.3 c.

After that I added demand that first edge in first call
of dfs must be procecced only once.It allowed me to
get Ac 0.093 An to take 1 place in problem raiting.

Edited by author 07.01.2009 12:59