棧的簡單應用-迷宮問題_ZenDei技術網路在線

迷宮問題迷宮問題一直是電腦工作者感興趣的問題，因為它可以展現棧的巧妙應用，這裡將利用棧開發一個走迷宮程式，雖然在發現正確路徑前，程式要嘗試許多錯誤路徑，但是，一旦發現，就能夠重新走出迷宮，而不會再去嘗試任何錯誤路徑。迷宮問題求解電腦中可以用如圖所示的方塊圖表示迷宮。圖中空白方塊為通道， ...

　迷宮問題

　　迷宮問題一直是電腦工作者感興趣的問題，因為它可以展現棧的巧妙應用，

這裡將利用棧開發一個走迷宮程式，雖然在發現正確路徑前，程式要嘗試許多

錯誤路徑，但是，一旦發現，就能夠重新走出迷宮，而不會再去嘗試任何錯誤路徑。

迷宮問題求解

電腦中可以用如圖所示的方塊圖表示迷宮。圖中空白方塊為通道，藍色方塊為牆

迷宮的儲存可以使用二維數組，其中“0”代表牆值，“1”代表通路。由於迷宮被表示為

二維數組，所以，在任何時刻，迷宮中的位置都可以用行，列坐標來描述。

在迷宮中的某一個位置進行移動的可能方向如圖所示

值得註意的是，並不是每一個位置都有四個鄰居。如果[row][col]在邊界上那麼鄰居的

個數就少於4個，甚至只有2個。為了避免邊界條件的檢查，在迷宮周圍加上一圈邊界。這樣，

一個m*n的迷宮就需要一個(m+2)*(n+2)的數組。入口位置在[1][1],而出口位置在[m][n]。

另一個簡化問題的策略是，用數值direc 預先定義出“可能的移動方向”數字0-3表示4個

可能的移動方向，對每個方向都指出其垂直和水平的偏移量。

　　求迷宮中一條徑的演算法的基本思想是：

若當前位置“可通“，則納入”當前路徑”，並繼續朝“下一個位置探索”，即切換“下一位置”為

“當前位置”，如此反覆直到出口；

若當前位置“不可通”則應順著“來向”退回到“前一通道塊”，然後朝著除“來向”之外的其他方向繼續探索；

若該通道塊的四周4個方塊均“不可通”，則應從“當前路徑”上刪除該通道塊。假設以棧

S記錄“當前路徑”，則棧頂中存放的是“當前路徑上最後一個通道塊”。由此，

“納入路徑”的操作即為“當前位置壓入”，“從當前路徑上刪除前一塊通道塊”的操作即為“彈出”。

需要說明的是，所謂的當前位置可通，指的是未曾走到過的通道塊，即要求該方塊位置S記錄“當前路徑”，

則棧頂中存放的是“當前路徑上最後一個通道塊”。由此，“納入路徑”的操作即為“當前位置壓入”，

“從當前路徑上刪除前一塊通道塊”的操作即為“彈出”。不僅是通道塊，而且不在當前路徑上(否則路徑不是簡單路徑)，

也不是曾經納入過路徑的通道塊(否則只能在死衚衕內轉圈)。

　sqstack.h

 1 #pragma once
 2 #include <stdio.h>
 3 #include <stdlib.h>
 4 #define STACK_INIT_SIZE 100//儲存空間初始分配量
 5 #define STACKINCREMENT  10//存儲空間分配增量
 6 #define OK 1
 7 #define ERROR 0
 8 typedef struct {
 9     int x;  //行值
10     int y;  //列值
11 }PosType;  //迷宮坐標位置類型
12 typedef struct 
13 {
14     int ord;      //序號
15     int di;       //方向
16     PosType seat; //位置  
17 
18 } StackType; //棧元素類型
19 
20 typedef struct {
21     StackType *base;   //在構造之前和銷毀之後，base的值為NULL
22     StackType *top;    //棧頂指針
23     int stacksize;     //當前已分配的存儲空間，以元素為單位
24     
25 }SqStack; //順序棧
26 
27 //棧的初始化
28 int InitStack(SqStack *p) {
29 
30 
31     p->base = (StackType*)malloc(STACK_INIT_SIZE * sizeof(StackType));
32     if (p->base == NULL)  return ERROR;  //記憶體分配失敗
33     p->top = p->base;     //棧頂與棧底相同表示一個空棧
34     p->stacksize = STACK_INIT_SIZE;
35     return OK;
36 
37 }
38 //判斷棧是否為空
39 int EmptyStack(SqStack *p) {
40     //若為空棧 則返回OK，否則返回ERROR
41     if (p->top == p->base) return OK;
42     else return ERROR;
43 }
44 //順序棧的壓入
45 int Push(SqStack *p, StackType e) {
46     //插入元素e為新的棧頂元素
47     if ((p->top - p->base) >= p->stacksize)   //棧滿，追加儲存空間
48     {
49         p->base = (StackType*)realloc(p->base, (p->stacksize + STACKINCREMENT) * sizeof(StackType));
50         if (p->base == NULL)   return ERROR;// 儲存空間分配失敗
51         p->top = p->base + p->stacksize;   
52         p->stacksize += STACKINCREMENT;
53     }
54     *(p->top) = e;
55     (p->top)++;
56     return OK;
57 }
58 // 順序棧的彈出     
59 int Pop(SqStack *p, StackType *e) {
60     //若棧不空，則刪除p的棧頂元素，用e返回其值
61     if (p->top == p->base) return ERROR;
62     --(p->top);
63     *e = *(p->top);
64     return OK;
65 
66 
67 }
68 //將順序棧置空 棧還是存在的，棧中的元素也存在，
69 //如果有棧中元素的地址任然能調用
70 int ClearStack(SqStack *p) {
71     p->top = p->base;
72     return OK;
73 }
74 //順序棧的銷毀
75 int DestroyStack(SqStack *p) {
76     //釋放棧底空間並置空
77     free(p->base);
78     p->base = NULL;
79     p->top = NULL;
80     p->stacksize = 0;
81 
82     return OK;
83 }

　　源代碼：

  1 #include <stdio.h>
  2 #include <stdlib.h>
  3 #include "sqstack.h" //引入順序棧儲存結構及其基本操作
  4 #define MAXLENGTH 25  //設迷宮最大行列為25
  5 #define ERROR 0
  6 #define OK 1
  7 #define TRUE 1
  8 #define FALSE 0
  9 typedef int Status;
 10 typedef int MazeType[MAXLENGTH][MAXLENGTH]; //迷宮數組[行][列]
 11 PosType begin, end;   //迷宮入口坐標，出口坐標
 12 PosType direc[4] = { {0,1},{1,0},{0,-1},{-1,0} }; //{行增量，列增量}，移動方向依次為東南西北
 13 MazeType maze; //迷宮數組
 14 int x, y;//迷宮的行，列
 15 int curstep = 1;  //當前足跡，初值在入口處為1
 16 struct SElemType
 17 {
 18     int ord;  //通道塊在路徑上的“序號”
 19     PosType seat;   //通道塊在迷宮中的“坐標位置”
 20     int di;  //從此通道塊走向下一通道塊的“方向”(0-3表示東-北)
 21 };
 22 void Print() {
 23     //輸出迷宮結構
 24     int i, j;
 25     for (i = 0; i < x; i++)
 26     {
 27         for (j = 0; j < y; j++)
 28             printf("%3d", maze[i][j]);
 29         printf("\n");
 30     }
 31 }
 32 void Init()
 33 {
 34     //設定迷宮佈局(牆值為0，通道值為1)
 35     //全局變數maze 未初始化 所以均為值均為0
 36     int i, j, x1, y1;
 37     printf("請輸入迷宮的行數，列數(包括外牆):");
 38     scanf("%d%d", &x, &y);
 39     for (i = 1; i < x - 1; i++)
 40         for (j = 1; j < y - 1; j++)
 41             maze[i][j] = 1;  //定義通道初值為1
 42     printf("請輸入迷宮內牆單元數:");
 43     scanf("%d", &j);
 44     printf("請依次輸入迷宮內牆每個單元的行數，列數:\n");
 45     //FILE *fp; 註釋掉的這五行之前是方便我調試的
 46     //fp = fopen("maze.txt", "r");
 47     //int *px1 = &x1, *py1 = &y1;
 48     for(i=1;i<=j;i++)
 49     {
 50         //fscanf(fp, "%d%d", px1, py1);
 51         //maze[x1][y1] = 0;
 52         scanf("%d%d", &x1, &y1);
 53         maze[x1][y1] = 0; //定義牆值為0
 54     }
 55     printf("迷宮結構如下:\n");
 56     Print();
 57     printf("請輸入入口的行數，列數:");
 58     scanf("%d%d", &begin.x, &begin.y);
 59     printf("請輸入出口的行數，列數:");
 60     scanf("%d%d", &end.x, &end.y);
 61 }
 62 void MarkPrint(PosType seat)
 63 {//標記迷宮塊不可通過
 64     maze[seat.x][seat.y] = -1;
 65     
 66 
 67 }
 68 Status Pass(PosType b)
 69 {
 70     //當迷宮m的b點的值為1，return OK;
 71     //否則return ERROR;
 72     if (maze[b.x][b.y] == 1)
 73         return OK;
 74     else
 75         return ERROR;
 76 }
 77 void FootPrint(PosType b)
 78 {
 79 //使迷宮m的b點的值變為足跡(curstep),表示經過
 80     maze[b.x][b.y] = curstep;
 81 
 82 }
 83 PosType NextPos(PosType  b,int di)
 84 {
 85     //根據當前位置b及其移動方向di，修改b為下一位置
 86     b.x += direc[di].x;
 87     b.y += direc[di].y;
 88     return b;
 89 }
 90 Status MazePath(PosType start, PosType end)
 91 {
 92     //若迷宮m中存在從入口start到出口end的通道
 93     //則求得一條存放在棧中，並返回TRUE；否則返回FAlSE
 94     SqStack s,*S; //順序棧
 95     S = &s;
 96     PosType curpos;
 97     StackType e,*pe;
 98     pe = &e;
 99     InitStack(S);
100     curpos = start;
101     do
102     {
103         if (Pass(curpos)) //當前可以通過，則是未曾走到的通道塊
104         {
105             FootPrint(curpos); //留下足跡
106             e.ord = curstep;  //棧元素序號為當前序號
107             e.seat = curpos;  //棧元素位置為當前位置
108             e.di = 0;  //從當前位置出發，下一位置為東
109             Push(S, e); //入棧當前位置及其狀態
110             curstep++;   //足跡加1
111             if (curpos.x == end.x&&curpos.y == end.y)  //到達出口
112                 return TRUE;
113             curpos = NextPos(curpos, e.di); //由當前位置及移動方向確定下一個當前位置
114         }
115         else //當前位置不能通過
116             if (!EmptyStack(S))  //棧不為空
117             {
118                 Pop(S, pe); // 退棧到前一位置
119                 curstep--;  //足跡減1
120                 while (e.di == 3 && !EmptyStack(S))  //前一位置處於最後一個方向(北)
121                 {
122                     MarkPrint(e.seat); //留下不能通過的標記(-1)
123                     Pop(S, pe); //退一步
124                     curstep--; //足跡再減1
125 
126                 }
127                 if (e.di < 3)  //沒有到最後一個方向(北)
128                 {
129                     e.di++;  //換下一個方向探索
130                     Push(S, e); //入棧該位置的下一個方向
131                     curstep++;// 足跡加1
132                     curpos = NextPos(e.seat, e.di);
133 
134                 }
135 
136             }
137 
138     }
139     while (!EmptyStack(S));
140     return FALSE;
141     
142     
143 }
144 int main() 
145 {
146     Init();  //初始化迷宮
147     if (MazePath(begin, end)) //有通路
148     {
149         printf("從此迷宮入口到出口的一條路徑如下:\n");
150         Print();
151     }
152     else
153         printf("此迷宮沒有從入口到出口的路徑\n");
154     return 0;
155 
156     
157 }
158

　　測試如下：

　　需要註意的是得到的路徑並不是最短路徑。要求最短路徑應該把所有

路徑求出，再比較棧的大小。最小長度的棧則保存著最短的路徑。