mazeSolver.cpp

 /**
 A Maze is given as N*N binary matrix of blocks where source block is the upper left most block i.e., maze[0][0] and destination block is lower rightmost block i.e., maze[N-1][N-1]. A rat starts from source and has to reach destination. The rat can move only in two directions: forward and down.
In the maze matrix, 0 means the block is dead end and 1 means the block can be used in the path from source to destination. Note that this is a simple version of the typical Maze problem. For example, a more complex version can be that the rat can move in 4 directions and a more complex version can be with limited number of moves.
 **/
 #include <iostream>
 #include <vector>

 bool isSafe(vector<vector<int>> &board, int row, int col) {
     // indicates if the next move is legal.
     if (row<0 || col <0 || row>=board.size() || col >= board[0].size() || (board[row][col] == 0))
         return false;
     return true;
 }

 bool findPathInMaze(vector<vector<int>> &board, vector<vector<int>> &solution, int row, int col) {

     // if we are at the last location, then we have found the path
     if ((row == board.size() -1) && (col == board[0].size())) {
         solution[row][col] = 1;
         return true;
     }

     if (isSafe(board, row, col)) {
         solution[row][col] = 1;

         if (findPathInMaze(board, solution, row+1, col))
             return true;

         if (findPathInMaze(board, solution, row, col+1))
             return true;

         solution[row][col] = 0;
         return false;
     }
     return false;
 }