迷宫问题 请问如何打印路径坐标 0为通路 1为墙
#pragma once#include<stdio.h>
#include<windows.h>
#include<assert.h>
//要定义的有：
//一个结构体为结构体pos，用于记录迷宫每个店的横纵坐标
//两个栈path和shortpath，记录通路的最短距离,栈内元素序列即是最短
//迷宫（迷宫地图，入口点）
#define N 6
#define Stack_size 20
typedef struct pos //迷宫内每个点的坐标
{
int row;
int col;
}pos;
typedef pos DataType;
typedef struct Stack //存放节点信息的栈
{
DataType* _array; //数组指针
size_t _top; //栈顶
size_t _end; //最大容量
}Stack;
typedef struct maze //迷宫
{
int mz[N][N];
pos entry; //入口点
}maze;
void StackInit(Stack* s)//栈的初始化
{
assert(s);
s->_array = (DataType*)malloc(sizeof(DataType)*Stack_size);
s->_end = Stack_size;
s->_top = 0;
}
void StackPush(Stack* s, DataType x)//入栈
{
assert(s);
if (s->_end == s->_top)//栈已满
{
s->_end *= 2;
s->_array = (DataType*)realloc(s->_array, sizeof(DataType)*(s->_end));
s->_array[s->_top] = x;
(s->_top)++;
}
else
{
s->_array[s->_top] = x;
(s->_top)++;
}
}
void StackPop(Stack* s)//出栈
{
assert(s);
if (s->_top == 0)
{
printf("the stack is empty");
}
else
{
s->_top--;
}
}
int StackEmpty(Stack* s)//判断栈是否为空
{
if (s->_top == 0)
{
return 1;
}
else
{
return 0;
}
}
DataType StackTop(Stack* s)//取栈顶元素
{
assert(s);
int num = s->_top;
DataType i = s->_array[(--num)];
return i;
}
void mazeinit(maze *M)//迷宫初始化
{
assert(M);
int a[N][N] = {
{ 1, 1, 1, 1, 1, 1 },
{ 0, 0, 0, 0, 0, 1 },
{ 1, 0, 1, 0, 1, 1 },
{ 1, 0, 1, 0, 0, 0 },
{ 1, 0, 1, 0, 1, 1 },
{ 1, 1, 1, 1, 1, 1 }
};
for (size_t i = 0;i < N;i++)
{
for (size_t j = 0;j < N;j++)
{
M->mz[i][j] = a[i][j];
}
}
M->entry.row = 1;
M->entry.col = 0;
}
void mazeprint(maze *M)
{
assert(M);
for (int i = 0;i < N;i++)
{
for (int j = 0;j < N;j++)
{
printf("%d ", (M->mz)[i][j]);
}
printf("\n");
}
printf("\n");
}
int can_stay(pos cur, maze *M)//判断是否能入栈
{
if (cur.row >= 1 && cur.row < N&&cur.col >= 1 && cur.col < N //坐标合法
&&M->mz[cur.row][cur.col] != 1 && M->mz[cur.row][cur.col] != 2) //该点不为墙也不为走过的点
{
return 1;
}
return 0;
}
void assign_pos(pos cur, maze **M)//标记
{
(*M)->mz[cur.row][cur.col] = 0;
}
int check_exit(pos cur, maze *M)//检查是否到达出口
{
if ((cur.row == 1) || (cur.row == N - 1) || (cur.col == 1) || (cur.col == N - 1))
{
if ((cur.row) != ((M->entry).row) && (cur.col) != ((M->entry).col))
{
return 1;
}
}
return 0;
}
void print_stack(Stack *s)
{
printf("找到出口！\n\n");
printf("栈顶\n");
for (size_t i = 0;i < s->_top;i++)
{
printf("[%d %d]\n", s->_array[i].col, s->_array[i].row);
}
printf("栈底\n\n");
}
void simple_getpath(maze *M, pos cur, Stack *s)
{
assert(M);
//2.判定当前点坐标是否可以走。（坐标合法且不为0）
if (can_stay(cur, M) == 0)
{
//3.如果合法则将当前点标记成走过的并入栈
//（维护一个栈可以记录走过的路径，栈的长度就是路径的长度）
assign_pos(cur, &M);
StackPush(s, cur);
}
else
{
return;
}
if (check_exit(cur, M) == 0)
{
print_stack(s);
return;
}
//4.判断当前点是否是出口，是出口就return（该迷宫不存在别的出口），
//如果不是出口，以顺时针的方向（上，右，下，左）探测临界点是否可以走（不为0且不为已经走过的点），
//并以递归形式重复步骤2-4.
//up
pos up = cur;
up.row -= 1;
simple_getpath(M, up, s);
//right
pos right = cur;
right.col += 1;
simple_getpath(M, right, s);
//down
pos down = cur;
down.row += 1;
simple_getpath(M, down, s);
//left
pos left = cur;
left.col -= 1;
simple_getpath(M, left, s);
//5.当一个点的4个方向都已经探测过，就返回上一层栈帧。
StackPop(s);
return;
}
void simplemaze()
{
maze M;
Stack path;
StackInit(&path);
mazeinit(&M);
mazeprint(&M);
simple_getpath(&M, M.entry, &path);
mazeprint(&M);
}
int main()
{
simplemaze();
system("pause");
return 0;
}
