题目链接

过河卒

题目思路

动态规划，把原问题分解成子问题，找动态方程

代码实现

#include<bits/stdc++.h>
#define int long long
using namespace std;
int dr[8][2]={{2,1},{2,-1},{-1,2},{1,-2},{-2,-1},{-1,-2},{1,2},{-2,1}};
const int Max=30;
int n,m,x,y;
int dp[Max][Max],mp[Max][Max];
signed main()
{
    cin>>n>>m>>x>>y;
    for(int i=0;i<8;i++)
    {
        mp[x+dr[i][0]][y+dr[i][1]]=1;
    }
    mp[x][y]=1;
    dp[0][0]=1;
    for(int i=0;i<=n;i++)
        for(int j=0;j<=m;j++)
        {
            if(!mp[i+1][j]) dp[i+1][j]+=dp[i][j];
            if(!mp[i][j+1]) dp[i][j+1]+=dp[i][j];
        }
    cout<<dp[n][m]<<endl;
    return 0;
}