迷宫问题(程序源码)
//实习2.9
//迷宫
//Visual C++6.0 调试通过
#include<stdio.h>
#include<stdlib.h>
#define CAN 0 ///迷宫通路
#define WALL 1 ///迷宫障碍
#define PATH 2 ///迷宫路径
#define EVER 3 ///曾经走过但事实上是不行的
#define Fail 0
#define Succ 1
#define M 80 ///迷宫的最大行数
#define N 80 ///迷宫的最大列数
typedef int Status;
Status ReadData(fname,pmaze,arg) //从文件中读取数据
char *fname;
int *pmaze;
int arg[];
{
FILE *fp;
int i,j;
fp=fopen(fname,"r");
if(!fp) return Fail;
fscanf(fp,"%d %d",&arg[0],&arg[1]);
for(i=0;i<arg[0];i++)
for(j=0;j<arg[1];j++)
fscanf(fp,"%d",pmaze+arg[1]*i+j);
return Succ;
}//ReadData
Status SetMaze(arg) //设置迷宫参数
int arg[];
{ printf("BEGIN (row<=%d,col<=%d):",arg[0],arg[1]);
scanf("%d,%d",&arg[2],&arg[3]);
arg[2]--;arg[3]--;
printf("END: (row<=%d,col<=%d):",arg[0],arg[1]);
scanf("%d,%d",&arg[4],&arg[5]);
arg[4]--;arg[5]--;
return Succ;
}//SetMaze
Status OutputMaze(pmaze,arg) //向屏幕输出迷宫数据
int *pmaze;
int arg[];
{ int i,j;
for(i=0;i<arg[0];i++)
{for(j=0;j<arg[1];j++)
switch(*(pmaze+arg[1]*i+j))
{
case CAN: printf("%2c",'+');break;
case WALL:printf("%2c",'#');break;
case PATH:printf("%2c",'*');break;
case EVER:printf("%2c",'@');break;
}//switch
printf("\n");
}
return Succ;
}//OutputMaze
Status Solution(pmaze,arg) //解决问题的函数
int *pmaze;
int arg[];
{
int *sR,*sC,top;//顺序表示的栈，top是两个栈的顶，*(sX+top)是最后一个入栈的元素
int r,c;
sR=(int *)malloc(arg[0]*arg[1]*sizeof(int));
sC=(int *)malloc(arg[0]*arg[1]*sizeof(int));
top=0;//当top==0时表示是空的
r=arg[2];c=arg[3];
while(r!=arg[4] || c!=arg[5])
{ //T
*(pmaze+arg[1]*r+c)=PATH;
top++; ///1推入栈
*(sR+top)=r; ///2
*(sC+top)=c; ///3
if(top!=0 && c<arg[1]-1 && *(pmaze+arg[1]*r+c+1)==CAN) c=c+1;
else if(top!=0 && r<arg[0]-1 && *(pmaze+arg[1]*(r+1)+c)==CAN) r=r+1;
else if(top!=0 && c>0 && *(pmaze+arg[1]*r+c-1)==CAN) c=c-1;
else if(top!=0 && r>0 && *(pmaze+arg[1]*(r-1)+c)==CAN) r=r-1;
else //此点是死胡同
{*(pmaze+arg[1]*r+c)=EVER;
top--; ///1 找到路径的上一点
r=*(sR+top); ///2
c=*(sC+top); ///3
top--; ///1否则找到的点在while循环的下
///2一次执行时回再次推入栈
if(top==-1) break;//说明没有合适的路径
}
}//while
if(r==arg[4] && c==arg[5])
{*(pmaze+arg[1]*r+c)=PATH;return Succ;}
else
{return Fail;}
}//Solution
main(argc,argv)
int argc;
char *argv[];
{ char *fname; ///数据文件名
int maze[M][N]; ///迷宫表示
int arg[6]; ///如下边表格所示的内容，是参数的集合
Status res; ///解决问题成功与否的标志
// arg[0] | arg[1] | arg[2] | arg[3] | arg[4] | arg[5]
// --------+--------+--------+--------+--------+-------
// rows | cols | r_begin| c_begin| r_end | c_end
printf("----+---+---+----MAZE SOLUTION----+---+---+----\n");
printf("===============================================\n");
printf(" + ---> This point has never been visited. \n");
printf(" # ---> This point is a wall-point. \n");
printf(" * ---> This point has ever been visited, \n");
printf(" but it is not a path-point. \n");
printf(" @ ---> This point is a path-point. \n");
printf("===============================================\n");
fname=(char *)malloc(20*sizeof(char));
//根据命令行参数读取文件名::开始
if(argc==1)
{printf("FILENAME(Lenth<=20): ");
scanf(" %s",fname);
}
else
fname=argv[1];
//根据命令行参数读取文件::结束
printf("===============================================\n");
//读取文件中的数据建立迷宫::开始
ReadData(fname,maze,arg);
OutputMaze(maze,arg);
//读取文件中的数据建立迷宫::结束
printf("===============================================\n");
//设置迷宫的出入口::开始
arg[2]=arg[3]=arg[4]=arg[5]=-1;
if(argc>=3)
{arg[2]=0;
arg[3]=0;
arg[4]=arg[0];
arg[5]=arg[1];
printf("BEGIN (row,col):");
printf("END: (row,col):");
arg[4]--;arg[5]--;
}
else
SetMaze(arg);
////以下四行为容错功能代码
if(arg[2]==-1) arg[2]=0;
if(arg[3]==-1) arg[3]=0;
if(arg[4]==-1) arg[4]=arg[0];
if(arg[5]==-1) arg[5]=arg[1];
//设置迷宫的出入口::结束
printf("===============================================\n");
//调用Solution解决问题::开始
res=Solution(maze,arg);
OutputMaze(maze,arg);
//调用Solution解决问题::结束
printf("===============================================\n");
//显示解决问题的结果::开始
if(res==Succ)
printf("Solve Successfully!\n");
else
printf("No Solution\n");
//显示解决问题的结果::结束
printf("----+---+----MAZE SOLUTION----+---+----\n");
}//main
作者会员名：xiezi