• • Given a MxN maze as binary matrix where each block is either 0 or 1. 0 means wall and 1 means entry. A rat starts from source maze and has to reach at destination mat[M][N]. the rat can move only in two directions, forward and down.Based on the above condition and maze ( matrix ) as input, filled with 0 and 1, write c or cpp code to print the path so that rat can reach at its destination. For example below figure. If we replace green as 1 and red as 0, the input matrix will be:

```{1, 0, 1, 0},
{1, 1, 1, 0},
{0, 0, 1, 0},
{1, 1, 1, 1},
{1, 1, 0, 1}
};```

The output path will be: (0,0) (1,0) (1,1) (1,2) (2,2) (3,2) (3,3) (4,3)

Below is the c code with best possible comments to understand the strategy for solving rat maze problem.

```#include<stdio.h>

#define row 5
#define col 4

void printPath (int m[row][col]);

int
main ()
{
// rat startig point is m and
// rat has to reach at m i.e at last right buttom corner
int m[row][col] = {
{1, 0, 1, 0},
{1, 1, 1, 0},
{0, 0, 1, 0},
{1, 1, 1, 1},
{1, 1, 0, 1}
};

// expected output
//  (0,0) (1,0) (1,1) (1,2) (2,2) (3,2) (3,3) (4,3)

printPath (m);
// getchar(); uncomment this line for windows
return 0;
}

void printPath (int m[row][col])
{
int i = 0;
int j = 0;
// chnage direction of travelling
// when next path is possible continue to go ahead horiontally
// otherwise change direction in up to downwards vertically
while( i < row)
{
if((m[i][j] == 1) && (j < col))
{
printf("(%d,%d) ",i,j);
j++;   // go horizontal
}
else
{
j = j -1;  // back to position
i++;     // go down
}

}

printf ("\n");
}```