Rat in a Maze Problem

Problem statement

A maze is given as N*N binary matrix of blocks where the source block is the upper left most block (maze[0][0]) and the destination block is the lower rightmost block (maze[N-1][N-1]). A rat starts from the source and has to reach the destination. The rat can move in two directions only: right and down. We need to find all possible ways that a rat can pass through the maze with the given constraints.

In the maze matrix, 0 means the block is a dead end, and X 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.

Let’s look at the example below: