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

学习编程中的Ben

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

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

代码如下：

1. 
   
2. // Example program
   
3. #include <iostream>
   
4. #include <string>
   
5. #include <cmath>
   
6. 
   
7. using namespace std;
   
8. 
   
9. int bx = 5, by = 5, hx, hy, z[10][2]{}, m = 1, we = 0;
   
10. 
    
11. void DFS(int x, int y){
    
12.    // 这行是为了调试
    
13.     cout << x << "-----" << y << "-----" << bx << endl;
    
14. 
    
15.     for (int i = 0; i < 9; i++){
    
16.         if (x == z[i][0] && y == z[i][1]){
    
17.             we += 0;
    
18.         }
    
19.     }
    
20.     if (x == bx && y == by){
    
21.         we += 1;
    
22.     }
    
23.     if (x < bx || y < by){
    
24.         DFS(x + 1, y);
    
25.         DFS(x, y + 1);
    
26.     }
    
27. }
    
28. 
    
29. int main()
    
30. {
    
31.     cin >> bx >> by >> hx >> hy;
    
32.     z[10][0] = hx;
    
33.     z[10][1] = hy;
    
34.     for (int i = -2; i <= 2; i++){
    
35.         for (int j = -2; j <= 2; j++){
    
36.             if (i == 0 || j == 0 || abs(j) == abs(i)){
    
37.                 continue;
    
38.             }
    
39.             z[m][0] = hx + i;
    
40.             z[m][1] = hy + j;
    
41.             m += 1;
    
42.         }
    
43.     }
    
44.     DFS(0, 0);
    
45.     cout << we;
    
46. }
    

复制代码

代码思路：

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



问题：

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


如图(我指的是x值)

                               
登录/注册后可看大图

@高山 @人造人


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

最佳答案

月排行榜 / 总排行榜

zhangjinxuan

2023-1-26 21:41:37

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

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

1. #include <iostream>
   
2. using namespace std;
   
3. long long ans,x1,y1,x2,y2;
   
4. bool m[30][30];
   
5. inline void setm(int x,int y)
   
6. {
   
7.         if (x>=0&&y>=0)m[x][y]=1;
   
8. }
   
9. inline void dfs(int x,int y)
   
10. {
    
11.         if (x==x1&&y==y1)
    
12.         {
    
13.                 ++ans;
    
14.                 return;
    
15.         }
    
16.         //printf("%d %d %d %d\n",x,y,m[x+1][y],m[x][y+1]);
    
17.         if (x+1<=x1&&m[x+1][y]==0)
    
18.                 dfs(x+1,y);
    
19.         if (y+1<=y1&&m[x][y+1]==0)
    
20.                 dfs(x,y+1);
    
21. }
    
22. int main()
    
23. {
    
24. 
    
25.         scanf("%d%d%d%d",&x1,&y1,&x2,&y2);
    
26.         setm(x2,y2);
    
27.         setm(x2+1,y2+2);setm(x2+2,y2+1);
    
28.         setm(x2-1,y2-2);setm(x2-2,y2-1);
    
29.         setm(x2-1,y2+2);setm(x2-2,y2+1);
    
30.         setm(x2+2,y2-1);setm(x2+1,y2-2);
    
31.         dfs(0,0);
    
32.         printf("%lld",ans);
    
33. }

复制代码

当 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 个月前做这道题用的代码（写的有点丑，见谅）：

1. #include <iostream>
   
2. using namespace std;
   
3. long long ans,x1,y1,x2,y2;
   
4. bool m[30][30];
   
5. inline void setm(int x,int y)
   
6. {
   
7.         if (x>=0&&y>=0)m[x][y]=1;
   
8. }
   
9. inline void dfs(int x,int y)
   
10. {
    
11.         if (x==x1&&y==y1)
    
12.         {
    
13.                 ++ans;
    
14.                 return;
    
15.         }
    
16.         //printf("%d %d %d %d\n",x,y,m[x+1][y],m[x][y+1]);
    
17.         if (x+1<=x1&&m[x+1][y]==0)
    
18.                 dfs(x+1,y);
    
19.         if (y+1<=y1&&m[x][y+1]==0)
    
20.                 dfs(x,y+1);
    
21. }
    
22. int main()
    
23. {
    
24. 
    
25.         scanf("%d%d%d%d",&x1,&y1,&x2,&y2);
    
26.         setm(x2,y2);
    
27.         setm(x2+1,y2+2);setm(x2+2,y2+1);
    
28.         setm(x2-1,y2-2);setm(x2-2,y2-1);
    
29.         setm(x2-1,y2+2);setm(x2-2,y2+1);
    
30.         setm(x2+2,y2-1);setm(x2+1,y2-2);
    
31.         dfs(0,0);
    
32.         printf("%lld",ans);
    
33. }

复制代码

当 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

明白了：

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

复制代码

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++题呀哥们

我**