迷宫问题，大一新生求帮助
在运行迷宫问题（八个方向可走）时，vs报错出现访问冲突，多次调试也没有办法😫
报错如下：
这是我的算法：
调试过程：
以下是完整代码：
#include
#include"string.h"
using namespace std;
const int M = 10;
const int N = 10;
int m[M][N] = {
(1,1,1,1,1,1,1,1,1,1),
(1,0,0,1,1,0,0,1,1,1),
(1,0,0,1,1,1,0,0,0,1),
(1,0,0,0,1,1,0,0,1,1),
(1,0,1,0,1,1,0,0,1,1),
(1,0,1,0,0,1,1,0,1,1),
(1,0,1,0,0,0,1,0,1,1),
(1,1,1,0,0,1,0,0,0,1),
(1,1,0,0,0,0,0,0,1,1),
(1,1,1,1,1,1,1,1,1,1)
};
typedef struct BOX{
int x=0,y=0;
int dir=1;
bool de=true;
}BOX;
BOX nextstep(BOX a) {
if (a.dir == 1) {
a.x--;
a.y--;
}
if (a.dir == 2) {
a.y--;
}
if (a.dir == 3) {
a.x++;
a.y--;
}
if (a.dir == 4) {
a.x++;
}
if (a.dir == 5) {
a.x++;
a.y--;
}
if (a.dir == 6) {
a.y--;
}
if (a.dir == 7) {
a.x--;
a.y++;
}
if (a.dir == 8) {
a.x--;
}
return a;
}
typedef struct {
BOX* top;
BOX* base;
int size;
}path;
void creatpath(path& a) {
a.base = new BOX;
a.top = a.base;
a.size = 0;
}
void push(path& a,BOX ox) {
if (a.top - a.base >= a.size) {
path b;
b.base = new BOX[a.size + 1];
BOX* p1=a.base,*p2=b.base ;
while (p1!=a.top ) {
*p2 = *p1;
p2++;
p1++;
}
*p2 = ox;
delete a.base;
a.size++;
a.base = b.base ;
a.top = a.base + a.size;
}
*a.top++ = ox;
}
bool pop(path& a,BOX &ox) {
if (a.top = a.base) {
return false;
}
a.top--;
ox = *a.top;
return true;
}
BOX Gettop(path a) {
a.top--;
BOX b = *a.top;
return b;
}
path findway( BOX start, BOX out) {
path way;
creatpath(way);//创建路线
push(way, start);//把起点压入路线
m[1][1] = 1;
BOX next,cur;
while (cur.x !=out.x &&cur.y!=out.y) {
cur = Gettop(way);//取得当前所在位置
next = nextstep(cur);//取得下一步位置
if (m[next.x][next.y] == 0) {//若下一位置能走
m[next.x][next.y] = 1;//标记下一个位置已经走过
push(way, next);//把下一个位置压入路线
if (next.x == out.x && next.y == out.y)
{
return way;
}//若走出迷宫返回路线
continue;//继续循环
}
if (m[next.x][next.y] == 1) {//若下一位置不能走
cur.dir++;//改变方向
if (cur.dir > 8) {//若四周都不能走
m[cur.x][cur.y] = 1;//标记当前位置不能走
pop(way,cur);//回退一格
}
}
}
}
void deletepath(path& way) {
delete way.base;
}
int main()
{
BOX start;
start.x = 1;
start.y = 1;
BOX out;
out.x = 5;
out.y = 1;
path v = findway(start, out);
BOX *p=v.base ;
while(p != v.top) {
cout << "(" << p->x << "," << p->y << "<" << ")" << "\n";
p++;
}
deletepath (v);
}
请大家帮忙看看！非常感谢！
/* 迷宫问题求解 */
#define ENDM 8 // 目标点横坐标
#define ENDN 9 // 目标点纵坐标
#define SM 1 //出发点横坐标
#define SN 1 //出发点纵坐标
#define ROW 10
#define COL 11
#include"stack.h" //请一定要认真看看stack.h文件哦，它可能和你现在编的函数有些小差异。
int dx[4]= {0, 1, 0, -1}; //方向定义，右0 下1 左2 上3 此处可根据出发点和目标点的不同而调整，使得路线尽量最短
int dy[4]= {1, 0, -1, 0};
char MAP[10][11]= { //注意，地图的设置，四个边框一定要是封闭的哦，如果给你的地图不封闭，同学们有办法解决不？
{'#', '#', '#', '#', '#', '#', '#', '#', '#', '#', '#'},
{'#', ' ', ' ', '#', '#', ' ', ' ', ' ', ' ', '#', '#'},
{'#', ' ', '#', ' ', '#', '#', ' ', '#', ' ', '#', '#'},
{'#', ' ', '#', ' ', '#', '#', ' ', '#', ' ', ' ', '#'},
{'#', ' ', '#', ' ', ' ', '#', ' ', '#', '#', ' ', '#'},
{'#', ' ', '#', '#', ' ', '#', ' ', ' ', '#', ' ', '#'},
{'#', ' ', '#', ' ', ' ', ' ', '#', ' ', ' ', ' ', '#'},
{'#', ' ', '#', ' ', '#', ' ', '#', ' ', '#', ' ', '#'},
{'#', ' ', ' ', ' ', '#', ' ', ' ', ' ', '#', ' ', '#'},
{'#', '#', '#', '#', '#', '#', '#', '#', '#', '#', '#'}
};
int AA[10][11]={ //与MAP对应
{1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1},
{1, 0, 0, 1, 1, 0, 0, 0, 0, 1, 1},
{1, 0, 1, 0, 1, 1, 0, 1, 0, 1, 1},
{1, 0, 1, 0, 1, 1, 0, 1, 0, 0, 1},
{1, 0, 1, 0, 0, 1, 0, 1, 1, 0, 1},
{1, 0, 1, 1, 0, 1, 0, 0, 1, 0, 1},
{1, 0, 1, 0, 0, 0, 1, 0, 0, 0, 1},
{1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1},
{1, 0, 0, 0, 1, 0, 0, 0, 1, 0, 1},
{1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1},
};
int R(int u,int v) //对于一个给定的坐标，如果该点越界或是障碍点，返回1，否则返回0
{
if (u<0 || v<0)
return 1;
if (u>9 || v>10)
return 1;
if (AA[u][v]==1)
return 1;
return 0;
}
int main()
{
int i,j, k;
int u,v;
SqStack s;
InitStack(&s); //初始化栈S
i=SM; //i, j是当前点坐标，从出发点(SM, SN)开始
j=SN;
while (1) //该while循环的程序逻辑，是严格按照流程图（流程图在哪里？请见王老师《算法设计与实现》课件之"讲义（不断更新中）.ppt"）来转换而成的
{
AA[i][j]=1; //当前点走过，所以标为1
k=-1; //之所以设置成-1，是为了和下面的k++呼应，让方向值k一开始从0开始。
do //体会什么叫“do while中嵌套一个while循环”
{
k++;
while(k>=4)
{
if (StackIsEmpty(s))
{
printf("本迷宫无解。\n");
DestroyStack(&s);
return -1;
}
else //如果栈内有点，那么就原路退回到刚走过来的那个点（旧点），并且重新刷新i,j,k的值
{
Pop(&s, &i, &j, &k);
k++; //换下一个方向。此处是“旧点新方向”
}
}
u= i + dx[k]; //产生新的尝试点（u,v）
v= j + dy[k];
}while(AA[u][v]==1 || R(u,v)==1); //必须是没走过的点，而且是未越界的非障碍点
if (u==ENDM && v== ENDN) //如果尝试点就是终点，那说明已经找到终点了，完整路径存放在此时的堆栈中。
{
Push(&s, i, j, k); //别忘了将当前点压栈，以方便等会下面的输出
Push(&s, u, v, 0); //别忘了将终点压栈，以方便等会下面的输出
/* 输出栈内结果*/
while (!StackIsEmpty(s))
{
Pop(&s, &i, &j, &k);
MAP[i][j]= '1'; //根据路径修改地图，走法标为"1"（当然，你可以改成其他数字符号），使得显示更直观好看
}
for (i=0; i<10; i++) //输出迷宫和走法
{
for(j=0; j<11; j++)
printf("%c ", MAP[i][j]);
printf("\n");
}
DestroyStack(&s); //撤退之前别忘了打扫战场，退出之前一定要记得销毁顺序栈哦！
return 0;
}
Push(&s, i, j, k); //如果尝试点不是终点，则将当前点和方向压栈，并“向前走（即修改当前点的值为(u,v) ）”
i= u;
j=v;
}
简单的dfs就能解决的问题....为啥要这么多结构体呢...
可能是索引或者栈溢出了, 能递归尽量还是递归吧....不容易出错....
#define MAXN 10
bool vis[MAXN][MAXN]; // main里面记得memset(vis, 0, sizeof(vis))
vector<pair<int, int>> path;
int graph[MAXN][MAXN];
void dfs(pair<int, int> const& cur, pair<int, int> const& dest){
if(cur.first==dest.first && cur.second==dest.second){
return;
}
int dx[8] = {0, 0, -1, 1, -1, -1, 1, 1};
int dy[8] = {-1, 1, 0, 0, -1, 1, -1, 1};
for(int i=0; i<8; i++){
auto next = {cur.first+dx[i], cur.second+dy[i]};
if(check(next)){
vis[next.first][next.second] = 1;
path.emplace_back(next);
dfs(next, dest);
vis[next.first][next.second] = 0;
path.pop_back();
}
}
}
bool check(pair<int, int> const& cur){
int x = cur.first, y = cur.second;
return x>=0 && x<MAXN && y>=0 && y<MAXN && (!vis[x][y]) && (1==graph[x][y]);
}
崩溃的时候在弹出的对话框按相应按钮进入调试，按Alt+7键查看Call Stack即“调用堆栈”里面从上到下列出的对应从里层到外层的函数调用历史。双击某一行可将光标定位到此次调用的源代码或汇编指令处，看不懂时双击下一行，直到能看懂为止。