Alogrithm：老鼠走迷官（一）

老鼠走迷宫是递回求解的基本题型，我们在二维阵列中使用2表示迷宫墙壁，使用1来表示老鼠的行走路径，试以程式求出由入口至出口的路径。

以下是用 C 语言实现的一个递归算法，解决迷宫问题（老鼠走迷宫）。我们使用二维数组表示迷宫，其中：

• 0 表示可以走的路径。
• 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;
}

---

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

原始迷宫：

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 Found

---