好家伙，寫大作業(yè),本篇為代碼的思路講解
?文章來源：http://www.zghlxwxcb.cn/news/detail-437362.html
1.大作業(yè)要求
走迷宮程序
問題描述：
以一個 m * n 的長方陣表示迷宮， 0和1分別表示迷宮的通路和障礙。 設(shè)計一個程序， 對任意設(shè)定的迷宮， 求出一條從入口到出口的通路， 或得出沒有通路的結(jié)論。
基本要求：
（1） 實現(xiàn)一個以鏈表做存儲的棧類型， 然后編寫一個求解迷宮的非遞歸程序。 求的通路以三元組（i， j， d） 的形式輸出， 其中：（i， j） 指示迷宮中的一個坐標， d 表示走到下一坐標的方向。 如： 對于下列數(shù)據(jù)的迷宮， 輸出一條通路：
（1， 1， 1），（1， 2， 2），
（2， 2， 2），（3， 2， 3），（3， 1， 2） ……。
（2） 編寫遞歸形式的算法， 求得迷宮中所有可能的道路；
擴展功能要求：
以方陣形式輸出迷宮及其到道路
測試數(shù)據(jù)： 迷宮的測試數(shù)據(jù)如下： 左上角（1， 1） 為入口， 右下角（8， 9） 為出口。
?
作業(yè)要求
1、 選題：從4個題目中任選其一，獨立完成。程序至少采用所學過的一種數(shù)據(jù)結(jié)構(gòu)（鏈表、棧、隊列、樹等）實現(xiàn)。學生可以根據(jù)自己的需求分析適當?shù)卣{(diào)整程序的合理性，使得程序能夠更加貼近實際。每個題目選題人員不得超過15人，向?qū)W委報名選題情況，先報先得，每個題目滿15人后必須另選其他題目。
2、 程序代碼要求：程序要求能夠正常運行，基本功能必須全部實現(xiàn)。完成可選做的擴展功能將得到較高的分數(shù)。容錯性強和功能細節(jié)考慮更完全也將得到較高的分數(shù)。
3、 開發(fā)語言:軟件工程和數(shù)據(jù)科學與大數(shù)據(jù)技術(shù)專業(yè)用Java語言，計算機科學與技術(shù)專業(yè)用C或C++語言。
?文章來源地址http://www.zghlxwxcb.cn/news/detail-437362.html
2.分析
來概括一下
這是個迷宮程序，手動輸入迷宮，找出所有解，輸出所有解
數(shù)據(jù)結(jié)構(gòu)要用棧
解法：
我們用一個二維度數(shù)組保存這個"迷宮"
1.隨后,我們確定起點和終點,
2.先站在起點上,將起點入棧
3.我們開始尋路,按照東南西北(即右下左上)的方向順序?qū)ふ蚁乱蛔鴺?/span>
3.1.如果該方向上有路,將下一坐標入棧,"走到"這個坐標上
3.2.如果下一坐標上是墻,則返回
3.3.如果下一個點是出口,則打印線路
?
3.單路徑版本
大概是這樣了
代碼如下:
單路徑版本
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#define MAXN 20
struct mark // 定義迷宮內(nèi)點的坐標類型
{
int x;
int y;
};
struct Element // 鏈棧元素結(jié)點
{
int x, y; // x行,y列
int d; // d下一步的方向
};
typedef struct LStack // 鏈棧
{
Element elem;
struct LStack *next; // 指針變量
};
typedef LStack *PLStack;
/*……………………………棧函數(shù)……………………………*/
int InitStack(PLStack &S) // 構(gòu)造空棧
{
S = NULL;
return 1;
}
int StackEmpty(PLStack S) // 判斷棧是否為空
{
if (S == NULL)
return 1;
else
return 0;
}
int Push(PLStack &S, Element e) // 壓入新數(shù)據(jù)元素
{
PLStack p;
p = (PLStack)malloc(sizeof(LStack));
p->elem = e;
p->next = S;
S = p;
return 1;
}
int Pop(PLStack &S, Element &e) // 棧頂元素出棧
{
PLStack p;
if (!StackEmpty(S))
{
e = S->elem;
p = S;
S = S->next;
free(p);
return 1;
}
else
return 0;
}
/*……………………求迷宮路徑函數(shù)……………………………*/
void MazePath(struct mark start, struct mark end, int maze[MAXN][MAXN], int diradd[4][2])
{
int i, j, d;
int a, b;
Element elem, e;
PLStack S1, S2;
InitStack(S1);
InitStack(S2);
maze[start.x][start.y] = 2; // 入口點作上標記
elem.x = start.x;
elem.y = start.y;
elem.d = -1; // 開始為-1
Push(S1, elem);
while (!StackEmpty(S1)) // 棧不為空 有路徑可走
{
Pop(S1, elem);
i = elem.x;
j = elem.y;
d = elem.d + 1; // 下一個方向
while (d < 4) // 試探東南西北各個方向
{
a = i + diradd[d][0];
b = j + diradd[d][1];
if (a == end.x && b == end.y && maze[a][b] == 0) // 如果到了出口
{
elem.x = a;
elem.y = b;
elem.d = 886; // 方向輸出為-1 判斷是否到了出口
Push(S1, elem);
printf("\n0=東 1=南 2=西 3=北 886為則走出迷宮\n\n通路為:(行坐標,列坐標,方向)\n");
while (S1) // 逆置序列 并輸出迷宮路徑序列
{
Pop(S1, e);
Push(S2, e);
}
while (S2)
{
Pop(S2, e);
printf("-->(%d,%d,%d)", e.x, e.y, e.d);
}
return; // 跳出兩層循環(huán)，本來用break,但發(fā)現(xiàn)出錯，exit又會結(jié)束程序，選用return
}
if (maze[a][b] == 0) // 找到可以前進的非出口的點
{
maze[a][b] = 2; // 標記走過此點
elem.x = i;
elem.y = j;
elem.d = d;
Push(S1, elem); // 當前位置入棧
i = a; // 下一點轉(zhuǎn)化為當前點
j = b;
d = -1;
}
d++;
}
}
printf("沒有找到可以走出此迷宮的路徑\n");
}
/*……………………………建立迷宮……………………………*/
void initmaze(int maze[MAXN][MAXN])
{
int i, j;
int m, n; // 迷宮行,列
printf("請輸入迷宮的行數(shù) m="); // 輸入迷宮
scanf("%d", &m);
printf("請輸入迷宮的列數(shù) n=");
scanf("%d", &n);
printf("\n請輸入迷宮的各行各列:\n用空格隔開,0代表路,1代表墻\n", m, n);
for (i = 1; i <= m; i++)
{
for (j = 1; j <= n; j++)
scanf("%d", &maze[i][j]);
}
printf("你建立的迷宮為\n");
for (i = 0; i <= m + 1; i++) // 加一圈圍墻
{
maze[i][0] = 1;
maze[i][n + 1] = 1;
}
for (j = 1; j <= n; j++)
{
maze[0][j] = 1;
maze[m + 1][j] = 1;
}
for (i = 0; i <= m + 1; i++) // 輸出迷宮
{
for (j = 0; j <= n + 1; j++)
printf("%d ", maze[i][j]);
printf("\n");
}
}
int main()
{
int sto[MAXN][MAXN];
struct mark start, end; // start,end入口和出口的坐標
int add[4][2] = {{0, 1}, {1, 0}, {0, -1}, {-1, 0}}; // 行增量和列增量 方向依次為東西南北
initmaze(sto); // 建立迷宮
printf("輸入入口的橫坐標,縱坐標[空格隔開]\n");
scanf("%d %d", &start.x, &start.y);
printf("輸入出口的橫坐標,縱坐標[空格隔開]\n");
scanf("%d %d", &end.x, &end.y);
MazePath(start, end, sto, add); // find path
printf("\n");
}
?
效果如下:
?
看上去沒什么問題了,
?
但是,這種方法無法實現(xiàn)多條路徑的打印
所以還是要使用搜索算法
下面,我們使用深度優(yōu)先搜索來解決這個問題
此處我們使用遞歸的思想
?
4.最終版本
解法由:
用一個二維度數(shù)組保存這個"迷宮"
1.隨后,我們確定起點和終點,
2.先站在起點上,將起點入棧
3.我們開始尋路,按照東南西北(即右下左上)的方向順序?qū)ふ蚁乱蛔鴺?/span>
3.1.如果該方向上有路,將下一坐標入棧,"走到"這個坐標上
3.2.如果下一坐標是墻,則進行下一次循環(huán)
3.3.如果下一個點是出口,則打印線路
?
改為
用一個二維度數(shù)組保存這個"迷宮"
1.隨后,我們確定起點和終點,
2.先站在起點上,將起點入棧
3.尋路方法(){
"走到下一點上"(第一次調(diào)用時不做這步)
3.1.開始尋路,按照東南西北(即右下左上)的方向順序確定下一坐標,
| 3.1.1如果該方向上有路,下一坐標入棧,并標記為2(標記為走過)
| | 3.1.1.1如果下一個點是出口,則打印線路,將下一坐標標記為0,棧頂出棧
| | 3.1.1.2.調(diào)用尋路方法
| 3.1.2.開始下一次循環(huán),回到3.1
3.2.出棧,當前點賦值為0
}
?
核心算法部分實現(xiàn):
//-----------遍歷迷宮尋找路徑(dfs)------------
void mazePath(int x,int y,int endx,int endy,int n,int m,Stack s){
int newx,newy,i;
Node t;
for(i=0;i<4;i++){
newx=x+direction[i][0];
newy=y+direction[i][1];
if(newx>=0&&newx<n&&newy>=0&&newy<m&&maze[newx][newy]==0){ //下一個路能走
push(newx,newy,s);
maze[newx][newy]=2;
if(newx==endx&&newy==endy){//走到出口
flag++;
printPath(s,n,m);
maze[newx][newy]=0;
pop(s);
}
else{
mazePath(newx,newy,endx,endy,n,m,s); //開始遞歸
}
}
}
maze[x][y]=0; //遍歷完四個方向之后回溯前將自己賦為空
pop(s);
}
?
完整代碼:
所有路徑版本:
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#define MAXN 20
/* *建立一個二維數(shù)組存迷宮
*要是四個方向能有位置則壓入棧，要是下一步?jīng)]有則彈出?；厮? *直到找到終點為止
*/
int direction[4][2] = {{0, 1}, {1, 0}, {0, -1}, {-1, 0}}; //定義一個數(shù)組存四個方向操作數(shù)
int MIN=100;//用于記錄最小路徑
int maze[MAXN][MAXN];
int flag=0;
//棧中存位置以及遍歷時所走的方向，打印時可以顯示出來
//棧的元素節(jié)點
typedef struct Node{
int x;
int y;
struct Node *next;
}Node;
typedef Node* Stack; //定義數(shù)據(jù)結(jié)構(gòu)棧 Stack
/*……………………………棧函數(shù)……………………………*/
//-----------創(chuàng)建一個空棧--------------
Stack creakEmptyStack(){
Stack p;
p=(Stack)malloc(sizeof(Node)); //申請一個空間
if(p){
p->next=NULL;
return p;
}
}
//------------將元素壓入棧----------------
void push(int x,int y,Stack s){
Stack p;
p=(Stack)malloc(sizeof(Node));
if(p){ //如果申請空間成功則用頭插法將元素壓入
p->x=x;
p->y=y;
if(!s->next) p->next=NULL; //如果此時棧里還沒有任何元素，則p此時為第一個結(jié)點
else p->next=s->next; //否則將p插入頭結(jié)點之后
s->next=p;
}
else{
printf("No space!\n");
}
}
//-------------檢測棧是否為空--------------
int isEmpty(Stack s){ //為空則返回1，不為空返回0
if(s->next==NULL) return 1;
else return 0;
}
//--------------將元素彈出棧----------------
void pop(Stack s){
Stack p;
p=s->next;
if(p->next){
s->next=p->next;
free(p);
}
else return;
}
//------------取棧頂元素------------------
Node top(Stack s){
Node t;
//判斷是否為空，若不為空則返回
t=*(s->next);
return t;
}
void mazePath(int x,int y,int endx,int endy,int n,int m,Stack s);
void printPath(Stack s,int n,int m);
int main()
{
int n,m,i,j,xa,xb,ya,yb,ox;
//--------------建立迷宮--------------
printf("請輸入迷宮大?。海ㄩL、寬）\n");
scanf("%d%d",&n,&m);
if(n<=20&&m<=20){
printf("請選擇構(gòu)建迷宮的方式：\n0.隨機生成迷宮\n1.手動輸入迷宮\n"); //實際上不是0就可以手動輸入
scanf("%d",&ox);
for(i=0;i<n;i++){
for(j=0;j<m;j++){
if(!ox)maze[i][j]=rand()%2; //這里為偽隨機數(shù)
else scanf("%d",&maze[i][j]);
}
}
printf("\n");
//----------輸出構(gòu)建迷宮-------------
printf("生成的迷宮如下：\n");
for(i=0;i<n;i++){
for(j=0;j<m;j++){
printf("%d ",maze[i][j]);
}
printf("\n");
}
printf("請輸入起點及終點：\n");
scanf("%d%d%d%d",&xa,&ya,&xb,&yb);
//標記起點
maze[xa-1][ya-1]=2;
//創(chuàng)建一個空棧
Stack s=creakEmptyStack();
mazePath(xa-1,ya-1,xb-1,yb-1,n,m,s);
printf("最短路徑長度為:%d",MIN);
if(!flag) printf("沒有成功找到路徑\n");
}
else printf("輸入數(shù)據(jù)超出迷宮范圍\n");
}
//-----------遍歷迷宮尋找路徑(dfs)------------
void mazePath(int x,int y,int endx,int endy,int n,int m,Stack s){
int newx,newy,i;
Node t;
for(i=0;i<4;i++){
newx=x+direction[i][0];
newy=y+direction[i][1];
if(newx>=0&&newx<n&&newy>=0&&newy<m&&maze[newx][newy]==0){ //下一個路能走
push(newx,newy,s);
maze[newx][newy]=2;
if(newx==endx&&newy==endy){//走到出口
flag++;
printPath(s,n,m);
maze[newx][newy]=0;
pop(s);
}
else{
mazePath(newx,newy,endx,endy,n,m,s); //開始遞歸
}
}
}
maze[x][y]=0; //遍歷完四個方向之后回溯前將自己賦為空
pop(s);
}
//-------------打印迷宮路徑-----------------
void printPath(Stack s,int n,int m){
int cont =0; //計算路徑長度
s=s->next;
int i=0,j=0;
printf("第%d條路徑為：\n",flag);
for(i=0;i<n;i++){ //按圖形輸出
for(j=0;j<m;j++){
if(maze[i][j]==2) printf("* ");
else printf("%d ",maze[i][j]);
}
printf("\n");
}
while(s->next){ //將棧中的元素輸出為直觀路徑
printf("(%d,%d)->",s->x+1,s->y+1);
s=s->next;
cont++;
}
printf("(%d,%d)",s->x+1,s->y+1);
cont++;
if(cont<MIN) MIN=cont;
printf("\n");
printf("路徑長度為：%d\n\n",cont);
}
?
測試樣例:
?
?
到了這里，關(guān)于數(shù)據(jù)結(jié)構(gòu)與算法大作業(yè)：走迷宮程序（C語言,DFS)(代碼以及思路）的文章就介紹完了。如果您還想了解更多內(nèi)容，請在右上角搜索TOY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！
![【Python數(shù)據(jù)結(jié)構(gòu)與算法】--- 遞歸算法的應用 ---[烏龜走迷宮] |人工智能|探索掃地機器人工作原理](https://imgs.yssmx.com/Uploads/2024/02/752756-1.gif)
