工学1号馆

home

« | 返回首页 | »

Project Euler 15–Lattice paths

By Wu Yudong on December 13, 2017

Starting in the top left corner of a 2×2 grid, and only being able to move to the right and down, there are exactly 6 routes to the bottom right corner.

How many such routes are there through a 20×20 grid?


题目大意:

从一个2×2网格的左上角开始,有6条(不允许往回走)通往右下角的路。

对于20×20的网格,这样的路有多少条?

#include<iostream>
#include<cmath>
using namespace std;

long long a[21][21];

int main()
{
	int i;
	for (i = 0; i < 21; i++) {
		a[0][i] = 1;
		a[i][0] = 1;
	}
	for (i = 1; i < 21; i++)
		for (int j = 1; j < 21; j++)
			a[i][j] = a[i][j - 1] + a[i - 1][j];
	cout << a[20][20] << endl;
	return 0;
}

Answer:137846528820
Completed on Tue, 11 Feb 2014, 16:18

如果文章对您有帮助,欢迎点击下方按钮打赏作者

Comments

No comments yet.
To verify that you are human, please fill in "七"(required)