题目描述 给出卒的起点（0,0）和终点A(Ax,Ay)，和马的点B(Bx,By)，卒不能走到马所管辖的点（马一步所能跳到的点），统计到达终点的路数，卒中只能向下或者向右走。由多少种不同的走法。 数据范围 0<Ax、Ay、Bx、By<21 输入格式 Ax Ay Bx By 输出格式 一个正整数表示路数。 输入输出样例 输入： 6 6 3 3 输出： 6 请用C++语言编写一段程序

思路：动态规划

题目要求卒不能走到马所管辖的点，因此我们可以先预处理出马所管辖的点有哪些，然后再用动态规划求解。

设 $f(i,j)$ 表示从 $(0,0)$ 走到 $(i,j)$ 的路数，$g(i,j)$ 表示 $(i,j)$ 是否为马所管辖的点，则状态转移方程为：

$$
f(i,j) = \begin{cases}
0, & g(i,j) = 1 \\
1, & i = 0 \text{ or } j = 0 \\
f(i-1,j) + f(i,j-1), & \text{otherwise}
\end{cases}
$$

时间复杂度 $O(n^2)$。

C++ 代码：