以下算法均是原創(chuàng)，未參考任何資料！請勿抄襲！歡迎交流。
親測可行：
使用藍橋杯比賽編譯器：DEV C++?
求迷宮中從入口到出口的路徑是一個經(jīng)典的程序設(shè)計問題，通常采用“窮舉求解”的方法，即順著某一方向向前探索，若能走通，則繼續(xù)往前走；否則原路返回，換一個方向繼續(xù)探索，直至所有可能的通路都探索到為止。
因此，在求解迷宮問題的時候應(yīng)用“棧”也就是自然而然的事了。
對于程序來說：
1.我們需要規(guī)定一個方向作為主方向，使得“自己”的位置不斷移動，直到“遇到走不通的地方”或者是“遇到之前走過的地方”。
方向定義：
東：1
南：2
西：3
北：4
2.我們需要直到我們經(jīng)過哪些地方，在這里我們將除棧頂外的其他元素視為“經(jīng)過的地方”?。。?/span>
3.我們需要一個二維數(shù)組存放“迷宮”，還需要一個二維數(shù)組存放“走過的地方”。
迷宮：
?走過的地方：（這里把所有地點初始化為0，代表尚未經(jīng)過，經(jīng)過的地方會被重新賦值為1）
?4.最后，當(dāng)我們“走”到終點的時候，路徑的每一個“點”都會存放到“?！敝?，我們將其依次彈出即可得到最終路徑。
?過程截圖：
?
棧：
順序棧，棧中每一個結(jié)構(gòu)體對應(yīng)一個點，x表示該點的橫坐標(biāo)，y表示該點的縱坐標(biāo)，direction表示該點的方向。
代碼實現(xiàn)：?
#include <stdio.h>
#include <stdlib.h>
#define MAXSIZE 10
//定義迷宮
int arr[MAXSIZE][MAXSIZE] = {
1,1,1,1,1,1,1,1,1,1,
1,0,0,1,1,1,1,1,1,1,
1,1,0,1,0,0,0,0,1,1,
1,1,0,1,0,1,1,0,1,1,
1,1,0,0,0,1,1,0,1,1,
1,1,0,1,0,1,1,0,1,1,
1,1,0,1,0,1,1,0,1,1,
1,1,0,1,0,1,1,0,1,1,
1,1,0,0,0,0,1,0,2,1,
1,1,1,1,1,1,1,1,1,1
};
//行走過的標(biāo)志
int arr_tar[MAXSIZE][MAXSIZE] = {0};
//棧的數(shù)據(jù)域
typedef struct Stack
{
int x;
int y;
int direction;
}Stack;
//順序棧
typedef struct SqStack
{
Stack* base;
int top;
}SqStack;
//初始化
void InitStack(SqStack* stack)
{
stack->base = (Stack*)malloc(MAXSIZE * MAXSIZE * sizeof(Stack));
stack->top = 0;
}
//入棧
void InsertStack(SqStack* stack, Stack data)
{
stack->base[stack->top] = data;
stack->top++;
printf("arr[%d][%d]成功入棧！\n", data.x, data.y);
}
//出棧
Stack PopStack(SqStack* stack)
{
stack->top--;
printf("arr[%d][%d]成功出棧！\n", stack->base[stack->top].x, stack->base[stack->top].y);
return stack->base[stack->top];
}
//判棧空
int StackEmpty(SqStack* stack)
{
if (stack->top == 0)
{
return 1;
}
else
{
return 0;
}
}
//取棧頂元素
Stack GetTop(SqStack* stack)
{
int q = stack->top - 1;
return stack->base[q];
}
//判斷該位置是否為墻和之前是否經(jīng)過
int CanPass(Stack data)
{
if (arr[data.x][data.y] == 1 || arr_tar[data.x][data.y] == 1)
{
return 1;
}
else
{
return 0;
}
}
//判斷該位置是否為出口
int IsEnd(Stack data)
{
if (arr[data.x][data.y] == 2)
{
printf("發(fā)現(xiàn)出口?。?！\n");
return 1;
}
else
{
return 0;
}
}
//移動
void move(SqStack* stack)
{
Stack data = GetTop(stack);
Stack new_data;
if (data.direction == 1)//東
{
printf("向東走了一格\n");
new_data.direction = 1;
new_data.x = data.x;
new_data.y = data.y + 1;
}
else if (data.direction == 2)//南
{
printf("向南走了一格\n");
new_data.direction = 1;
new_data.x = data.x + 1;
new_data.y = data.y;
}
else if (data.direction == 3)//西
{
printf("向西走了一格\n");
new_data.direction = 1;
new_data.x = data.x;
new_data.y = data.y - 1;
}
else if (data.direction == 4)//北
{
printf("向北走了一格\n");
new_data.direction = 1;
new_data.x = data.x - 1;
new_data.y = data.y;
}
InsertStack(stack, new_data);
}
//更新走過的路徑
void AddPath(Stack data)
{
arr_tar[data.x][data.y] = 1;
}
void PopPath(Stack data)
{
arr_tar[data.x][data.y] = 0;
}
int main()
{
SqStack* stack = (SqStack*)malloc(sizeof(SqStack));
//遍歷迷宮
int i, j;
for (i = 0;i < MAXSIZE; i++)
{
for (j = 0;j < MAXSIZE; j++)
{
printf("%d\t", arr[i][j]);
}
printf("\n");
}
printf("--------------------破譯中--------------------\n");
//初始化
InitStack(stack);
//設(shè)置初始點
int x = 1, y = 1;
Stack data = {x, y, 1};
InsertStack(stack, data);
do
{
if(!CanPass(GetTop(stack)))//不是墻并且從未走過
{
if (IsEnd(GetTop(stack)))//檢測出口
{
break;
}
else
{
AddPath(GetTop(stack));
move(stack);//添加下一個塊到棧中
}
}
else//是墻
{
PopStack(stack);
PopPath(GetTop(stack));//棧頂元素的路徑不算入經(jīng)過地點
if (!StackEmpty(stack))
{
if (GetTop(stack).direction == 4 && !StackEmpty(stack))
{
AddPath(GetTop(stack));
PopStack(stack);
PopPath(GetTop(stack));
}
if (GetTop(stack).direction < 4)
{
//更新棧頂坐標(biāo)的方向
stack->base[stack->top - 1].direction++;
}
}
}
//getchar();
}while(!StackEmpty(stack));
printf("--------------------破譯完畢--------------------\n");
//輸出結(jié)果
while (!StackEmpty(stack))
{
data = PopStack(stack);
arr[data.x][data.y] = 3;
}
//遍歷迷宮
for (i = 0;i < MAXSIZE; i++)
{
for (j = 0;j < MAXSIZE; j++)
{
printf("%d\t", arr[i][j]);
}
printf("\n");
}
return 0;
} 歡迎大家留言交流
結(jié)語：這不僅僅是一個算法，你把他加點功能（增刪改查），他就變成了期末的課程設(shè)計。文章來源：http://www.zghlxwxcb.cn/news/detail-473130.html
文章來源地址http://www.zghlxwxcb.cn/news/detail-473130.html
到了這里，關(guān)于【數(shù)據(jù)結(jié)構(gòu) 迷宮問題求解】棧的應(yīng)用|c語言|迷宮問題的文章就介紹完了。如果您還想了解更多內(nèi)容，請在右上角搜索TOY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！
