在迷宫中寻找路径时进行分段

Question

我试图打印出迷宫的坐标，因为我试图使用深度优先搜索算法解决，但是，它打印出初始位置，但它存在故障。我做错了什么吗?下面是我的代码:

#include "mazegen.h"
#include "stack.h"
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <time.h>
#define  BUFFERSIZE 500
#define  FLAG 
void mazeSolution(char maze[100][100], int counter, int counter2)
{
   stack*currentCell;
   int i;
   int j;
   currentCell = create();
  for(i=0; i<counter; i++)
  {
      for(j=0; j<counter2; j++)
      {
          if(maze[i][j] == 'S')
          {
              push(currentCell,i,j);
              currentCell->visited = true;
          }
      }
  }
   printStack(currentCell);
   while(currentCell != NULL)
   { 
      pop(currentCell);
      if(maze[i][j] == 'F')
      {
           break;
      }
      if(i != 0)
      { 
          if(maze[i-1][j] == ' ' && currentCell->visited != true)
          {
              currentCell->visited = true;
              push(currentCell,i-1,j);
          }
      }
      if(maze[i+1][j] == ' ' && currentCell->visited != true)
      {
          currentCell->visited = true;
          push(currentCell,i+1,j);
      }
      if(j != 0)
      {
          if(maze[i][j-1] == ' ' && currentCell->visited != true)
          {
              currentCell->visited = true;
              push(currentCell, i,j-1);
          }
      }
      if(maze[i][j+1] == ' ' && currentCell->visited != true)
      {
           currentCell->visited = true;
            push(currentCell, i, j+1); 
      }
 }
  printf("No solutionn");

  printStack(currentCell);
}

我认为这与我的pop函数和我实现它的方式有关

void pop (stack*theStack)
{
    node*theHead;
    if(theStack == NULL)
    {
        printf("Empty Stack. Errorn");
         exit(0);
    }
    theHead = removeFromFront(theStack->list);
    theStack->list = theHead;

}
node*removeFromFront(node*theList) 
{
    node*temp;
    temp = theList->next;
    if(temp == NULL)
    {
        printf("pop Errorn");
        return NULL;
    }
    theList = theList->next;
    return theList;
}.       

Answer 1

看看这部分代码:

while(currentCell != NULL)
{ 
      pop(currentCell);
      if(maze[i][j] == 'F')
      {
           break;
      }
   ...
}

你正在从堆栈中弹出一个值-这是ok的。但是您需要将弹出的值分配给i和j。在您的代码中，i和j的值保持不变，因此您有一个无限的while循环。在这个循环中，你不断地向堆栈中推送值，最终导致段错误。

Answer 2

在堆栈上保持已访问状态是无用的-当您尝试从某个新方向访问它时，您需要检查特定位置是否已访问过，如果迷宫中存在循环可能会发生这种情况。因此，这个属性的合适位置是迷宫本身，而不是堆栈。

你不需要单独的stack和node结构-堆栈实际上是一个节点列表。

构建堆栈很容易，但是在开始编码之前，您需要想象它的结构和行为。有两种基本的(纯C)解决方案:使用预分配的数组或动态链表。让我们使用数组。

一个栈的项将是

typedef struct node {
    int i, j;
} Node;

堆栈本身:

Node stack[ 10001];

和一些当前堆叠的项:

int stkptr = 0;

现在我们可以测试堆栈是否包含任何数据:

int StackNonEmpty() { return stkptr; }

将新位置压入堆栈:

void Push(int i, int j) {
    stack[ stkptr].i = i;
    stack[ stkptr].j = j;
    stkptr ++;
}

从栈顶读取一个位置(假设StackNonEmpty() != 0):

void Fetch(int *pi, int *pj) {
    *pi = stack[ stkptr - 1].i;
    *pj = stack[ stkptr - 1].j;
}

并将其从堆栈中移除:

void Pop() { stkptr --; }

我们还需要为访问位置定义一个标记:

int VISITED = '.';

或

#define VISITED '.'

，我们准备好编写算法了:

for(i=0; i<counter; i++)
    for(j=0; j<counter2; j++)
        if(maze[i][j] == 'S')
        {
            Push(i,j);   // set the Start position
            i = counter; // this is to break the outer loop
            break;       // and this breaks the inner loop
        }
while( StackNonEmpty())
{
    Fetch(& i, & j);             // get a current position
    if( maze[i,j] == 'F')              // Finish found?
        break;
    if( maze[i,j] == ' ')              // empty cell?
        maze[i,j] = VISITED;
    // find next possible step
    if( i > 0 && maze[i-1,j] == ' ')   // cell to the left is empty
        Push(i-1,j);                   // step left
    else
    if( j > 0 && maze[i,j-1] == ' ')   // cell above is empty
        Push(i,j-1);                   // step up
    else
    if( i+1 < counter && maze[i+1,j] == ' ')
        Push(i+1,j);                   // step right
    else
    if( j+1 < counter2 && maze[i,j+1] == ' ')
        Push(i,j+1);                   // step down
    else                               // dead end - no way out
        Pop();                         // step back
}
if( StackNonEmpty())      // exited with break, so 'F' found
    PrintStack();
else
    PrintFailureMessage();  // could not reach 'F'

要显示结果，只需打印stack数组的所有项，直到stkptr的位置:

void PrintStack() {
    for(i = 0; i < stkptr; i ++)
        printf( "%d,%dn", stack[i].i, stack[i].j);
}

编辑
" VALID "状态赋值更正(was ==而不是=)，PrintFailureError替换为PrintFailureMessage .