|
|
вернуться в форум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 |
|
|