# Labyrinth SPOJ

I used the simple DFS technique but its showing TLE . Can any one give me some optimization techniques.

hello Japoorv
I dont know the actual algorithm which should be used but i think this problem can be solved using this O(n) aproach.Here is my approach
-> process the given graph . if you have noticed then the problem explicitly says that the given graph which formed by considering only the free blocks is a tree.rightt??
-> form the given tree now use this variation of DFS to solve this problem .For each node,maintain the two maximum counts of children under this node so the maximum length that can be used including this will be count1+count2+1 right?? and pass max(count1+1,count2+1) to the parent of the current node .
for each node if you do this then it takes only O(n) to find the maximum distance between any two nodes.

if you still have some problem then let me know so that i can make it a bit more explanatory. So, think about this I will try this today and will let you know about the result here.

iβm getting a nzec.
please have a look at this
http://discuss.codechef.com/questions/54199/spoj-labyrinth-nzec

1 Like

What i used is Do BFS from any of the lattice point which have a β.β and find lattice point containing a β.β from this point.Then from the newly find lattice point do BFS again and maintain a distance array to count the maximum distance found from this newly find lattice point.The maximum distance will be the diameter or in this case the required answer.

Brother, refer : http://ideone.com/ShQYJ3
Itβs easy now, hope you got it.

3 Likes

Brother, you may use a different code : https://ideone.com/NmCcQY

1 Like