SunshineNBB 2015-12-29 06:09 采纳率: 0%
浏览 4775

C:用递归及非递归解决迷宫问题

以下是现有的代码,但是递归放在里面出现错误,求大神给我改改。
#include
#include
#define N 39
#define M 39
int X;

int maze[N+2][M+2];
/******递归函数定义*******/
typedef struct {
int x,y;
}Dj;
Dj move[4];

/******非递归函数定义*******/
struct point{

int row,col,predecessor;
}queue[512];
int head=0,tail=0;

/******* 手动生成迷宫函数**********/
void shoudong_maze(int m,int n)
{
int i,j;
printf("\n\n");
printf("请按行输入迷宫(0表示通路,1表示障碍,不包括墙,中间用空格隔开):\n\n");
for(i=0;i<m+2;i++)
for(j=0;j<n+2;j++)

scanf("%d",&maze[i][j]);
}

/******* 自动生成迷宫函数**********/
void zidong_maze(int m,int n)
{
int i,j;
printf("\n迷宫正在生成,请稍后。\n\n");
system("pause");
for(i=1;i<m+1;i++)
for(j=1;j<n+1;j++)
maze[i][j]=rand()%2;
//由于rand()产生的随机数是从0到RAND_MAX(最大)
//RAND_MAX是定义在stdlib.h中的,其值至少为32767)
//要产生从X到Y的数,只需要这样写:k=rand()%(Y-X+1)+X;
for(i=0;i<m+2;i++)
{
maze[0][i]=1;
maze[m+1][i]=1;
}
for(j=0;j<n+2;j++)
{
maze[j][0]=1;
maze[j][n+1]=1;
}
}

/********将迷宫打印成图形*********/
void print_maze(int m,int n)
{

int i,j;
printf("\n迷宫生成结果如下:\n\n");
printf("迷宫入口(1,1)\n");
printf(" ↓");
for(i=0;i<m+2;i++)
{

printf("\n");
for(j=0;j<n+2;j++)
{

if(maze[i][j]==0)
printf("□");
if(maze[i][j]==1)
printf("■");
}
}

printf("→\n");
printf("迷宫出口:(%d,%d)\n",m+1,n+1);
}

/**********打印迷宫路径 (若存在路径)***********/

void result_maze(int m,int n)
{

int i,j;

printf("迷宫通路(用☆表示)如下所示:\n\t");

for(i=0;i<m+2;i++)
{

printf("\n");

for(j=0;j<n+2;j++)
{

if(maze[i][j]==0||maze[i][j]==2)
printf("□");

if(maze[i][j]==1)
printf("■");

if(maze[i][j]==3)
printf("☆");

}

}

}

/*******入队*********/
void enqueue(struct point p)
{

queue[tail]=p;

tail++;
}

/*******出队*********/
struct point dequeue()
{

head++;

return queue[head-1];
}

/*******判断队列是否为空*******/
int is_empty()
{

return head==tail;

}

/*******访问节点*******/
void visit(int row,int col,int maze[41][41])
{

struct point visit_point={row,col,head-1};
maze[row][col]=2;

enqueue(visit_point);

}

/*******探索迷宫路径*******/

int mgpath(int maze[41][41],int m,int n)
{

int X=1;

struct point p={1,1,-1};

if(maze[p.row][p.col]==1)
{

printf("\n===============================================\n");

printf("此迷宫无解\n\n");
X=0;
return 0;
}

maze[p.row][p.col]=2;

enqueue(p);

while(!is_empty())
{

p=dequeue();

if((p.row==m)&&(p.col==n))
break;

if((p.col+1 visit(p.row,p.col+1,maze);
if((p.row+1 visit(p.row+1,p.col,maze);
if((p.col-1>=0)&&(maze[p.row][p.col-1]==0)) //左边界
visit(p.row,p.col-1,maze);

if((p.row>=0)&&(maze[p.row-1][p.col]==0)) //上边界
visit(p.row-1,p.col,maze);

}

if(p.row==m-1&&p.col==n-1)
{

printf("\n==================================================================\n");

printf("迷宫路径为:\n");
printf("(%d,%d)\n",p.row,p.col);

maze[p.row][p.col]=3;

while(p.predecessor!=-1)
{

p=queue[p.predecessor];

printf("(%d,%d)\n",p.row,p.col);

maze[p.row][p.col]=3;

}

}

else
{

printf("\n=============================================================\n");

printf("此迷宫无解!\n\n");
X=0;
}

return 0;

}

/******递归函数*******/
int path(int maze[][N+2],Dj move[],int x,int y,int step)
{
int i;
step++;
maze[x][y]=step;
step++;
maze[x][y]=step;
if(x==M&&y==N)
return 1;
for(i=0;i<4;i++)
{
if(maze[x+move[i].x][y+move[i].y]==0)
if(path(maze,move,x+move[i].x,y+move[i].y,step))
return 1;
}
step--;
maze[x][y]=0;
return 0;
}

/********主函数********/
void main(void)

{

Dj move[4];
int maze[N+2][M+2];
int i,h,m,n,cycle=0;

while(cycle!=(-1))
{

printf("********************************************************************************\n");

printf(" 欢迎进入迷宫求解系统\n");

printf("********************************************************************************\n");

printf(" →_→ 手动生成迷宫 请按:1\n");

printf(" →_→ 自动生成迷宫 请按:2\n");

printf(" →_→ 退出 请按:3\n\n");

printf("********************************************************************************\n");
printf("\n");

printf("请选择你的操作:\n");

scanf("%d",&i);

switch(i)
{

case 1:/*printf("\n请输入行数:");

scanf("%d",&m);

printf("\n");

printf("请输入列数:");
scanf("%d",&n);

while((m<=0||m>39)||(n<=0||n>39))
{

printf("\n抱歉,你输入的行列数超出预设范围(0-39,0-39),请重新输入:\n\n");

printf("请输入行数:");
scanf("%d",&m);

printf("\n");

printf("请输入列数:");
scanf("%d",&n);
} /
printf("
*******************************************************************************\n");

printf(" →_→ 递归算法 请按:1\n");

printf(" →_→ 非递归算法 请按:2\n");

printf(" →_→ 退出 请按:3\n\n");

printf("********************************************************************************\n");
printf("\n");

printf("请选择你的操作:\n");

scanf("%d",&h);
if(h==1)
{
printf("\n请输入行数:");

scanf("%d",&m);

printf("\n");

printf("请输入列数:");
scanf("%d",&n);

while((m<=0||m>39)||(n<=0||n>39))
{

printf("\n抱歉,你输入的行列数超出预设范围(0-39,0-39),请重新输入:\n\n");

printf("请输入行数:");
scanf("%d",&m);

printf("\n");

printf("请输入列数:");
scanf("%d",&n);
}
path(maze,move,0,0,0);
shoudong_maze(m,n);

print_maze(m,n);

mgpath(maze,m,n);

if(X!=0)
result_maze(m,n);

printf("\n\nPress Enter Contiue!\n");

getchar();

while(getchar()!='\n');break;
}
else
{
shoudong_maze(m,n);

print_maze(m,n);

mgpath(maze,m,n);

if(X!=0)
result_maze(m,n);

printf("\n\nPress Enter Contiue!\n");

getchar();

while(getchar()!='\n');break;
}

    case 2:printf("\n请输入行数:");      
        scanf("%d",&m);     
        printf("\n");      
        printf("请输入列数:");     
        scanf("%d",&n);      
        while((m<=0||m>39)||(n<=0||n>39))
        {      
            printf("\n抱歉,你输入的行列数超出预设范围(0-39,0-39),请重新输入:\n\n");       
            printf("请输入行数:");      
            scanf("%d",&m);      
            printf("\n");       
            printf("请输入列数:");           
            scanf("%d",&n);
        }
        zidong_maze(m,n);     
        print_maze(m,n);     
        mgpath(maze,m,n);     
        if(X!=0) 
            result_maze(m,n);     
        printf("\n\nPress Enter Contiue!\n");     
        getchar();      
        while(getchar()!='\n');      
        break;     
    case 3:cycle=(-1);
        break;     
    default:printf("\n");
        printf("你的输入有误!\n");     
        printf("\nPress Enter Contiue!\n");     
        getchar();      
        while(getchar()!='\n');     
        break; 
} 

}

}

  • 写回答

2条回答 默认 最新

  • threenewbee 2016-01-23 20:46
    关注
    评论

报告相同问题?

悬赏问题

  • ¥15 数据库数据成问号了,前台查询正常,数据库查询是?号
  • ¥15 算法使用了tf-idf,用手肘图确定k值确定不了,第四轮廓系数又太小才有0.006088746097507285,如何解决?(相关搜索:数据处理)
  • ¥15 彩灯控制电路,会的加我QQ1482956179
  • ¥200 相机拍直接转存到电脑上 立拍立穿无线局域网传
  • ¥15 (关键词-电路设计)
  • ¥15 如何解决MIPS计算是否溢出
  • ¥15 vue中我代理了iframe,iframe却走的是路由,没有显示该显示的网站,这个该如何处理
  • ¥15 操作系统相关算法中while();的含义
  • ¥15 CNVcaller安装后无法找到文件
  • ¥15 visual studio2022中文乱码无法解决