学习编程中的Ben 发表于 2023-1-26 21:14:34

关于题目——过河卒的问题

本帖最后由 学习编程中的Ben 于 2023-1-26 21:18 编辑

这题摘自洛谷，题目详情------>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{}, 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 && y == z){
            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 = hx;
    z = 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 = hx + i;
            z = hy + j;
            m += 1;
      }
    }
    DFS(0, 0);
    cout << we;
}


代码思路：

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



问题：

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


如图(我指的是x值)


https://s1.ax1x.com/2023/01/26/pSN2b79.png


@高山 @人造人


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






sfqxx 发表于 2023-1-26 21:21:38

我康康

学习编程中的Ben 发表于 2023-1-26 21:23:16

@tommyyu @Hello.

the_ben 发表于 2023-1-26 21:23:36

看不懂{:10_266:}

sfqxx 发表于 2023-1-26 21:33:21

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

学习编程中的Ben 发表于 2023-1-26 21:35:04

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

zhangjinxuan 发表于 2023-1-26 21:41:37

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

这是我 5 个月前做这道题用的代码（写的有点丑，见谅）：
#include <iostream>
using namespace std;
long long ans,x1,y1,x2,y2;
bool m;
inline void setm(int x,int y)
{
        if (x>=0&&y>=0)m=1;
}
inline void dfs(int x,int y)
{
        if (x==x1&&y==y1)
        {
                ++ans;
                return;
        }
        //printf("%d %d %d %d\n",x,y,m,m);
        if (x+1<=x1&&m==0)
                dfs(x+1,y);
        if (y+1<=y1&&m==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 发表于 2023-1-26 21:44:59

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

python显示：语法错误

liuhongrun2022 发表于 2023-1-26 21:54:01

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

这是C++题呀哥们

学习编程中的Ben 发表于 2023-1-26 22:31:43

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

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

谢了

学习编程中的Ben 发表于 2023-1-27 08:43:28

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

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

我其实不会dfs{:10_282:}

zhangjinxuan 发表于 2023-1-27 08:44:13

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

啊{:10_277:}

zhangjinxuan 发表于 2023-1-27 08:46:31

学习编程中的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小 发表于 2023-1-27 08:48:19

你居然还会C++!{:10_257:}

学习编程中的Ben 发表于 2023-1-27 09:44:26

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

对啊，我本来就会

Mike_python小 发表于 2023-1-27 09:52:05

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

我C++啥算法都不会{:10_282:}

liuhongrun2022 发表于 2023-1-27 10:06:28

本帖最后由 liuhongrun2022 于 2023-1-27 10:08 编辑

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

一样{:10_266:}
只会Python基础的渣渣{:10_266:}

sfqxx 发表于 2023-1-27 10:25:36

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

我**
页: [1]
查看完整版本: 关于题目——过河卒的问题