中國礦業大學信控學院
一、 問題描述
問題中迷宮可用方陣[m,n]表示，0表示能通過，1表示不能通過，若要從從左上角[1,1]進入迷宮，設計演算法，尋求一條從右下角 [m,n] 出去的路徑，我們用遞增的數來代表尋找出口方向與步數，用-2來代表尋找程序中找錯的路徑，
二、 需求分析
需要先創建一個迷宮，在開始后就開始搜尋，當一個點周圍有0點（改點并不是以搜尋過的點），那么到這里繼續往下搜，如果搜到盡頭那么就要倒回去，在搜尋倒回去的周圍還有為搜尋過得0點，因此需要一個存盤演算法，要滿足后入先出，那么就是堆疊，利用堆疊就可以滿足需求，
三、 演算法分析
1. 首先先定義堆疊，本問題中，不需要在中間插入與彈出，插入與彈出操作均在堆疊頭，因此我們利用順序堆疊，
并且該堆疊與實驗課的堆疊不同，因為要滿足實際需求，所以我們需要定義步數以及改點所在的位置以及臨近路徑的位置在我們堆疊中，具體操作如下，
1 //記錄通道塊在迷宮矩陣當中的橫、縱坐標
2 struct Position {
3 int x;
4 int y;
5 };
6
7 //放入堆疊當中的通道塊元素
8 struct SElement {
9 int ord;//記錄步數
10 Position p;//記錄位置
11 int di;//記錄下一次測驗這一路徑的臨近路徑的位置
12 };
13
14 struct MyStack {
15 SElement* base;
16 SElement* top;
17 int stacksize;
18 };
2. 堆疊的一些列基礎操作，例如創建堆疊，判斷堆疊是否為空，取堆疊頂元素，獲取堆疊長，入堆疊，出堆疊，上述操作類似學校實驗中基本操作，這里不在敘述，詳見附錄中全部代碼，
3. 接下來創建迷宮，這里迷宮利用陣列來生成，x軸為n，y軸為m
n為18，m為15，生成方法簡單，這里不在敘述，詳見附錄中全部代碼，
4. 接下來定義如何走這個迷宮，考慮我們用0作為通道，1作為墻壁，那么搜尋一個點的上下左右0就是可以通過，1就是不能通過，利用以下回圈來完成目標：
步驟1：挪到0處的點并且把剛才位置入堆疊，讓改點改為步數，讓步數加一，然后繼續搜索其上下左右（除去剛才通過的點）如果有0，繼續執行步驟1，
步驟2：如果周圍的點無0（除去剛才已經通過的點），讓改點改為-2，那么就出堆疊，把路徑調到剛才的那個點，并且把步數減一，然后執行步驟1，搜尋其上下左右（出去剛才走錯的點以及入這個點之前的點），
直至入堆疊點是終點那么退出回圈，
代碼如下：
1 do
2 {
3 if (Pass(curp))
4 {
5 FootPrint(curp, curStep);//可走就在迷宮里面留下足跡
6 //創建一個堆疊元素，存盤可行路徑的相關值
7 SElement e;
8 e.di = 1;// 下一個路塊為這一個路塊的右邊的路塊
9 e.ord = curStep;
10 e.p.x = curp.x;
11 e.p.y = curp.y;
12 Push(&path, e);//將路徑塊入堆疊
13 if (curp.x == m - 2 && curp.y == n - 2) break; //如果被壓入的路徑塊到了迷宮的終點就退出回圈
14 //找到下一個被試塊
15 curp = NextPosition(curp, 1);//找到前一個被試塊東面的路徑塊作為被試塊
16 curStep++;//被探索的步數加一
17 }
18 else//如果當前被試路徑不能夠通過的話
19 {
20 if (!IsStackEmpty(&path))
21 {
22 SElement e;
23 Pop(&path, &e);
24 curStep--;
25 //將這一段所有的周圍路徑都已經被測驗過的路徑從堆疊中清除
26 while (e.di == 4 && !IsStackEmpty(&path)) {
27 MarkPrint(e.p);
28 Pop(&path, &e);
29 curStep--;
30 }
31 //如果當前堆疊頂還有未被測驗的路徑就測驗剩余的周圍路徑
32 if (e.di<4)
33 {
34 curp = NextPosition(e.p, e.di + 1);
35 e.di++;
36 curStep++;
37 Push(&path, e);
38 }
39 }
40 }
41 } while (!IsStackEmpty(&path));
5. 在定義上述代碼中如何去搜尋，按照從右到下再到左再到上的方法搜尋，代碼如下：
1 //按順時針方向從右開始尋找矩陣當中某一個位置的臨近位置
2 Position NextPosition(Position now, int direction)
3 {
4 Position next;
5 int x = now.x;
6 int y = now.y;
7 switch (direction)
8 {
9 //右
10 case 1: {
11 next.x = x;
12 next.y = y + 1;
13 break;
14 }
15 //下
16 case 2: {
17 next.x = x + 1;
18 next.y = y;
19 break;
20 }
21 //左
22 case 3: {
23 next.x = x;
24 next.y = y - 1;
25 break;
26 }
27 //上
28 case 4:{
29 next.x = x - 1;
30 next.y = y;
31 break;
32 }
33 default:break;
34 }
35 return next;
36}
6. 定義是否可以通過函式，是就回傳ture不是就回傳false，代碼如下：
1 //輔助函式考察當前路徑能否通過
2 bool Pass(Position posi)
3 {
4 //只有路徑所在位置的數字為0的是可以走的
5 if (Maze[posi.x][posi.y] == 0)
6 {
7 return true;
8 }
9 return false;
10 }
7. 定義是入堆疊和出堆疊時如何修改迷宮陣列中的值，代碼如下：
1 //改變改點為步驟數
2 void FootPrint(Position p, int step)
3 {
4 Maze[p.x][p.y] = step;
5 }
6
7 //路徑不可走的話就留下-2的標記
8 void MarkPrint(Position p)
9 {
10 Maze[p.x][p.y] = -2;
11}
8. 定義列印迷宮函式，這個就是遍歷整個陣列，程序簡單這里不在敘述，見附錄中全部代碼，
四、 結論
編輯ing...
五、 參考文獻
[1] 嚴蔚敏，吳偉民——《資料結構》清華大學出版社2004.2.1
六、 附錄
完整代碼如下：
1 #include <stdio.h> 2 #include <malloc.h> 3 #define STACK_INIT_SIZE 100 4 #define STACKINCREMENT 10 5 6 //記錄通道塊在迷宮矩陣當中的橫、縱坐標 7 struct Position { 8 int x; 9 int y; 10 }; 11 12 //放入堆疊當中的通道塊元素 13 struct SElement { 14 int ord;//記錄步數 15 Position p;//記錄位置 16 int di;//記錄下一次測驗這一路徑的臨近路徑的位置 17 }; 18 19 struct MyStack { 20 SElement* base; 21 SElement* top; 22 int stacksize; 23 }; 24 25 //創建一個堆疊如果創建成功則回傳1，否則就回傳0 26 int InitStack(MyStack* s) 27 { 28 s->base = (SElement*)malloc(STACK_INIT_SIZE * sizeof(SElement));//為堆疊分配初始空間 29 if (!s->base) return 0; 30 s->top = s->base;//設定為空堆疊 31 s->stacksize = STACK_INIT_SIZE; 32 return 1; 33 } 34 35 //判斷堆疊是否為空，如果是空的就回傳0，否則就回傳1 36 int IsStackEmpty(MyStack* s) 37 { 38 if (s->top == s->base) return true; 39 return false; 40 } 41 42 //獲取堆疊頂元素,如果堆疊為空就回傳0 否則就回傳1 43 int GetTop(MyStack* s, SElement* e) 44 { 45 if (IsStackEmpty(s)) return 0; 46 e = s->top - 1; 47 return 1; 48 } 49 50 //獲取堆疊的長度，并且通程序式回傳 51 int StackLength(MyStack* s) 52 { 53 return s->top - s->base; 54 } 55 56 //插入元素e為新的堆疊頂元素，插入成功則回傳1，否則回傳0 57 int Push(MyStack* s, SElement e) 58 { 59 if (s->top - s->base >= STACK_INIT_SIZE) 60 { 61 s->base = (SElement*)realloc(s->base, (s->stacksize + STACKINCREMENT) * sizeof(SElement)); 62 if (!s->base) return 0; 63 s->top = s->base + s->stacksize; 64 s->stacksize += STACKINCREMENT; 65 } 66 *(s->top) = e; 67 s->top++; 68 return 1; 69 } 70 71 //彈出堆疊頂元素賦值給e彈出成功回傳1，彈出失敗回傳0 72 int Pop(MyStack* s, SElement* e) 73 { 74 if (IsStackEmpty(s)) return 0; 75 *e = *(s->top - 1); 76 s->top--; 77 return 1; 78 } 79 80 //定義墻元素為1 可走路徑為0 已知路徑為curStep 不能夠通過的路徑為-2 81 #define m 15 82 #define n 18 83 int Maze[m][n] = { { 1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1 }, 84 { 1,0,0,0,1,0,0,1,0,0,0,0,0,0,0,0,0,1 }, 85 { 1,0,1,1,1,0,1,0,0,1,0,1,1,1,1,1,0,1 }, 86 { 1,0,1,1,1,0,1,0,1,1,0,1,0,1,1,0,0,1 }, 87 { 1,0,0,0,0,0,1,0,1,1,0,1,0,0,0,0,1,1 }, 88 { 1,1,1,1,0,0,1,0,1,1,0,1,1,1,1,0,1,1 }, 89 { 1,1,1,0,0,1,1,0,1,1,0,0,0,1,1,1,1,1 }, 90 { 1,1,1,0,1,1,1,0,1,1,1,1,0,1,1,0,0,1 }, 91 { 1,1,1,0,0,0,0,0,0,0,1,1,0,1,1,0,1,1 }, 92 { 1,0,0,1,1,1,1,1,1,0,1,1,0,1,0,0,1,1 }, 93 { 1,1,0,0,0,0,0,0,0,0,1,0,0,1,0,1,1,1 }, 94 { 1,0,0,1,0,1,0,1,0,0,1,1,0,0,0,1,1,1 }, 95 { 1,1,0,1,0,1,0,1,1,1,0,0,0,1,1,1,1,1 }, 96 { 1,1,0,0,0,0,0,1,1,1,1,1,0,0,0,0,0,1 }, 97 { 1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1 } }; 98 99 //輔助函式考察當前路徑能否通過 100 bool Pass(Position posi) 101 { 102 //只有路徑所在位置的數字為0的是可以走的 103 if (Maze[posi.x][posi.y] == 0) 104 { 105 return true; 106 } 107 return false; 108 } 109 110 //按順時針方向從右開始尋找矩陣當中某一個位置的臨近位置 111 Position NextPosition(Position now, int direction) 112 { 113 Position next; 114 int x = now.x; 115 int y = now.y; 116 switch (direction) 117 { 118 //右 119 case 1: { 120 next.x = x; 121 next.y = y + 1; 122 break; 123 } 124 //下 125 case 2: { 126 next.x = x + 1; 127 next.y = y; 128 break; 129 } 130 //左 131 case 3: { 132 next.x = x; 133 next.y = y - 1; 134 break; 135 } 136 //上 137 case 4: 138 { 139 next.x = x - 1; 140 next.y = y; 141 break; 142 } 143 default:break; 144 } 145 return next; 146 } 147 148 //改變改點為步驟數 149 void FootPrint(Position p, int step) 150 { 151 Maze[p.x][p.y] = step; 152 } 153 154 //路徑不可走的話就留下-2的標記 155 void MarkPrint(Position p) 156 { 157 Maze[p.x][p.y] = -2; 158 } 159 160 //列印出迷宮矩陣 161 void Display_migong() 162 { 163 for (int i = 0; i<m; i++) 164 { 165 for (int j = 0; j<n; j++) 166 { 167 if (Maze[i][j]<0) 168 printf("%d ", Maze[i][j]); 169 else if (Maze[i][j]<10) 170 printf("%d ", Maze[i][j]); 171 else 172 printf("%d ", Maze[i][j]); 173 } 174 printf("\n"); 175 } 176 } 177 178 int main() 179 { 180 181 //迷宮程式主體 182 MyStack path;//記錄路徑的堆疊 183 InitStack(&path);//初始化路徑陣列 184 Position curp;//當前被試位置 185 Display_migong(); 186 //初始化當前位置為矩陣入口 187 curp.x = 1; 188 curp.y = 1; 189 int curStep = 1;//被探索的步數 190 do 191 { 192 if (Pass(curp)) 193 { 194 FootPrint(curp, curStep);//可走就在迷宮里面留下足跡 195 //創建一個堆疊元素，存盤可行路徑的相關值，將這個元素存盤到堆疊當中 196 SElement e; 197 e.di = 1;//下一個路塊為這一個路塊的右邊的路塊 198 e.ord = curStep; 199 e.p.x = curp.x; 200 e.p.y = curp.y; 201 Push(&path, e);//將路徑塊入堆疊 202 if (curp.x == m - 2 && curp.y == n - 2) break; //如果被壓入的路徑塊到了迷宮的終點就退出回圈 203 curp = NextPosition(curp, 1);//找到前一個被試塊東面的路徑塊作為被試塊 204 curStep++;//被探索的步數加一 205 } 206 else//如果當前被試路徑不能夠通過的話 207 { 208 if (!IsStackEmpty(&path)) 209 { 210 SElement e; 211 Pop(&path, &e); 212 curStep--; 213 //將所有的周圍路徑都已經被測驗過的路徑從堆疊中清除 214 while (e.di == 4 && !IsStackEmpty(&path)) { 215 MarkPrint(e.p); 216 Pop(&path, &e); 217 curStep--; 218 } 219 //如果當前堆疊頂還有未被測驗的路徑就測驗剩余的周圍路徑 220 if (e.di<4) 221 { 222 curp = NextPosition(e.p, e.di + 1); 223 e.di++; 224 curStep++; 225 Push(&path, e); 226 } 227 } 228 } 229 } while (!IsStackEmpty(&path)); 230 printf("\n"); 231 //列印出結果迷宮矩陣 232 Display_migong(); 233 return 0; 234 }
轉載請註明出處，本文鏈接：https://www.uj5u.com/houduan/52973.html
標籤：C
上一篇：c語言一道題