CareerCup

Use backtracking with a 3D solution matrix.
Terminating condition :
if(x == 0 || x == n-1 || y == 0 || y == n-1 || z== 0 || z== n-1)
At this pt. print the sol matrix and backtrack to find other possible paths.

Recursive solution.

Let f(n) be the function which does the job. That is, returns all paths from the centre of the cube to the surface. Then, f(n) can be constructed from f(n-2). If you have all paths returned by f(n-2), looks at each path. Look at the last vertex on the path. See which coordinate/s of the last vertex can be extended by one step to reach 0 or n. You can only change one coordinate in one step. Once any coordinate hits n OR 0, we are done. So, create more paths from the paths returned by f(n-2) in this way. Keep doing this till you reach the base case. which will be f(3) or f(2). Both of them are easy to solve.

Slight mistake. It's better to assume we are at the origin and that n = 2m or 2m+1. So end points will be m and -m, say. (for the odd case at least)

Then, f(n-2) returns path in which last vertices have one vertex at m-1 or -m+1.

Apply single-source shortest path from the center to all vertices. Then run through the edge vertices e.g. (x == 0 || x == n-1 || y == 0 || y == n-1 || z== 0 || z== n-1) and generate the sequence of path from that vertex to the center for all those vertices.

Use Dijkstra's algorithm with Min-Heap.

I hope this should solve the problem as I am touching all the vertices on the edge.

in Question itz mentioned like we need to go to surface not specifically to vertices....so y shld we go to vertices as shorter path is there from starting point to the surface of each face

Please write a question with proper punctuation marks. It requires to be read at least a couple of times to understand.

Posting for feedback on implementation.

final int MAX_SIZE = 10; // Can set to whatever you want.
final int cube[][][] = new int[MAX_SIZE][MAX_SIZE][MAX_SIZE];
void printPathToSurface(int x, int y, int z){ // input can be the center location
 printPaths(x, y, z, "");
}
void printPaths(int x, int y, int z, String prevPath){
 if(x < 0 || y < 0 || z < 0 || x >= (MAX_SIZE) || y >= (MAX_SIZE) || z >= (MAX_SIZE))
  return;
 if(x == 0 || x == (MAX_SIZE - 1) || y == 0 || y == (MAX_SIZE - 1) ||
    z == 0 || z== (MAX_SIZE - 1)){
  System.out.println(prevPath);
  return;
 String path = new String(prevPath);
 path += "(" + String.valueof(cube[x]) + "," + String.valueof(cube[y]) + "," +
                String.valueof(cube[z]) + ")"
 for(int i=x-1; i<=x+1;i++){
  for(int j=y-1; j<=y+1;j++){
   for(int k=z-1; k<=z+1;k++){
    printPaths(i, j, k, path);
   }
  }
 }
}

# The interpretation of the problem here is that you are at the
# center of a cube, and it's n units from the center to the surface,
# and you want to enumerate all paths that go to a point on the surface
# without reversing direction in any dimension.  Diagonal moves
# aren't allowed; every step in the path is magnitude 1 and 
# parallel to one of the three axes.  Paths are allowed to continue
# along the surface, as long as you don't reverse directions.

directions = dict(
    L = ('x', -1),
    R = ('x', 1),
    D = ('y', -1),
    U = ('y', 1),
    B = ('z', -1),
    F = ('z', 1),
)
    
def generate_paths(n):
    def gen_paths(path, coords):
        if any(abs(coord) > n for coord in coords.values()):
            return
        if any(abs(coord) == n for coord in coords.values()):
            yield path
        for direction, delta_info in directions.items():
            axis, delta = delta_info
            # make sure we don't backtrack, take advantage
            # that product of two negative numbers is positive
            if delta * coords.get(axis, 0) >= 0:
                new_path = path + direction
                new_coords = coords.copy()
                new_coords[axis] = new_coords.get(axis, 0) + 1
                for newer_path in gen_paths(new_path, new_coords):
                    yield newer_path

    return gen_paths('', {})            

def run():
    for n in [1,2,3,4]:
        solutions = generate_paths(n)
        num_solutions = sum(1 for solution in solutions)
        print 'n=%d: %d solutions' % (n, num_solutions)

run()

n=1: 78 solutions
n=2: 1878 solutions
n=3: 39222 solutions
n=4: 837846 solutions