Firstly, that question is missing a lot of details.
In absence of those details I'm going to make soem assumptions:
1. cube is odd lengthed, so that we can define a unique center of cube.
2. While traversing from a cell(x, y, z) we can only move into any of the 6
adjacent cells[x(+-)1, y(+-)1, z(+-)1] or you can assume all 8 neighbours
also, accordingly change your function to get neighbours.
3. Traversing Paths to surface would be done in a manner such that you
cannot revisit a cell, else there can be infinite many possibilities.
Since there will be exponential no. of such paths so enumerating them will
take exponential amount of time.
Simple recursive implementation could go something like this:
Algorithm(x, y, z, Path, Visited): // 'Path' is a list of cells visited
till now starting from the center cell. 'Visited' is a boolean NxNxN array.
or, you can choose to drop the 'Visited' array and implement
IsAlreadyVisited(x, y, z) function by searching in teh list 'Path'.
If current cell(x, y, z) is a surface cell.
Report a Path found and output the 'Path'.
return;
else for each of the 6 neighbours (unvisited): //(x' y' z') is an
unvisited neighbour of (x, y, z)
Path.append(x', y', z')
Visited(x', y', z') = true;
Algorithm(x', y', z', Path, Visited)
Depth of recursion is O(N^3).
You can use the symmetry argument here and only count the paths ending on a
particular surface (say- Top surface) rest of the paths can be calculated
by mirroring them onto other surfaces easily, but this will not cut down
the asymptotic complexity of the solution. In fact paths ending on a
particular face will also exhibit symmetry.
On 27 October 2012 10:11, payal gupta <gpt.pa...@gmail.com> wrote:
>
> Sorry ,posted the wrong question initially actually i needed the algo for
> this question. Thanx.
>
>
> On Saturday, October 27, 2012 7:04:10 AM UTC+5:30, raghavan wrote:
>
>> By any chance did you read the new blog post by Gayle Laakmaan..
>>
>> I guess to detect typos we can use some sort of Trie implementation..
>>
>>
>> On Fri, Oct 26, 2012 at 7:50 PM, payal gupta <gpt....@gmail.com> wrote:
>>
>>>
>>> Given a cube with sides length n, write code to print all possible
>>> paths from the center to the surface.
>>> Thanx in advance.
>>>
>>>
>>> Regards,
>>> PAYAL GUPTA,
>>> NIT-B.
>>>
>>>
>>>
>>> --
>>> You received this message because you are subscribed to the Google
>>> Groups "Algorithm Geeks" group.
>>> To view this discussion on the web visit https://groups.google.com/d/**
>>> msg/algogeeks/-/ZaItRf_9A_IJ<https://groups.google.com/d/msg/algogeeks/-/ZaItRf_9A_IJ>
>>> .
>>>
>>> To post to this group, send email to algo...@googlegroups.com.
>>> To unsubscribe from this group, send email to algogeeks+...@**
>>> googlegroups.com.
>>>
>>> For more options, visit this group at http://groups.google.com/**
>>> group/algogeeks?hl=en <http://groups.google.com/group/algogeeks?hl=en>.
>>>
>>
>>
>>
>> --
>> Thanks and Regards,
>> Raghavan KL
>>
>>
>> --
> You received this message because you are subscribed to the Google Groups
> "Algorithm Geeks" group.
> To view this discussion on the web visit
> https://groups.google.com/d/msg/algogeeks/-/vVmz5r1gpIYJ.
>
> To post to this group, send email to algogeeks@googlegroups.com.
> To unsubscribe from this group, send email to
> algogeeks+unsubscr...@googlegroups.com.
> For more options, visit this group at
> http://groups.google.com/group/algogeeks?hl=en.
>
--
You received this message because you are subscribed to the Google Groups
"Algorithm Geeks" group.
To post to this group, send email to algogeeks@googlegroups.com.
To unsubscribe from this group, send email to
algogeeks+unsubscr...@googlegroups.com.
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
