As far as I can see the problem has relatively small
percent of the difficulty, but I can't think of the way I
should walk the pattern by means of minimal number of
threads..

Is the problem only a DFS (and if it is how should it be
done) or there is something else?

Thank you.

You need some graph theory and common sense to solve it.
Basically after you do the logic the problem breaks down to
simple bfs/dfs and counting degrees. The idea comes from
the problem of decompossing graph to a minimum amount of
paths which is solved by some simple logic - you should be
able to prove it yourself.


Hint - it has something to do with Euler ...

Helpfull to have math invariant(which right for every algo)
I think that answer=Nc+Ndb/2
where Ndb- sum of disbalances of vertices of grid's graph.
and Nc- number of alternating loops which unreached from
disbalanced vertices by alternating pathes.
But can't go far then test 8.

AC 0.031 now.Idea is right. It taken 3 days to
convert idea in quick algo.

Edited by author 04.01.2009 10:13