The traditional maze is 2-dimensional: the navigator can move in the positive or negative directions along two axes x and y. Now imagine, if you will, a 5-dimensional maze. As in the 2-dimensional case, the navigator may only move along one of these directions at any time, and some of the directions are blocked by walls. Your task is to find and give the shortest path through the given maze.
This problem is a generalization of Problem 283. If you haven't solved that yet, I would recommend solving it first.
- The maze will be represented by an [ M x N x O x P x Q ] matrix.
- Each element of the matrix represents a valid location in the maze and the value of each element is a binary-coded representation of the walls, positive directions in which you can not move. If a value reads 0, it means the navigator is permitted to move along any of the five dimensions in the positive direction.
- Walls are bi-directional: if a wall exists between two locations, you cannot traverse it in either direction. A skilled navigator must check the destination location's walls if she wishes to move in the negative direction along any dimension.
- The start position is at the origin: subscript (1,1,1,1,1).
- The end position is at the furthest extent: subscript (M,N,O,P,Q).
- The output should be a matrix of the same size as the input matrix that lists the steps you need to go through to traverse the maze with the remaining squares being 0. Refer to Problem 283 for a 2-D example.
- You are NOT guaranteed that there will be only one shortest path for the test cases. If there exist multiple shortest paths, you must represent them all. It can easily be shown that the superposition of two shortest paths will never lead to a multi-valued element in the output matrix.