First, running BFS multiple times is an overkill. You can run it once having an artificial node that connects all the sources with edges of 0 weight. Or even better run a Flood Fill with the source cells set to 0. Next, if I understood you correctly, you just greedily select a cell with maximum value and put a new delivery office there. This doesn't work if there are two peaks that you need to cover with one delivery center in between.
PS My solution is not accepted either. On Mon, Mar 25, 2019 at 10:22 AM mukesh tiwari <[email protected]> wrote: > Hi Everyone, > My idea for this problem is run multiple source BFS from delivery node. > Final value of this resulting bfs run would be minimum value at each cell, > say Ret. > After this, I find the cell which has height value and establish a > delivery cell and run the bfs again from this cell, TRun. I compute again > the minimum from Ret and TRun, and maximum of these minimums are my answer. > > Explanation for first test case. > > 101 > 000 > 101 > From first source : > 012 > 123 > 234 > > From second source : > 210 > 321 > 432 > > From third source : > 234 > 123 > 012 > > from fourth source : > 432 > 321 > 210 > > minimum of all these Ret: > 010 > 121 > 010 > > Now I see the Ret has max value of 2 at (2, 2), so run bfs again from > (2, 2) and compute TRun > 212 > 101 > 212 > > Minimum of Ret and TRun > 010 > 101 > 010 > > And maximum value in minimum of Ret and TRun is 1 which is my answer. Any > idea or hint that what is wrong with my thinking would be very helpful. You > can also have a look at my code [1][2] > > [1] https://repl.it/repls/MutedMagentaOpen64 > [2] https://gist.github.com/mukeshtiwari/b4db6fc8af8aefd9895352fcbfd00908 > > Best, > Mukesh > > > > > > -- > 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/42349390-6ce9-4b2f-9cf6-fdc81dc33c84%40googlegroups.com > . > For more options, visit https://groups.google.com/d/optout. > -- 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/CADpTfwPs%2BeZ_%3DJwdzbYZDKYmEM14MMuwMDNj1JYyHht59TWroA%40mail.gmail.com. For more options, visit https://groups.google.com/d/optout.
