This can be done by backtracking....easily... With regards,
Praveen Raj DCE-IT 3rd yr 9999735993 [email protected] On Wed, Sep 28, 2011 at 11:30 PM, rashmi i <[email protected]> wrote: > > 1. Datacenter Cooling > > We have some rooms in our datacenter, and we need to connect them all with > a single cooling duct. > > Here are the rules: > > - The datacenter is represented by a 2D grid. > - Rooms we own are represented by a 0. > - Rooms we do not own are represented by a 1. > - The duct has to start at the air intake valve, which is represented > by a 2. > - The duct has to end at the air conditioner, which is represented by a > 3. > - The duct cannot go in multiple directions out of the intake or the AC > - they must be the two endpoints of the duct. > - The duct must pass through each room exactly once. > - The duct cannot pass through rooms we do not own. > - The duct can connect between rooms horizontally or vertically but not > diagonally. > > Here is an example datacenter: > > 2 0 0 0 > > 0 0 0 0 > > 0 0 3 1 > > > There are two possible ways to run the duct here: > > 2--0--0--0 > | > 0--0--0--0 > | > 0--0--3 1 > > or > > 2 0--0--0 > | | | > 0 0 0--0 > | | | > 0--0 3 1 > > Write a program to compute the number of possible ways to run the duct. For > the above example, the correct answer is 2. > Input format: > > Your program should read from stdin. The input will be a series of integers > separated by whitespace. > > The first two integers will be W and H, with width and height of the > datacenter. These will be followed by W*H more integers, specifying the 2D > grid representing the datacenter. > Output format: > > Your program should write a single integer out to stdout: the number of > possible ways to run the duct. > > See how fast you can make it. > > Our best solution (written in C) can solve the following test case in under > 5 seconds on a 2.4GHz Pentium 4, but it's pretty good if you can get to > within 1-2 orders of magnitude of that. > > 7 8 > 2 0 0 0 0 0 0 > 0 0 0 0 0 0 0 > 0 0 0 0 0 0 0 > 0 0 0 0 0 0 0 > 0 0 0 0 0 0 0 > 0 0 0 0 0 0 0 > 0 0 0 0 0 0 0 > 3 0 0 0 0 1 1 > > > > -- > R@$!-! > "DoN'T LimIt Ur cHaLlEngeS, ChAlLenGe uR LImItS." > > -- > You received this message because you are subscribed to the Google Groups > "Algorithm Geeks" group. > To post to this group, send email to [email protected]. > To unsubscribe from this group, send email to > [email protected]. > For more options, visit this group at > http://groups.google.com/group/algogeeks?hl=en. > -- You received this message because you are subscribed to the Google Groups "Algorithm Geeks" group. To post to this group, send email to [email protected]. To unsubscribe from this group, send email to [email protected]. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
