CODE[VS] 1219 骑士游历

题目链接：
CODE【VS】1219骑士游历

题目描述 Description

设有一个n*m的棋盘（2≤n≤50，2≤m≤50），如下图，在棋盘上有一个中国象棋马。

规定：

1)马只能走日字

2)马只能向右跳

问给定起点x1,y1和终点x2,y2，求出马从x1,y1出发到x2,y2的合法路径条数。

输入描述 Input Description

第一行2个整数n和m

第二行4个整数x1,y1,x2,y2

输出描述 Output Description

输出方案数

样例输入 Sample Input

30 30

1 15 3 15

样例输出 Sample Output

2

数据范围及提示 Data Size & Hint

2<=n,m<=50

思路：

状态转移方程：
dp[i][j] = dp[i-1][j+2]+dp[i-1][j-2]+dp[i-2][j+1]+dp[i-2][j-1];

/*******************
    > File Name: 1219_骑士游历.cpp
    > Author: dulun
    > Mail: dulun@xiyoulinux.org
    > Created Time: 2016年03月09日 星期三 21时27分48秒
 *******************************/

#include<iostream>
#include<stdio.h>
#include<cstring>
#include<cstdlib>
#include<algorithm>
#define LL long long
using namespace std;

const int N = 60;

LL dp[N][N]; //路径太多，用int会溢出。。。

int main()
{
    int n, m;
    cin>>n>>m;
    int x1, y1, x2, y2;
    cin>>x1>>y1>>x2>>y2;
    dp[x1][y1] = 1;
    //游历的时候路径一定在x1,x2之间，行数从1-n.
    for(int i = x1+1; i <= x2; i++)
    //这里需注意！x1+1从起点的下一列开始迭代，如果从第x1行开始，会将dp[x1][y1]覆盖为0，从而结果错误，
    for(int j = 1; j <= n; j++)
    {//这里会越界，，不过能a，应该是“dp[i][-1]”的空间值为0，很危险,还是不要这样了
       // dp[i][j] = dp[i-1][j+2]+dp[i-1][j-2]+dp[i-2][j-1]+dp[i-2][j+1];
        if(i<=2 && j<=2) dp[i][j]=dp[i-1][j+2];  
        else if(i<=2 && j>2) dp[i][j]=dp[i-1][j-2]+dp[i-1][j+2];  
        else if(i>2 && j<=2) dp[i][j]=dp[i-1][j+2]+dp[i-2][j+1]+dp[i-2][j-1]; 
        else   dp[i][j] = dp[i-1][j+2]+dp[i-1][j-2]+dp[i-2][j+1]+dp[i-2][j-1];
    }

    cout<<dp[x2][y2]<<endl;

    return 0;
}