Niuke: crossing the river

Well , This question is obvious dp subject .

First write the dynamic transfer equation , set up dp[i][j] Representation coordinates (0,0) To (i,j) The number of paths , This number of paths is equal to the sum of the number of paths of the left node and the number of paths of the upper node , obviously dp[i][j]=dp[i-1][j]+dp[i][j-1], This is the case that this point can go . Of course , If this point can be reached by a horse , So directly dp[i][j]=0.

As for the concrete realization ：

1. When judging the horse point , Directly judge the coordinates in the traversal process , The previous idea was to mark on the map first , Such an approach is still a little troublesome

2. Special assignments are required in the first column and row , The coordinate origin needs to be assigned 1

3. As for the data size, let's calculate 40 Internal selection 20 About the maximum order of magnitude , Probably 137846528820, then int The maximum value of 2147483647, Obviously , Here we need to use larger data types to store answers , such as long long

The code is as follows ：

#include<bits/stdc++.h>
using namespace std;
int n,m,x,y;
// Check whether the coordinates are the points that the horse can reach 
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;
}