×

# Labyrinth SPOJ

 0 www.spoj.com/problems/LABYR1/ I used the simple DFS technique but its showing TLE . Can any one give me some optimization techniques. I already used Fast I/O asked 03 Jul '14, 20:50 5★japoorv 295●9●23●56 accept rate: 0%

 2 Brother, refer : http://ideone.com/ShQYJ3 It's easy now, hope you got it. answered 27 Oct '14, 15:53 2.9k●31●53 accept rate: 9%
 0 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. answered 04 Jul '14, 01:19 4★kodoos 1●1 accept rate: 0%
 0 i'm getting a nzec. please have a look at this http://discuss.codechef.com/questions/54199/spoj-labyrinth-nzec answered 27 Oct '14, 00:29 55●6 accept rate: 0% 1 Brother, you may use a different code : https://ideone.com/NmCcQY (27 Oct '14, 15:54)
 0 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. answered 27 Oct '14, 14:26 6★vippu95 117●1●3●9 accept rate: 50%
 toggle preview community wiki:
Preview

By Email:

Markdown Basics

• *italic* or _italic_
• **bold** or __bold__
• image?![alt text](/path/img.jpg "title")
• numbered list: 1. Foo 2. Bar
• to add a line break simply add two spaces to where you would like the new line to be.
• basic HTML tags are also supported
• mathemetical formulas in Latex between \$ symbol

Question tags:

×18

question asked: 03 Jul '14, 20:50

question was seen: 3,560 times

last updated: 27 Oct '14, 15:54