I'm fairly certain that for an unweighted directed graph, BFS is the most effective way to find the shortest path between two points when the point distribution is random enough to prevent heuristics from being applied.
I know what you meant by saying this, but i find it funny that the way you worded that, you'd do that and then leave us with unremovable /e/njoyment.
I wasn't the one who chose the BITMAP test as the coding test to join the Empires team. But, this is what I think: The purpose of the BITMAP test is not just to test programming skill. It's to make sure that a coder is willing to put in the time and effort to solve a difficult problem, even if they don't have any idea how to solve it. Personally, it took me over 70 attempts to solve the BITMAP problem. But I persevered and worked through it. The Empires code isn't something that can be dived into without effort. It's massive and complicated, and it will take time to learn and discover how the game is programmed. The test serves as a sort of filter to make sure a coder is really willing to put in the time to learn the codebase.
Also, to solve BITMAP, you must submit the problem and have it show up as green in the test result. A source code solution is not enough - it has to run within the time and memory limits.
I could see a generic breadth-first search taking too long, but I bet it can be optimized by knowing that it takes the shape of a rectangular grid. EDIT: Turns out a normal breadth-first algorithm does work just fine, I don't know what anyone else is saying now. I actually got it right on the first submission with the queue-based search, the rest were assorted ways of trying with arrays. That really was a fun challenge. I should do more of them. I actually learned a lot about searching algorithms, graph theory and all sorts of things about templates from doing it.
sorry to break the bad news to you candles but by solving the problem you signed a pact with the devil and are now part of the development team. this is not negotiable, now go work and make it awesome. also its empires, ofc you use a stack to solve :D
Thats funny according to the site only your last one was good the rest had wrong answers or was too slow. Problems solved: 1 Solutions submitted: 14 Solutions accepted: 1 Wrong Answer: 6 Compile Error: 0 Runtime Error: 0 Time Limit Exceeded: 7 I love the limits though... Source limit:50,000B Memory limit:256MB <-- Anyone who uses this much memory should not be programming. In fact I challenge you to use up close to this much memory in this test(forgetting the time limit) without using it for no reason.
Viroman, the memory limit appears to be set by the cluster being used to solve the solution and not by the program setter. http://www.spoj.com/clusters/
Just message with a username and password you want for the git and svn and I'll give you access to everything candles.
This must be one of the only threads on here, that after going slightly offtopic within 6 pages its back on an almost identical track to how it started. Im amazed. *Insert witty meme here*