Last Updated: 28 Dec, 2020
Meliodas and Elizabeth
Moderate
Asked in company
There is a N * N maze in Liones guarded by the demons. Goddess Elizabeth is being trapped by the demons. She is kept at the center of the maze. Prince Meliodas is worried and he wants to save Elizabeth at any cost. He killed all the demons guarding the maze. Only the four corners of the maze are open for Meliodas to enter. The magical spell of the demons guarded the maze is still in effect. Thus, there is a limitation on the movement of Meliodas. At any cell of the maze, he can move exactly X steps in only four directions, i.e. Up, Down, Left, and Right where X is the power of each cell of the maze.
Given an N * N maze of non negative integers, where each integer denotes the power of that cell. You have to find the number of ways in which Meliodas can save goddess Elizabeth.
For example:
An input maze is shown below
Elizabeth is trapped in the green cell and Meliodas can enter the maze from any of the yellow cells.
Input format:
The first line of input contains an integer ‘T’ denoting the number of test cases.
The first line of each test case contains an integer ‘N’ denoting the size of the matrix.
For the next N lines, each line contains N space-separated integers, denoting the power of the cells of the maze.
Output format:
For each test case, print a single containing a single integer denoting the total paths in which Meliodas can save Elizabeth. In other words, print the total number of valid paths from the corner cells to the middle cell of the maze.
The output of each test case is printed in a separate line.
Note:
You are not required to print the output explicitly, it has already been taken care of. Just implement the function and return the answer.
The maze will contain an odd number of rows and columns, i.e ‘N’ will always be odd.
Constraints :
1 <= T <= 5
3 <= N <= 9
0 <= DATA <= 10
where ‘T’ is the number of test cases, ‘N’ is the dimension of the maze and ‘data’ is the power of each cell of the maze.
Time limit: 1 sec.
Approaches
The idea is very simple. We will check from each corner cell and recursively check if it leads to the solution or not. If yes, we will increment our number of paths by 1 else we will backtrack.
Algorithm:
Initialise an integer variable ‘totalPaths’ by 0.
For each corner, we will call a recursive function called countPathsHelper.
Algorithm for countPathsHelper:
- If we have reached the destination, simply increment the ‘totalPaths’ and return.
- Else:
- If the current cell is already visited, return.
- Mark the current cell as visited.
- Move in all 4 possible directions and recursively check if anyone leads to the destination or not.
- Mark the cell as not visited, this is the backtracking step.
- Return the answer stored in ‘totalPaths’.
How to mark the cells visited?
Method 1: Using extra space
- Use a HashMap of pairs. A pair will be formed by the x and y indices of the cell. To mark a cell visited, insert the pair formed by the cell indices to the HashMap. To unmark the cell, just remove the pair from the HashMap.
- Use a 2-D boolean matrix. To mark a cell visited, set ‘true’ for that cell in the boolean matrix. To unmark a cell, set ‘false’ for that cell in the boolean matrix.
Method 2: Without using extra space
Note that we can move from a cell, if its value is greater than 0. If its value is 0 or less than zero, we will simply return as we can’t move anywhere from this cell.
Firstly, store the value of the cell in a temporary variable.
To mark a cell visited, we can just set its value as 0 or -1. To unmark a cell, we will restore its value stored in the temporary variable.
This is a space-efficient method to mark a cell visited or unvisited.