```c++
//二维数组中[x][y]，x表示行，y表示列
#define EAST MAZE[x][y+1] // 东方向
#define WEST MAZE[x][y-1] // 西方向
#define SOUTH MAZE[x+1][y] // 南方向
#define NORTH MAZE[x-1][y] // 北方向
using namespace std;
const int ExitX = 8; // 出口x坐标
const int ExitY = 10; // 出口y坐标
struct list
{
int x, y;
struct list* next;
};
typedef struct list node;
typedef node* link;
int MAZE[10][12] = { 1,1,1,1,1,1,1,1,1,1,1,1, // 定义迷宫
1,0,0,0,1,1,1,1,1,1,1,1,
1,1,1,0,1,1,0,0,0,0,1,1,
1,1,1,0,1,1,0,1,1,0,1,1,
1,1,1,0,0,0,0,1,1,0,1,1,
1,1,1,0,1,1,0,1,1,0,1,1,
1,1,1,0,1,1,0,1,1,0,1,1,
1,1,1,0,1,1,0,1,1,0,1,1,
1,1,1,0,0,0,0,0,1,0,0,1,
1,1,1,1,1,1,1,1,1,1,1,1
};
link push(link path, int x, int y);
link pop(link path, int* x, int* y);
int chkExit(int x, int y, int ex, int ey);
link push(link path, int x, int y)
{
link newnode;
newnode = new node;
if (!newnode)
{
cout << "Error:内存分配失败！" << endl;
return NULL;
}
newnode->x = x;
newnode->y = y;
newnode->next = path;
path = newnode;
return path;
}
link pop(link path, int* x, int* y)
{
link top;
if (path != NULL)
{
top = path;
path = path->next;
*x = top->x;
*y = top->y;
delete top;
return path;
}
else
*x -= 1;
return path;
}
int chkExit(int x, int y, int ex, int ey)
{
if ((x == ex) && (y = ey))
{
if (NORTH == 1 || SOUTH == 1 || WEST == 1 || EAST == 2)
return 1;
if (NORTH == 1 || SOUTH == 1 || WEST == 2 || EAST == 1)
return 1;
if (NORTH == 1 || SOUTH == 2 || WEST == 1 || EAST == 1)
return 1;
if (NORTH == 2 || SOUTH == 1 || WEST == 1 || EAST == 1)
return 1;
}
return 0;
}
int main(void)
{
cout << endl << endl;
int i, j;
link path = NULL;
int x = 1; // 入口x坐标
int y = 1; // 入口y坐标
cout << " " << "迷宫图（0的位置可走，1的位置为墙）：\n" << endl; // 显示地图
for (i = 0; i < 10; i++)
{
for (j = 0; j < 12; j++)
cout << " " << MAZE[i][j] << " ";
cout << endl;
}
cout << endl << endl;
// 开始走迷宫
while (x <= ExitX && y <= ExitY)
{
MAZE[x][y] = 2;
if (NORTH == 0)
{
x -= 1;
path = push(path, x, y);
}
else if (SOUTH == 0)
{
x += 1;
path = push(path, x, y);
}
else if (WEST == 0)
{
y -= 1;
path = push(path, x, y);
}
else if (EAST == 0)
{
y += 1;
path = push(path, x, y);
}
else if (chkExit(x, y, ExitX, ExitY) == 1)
break;
else
{
MAZE[x][y] = 2;
path = pop(path, &x, &y);
}
}
cout << "迷宫完成图（0的位置未走，1的位置为墙，2的位置已走）：\n" << endl; // 显示地图
for (i = 0; i < 10; i++)
{
for (j = 0; j < 12; j++)
cout << " " << MAZE[i][j] << " ";
cout << endl;
}
return 0;
}
这以下两小段怎么理解，把位置返回给path又有什么用
top = path;
path = path->next;
*x = top->x;
*y = top->y;
delete top;
return path;
if (!newnode)
{
cout << "Error:内存分配失败！" << endl;
return NULL;
}
newnode->x = x;
newnode->y = y;
newnode->next = path;
path = newnode;
return path;
```
这两段就是路径出栈和入栈,整个程序主要算法是用栈模拟递归算法求路径,
以下这段是出栈
top = path; //先临时变量保存顶部指针,为delete做准备
path = path->next; //路径指向顶部下面那个元素的指针
*x = top->x; //把坐标传回,实际等于回退到该位置
*y = top->y;
delete top; //删除原来顶部指针内存
return path; //返回新的顶部指针
入栈相对简单一点
//察看是否成功
if (!newnode)
{
cout << "Error:内存分配失败！" << endl;
return NULL;
}
newnode->x = x; //设置坐标
newnode->y = y;
newnode->next = path; //新顶部指针连接进旧顶部
path = newnode; //设置新顶部
return path;//返回路径