过河卒 题解

首先不考虑马的情况。
那么每一个位置，都可以从他的上方走来，和从他的左边走来。
那么很容易想到状态转移方程dp[i][j]=dp[i-1][j]+dp[i][j-1]
由于多了一个马，那么记录这个马控制的九个点，在对应的vis数组进行标记
如果vis[i][j]==1，那么就让dp[i][j]=0，else dp[i][j]=dp[i-1][j]+dp[i][j-1]
注意边界条件，卒子在第一行的时候，只能是从左边移动而来，卒子在第一列的时候，只能是从上面移动而来。
最后输出dp[n][n]即可

#include <bits/stdc++.h>
using namespace std;
#define ll long long
ll dp[22][22];
int vis[22][22];
int dx[8]={-1,-2,-2,-1,1,2,2,1};//x为横着移动
int dy[8]={-2,-1,1,2,2,1,-1,-2};
int main()
{
    int n,m,x,y;
    scanf("%d%d%d%d",&n,&m,&x,&y);
    for(int i=0;i<8;i++)
    {
        if(x+dx[i]>=0&&x+dx[i]<=n&&y+dy[i]>=0&&y+dy[i]<=m)
            vis[x+dx[i]][y+dy[i]]=1;
    }
    vis[x][y]=1;
    if(!vis[0][0]) dp[0][0]=1;
    for(int i=1;i<=n;i++)
    {
        if(vis[i][0])
            dp[i][0]=0;
        else
            dp[i][0]=dp[i-1][0];
    }
    for(int i=1;i<=m;i++)
    {
        if(vis[0][i])
            dp[0][i]=0;
        else
            dp[0][i]=dp[0][i-1];
    }
    for(int i=1;i<=n;i++)
    {
        for(int j=1;j<=m;j++)
        {
            if(vis[i][j])
                dp[i][j]=0;
            else
                dp[i][j]=dp[i-1][j]+dp[i][j-1];
        }
    }
    printf("%lld\n",dp[n][m]);
}