A journey in 3D
All submissions for this problem are available.
Master Yoda is teaching a young Padawan learner, an IIT Kanpur student, the knowledge and powers of a Jedi. During his training, one of the tasks he has to accomplish is to fly a starship across a 3D maze created by Master Yoda for his training. The maze is filled with virtual droids of the Empire’s Army at certain cells. The student has to fly the starship across the maze such that at no time the starship is in the same cell with any of the droids, otherwise he will fail the test and will be kicked out of the Jedi Training Camp.
Description of the maze:
The Maze is a 3-D grid of size (N+2) x C x D. It is a vertical stack of D layers where each layer is a 2-D grid containing N+2 rows and C columns. The first (index 0) and the last (index N+1) rows of each layer are filled with ‘O’ (open positions in the Maze), except that one cell in the first row of some layer will be marked ‘S’, the starting position of the student and his starship, and one cell in the last row of some layer will be marked with ‘D’, his destination. Every other cell in this grid will either contain an enemy droid marked with ‘X’ or an empty space marked with ‘O’.
The starship has an intelligent R2D2 robot installed which guides the student in flying the starship and deciding his path. The configuration of the grid is stored in the memory of R2D2. It is well known that Master Yoda is a very strict teacher when it comes to Jedi training. He has already computed the minimum number of moves it will take the student to fly from the starting point and reach the destination already feeded in R2D2.
Master Yoda realised that if the drones in the maze are kept static, it is too easy for R2D2 to plan a path. Thus, Yoda decides to use his Jedi powers to set the Maze in motion, moving certain rows and columns of all the layers, to add some difficulty to the task. But he won’t move the first and the last rows of any layer (which keeps ‘S’ and ‘D’ positions static), since that will be too much for a young Padawan learner, only the masters practice in such a grid.
As soon as the Young Padawan Learner (IITK student) starts the flight, Yoda sets the maze in motion. In each layer, the rows with indices 0 and N+1 remain stationary.
For the first layer (the bottom-most layer which is index 0), the row with index 1 is moved towards the right 1 cell at a time (i.e. one cell to the right in each move). The row with index 2 moves to the left, row with index 3 to the right and so on. For the rest of the layers, each row (except rows with indices 0 and N+1) move in the direction opposite to that of the row just below. All the rows move one cell at a time (i.e. one cell in each move). The row motion is modular i.e. whatever position (‘X’ or ‘O’) leaves the corner of the maze on any side, comes back in the same row, the same layer on the other side.
Description of the motion for the starship:
At all times, the starship must remain in the 3-D Maze of dimensions (N+2) x C x D.
In each move, the starship may stay in its current cell or may move to the cell just adjacent to it, i.e. the starship may move one cell either to its right, or to its left in the same row, or one cell up or down in its column, or one cell up to the layer stacked above it or one cell down to the layer underneath keeping the row and columns indices the same. The motion of the starship isn’t modular unlike that of the rows. Although, the starship can’t share a cell with any droid at all times, it may jump over an approaching droid in the same row. It means if a droid is in the neighbouring cell of the starship, in the next move, both of them can exchange their positions without the student failing.
The first line of the input contains an integer M denoting the maximum number of moves allowed.
The next line contains three space separated integers N C and D denoting the dimensions of the Maze.
The next N+2 lines contain C characters denoting the layer 0 of the Maze
The next N+2 lines contain C characters denoting the layer 1 of the Maze
The next N+2 lines contain C characters denoting the layer D-1 of the Maze
Output an integer denoting the minimum number of moves needed to reach the destination. If it is not possible to reach the destination in less than equal to M moves then output -1
- 1 ≤ M ≤ 4000
- 1 ≤ N ≤ 100
- 1 ≤ C ≤ 100
- 1 ≤ D ≤ 10
Input: 20 2 3 1 OOS OOO XXO OOD Output: 5
|Time Limit:||0.1 sec|
|Source Limit:||50000 Bytes|
|Languages:||C, JAVA, GO|
Fetching successful submissions