题解：P1002 [NOIP2002 普及组] 过河卒

· · 题解

思路

简单 dp 题。我们仅需求卒能移动到这个位置的位置的方案数之和即可得到这个位置的方案数。注意，马的位置卒不能走，所以应当设为 0。

状态转移方程为：

f_{i,j} = \begin{cases} 0 & \text{horse can go to here} \\ f_{i-1,j} + f_{i,j-1} & \text{horse can't go to here} \end{cases}

初始状态为：

f_{i,j} = \begin{cases} 0 & \text{horse can go to here} \\ 1 & \text{horse can't go to here} \\ \end{cases} (\operatorname{if} i = 0 \lor j = 0)

实现

# include <iostream>
using namespace std;
long long a[50][50];
bool h[50][50];
const int X[9]={0,-2,-2,-1,-1,1,1,2,2};
const int Y[9]={0,-1,1,-2,2,-2,2,-1,1};
int main(){
    int n,m,x,y;
    cin >> n >> m >> x >> y;
    a[1][1] = 1;
    n++,m++,x++,y++;
    for (int i = 0;i < 9;i++) h[x+X[i]][y+Y[i]] = true;
    for (int i = 1;i <= n;i++){
        for (int j = 1;j <= m;j++){
            if (!h[i][j] && (i != 1 || j != 1)) a[i][j] = a[i-1][j] + a[i][j-1];
        }
    }cout << a[n][m];
    return 0;
}