Answers to: Labyrinth SPOJhttps://discuss.codechef.com/questions/46419/labyrinth-spoj<p><a href="http://www.spoj.com/problems/LABYR1/">www.spoj.com/problems/LABYR1/</a></p>
<p>I used the simple DFS technique but its showing TLE . Can any one give me some optimization techniques.
I already used Fast I/O</p>enMon, 27 Oct 2014 15:54:00 +0530Comment by topcoder_7 on codedog29's answerhttps://discuss.codechef.com/questions/46419/labyrinth-spoj#54218<p>Brother, you may use a different code : <a href="https://ideone.com/NmCcQY">https://ideone.com/NmCcQY</a></p>topcoder_7Mon, 27 Oct 2014 15:54:00 +0530https://discuss.codechef.com/questions/46419/labyrinth-spoj#54218Answer by topcoder_7https://discuss.codechef.com/questions/46419/labyrinth-spoj/54217<p>Brother, refer : <a href="http://ideone.com/ShQYJ3">http://ideone.com/ShQYJ3</a>
It's easy now, hope you got it.</p>topcoder_7Mon, 27 Oct 2014 15:53:17 +0530https://discuss.codechef.com/questions/46419/labyrinth-spoj/54217Answer by vippu95https://discuss.codechef.com/questions/46419/labyrinth-spoj/54211<p>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.</p>vippu95Mon, 27 Oct 2014 14:26:55 +0530https://discuss.codechef.com/questions/46419/labyrinth-spoj/54211Answer by codedog29https://discuss.codechef.com/questions/46419/labyrinth-spoj/54202<p>i'm getting a nzec.
please have a look at this
<a href="http://discuss.codechef.com/questions/54199/spoj-labyrinth-nzec">http://discuss.codechef.com/questions/54199/spoj-labyrinth-nzec</a></p>codedog29Mon, 27 Oct 2014 00:29:03 +0530https://discuss.codechef.com/questions/46419/labyrinth-spoj/54202Answer by kodooshttps://discuss.codechef.com/questions/46419/labyrinth-spoj/46446<p>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.</p>
<p>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.</p>kodoosFri, 04 Jul 2014 01:19:57 +0530https://discuss.codechef.com/questions/46419/labyrinth-spoj/46446