牛客网：过河卒

嘛，这题是个很明显的dp题目。

首先写出动态转移方程，设dp[i][j]表示坐标(0,0)到(i,j)的路径数，这个路径数等于其左边节点的路径数和上边节点的路径数之和，显然dp[i][j]=dp[i-1][j]+dp[i][j-1]，这是这个点可以走的情况。当然，如果这个点是马可以到达的，那么直接dp[i][j]=0。

至于具体的实现：

1.在判断马点的时候，直接在遍历过程中判断坐标即可，之前的思路想着先在地图上面标记，这样的做法还是麻烦了点

2.在第一列和第一行时需要特殊赋值，坐标原点需要赋值1

3.至于数据大小我们算一下40里选20的组合数大约估计一下最大数量级，大概是137846528820，然后int的最大值是2147483647，很明显，这里我们要用更大的数据类型来存储答案，比如long long

代码如下所示：

#include<bits/stdc++.h>
using namespace std;
int n,m,x,y;
//检查坐标是否是马可以到的点
bool check(int i, int j, int x, int y){
    return (abs(x-i) + abs(y-j) == 3 && x!=i && y!=j) || (x==i && y==j);
}

long long dp(vector<vector<long long>> &mp){
    mp[0][0]=1;
    for(int i=1;i<=n;++i){
        mp[i][0] = (check(i, 0, x, y)) ? 0 : mp[i-1][0];    
    }
    for(int j=1;j<=m;++j){
        mp[0][j] = (check(0, j, x, y)) ? 0 : mp[0][j-1];
    }
    for(int i=1;i<=n;++i){
        for(int j=1;j<=m;++j){
            mp[i][j] = (check(i, j, x, y)) ? 0 : mp[i-1][j] + mp[i][j-1];
        }
    }
    return mp[n][m];
}

int main(){
    cin>>n>>m>>x>>y;
    vector<vector<long long>> mp(n+1, vector<long long>(m+1, 0));
    cout<<dp(mp)<<endl;
    return 0;
}