论坛 › 萌新交流区 › 迷宫问题

墨笠阳 发表于 2023-7-2 16:43:19

迷宫问题

本帖最后由 墨笠阳 于 2023-7-9 09:35 编辑



调试时，有些数据运行结果是对的，但会报这个错误，有些数据运行结果有误，求大佬不吝指教{:10_266:}{:10_266:}{:10_266:}
#define MAX_STACK_FindPath_SIZE 1275
#define MAX_ROW 50
#define MAX_COL 50


//位置
typedef structposition {
      int x = 0;
      int y = 0;
      int pos = 1;//1，有障碍      0 无障碍      
      int step = 0;//1 已访问 0 未访问，-1 回退时再次访问
}position;

typedef struct {
      position* base;
      position* top;
      int stacksize;
}Stack;

//初始化
int InitStack_FindPath(Stack& S) {
      S.base = new position;
      if (!S.base)
                return 0;
      else {
                S.top = S.base;
                S.stacksize = MAX_STACK_FindPath_SIZE;
                return 1;
      }
}

int InitStack_maze(Stack& S) {
      int max = MAX_ROW * MAX_COL;
      S.base = new position;
      if (!S.base)
                return 0;
      else {
                S.top = S.base;
                S.stacksize = max;
                return 1;
      }
}

//入栈
int Push(Stack& S, position p) {
      if (S.top - S.base == S.stacksize)//栈满
                return 0;
      else {               
                *S.top = p;
                S.top++;
                return 1;
      }
}

//出栈
int Pop(Stack& S, position& p) {
      if (S.top == S.base)
                return 0;
      else {
               
                p = *(S.top - 1);

                /*
                p.x = (S.top - 1)->x;
                p.y = (S.top - 1)->y;
                p.pos = (S.top - 1)->pos;/**/
                S.top--;
                return 1;
      }
}
#include <iostream>
#include <malloc.h>
#include"struct.h"
using namespace std;

void Creat_maze(int row, int col, Stack& maze);
int FindPath(Stack& maze, Stack& pass, position* p,position start, position end, int row, int col);
int main() {
      position* p;//指向当前起点的指针
      Stack path;//通路
      Stack maze;//迷宫
      int m, n;//行、列
      
      //初始化指针p
      do {
                p = new position;
      } while (!p);
      //初始化path栈、maze栈
      InitStack_FindPath(path);
      InitStack_maze(maze);

      cout << "迷宫规格m*n:\n" << "请输入m,n的值\n" << endl;
      cin >> m >> n;

      position start = { 0 ,0 ,0 };//入口
      position end = { m - 1 , n - 1, 0 };//出口

      cout << "\n1 表示不可通行，0 表示可通行\n" ;
      cout << "默认入口为第一个元素，出口为最后一个元素，" << "请输入迷宫元素\n" << endl;

      //构建迷宫m*n
      Creat_maze(m, n, maze);

      p = maze.base;
      Push(path, *p);

      if (FindPath(maze,path, p,start, end, m, n)) {
                p = path.base;
                cout << "通道为：" << endl;
                while (p != path.top) {
                        cout << "\t(" << p->x << "," << p->y << ")" << endl;
                        p++;
                }
                delete p;
                return 1;
      }
      else {
                cout << "此迷宫无通路！" << endl;
                delete p;
                return 0;
      }

}
void Creat_maze(int row, int col, Stack& maze) {
      int i, j;
      position p;

      for (i = 0; i < row; i++) {
               
                p.x = i;
                for (j = 0; j < col; j++) {
                        p.y = j;
                        cin >> p.pos;
                        Push(maze, p);                        
                }               
      }
      
}

/*
* 通道函数：
*      从起点出发，将起点入栈，标记其为已访问，然后依次对当前位置上，左，下，右进行深度遍历,
*      .1.若 p 所指的 position 的 上（左下右）可通，即 pos=0,且未被访问，即pos=0,则入栈pass
*   p.step=1 ,将新位置设为新起点，继续遍历,直到无前路
*
*      此过程中，如果访问到end，return 1,否则继续访问，直到遍历完成，return 0
*/
int FindPath(Stack& maze, Stack& path, position* per, position start ,position end, int row, int col) {
      
      while (per!=&end) {//per未指向end
                //向上
                {
                        per = per - col;
                        if (!per && per->pos == 0 && per->step == 0) {//!per未越上边界,per->pos==0无障碍，per->step == 0未访问
                                                      //per->pos = 1;
                        //if (per->pos == 0 && per->step == 0) {
                              per->step = 1;
                              Push(path, *per);
                                                //FindPath(maze, path, per, start,end, row, col);
                              if (FindPath(maze, path, per, start, end, row, col)) {
                                        return 1;
                              }
                              else {
                                        return 0;
                              }
                        }
                        else
                              per = per + col;
                }
                //向左
                {
                        position p=*per;
                        per = per - 1;
                        if (!per&&p.x==per->x && per->pos == 0 && per->step == 0) {
                              
                              per->step = 1;
                              Push(path, *per);
                              
                              if (FindPath(maze, path, per, start, end, row, col)) {
                                        return 1;
                              }
                              else {
                                        return 0;
                              }
                        }
                        else
                              per = per + 1;
                }
                //向下
                {
                        per = per + col;
                        if (!(per->x==0&&per->y==0&&per->pos==1) && per->pos == 0 && per->step == 0) {
                              per->step = 1;
                              Push(path, *per);                              
                              if (FindPath(maze, path, per, start, end, row, col)) {
                                        return 1;
                              }
                              else {
                                        return 0;
                              }
                        }
                        else
                              per = per - col;
                }
                //右
                {
                        position p=*per;
                        per = per + 1;
                        if (!(per->x == 0 && per->y == 0 && per->pos == 1)&&p.x==per->x && per->pos == 0 && per->step == 0) {
                              //p.x==per->x未到右界,per->pos==0无障碍且未访问
                              per->step = 1;
                              Push(path, *per);                        
                              if (FindPath(maze, path, per, start, end, row, col)) {
                                        return 1;
                              }
                              else {
                                        return 0;
                              }
                        }
                        else
                              per = per - 1;
                }
                // 1,per==end,结束，有通路，，return 1
                // 2,per!=end,回退：pop(FindPath,tem),(maze.base + (tem.x * row + tem.y))->step = -1
                //退一格看一眼 上左下右
                //FindPath(maze, FindPath, per, end, row, col);
                // 直到per==end,有通路，结束
                // 或者back==start，无通路，结束
                {
                        if (per->x == end.x && per->y == end.y) {                              
                              return 1;                              
                        }
                        else {
                              position tem;
                              Pop(path, tem);
                              //cout << (path.top - 1)->x<< (path.top - 1)->y<<"\t";//输出回退后新栈顶元素，测试Pop(),经检验POp()无误
                              if (tem.x == start.x && tem.y == start.y && tem.pos == 0) {
                                        return 0;
                              }                              
                              else {                                                                        
                                        per->x = (path.top - 1)->x;
                                        per->y = (path.top - 1)->y;
                                        per->pos = (path.top - 1)->pos;
                                        per->step = (path.top - 1)->step;
                                        per = maze.base + (per->x) * col + (per->y);                        
                                        if (FindPath(maze, path, per, start, end, row, col)) {
                                                return 1;
                                        }
                                        else {
                                                return 0;
                                        }
                              }
                        }
                        
                }

      }

      //per 指向了终点
      return 1;

}

isdkz 发表于 2023-7-2 16:46:06

你的代码中的问题可能是来自于内存溢出、堆栈溢出、数组越界等问题，但是不幸的是，根据你的问题描述，很难确定确切的错误来源。这里有一些我觉得可能存在问题的地方：

1. 边界检查问题：你在处理“向上”、“向左”、“向下”、“向右”方向的时候，并没有进行充分的边界检查。比如在“向上”操作中，你是通过减去一个“列”数量的值来向上移动的，但是并没有判断当前位置是否在第一行，可能会导致越界访问。同理，“向左”、“向右”也存在同样的问题。

2. 内存管理问题：在main()函数中，你使用了 new 创建了一个 position 对象的指针，但是在函数结束的时候并没有释放它。并且在 FindPath() 函数的递归调用中也没有释放这个指针。这可能会导致内存泄漏。

3. 空指针访问：在 FindPath() 函数中， while(per!=&end) 的判断可能会出现问题。因为 per 可能不会指向 end ，这可能会造成无限循环。同时，如果 per 成为了空指针，程序可能会崩溃。

我建议你按照以下步骤进行调试：

1. 确保没有越界访问：对于每一次访问数组或者指针操作，都要确保没有越过其边界。

2. 检查内存管理：确保为每一个使用 new 分配的内存都有一个相应的 delete 来释放它。

3. 检查指针的有效性：在使用指针之前，确保它们已经被正确初始化并且没有被意外修改。

希望这些建议能对你有所帮助。如果还有其他的错误或者更详细的错误信息，欢迎继续提问。

sfqxx 发表于 2023-7-2 16:46:40

isdkz 发表于 2023-7-2 16:46
你的代码中的问题可能是来自于内存溢出、堆栈溢出、数组越界等问题，但是不幸的是，根据你的问题描述，很难 ...

我的 gpt 显示消息太长了{:10_254:}

isdkz 发表于 2023-7-2 16:48:23

sfqxx 发表于 2023-7-2 16:46
我的 gpt 显示消息太长了

现在官方的gpt应该加强了，之前也不行

sfqxx 发表于 2023-7-2 18:03:31

isdkz 发表于 2023-7-2 16:48
现在官方的gpt应该加强了，之前也不行

我听说翻 墙次数多了会触犯法律规定

isdkz 发表于 2023-7-2 18:23:42

sfqxx 发表于 2023-7-2 18:03
我听说翻 墙次数多了会触犯法律规定

{:10_249:}

sfqxx 发表于 2023-7-2 18:30:57

isdkz 发表于 2023-7-2 18:23


真的，所以我不敢

陶远航 发表于 2023-7-2 20:28:25

根据您提供的代码，很可能出现“Debug Assertion Failed”的原因是访问了无效的内存地址。这可能是由于在使用Pop函数时，出栈时访问了已被删除的指针的错误。

在FindPath函数的回退部分，您使用了Pop函数将栈顶元素弹出，并将其赋值给per指针。但是，在此之后，您又尝试通过per->x和per->y访问已经出栈的位置。这可能导致访问无效的内存。

要解决这个问题，您可以在执行Pop函数之前将栈顶元素保存到临时变量中，然后使用临时变量进行相关操作。

下面是对FindPath函数回退部分的修改：

{
    if (per->x == end.x && per->y == end.y) {
      return 1;
    }
    else {
      position tem;
      Pop(path, tem);
      if (tem.x == start.x && tem.y == start.y && tem.pos == 0) {
            return 0;
      }
      else {
            per = path.top - 1;// 使用栈顶元素进行回退
            per = maze.base + (per->x) * col + (per->y);
            if (FindPath(maze, path, per, start, end, row, col)) {
                return 1;
            }
            else {
                return 0;
            }
      }
    }
}

通过上述修改，应该可以避免访问无效的内存地址，并解决“Debug Assertion Failed”的问题。

歌者文明清理员 发表于 2023-7-2 22:17:27

sfqxx 发表于 2023-7-2 18:30
真的，所以我不敢

www.github.com/dddddgz/cn-internet-bad

###为了不使论坛被墙掉发在github###

编程追风梦 发表于 2023-7-3 10:28:01

根据提供的代码，我注意到您在 `FindPath` 函数中存在一个问题。在递归调用 `FindPath` 时，您在参数列表中将 `per` 传递给了 `end`，导致了不正确的递归调用。这会导致结果出错或产生异常。

下面是相关代码片段，我已经标出了问题所在：

//错误的递归调用
if (FindPath(maze, path, per, end, row, col)) {
    return 1;
}
else {
    return 0;
}


为了修复这个问题，您应该将 `end` 替换为 `start`，如下所示：

if (FindPath(maze, path, per, start, end, row, col)) {
    return 1;
}
else {
    return 0;
}


此外，还有几个注意事项：

1. 在 `Creat_maze` 函数中，您可以将 `Push(maze, p);` 放在内循环之外，以避免重复入栈。

2. 在 `FindPath` 函数中，`per = per + col;` 和 `per = per - col;` 这两行代码的位置需要调整，以确保在计算新位置之前将 `per` 恢复到原始位置。

请注意这些修正，并再次运行您的代码进行测试。

如果回答对你有帮助，给个最佳答案吧，求求了

墨笠阳 发表于 2023-7-9 09:33:08

isdkz 发表于 2023-7-2 16:46
你的代码中的问题可能是来自于内存溢出、堆栈溢出、数组越界等问题，但是不幸的是，根据你的问题描述，很难 ...

谢谢您的回复，经过调试，我发现
1.初始化栈时，确实成功开辟了数组空间，可是指向栈内元素的指针 p 和 per，在 p = maze.base 之后，也为空，导致运行时 per 始终不向上和向左遍历
2.发生数组越界时，向上越界多为设定的position类型元素的默认值，向左越界时多为随机数值，如x= 40000      y= 0    pos= 153      step= -33686019，不知道为什么
3.内存管理问题：原先我使用new 开辟了一个position类型大小的空间，并将其首地址赋给了p,经过您的提醒，我检查了全文，补全了delete，可是仍然报了“Debug Assertion Failed”的错误，后来误打误撞把
p = new position;
        while (!p) {
                delete p;
                p = new position;
                //最终这个p将在程序结束时delete
        }
及对应的delete删除，未报该错误了，却不知道是为什么
4.在 FindPath()函数中， while(per!=&end)的判断确实可能出现问题了，因为&end未声明是maze栈出口的地址，只是存放了出口的 x ， y ,pos 等信息，现已将 end 和 start 改成指针类型，并使其分别指向 maze 栈的出口和入口
以上是我的新困惑，请不吝赐教
以下为修改后的代码
#include<malloc.h>
#define MAX_STACK_FindPath_SIZE 1275
#define MAX_ROW 50
#define MAX_COL 50


//位置
typedef structposition {
    int x = 0;
    int y = 0;
    int pos = 1;//1，有障碍      0 无障碍      
    int step = 0;//1 已访问 0 未访问，-1 回退时再次访问
}position;

typedef struct {
    position* base;
    position* top;
    int stacksize;
}Stack;

//初始化
int InitStack_FindPath(Stack& S) {
    S.base = new position;
    if (!S.base)
      return 0;
    else {
      S.top = S.base;
      S.stacksize = MAX_STACK_FindPath_SIZE;
      return 1;
    }
}

int InitStack_maze(Stack& S) {
    int max = MAX_ROW * MAX_COL;
    S.base = new position;
    if (!S.base)
      return 0;
    else {
      S.top = S.base;
      S.stacksize = max;
      return 1;
    }
}

//入栈
int Push(Stack& S, position p) {
    if (S.top - S.base == S.stacksize)//栈满
      return 0;
    else {
      *S.top = p;
      S.top++;
      return 1;
    }
}

//出栈
int Pop(Stack& S, position& p) {
    if (S.top == S.base)
      return 0;
    else {
      p = *(S.top - 1);
      S.top--;
      return 1;
    }
}
#include<iostream>
#include"struct.h"
using namespace std;

void Creat_maze(Stack& maze, int row,int col);
int FindPath(Stack& maze, Stack& path, position* p, position* start,position* end,int row,int col);
int main() {
        Stack maze;
        Stack path;
        position* p;
        position* start, * end;
        int row, col;
        InitStack_FindPath(path);
        InitStack_maze(maze);
        cout << "请输入行数：" ;
        cin >> row;
        cout << "\n请输入列数：";
        cin >> col;
        cout << endl;
        Creat_maze(maze,row,col);
        start = maze.base;
        end = maze.top - 1;
        p = maze.base;

        if (p) {
                cout << "NULL";
                cout << "\tx= " << p->x << "\ty= " << p->y << "\tpos= " << p->pos << "\tstep= " << p->step << endl;
        }

        p->step = 1;
        if (FindPath(maze, path, p, start,end,row, col)) {
                p = path.base;
                while (p!=path.top) {                       
                        cout << "(" << p->x << "," << p->y << ")" << endl;
                        p++;
                }
                return 1;
        }
        else {
                cout << "此迷宫无通路！" << endl;               
                return 0;
        }
}
void Creat_maze(Stack& maze, int row, int col) {
        int i, j;
        position p;
        for (i = 0; i < row; i++) {
                p.x = i;
                for (j = 0; j < col; j++) {
                        p.y = j;
                        cin >> p.pos;
                        Push(maze, p);
                }
        }
}
int FindPath(Stack& maze, Stack& path, position* p,position* start, position* end, int row, int col) {
        position* per;
       {
                //向上
                {
                        per = p - col;
                        //验证per是否空
                        /**
                        if (per) {
                                cout << "NULL";
                                cout << "\tx= " << per->x << "\ty= " << per->y << "\tpos= " << per->pos << "\tstep= " << per->step<<endl;
                        }/**/
                        /**
                        if (p) {
                                cout << "NULL";
                                cout << "\tx= " << per->x << "\ty= " << per->y << "\tpos= " << per->pos << "\tstep= " << per->step << endl;
                        }/**/
                        if (!per && per->pos == 0 && per->step == 0) {
                                //!per 未越上边界
                                //per->pos == 0 无障碍
                                //per->step == 0 未被访问
                                Push(path, *per);
                                per->step = 1;
                                if (FindPath(maze, path, per, start, end, row, col)) {
                                        return 1;
                                }
                                else {
                                        return 0;
                                }
                        }
                }
                //向左
                {
                        per = p - 1;
                        /*
                        if (per) {
                                cout << "NULL";
                                cout << "\tx= " << per->x << "\ty= " << per->y << "\tpos= " << per->pos << "\tstep= " << per->step << endl;
                        }/**/
                        if (!per && p->x == per->x && per->pos == 0 && per->step == 0) {
                                //!per && p->x == per->x 未越界
                                Push(path, *per);
                                per->step = 1;
                                if (FindPath(maze, path, per, start, end, row, col)) {
                                        return 1;
                                }
                                else {
                                        return 0;
                                }
                        }
                       
                }
                //向下
                {
                        per = p + col;
                        if (!(per->x == 0 && per->y == 0 && per->pos == 1) && per->pos == 0 && per->step == 0) {
                                //per->x == 0 && per->y == 0 && per->pos == 1 是position类型元素的默认值，表示maze栈外元素
                                Push(path, *per);
                                per->step = 1;
                                if (FindPath(maze, path, per, start, end, row, col)) {
                                        return 1;
                                }
                                else {
                                        return 0;
                                }
                        }
                }
                //向右
                {
                        per = p + 1;
                        if (p->x == per->x && !(per->x == 0 && per->y == 0 && per->pos == 1) && per->pos == 0 && per->step == 0) {
                                Push(path, *per);
                                per->step = 1;
                                if (FindPath(maze, path, per, start, end, row, col)) {
                                        return 1;
                                }
                                else {
                                        return 0;
                                }
                        }
                }

                //判断，是出口
                if (p == end) {
                        return 1;
                }
                //不是出口，回退，
                        //判断，新起点是入口，return 0，F
                        // 0 0 0
                        // 0 1 0
                        // 1 1 0
                        //否，遍历,F
                //判断，回退后path栈空，return 0
                //path栈未空，以栈顶元素为新起点再遍历
                else {
                        position tem;
                        Pop(path, tem);
                        //per = (maze.base + (tem.x * row + tem.y));
                        //per = (maze.base + (path.top - 1)->x * col + (path.top - 1)->y);
                        /**if (per == start) {
                                delete per;
                                return 0;
                        }
                        else {
                                if (FindPath(maze, path, per, start, end, row, col)) {
                                        delete per;
                                        return 1;
                                }
                                else {
                                        delete per;
                                        return 0;
                                }
                        }/**/
                        if (path.base == path.top) {
                                return 0;
                        }
                        else {
                                per = (maze.base + (path.top - 1)->x * col + (path.top - 1)->y);
                                if (FindPath(maze, path, per, start, end, row, col)) {
                                        return 1;
                                }
                                else {
                                        return 0;
                                }
                        }
                               
                }
       }
}

查看完整版本: 迷宫问题