//迷宮問題，暴力求解#include"stdio.h"#include"Stack.c"#define MAX_SIZE 100 //迷宮最大規格是100x100int MG[MAX_SIZE][MAX_SIZE] ;//1代表通，0代表不通typedef struct Mnode {int up ,down ,left , right ;int pass ;//是否經過}Mnode ;Status Search_Road ( Stack *s , int width , int height ,point start , point end);//尋找路徑函數，找到返回TRUEint main (){Stack s ;Stack out;int w,h ;int i , j;point start ;point end ;if( Init_Stack(&s)){printf("Input migong canshu :\n") ;scanf("%d %d" ,&w , &h) ;// printf("%d %d \n",w,h);printf("input road ,0 is not able,1 is not able \n");for ( i = 0 ; i < w ; i ++){for ( j = 0 ; j < h ; j++ ){scanf("%d", &MG[i][j]) ;}}start.x = 1 , start.y =1 ,end.x = w-2,end.y = h-2 ;if (Search_Road(&s,w,h,start,end)){Init_Stack(&out) ;point p;while (!IsEmpty(&s)){//point p;p = Pop(&s) ;Push(&out,p) ;}p = Pop(&out) ;printf("[%d , %d]",p.x,p.y);while (!IsEmpty(&out)){// point p ;p = Pop(&out) ;printf("--> [%d , %d]",p.x,p.y);}}else{printf("No Way !\n");}}}void Clear(Mnode *m){m->down = 0;m->left = 0;m->right = 0;m->up = 0;m->pass = 0 ;}Status Search_Road ( Stack *s , int width , int height ,point start , point end){int i = 0 , j = 0 ;point p = start ;Mnode m[MAX_SIZE][MAX_SIZE] ;//保存上一個位置的探索方向Clear(&m[p.x][p.y]);for ( i ; i <height ; i++)for ( j ; j <width ; j ++ ){Clear(&m[i][j]);}do {//printf(" To point %d %d \n", p.x,p.y);if (MG[p.x][p.y] == 1&& m[p.x][p.y].pass == 0 ){//如果此位置可以通過,并且沒有走過Push(s , p );//該位置進棧if ( p.x == end.x && p.y == end.y ){ //如果該點是終點，結束return TRUE ;}m[p.x][p.y].pass = 1 ;//切換當前位置的東鄰方塊為新的位置p.y ++ ;// Clear(&m[p.x][p.y-1]);m[p.x][p.y-1].right=1;}else{p = GetTop(s);if ( m[p.x][p.y].up !=1 ){//如果棧頂位置有其他位置沒有探索，順時針尋找棧頂位置的下一個相鄰塊if(m[p.x][p.y].left == 1 ){//printf("Up\n");if ( m[p.x-1][p.y].down == 1)//如果該位置的上面位置已經向下走過，則該位置不能向下走，即不能向后退{m[p.x][p.y].up = 1 ;}else{m[p.x][p.y].up = 1 ;p.x -- ;}}else if ( m[p.x][p.y].down == 1 ){// printf("left\n");if ( m[p.x][p.y-1].right == 1){m[p.x][p.y].left = 1 ;}else{m[p.x][p.y].left = 1 ;p.y -- ;}}else if ( m[p.x][p.y].right == 1 ){// printf("Down\n");if ( m[p.x+1][p.y].up == 1 ){m[p.x][p.y].down =1 ;}else {m[p.x][p.y].down =1 ;p.x ++ ;}}}else{//如果棧不空，但棧頂四周都不通p = GetTop(s);m[p.x][p.y].pass = 0 ;Pop(s) ;p = GetTop(s);}}}while ( ! IsEmpty(s) );//如果棧空，證明沒有路到終點return FALSE;}
利用棧的特性，進行求解迷宮從入口到出口的路徑

下為迷宮

求解思路如下

?

代碼如如上

其中棧的實現如下

#include"head.h"
#include<stdio.h>
#include<malloc.h>
#define elemtype point
#define INIT_STACK 100
#define INCREASEMENT_STACK 10
typedef struct point{
int x ;
?? int y ;
}point;
typedef struct Stack{
elemtype *base , *top ;//棧底和棧頂指針
int size_stack ;//棧大小
}Stack ;
Status Init_Stack (Stack *s);//初始化棧
Status IsEmpty (Stack *s);//判斷棧是否為空
Status Push (Stack *s, elemtype e);//進棧
elemtype GetTop (Stack *s );//得到棧頂元素
elemtype Pop(Stack *s );//出棧
Status Clear_Stack(Stack *s);//清空棧
Status Destroy_Stack (Stack *s);//銷毀棧
//int main (){
//
//??? Stack s ;
//??? int i ;
//??? Init_Stack (&s) ;
//??? if (IsEmpty(&s))
//??????? printf("empty\n") ;
//
//??? for ( i = 0; i < 110 ; i ++){
//
//??????? Push(&s , i) ;
//??? }
//??????? if (!IsEmpty(&s))
//??????? printf("! empty\n") ;
//???? printf ("%d" , Pop(&s) );
//
//???? Clear_Stack(&s) ;
//???? Destroy_Stack(&s) ;
//}
Status Init_Stack (Stack *s){
s->base = (elemtype *) malloc (INIT_STACK * sizeof(elemtype)); //分配空間
if (s->base == NULL) {
exit(-1) ;
?}
? s->top = s->base ;
? s->size_stack = INIT_STACK ;
}

Status IsEmpty (Stack *s){
if (s->base != NULL)
??? return (s->base == s->top) ;
??? else
??????? return ERROR ;
}
Status Push (Stack *s, elemtype e){
if (s->base == NULL)
??????? return ERROR ;
if ((s->top )- (s->base) >=( s->size_stack)){//如果棧滿
s->base = (elemtype *)realloc (s->base , ((s->size_stack)+INCREASEMENT_STACK)*sizeof(elemtype));
??????????????? s->top = s->base + s->size_stack ;
??????????????? s->size_stack += INCREASEMENT_STACK ;
}
????? *(s->top++) = e ;
???? // s->top++;
????? return OK;
}
elemtype GetTop (Stack *s ){
if ( !IsEmpty( s )){
return *(s->top-1) ;
??? }
??? printf("error : Stack Is Empty \n");
}
elemtype Pop(Stack *s ){
if (IsEmpty(s))
????? {
????????? printf ("Stack Is Empty !") ;
????? }
????? return *(--s->top);
}
Status Clear_Stack(Stack *s){
s->top = s->base ;
????? return OK;
}
Status Destroy_Stack (Stack *s){
free(s->base) ;
}

輸入測試用例如下

總結

以上是生活随笔為你收集整理的栈-迷宫求解路径问题的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。