注册 登录
编程论坛 → C语言论坛

递归的迷宫问题，请问代码错在什么地方

komorebi0110 发布于 2020-04-19 21:08， 3579 次点击
A maze is to be represented by a 12*12 array composed of three values: Open, Wall, or Exit. There is one exit from the maze. Write a program to determine whether it is possible to exit the maze from the starting point (any open square can be a starting point). You may move vertically and horizontally to any adjacent open square(左右上下四个方向). You may not move to a square containing a wall. The input consists of a series of 12 lines of 12 characters each, representing the contents of each square in the maze. The characters are O, W, or E.
【输入】 12×12的迷宫方阵，每个格子的可能取值有：O, W, or E，输入数据能够确保迷宫只有一个出口。
任意3个起点的坐标,格式如下(x,y)。其中x为纵坐标，y为横坐标，起始坐标从左上角的格子开始，坐标起始值为0.
【输出】
起点到出口的最短路径长度（经过多少个方格），若起点无法到达出口则输出-1。起始节点和结束节点都算入路径长度的计算。

例如：
【输入】
O W O W O W O O W O W O
O W O W W W W O W O O E
O W W W O O O O O O O O
W W W O O O O W W W O W
O O O O W W W O O O O O
O O W O W O W O W O W W
O W W O O O W W O O O W
O O W O O W W W O O O O
O O O W O O O O W W W W
W W W O O O O W W W O O
O W W W W O O O O O W W
W W W O O O O O W W W W
(0,0) (5,7) (7,8)
【输出】
-1 9 10
【解释】
输出表示第一个点（0，0）无法到达出口；
第二个点（5，7）到达出口的最短路径是9；
第三个点（7，8）到达出口的最短路径是10；
11 回复
#2
komorebi01102020-04-19 21:11
#include<stdio.h>
#include<iostream>
using namespace std;
class migong
{  public:
    migong();
    void initial();
    int jisuan();
    void seten();
    void solved(int x,int y,int n);
private:
    int Migong[12][12];
    int step;
    int Ex;
    int Ey;
};
migong::migong()
{
    step=1000000;
}
void migong::initial()
{
    step=1000000;
}
void migong::seten()
{
    for(int i = 0; i<12; i++)
 {
  for(int j = 0; j < 12; j++)
  {
   char temp;
   cin>>temp;
   if(temp=='W')
            Migong[i][j]=1;
            else if(temp=='E')
            {
                Ex=i;
                Ey=j;
                Migong[i][j]=0;
            }
   else if(temp=='O')
    Migong[i][j]=0;
    }
  }


}

void migong::solved(int x,int y,int n)
{
 if(Migong[x][y]!=0)
  return;
 if(x==Ex&&y==Ey)
 {

  step=min(step,n);
  return;
 }
if(x > 0)
solved(x-1,y,n+1);
 if(y > 0)
 solved(x,y-1,n+1);
 if(x < 11)
solved(x+1,y,n+1);
 if(y < 11)
 solved(x,y+1,n+1);
 Migong[x][y]=0;
 return;
}
int migong::jisuan()
{
    return step;
}
int main()
{
    migong A;
    A.seten();
    for(int i=0;i<3;i++)
    {     A.initial();
        int x,y;
        char c;
        cin>>c>>x>>c>>y>>c;
        A.solved(x,y,0);
        if(A.jisuan()==1000000)
            cout << "-1";
   else
    cout << A.jisuan()+1 <<' ';
     }
}

//最近刚学了八皇后问题，知道什么叫回溯...看不出来问题在哪里QAQ
#3
wmf20142020-04-19 23:32
你的递归算法有问题，最后是溢出退出。
迷宫求最短路径适合用广搜，深搜也行，关键是记录步数。我最大限度保留你的代码框架，重新写的递归后代码如下，楼主可参考注释加深理解：
程序代码：
#include<iostream>
using namespace std;
class migong
{
public:
    migong();
    void initial()
    {
        step=200;
        for(int i=0;i<12;i++)
            for(int j=0;j<12;j++)
                if(Migong[i][j]>=0&&Migong[i][j]<step)Migong[i][j]=2000;
    }
    int jisuan();
    void seten();
    void solved(int,int,int);
private:
    int Migong[12][12];
    int step;
};
migong::migong()
{
    step=200;
    //由于最多也只有12*12=144步，同时1000和2000有特殊用途，我的算法要求step初始值只能大于144且小于1000
}
void migong::seten()
{
    for(int i = 0; i<12; i++)
    {
        for(int j = 0; j < 12; j++)
        {
            char temp;
            cin>>temp;
            if(temp=='W')
                Migong[i][j]=-1;
            else if(temp=='E')
                Migong[i][j]=1000;  //出口值
            else if(temp=='O')
                Migong[i][j]=2000;  //通路初始值，求最短路径就必须设置一个大于12*12的值
        }
    }
}

void migong::solved(int x,int y,int n)
{
    int i,j;
    if(x<0||y<0||x>11||y>11||n>step||n>Migong[x][y])return ;  
    //坐标不合格或步数大于坐标位置值或步数大于step返回找下一条路
    if(Migong[x][y]==1000)
    {//找到出口
        step=n;
        return;
    }
    Migong[x][y]=n;
    for(i=0;i<4;i++)
        solved(x-1+(i*2+1)%3,y-1+(i*2+1)/3,n+1);  //四个方向递归
}
int migong::jisuan()
{
    return step;
}
int main()
{
    migong A;
    A.seten();
    for(int i=0;i<3;i++)
    {
        int x,y,c;
        cin>>x>>y;
        A.initial();
        A.solved(x,y,0);
        c=A.jisuan();
        if(c>144)c=-2;
        cout << c+1 <<' ';
    }
    cout << endl;
    return 0;
}
#4
forever742020-04-19 23:52
嗯，楼主的代码会在非墙的走廊里来回走个没完。
所以会溢栈。
#5
wmf20142020-04-20 08:09
回复 3楼 wmf2014
忘了说明，我的输入数据在输入入口坐标是直接输入，不需要单独要cin>>c，具体数据如下：
O W O W O W O O W O W O
O W O W W W W O W O O E
O W W W O O O O O O O O
W W W O O O O W W W O W
O O O O W W W O O O O O
O O W O W O W O W O W W
O W W O O O W W O O O W
O O W O O W W W O O O O
O O O W O O O O W W W W
W W W O O O O W W W O O
O W W W W O O O O O W W
W W W O O O O O W W W W
0 0 5 7 7 8


把这些数据放到一个文本文件里，重定向该文本就可以了，这样调试时就不需要一个个地用键盘输入。
#6
return_02020-04-20 09:13
重复性剪枝
#7
return_02020-04-20 09:18
这道题也不适合你的算法，适合搜索算法
#8
komorebi01102020-04-20 15:11
//orz虽然不知道什么叫重复性剪枝，但我发现我少写了一行，改了一下能出结果
//我开头写的是什么我也不知道QAQ
#include<stdio.h>
#include<iostream>
using namespace std;
class migong
{  public:
    migong();
    void initial();
    int jisuan();
    void seten();
    void solved(int x,int y,int n);
private:
    int Migong[12][12];
    int step;
    int Ex;
    int Ey;
};
migong::migong()
{
    step=1000000;
}
void migong::initial()
{
    step=1000000;
}
void migong::seten()
{
    for(int i = 0; i<12; i++)
 {
  for(int j = 0; j < 12; j++)
  {
   char temp;
   cin>>temp;
   if(temp=='W')
            Migong[i][j]=1;
            else if(temp=='E')
            {
                Ex=i;
                Ey=j;
                Migong[i][j]=0;
            }
   else if(temp=='O')
    Migong[i][j]=0;
    }
  }


}

void migong::solved(int x,int y,int n)
{
 if(Migong[x][y]!=0)
  return;
 if(x==Ex&&y==Ey)
 {

  step=min(step,n);
  return;
 }
 Migong[x][y]=1;
if(x > 0)
solved(x-1,y,n+1);
 if(y > 0)
 solved(x,y-1,n+1);
 if(x < 11)
solved(x+1,y,n+1);
 if(y < 11)
 solved(x,y+1,n+1);
 Migong[x][y]=0;

}
int migong::jisuan()
{
    return step;
}
int main()
{
    migong A;
    A.seten();
    for(int i=0;i<3;i++)
    {     A.initial();
        int x,y;
        char c;
        cin>>c>>x>>c>>y>>c;
        A.solved(x,y,0);
        if(A.jisuan()==1000000)
            cout << "-1"<<' ';
   else
    cout << A.jisuan()+1 <<' ';
     }
}
#9
return_02020-04-20 21:25
回复 8楼 komorebi0110
重复性剪枝我给你解释一下，先从剪枝算法说起
剪枝剪枝，顾名思义，就是减少搜索算法的可能性（枝叶数），从而加快速度。虽然大家都说“剪枝算法”，但是我个人觉得他不算是算法，常见的剪枝有以下几种：
可行性剪枝
最优性剪枝
重复性剪枝


前二者我就不说了，今天主要是要讲明第三者。

重复性剪枝，就是用flag，或flag数组来防止dfs，bfs等算法的重复，因此得名重复性剪枝。
重复性剪枝一般情况是必须插入的，因为很多情况下如果没有重复性剪枝，就像这道题，你的角色就会在走廊里来回走，后果不堪设想。

这道题正确采用剪枝的方法应该是数组吧，我贴一下核心代码：
在此我说明一下，这道题其实不适合，真的不适合用回溯。我也不写广搜了，这道题最好用dfs（深搜）：
vis[x][y]=true;
dfs(x+dx[i],y+dx[i]);
vis[x][y]=false;
dfs套用dfs时按这个方式套用，前面要有一个if，里面说明vis数组为false才能继续探索。

这道题所用的是标记法，非常实用的剪枝，如果还有疑问告诉我哦
#10
komorebi01102020-04-21 11:28
回复 9楼 return_0
emmm因为我水平太烂了加上自学能力极弱看得一知半解，现在我数据结构课刚学到递归，dfs我还没接触过，不过这学期应该会讲到这类题，等讲到dfs我应该就能明白了，谢谢大神！
#11
wmf20142020-04-21 22:52
回复 10楼 komorebi0110
楼主还是要立足于学习书本知识为好，论坛里接受的很多信息不准确（也包括我输出的信息），容易被误导。
1，关于深搜和广搜，可参考https://这篇文章，里面说的很清楚：深搜适合穷尽所有路线方案，广搜适合找最短路线。形象地理解就是广搜相当于以出发点为圆心，一圈圈往外搜索，直到找到目标，很显然最长路线就是圆心到目标为半径所包含的圆内所有点的一半。而深搜是从出发点先往一个方向搜，直到搜不动才换方向，最终会穷尽能搜到的所有点，这个面积肯定比最短距离为半径的圆的面积大。
2，只要使用深搜算法，即使不用递归，也必然会回溯。DFS最后都会回到出发点，因为该算法必须清除路线标记，否则得不到所有解，也就可能得不到最短路径。而广搜比较适合用循环解决，即使用递归也不需要清除标记就能得到最短路径。
3，关于剪枝，楼主和10楼代码类似，深搜时打标记，回溯时清除标记，根本没有剪枝。剪枝行为一般类似于动态规划的反过程，动态规划是记住并使用层层递进过程中的最优解，而剪枝是记住并丢弃达不到目标或最差解。我3楼的代码就用了两种方法剪枝，一是当深搜步数大于当前最少步数时，就不再深搜，第二种是当走别人走过的路且交叉点步数大于别人在这个位置的步数时不再深搜。通过比较，我三个起点坐标递归的次数分别是13、2161、2233，而楼主的递归次数分别是9、16674、49885，显然通过剪枝后递归的次数只有不剪枝的1/23，至于为什么第一个递归次数多于楼主，是算法上细微差别导致的，楼主是在递归前判断坐标合法性，不合法的没进递归，我的是在递归后判断，不管是否合法先递归再说，如果起点坐标在边缘，自然就多了些。
以上观点仅供参考。
#12
komorebi01102020-04-25 17:23
回复 11楼 wmf2014
谢谢！
1
©2025, BC-CN.NET
电脑版