Maze With N doors and 1 Key | C ++ implementation of the approach ; Recursive function to check whether there is a path from the top left cell to the bottom right cell of the maze ; Check whether the current cell is within the maze ; If key is required to move further ; If the key hasn 't been used before ; If current cell is the destination ; Either go down or right ; Key has been used before ; If current cell is the destination ; Either go down or right ; Driver code ; If there is a path from the cell ( 0 , 0 )
#include <bits/stdc++.h> NEW_LINE using namespace std ; bool findPath ( vector < vector < int > > maze , int xpos , int ypos , bool key ) { if ( xpos < 0 || xpos >= maze . size ( ) || ypos < 0 || ypos >= maze . size ( ) ) return false ; if ( maze [ xpos ] [ ypos ] == '1' ) { if ( key == true ) if ( xpos == maze . size ( ) - 1 && ypos == maze . size ( ) - 1 ) return true ; return findPath ( maze , xpos + 1 , ypos , false ) || findPath ( maze , xpos , ypos + 1 , false ) ; return false ; } if ( xpos == maze . size ( ) - 1 && ypos == maze . size ( ) - 1 ) return true ; return findPath ( maze , xpos + 1 , ypos , key ) || findPath ( maze , xpos , ypos + 1 , key ) ; } bool mazeProb ( vector < vector < int > > maze , int xpos , int ypos ) { bool key = true ; if ( findPath ( maze , xpos , ypos , key ) ) return true ; return false ; } int main ( ) { vector < vector < int > > maze = { { '0' , '0' , '1' } , { '1' , '0' , '1' } , { '1' , '1' , '0' } } ; int n = maze . size ( ) ; if ( mazeProb ( maze , 0 , 0 ) ) cout << " Yes " ; else cout << " No " ; }