洛谷——过河卒问题_过河卒洛谷

棋盘上 AA 点有一个过河卒，需要走到目标 BB 点。卒行走的规则：可以向下、或者向右。同时在棋盘上 CC 点有一个对方的马，该马所在的点和所有跳跃一步可达的点称为对方马的控制点。因此称之为“马拦过河卒”。

棋盘用坐标表示，AA 点 (0, 0)(0,0)、BB 点 (n, m)(n,m)，同样马的位置坐标是需要给出的。

现在要求你计算出卒从 AA 点能够到达 BB 点的路径的条数，假设马的位置是固定不动的，并不是卒走一步马走一步。

输入格式
一行四个正整数，分别表示 BB 点坐标和马的坐标。

输出格式
一个整数，表示所有的路径条数。

输入输出样例

• 输入 6 6 3 3
• 输出 6

题目分析

首先必须清楚他要我们输入的是终点坐标以及马的位置，起点是确定的AA(0,0)，然后我们需要知道本题让我们求的是所有的路径数，这样，我们最先想到的可能就是深度优先搜索dfs了，当然动态规划也是一个不错的选择，因为本题中卒子运动到每一个点的状态是与前面一个点的状态关系是很容易得出来的，也就是，当没有任何限制的时候，此时如果卒子运动到了f[i][j]位置，那么f[i][j] = f[i-1][j] + f[i][j-1] (因为卒子不是往下走就是往右走)，但是本题目中有限制，就是不能踩到马的控制点。

区域中各个点的初始化

一开始区域马的位置定义为-1，判断区域的每一行和每一列中是否包含马的控制点，如果是，则该位置的路径数定为-1，否则该位置的路径数定为1，区域内其他的位置的路径数都定义为零（只要定义二维数组即可，因为一定义就会赋值为0）。

马控制点的处理

我们需要先定义一个数组来存放以马为中心，马走一步之后可以到达的点的坐标， 即马的控制点（一共8个点），在定义一个函数来判断卒子是否已经走到了马的控制点，以及马的控制点是否已经越界了，如果不越界，就将让它等于-1。

求解每一个点的路径数

遍历每一个点，找到从原点到达区域内任意一点的路径数。
双重循环中做如下处理 ：卒子凡是到了等于-1的位置就用跳过，继续遍历下一个点，由于每一个点的路径由上一个点的路径来递推，而上一个点可能是来自上方，也可能来自左方，因此，需要分别判断上方或者左方的点的位置的值是否为-1，如果不是，就加上上方或者左方的点的路径数，最终输出到达终点的路径数即可。

#include <bits/stdc++.h>
using namespace std;
ll bx, by, mx, my;
ll pan[25][25];
ll local[8][2] = {
    {
   1, 2} , {
   2, 1} , {
    -1, 2} , {
   1, -2} , {
   2, -1} , {
   -2 , 1}, {
   -1 , -2} , {
   -2, -1} };
void judge() {
   
    pan[mx][my] = -1;
    for (int i = 0; i < 8; i++) {
   
        if 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19