A maze is a path or collection of paths, typically from an entrance to a goal. The word is used

to refer both to branching tour puzzles through which the solver must find a route, and to

simpler non$-$branching $("$unicursal$")$ patterns that lead unambiguously through a convoluted

layout to a goal. Generally, 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].$ Possible move is forward and down.

Figure $1$: A Simple Maze

Gray blocks are dead ends. Now design a suitable algorithm to find the path from source to

destination. You have to use backtracking approach to find the path. Also keep in mind that,

Brute Force solution is not allowed.

Inputs:

$\{1,0,,\}$

$\{1,1,,1\}$

$\{0,1,0,\}$

$\{1,1,1,1\}$

Where $1$ is the path and $0$ is the wall$($block$).$

Outputs:

$\{1,0,0,0\}$

$\{1,1,0,0\}$

$\{0,1,0,0\}$

$\{0,1,1,1\}$

Figure $2$: Solution of Figure $1$

Future Scope: Modify the algorithm such that the object in the maze can move four

directions.