On Sunday, April 17, 2016 at 11:14:52 AM UTC+5:30, Wing-chung Leung wrote: > Good question? Can you explain the DFS algorithm? Anyway I have one answer > myself. > > 1. Construct of priority queue of heights and location of the blocks. Only > the height is compared to locate the mininum items. > > 2. Add everything on the sides, except the corner, into the priority queue. > > 3. If current height is less than the min-height of the queue, set the > current height to be the min-height. (Note that the items form a bounded > area, and everything inside that area will be filled to at least that height.) > > 4. Pop an item from the min-queue. > > 5. If the height of the popped item is less than the current height, add the > difference to the volume of water filled. > > 6. If any/all of the neighbours of the popped item was not ever added into > the queue, add each of them to the queue. > > 7. Repeat steps 3-6 until the queue is empty. > (Note: by popping the lowest tiles, and adding their neighbours, it may form > a smaller bounded area with a higher height.) > > 8. The total differences added in step 5 is the answer. > > Complexity: unknown, but likely O(log (m*n) * m*n) for the worst case to > O(m*n) for the best case. The log(m*n) is multiplied due to the use of a > priority queue. > > On Tuesday, April 5, 2016 at 2:24:58 AM UTC+8, edston wrote: > > Haha > > > > > > This is a very old thread. :D > > > > > > Anyways answer is to do DFS > > Time: O(n*m) > > > > > > Best > > Vivek > >
what values will be present in the min-queue? -- You received this message because you are subscribed to the Google Groups "Google Code Jam" group. To unsubscribe from this group and stop receiving emails from it, send an email to [email protected]. To post to this group, send email to [email protected]. To view this discussion on the web visit https://groups.google.com/d/msgid/google-code/618155b8-ad3b-4bc8-a271-382f92cf7c30%40googlegroups.com. For more options, visit https://groups.google.com/d/optout.
