题意

• n*m的棋盘，卒在(0,0)，可以向右或者向下走，最终要走到(n,m)，同时，棋盘上还有一匹马，它会控制他能走到的8个点，以及它自己所在的位置,卒不能走这几个位置
• 请问最终有多少条路径能让卒走到(n,m)

思路

• 实现方法一：提前把不能走的点标一个极小值，转移方程为
• 实现方法二：走到每一个位置都检查是不是被马覆盖，如果是就清零

代码

//思路一
#include<bits/stdc++.h>
using namespace std;

long long dp[30][30];
int main(){
    int n,m,x,y;
    cin >> n >> m >> x >> y;
    //init
    dp[x][y]=-0x3f3f3f3f;
    if(x-1>=0&&y-2>=0) dp[x-1][y-2]=-0x3f3f3f3f;
    if(x-1>=0&&y+2<=m) dp[x-1][y+2]=-0x3f3f3f3f;
    if(x-2>=0&&y-1>=0) dp[x-2][y-1]=-0x3f3f3f3f;
    if(x-2>=0&&y+1<=m) dp[x-2][y+1]=-0x3f3f3f3f;
    if(x+1<=n&&y-2>=0) dp[x+1][y-2]=-0x3f3f3f3f;
    if(x+1<=n&&y+2<=m) dp[x+1][y+2]=-0x3f3f3f3f;
    if(x+2<=n&&y-1>=0) dp[x+2][y-1]=-0x3f3f3f3f;
    if(x+2<=n&&y+1<=m) dp[x+2][y+1]=-0x3f3f3f3f;
    dp[0][0]=1;
    for(int j=1;j<=m;j++) dp[0][j]+=dp[0][j-1];
    for(int j=1;j<=n;j++) dp[j][0]+=dp[j-1][0];

    for(int i=1;i<=n;i++){
        for(int j=1;j<=m;j++){
            dp[i][j]+=max(0ll,dp[i-1][j])+max(0ll,dp[i][j-1]);
        }
    }
    // for(int i=0;i<=n;i++){
    //     for(int j=0;j<=m;j++){
    //         printf("%4d",max(dp[i][j],0)); 
    //     }
    //     printf("\n");
    // }
    cout << dp[n][m] << endl;
    return 0;
}
//思路二
#include<bits/stdc++.h>
using namespace std;
long long dp[30][30];
int main(){
    int n,m,x,y;
    cin >> n >> m >> x >> y;
    n++,m++,x++,y++;
    //为了方便操作，先把整个图往右下挪一点
    dp[1][1]=1;
    for(int i=1;i<=n;i++){
        for(int j=1;j<=m;j++){
            if(i==1&&j==1) continue;
            if((abs(x-i)==1&&abs(y-j)==2)||(abs(x-i)==2&&abs(y-j)==1)||(i==x&&j==y)){
                dp[i][j]=0;
            }else{
                dp[i][j]=dp[i-1][j]+dp[i][j-1];
            }
        }
    }
    cout << dp[n][m] << endl;
    return 0;
}