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 [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
-~----------~----~----~----~------~----~------~--~---
