Thursday, August 27, 2009

11474 - Dying Tree - UVA

graph search algorithm - DFS( Depth-First Search )

The problem wants to know whether there is a tree to call a doctor to save the sick tree or not?
This tree can also be the sick tree.
I first construct an adjacency matrix from the trees,( excluding doctors ), HOW? Two trees can talk to each other if the minimum distance between them is less than or equal to k. Then I run DFS from node 1, in the DFS function I check whether there is a doctor to whom the current tree in the DFS function can communicate? HOW? An ordinary tree can communicate to a doctor if the minimum distance between them is less than or equal to d. I have a global boolean variable for checking the answer. If in DFS function I find a connection between a tree and a doctor I set it to true and return, otherwise I continue searching from the adjacent trees to the current tree( adjacency matrix ).

No comments:

Post a Comment