Code:
#include<stdio.h>
#include<conio.h>
/* graph: Pointer to the starting of mXn matrix
i, j: Current position of the robot (For the first call use 0,0)
m, n: Dimentions of given the matrix
pi: Next index to be filed in path array
*route[0..pi-1]: The path traversed by robot till now (Array to hold the
path need to have space for at least m+n elements) */
void displayAllroutesUtil(int *graph, int i, int j, int m, int n, int *route, int pi)
{
int k,l;
// Reached the bottom of the matrix so we are left with
// only option to move right
if (i == m - 1)
{
for (k = j; k < n; k++)
route[pi + k - j] = *((graph + i*n) + k);
for (l = 0; l < pi + n - j; l++)
printf("%d ",route[l]);
printf("\n ");
return;
}
// Reached the right corner of the matrix we are left with
// only the downward movement.
if (j == n - 1)
{
for (k = i; k < m; k++)
route[pi + k - i] = *((graph + k*n) + j);
for (l = 0; l < pi + m - i; l++)
printf("%d ",route[l]);
printf("\n ");
return;
}
// Add the current cell to the path being generated
route[pi] = *((graph + i*n) + j);
// Print all the paths that are possible after moving down
displayAllroutesUtil(graph, i+1, j, m, n, route, pi + 1);
displayAllroutesUtil(graph, i, j+1, m, n, route, pi + 1);
// Print all the paths that are possible after moving diagonal
// printAllPathsUtil(mat, i+1, j+1, m, n, path, pi + 1);
}
// The main function that prints all paths from top left to bottom right
void displayAllroutes(int *graph, int m, int n)
{
int route[m+n];
displayAllroutesUtil(graph, 0, 0, m, n, route, 0);
}
int main()
{
int graph[4][4] = { {0, 1, 1,0}, {1, 0, 0,1},{1, 0, 0,1},{1, 1, 1,0} };
displayAllroutes(*graph, 2, 4);
return 0;
}