|
|
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 Something strange with test 12. A lot of people get WA here. I don't find error in my solution and but still get WA. Can anyone help me with test cases. You can submit your tricky test to [Ilya point Grebnov@mail.ru]. Test 12 is wrong! In problem: "Even though the maze is a practice one, no snake of length 18 can get out from it alive". But in Test 12 it is possible and may be in others.
For passing Test 12 you must ignore all circles with len >=18.
|
|
|
