UC知道迷宫问题 用C语言不要C++
来源：百度知道 编辑：UC知道 时间：2024/09/24 14:15:33
迷宫问题
1 问题描述
以一个m*n的长方阵表示迷宫，0和1分别表示迷宫中的通路和障碍。设计一个程序，对任意设定的迷宫，求出一条从入口到出口的通路，或得出没有通路的结论。
2 基本要求
（1）实现一个以连标作存储结构的栈类型，然后便携一个求解迷宫的非递归程序。求得的通路以三元组（i,j,d）的形式输出，其中：（i,j）指示迷宫中的一个坐标，d表示走到下一坐标的方向。（2）编写递归形式的算法，求得迷宫中所有可能的通路；
3 测试数据
迷宫的测试数据如下：左上角（1，1）为入口，右下角（9,8）为出口。
1 2 3 4 5 6 7 8
0 0 1 0 0 0 1 0
0 0 1 0 0 0 1 0
0 0 0 0 1 1 0 1
0 1 1 1 0 0 1 0
0 0 0 1 0 0 0 0
0 1 0 0 0 1 0 1
0 1 1 1 1 0 0 1
1 1 0 0 0 1 0 1
1 1 0 0 0 0 0 0
1 问题描述
以一个m*n的长方阵表示迷宫，0和1分别表示迷宫中的通路和障碍。设计一个程序，对任意设定的迷宫，求出一条从入口到出口的通路，或得出没有通路的结论。
2 基本要求
（1）实现一个以连标作存储结构的栈类型，然后便携一个求解迷宫的非递归程序。求得的通路以三元组（i,j,d）的形式输出，其中：（i,j）指示迷宫中的一个坐标，d表示走到下一坐标的方向。（2）编写递归形式的算法，求得迷宫中所有可能的通路；
3 测试数据
迷宫的测试数据如下：左上角（1，1）为入口，右下角（9,8）为出口。
1 2 3 4 5 6 7 8
0 0 1 0 0 0 1 0
0 0 1 0 0 0 1 0
0 0 0 0 1 1 0 1
0 1 1 1 0 0 1 0
0 0 0 1 0 0 0 0
0 1 0 0 0 1 0 1
0 1 1 1 1 0 0 1
1 1 0 0 0 1 0 1
1 1 0 0 0 0 0 0
#include<stdio.h>
#include<stdlib.h>
#define MAXSIZE 100
#define m 6
#define n 8
//定义方向坐标
typedef struct
{
int x,y;
}item;
//定义数据结构x，y，行走方向d
typedef struct
{
int x,y,d;
}datatype;
//定义栈
typedef struct
{
datatype data[MAXSIZE];
int top;
}SeqStack;
//设置迷宫，外圈用1包围. 0表示有路径
int maze[m+2][n+2]={
{1,1,1,1,1,1,1,1,1,1},
{1,0,1,1,1,0,1,1,1,1},
{1,1,0,1,0,1,1,1,1,1},
{1,0,1,0,0,0,0,0,1,1},
{1,0,1,1,1,0,1,1,1,1},
{1,1,0,0,1,1,0,0,0,1},
{1,0,1,1,0,0,1,1,0,1},
{1,1,1,1,1,1,1,1,1,1}
};
//定义任意数据相邻的8个方向（从正东方向，逆时针开始）
item move[8]={{0,1},{1,1},{1,0},{1,-1},
{0,-1},{-1,-1},{-1,0},{-1,1}
};
//栈初始化
SeqStack *Init_SeqStack()
{
SeqStack *s;
s=(SeqStack *)malloc(sizeof(SeqStack));
s->top=-