《數據結構與演算法分析》課程設計——迷宮問題

来源:https://www.cnblogs.com/zhangzhangzhang624531420/archive/2020/01/12/12181727.html
-Advertisement-
Play Games

中國礦業大學信控學院 一、 問題描述 問題中迷宮可用方陣[m,n]表示，0表示能通過，1表示不能通過。若要從從左上角[1,1]進入迷宮，設計演算法，尋求一條從右下角 [m,n] 出去的路徑。我們用遞增的數來代表尋找出口方向與步數，用-2來代表尋找過程中找錯的路徑。 二、 需求分析 需要先創建一個迷宮， ...


中國礦業大學信控學院

 

一、 問題描述

 

問題中迷宮可用方陣[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 }

您的分享是我們最大的動力!

-Advertisement-
Play Games
更多相關文章
  • css的三種導入方式
    內聯樣式表 內部樣式表 外部樣式表 創建一個cssTest.css的css文件 使用外部樣式表 完整測試代碼 css文件 css三種導入方式的優先順序 內聯樣式表 內部樣式表 外部樣式表 ...
  • es6種for迴圈中let和var區別
    let和var區別： 1 for(var i=0;i<5;i++){ 2 setTimeout(()=>{ 3 console.log(i);//5個5 4 },100) 5 } 6 console.log(i);//5 7 console.log(' ') 8 9 for(let j=0;j<5; ...
  • javascript當中靜態方法和prototype用法
    6）靜態方法和prototype（難）例 3.6.1<head> <meta http-equiv="content-type" content="text/html; charset=utf-8"/></head><script> /*note that 馬克-to-win： static var ...
  • react-antd-input-onPressEnter
    2020-01-11 ant-Design ，Input ， onPressEnter 和 onChange 的區別 onChange 輸入內容的回調 onPressEnter 按下回車的回調 需求：看下圖，右邊欄配置開關組件的內容。輸入內容，不想要左邊實時更改 原來的代碼：<Input defau ...
  • JavaScript仿計算器案例源代碼
    效果圖 index.html <!DOCTYPE html> <html> <head> <title></title> <link rel="stylesheet" type="text/css" href="calc.css"> <script type="text/javascript" sr ...
  • K8s~為pod添加sidecar進行日誌收集
    我們在k8s部署服務時，一般來說一個服務會對應一類pod，而pod通過rs實現副本集，而這些pod的日誌一般有控制台stdout和文件的，一般會把這些日誌最終輸出到elasticsearch里，再通過kabana進行分析，而在實現由pod到elasticsearch（es）時有多種方法，下麵我列舉一 ...
  • spring cloud springboot 框架源碼 activiti工作流 前後分離 集成代碼生成器
    1.代碼生成器： [正反雙向](單表、主表、明細表、樹形表，快速開發利器)freemaker模版技術 ,0個代碼不用寫,生成完整的一個模塊,帶頁面、建表sql腳本、處理類、service等完整模塊2.多數據源：（支持同時連接無數個資料庫，可以不同的模塊連接不同數的據庫）支持N個數據源3.阿裡資料庫連 ...
  • 《數據結構與演算法分析》課程設計——貪吃蛇問題
    中國礦業大學信控學院 /*文獻參考*/ https://blog.csdn.net/Fdog_/article/details/102625969 https://blog.csdn.net/DY_1024/article/details/78841757 一、問題描述 以數據結構思想設計實現貪吃蛇 ...
一周排行
    -Advertisement-
    Play Games
  • 移動開發（一）：使用.NET MAUI開發第一個安卓APP
    移動開發（一）：使用.NET MAUI開發第一個安卓APP 對於工作多年的C#程式員來說，近來想嘗試開發一款安卓APP，考慮了很久最終選擇使用.NET MAUI這個微軟官方的框架來嘗試體驗開發安卓APP，畢竟是使用Visual Studio開發工具，使用起來也比較的順手，結合微軟官方的教程進行了安卓 ...
  • wpf ToggleButton選中效果和一個登錄界面
    前言 QuestPDF 是一個開源 .NET 庫，用於生成 PDF 文檔。使用了C# Fluent API方式可簡化開發、減少錯誤並提高工作效率。利用它可以輕鬆生成 PDF 報告、發票、導出文件等。 項目介紹 QuestPDF 是一個革命性的開源 .NET 庫，它徹底改變了我們生成 PDF 文檔的方 ...
  • 彈幕樹洞項目功能新增篇
    項目地址 項目後端地址： https://github.com/ZyPLJ/ZYTteeHole 項目前端頁面地址： ZyPLJ/TreeHoleVue (github.com) https://github.com/ZyPLJ/TreeHoleVue 目前項目測試訪問地址： http://tree ...
  • 第27篇 sqlserver2022詳細安裝步驟
    話不多說，直接開乾 一.下載 1.官方鏈接下載： https://www.microsoft.com/zh-cn/sql-server/sql-server-downloads 2.在下載目錄中找到下麵這個小的安裝包 SQL2022-SSEI-Dev.exe，運行開始下載SQL server； 二. ...
  • .NET 開源高性能 MQTT 類庫
    前言 隨著物聯網（IoT）技術的迅猛發展，MQTT（消息隊列遙測傳輸）協議憑藉其輕量級和高效性，已成為眾多物聯網應用的首選通信標準。 MQTTnet 作為一個高性能的 .NET 開源庫，為 .NET 平臺上的 MQTT 客戶端與伺服器開發提供了強大的支持。 本文將全面介紹 MQTTnet 的核心功能 ...
  • Serilog文檔翻譯系列（六） - 可用的接收器、增強器、格式化輸出
    Serilog支持多種接收器用於日誌存儲，增強器用於添加屬性，LogContext管理動態屬性，支持多種輸出格式包括純文本、JSON及ExpressionTemplate。還提供了自定義格式化選項，適用於不同需求。 ...
  • 警惕 Visual Studio 屬性求值副作用導致邏輯不符合預期
    目錄簡介獲取 HTML 文檔解析 HTML 文檔測試參考文章 簡介 動態內容網站使用 JavaScript 腳本動態檢索和渲染數據，爬取信息時需要模擬瀏覽器行為，否則獲取到的源碼基本是空的。 本文使用的爬取步驟如下： 使用 Selenium 獲取渲染後的 HTML 文檔 使用 HtmlAgility ...
  • [使用目前最新版]HybridCLR6.9.0+YooAsset2.2.4實現純C# Unity熱更新方案 (一)
    1.前言 什麼是熱更新 游戲或者軟體更新時，無需重新下載客戶端進行安裝，而是在應用程式啟動的情況下，在內部進行資源或者代碼更新 Unity目前常用熱更新解決方案 HybridCLR，Xlua，ILRuntime等 Unity目前常用資源管理解決方案 AssetBundles，Addressable， ...
  • 在 ASP.NET Core Web API 中使用操作篩選器統一處理通用操作
    本文章主要是在C# ASP.NET Core Web API框架實現向手機發送驗證碼簡訊功能。這裡我選擇是一個互億無線簡訊驗證碼平臺，其實像阿裡雲，騰訊雲上面也可以。 首先我們先去 互億無線 https://www.ihuyi.com/api/sms.html 去註冊一個賬號 註冊完成賬號後，它會送 ...
  • 第28篇 如何.net中實現高效可靠數據同步api
    通過以下方式可以高效，並保證數據同步的可靠性 1.API設計 使用RESTful設計，確保API端點明確，並使用適當的HTTP方法（如POST用於創建，PUT用於更新）。 設計清晰的請求和響應模型，以確保客戶端能夠理解預期格式。 2.數據驗證 在伺服器端進行嚴格的數據驗證，確保接收到的數據符合預期格 ...
所有分類