Question

数据结构迷宫问题（c语言）

1.输入数据
2.输入迷宫的大小m行和n列，两者为整数
3.由随机数产生0或1，建立迷宫
4.输出数据
首先输出模拟迷宫的二维数组，若存在最短路径，则由出口回溯到入口打印这一条路径，如下所示：（m，n），...,(i,j),...,(1,1)
如无通道，则打印：
There is no path

Answer 1

#include<stdio.h>
#include<string.h>
#include<stdlib.h>
#include<time.h>
int m,n,num,map[101][101],f[101][101],a[101],b[101],d[2][4]={0,-1,0,1,-1,0,1,0},ans,flag;
void maze()
{
int i,j;
time_t t;
srand(time(&t));
for(i=0;i<m;i++)
for(j=0;j<n;j++)
{
map[i][j]=rand()%2;
if(map[i][j])
num++;
}
if(num<m*n/2)
{
for(i=0;i<m;i++)
for(j=0;j<n;j++)
if(!map[i][j])
map[i][j]+=rand()%2;
}
map[0][0]=1;
map[m-1][n-1]=1;
}
void print()
{
int i,j;
for(i=0;i<m;i++)
for(j=0;j<n;j++)
{
printf("%d ",map[i][j]);
if(j==n-1)puts("");
}
}
void dfs(int x,int y)
{
int i,tx,ty;
if(!flag)
return;
for(i=0;i<4;i++)
{
tx=x+d[0][i];
ty=y+d[1][i];
if(!f[tx][ty]&&tx>=0&&ty>=0&&tx<m&&ty<n&&map[tx][ty])
{
f[tx][ty]=1;
a[ans]=tx;
b[ans++]=ty;
if(tx+ty==0)
{
printf("(%d,%d)\n",m,n);
for(flag=i=0;i<ans;i++)
printf("(%d,%d)\n",a[i]+1,b[i]+1);
return;
}
dfs(tx,ty);
f[tx][ty]=0;
ans--;
}
}
}
int main()
{
while(scanf("%d%d",&m,&n),m+n)
{
memset(f,0,sizeof(f));
num=ans=0;
flag=1;
maze();
print();
dfs(m-1,n-1);
if(flag)
puts("There is no path");
}
return 0;
}

Answer 2

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#define MAXLEN 10//迷宫包括外墙最大行列数目
#define TRUE 1
#define FALSE 0
#define OK 1
#define ERROR 0
#define OVERFLOW -2
typedef int Status;
#define STACK_INIT_SIZE 100 //存储空间初始分配量

typedef struct{
int r,c;
} PosType;//迷宫中r行c列的位置

typedef struct MazeType{
int r;
int c;
char arr[MAXLEN][MAXLEN];//可取' ''*' '@' '#'
}MazeType; //迷宫类型

typedef struct{
int step; // 当前位置在路径上的“序号”
PosType seat; //当前的坐标位置
int di; //往下一坐标位置的方向
}SElemType;

typedef struct NodeType{
SElemType data;
NodeType *next;
}NodeType,*LinkType;//结点类型
typedef struct SqStack{
LinkType top;
int stacksize;
}SqStack; //栈类型

PosType start;
PosType end;
MazeType maze;
bool found;

Status InitStack(SqStack &S){
S.top=(LinkType)malloc(sizeof(NodeType));
S.top->next=NULL;
S.stacksize=0;
return OK;
}//InitStack;

Status Push(SqStack &S,SElemType &e){
LinkType p;
p=(NodeType*)malloc(sizeof(NodeType));
if(!p) return ERROR;
p->data=e;
p->next=S.top;
S.top=p;
S.stacksize++;
//S.top=S.base+S.stacksize;
//S.top->data=e;
return OK;
}//Push

Status StackEmpty(SqStack S){
if(S.top->next==NULL) return OK;
return ERROR;
}//StackEmpty

Status Pop(SqStack &S,SElemType &e){
LinkType p;
if(StackEmpty(S)) return ERROR;
p=S.top;
e=p->data;
S.top=S.top->next;
S.stacksize--;
free(p);
return OK;
// 栈顶元素出栈
}//Pop

Status DestroyStack(SqStack &S){//销毁栈S,
LinkType p;
while(S.top!=NULL){
p=S.top;
S.top=S.top->next;
free(p);
}//while
if(S.top==NULL) return OK;
else return ERROR;
}//DestroyStack

Status MarkPrint(MazeType &maze,PosType curpos){
maze.arr[curpos.r][curpos.c]='@';//"@"表示曾走过但不通
return OK;
}//Markprint曾走过但不是通路标记并返回OK

Status FootPrint(MazeType &maze,PosType curpos){
maze.arr[curpos.r][curpos.c]='*';//"*"表示可通
return OK;
}//FootPrint

PosType NextPos(PosType &curpos,int i){
PosType cpos;
cpos=curpos;
switch(i){ //1.2.3.4分别表示东,南,西,北方向
case 1 : cpos.c+=1; break;
case 2 : cpos.r+=1; break;
case 3 : cpos.c-=1; break;
case 4 : cpos.r-=1; break;
default: exit(ERROR);
}//switch
return cpos;
}//Nextpos

Status Pass(MazeType &maze, PosType curpos){
/*for(int i=0;i<10;i++){
for(int j=0;j<10;j++){
printf("%4c",maze.arr[i][j]);
}
printf("\n");
}*/
//char a=' ';
//printf("%4d",a);
//printf("%d,%d",curpos.r,curpos.c);
//printf("%4c",maze.arr[1][1]);
if(maze.arr[curpos.r][curpos.c]==' '){//当前位置可通
//printf("go");
return TRUE;
}//if
else{
//printf("go");
return FALSE;
}//else
}//Pass

void InitMaze(MazeType &maze, char a[MAXLEN][MAXLEN], int row, int col){
//printf("go");
maze.r=row;
maze.c=col;
//printf("%d,%d",row,col);
for(int i=0;i<=col+1;i++){a[0][i]='1';a[row+1][i]='1';}
//printf("go");
for(i=0;i<=row+1;i++){a[i][0]='1';a[i][col+1]='1';}
//printf("go");
/*for(i=0;i<10;i++){
for(int j=0;j<10;j++){
printf("%4c",a[i][j]);
}
printf("\n");
}
*/
for(i=0;i<=maze.r+2;i++){
for(int j=0;j<maze.c+2;j++){
if(a[i][j]=='1') maze.arr[i][j]='#';
//if(a[i][j]==0) maze.arr[i][j]=' ';
else maze.arr[i][j]=' ';
}//for
}//for
}//InitMaze

Status MazePath(MazeType &maze,PosType start,PosType end)
{//求解迷宫maze中，从入口start到出口end的一条路径，
//若存在则返回TRUE,否则返回FALSE
PosType curpos;
int curstep;
SqStack S;
SElemType e;

InitStack(S);
curpos=start;//设定“当前位置”为“入口位置”
curstep=1; //探索第一步
found=false;

do{
if(Pass(maze,curpos))
{
//当前位置可以通过，即是未曾走到过的通道块留下足迹
FootPrint(maze,curpos);//做可以通过的标识

e.step=curstep;
e.seat=curpos;
e.di=1;//为栈顶元素赋值

if(Push(S,e)!=OK) return ERROR;
if(curpos.r==end.r && curpos.c==end.c) found=true;//如果到达终点返回true

else{
curpos=NextPos(curpos,1);//下一位置是当前位置的东邻
curstep++;//探索下一步
}//else
}//if

else
if(StackEmpty(S)!=1)
{
Pop(S,e);
while(e.di==4 && !StackEmpty(S))
{

MarkPrint(maze,e.seat);
Pop(S,e);
curstep--;
}//while
if(e.di<4)
{
e.di++;
Push(S,e);//换下个方向探索
curpos=NextPos(e.seat,e.di);
}//if
}//if
}while(StackEmpty(S)!=1&&!found);
DestroyStack(S);
if(found)
return true;
else
return false;//没有找到路径

}//MazePath

void PrintMaze(MazeType &maze){
//将标记路径信息的迷宫输出到终端(包括外墙)
for(int i=0;i<=maze.r+2;i++){
for(int j=0;j<=maze.c+2;j++){
printf("%4c",maze.arr[i][j]);//输出迷宫
}//for
printf("\n");
}//for
}//PrintMaze

void Initialization(){
system("cls");
printf("********************************************************");
printf("\n*CreatMaze--c MazePath--m PrintMaze--p Quit--q*");
printf("\n********************************************************");
}//Initialization

void ReadCommand(char &cmd){
do{
if(cmd=='c'||cmd=='C'){
printf("\n********************************************************");
printf("\n*Enter a operation :m或M *");
printf("\n*退出--Enter a operation :q或Q *");
printf("\n********************************************************");
}//if
else if(cmd=='m'||cmd=='M'){
printf("\n********************************************************");
printf("\n*Enter a operation :p或P *");
printf("\n*退出--Enter a operation :q或Q *");
printf("\n********************************************************");
}//else if
else if(cmd=='0'){
printf("\n********************************************************");
printf("\n*Enter a operation :c或P *");
printf("\n*退出--Enter a operation :q或Q *");
printf("\n********************************************************");
}
printf("\n\n Operration:-");
cmd=getchar();
}while(!(cmd=='c'||cmd=='C'||cmd=='m'||cmd=='M'||cmd=='p'||cmd=='P'||cmd=='q'||cmd=='Q'));
}//ReadCommand

void Interpre(char cmd){
//MazeType maze;//开始的时候定义在这个地方，不是全局的，调用出现了问题。
//PosType start;//开始的时候定义在这个地方，不是全局的，调用出现了问题。
//PosType end;//开始的时候定义在这个地方，不是全局的，调用出现了问题。
switch(cmd){
case 'C':
case 'c':{
int rnum, cnum, i=0,m=1,n=1;
char a2[MAXLEN][MAXLEN];
char input[1];
char data[100000];
printf("\n请输入迷宫数据文件名！\n");
//printf("go");
scanf("%s",input);
FILE *fp;
fp=fopen(input,"r");
//printf("go");
if(!fp){
printf("\n不能打开文件\n");
break;
}//if
//printf("go");
while(!feof(fp)){
fscanf(fp,"%s",&data[i]);
if(i==0){rnum=(int)data[i]-(int)'0';/*printf("%d",rnum);*/}
if(i==1){cnum=(int)data[i]-(int)'0';/*printf("%d",rnum);*/}
if(i>=2){
if(n>cnum){m++;n=1;}
a2[m][n]=data[i];
//printf("%d",a2[m][n]);
n++;
}//if
i++;
}//while
fclose(fp);
//printf("go");
InitMaze(maze, a2, rnum, cnum);
printf("\n迷宫建立完成！！\n");
//PrintMaze(maze);
break;
}//case
case 'M':
case 'm':{
printf("\n请输入迷宫入口的坐标，以空格为间隔:--");
scanf("%d %d",&start.r,&start.c);
printf("\n请输入迷宫出口的坐标，以空格为间隔:--");
scanf("%d %d",&end.r,&end.c);
//printf("%d,%d,%d,%d",start.r,start.c,end.r,end.c);
//PrintMaze(maze);
MazePath(maze, start, end);
//PrintMaze(maze);
break;
}//case
case 'P':
case 'p':{
if(found){
printf("\n求解迷宫的结果如下--\n");
PrintMaze(maze);
}//if
else{
printf("\n找不到路径！\n");
}//else
}//case
}//switch
}//Interpre

void main(){
char cmd='0';
Initialization();
//cmd=getchar();
do{
ReadCommand(cmd);
Interpre(cmd);
}while(cmd!='q'&&cmd!='Q');
}//main

Answer 3

等高手，思想可能较容易，写出来会很多