Alogrithm：老鼠走迷官（一）
1. 说明
老鼠走迷宫是递回求解的基本题型，我们在二维阵列中使用2表示迷宫墙壁，使用1来表示老鼠的行走路径，试以程式求出由入口至出口的路径。
2. 解法
以下是用 C 语言实现的一个递归算法，解决迷宫问题（老鼠走迷宫）。我们使用二维数组表示迷宫，其中：
- 0 表示可以走的路径。
- 2 表示墙壁（不可通行）。
- 1 表示老鼠当前已经走过的路径。
2.1 代码实现
#include <stdio.h>
#define N 5 // 迷宫的大小
// 迷宫示例：0 表示路径，2 表示墙壁
int maze[N][N] = {
{0, 2, 0, 0, 0},
{0, 2, 0, 2, 0},
{0, 0, 0, 2, 0},
{0, 2, 2, 2, 0},
{0, 0, 0, 0, 0}
};
// 判断位置 (x, y) 是否可以通行
int isValid(int x, int y) {
return (x >= 0 && x < N && y >= 0 && y < N && maze[x][y] == 0);
}
// 递归解决迷宫问题
int solveMaze(int x, int y) {
// 如果到达出口
if (x == N - 1 && y == N - 1) {
maze[x][y] = 1; // 标记路径
return 1;
}
// 检查当前位置是否有效
if (isValid(x, y)) {
maze[x][y] = 1; // 标记为路径
// 尝试向下走
if (solveMaze(x + 1, y)) return 1;
// 尝试向右走
if (solveMaze(x, y + 1)) return 1;
// 尝试向上走
if (solveMaze(x - 1, y)) return 1;
// 尝试向左走
if (solveMaze(x, y - 1)) return 1;
// 如果无法继续，回溯并标记为未走过
maze[x][y] = 0;
}
return 0; // 无法找到路径
}
// 打印迷宫
void printMaze() {
for (int i = 0; i < N; i++) {
for (int j = 0; j < N; j++) {
printf("%d ", maze[i][j]);
}
printf("\n");
}
}
int main() {
printf("Original Maze:\n");
printMaze();
if (solveMaze(0, 0)) {
printf("\nPath Found:\n");
printMaze();
} else {
printf("\nNo Path Found\n");
}
return 0;
}2.2 样例运行
2.2.1 输入迷宫：
0 2 0 0 0
0 2 0 2 0
0 0 0 2 0
0 2 2 2 0
0 0 0 0 02.2.2 输出结果：
原始迷宫：
0 2 0 0 0
0 2 0 2 0
0 0 0 2 0
0 2 2 2 0
0 0 0 0 0如果找到路径：
1 2 0 0 0
1 2 0 2 0
1 1 1 2 0
0 2 2 2 0
0 0 0 0 0如果没有路径（例如迷宫被堵死）：
No Path Found2.3 复杂度分析
- 时间复杂度：O(4^(N*M))，其中 N*M 是迷宫大小。由于每个位置最多有 4 种移动方向，递归深度是迷宫的大小。
- 优化方式：可以使用动态规划或标记避免重复计算。
- 空间复杂度：O(N*M)，递归栈深度。