Thank you very much Shalin and Wade. Your ideas are really nice. I will
give them a try and give u feedback.
wade, the timelimit was 10 seconds, my solution took 10.025 seconds.
shalinmangar wrote:
> The low input size constraints (max size of the graph is 40*40) suggest
> that a brute force DFS to find the connected components may work fine.
>
> Each square (x,y) is a node with edges to each reachable square {
> {x+1,y), {x,y+1], {x-1,y}, {x,y-1} }. Maintain a boolean matrix to keep
> track of visited nodes. Do a DFS from each node not visited yet and
> find out the size of the connected component. While doing the DFS
> maintain the minimum and maximum heights visited. After the DFS
> finishes, if the number of nodes visited >= k then update the (max -
> min) value found so far to find the necessary. After all the nodes have
> been visited, the (max-min) value gives the answer.
>
> Regards,
> Shalin.
--~--~---------~--~----~------------~-------~--~----~
You received this message because you are subscribed to the Google Groups
"Algorithm Geeks" group.
To post to this group, send email to algogeeks@googlegroups.com
To unsubscribe from this group, send email to [EMAIL PROTECTED]
For more options, visit this group at http://groups.google.com/group/algogeeks
-~----------~----~----~----~------~----~------~--~---
