连dfs都不会了

陈尚涵

草泥马，小丑了，我甜蜜的没写vis，我是该笑还是哭啊
---------------------------------------------------------------------------------------------------

https://www.luogu.com.cn/problem/P4554
这道题，我只能想到dfs
不过这不是最重要的，最重要的是我的dfs给死循环了  
找半天硬是没有发现问题，我真是越来越菜了，已经是dfs都写不好的fw了
另外说的是，这道题我没有看题解，也不打算看题解，我认为dfs应该可以做（至少能拿点分），所以只讨论关于这个代码中dfs的内容
希望大佬帮帮我
@zhangjinxuan @tommyyu @liuhongrun2022 @Wei-Yuanzhe

1. #include <iostream>
   
2. using namespace std;
   
3. int dx[] = {-1, 1, 0, 0};
   
4. int dy[] = {0, 0, -1, 1};
   
5. int map[505][505];
   
6. int n, m, sx, sy, ex, ey, ans;
   
7. void dfs(int x, int y, int v){
   
8.         for (int i = 0; i < 4; i++){
   
9.                 int xx = x + dx[i];
   
10.                 int yy = y + dy[i];
    
11.                 if (xx >= 0 && xx < n && yy >= 0 && yy < m); else continue;
    
12.                 int vv = v;
    
13.                 if (map[xx][yy] != map[x][y]) vv++;
    
14.                 if (xx == ex && yy == ey){ if (vv < ans) ans = vv; else continue; }
    
15.                 else dfs(xx, yy, vv);
    
16.         }
    
17. }
    
18. int main(){
    
19.         while (true){
    
20.                 cin >> n >> m;
    
21.                 if (n == 0 && m == 0){
    
22.                         return 0;
    
23.                 }
    
24.                 for (int i = 0; i < n; i++){
    
25.                         for (int j = 0; j < m; j++){
    
26.                                 char tmp;
    
27.                                 cin >> tmp;
    
28.                                 if (tmp == '@'){
    
29.                                         map[i][j] = 1;
    
30.                                 }
    
31.                         }
    
32.                 }
    
33.                 cin >> sx >> sy >> ex >> ey;
    
34.                 ans = 114514;
    
35.                 dfs(sx, sy, 0);
    
36.                 cout << ans << endl;;
    
37.         }
    
38.         return 0;
    
39. }

复制代码

陈尚涵

此贴是我有病，已经改分类，就别回答了

isdkz

这段代码中的死循环问题是因为在判断边界时使用了分号，导致后面的语句一直执行。应该使用大括号将语句块括起来。

另外，这段代码中的 dfs 函数只是简单的深度优先搜索，并没有使用任何剪枝技巧，因此效率较低。可以考虑使用 A* 算法等更高效的搜索算法来解决这个问题。

以下是修改后的代码：

1. #include <iostream>
   
2. #include <queue>
   
3. #include <cstring>
   
4. using namespace std;
   
5. 
   
6. const int MAXN = 505;
   
7. const int INF = 0x3f3f3f3f;
   
8. 
   
9. int dx[] = {-1, 1, 0, 0};
   
10. int dy[] = {0, 0, -1, 1};
    
11. int map[MAXN][MAXN];
    
12. int n, m, sx, sy, ex, ey, ans;
    
13. int dis[MAXN][MAXN];
    
14. 
    
15. struct Node {
    
16.     int x, y, f;
    
17.     bool operator<(const Node& other) const {
    
18.         return f > other.f;
    
19.     }
    
20. };
    
21. 
    
22. bool isValid(int x, int y) {
    
23.     return x >= 0 && x < n && y >= 0 && y < m;
    
24. }
    
25. 
    
26. void Astar() {
    
27.     priority_queue<Node> pq;
    
28.     memset(dis, INF, sizeof(dis));
    
29.     pq.push({sx, sy, 0});
    
30.     dis[sx][sy] = 0;
    
31.     while (!pq.empty()) {
    
32.         Node cur = pq.top();
    
33.         pq.pop();
    
34.         int x = cur.x, y = cur.y;
    
35.         if (x == ex && y == ey) {
    
36.             ans = dis[x][y];
    
37.             return;
    
38.         }
    
39.         if (dis[x][y] < cur.f) continue;
    
40.         for (int i = 0; i < 4; i++) {
    
41.             int nx = x + dx[ i], ny = y + dy[ i];
    
42.             if (!isValid(nx, ny)) continue;
    
43.             int nd = dis[x][y] + (map[nx][ny] != map[x][y]);
    
44.             if (nd < dis[nx][ny]) {
    
45.                 dis[nx][ny] = nd;
    
46.                 pq.push({nx, ny, nd + abs(nx - ex) + abs(ny - ey)});
    
47.             }
    
48.         }
    
49.     }
    
50. }
    
51. 
    
52. int main() {
    
53.     while (cin >> n >> m && n && m) {
    
54.         memset(map, 0, sizeof(map));
    
55.         for (int i = 0; i < n; i++) {
    
56.             for (int j = 0; j < m; j++) {
    
57.                 char tmp;
    
58.                 cin >> tmp;
    
59.                 if (tmp == '@') {
    
60.                     map[ i][j] = 1;
    
61.                 }
    
62.             }
    
63.         }
    
64.         cin >> sx >> sy >> ex >> ey;
    
65.         ans = INF;
    
66.         Astar();
    
67.         cout << ans << endl;
    
68.     }
    
69.     return 0;
    
70. }
    

复制代码

Mike_python小

你的代码中有一个问题导致了死循环：在dfs函数中，你没有对已经访问过的位置进行标记，导致程序会一直在同一个位置循环遍历。

解决方法是在进入一个新的位置之前，先将该位置标记为已访问（比如将其值设为-1），这样在下次遇到该位置时就可以跳过。

以下是对你的代码做出修改后的版本：

2. #include <iostream>
3. using namespace std;
5. int dx[] = {-1, 1, 0, 0};
6. int dy[] = {0, 0, -1, 1};
7. int map[505][505];
8. int n, m, sx, sy, ex, ey, ans;
10. void dfs(int x, int y, int v) {
11.     if (x == ex && y == ey) {
12.         if (v < ans)
13.             ans = v;
14.         return;
15.     }
17.     map[x][y] = -1;  // 标记当前位置为已访问
19.     for (int i = 0; i < 4; i++) {
20.         int xx = x + dx[i];
21.         int yy = y + dy[i];
22.         if (xx >= 0 && xx < n && yy >= 0 && yy < m && map[xx][yy] != -1) {
23.             int vv = v;
24.             if (map[xx][yy] != map[x][y])
25.                 vv++;
26.             dfs(xx, yy, vv);
27.         }
28.     }
30.     map[x][y] = 0;  // 恢复当前位置的状态
31. }
33. int main() {
34.     while (true) {
35.         cin >> n >> m;
36.         if (n == 0 && m == 0) {
37.             return 0;
38.         }
39.         for (int i = 0; i < n; i++) {
40.             for (int j = 0; j < m; j++) {
41.                 char tmp;
42.                 cin >> tmp;
43.                 if (tmp == '@') {
44.                     map[i][j] = 1;
45.                 } else {
46.                     map[i][j] = 0;
47.                 }
48.             }
49.         }
50.         cin >> sx >> sy >> ex >> ey;
51.         ans = 114514;
52.         dfs(sx, sy, 0);
53.         cout << ans << endl;
54.     }
55.     return 0;
56. }

复制代码

请根据以上修改尝试重新运行代码并测试是否成功解决了死循环的问题。如果还有其他问题，请随时提问。

球一个最佳答案谢谢啦！这对我非常重要！
回答可能有误，多多谅解！

陶远航

你的代码中的 DFS 函数有一个逻辑错误，在判断 (xx == ex && yy == ey) 时，应该将 vv < ans 的条件加在外层的 if 语句中，而不是放在内层的 else 语句中。

这样做的目的是，当 (xx == ex && yy == ey) 成立时，如果 vv 小于 ans，就更新 ans 的值；否则，直接跳过当前循环。如果将 vv < ans 放在内层的 else 语句中，当 (xx == ex && yy == ey) 成立时，如果 vv 大于等于 ans，就无法跳过当前循环，从而导致死循环。

以下是经过修改的代码：

1. #include <iostream>
   
2. using namespace std;
   
3. 
   
4. int dx[] = {-1, 1, 0, 0};
   
5. int dy[] = {0, 0, -1, 1};
   
6. int map[505][505];
   
7. int n, m, sx, sy, ex, ey, ans;
   
8. 
   
9. void dfs(int x, int y, int v) {
   
10.     for (int i = 0; i < 4; i++) {
    
11.         int xx = x + dx[ i];
    
12.         int yy = y + dy[ i];
    
13.         
    
14.         if (xx >= 0 && xx < n && yy >= 0 && yy < m) {
    
15.             int vv = v;
    
16.             if (map[xx][yy] != map[x][y])
    
17.                 vv++;
    
18.             
    
19.             if (xx == ex && yy == ey) {
    
20.                 if (vv < ans)
    
21.                     ans = vv;
    
22.             } else {
    
23.                 dfs(xx, yy, vv);
    
24.             }
    
25.         }
    
26.     }
    
27. }
    
28. 
    
29. int main() {
    
30.     while (true) {
    
31.         cin >> n >> m;
    
32.         if (n == 0 && m == 0) {
    
33.             return 0;
    
34.         }
    
35.         
    
36.         for (int i = 0; i < n; i++) {
    
37.             for (int j = 0; j < m; j++) {
    
38.                 char tmp;
    
39.                 cin >> tmp;
    
40.                 if (tmp == '@') {
    
41.                     map[ i][j] = 1;
    
42.                 }
    
43.             }
    
44.         }
    
45.         
    
46.         cin >> sx >> sy >> ex >> ey;
    
47.         ans = 114514;
    
48.         dfs(sx, sy, 0);
    
49.         cout << ans << endl;
    
50.     }
    
51.    
    
52.     return 0;
    
53. }
    

复制代码

这样修改后的代码应该能够解决死循环的问题，正常运行并给出正确结果。希望能对你有所帮助！
如果问题已经解决，请设置最佳答案

tommyyu

原来不止我一个

陈尚涵

tommyyu 发表于 2023-9-24 20:35
原来不止我一个

我承认我是小丑，开学后太久没写题退化了，原来没写vis数组

liuhongrun2022

陈尚涵 发表于 2023-9-24 20:39
此贴是我有病，已经改分类，就别回答了

鱼币给我吧

陈尚涵

liuhongrun2022 发表于 2023-9-24 20:42
鱼币给我吧

给我个原因说服自己

liuhongrun2022

陈尚涵 发表于 2023-9-24 20:44
给我个原因说服自己

因为你无法取回悬赏，并且如果给我了，可以给你一些

陈尚涵

liuhongrun2022 发表于 2023-9-24 20:46
因为你无法取回悬赏，并且如果给我了，可以给你一些

等于说这样还是我亏了，但你赚了，这可不行

Wei-Yuanzhe

普及+提高

Wei-Yuanzhe

我还是泰拉了

liuhongrun2022

陈尚涵 发表于 2023-9-24 20:51
等于说这样还是我亏了，但你赚了，这可不行

我要15鱼币，给你25

liuhongrun2022

陈尚涵 发表于 2023-9-24 20:51
等于说这样还是我亏了，但你赚了，这可不行

给的话你还可以得到，不给可一分不得

琅琊王朝

1. #include<iostream>
   
2. #include<cstdio>
   
3. #include<deque>
   
4. using namespace std;
   
5. char sz[505][505];
   
6. long long a[500][500];
   
7. long long n,m,qx,qy,zx,zy;
   
8. long long fx[4]={0,0,1,-1};//控制移动的数组
   
9. long long fy[4]={1,-1,0,0};
   
10. deque<int>qz;//3个双端队列
    
11. deque<int>xd;
    
12. deque<int>yd;
    
13. long long x,y,z;
    
14. void sddl()
    
15. {
    
16.     while(xd.empty()!=true&&yd.empty()!=true)//不空不走
    
17.     {
    
18.         x=xd.front();//这个是获取队列的头部元素
    
19.         y=yd.front();
    
20.         z=qz.front();
    
21.         if(x==zx&&y==zy)
    
22.         {
    
23.             while (xd.empty()!=true)xd.pop_front();//清空队列，我之前因为没清空疯狂80分
    
24.             while (yd.empty()!=true)yd.pop_front();
    
25.             while (qz.empty()!=true)qz.pop_front();
    
26.             cout<<z<<endl;
    
27.             return;
    
28.         }
    
29.         xd.pop_front();
    
30.         yd.pop_front();
    
31.         qz.pop_front();
    
32.         for(int i=0;i<4;i++)
    
33.         {
    
34.             if(x+fx[i]>=0&&x+fx[i]<n&&y+fy[i]>=0&&y+fy[i]<m)//判断越界
    
35.             {
    
36.                 if(a[x+fx[i]][y+fy[i]]==0)//标记来过没
    
37.                 {
    
38.                     a[x+fx[i]][y+fy[i]]=1;
    
39.                     if(sz[x+fx[i]][y+fy[i]]==sz[x][y])//走这个不需要花费，走起
    
40.                     {
    
41.                         xd.push_front(x+fx[i]);//这个是插入到头部的意思
    
42.                         yd.push_front(y+fy[i]);
    
43.                         qz.push_front(z);
    
44.                     }else//花费1点
    
45.                     {
    
46.                         xd.push_back(x+fx[i]);//这个是插入到尾部的意思
    
47.                         yd.push_back(y+fy[i]);
    
48.                         qz.push_back(z+1);
    
49.                     }
    
50.                 }
    
51.             }
    
52.         }
    
53.     }
    
54.     return;
    
55. }
    
56. int main()
    
57. {
    
58.     while(true)
    
59.     {
    
60.         scanf("%lld%lld",&n,&m);
    
61.         if(n==0&&m==0)
    
62.         {
    
63.             return 0;
    
64.         }
    
65.         for(int i=0;i<n;i++)
    
66.         {
    
67.             for(int j=0;j<m;j++)
    
68.             {
    
69.                 cin>>sz[i][j];
    
70.                 a[i][j]=0;
    
71.             }
    
72.         }
    
73.         scanf("%lld%lld%lld%lld",&qx,&qy,&zx,&zy);
    
74.         a[qx][qy]=1;//省一下
    
75.         xd.push_front(qx);//这个是插入到头部的意思
    
76.         yd.push_front(qy);
    
77.         qz.push_front(0);
    
78.         sddl();
    
79.     }
    
80.     return 0;
    
81. }

复制代码