减小字体
增大字体- ·上一篇文章：中国2006年度安全报告 新病毒数暴增黑客团伙猖獗
- ·下一篇文章：用c做的简单的坦克大战小游戏
利用栈实现迷宫的求解
求解思想：回溯法是一种不断试探且及时纠正错误的搜索方法。下面的求解过程采用回溯法。从入口出发，按某一方向向前探索，若能走通（未走过的），即某处可以到达，则到达新点，否则试探下一方向 ; 若所有的方向均没有通路，则沿原路返回前一点，换下一个方向再继续试探，直到所有可能的通路都探索到，或找到一条通路，或无路可走又返回到入口点。 在求解过程中，为了保证在到达某一点后不能向前继续行走（无路）时，能正确返回前一点以便继续从下一个方向向前试探，则需要用一个栈保存所能够到达的每一点的下标及从该点前进的方向。 |
参考答案
#include<stdio.h>
#include<graphics.h>
struct data{
int x,y,d;
};
typedef struct data *pdata;
typedef struct data datatype;
struct seqstack{
int maxnum;
int t;
struct data *s;
};
typedef struct seqstack *pseqstack;
pseqstack createemptystack_seq(int m){
pseqstack pastack;pastack=NULL;
pastack->s=(pdata)malloc(sizeof(struct data)*m);
pastack->maxnum=m;
pastack->t=-1;
return pastack;
}
int isemptystack_seq(pseqstack pastack){
if(pastack->t==-1) return 1;
else return 0;
}
void push_seq(pseqstack pastack,datatype x){
if(pastack->t>=pastack->maxnum-1) printf("overflow!\n");
else {pastack->t=pastack->t+1;
pastack->s[pastack->t]=x;
}
}
void pop_seq(pseqstack pastack){
if(pastack->t==-1) printf("underflow!\n");
else pastack->t=pastack->t-1;
}
datatype top_seq(pseqstack pastack){
if(pastack->t==-1) printf("it is empty!\n");
else return(pastack->s[pastack->t]);
}
void drawretangle(int x,int y,int color){
int i,j;
for(i=0;i<20;i++){
for(j=0;j<20;j++){
putpixel(x+i,y+j,color);
}
}
}
int main(){
int maze[15][15]={
1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,
0,0,0,0,0,0,0,0,0,1,1,1,1,1,1,
1,0,0,1,1,1,1,1,0,0,0,0,0,0,1,
1,1,0,0,0,0,0,0,0,0,0,1,1,0,1,
1,1,0,1,1,1,0,0,1,1,0,1,1,0,1,
1,1,0,1,0,1,1,0,1,1,0,0,0,0,1,
1,1,0,1,0,0,0,0,1,1,0,1,0,0,1,
1,1,0,1,0,0,1,0,0,0,0,1,0,0,1,
1,0,0,0,0,1,0,0,0,0,0,0,0,0,1,
1,0,1,0,0,1,0,1,1,0,1,0,1,0,1,
0,0,1,0,0,0,0,0,0,0,1,0,0,0,1,
1,0,0,0,0,0,0,1,1,0,1,0,0,0,1,
1,0,1,0,0,1,0,0,0,0,0,1,0,0,1,
1,0,1,0,0,0,0,0,1,0,0,0,0,0,1,
1,1,1,1,1,1,1,1,1,1,1,1,1,1,1
};
int i,j,color,gm=DETECT,gd;
int direction[4][2]={0,1,1,0,0,-1,-1,0};
int x1=1,y1=0,x2=10,y2=0,m=15,n=15,k,g,h;
pseqstack st;
datatype element;
st=createemptystack_seq(m*n);
maze[x1][y1]=2;
element.x=x1;
element.y=y1;
element.d=-1;
push_seq(st,element);
initgraph(&gm,&gd,"");
setbkcolor(1);
for(i=0;i<15;i++){
for(j=0;j<15;j++){
if(maze[i][j]==1)
drawretangle(100+i*20,100+j*20,3);
else
drawretangle(100+i*20,100+j*20,7);
}
}
for(i=0;i<16;i++){setcolor(i);line(400,50+i*10,470,50+i*10);}
drawretangle(100+element.x*20,100+element.y*20,6);getch();delay(60000);
while(!isemptystack_seq(st)){
element=top_seq(st);
pop_seq(st);
i=element.x;
j=element.y;
k=element.d+1;
while(k<=3){
g=i+direction[k][0];
h=j+direction[k][1];
if(g==x2&&h==y2&&maze[g][h]==0){
drawretangle(100+g*20,100+h*20,6);delay(60000);delay(60000);
element.x=i;
element.y=j;
push_seq(st,element);
element.x=g;
element.y=h;
push_seq(st,element);
while(!isemptystack_seq(st)){
element=top_seq(st);
drawretangle(100+element.x*20,100+element.y*20,15);
delay(60000);delay(60000);
pop_seq(st);
}
getch();closegraph();
}
if(maze[g][h]==0){
maze[g][h]=2;
element.x=i;
element.y=j;
element.d=k;
push_seq(st,element);
i=g;
j=h;
drawretangle(100+i*20,100+j*20,6);delay(60000);delay(60000);
k=-1;
}
k++;
}
drawretangle(100+i*20,100+j*20,7);delay(60000);delay(60000);
}
getch();
closegraph();
return 0;
}
