[已解决]关于题目——过河卒的问题

学习编程中的Ben

这题摘自洛谷，题目详情------>https://www.luogu.com.cn/problem/P1002

有些人可能建议会让我看题解，但谢谢了，我只是想知道我代码的错误

代码如下：

// Example program
#include <iostream>
#include <string>
#include <cmath>

using namespace std;

int bx = 5, by = 5, hx, hy, z[10][2]{}, m = 1, we = 0;

void DFS(int x, int y){
   // 这行是为了调试
    cout << x << "-----" << y << "-----" << bx << endl;

    for (int i = 0; i < 9; i++){
        if (x == z[i][0] && y == z[i][1]){
            we += 0;
        }
    }
    if (x == bx && y == by){
        we += 1;
    }
    if (x < bx || y < by){
        DFS(x + 1, y);
        DFS(x, y + 1);
    }
}

int main()
{
    cin >> bx >> by >> hx >> hy;
    z[10][0] = hx;
    z[10][1] = hy;
    for (int i = -2; i <= 2; i++){
        for (int j = -2; j <= 2; j++){
            if (i == 0 || j == 0 || abs(j) == abs(i)){
                continue;
            }
            z[m][0] = hx + i;
            z[m][1] = hy + j;
            m += 1;
        }
    }
    DFS(0, 0);
    cout << we;
}

代码思路：

先求出所有马能吃到的点，即main函数中的循环
在通过递归，发现一条能走的路就将数量+1



问题：

上方我的注释中，打印了每次递归调用的值，
在我的DFS函数，递归的条件就是函数的参数(x与y)要小于B点的x和y
但经过运行，却发现x的值一直在增加，明显不符合判断


如图(我指的是x值)

                               
登录/注册后可看大图

@高山 @人造人


顺便在问一下各位，不知道为什么，我链接发不出来了，我点了那个带绿色加号的符号，也输入了要输入的，最后还是这样

最佳答案

月排行榜 / 总排行榜

zhangjinxuan

2023-1-26 21:41:37

dfs 会超，正解应该用递推，而且你的 dfs 我也觉得很奇怪

这是我 5 个月前做这道题用的代码（写的有点丑，见谅）：

#include <iostream>
using namespace std;
long long ans,x1,y1,x2,y2;
bool m[30][30];
inline void setm(int x,int y)
{
        if (x>=0&&y>=0)m[x][y]=1;
}
inline void dfs(int x,int y)
{
        if (x==x1&&y==y1)
        {
                ++ans;
                return;
        }
        //printf("%d %d %d %d\n",x,y,m[x+1][y],m[x][y+1]);
        if (x+1<=x1&&m[x+1][y]==0)
                dfs(x+1,y);
        if (y+1<=y1&&m[x][y+1]==0)
                dfs(x,y+1);
}
int main()
{

        scanf("%d%d%d%d",&x1,&y1,&x2,&y2);
        setm(x2,y2);
        setm(x2+1,y2+2);setm(x2+2,y2+1);
        setm(x2-1,y2-2);setm(x2-2,y2-1);
        setm(x2-1,y2+2);setm(x2-2,y2+1);
        setm(x2+2,y2-1);setm(x2+1,y2-2);
        dfs(0,0);
        printf("%lld",ans);
}

当 dfs 到某个坐标的时候，就分别 dfs x + 1,y 和 x, y + 1，如果新位置是马占领的地方就不 dfs 了

你可以照这个代码改一下，或者改成记忆化搜索也行

跳转到最佳答案楼层

sfqxx

我康康

学习编程中的Ben

@tommyyu @Hello.

the_ben

看不懂

sfqxx

地址应该发的出来啊
您直接把地址打出来应该就可以了

学习编程中的Ben

https://www.luogu.com.cn/problem/P1002

zhangjinxuan

dfs 会超，正解应该用递推，而且你的 dfs 我也觉得很奇怪

这是我 5 个月前做这道题用的代码（写的有点丑，见谅）：

#include <iostream>
using namespace std;
long long ans,x1,y1,x2,y2;
bool m[30][30];
inline void setm(int x,int y)
{
        if (x>=0&&y>=0)m[x][y]=1;
}
inline void dfs(int x,int y)
{
        if (x==x1&&y==y1)
        {
                ++ans;
                return;
        }
        //printf("%d %d %d %d\n",x,y,m[x+1][y],m[x][y+1]);
        if (x+1<=x1&&m[x+1][y]==0)
                dfs(x+1,y);
        if (y+1<=y1&&m[x][y+1]==0)
                dfs(x,y+1);
}
int main()
{

        scanf("%d%d%d%d",&x1,&y1,&x2,&y2);
        setm(x2,y2);
        setm(x2+1,y2+2);setm(x2+2,y2+1);
        setm(x2-1,y2-2);setm(x2-2,y2-1);
        setm(x2-1,y2+2);setm(x2-2,y2+1);
        setm(x2+2,y2-1);setm(x2+1,y2-2);
        dfs(0,0);
        printf("%lld",ans);
}

当 dfs 到某个坐标的时候，就分别 dfs x + 1,y 和 x, y + 1，如果新位置是马占领的地方就不 dfs 了

你可以照这个代码改一下，或者改成记忆化搜索也行

sfqxx

学习编程中的Ben 发表于 2023-1-26 21:35
https://www.luogu.com.cn/problem/P1002

python显示：语法错误

liuhongrun2022

sfqxx 发表于 2023-1-26 21:44
python显示：语法错误

这是C++题呀哥们

学习编程中的Ben

zhangjinxuan 发表于 2023-1-26 21:41
dfs 会超，正解应该用递推，而且你的 dfs 我也觉得很奇怪

这是我 5 个月前做这道题用的代码（写的有点丑 ...

谢了

学习编程中的Ben

zhangjinxuan 发表于 2023-1-26 21:41
dfs 会超，正解应该用递推，而且你的 dfs 我也觉得很奇怪

这是我 5 个月前做这道题用的代码（写的有点丑 ...

我其实不会dfs

zhangjinxuan

学习编程中的Ben 发表于 2023-1-27 08:43
我其实不会dfs

啊

zhangjinxuan

学习编程中的Ben 发表于 2023-1-27 08:43
我其实不会dfs

明白了：

if (x == bx && y == by){
    we += 1;
}

dfs 应该有边界条件，emm，感觉……

额, dfs 不能一直 dfs，不能是一直递归，所以你这个就无限增加

尝试在 we += 1 的后面加上 return，因为 x == bx, y == bx 就走不了了，退出

Mike_python小

你居然还会C++!

学习编程中的Ben

Mike_python小 发表于 2023-1-27 08:48
你居然还会C++!

对啊，我本来就会

Mike_python小

学习编程中的Ben 发表于 2023-1-27 09:44
对啊，我本来就会

我C++啥算法都不会

liuhongrun2022

Mike_python小 发表于 2023-1-27 09:52
我C++啥算法都不会

一样
只会Python基础的渣渣

sfqxx

liuhongrun2022 发表于 2023-1-26 21:54
这是C++题呀哥们

我**