Traversing a Grid/Matrix

How to traverse a grid or matrix using recursion


Category: Data Structure And Algorithms Tags: C#, Java, C++ Programming

Traversing a Grid Code Files

Introduction

        Suppose a given grid M×N where M are rows and N are columns then we have to find out how many ways are there to move from index (1,1) to (M,N) if we only can move right and down.

Implementation

        Suppose there is grid of 2×2 as shown below then only 2 ways can be there to reach from (1,1) to (M,N) we can not move diagonally only can move right and down.

Traversing grid

        In above picture we have S means source and D means destination and we cannot move diagonally, only we can move right and down so there will be only 2 ways in 2×2 grid.
        So same we can achieve if we move from (2,2) to (1,1) in above picture if we move only left and up. If we start from (2,2) so only 2 moves will be there (1,2) and (2,1) and once any one of the coordinate(row and column) reaches to one it has to go only left or right, there will be no any other moves. Now suppose we try to solve with recursion and having grid of 3×3, so:Traversing a Grid

        Above picture you can see we are splitting M×N in manner of (M-1, N) and (M, N-1) and wherever any coordinate is 1 we say it is left with only one way (in grey background). When we backtrack the recursion tree and go up we sum the children values and lead to 1+1=2, 2+1=3, 3+3=6. So there will be 6 ways to reach from (1,1) to (3,3) or vice versa if we follow direction rules.
Now lets see it with code:

static int GetWays(int x, int y)
{
    if (x == 1 || y == 1)
        return 1;
    else
        return GetWays(x - 1, y) + GetWays(x, y - 1);
}

        Above we can see we are returning 1 if any of the coordinate equals to one until that we break it in (M-1, N) and (M, N-1). And we will execute this code from Main method:

int M = 3;
int N = 3;
Console.WriteLine("Ways of reaching from (1,1) to ({0},{1}) are: {2}", M, N, GetWays(3, 3));

And output will be:
Ways of reaching from (1,1) to (3,3) are: 6


Like 1 Person
Last modified on 31 October 2018
Nikhil Joshi

Nikhil Joshi
Ceo & Founder at Dotnetlovers
Atricles: 133
Questions: 9
Given Best Solutions: 9 *

Comments:


You are not loggedin, please login or signup to add comments:

Existing User

Login via:

New User



x