如何使用堆栈打印移动路径(在C99中)？

我在这个数据结构类中使用堆栈实现了一个迷宫。然而，挑战在于使用此代码中的堆栈来输出迷宫的路径，包括当它到达无法再移动的坐标时返回到它来的方式的过程。我试着用ChatGPT解决它，但我对结果不满意，所以我像这样寻求帮助。
这是我的代码。

#define MAZE_SIZE 10
#define MAX_STACK_SIZE 100

#include <stdio.h>

int back_count ;

typedef struct {
    short r ;
    short c ;
} element;

typedef struct {
    int top ;
    element data[MAX_STACK_SIZE];
} StackType ;

void init_stack(StackType *s) {
        s->top = -1 ;
}

int is_empty(StackType *s) {
        return (s->top == -1);
}

int is_full(StackType *s) {
        return (s->top == MAX_STACK_SIZE - 1) ;
}

void push(StackType *s, element item) {
        if (is_full(s)) {
            fprintf(stderr, "Stack Full") ;
            return;
        }
        else {
            s->data[++(s->top)] = item ;
        }
}

element pop(StackType *s) {
        if (is_empty(s)) {
            fprintf(stderr, "Stack Empty") ;
            element err = {-1, -1};
            return err;
        }
    else {
            return (s->data[(s->top)--]) ;
        }
}

element here = {1, 0}, entry = {1, 0};

char maze[MAZE_SIZE][MAZE_SIZE] = {
        {'1','1','1','1','1','1','1','1','1','1'},
        {'e','1','0','1','0','0','0','1','0','1'},
        {'0','0','0','1','0','0','0','1','0','1'},
        {'0','1','0','0','0','1','1','0','0','1'},
        {'1','0','0','0','1','0','0','0','0','1'},
        {'1','0','0','0','1','0','0','0','0','1'},
        {'1','0','0','0','0','0','1','0','1','1'},
        {'1','0','1','1','1','0','1','1','0','1'},
        {'1','1','0','0','0','0','0','0','0','x'},
        {'1','1','1','1','1','1','1','1','1','1'}
} ;

void push_loc(StackType *s, int r, int c) {
        if(r<0 || c<0) {
        return ;
        }
        if(maze[r][c] != '1' && maze[r][c] != '.') {
            element tmp ;
            tmp.r = r ;
            tmp.c = c ;
            push(s, tmp) ;
        }
}

void maze_print(char maze[MAZE_SIZE][MAZE_SIZE]) {
        printf("\n") ;
        for(int r=0; r<MAZE_SIZE; r++) {
            for(int c=0; c<MAZE_SIZE; c++) {
                    printf("%c", maze[r][c]) ; 
            }
        printf("\n") ;
        }
}

int backcount(int r, int c) {
        if ((maze[r + 1][c] == '1' || maze[r + 1][c] == '.') && (maze[r - 1][c] == '1' || maze[r - 1][c] == '.') && (maze[r][c + 1] == '1' || maze[r][c + 1] == '.') && (maze[r][c - 1] == '1' || maze[r][c - 1] == '.'))
        {
            back_count++;
        }
    return back_count;
}

int main(void) {
        int r, c ; 
        StackType s ;

        init_stack(&s) ;
        here = entry ;
        while(maze[here.r][here.c] != 'x') {
            r = here.r ;
            c = here.c ;
            maze[r][c] = '.' ;
            maze_print(maze) ;
            push_loc(&s, r-1,c) ;
            push_loc(&s, r+1,c) ;
            push_loc(&s, r,c-1) ;
            push_loc(&s, r,c+1) ;
            backcount(r, c) ;
    
            if(is_empty(&s)) {
                    printf("Fail\n") ;
                    return 0 ;
            }
            else {
                    here = pop(&s) ;
            }
        } 
        printf("Success\n") ;
        printf("Back count : %d\n", backcount(r, c)) ;

        return 0 ;
}

我做了另一个堆栈来推动所有的移动路径并打印出来，输出是这个迷宫的（1，4）到（4，3）。
这是将产生我想要的输出的路径。

Path to exit : (1, 0)
(2, 0)
(2, 1)
(2, 2)
(2, 3)
(3, 3)
(3, 4)
(2, 4)
(2, 5)
(2, 6)
(1, 6)
(1, 5)
(1, 4)
(1, 5)
(1, 6)
(2, 6)
(2, 5)
(2, 4)
(3, 4)
(3, 3)
(4, 3)
(4, 2)
(4, 1)
(5, 1)
(5, 2)
(5, 3)
(6, 3)
(6, 4)
(6, 5)
(7, 5)
(8, 5)
(8, 6)
(8, 7)
(8, 8)

澄清一下，你的目标是解决迷宫，同时也提供算法找到的路径，对吗？
现在，当你站在一个单元格上时，你正在存储堆栈中所有相邻的单元格。这对于保存尚未探索的单元格列表很好，但对于存储到目前为止所采用的路径则不太好。
例如，假设你有这个迷宫：

// e = entrance, x = exit, 0 = path, 1 = wall
  col 0 1 2
row
  0   1 0 1
  1   0 e x
  2   1 0 1

出口就在入口旁边。使用您的方法，在循环的第一次迭代中，您将把e旁边的所有tile放入堆栈中，如下所示：

Stack:
0: (0, 1)  // above e
1: (2, 1)  // below e
2: (1, 0)  // left of e
3: (1, 2)  // right of e

然后你会弹出堆栈的顶部，这是入口右边的单元格，你会看到它是出口，然后你的程序就完成了。
但堆栈的状态仍然是这样的：

Stack:
0: (0, 1)  // above e
1: (2, 1)  // below e
2: (1, 0)  // left of e

如果你用视觉的方式来展示它，就是：

. o .
o . .
. o .

堆栈根本不反映让你走到最后的路径。相反，它反映了所有的瓷砖，你 * 没有 * 访问，以找到结束。
相反，尝试颠倒使用堆栈的方式。不要存储所有你没有访问过的单元格，而是尝试存储所有你访问过的单元格。这样，您就可以使用堆栈来存储到达当前位置的路径。

主回路：
检查所有4个相邻单元格，并对每一个单元格执行以下操作：
如果是exit，则将当前位置和邻居的位置压入堆栈，然后退出Main Loop。
如果它是一个空的空间，则将当前位置压入堆栈并开始主循环的下一次迭代
如果是墙或已访问过，则不执行任何操作并继续检查当前单元格的其他邻居
您已检查了所有相邻单元格，但找不到要转到的单元格。这意味着我们必须后退一步，因为我们无法从这里到达出口。
将此单元格标记为“已访问”（您使用的是'.'字符）
从堆栈中弹出一个单元格，这是你的新位置（如果你不能，因为堆栈是空的，那么迷宫是不可解的）
堆栈现在保存了您到达出口所采用的路径。

这大概就是你的main函数应该看起来的样子，我还没有测试它的语法错误，但是注解应该清楚地说明每一步发生了什么：

element neighbors[4] = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}};

while (true) {

  bool exit_found = false, took_step = false;

  // Check all 4 neighbors
  for (int i = 0; i < 4; i++) {
    int r = here.r + neighbors[i].r; // neighboring row
    int c = here.c + neighbors[i].c; // neighboring column
    char neighbor = maze[r][c];

    if (neighbor == 'e') {
      // The exit! The maze is solved.

      // The stack holds the path that is behind us,
      // complete the path by adding the current location and the exit.
      push_loc(&s, here.r, here.c);
      push_loc(&s, r, c);

      exit_found = true;
      break; // Stop checking the neighbors
    }

    if (neighbor == '0') {
      // A new path we can go! Take a step forward.

      // The stack holds the path behind us,
      // add our current location to it and then move to the new location.
      push_loc(&s, here.r, here.c);
      here.r = r;
      here.c = c;

      took_step = true;
      break; // Stop checking the neighbors.
    }

    // If the neighbor is anything other than exit or empty, (visited, or wall)
    // then we do nothing and keep checking the other neighbors.
  }

  // Depending on what we found, what should we do?
  if (exit_found) break; // We're done!
  if (took_step) continue; // We're on a new location now, repeat the process!

  // We've checked all neighboring and we didn't take a step or found the exit.
  // That means we have to take a step back because we can't get to the exit from here.

  // Mark this cell as visited.
  maze[here.r][here.c] = '.';

  // Make sure we can still pop from the stack.
  if (is_empty(&s)) {
    printf("unsolvable");
    exit(-1);
  }

  // Take a step back.

  // stack = [loc1, loc2, loc3, loc4], here = loc5
  here = pop(&s);
  // stack = [loc1, loc2, loc3],       here = loc4
}

printf("The path to the exit is:\n");

for (int i = 0; i <= s.top; i++) {
  printf("(%d, %d)\n", s.data[i].r, s.data[i].c);
}

我刚刚意识到你（和我）的代码还有一些其他问题，当你检查一个瓦片的邻居时，你没有检查这些瓦片是否在迷宫的边界内（例如，当我们查看一个单元的左侧时，数组的索引-1-你的例子中的入口点有这个问题）。这应该不会太难修复，你只需要记住这样做，因为C不会给予你任何警告，当它发生时，它只是程序可能会segfault或你的结果变得胡言乱语。

如何使用堆栈打印移动路径(在C99中)？

1条答案

相关问题

热门标签

最新问答