迷宫栈和队列.doc

问题三： 迷宫 ：栈 插入、删除都在一边。 #includeiostream using namespace std; #define N 10 // #define M 10 //迷宫的大小 10 10的 #define maxsize 100 int mg[M][N]= { {1,1,1,1,1,1,1,1,1,1}, {1,0,0,1,0,0,0,1,0,1}, {1,0,0,1,0,0,0,1,0,1}, {1,0,0,0,0,1,1,0,0,1}, {1,0,1,1,1,0,0,0,0,1}, {1,0,0,0,1,0,0,0,0,1}, {1,0,1,0,0,0,1,0,0,1}, {1,0,1,1,1,0,1,1,0,1}, {1,1,0,0,0,0,0,0,0,1}, {1,1,1,1,1,1,1,1,1,1} }; //初始化一下 struct node { int i; int j; int nextv; }stk[maxsize]; int top=-1; //定义一个栈顶 元素 void mgpath(int x0,int y0,int xn,int yn) { int i,j,k,n_val,find; int cesi=0; top++; //初始化 stk[top].i =x0; stk[top].j =y0; stk[top].nextv =-1; mg[1][1]=-1; // while(top-1) { i=stk[top].i; j=stk[top].j; n_val=stk[top].nextv ; //再次退回时，从它的方向开始就行了，以前的不重复。 if(i==xnj==yn) { //到了出口 ，显示 cout迷宫路径 显示如下：endl; for(k=0;k=top;k++) { cout(stk[k].i ,stk[k].j) ---- \t; if((k+1)%4==0) coutendl; } coutendl; break;//为什么不加 会运行 好多次？？ } find=0; while(n_val8find==0) { n_val++; //从0开始 switch(n_val) { case 0: i=stk[top].i-1;j=stk[top].j-1;break; //8个方向 case 1: i=stk[top].i-1;j=stk[top].j;break; case 2: i=stk[top].i-1;j=stk[top].j+1;break; case 3: i=stk[top].i;j=stk[top].j-1;break; case 4: i=stk[top].i;j=stk[top].j+1;break; case 5: i=stk[top].i+1;j=stk[top].j-1;break; case 6: i=stk[top].i+1;j=stk[top].j;break; case 7: i=stk[top].i+1;j=stk[top].j+1;break; } if(mg[i][j]==0) find=1; //有空的 可以找到相邻的点 } if(find==1) { stk[top].nextv =n_val;//找到一个 ，并将其 值 赋值好！ top++;// 进栈 stk[top].i =i;stk[top].j =j;stk[top].nextv =-1; mg[i][j]=-1; } else //没有 回溯。 { mg[stk[top].i ][stk[top].j ]=0; top--; } } } void main() { mgpath(1,1,8,8); } 第二种： 队列 : 所有插入操作都只能在表的一边，而删除则在另一边。 #includeiostream using namespace std; #define N 10 #define M 10 #define maxsize 300 int mg[M][N]= { {1,1,1,1,1,1,1,1,1,1}, {1,0,0,1,0,0,0,1,0,1}, {1,0,0,1,0,0,0,1,0,1}, {1,0,0,0,0,1,1,0,0,1}