You are not logged in. Please login at to post your questions!


Labyrinth SPOJ

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

japoorv's gravatar image

accept rate: 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

kodoos's gravatar image

accept rate: 0%

i'm getting a nzec. please have a look at this


answered 27 Oct '14, 00:29

codedog29's gravatar image

accept rate: 0%


Brother, you may use a different code :

(27 Oct '14, 15:54) topcoder_72★

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

vippu95's gravatar image

accept rate: 50%

Brother, refer : It's easy now, hope you got it.


answered 27 Oct '14, 15:53

topcoder_7's gravatar image

accept rate: 9%

toggle preview

Follow this question

By Email:

Once you sign in you will be able to subscribe for any updates here



Answers and Comments

Markdown Basics

  • *italic* or _italic_
  • **bold** or __bold__
  • link:[text]( "title")
  • 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:


question asked: 03 Jul '14, 20:50

question was seen: 3,612 times

last updated: 27 Oct '14, 15:54