程序可运行，但一直输出“当前搜索节点:（6，0）”，不能输出正确路径，不知道怎么改

Question

#include<stdio.h>
#include<stdlib.h>
#include<stdbool.h>

#define OK 1
#define ERROR 0

typedef int Status;

//迷宫地图（0为通路，1为墙）
int maze[8][8]={
    {0,0,1,0,0,0,1,0},
    {0,0,1,0,0,0,1,0},
    {0,0,0,0,1,1,0,0},
    {0,1,1,1,0,0,0,0},
    {0,0,0,1,0,0,0,0},
    {0,1,0,0,0,1,0,0},
    {0,1,1,1,0,1,1,0},
    {1,0,0,0,0,0,0,0},
};
     
//因为要用到坐标，所以先定义坐标的结构体（数据域） 
typedef struct{
    int x,y;
}Direction;


//定义链表节点的结构体（指针域）
typedef struct Node{
    Direction data;
    struct Node *next;
}Node; 
 
 //定义栈的结构体 将路径放入栈里 
typedef struct{
    Node *top;
}Stack;

//初始化
Status InitStack(Stack *stack){
    stack->top=NULL;
    return OK;
} 

//入栈
Status Push(Stack *stack,Direction direction){
    Node *newNode=(Node *)malloc(sizeof(Node));      //分配空间 
    newNode->data=direction;
    newNode->next=stack->top;           //将新结点插入栈顶 
    stack->top=newNode;                 //修改栈顶指针 
    return OK;
} 

//出栈 
Direction Pop(Stack *stack){
    if(stack->top==NULL){                            //判断是否为空栈 
    Direction invalidDirection={-1,-1};
    return invalidDirection;
    }        
    Node *temp=stack->top;
    Direction direction=temp->data;
    stack->top=temp->next;
    free(temp);
    return direction;
}

//检查坐标是否有效
Status isValidDirection(Direction direction){
    return (direction.x>=0 && direction.x<8 && direction.y>=0 && direction.y<8 )&& maze[direction.x][direction.y]==0;//判断该坐标的位置是否为“0” 
} 

bool isGoalReached(Direction start,Direction end){
    return start.x ==end.x && start.y== end.y;
}

//打印路径
void printPath(Stack *stack){
    Node *currentNode=stack->top;
    while(currentNode !=NULL){
        printf("(%d,%d)",currentNode->data.x,currentNode->data.y);
        currentNode=currentNode->next;
    }
        printf("\n");
} 

void printCurrentPosition(Direction position){
    printf("当前搜索节点:(%d,%d)\n",position.x,position.y);
}
Direction getNextDirection(Direction current,int directionIndex){
    switch(directionIndex){
        case 0://up
          return Direction{current.x-1,current.y};
        case 1://down
           return Direction{current.x+1,current.y};
        case 2://left
           return Direction{current.x,current.y-1};
        case 3://right
           return Direction{current.x,current.y+1};
        
    }
}
//深度优先搜索 
bool solveMaze(Direction start,Direction end,Stack *pathStack){
    Direction current=start;
    if(!isValidDirection(current)){
    return false; 
    } 
    Stack backtrackStack;   //用于回溯的栈
    InitStack(&backtrackStack);
    
    Push(pathStack,current);                   //将起点入栈 
    
    maze[current.x][current.y]=2;                   //标记起点已访问  将指定位置设置为2
     
    while(pathStack->top != NULL){
      current=pathStack->top->data;
      printCurrentPosition(current);
    
         if(isGoalReached(current,end)){
         printPath(pathStack);
         return true;
         }
    
         bool foundNext=false;     //尝试向四个方向移动 
      for(int i=0;i<4;i++){
      Direction next=getNextDirection(current,i);
      if(isValidDirection(next)){
        Push(&backtrackStack,next);
        Push(pathStack,next);
        maze[next.x][next.y]=2;
        foundNext = true;
        break;
    }
}
      if(!foundNext){
        Pop(&backtrackStack);
        current = Pop(&backtrackStack);
      } 
    }
return false;
}

int main(){
    int maze[8][8]={
    {0,0,1,0,0,0,1,0},
    {0,0,1,0,0,0,1,0},
    {0,0,0,0,1,1,0,0},
    {0,1,1,1,0,0,0,0},
    {0,0,0,1,0,0,0,0},
    {0,1,0,0,0,1,0,0},
    {0,1,1,1,0,1,1,0},
    {1,0,0,0,0,0,0,0},
};
 Direction start={0,0};
 Direction end={7,7};
 Stack pathStack;
 InitStack(&pathStack);

if(solveMaze(start,end,&pathStack)){
    printf("成功走出迷宫！\n");
    printPath(&pathStack);
}
else {
    printf("未找到路径。\n");
}
 return 0;
}

Answer 1

以下是修改后的代码，主要问题在于回溯逻辑和路径标记的处理：

#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>

#define OK 1
#define ERROR 0

typedef int Status;

// 迷宫地图（0 为通路，1 为墙）
int maze[8][8] = {
    {0,0,1,0,0,0,1,0},
    {0,0,1,0,0,0,1,0},
    {0,0,0,0,1,1,0,0},
    {0,1,1,1,0,0,0,0},
    {0,0,0,1,0,0,0,0},
    {0,1,0,0,0,1,0,0},
    {0,1,1,1,0,1,1,0},
    {1,0,0,0,0,0,0,0}
};

typedef struct {
    int x, y;
} Direction;

typedef struct Node {
    Direction data;
    struct Node* next;
} Node;

typedef struct {
    Node* top;
} Stack;

Status InitStack(Stack* stack) {
    stack->top = NULL;
    return OK;
}

Status Push(Stack* stack, Direction direction) {
    Node* newNode = (Node*)malloc(sizeof(Node));
    if (!newNode) {
        perror("Malloc failed");
        exit(1);
    }
    newNode->data = direction;
    newNode->next = stack->top;
    stack->top = newNode;
    return OK;
}

Direction Pop(Stack* stack) {
    if (stack->top == NULL) {
        Direction invalidDirection = { -1, -1 };
        return invalidDirection;
    }
    Node* temp = stack->top;
    Direction direction = temp->data;
    stack->top = temp->next;
    free(temp);
    return direction;
}

Status isValidDirection(Direction direction) {
    return (direction.x >= 0 && direction.x < 8 && direction.y >= 0 && direction.y < 8) && maze[direction.x][direction.y] == 0;
}

bool isGoalReached(Direction current, Direction end) {
    return current.x == end.x && current.y == end.y;
}

void printPath(Stack* stack) {
    Node* currentNode = stack->top;
    while (currentNode) {
        printf("(%d,%d) ", currentNode->data.x, currentNode->data.y);
        currentNode = currentNode->next;
    }
    printf("\n");
}

void printCurrentPosition(Direction position) {
    printf("当前搜索节点: (%d,%d)\n", position.x, position.y);
}

bool solveMaze(Stack* pathStack, Direction current, Direction end, bool visited[8][8]) {
    if (visited[current.x][current.y]) return false; // 如果已经访问过，直接返回
    if (isGoalReached(current, end)) {
        printPath(pathStack);
        return true;
    }
    visited[current.x][current.y] = true; // 标记当前位置为已访问
    printCurrentPosition(current); // 打印当前搜索节点

    // 定义可移动的四个方向
    static Direction dirs[4] = { {-1, 0}, {1, 0}, {0, -1}, {0, 1} };
    for (int i = 0; i < 4; i++) {
        Direction next = { current.x + dirs[i].x, current.y + dirs[i].y };
        if (isValidDirection(next) && !visited[next.x][next.y]) {
            Push(pathStack, next);
            if (solveMaze(pathStack, next, end, visited)) return true;
            Pop(pathStack); // 回溯
        }
    }

    visited[current.x][current.y] = false; // 回溯时恢复当前节点状态
    return false;
}

int main() {
    Direction start = { 0, 0 };
    Direction end = { 7, 7 };
    Stack pathStack;
    bool visited[8][8] = { false };

    InitStack(&pathStack);
    Push(&pathStack, start); // 将起点压入栈，开始搜索

    if (solveMaze(&pathStack, start, end, visited)) {
        printf("成功走出迷宫!\n");
    }
    else {
        printf("没有找到路径。\n");
    }

    return 0;
}