题解 | #过河卒#

一、判断能否用动态规划

1.原问题： 从起点到终点的路径条数

子问题：从起点到位置（i，j）的路径条数

可以知道，具有相同的子问题

2.每一个子问题都是包含了它的子问题的最优解

满足此后决策是基于当前状态的最优决策

3.解决当前的决策和过去的状态没有关系

满足无后效性

综上可以使用动态规划

二、推状态转移方程

因为每一个位置都可以从上面和左面走来，所以可知，状态转移方程为

dp[i][j]=dp[i-1][j]+dp[i][j-1];

#include<bits/stdc++.h>
using namespace std;
int n,m,x,y;
const int mod=10000007;
typedef long long ll;
const int M=1005;
ll dp[M][M];
int mov[8][2]={{-2,-1},{-2,1},{-1,-2},{-1,2},{1,-2},{1,2},{2,-1},{2,1}};
bool check(int a,int b){
    if(a==x&&b==y) return true;
    for(int i=0;i<8;i++){
        if(a==x+mov[i][0]&&b==y+mov[i][1]) return true;
    }
    return false;
}
int main(){
    cin>>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;
            dp[i][j]=(dp[i-1][j]%mod+dp[i][j-1]%mod)%mod;
            if(check(i,j))
                dp[i][j]=0;
        }
    }
    cout<<dp[n][m]%mod<<endl;
    return 0;
}