Table of Contents
Method of finding the solution
Example
Output
Explanation of the above code
Conclusion
Home Backend Development C++ Programming in C++, find the number of paths from one point to another in a grid

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

Aug 29, 2023 pm 10:25 PM
grid Number of paths point

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
Copy after login

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";
}
Copy after login

Output

252
Copy after login

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!

Statement of this Website
The content of this article is voluntarily contributed by netizens, and the copyright belongs to the original author. This site does not assume corresponding legal responsibility. If you find any content suspected of plagiarism or infringement, please contact admin@php.cn

Hot AI Tools

Undresser.AI Undress

Undresser.AI Undress

AI-powered app for creating realistic nude photos

AI Clothes Remover

AI Clothes Remover

Online AI tool for removing clothes from photos.

Undress AI Tool

Undress AI Tool

Undress images for free

Clothoff.io

Clothoff.io

AI clothes remover

AI Hentai Generator

AI Hentai Generator

Generate AI Hentai for free.

Hot Article

R.E.P.O. Energy Crystals Explained and What They Do (Yellow Crystal)
2 weeks ago By 尊渡假赌尊渡假赌尊渡假赌
Repo: How To Revive Teammates
1 months ago By 尊渡假赌尊渡假赌尊渡假赌
Hello Kitty Island Adventure: How To Get Giant Seeds
4 weeks ago By 尊渡假赌尊渡假赌尊渡假赌

Hot Tools

Notepad++7.3.1

Notepad++7.3.1

Easy-to-use and free code editor

SublimeText3 Chinese version

SublimeText3 Chinese version

Chinese version, very easy to use

Zend Studio 13.0.1

Zend Studio 13.0.1

Powerful PHP integrated development environment

Dreamweaver CS6

Dreamweaver CS6

Visual web development tools

SublimeText3 Mac version

SublimeText3 Mac version

God-level code editing software (SublimeText3)

Multi-grid redundant bounding box annotation for accurate object detection Multi-grid redundant bounding box annotation for accurate object detection Jun 01, 2024 pm 09:46 PM

1. Introduction Currently, the leading object detectors are two-stage or single-stage networks based on the repurposed backbone classifier network of deep CNN. YOLOv3 is one such well-known state-of-the-art single-stage detector that receives an input image and divides it into an equal-sized grid matrix. Grid cells with target centers are responsible for detecting specific targets. What I’m sharing today is a new mathematical method that allocates multiple grids to each target to achieve accurate tight-fit bounding box prediction. The researchers also proposed an effective offline copy-paste data enhancement for target detection. The newly proposed method significantly outperforms some current state-of-the-art object detectors and promises better performance. 2. The background target detection network is designed to use

Steps to set up camera grid on iPhone Steps to set up camera grid on iPhone Mar 26, 2024 pm 07:21 PM

1. Open the desktop of your iPhone, find and click to enter [Settings], 2. Click to enter [Camera] on the settings page. 3. Click to turn on the switch on the right side of [Grid].

CSS Layout Tips: Best Practices for Implementing Circular Grid Icon Layout CSS Layout Tips: Best Practices for Implementing Circular Grid Icon Layout Oct 20, 2023 am 10:46 AM

CSS Layout Tips: Best Practices for Implementing Circular Grid Icon Layout Grid layout is a common and powerful layout technique in modern web design. The circular grid icon layout is a more unique and interesting design choice. This article will introduce some best practices and specific code examples to help you implement a circular grid icon layout. HTML structure First, we need to set up a container element and place the icon in this container. We can use an unordered list (&lt;ul&gt;) as a container, and the list items (&lt;l

How to type the point '丶' using the keyboard? How to type the point '丶' using the keyboard? Feb 15, 2024 pm 01:51 PM

When typing on a keyboard, many users are curious about how to type the point "丶" on the keyboard? So let’s take a look at the method that the editor brings to you on how to type this “丶” symbol on the keyboard. 1. Click "丶" and type directly on the keyboard [dian]. You will see the punctuation mark [丶] on the selection bar. 2. Special symbols In the Sogou Pinyin input method, when switching to Chinese mode, pressing the v key will cause some special symbols to appear. These symbols include numbers (eg: v123), dates (eg: v2013/1/1), calculations (eg: v1+1) and functions (eg: v2~3). These symbols make it easy to enter a variety of different information. 2. Then press the number key again, any number from 0 to 9 can be used

Written in C++, find the number of triangles formed by a set of points on three lines Written in C++, find the number of triangles formed by a set of points on three lines Sep 09, 2023 am 09:53 AM

Now we get several points present in 3 rows; for example, we need to find out how many triangles these points can form Input:m=3,n=4,k=5Output:205Input:m=2,n=2, k=1Output:10 We will apply some combinatorial mathematics to solve this problem and formulate some formulas to solve this problem. Method to find a solution In this method we will devise a formula: applying combinatorics to the current situation, this formula will provide us with the result. C++ code for the above method This is the C++ syntax we can use as input to solve the given problem - example #include<bits/stdc++.h>#define

How to check if three points are collinear in Java? How to check if three points are collinear in Java? Sep 05, 2023 pm 06:41 PM

If three points lie on a straight line, they are said to be collinear. If the points are not on the same straight line, they are not collinear. This means that if three points (x1,y1), (x2,y2), (x3,y3) are on the same straight line, they are collinear. Among them, x1, y1, x2, y2, x3, y3 are points on the x-axis and y-axis, (x1, y1), (x2, y2), (x3, y3) are the coordinates. Mathematically, there are two ways to determine whether three points are collinear. Find the area of ​​a triangle by using the points. If the area of ​​the triangle is zero, then the three points are collinear. Formulatofindareaoftriangle=0.5*[x1*(y2-y3)+x2*

C++ program to find the number of jumps required by a robot to reach a specific cell in a grid C++ program to find the number of jumps required by a robot to reach a specific cell in a grid Sep 17, 2023 pm 07:17 PM

Let's say we have a hxw grid. The grid is represented in a two-dimensional array called 'initGrid', where each cell in the grid is represented by a '#' or '.'. '#' means there is an obstacle in the grid, '.' means there is a path on that cell. Now, a robot is placed on a cell 'c' on the grid which has row number x and column number y. The robot has to move from one cell 'd' which has row number p and column number q to another cell. The cell coordinates c and d are both given as pairs of integers. The robot can now move from one cell to another as follows: If the cell the robot wants to move to is located vertically or horizontally adjacent to the current cell, the robot can

C++ program to calculate the total cost required for a robot to complete a trip in a grid C++ program to calculate the total cost required for a robot to complete a trip in a grid Aug 25, 2023 pm 04:53 PM

Suppose we have a grid of size hxw. Each cell in the grid contains a positive integer. Now there is a path finding robot placed on a specific cell (p,q) (where p is the row number and q is the column number) and it can move to the cell (i,j). The move operation has a specific cost equal to |p-i|+|q-j|. There are now q trips with the following properties. Each trip has two values ​​(x, y) and has a common value d. The robot is placed on a cell with value x and then moves to another cell with value x+d. Then it moves to another cell with value x+d+d. This process will continue until the robot reaches a cell with a value greater than or equal to y. y-x is a multiple of d

See all articles