I set out to solve LABYR1 last early this week and found that PT07Z would act as a good precursory problem so solved that first.
There are a lot of forests on this way <= Does that ring a bell as to which road we should take?
Well, coming to the hints and note taking part...
I came across this article [ https://cptalks.quora.com/Diameter-of-a-Tree ] which claims to be an optimization I am yet to analyse.
A classic textbook lemma exists for such problems which I applied here. I used DFS twice.
Tested here: http://www.spoj.com/status/PT07Z,chandniverma/
Complexities in the worst case:
For Problem 4: Time is O(N) where N is the no. of nodes in the tree.
Space needed is O(N) where N= no. of nodes in the tree.
For Problem 5: Time for each test case is O(R*C) where R and C=no. of rows and columns in the labyrinth respectively.
Space needed is O(R*C)