Coding Recipies: Maze with Key

20 Oct 2013

Maze with Key

Problem Statement:

Help Jerry Walk through the maze from top left to bottom right , collecting the key on the way.
The path from source to destination should not pass through any cell not more than once. Jerry can move in the following directions:

1. Left
2. Right
3. Up
4. Down
5. North East
6. North West
7. South West
8 . South East

Matrix Representation:

'0' represent a wall in the matrix.
'1' in the matrix represent path.
'2' represents the lying key in the matrix.

Now lets us consider a 8 x 8 matrix , in which Jerry has to pick the key to open the door of the maze.

Solution Matrix containing the path:

Fig: Solution Matrix Containing the path

Solution :

I had discussed a similar problem in my precious post. In this maze the the mouse has to collect the key to open the final door of the maze. This problem is clearly of backtracking. I will discuss the solution for moving in one direction , for the other 7 remaining it will be similar.

Refer to full Source Code

Concept:

Supposing that the mouse choose to move in the North East direction

//Move NE
if (row > 0 && col < size )  // check if cell is within the matrix
{
    if (maze[row - 1][col + 1] == 1 || maze[row - 1][col + 1] == 2) //Enter if path exists
    {
        if(solution[row - 1][col + 1] != 1){ // Check if same cell is being revisited twice
            
            if(maze[row - 1][col + 1] == 2){ //Key Found
                isKeyFound=true;
            }
            
            solution[row][col] = 1;             // Mark the current cell as point in the solution
            solveMaze(maze, solution, row - 1, col + 1); // Move North East
            solution[row][col] = 0;             // Backtracking , reverting the path
            
            if(maze[row - 1][col + 1] == 2){   // discarding the key as this is not a valid path
                isKeyFound=false;
            }
        }
    }
}

I have mention the necessary comments at each line of code.

Now the exit condition.

          // exit gate reached
  if (row == size && col == size) {
   if(isKeyFound){
    solution[row][col] = 1;
    System.out.println("Path Marix is :");
    printSolution(solution);
    System.out.println("===============================");
   }
  }

When the bottom rightmost cell is encountered , we check if key is found then print the solution and return true to the calling function as solution exists.
In the above code the number of 'if's and 'else's can be reduced but to keep the code modular i have made logic of each direction independent of others. The above problem can be again solved by DFS traversal using stack , so I would encourage you to try that yourself.

Also, readers read A* algorithm after reading this post in order to develop approach to solve more problems of this type.

In case you have any queries or suggestions , please post comments or inbox me.

Happy Coding !! :)