用C语言问题描述:以一个m*n的长方阵表示迷宫,0和1分别表示迷宫中的通路和障碍。设计一个程序,对任意设定的迷宫,求出一条从入口到出口的通路,或得出没有通路的结论。
时间: 2023-06-19 13:05:03 浏览: 104
以下是用C语言实现的迷宫求解程序:
```c
#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>
#define MAX_ROW 20
#define MAX_COL 30
typedef struct {
int row, col; // 行、列
} Position;
Position stack[MAX_ROW*MAX_COL]; // 用数组实现栈
int top = -1; // 栈顶指针
void push(Position p) {
stack[++top] = p;
}
Position pop() {
return stack[top--];
}
bool is_empty() {
return top == -1;
}
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,0,0,0,1,0,0,0,1,0,0,0,1,1,1,1,1,1,1,0,1,0,1,0,1,0,1,0,1,1},
{1,0,1,0,1,0,1,1,1,1,1,0,1,0,0,0,0,0,1,0,1,0,1,0,1,0,1,0,0,1},
{1,0,1,0,1,1,1,0,0,0,1,0,1,0,1,1,1,0,1,0,1,0,1,0,1,0,1,0,1,1},
{1,0,1,1,1,0,0,0,1,0,1,0,1,0,1,0,1,0,1,0,1,0,1,0,1,0,1,0,0,1},
{1,0,1,0,0,0,1,0,1,0,1,1,1,1,1,0,1,0,1,0,1,0,1,0,1,0,1,0,1,1},
{1,0,1,0,1,1,1,0,1,0,1,0,0,0,1,0,1,0,1,0,1,0,1,0,1,0,1,0,1,1},
{1,0,0,0,1,0,0,0,1,0,1,1,1,0,1,0,1,0,1,0,1,0,1,0,1,0,1,0,0,1},
{1,0,1,0,1,1,1,1,1,0,1,0,0,0,1,0,1,0,1,1,1,0,1,0,1,0,1,0,1,1},
{1,0,1,0,0,0,1,0,0,0,1,0,1,1,1,0,1,0,1,0,0,0,1,0,1,0,1,0,0,1},
{1,0,1,1,1,0,1,0,1,1,1,0,1,0,0,0,1,0,1,0,1,1,1,0,1,0,1,0,1,1},
{1,0,0,0,1,0,1,0,0,0,1,0,1,0,1,0,1,0,1,0,0,0,1,0,1,0,1,0,0,1},
{1,1,1,0,1,0,1,1,1,0,1,1,1,0,1,0,1,0,1,1,1,1,1,0,1,0,1,0,1,1},
{1,0,1,0,1,0,1,0,0,0,0,0,0,0,1,0,1,0,1,0,0,0,1,0,1,0,1,0,0,1},
{1,0,1,0,1,0,1,0,1,1,1,1,1,0,1,0,1,0,1,0,1,1,1,0,1,0,1,0,1,1},
{1,0,1,0,1,0,1,0,1,0,0,0,1,0,1,0,1,0,1,0,0,0,1,0,1,0,1,0,0,1},
{1,0,1,1,1,0,1,1,1,0,1,0,1,1,1,0,1,0,1,0,1,1,1,0,1,0,1,0,1,1},
{1,0,0,0,1,0,0,0,0,0,1,0,0,0,0,0,1,0,1,0,0,0,0,0,1,0,1,0,0,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] = {0};
bool solve_maze(int row, int col) {
push((Position){row, col});
visited[row][col] = 1;
while (!is_empty()) {
Position p = pop();
int r = p.row, c = p.col;
if (r == MAX_ROW-1 && c == MAX_COL-1) { // 到达终点
printf("到达终点!\n");
return true;
}
// 向上探索
if (r > 0 && maze[r-1][c] == 0 && visited[r-1][c] == 0) {
push((Position){r-1, c});
visited[r-1][c] = 1;
}
// 向下探索
if (r < MAX_ROW-1 && maze[r+1][c] == 0 && visited[r+1][c] == 0) {
push((Position){r+1, c});
visited[r+1][c] = 1;
}
// 向左探索
if (c > 0 && maze[r][c-1] == 0 && visited[r][c-1] == 0) {
push((Position){r, c-1});
visited[r][c-1] = 1;
}
// 向右探索
if (c < MAX_COL-1 && maze[r][c+1] == 0 && visited[r][c+1] == 0) {
push((Position){r, c+1});
visited[r][c+1] = 1;
}
}
printf("没有通路!\n");
return false;
}
int main() {
solve_maze(0, 0);
return 0;
}
```
该程序使用深度优先搜索算法,在迷宫中搜索通路。将起点入栈,然后循环进行以下操作:从栈中取出一个位置,对其四个相邻位置进行探索,将可访问的位置入栈,并标记为已访问。如果到达终点,则输出“到达终点!”并返回true,否则继续循环。如果栈为空,则没有通路,输出“没有通路!”并返回false。
该程序的时间复杂度为O(mn),其中m、n分别为迷宫的行数和列数。
阅读全文