[Problem4 SPOJ:PT07Z and Problem5 SPOJ:LABYR1] More on mazes

PROBLEMS: http://www.spoj.com/problems/PT07Z and http://www.spoj.com/problems/LABYR1

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.


SOLUTIONS: https://github.com/glassrose/CPP_Problem_Solving/blob/master/SPOJ-PT07Z.cpp
and https://github.com/glassrose/CPP_Problem_Solving/blob/master/SPOJ-LABYR1.cpp

Tested here: http://www.spoj.com/status/PT07Z,chandniverma/
and http://www.spoj.com/status/LABYR1,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)