wikioi 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-2][j-1]+dp[i-2][j+1]+dp[i-1][j+2]

#include <iostream>#include <cstring>using namespace std;#define MAXN 111long long dp[MAXN][MAXN];int main(){    int n, m, x1, y1, x2, y2;    cin >> n >> m;    cin >> x1 >> y1 >> x2 >> y2;    dp[x1][y1] = 1;    for(int i=x1+1; i<=x2; i++)    {        for(int j=1; j<=n; j++)        {            //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];            dp[i][j]=dp[i-2][j-1]+dp[i-1][j-2]+dp[i-1][j+2]+dp[i-2][j+1];        }    }    cout << dp[x2][y2];    return 0;}

由于dp数组从0开始，默认值为0。因此，不需要单独考虑边界问题。