資源簡介
迷宮問題是比較經典的算法設計題,改C程序較好的實現了迷宮問題。
代碼片段和文件信息
#include?
#include?
#include
#include
#define?M?120
#define?N?120
#define?MAXLEN?M*N
int?sxsyexey;
int?nm;
char?maze[M][N];
double?BeginTimeconsumeFinish;//時間消耗
?
?
typedef?struct//棧元素類型
{???int?xydir;
}elemtype;
typedef?struct//棧結構
{??elemtype?stack[MAXLEN];
???int?top;
}?sqstack;
?typedef?struct//隊列元素類型
{???int?xypre;
????
}QueueNode;
typedef?struct//隊列結構
{???QueueNode?queue[MAXLEN];
????int?front?rear;
}SqQueue;?
struct?moved//方向數組結構體類型
{???int?dxdy;
};
void?inimove(struct?moved?move[])//初始化方向數組
{????move[0].dx=0;move[0].dy=1;
?????move[1].dx=1;move[1].dy=0;
?????move[2].dx=0;move[2].dy=-1;
?move[3].dx=-1;move[3].dy=0;
}
void?inistack(sqstack?*s)//初始化棧
{????s->top=-1;
}
int?push(sqstack?*selemtype?x)//入棧操作
{???if(s->top==MAXLEN-1)
????????return?0;
????else
{????s->stack[++s->top]=x;
?????return?1;
}
}
elemtype?pop(sqstack?*s)//出棧操作
{elemtype?elem;
????if(s->top<0)
{???elem.x=NULL;
????????elem.y=NULL;
????elem.dir=NULL;
????return?elem;
}
????else?
{???s->top--;
????????return(s->stack[s->top+1]);
}
}
void?iniqueue(SqQueue?*s)
{????s->front=1;
?????s->rear=1;
}
int?shortpath(char?maze[][N]struct?moved?move[]SqQueue?*p)//尋找最段路徑?
{????int?ijxydir;
?????p->queue[1].x=sx;
?????p->queue[1].y=sy;
?p->queue[1].pre=0;
?maze[sx][sy]=-1;
?while(p->front<=p->rear)
?{????i=p->queue[p->front].x;//ij為出發點
??????j=p->queue[p->front].y;?
??????for(dir=0;dir<4;dir++)//尋找從ij出發四個方向有那些可以到達
??{????x=i+move[dir].dx;
???????y=j+move[dir].dy;
???????if(maze[x][y]==‘O‘)//?如有可到達點將此點入隊
???{???p->rear++;
???????p->queue[p->rear].x=x;
???p->queue[p->rear].y=y;
???p->queue[p->rear].pre=p->front;
???maze[x][y]=-1;
???}
???if((x==ex)&&(y==ey))//如到達出口返回真
??????return?1;
??}
??????p->front++;//對頭指針指向下一隊列元素
}
return?0;
}
void?printpath(SqQueue?*psqstack?*s)//將最短路徑入棧
{????int?if;
?????elemtype?elem;
?i=p->front;
?do//從隊列中取出最短迷宮路經放入棧中
?{???elem.x=p->queue[i].x;
?????????elem.y=p->queue[i].y;
?f=push(selem);
??if(f==0)
?????printf(“棧長度太短\n“);
??i=p->queue[i].pre;
??? ?
}while(i>0);//不變了
printf(“\n“);
}
void?draw(char?maze[][N]sqstack?*s)//將路徑從棧中彈出還原為原來的并以P代O
{????int?ij;
?????elemtype?elem;
?for(i=1;i<=M;i++)
??????for(j=1;j<=N;j++)
???if(maze[i][j]==-1)
?maze[i][j]=‘O‘;
?while(s->top>-1)
?{???elem=pop(s);
?????i=elem.x;
?j=elem.y;
?maze[i][j]=‘P‘;
??}?
maze[sx][sy]=‘S‘;
for(i=1;i<=m;i++)//輸出找到路徑后的迷宮
{for(j=1;j<=n;j++)
{printf(“%c“maze[i][j]);
????????}
????printf(“\n“);
}
}
int?main()
{
FILE?*fp;
char?filename[10];
int?ijf;
????sqstack?*s;
SqQueue?*p;
????printf(“Please?input?the?file?name:“);
scanf(“%s“filename);
fp=fopen(filename“r“);
if(fp==NULL)
??? { printf(“打開失敗“);
????exit(1);
}
fscanf(fp“%d“&m);
fscanf(fp“%d“
?屬性????????????大小?????日期????時間???名稱
-----------?---------??----------?-----??----
?????文件???????2608??2007-11-29?16:03??maze.txt
?????文件???????4293??2007-12-05?09:24??maze.cpp
?????文件?????217146??2007-11-29?16:05??maze.exe
-----------?---------??----------?-----??----
???????????????224047????????????????????3
- 上一篇:網上在線鮮花銷售系統論文
- 下一篇:購物網站開發 開題報告
評論
共有 條評論