Link to pdf version on UVa OJ
What happened on my mind : There are two ways to think about this. First, when a node is adjacent to 3 nodes it will wake up. Second, when does a node can "help" wake up another node? When it is awake. Thinking in the second way helped me think about Queue data structure. As soon as a node is awaken it is added to a queue, when it is popped from a queue it "helps" adjacent slept nodes (increases their awakeNeighborCount by one). When some nodes awakeNeighborCount becomes 3 it is awaken, so it is added to the queue. I don't know what to call this algorithm :D maybe BFS, maybe Bellman-Ford, why Bellman-Ford? Because at each iteration, those nodes that has gotten awaken, help other nodes.
Again I used multiple functions to solve the problem.
Take a look at my solve() function for more details.
My code on github.
What happened on my mind : There are two ways to think about this. First, when a node is adjacent to 3 nodes it will wake up. Second, when does a node can "help" wake up another node? When it is awake. Thinking in the second way helped me think about Queue data structure. As soon as a node is awaken it is added to a queue, when it is popped from a queue it "helps" adjacent slept nodes (increases their awakeNeighborCount by one). When some nodes awakeNeighborCount becomes 3 it is awaken, so it is added to the queue. I don't know what to call this algorithm :D maybe BFS, maybe Bellman-Ford, why Bellman-Ford? Because at each iteration, those nodes that has gotten awaken, help other nodes.
Again I used multiple functions to solve the problem.
Take a look at my solve() function for more details.
My code on github.
No comments:
Post a Comment