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[0][0] 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.

Rat at Maze problem

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[0][0] and
  // rat has to reach at m[4][3] 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");
}



Related Contents to follow