题解 P1002 【过河卒】

xiejinhao · 2019-04-13 22:35:13 · 题解

P1002 过河卒 题解

这题不用高精，具体做法如下

我们先来看题目：

• 棋盘上 A 点有一个过河卒，需要走到目标 B 点。卒行走的规则：可以向下、或者向右。同时在棋盘上 C 点有一个对方的马，该马所在的点和所有跳跃一步可达的点称为对方马的控制点。因此称之为“马拦过河卒”。棋盘用坐标表示，A 点 (0,0)、B 点 (n,m)(n, m 为不超过 20 的整数)，同样马的位置坐标是需要给出的。现在要求你计算出卒从 A 点能够到达 B 点的路径的条数，假设马的位置是固定不动的，并不是卒走一步马走一步。

什么意思呢？我们要清楚，A 点的坐标是(0,0)！并且，卒只能向下或向右！

我们都清楚象棋中的马是如何跳的，跳的是“日”字形。看下表：以输入样例 6×6，马在 (3,3) 为例，左至右分别为 x ，上至下分别为 y。

下面顺便对样例进行一下解释：

其中 P 点为马的控制点。我们不妨把马的控制点 g[x][y] 标记为 1。

样例共有 6 条路径

大家仔细观察一下，马在第一排 (y=0) 的走法有三种：

1. 第一排走到底，再走到目标点；
2. 第一排走到第四个 0 的位置，这里大家可以看出有一种路径；
3. 第一排走到倒数第二个 0 的位置，拐个弯到达目标位置；

这里总共 3 种走法； 在第一列 (x=0) 的走法有两种，分别是：

1. 第一列走到倒数第二个 0 的位置，拐个弯到达目标位置；
2. 第一列走到第四个 0 的位置，大家可以看出有一种路径；
3. 第一列走到底，再走到目标点；

这里总共有 3 种走法；加上前面的3种，共有6种！

看到这里，大家应该明白了题意，现在我们看输入输出：

1. 输入前两个数，为棋盘的长宽；
2. 输入后两个数，为马的坐标（x,y)；

到此，题目就解读完毕了，下面分析算法：

上文已经讲到，我们将马的控制点标记为了 1，那么剩下的不是 1 的点就是可走的，因此搜索路径为：

• （如果 !g[x][y])搜索……

在此之前，先标记马的控制点，为了不让数组越界，要判断下一步的操作是否合法，具体代码如下：

    long long x2,y2,g[25][25]//全局变量
    scanf（"%lld",&x2,&y2)
    g[x2][y2]=1;
    if(x2>1 && y2!=0)g[x2-2][y2-1]=1;
    if(x2<19 && y2!=0)g[x2+2][y2-1]=1;
    if(x2>1 && y2!=20)g[x2-2][y2+1]=1;
    if(x2<19 && y2!=20)g[x2+2][y2+1]=1;
    if(x2!=0 && y2>1)g[x2-1][y2-2]=1;
    if(x2!=0 && y2<19)g[x2-1][y2+2]=1;
    if(x2!=20 && y2>1)g[x2+1][y2-2]=1;
    if(x2!=20 && y2<19)g[x2+1][y2+2]=1;

看不懂的小伙伴仔细思考一下啦~

（这一段代码我就不更新码风了大家将就看吧……）

这里告诉大家一个公式（证明度娘）

• 在平面内，从点 (0,0) 到点 (x,y) 的路径数f[x][y]=f[x-1][y]+f[x][y-1]

现在解释一下：其实就是一个简单的 DP 方程（或者说递推式），到达一个点 (x,y)，可能从 (x-1,y) 或者 (x,y-1) 走来，因此方案数为到 (x-1,y) 和到 (x,y-1) 方案的总和。

然后就可以愉快的开始搜索了，思路有两种：

1. dfs 深搜+回溯（即递归搜索）
2. 递推（或者说是 DP）

不论是递推或是递归，都要确定边界：

根据上述公式，数组不能越界对吧？

递推：

1. 若 x=0，则 f[x][y]=f[0][y-1]（自己画图思考一下）
2. 若 y=0，则 f[x][y]=f[x-1][0]
3. 当 g[x][y]=1 的时候，肯定不能搜索啦（f[x][y]=0 )

最后，写个 else （上述公式） 就好了

递归：（其实边界和递推是差不多的）

• 递归代码实现我没写，留给大家自己想吧，这里给到递推实现的代码：

• 这里还要提个醒：这题不需要高精，long long 就可以了！

代码实现：

//认真看哦，杜绝抄袭
#include<cstdio>
using namespace std;
long long f[25][25];
bool g[25][25];
//用long long就可以了，爆不掉，不需要高精
//x1为棋盘长度 y1为棋盘宽度
//x2为马的横坐标 y2为马的纵坐标
//g数组记录该点是否可走 f数组记录路线
int main() {
    int x1, y1, x2, y2; 
    scanf("%d %d", &x1, &y1);
    scanf("%d %d", &x2, &y2);
    g[x2][y2] = 1;
    //记录马的控制点
    if(x2 > 1 and y2 != 0)   g[x2 - 2][y2 - 1] = 1;//这里>1与>=2是等效的，下同
    if(x2 < 19 and y2 != 0)  g[x2 + 2][y2 - 1] = 1;//这里<19与<=18是等效的，下同
    if(x2 > 1 and y2 != 20)  g[x2 - 2][y2 + 1] = 1;
    if(x2 < 19 and y2 != 20) g[x2 + 2][y2 + 1] = 1;
    if(x2 != 0 and y2 > 1)   g[x2 - 1][y2 - 2] = 1;
    if(x2 != 0 and y2 < 19)  g[x2 - 1][y2 + 2] = 1;
    if(x2 != 20 and y2 > 1)  g[x2 + 1][y2 - 2] = 1;
    if(x2 != 20 and y2 < 19) g[x2 + 1][y2 + 2] = 1;
    //递推过程
    for(int i = 0; i <= x1; ++i) 
        for(int j = 0; j <= y1; ++j) 
            if(!g[i][j]) { //该点没被马控制
                if(i == 0 and j == 0) //递推边界1 f[0][0]=1
                    f[0][0] = 1;
                else if(i == 0 and j > 0)//递推边界2，x=0时；
                    f[0][j] = f[0][j - 1];
                else if(i > 0 and j == 0)//递推边界3，y=0时；
                    f[i][0] = f[i - 1][0];
                else
                    f[i][j] = f[i - 1][j] + f[i][j - 1];//递推核心
            }

    //最终i循环到x1位置，j循环到y1位置(x1,y1)即为目标点)则f[x1][y1]就是答案
    printf("%lld\n", f[x1][y1]);//格式化输出(lld不要写成d)
    return 0;//返回值return 0一定要写，不然比赛会出错（windows自动返回0）
}

看我写的这么辛苦的份上，点个赞好吗~

（其实后来看来代码有点繁琐，但是好理解就好了）

Update \ 2019.12.26

• 使用了 LATEX 进行渲染并更新了码风（之前的太丑了）

• 进行了一些小小的补充