49. 跳马问题

★   输入文件：horse.in   输出文件：horse.out   简单对比
时间限制：1 s   内存限制：128 MB

【问题描述】

    有一只中国象棋中的 “ 马 ” ，在半张棋盘的左上角出发，向右下角跳去。规定只许向右跳（可上，可下， 但不允许向左跳）。请编程求从起点 A(1,1) 到终点 B(m,n) 共有多少种不同跳法。

   【输入格式】       输入文件只有一行，两个整数m和n（1≤m,n≤20），两个数之间有一个空格。  【输出格式】       输出文件只有一个整数，即从 A 到 B 全部的走法。    【输入输出样例】      输入文件(horse.in)    5　9     输出文件(horse.out)    37   自动选择评测机   gcc/g++4.8.5 gcc/g++4.8.5 -O2 gcc/g++4.8.5(C++11) gcc/g++4.6.3 gcc/g++4.6.3 -O2         
 Pascal C C++ 天哪 这可真是一道水水水水题啊   我就不用DFS来做了 用一下动态规划试试看！ 其实看起来还是比较简单的 f[i][j] = f[i - 2][j - 1] + f[i - 2][j + 1] + f[i - 1][j - 2] + f[i - 1][j + 2]; 然后i和j都从小往大枚举for循环 其实也就是从左往右 从上往下 至于正确性？不好证明。。 但是确实卡过了诶 QaQ  左右上方四个点的和   说实话 这一道题 调起来确实挺费劲的

#include
using namespace std;
int f[1005][1005];
int main()
{
    freopen("horse.in","r",stdin);
    freopen("horse.out","w",stdout);
    int n,m;
    scanf("%d%d",&n,&m);
    f[1][1]=1;
    for(int i=2;i<=m;i++)
        for(int j=1;j<=n;j++)
            f[i][j]=f[i-2][j-1]+f[i-2][j+1]+f[i-1][j-2]+f[i-1][j+2];
    printf("%d",f[m][n]);
    
    return 0;
}