小兔的棋盘

时间限制：1000/1000 MS（Java / Others）内存限制：32768/32768 K（Java / Others）
总提交内容：13029接受的提交内容：6517

问题描述

小兔的叔叔从外面旅游回来给她带来了一个礼物，小兔高兴地跑回自己的房间，拆开一看是一个棋盘，小兔有所失望。不过没过几天发现了棋盘的好玩之处。从起点（0,0）走到终点（N，N）的最短路径数是C（2N，N），现在小兔又想如果不穿越对角线（但可接触对角线上的格点），这样的路径数有多少？小兔想了很长时间都没想出来，现在想请你帮助小兔解决这个问题，对于你来说应该不难吧！

输入

每次输入一个数N（1 <= N <= 35），当Ñ等于-1时结束输入。

产量

对于每个输入数据输出路径数，具体格式看样品。

样本输入

-1

样本输出

1 1 2

2 3 10

3 12 46024

#include <iostream>

#include <cstring>

#include <cstdio>

using namespace std;

int n;

long long map[][];

int main()

{

    int i,j,cnt=;;

    while(cin>>n&&n!=-)

    {

        memset(map,,sizeof(map));

        for(i=;i<=n;++i)//先把第一行的每一个数置1，因为迷宫是关于对角线对称的，只要考虑一边，最后乘以2就好

            map[][i]=;

        for(i=;i<=n;++i)

            for(j=;j<=i;++j)

        {

            if(i==j)

                map[i][j]=map[i][j-];//在对角线上，前一步只能是从上面走下来

            else

                map[i][j]=map[i-][j]+map[i][j-];//不在对角线上，可以从上和左两个方向走

        }

        printf("%d %d %I64d\n",cnt++,n,*map[n][n]);//cnt是测试样例的序号，n是输入的测试样例，最后一个是步数

    }

    return ;

}

小兔

hdu2067 小兔的棋盘

小兔的棋盘