求个c++源码 走迷宫 程序开始运行时显示一个迷宫地图，迷宫*有一只老鼠，迷宫的右下方有一个粮仓
发布网友
发布时间：2022-07-24 21:45
共2个回答
热心网友
时间：2023-10-10 02:33
编译通过，代码如下：
#include<stdio.h>
#include<stdlib.h>
#define N 50
int **maze;
int row;
int col;
int stack[50];//存放路径的栈
void CreateMaze()//用于动态创建迷宫
{
int i,j;
printf("请输入迷宫的行数：");
scanf("%d",&row);
printf("请输入迷宫的列数：");
scanf("%d",&col);
if(row<=0||col<=0)
{
printf("输入的行数或列数不符合规则！\n");
exit(1);
}
//利用指针的指针动态创建二维数组
maze=(int **)malloc((row+2)*sizeof(int *));
for(i=0;i<row+2;i++)
{
maze[i]=(int *)malloc((col+2)*sizeof(int));
}
//加边墙
for(i=0;i<row+2;i++)
{
maze[i][0]=1;
maze[i][col+1]=1;
}
for(i=0;i<col+2;i++)
{
if(i==1)
{
maze[0][i]=0;
}
else maze[0][i]=1;
if(i==col)
{
maze[row+1][col]=0;
}
else maze[row+1][i]=1;
}
for(i=1;i<=row;i++)
{
for(j=1;j<=col;j++)
{
printf("请输入第%d行的第%d个数:\n",i,j);
scanf("%d",&maze[i][j]);
}
}
//输入下一个当前加边墙的迷宫，以验证输入是否正确
printf("输入完毕！当前加边墙的迷宫为：\n");
for(i=0;i<row+2;i++)
{
for(j=0;j<col+2;j++)
{
printf("%d",maze[i][j]);
}
printf("\n");
}
}
void ShowMaze()//输出迷宫
{
int i,j;
for(i=1;i<=row;i++)
{
for(j=1;j<=col;j++)
{
printf("%d",maze[i][j]);
}
printf("\n");
}
}
//释放迷宫数组
void DestroyMaze()
{
int i;
for(i=0;i<row+2;i++)
free(maze[i]);
free(maze);
}
//用DFS方法来实现回溯，找到迷宫的一条解路径
int FindPath()
{
int i,j,k,count,x,y,direction;
count=0;
x=1,y=1;
direction=0;
j=0,k=0;
for(i=0;i<N;i++)
{
stack[i]=0;
}
i=0;
while(1)
{
count=0;//用count判断是否有路可走
{
if(x==1&&y==1)
maze[x][y]=2;
if(maze[x][y+1]==0)//东
{
count++;
maze[x][y+1]=2;
y=y+1;
stack[i]=-1;
i++;
if(x==row&&y==col)
return 1;
}
else if(maze[x+1][y]==0)//南
{
if(maze[x+1][y]==0)
count++;
{
maze[x+1][y]=2;
x=x+1;
stack[i]=-2;
i++;
if(x==row&&y==col)
return 1;
}
}
else if(maze[x][y-1]==0)//西
{
count++;
if(maze[x][y-1]==0)
{
maze[x][y-1]=2;
y=y-1;
stack[i]=-3;
i++;
if(x==row&&y==col)
return 1;
}
}
else if(maze[x-1][y]==0)//北
{
count++;
if(maze[x-1][y]==0)
{
maze[x-1][y]=2;
x=x-1;
stack[i]=-4;
i++;
if(x==row&&y==col)
return 1;
}
}
}
if(count==0)
{
if(i<0)
return 0;
direction=stack[i--];
switch(direction)
{
case -1:y=y-1;break;
case -2:x=x-1;break;
case -3:y=y+1;break;
case -4:x=x+1;break;
default:break;
}
}
}
}
int main()
{
CreateMaze();
if(FindPath())
{
printf("已经找到了一条路径，如下:\n");
ShowMaze();
}
else
{
printf("没有合适的路径走出当前迷宫！\n");
}
DestroyMaze();
}
热心网友
时间：2023-10-10 02:33
#include
#include
#include
#define stack_init_size 200
#define stack_increment 10
#define OVERFLOW 0
#define OK 1
#define ERROE 0
#define TRUE 1
#define FALSE 0
typedef int Status;
typedef struct{
int x;
int y;
}PosType;
typedef struct {
int ord; // 通道块在路径上的"序号"
PosType seat; //通道块在迷宫中的"坐标位置"
int di; //从此通道块走向下一通道块的"方向"
}SElemType;
typedef struct{
SElemType *base;
SElemType *top;
int stacksize;
}SqStack;
int mg[20][20];
/*随机生成迷宫的函数
/*为了能够让尽量能通过，将能通过的块和不能通过的块数量比大致为2:1*/
void Random(){
int i,j,k;
srand(time(NULL));
mg[1][0]=mg[1][1]=mg[18][19]=0; //将入口、出口设置为"0"即可通过
for(j=0;j<20;j++)
mg[0][j]=mg[19][j]=1; /*设置迷宫外围"不可走"，保证只有一个出口和入口*/
for(i=2;i<19;i++)
mg[i][0]=mg[i-1][19]=1; /*设置迷宫外围"不可走"，保证只有一个出口和入口*/
for(i=1;i<19;i++)
for(j=1;j<19;j++){
k=rand()%3; //随机生成0、1、2三个数
if(k)
mg[i][j]=0;
else{
if((i==1&&j==1)||(i==18&&j==18)) /*因为距入口或出口一步的路是必经之路，故设该通道块为"0"加大迷宫能通行的概率*/
mg[i][j]=0;
else
mg[i][j]=1;
}
}
}
//构造一个空栈
Status InitStack(SqStack &s){
s.base =(SElemType *)malloc(stack_init_size * sizeof(SElemType));
if(!s.base) return OVERFLOW;
s.top=s.base;
s.stacksize=stack_init_size;
return OK;
}
//当前块可否通过
Status Pass(PosType e){
if (mg[e.x][e.y]==0) //0时可以通过
return OK; // 如果当前位置是可以通过，返回1
return OVERFLOW; // 其它情况返回0
}
//留下通过的足迹
Status FootPrint(PosType e){
mg[e.x][e.y]=7;
return OK;
}
//压入栈
Status Push(SqStack &s,SElemType e){
if(s.top-s.base>=s.stacksize){
s.base=(SElemType *)realloc(s.base,(s.stacksize+stack_increment) *sizeof(SElemType));
if(!s.base)exit(OVERFLOW);
s.top=s.base+s.stacksize;
s.stacksize+=stack_increment;
}
*s.top++=e;
return OK;
}
//出栈
Status Pop(SqStack &s,SElemType &e){
if(s.top==s.base)
return ERROE;
e=*--s.top;
return OK;
}
//下一步
PosType NextPos(PosType &e,int dir){
PosType E;
switch(dir){
case 1:E.x=e.x; //向下
E.y=e.y+1;
break;
case 2:E.x=e.x+1; //向右
E.y=e.y;
break;
case 3:E.x=e.x; //向上
E.y=e.y-1;
break;
case 4:E.x=e.x-1; //向左
E.y=e.y;
break;
}
return E;
}
//是否空栈
Status StackEmpty(SqStack s){
if (s.top==s.base)
return OK;
return OVERFLOW;
}
//留下不能通过的足迹
Status MarkPrint(PosType e){
mg[e.x][e.y]=3;
return OK;
}
//迷宫函数
// 若迷宫maze中从入口 start到出口 end的通道，则求得一条存放在栈中
// （从栈底到栈顶），并返回TRUE；否则返回FALSE
Status MazePath(int mg,PosType start,PosType end,SqStack &s){
PosType curpos;
InitStack(s);
SElemType e;
int curstep;
curpos=start; // 设定"当前位置"为"入口位置"
curstep=1; // 探索第一步
do{
if(Pass(curpos)){ // 当前位置可通过，即是未曾走到过的通道块
FootPrint(curpos); // 留下足迹
e.di =1;
e.ord = curstep;
e.seat= curpos;
Push(s,e); // 加入路径
if(curpos.x==end.x&&curpos.y==end.y){
printf("\n\n0∩_∩0 能到达终点!");
return TRUE;
}
curpos=NextPos(curpos,1); // 下一位置是当前位置的东邻
curstep++; // 探索下一步
}
else{ // 当前位置不能通过
if(!StackEmpty(s)){
Pop(s,e);
while(e.di==4&&!StackEmpty(s)){
MarkPrint(e.seat);
Pop(s,e);
}
if(e.di<4){
e.di++;
Push(s,e); // 留下不能通过的标记，并退回一步
curpos=NextPos(e.seat,e.di); /* 当前位置设为新方向的相邻块*/
}//if
}//if
}//else
}while(!StackEmpty(s));
printf("\n\n囧 ! 不能到达终点!");
return FALSE;
}
//打印迷宫
void PrintMaze(){
int i,j;
printf("运行路径:\n\n");
for(i=0;i<20;i++){
for(j=0;j<20;j++){
if(mg[i][j]==0)printf(" ");
else if(mg[i][j]==1) printf("■"); //迷宫的"墙"
else if(mg[i][j]==3) printf("◇"); //不通的路
else if(mg[i][j]==7)printf("○"); //通过的路径
}
printf("\n");
}
printf("\n");
}
void main(){
SqStack S;
PosType start,end;
start.x=1;start.y=0; //起点坐标
end.x=18;end.y=19; //终点坐标
printf("\n==================迷宫游戏==================");
printf("\n说明:■不能走的区域\t◇走不通的区域");
printf("\n '空格'代表未到过的区域");
printf("\n ○代表能通过的路径，指向终点");
printf("\n============================================");
Random();
printf("\n\nTest 1:");
MazePath(mg[20][20],start,end,S);
PrintMaze();
system("pause");
Random();
printf("\nTest 2:");
MazePath(mg[20][20],start,end,S);
PrintMaze();
system("pause");
Random();
printf("\nTest 3:");
MazePath(mg[20][20],start,end,S);
PrintMaze();
printf("\n==========程序退出，感谢使用!==========\n");
}
