用C语言问题描述:以一个m*n的长方阵表示迷宫,0和1分别表示迷宫中的通路和障碍。设计一个程序,对任意设定的迷宫,求出一条从入口到出口的通路,或得出没有通路的结论。
时间: 2023-08-31 21:09:26 浏览: 55
以下是使用C语言实现求解迷宫通路的示例代码:
```c
#include <stdio.h>
#include <stdlib.h>
#define MAX_ROW 100
#define MAX_COL 100
// 迷宫的结构体
typedef struct {
int row; // 行数
int col; // 列数
int maze[MAX_ROW][MAX_COL]; // 迷宫数组
} Maze;
// 栈的结构体
typedef struct {
int row; // 行号
int col; // 列号
} Stack;
// 初始化迷宫
void initMaze(Maze *maze) {
int i, j;
printf("请输入迷宫的行数和列数:");
scanf("%d %d", &maze->row, &maze->col);
printf("请输入迷宫的地图:\n");
for (i = 0; i < maze->row; i++) {
for (j = 0; j < maze->col; j++) {
scanf("%d", &maze->maze[i][j]);
}
}
}
// 打印迷宫
void printMaze(Maze *maze) {
int i, j;
printf("迷宫地图如下:\n");
for (i = 0; i < maze->row; i++) {
for (j = 0; j < maze->col; j++) {
printf("%d ", maze->maze[i][j]);
}
printf("\n");
}
}
// 判断当前位置是否能走,能走返回1,否则返回0
int canMove(Maze *maze, int row, int col) {
if (row < 0 || row >= maze->row || col < 0 || col >= maze->col) {
return 0; // 超出边界
}
if (maze->maze[row][col] == 1) {
return 0; // 是障碍
}
return 1;
}
// 求解迷宫通路
void solveMaze(Maze *maze) {
Stack stack[MAX_ROW * MAX_COL]; // 定义栈
int top = 0; // 栈顶
int i, row, col, found = 0;
printf("请输入起点坐标:");
scanf("%d %d", &row, &col);
row--; // 行号从0开始
col--; // 列号从0开始
stack[top].row = row; // 将起点入栈
stack[top].col = col;
while (top >= 0 && !found) {
row = stack[top].row; // 取出栈顶元素
col = stack[top].col;
top--; // 栈顶下移
if (maze->maze[row][col] == 2) { // 如果是终点,找到路径
found = 1;
} else { // 不是终点,继续搜索
maze->maze[row][col] = 1; // 标记为已走过
// 上下左右四个方向依次搜索
if (canMove(maze, row - 1, col)) { // 上
top++; // 新点入栈
stack[top].row = row - 1;
stack[top].col = col;
}
if (canMove(maze, row, col + 1)) { // 右
top++;
stack[top].row = row;
stack[top].col = col + 1;
}
if (canMove(maze, row + 1, col)) { // 下
top++;
stack[top].row = row + 1;
stack[top].col = col;
}
if (canMove(maze, row, col - 1)) { // 左
top++;
stack[top].row = row;
stack[top].col = col - 1;
}
}
}
if (found) { // 打印路径
printf("找到通路,路径如下:\n");
for (i = 0; i <= top; i++) {
printf("(%d,%d)->", stack[i].row + 1, stack[i].col + 1);
}
printf("\n");
} else {
printf("没有通路!\n");
}
}
int main() {
Maze maze;
initMaze(&maze); // 初始化迷宫
printMaze(&maze); // 打印迷宫
solveMaze(&maze); // 求解迷宫通路
return 0;
}
```
这个程序使用了深度优先搜索算法来求解迷宫通路。首先让用户输入迷宫的行数和列数,然后输入迷宫的地图,其中0表示通路,1表示障碍。程序会提示用户输入起点坐标,然后从起点开始搜索,如果找到终点就打印路径,否则打印“没有通路”。
阅读全文