INDER INDER - 1 year ago 226
C++ Question

3d Maze Programming

This is a question from TCS codevita Round 1 which was held in July.I was trying to solve this.

I don't need the entire code or logic. Just need some hint to get me started on the problem.What method should I apply on this problem.


Suppose, an ant is trapped in a maze, with only one way in and one way out.
The maze is a cubic­lattice like structure of dimension NxNxN (Length=Breadth=Height=N). The way in is the left­bottom most point, and the way out is the
right top­most point (along the principal diagonal). The below picture shows the maze for N=2.

enter image description here

Assuming the ant only moves right, forward or upwards along the grids of the maze, calculate the total number of ways in which the ant can
escape. Mathematically right, forward and upwards are defined at positive changes in co­ordinates on x, y and z axes respectively.

For, N=1, the grid structure and solution is shown below:

enter image description here

Thus, for N=1, we have a net of 6 ways.
Input Format:
Single integer N

Output Format:
Output also consists of a single number corresponding to the number of ways the ant can escape the maze.


  • 0<N<=8

enter image description here

Answer Source

To get out the ant needs to make N moves right, N moves up, and N moves forward.

Since no paths are blocked, these moves can be made in any order without restriction.

Every different ordering of R, U, and F moves is a different path, so the answer is the number of distinct strings consisting of N Rs, Us, and Fs.

That can be simply calculated as (3N)! / (N!)^3.

... where ! is factorial, not Boolean negation, and ^ is exponential, not XOR :)