迷宫走人是一个非常有趣的问题，某人在迷宫的某个点要通过一定的方式找到出口的位置，当然，这一切都得由程序来控制。
用栈来解决这个问题，是相当符合我们直观的思维的。如果用的是队列，则变成了广度优先，而且能找到最短的路径，但没有了我们这里的人在迷宫中“搜索”的意思。
在实现这个算法之前，需要一个二维整型数组来当地图（用1表示墙，用0表示路），还要有一个记录当前走过结点信息的结构体：
enum direction{UNSEARCHED,EAST,SOUTH,WEST,NORTH,SEARCHED};
struct searchNode
{
enum direction mDir;
int visited;
};
还有两个整型栈StackX及StackY来存放已访问过的结点的信息.
当然，还有一些辅助变量，如起点，终点等，不再赘述了。
算法的核心过程，我是这样想的：
while(!(curX==startX&&curY==startY&&!flag))
{ //终止条件为：如果回到的原来的起点且四个方向都找过了.从这里跳出的话，肯定是、寻找失败了.
flag=0;//标志本次寻找结果的布尔值.
如果当前四个方向未完全走完
{ 找到第一个可走的方向(不是墙且不没有被访问过)
{
push(curX,curY)
更新当前的curX,curY,
跳出:
}
}
如果curX==endX&&curY==enY则打印成功并跳出
如果flag==0
{
curX=pop(StackX);
curY=pop(StackY);
}
}
还算清楚吧~~~
当然，在最终实现时，除了算法的实现外，还需要考虑一些边界情况，如：出发点和终点在一起如何处理？打印出路径怎么做，当然啦，在主算法搞定的情况下，这些内容只不过算是最后完工前的调试工作罢了.
好了，下面就是我的实现代码了:
#include "ECStack.h"
#include "MazeQ.h"
#include "Global.h"
#include "Ulti.h"
#include "MyAssert.h"
#include <time.h>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
/*input file specification:*/
/*inputData.txt
startX,startY,endX,endY;//follow C Array law,start index is 0
mazeInfo.txt
rowNum,colNum.
a01,a02 ...
... ... ...
... ... ann
*/
char *inFileName="inputData.txt";
char *outFileName="outputData.txt";
#define DEBUG 1
void main(int argc,char* argv[])
{
FILE* inputFile;/*input file*/
FILE* outputFile;/*output file*/
// FILE* mazeFile;
double startTime,endTime,tweenTime;/*time callopsed info*/
//maze info.
int** mazeArr;
int rowNum,colNum;
//Ulti object
PSeqStack StackX,StackY;//StackDir;
//search wArr
struct searchNode** searchWArr;
//flags.
int flag;
//startNode,endNode,
int startX,startY,endX,endY;
int curX,curY;//curDir;
int tmpX,tmpY;
int** ansArr;
int i,j;/*iterator index*/
/*input file open*/
if(argc>1)strcpy(inFileName,argv[1]);
assertF((inputFile=fopen(inFileName,"rb"))!=NULL,"input file error");
printf("input file open success\n");
/*outpout file open*/
if(argc>2)strcpy(outFileName,argv[2]);
assertF((outputFile=fopen(outFileName,"wb"))!=NULL,"output file error");
printf("output file open success\n");
/*data input*/
read2DArrInt(&mazeArr,&rowNum,&colNum,"mazeInfo.txt");
fscanf(inputFile,"%d,%d,%d,%d;",&startX,&startY,&endX,&endY);
//mem apply
searchWArr=(struct searchNode**)malloc(sizeof(struct searchNode*)*rowNum);
for(i=0;i<rowNum;i++)
searchWArr[i]=(struct searchNode*)malloc(sizeof(struct searchNode)*colNum);
twoDArrMemApply(&ansArr,rowNum,colNum);
StackX=createNullSeqStack();
StackY=createNullSeqStack();
//StackDir=createNullSeqStack();
//data init
for(i=0;i<rowNum;i++)
for(j=0;j<colNum;j++)
{
searchWArr[i][j].mDir=UNSEARCHED;
searchWArr[i][j].visited=0;
ansArr[i][j]=-1;
}
#if DEBUG
printf("\n*******start of test program******\n");
printf("now is runnig,please wait...\n");
startTime=(double)clock()/(double)CLOCKS_PER_SEC;
/******************Core program code*************/
curX=startX,curY=startY;
flag=1;
if(curX==endX&&curY==endY)
{
seqPush(StackX,curX);
seqPush(StackY,curY);
}
else
{
while(!(curX==startX&&curY==startY&&!flag))
{
flag=0;
//if(!searchWArr[curX][curY]->visited)
//{
if(!searchWArr[curX][curY].visited)
searchWArr[curX][curY].visited=1;
while(searchWArr[curX][curY].mDir+1!=SEARCHED)
{
searchWArr[curX][curY].mDir++;//find next direction
//EAST,SOUTH,WEST,NORTH,SEARCHED
switch(searchWArr[curX][curY].mDir)
{
case EAST:tmpX=0;tmpY=1;printf("e\n");
break;
case SOUTH:tmpX=1;tmpY=0;printf("s\n");
break;
case WEST:tmpX=0;tmpY=-1;printf("w\n");
break;
case NORTH:tmpX=-1;tmpY=0;printf("n\n");
break;
default:
printf("error dir search\n");
}
if(mazeArr[curX+tmpX][curY+tmpY]==WALKABLE&&!searchWArr[curX+tmpX][curY+tmpY].visited)
{
printf("(%d,%d)\n",curX,curY);
seqPush(StackX,curX);
seqPush(StackY,curY);
// seqPush(StackDir,searchWArr[curX][curY]->mDir);
curX+=tmpX;
curY+=tmpY;
flag=1;
break;
}
}
//}
if(flag&&curX==endX&&curY==endY)
{
printf("target founded\n");
break;
}
if(flag==0&&!(curX==startX&&curY==startY))
{
curX=seqPop(StackX);
curY=seqPop(StackY);
//curDir=seqPop(StackDir);
}
}
}
if(flag)
{
while(!isNullSeqStack(StackX)&&!isNullSeqStack(StackY))
{
tmpX=seqPop(StackX);
tmpY=seqPop(StackY);
//fprintf(outputFile,"(%d,%d)->",tmpX,tmpY);
ansArr[tmpX][tmpY]=1;
}
fprintf(outputFile,"path founded:\r\n");
ansArr[endX][endY]=1;//because the target node was not push into the stacks.
for(i=0;i<rowNum;i++)
{
for(j=0;j<colNum;j++)
if(ansArr[i][j]==1)fprintf(outputFile,"o ");
else fprintf(outputFile,"* ");
fprintf(outputFile,"\r\n");
}
}
else
{
fprintf(outputFile,"no way lead to the target node\r\n");
}
/******************End of Core program**********/
endTime=(double)clock()/(double)CLOCKS_PER_SEC;
tweenTime=endTime-startTime;/*Get the time collapsed*/
/*Time collapsed output*/
printf("the collapsed time in this algorithm implement is:%f\n",tweenTime);
fprintf(outputFile,"the collapsed time in this algorithm implement is:%f\r\n",tweenTime);
printf("\n*******end of test program******\n");
#endif
twoDArrMemFree(&ansArr,rowNum);
printf("program end successfully,\n you have to preess any key to clean the buffer area to output,otherwise,you wiil not get the total answer.\n");
getchar();/*Screen Delay Control*/
return;
}
源码下载:
http://emilmatthew.51.net/downloads/walkInTheMazeC.rar
//如果上面这个链接无法响应下载（有可能是被网站给屏蔽掉了），则可使用下载工具（如迅雷等）下载。
欢迎提出批评与指正意见！
