题解 | #[NOIP2002 普及组] 过河卒#

解题思路：

• 利用二维数组dp
• 卒子只能两个方向走，一个是向右，一个是向下。可得状态方程$dp[i][j]=dp[i-1][j]+dp[i][j-1]dp[i][j]\; =\; dp[i-1][j]\; +\; dp[i][j-1]$。
• 在处理马点的时候，应该做出判断，如果该点是马点或者马可以跳到的点则应该设置为0，即abs(i-x)+abs(j-y) && i != x && j !=y和马点$(x,y)(x,y)$处设置为0
• 初始化$dp[0][0]=1dp[0][0]\; =\; 1$,$dp[i][0]=dp[i-1][0]dp[i][0]\; =\; dp[i-1][0]$,$dp[0][j]=dp[0][j-1]dp[0][j]\; =\; dp[0][j-1]$
• 注意最后一个坑点，int存储不了，得使用long long

#include<bits/stdc++.h>
using namespace std;
long long  mp[25][25];
int check(int i, int j, int x, int y){//判断马点
    return (abs(i-x) + abs(j-y) == 3 && i != x && j != y) || (i == x && j == y);
}
long long solve(int n, int m, int x, int y){
    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(){
    int n,m, x, y;
    cin>>n>>m>>x>>y;
    cout<<solve(n,m,x,y)<<endl;
    return 0;
}