ID:190947
 
I went to the ACM South-Central USA Regional Programming Contest this year (and got my arse kicked royally). This one problem has been bothering me ever since then. Does anyone see a possible solution? Languages that we were allowed to use were C, C++, Java, and Delphi. Our group just uses Java....mainly because that is all that we are familiar with.

Problem: http://acm2002.csc.lsu.edu/problems/4.php
Looks like a problem for.... *cue heroic music* Graph Theory!

I can't think of a simple solution offhand, but you could always construct a graph structure and try an exhaustive search of all possible routes.

There's a famous related problem (about bridges somewhere) which involves making a cycle through all nodes in a graph and ending up where you started. A really simple method for finding this was eventually figured out (it has something to do with counting the number of paths into all node, and seeing if they're odd or even.. but again, I don't remember exactly what you do with that information). It's not exactly the problem here (the butler isn't making a full cycle.. he doesn't start in his room), but it's similar.

-AbyssDragon
In response to AbyssDragon
Yeah..I know its path-based, and I had an attempt to solving it, then I realized that you could have multiple doors (paths) between 2 rooms. That blew up my algorithm nicely.