【正文】 通路時沿原路返回 _x0001_ 7 百手起駕 整理為您 路徑信息入棧和出棧 當前位置 curpos 可通時 maze 數(shù)組中的對應(yīng)位置留下足跡，標記下一個探索方向，若棧 s 滿則追加棧空間，路徑信息入 e 棧 *=e， ++。若當前位置不可通且棧不為空則后退一步，路徑信息 e 出棧 e=* 并改變探索方向。程序的操作流程如圖 所示。 開始p ass ( maze ,curpos )f ootprint ( maze , curpos )Ye . pos = curpose . di = 1push ( s , e )pop ( s , e )s . top !=s . baseY結(jié)束N 圖 路徑信息入棧和出棧 _x0001_ 8 百手起駕 整理為您 當前探索位置的切換 利用二維數(shù)組來確定當前探索位置 curpos。方向變量 的數(shù)值為 1時，則橫坐標加 1； 的數(shù)值為 2 時，則縱坐標加 1； 3時，則橫坐標減 1； 的數(shù)值為 4時，則縱坐標減 1。程序的操作流程如圖 。 Switch( e . di )curpos . x ++curpos . y ++curpos . x curpos . y cas e 1 :cas e 2 :cas e 3 :cas e 4 :breakbreakbreakbreak開始結(jié)束 圖 當前探索位置的切換 _x0001_ 9 百手起駕 整理為您 最終探索路徑的輸出及標記 迷宮探索結(jié)束時若找不到出口則輸出尋找不到路徑。若成功找到出口則根據(jù)棧 s 儲存的路徑坐標信息 e在迷宮數(shù)據(jù) maze數(shù)組的相應(yīng)位置標記 2。程序的操作流程如圖 所示。 m azepath ( maze , start ,end , s , e )printf ( 尋找不到路徑 \ n )s . top != s . basepop ( s , e )maze [ e . pos . y ][ e .pos . x ]= 2Y結(jié)束YNprintf (% d % d , ,e . pos . y , e . pos . x )N開始 圖 最終探索路徑的輸出及標記 _x0001_ 10 百手起駕 整理為您 打印迷宮信息 根據(jù)棧 s 儲存的路徑坐標信息在迷宮數(shù)據(jù) maze[x][x]的不同輸出不同的符號，分別表示迷宮的障礙和走出迷宮的路徑。程序的操作流程如圖 所示。 char b = 1int i = 0 ， j = 0i hj lmaze [ i ][ j ]== 1 maze [ i ][ j ]== 2printf ( ■ )printf (% c , b )YYNYYp rintf( )Nj ++i ++p rintf ( \ n )N開始結(jié)束N 圖 打印迷宮信息 _x0001_ 11 百手起駕 整理為您 文件包含和結(jié)構(gòu)體的定義 include include include define STACK_INIT_SIZE 10 int h,l。//保存迷宮大小的行數(shù)和列數(shù) typedef struct{ int x。 int y。 }point。//定義坐標變量結(jié)構(gòu)體 typedef struct{ point pos。//保存當前路徑的坐標 int di。//保存下一個探索方向的標記值 }selemtype。//定義路徑信息結(jié)構(gòu) 體 typedef struct{ selemtype *base。//棧頂 selemtype *top。//棧底 int stacksize。//棧的容量 }sqstack。//棧的定義 point start,end。//迷宮出入口的聲明 棧的初始化及入棧出棧函數(shù) //棧的初始化 int initstack(sqstack amp。s){ //申請棧的空間 =(selemtype *)malloc(STACK_INIT_SIZE*sizeof(selemtype))。 if(!)//判斷棧是否申請成功 exit(2)。 =。//使棧為空 =STACK_INIT_SIZE。//給棧的容量賦值 return 1。 } //入棧函數(shù) int push(sqstack amp。s,selemtype e){ if(=)//判斷棧是否已滿 { =(selemtype *)realloc(,(+10)*sizeof(selemtype))。//棧滿時追加申請空間 _x0001_ 12 百手起駕 整理為您 if(!) exit(0)。 =+。 +=10。} *=e。//元素入棧 ++。 return 1。 } //出棧函數(shù) int pop(sqstack amp。s,selemtype amp。e){ //棧不為空時元素出棧 if(==)exit(0)。 e=*。 return 1。 } 申請迷宮大小及障礙的設(shè)置 //迷宮 大小初始化 int **initmaze() { int **maze。//指向二維數(shù)組的指針 printf(設(shè)置迷宮的行和列 (如 3 3))。 scanf(%d%d,amp。h,amp。l)。 //用 malloc 函數(shù)動態(tài)申請一個二維數(shù)組 maze=(int**)malloc(sizeof(int)*h)。 for(int i=0。ih。i++) maze[i]=(int*)malloc(sizeof(int)*l)。 return maze。 } //迷宮障礙設(shè)置函數(shù) void setza(int **maze) { char n,m。 int x,y。 printf(設(shè)置入口的坐標 (如 1 1))。 scanf(%d%d,amp。y,amp。x)。//設(shè)置入口坐標 while(!((y==h||y==1||x==l||x==1)amp。amp。(x=lamp。amp。y=h)amp。amp。(x!=0amp。amp。y!=0))){ printf(請把入口設(shè)置在迷宮的邊緣 \n)。 scanf(%d%d,amp。y,amp。x)。//設(shè)置入口坐標 } =x1。=y1。 printf(設(shè)置出口的坐標 (如 2 3))。 scanf(%d%d,amp。y,amp。x)。//設(shè)置出口坐標 _x0001_ 13 百手起駕 整理為您 while(!((y==h||y==1||x==l||x==1)amp。amp。(x=lamp。amp。y=h)amp。amp。(x!=0amp。amp。y!=0)amp。amp。!(y==+1amp。amp。x==+1))){ printf(請把出口設(shè)置在迷宮的邊緣 ,不要與入口重合 \n)。 scanf(%d%d,amp。y,amp。x)。//設(shè)置出口坐標 } =x1。=y1。 printf(設(shè)置障礙的坐標 \n)。 scanf(%d%d,amp。n,amp。m)。//設(shè)置障礙坐標 //當輸入 時結(jié)束障礙設(shè)置 while(!(n==0amp。amp。m==0)){ maze[n1][m1]=1。 scanf(%d%d,amp。n,amp。m)。 } } 通道可通性測試 //當前位置可通性測試 int pass(int **maze,point curpos) { //根據(jù) maze 二維數(shù)組儲存的數(shù)值判斷當前位置是否可通 if(maze[][]!=1amp。amp。maze[][]!=8){ return (true)。 } else return(false)。 } 為走過的通道留下足跡 //留下足跡 void footprint(int **maze,point curpos) { maze[][]=8。 } 探索位置的切換 //當前探索位置到下一個探索位置坐標的切換 point nextpos(point curpos,int a) { switch(a){ case 1://向右移動 if(l1)++。 break。 _x0001_ 14 百手起駕 整理為您 case 2://向下移動 if(h1)++。 break。 case 3://向左移動 if(0)。 break。 case 4://向上移動 if(0)。 break。 } return curpos。 } 入口到出口的路徑探索 //路徑探索函數(shù) int mazepath(int **maze,point start,point end,sqstack amp。s,selemtype e) { initstack(s)。//棧的初始化為路徑信息入棧做準備 point curpos=start。//把迷宮入口作為探索的起始位置 do{ if(pass(maze,curpos)){ footprint(maze,curpos)。//若當前位置可通，則留下足跡 =curpos。//把當前位置的坐標賦值給路徑信息元素 =1。//標記下一個探索位置 的方向 push(s,e)。//當前路徑信息入棧 //若當前位置為迷宮出口則返回 true 結(jié)束探索 if(==amp。amp。==) return (true)。 curpos=nextpos(curpos,)。//切換當前位置繼續(xù)判斷可通性 } else{//當前位置不可通 if(!=){//棧不為空 pop(s,e)。//路徑信息出棧 while(==4amp。amp。!=){ //退回一步后，檢查一下個探索位置的方向標記值 //若 =4 且棧不為空，則將路徑信息元素不斷出棧， //直到 4 為止 pop(s,e)。 } _x0001_ 15 百手起駕 整理為您 if(4){//若當前位置標記的下一個探索方向的值小于 4 ++。// push(s,e)。//改變下一個探索方向后將元素信息再次入棧 curpos=nextpos( ,)。//切換當前位置繼續(xù)判斷可通性 } } } }while(!=)。//若棧不為空則繼續(xù)執(zhí)行路徑探索循環(huán) return (false)。//尋找不到路徑返回 false } 打印迷宮信息 //打印迷宮信息 void printmaze(int **maze) { int k。 char b=1。//把迷宮障礙和最終路徑分別標記為 a 和 b 兩種字符 //逐行輸出迷宮信息 for(k=0。kl+2。k++){ if((==0amp。amp。+1==k)||(==0amp。amp。+1==k)) printf( )。 else printf(█)。 } printf(\n)。 for(int i=0。ih。i++){ if((==0amp。amp。==iamp。amp。!=0amp。amp。!=h1)||(==0amp。amp。==iamp。a