迷宫问题 用C语言不要C++

Question

迷宫问题
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

Answer 1

#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=-1;
return s;
}
//判断空栈
int Empty_SeqStack(SeqStack *s)
{
if(s->top==-1)
return 1;
else return 0;
}
//入栈
int Push_SeqStack(SeqStack **s,datatype x)
{
if((*s)->top==MAXSIZE-1) return 0;
else
{
(*s)->top++;
(*s)->data[(*s)->top]=x;
return 1;
}
}
//出栈
int Pop_SeqStack(SeqStack **s,datatype *x)
{
if(Empty_SeqStack(*s)) return 0;
else
{
*x=(*s)->data[(*s)->top];
(*s)->top--;
return 1;
}
}

//求迷宫路径
int path(SeqStack **s,int maze[m+2][n+2],item move[8])
{
datatype temp;
int x,y,d,i,j;
temp.x=1;temp.y=1;temp.d=-1; //标记走过路径为-1，从第一个点开始走
Push_SeqStack(s,temp);
while(!Empty_SeqStack(*s))
{
Pop_SeqStack(s,&temp);
x=temp.x;y=temp.y;d=temp.d+1;
while(d<8) //对8个方向分别进行试探
{
i=x+move[d].x;j=y+move[d].y;
if(maze[i][j]==0) //0表示如果路径可走
{
// temp.x=x;temp.y=y;temp.d=d;
temp.x=i;temp.y=j;temp.d=d;
Push_SeqStack(s,temp); //入栈
x=i;y=j;maze[x][y]=-1;
if(x==m && y==n) //找到出口，退出
{
maze[x][y] = 0;
return 1;
}
else d=0; //设置当前栈中点的方向，继续判断
}
else d++; //当前方向不可以，寻找下一个方向
}
}
return 0;
}
//输出迷宫路径
int print(SeqStack **s)
{
datatype temp2;
printf("\nNPC finds the way of the maze!\n");
while(!Empty_SeqStack(*s))
{
Pop_SeqStack(s,&temp2);
maze[temp2.x][temp2.y]='#';
// printf("%c ",maze[temp2.x][temp2.y]);
// if(temp2.x==m+1)
// printf("\n");
}
for(int i = 0; i < m + 2; i ++ )
{
for(int j = 0; j < n + 2; j ++)
{
if(maze[i][j] > 1)printf("%2c ",maze[i][j]);
else printf("%2d ",maze[i][j]);
}
printf("\n");
}
return 1;
}

void main()
{
SeqStack *s;
s=Init_SeqStack();
if(path(&s,maze,move)==1)
print(&s);
else printf("\nThere is not way to get out!\n");
}

Answer 2

具体程序不想弄，建议看看清华的数据结构，自己慢慢弄

Answer 3

20分是不是太少了？