使用C中的堆栈获得迷宫的出口

Question

我有一个使用递归函数搜索迷宫出口的算法，我如何在没有递归但使用堆栈的情况下将其传递给函数？这个算法所做的基本上是，尝试找到一个矩阵的出口，如果下一步是0，或者如果已经被覆盖，则返回并尝试另一条路径，但我需要将递归函数更改为使用堆栈而不是递归的函数，我该怎么做？

void print_maze(char **maze, int width, int height) {
for (int i=0; i<13; i++ ){
for (int j=0; j<10; j++ )
{
printf ("%d", maze[i][j]);
}
printf("n");
}
}
int maze(int x_current, int y_current,char **mazeHere, int height,int width)
{
if (x_current < 0 || x_current >= width || y_current < 0 || y_current >= height)
return 0;
char here = mazeHere[x_current][y_current];
if (here == 3)
return 1;
if(here == 0 || here == 2)
return 0;

mazeHere[x_current][y_current] = 2;
if(maze(x_current ,y_current-1,mazeHere,height,width))return 1;
if(maze(x_current+1,y_current,mazeHere,height,width))return 1;
if(maze(x_current,y_current+1,mazeHere,height,width))return 1;
if(maze(x_current-1,y_current,mazeHere,height,width))return 1;

else{ mazeHere[x_current][y_current] = 1;
return 0;
}
}

int main(void)
{
char matriz [13][10]={
{0,0,0,0,0,0,0,0,0,0},
{0,0,1,1,1,1,1,0,0,0},
{0,0,1,0,0,0,1,0,0,0},
{0,0,1,0,0,0,1,0,0,0},
{1,1,1,0,1,1,1,1,1,0},
{0,1,0,0,1,0,0,0,0,0},
{0,1,1,0,1,1,1,0,0,0},
{0,0,1,0,1,0,0,0,1,0},
{0,0,1,0,0,0,1,1,1,0},
{0,0,1,1,1,1,1,0,0,0},
{0,0,0,0,0,0,1,0,0,0},
{0,0,0,0,0,0,1,1,1,3},
{0,0,0,0,0,0,0,0,0,0},};
int b= 0;
int height = 10;
int width = 13;
int p = 0;
int o = 0;
char **a = malloc(width * sizeof(char*));
for(int x = 0; x< width; x++){
a[x] = malloc(height * sizeof(char));
}

for (int i=0; i<13; i++ ){
for (int j=0; j<10; j++ )
{
a[i][j]= matriz[i][j];
}
}

int res = maze(4,0,a,height,width);
puts(res ? "success!" : "no luck!");
print_maze(a, width, height);
return 0;
}

Answer 1

我知道没有递归很难。顺便说一句，如果您编写了堆栈数据结构及其操作的代码，那么从递归到使用堆栈的转换就不那么困难了。我们将假定此事。

递归函数基本上有这样的结构：

position *seek(position *now, type arg...){
...
if(condition){
return NULL;
} else {
now->next = seek(arg_next);
}
}

凭感觉去理解是可以的。到目前为止，它在这里所做的是将新结果链接到结果。换句话说，将结果存储为数据结构。在这里，数据结构更改为堆栈。然后…：

void seek(stack *stack, type arg...){
...
while(1){
if(condition){
break;
} else {
stack->push(next_result)
}
}
}

太容易了！剩下的就是增加条件和考虑回溯。基于以上内容，请尝试重写您的代码！