迷宫求解是一个经典的算法问题，通常使用深度优先搜索（DFS）或广度优先搜索（BFS）来解决。而栈是DFS的一个常用工具，因为栈是后进先出（LIFO）的数据结构，可以很好地模拟递归调用时的函数调用栈。
以下是一个使用栈来求解迷宫问题的C语言示例。在这个示例中，我们假设迷宫是一个二维数组，其中0表示可通过的空格，1表示墙壁或障碍物，2表示起点，3表示终点。
数据结构定义
首先，我们需要定义迷宫的数据结构以及栈的数据结构。
|
#include <stdio.h> |
|
#include <stdlib.h> |
|
#include <stdbool.h> |
|
|
|
#define MAX_SIZE 10 |
|
|
|
typedef struct { |
|
int x; |
|
int y; |
|
} Position; |
|
|
|
typedef struct { |
|
Position pos; |
|
int dir; // 0: 上, 1: 右, 2: 下, 3: 左 |
|
} StackNode; |
|
|
|
typedef struct { |
|
StackNode data[MAX_SIZE * MAX_SIZE]; |
|
int top; |
|
} Stack; |
|
|
|
int maze[MAX_SIZE][MAX_SIZE] = { |
|
// 迷宫布局，0为空格，1为墙壁，2为起点，3为终点 |
|
// ... |
|
}; |
|
|
|
int mazeSize = MAX_SIZE; // 迷宫的大小 |
栈的操作函数
接下来，我们实现栈的基本操作函数。
|
void initStack(Stack *s) { |
|
s->top = -1; |
|
} |
|
|
|
bool isFull(Stack *s) { |
|
return s->top == MAX_SIZE * MAX_SIZE - 1; |
|
} |
|
|
|
bool isEmpty(Stack *s) { |
|
return s->top == -1; |
|
} |
|
|
|
bool push(Stack *s, Position pos, int dir) { |
|
if (isFull(s)) { |
|
return false; |
|
} |
|
s->data[++s->top].pos = pos; |
|
s->data[s->top].dir = dir; |
|
return true; |
|
} |
|
|
|
bool pop(Stack *s, Position *pos, int *dir) { |
|
if (isEmpty(s)) { |
|
return false; |
|
} |
|
*pos = s->data[s->top].pos; |
|
*dir = s->data[s->top].dir; |
|
s->top--; |
|
return true; |
|
} |
迷宫求解函数
现在，我们实现迷宫求解函数，使用DFS和栈。
|
bool isValid(Position pos) { |
|
return pos.x >= 0 && pos.x < mazeSize && |
|
pos.y >= 0 && pos.y < mazeSize && |
|
maze[pos.x][pos.y] == 0; // 空格可走 |
|
} |
|
|
|
bool dfs(Stack *s, Position *endPos) { |
|
Position currentPos, nextPos; |
|
int dir; |
|
|
|
if (pop(s, ¤tPos, &dir)) { |
|
// 尝试四个方向 |
|
int dx[] = {-1, 0, 1, 0}; // 上, 右, 下, 左 |
|
int dy[] = {0, 1, 0, -1}; // 上, 右, 下, 左 |
|
|
|
for (int i = 0; i < 4; ++i) { |
|
nextPos.x = currentPos.x + dx[i]; |
|
nextPos.y = currentPos.y + dy[i]; |
|
|
|
if (isValid(nextPos)) { |
|
maze[nextPos.x][nextPos.y] = 1; // 标记为已访问 |
|
|
|
if (nextPos.x == endPos->x && nextPos.y == endPos->y) { |
|
// 到达终点，打印路径或进行其他操作 |
|
// ... |
|
return true; |
|
} else { |
|
push(s, nextPos, i); // 将下一步压入栈中 |
|
} |
|
} |
|
} |
|
} |
|
|
|
return false; |
|
} |
|
|
|
void solveMaze() { |
|
Position startPos = { /* 起点坐标 */ }; |
|
Position endPos = { /* 终点坐标 */ }; |
|
Stack s; |
|
initStack(&s); |
|
|
|
maze[startPos.x][startPos.y] = 1; // 标记起点为已访问 |
|
push(&s, startPos, -1); // 将起点压入栈中，方向 |
