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

×

Labyrinth SPOJ

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

japoorv's gravatar image

5★japoorv
29592356
accept rate: 0%


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

link

answered 27 Oct '14, 15:53

topcoder_7's gravatar image

2★topcoder_7
2.9k3153
accept rate: 9%

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.

link

answered 27 Oct '14, 14:26

vippu95's gravatar image

6★vippu95
117139
accept rate: 50%

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

link

answered 27 Oct '14, 00:29

codedog29's gravatar image

3★codedog29
556
accept rate: 0%

1

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

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

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.

link

answered 04 Jul '14, 01:19

kodoos's gravatar image

4★kodoos
11
accept rate: 0%

toggle preview
Preview

Follow this question

By Email:

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

By RSS:

Answers

Answers and Comments

Markdown Basics

  • *italic* or _italic_
  • **bold** or __bold__
  • link:[text](http://url.com/ "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:

×18

question asked: 03 Jul '14, 20:50

question was seen: 3,581 times

last updated: 27 Oct '14, 15:54