路线方案数

题目

给定一个2*n的矩阵,每个单元点面积为1,且拥有独立编号。当处于坐标(x,y)时,可以向(x-1,y),(x+1,y),(x,y-1),(x,y+1)移动。
现在想考考你,从任意一点出发,每个单元正好经过一次的方案数是多少?

输入

题目包含多组测试样例。每行输入一个n(1<=n<=100000)。

输出

每组样例输出一个数代表方案数。

样例输入

  • 2

样例输出

  • 8

思路

去数 2*3 2*4
发现最左边的方案数是n*2 最右边同理
剩下就是中间每块是(n-1)
公式推到: [n>1] 4*n + (n-1) * (n*2-4)

AC代码

#include <iostream>
typedef long long ll;
using namespace std;
int main()
{
    ll n;
    while (cin >> n)
    {
        ll res = 4*n+(n-1)*(n*2-4);
        if(n == 1)cout << 2 << endl;
        else cout << res << endl;
    }
}
Last modification:April 3rd, 2020 at 01:40 pm
如果觉得我的文章对你有用,请随意赞赏