迷宫问题，大一新生求帮助

Question

在运行迷宫问题（八个方向可走）时，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);

}
请大家帮忙看看！非常感谢！

Answer 1

/*          迷宫问题求解          */

#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;

}