用栈求解迷宫问题的所有路径及最短路径程序

以下是用栈求解迷宫问题的所有路径及最短路径的程序：

1. 定义迷宫的大小和起点、终点的坐标。

2. 定义一个栈，用来存储路径。

3. 定义一个二维数组，用来表示迷宫的地图。

4. 定义一个二维数组，用来记录每个点是否被访问过。

5. 定义一个结构体，用来存储每个点的坐标和步数。

6. 定义一个函数，用来判断当前点是否可以走。

7. 定义一个函数，用来求解迷宫问题的所有路径。

8. 定义一个函数，用来求解迷宫问题的最短路径。

9. 在主函数中调用以上两个函数，输出结果。

具体实现细节可以参考以下代码：

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

#define MAX_ROW 10
#define MAX_COL 10

typedef struct {
int row;
int col;
int step;
} Point;

int maze[MAX_ROW][MAX_COL] = {
{, 1, , , , , , , , },
{, 1, , 1, 1, 1, 1, 1, 1, },
{, 1, , 1, , , , , 1, },
{, 1, , 1, , 1, 1, , 1, },
{, 1, , 1, , 1, 1, , 1, },
{, 1, , 1, , , , , 1, },
{, 1, , 1, 1, 1, 1, 1, 1, },
{, 1, , , , , , , 1, },
{, 1, 1, 1, 1, 1, 1, 1, 1, },
{, , , , , , , , , }
};

int visited[MAX_ROW][MAX_COL] = {};

Point stack[MAX_ROW * MAX_COL];
int top = -1;

void push(Point p) {
stack[++top] = p;
}

Point pop() {
return stack[top--];
}

int is_empty() {
return top == -1;
}

int is_valid(Point p) {
if (p.row < || p.row >= MAX_ROW || p.col < || p.col >= MAX_COL) {
return ;
}
if (maze[p.row][p.col] == || visited[p.row][p.col] == 1) {
return ;
}
return 1;
}

void print_path() {
int i;
for (i = ; i <= top; i++) {
printf("(%d,%d) ", stack[i].row, stack[i].col);
}
printf("\n");
}

void find_all_paths(Point start, Point end) {
Point cur = start;
cur.step = ;
visited[cur.row][cur.col] = 1;
push(cur);
while (!is_empty()) {
cur = pop();
if (cur.row == end.row && cur.col == end.col) {
print_path();
visited[cur.row][cur.col] = ;
top--;
continue;
}
Point next;
next.row = cur.row - 1;
next.col = cur.col;
next.step = cur.step + 1;
if (is_valid(next)) {
visited[next.row][next.col] = 1;
push(next);
}
next.row = cur.row + 1;
next.col = cur.col;
if (is_valid(next)) {
visited[next.row][next.col] = 1;
push(next);
}
next.row = cur.row;
next.col = cur.col - 1;
if (is_valid(next)) {
visited[next.row][next.col] = 1;
push(next);
}
next.row = cur.row;
next.col = cur.col + 1;
if (is_valid(next)) {
visited[next.row][next.col] = 1;
push(next);
}
visited[cur.row][cur.col] = ;
top--;
}
}

void find_shortest_path(Point start, Point end) {
Point cur = start;
cur.step = ;
visited[cur.row][cur.col] = 1;
push(cur);
while (!is_empty()) {
cur = pop();
if (cur.row == end.row && cur.col == end.col) {
printf("Shortest path: %d\n", cur.step);
visited[cur.row][cur.col] = ;
top--;
continue;
}
Point next;
next.row = cur.row - 1;
next.col = cur.col;
next.step = cur.step + 1;
if (is_valid(next)) {
visited[next.row][next.col] = 1;
push(next);
}
next.row = cur.row + 1;
next.col = cur.col;
if (is_valid(next)) {
visited[next.row][next.col] = 1;
push(next);
}
next.row = cur.row;
next.col = cur.col - 1;
if (is_valid(next)) {
visited[next.row][next.col] = 1;
push(next);
}
next.row = cur.row;
next.col = cur.col + 1;
if (is_valid(next)) {
visited[next.row][next.col] = 1;
push(next);
}
visited[cur.row][cur.col] = ;
top--;
}
}

int main() {
Point start = {, };
Point end = {9, 9};
printf("All paths:\n");
find_all_paths(start, end);
printf("------------------------------\n");
find_shortest_path(start, end);
return ;
}