Travelling in a Maze

We might have come across problems asking number of possible paths to reach destination from source point. Lets see one such problem that can be solved with simple DP.

Question is, given a maze of dimensions MxN, and few obstructions, find number of paths that are possible starting at (1,1) and ends at (M,N). Also given that we can travel only to right or down from current position. ((1,1) will on top-left and (M,N) will be on bottom-right).

Lets once trace out for a maze with no obstructions. How many different paths are possible? There might be a mathematical formula for this. But let us solve it using DP. We will caluclate possible ways to reach each position starting from (1,1) and moving away from it towards (M,N).

Recursion formula would be,

f(X,Y) = 0 if either X = 0 or Y = 0
1 if X = 1 and Y = 1
f(X-1,Y)+f(X,Y-1) for rest of X,Y

For either X =0 or Y= 0, we never reach to those points, so number of paths leading to those points is 0.
For (X,Y) = (1,1), f(X,Y) = 1 because that is the source node. Only one possible way to reach there.
For rest of X and Y, reaching to that position is possible only from (X-1,Y) or (X,Y-1) as we can move only to right or down.

So tracing for X=4,Y=4, maze will become,

0 0 0 0 0
0 1 1 1 1
0 1 2 3 4
0 1 3 6 10
0 1 4 10 20

So to reach (4,4) from (1,1), there are 20 paths possible.

Now for any given obstructions, mark them 0 in the DP matrix and then apply above recursive formula for rest of the positions.

Code solving above question would be,

#include <iostream>;
#include <cstdio>;

using namespace std;

void travel_in_maze(int a[][100],int m,int n)
{
    int i,j;
    for(i = 0;i <= m;i++)
    {
        for(j = 0;j <= n;j++)
        {
            if(i == 0 || j == 0)
                a[i][j] = 0;
            else if(i == 1 && j == 1)
                a[i][j] = 1;
            else if(a[i][j] != 0)
                a[i][j] = a[i-1][j] + a[i][j-1];
        }
    }
}

int main()
{
    int m,n;
    int maze[100][100];
    int i,j;
    for(i = 0;i < 100;i++)
    {
        for(j = 0;j < 100;j++)
        {
            maze[i][j] = -1;
        }
    }
    scanf("%d %d",&m,&n);
    int obs; /* number of obstructions */
    int x,y;
    scanf("%d",&obs);
    for(i = 0;i < obs; i++)
    {
        scanf("%d %d",&x,&y);
        maze[x][y] = 0;
    }
    travel_in_maze(maze,m,n);
    printf("Number of paths = %d\n",maze[m][n]);
return 0;
}
Tracing for following case,
M = 5, N = 5
obs = 3
obstruction points = (1,3)
(5,1)
(3,2)

0 0 0 0 0 0
0 1 1 0 0 0
0 1 2 2 2 2
0 1 0 2 4 6
0 1 1 3 7 13
0 0 1 4 11 24

Number of paths = 24.
Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s