Programming in C++, find the number of paths from one point to another in a grid

In this article, we are given a problem where we need to find the total number of paths from point A to point B, where A and B are fixed points i.e. A is a grid The upper left corner point in , B is the lower right corner point in the grid, e.g. −

Input : N = 5
Output : 252

Input : N = 4
Output : 70

Input : N = 3
Output : 20

In the given problem, we can formalize the answer and derive the result through simple observations.

Method of finding the solution

In this method, we derive a formula through observation, that is, when crossing the grid from A to B, we need to go to the right n times, Traveling down n times, this means we need to find all possible combinations of paths, so we get the combined formula of (n n) and n.

Example

#include<bits/stdc++.h>

using namespace std;
int fact(int n){ // factorial function 
   if(n <= 1)
      return 1;
   return n * fact(n-1);
}
int main() {
   int n = 5; // given n
   int answer = 0; // our answer
   answer = fact(n+n); // finding factorial of 2*n
   answer = answer / (fact(n) * fact(n)); // (2*n)! / (n! + n!)
   cout << answer << "\n";
}

Output

252

Explanation of the above code

In this code, we calculate the combined formula of 2*n to n, because We know that from point A to point B, we need exactly 2*n operations in two directions, that is, there are n operations in one direction and n operations in the other direction, so we find all possibilities of these operations The combination is (2*n)!/ (n! n!). The overall time complexity of the given program is O(1), which means that our complexity does not depend on the given n.

Conclusion

In this article, we discussed a problem to find the number of routes from one point to another point in a grid. We also learned a C program for this problem and our complete approach to solving it. We can write the same program in other languages ​​such as C, java, python and other languages. We hope this article was helpful to you.

The above is the detailed content of Programming in C++, find the number of paths from one point to another in a grid. For more information, please follow other related articles on the PHP Chinese website!