Thursday, January 10, 2013

Path from left upper corner to the right lower corner in a square

Question:
Given a n*n square,  start from the left upper corner, find a path to the right lower corner. At any cell, you can move one step either to the right or to the lower if there is no boundary.  Write a function and return how many paths exist. 

Answer:

#include <iostream>
using namespace std;

int main() {
    int n = 10;
    int path_matrix[n][n];
 
    for(int i=0;i<n;i++)
        for(int j=0;j<n;j++)
            if(i==0 || j==0)
                path_matrix[i][j]=1;
            else
                path_matrix[i][j]= path_matrix[i-1][j] + path_matrix[i][j-1];
 
    cout<<path_matrix[n-1][n-1]<<endl;
    return 0;
}



No comments:

Post a Comment