現在網上各種對于迷宮的求解，版本多的數不勝數。本人小白一枚，貼上自己對迷宮的求解這個小項目，自己寫的。望能幫助一些同樣有困難的人，畢竟我當時費解了好一會兒時間呢。
首先，先標明對于迷宮求解這個項目，首先我提出自己的思路，利用“窮舉求解”的方法（嚴蔚敏老師數據結構一書中提到，一開始不知方法其名。）其實簡單來說就是一條路一條路去試，當然不能隨便試，我的方法是按照從入口出發，順一個方向向前探索，走得通就繼續向前走；否則留下標記沿原路退回并換一個方向繼續探索，直到所有的路都走完為止。還是用棧的先進后出的結構保存一路的路線。代碼用到了棧的順序實現數組格式的結構（對于棧并沒有詳細闡述）。
//調用頭文件#ifndef AFXSTD_H#define AFXSTD_H #include<stdio.h>#include<stdlib.h>#include<malloc.h>#include<iostream>using namespace std; // cout; cin;C++的輸入輸出#endif
//迷宮的結構體的創建#ifndef MAZE_H#define MAZE_H #define ROWSIZE 10 //迷宮大小#define COLSIZE 10#define Reachable 0 //可以到達的結點#define Bar 1 //障礙物#define Foot 2 //足跡#define Mark 3 //不可通路標記typedef int MapType[ROWSIZE][COLSIZE]; // 地圖類型 typedef struct { int row;// x int col;// y;}PosType; //坐標結構體 typedef struct{ int ord; //通道塊在道路上的序號 PosType seat; //小人坐標 int di; // 方向 // 1 2 3 4}MElemType; //試迷宮小人的結構 typedef MElemType SElemType; // 和stack 關聯 bool MazePass(MapType maze,PosType curpos);void FootPrint(MapType maze,PosType curpos); //足跡打印PosType NextPos(PosType curpos,int di); //下一個位置void MarkPrint(MapType maze,PosType curpos); //打印不可通標記bool MazePath(MapType maze,PosType start,PosType end); //迷宮解謎核心void PrintMap(MapType maze); //打印地圖 #endif//棧的結構體#include"Maze.h"#ifndef SEQSTACK_H#define SEQSTACK_H#define STACKSIZE 100 //typedef int SElemType; struct SeqStack{ SElemType *data; int maxsize; int top;}; void Init_Stack(SeqStack &st);void Destroy_Stack(SeqStack &st);void Stack_Clear(SeqStack &st);bool Stack_Empty(SeqStack &st);bool Stack_Full(SeqStack &st);int Stack_Size(SeqStack &st);bool Stack_Push(SeqStack &st,const SElemType &x);bool Stack_Pop(SeqStack &st, SElemType &x); SElemType GetTop(SeqStack &st);void Pop(SeqStack &st); #endif以上是頭文件的創建，和結構體的創建，現在真的深切感到結構體的重要性。結構體創建不好就是自己給自己挖坑，切記切記！！
現在貼出函數的代碼，解釋我會盡力都寫清楚。（棧的問題我后續會重新再仔細闡述的，這次的重點在于迷宮的求解，所以直接貼出棧的詳細代碼，望諒解。）
//這里是棧的實現代碼#include"AfxStd.h"#include"Stack.h" bool Stack_Resize(SeqStack &st){ SElemType *s = (SElemType*)malloc(sizeof(SElemType)*st.maxsize * 2); if(NULL == s) return false; for(int i = 0;i<= st.top;++i) { s[i] = st.data[i]; } free(st.data); st.data = s; st.maxsize = st.maxsize * 2; return true;}void Init_Stack(SeqStack &st){ st.maxsize = STACKSIZE; st.top = -1; st.data = (SElemType*)malloc(sizeof(SElemType)*st.maxsize); if(NULL == st.data) { exit(0); }}void Destroy_Stack(SeqStack &st){ free(st.data); st.data = NULL; st.maxsize = 0; st.top = -1;} void Stack_Clear(SeqStack &st){ st.top = -1;}bool Stack_Empty(SeqStack &st){ return Stack_Size(st) == 0;}bool Stack_Full(SeqStack &st){ return Stack_Size(st) == st.maxsize;} int Stack_Size(SeqStack &st){ return st.top + 1;} bool Stack_Push(SeqStack &st,const SElemType &x){ if(Stack_Full(st) && ! Stack_Resize(st)) { return false; } st.data[++st.top] = x; return true;}bool Stack_Pop(SeqStack &st, SElemType &x){ if(Stack_Empty(st)) { return false; } x = st.data[st.top--]; return true;}//調用前面創建的頭文件#include"AfxStd.h"#include"Maze.h"#include"Stack.h" ///////////////////////////////////////////////// bool MazePass(MapType maze,PosType curpos) //判斷是否可以通過{ return maze[curpos.row][curpos.col] == Reachable; //判斷當前結點是否能通過}void FootPrint(MapType maze,PosType curpos) //打印足跡 { maze[curpos.row][curpos.col] = Foot; }PosType NextPos(PosType curpos,int di) //對下一個結點方向的判斷{ switch(di) { case 1: curpos.row+=1; break;// 1 case 2: curpos.col-=1; break;// 2 case 3: curpos.row-=1; break;// 3 case 4: curpos.col+=1; break;// 4 } return curpos;}void MarkPrint(MapType maze,PosType curpos) //不能通過的結點留下不能通過的標記{ maze[curpos.row][curpos.col] = Mark;} bool MazePath(MapType maze,PosType start,PosType end)//（核心）迷宮解謎{ bool res = false; //定義一個res參數為布爾型 PosType curpos = start; //初始當前位置為入口 int curstep = 1; // 初始探索方向為1 SeqStack st; //路徑存儲棧 MElemType e; //初始探索小人 Init_Stack(st); //初始化棧 do{ if(MazePass(maze,curpos)) //當前位置可通過，即是未曾走到過的坐標 { FootPrint(maze,curpos); //留下足跡 e.di = 1, e.seat = curpos,e.ord = curstep++; Stack_Push(st,e); //加入路徑中 if(curpos.row == end.row && curpos.col == end.col) { res = true; break; } //到達終點 curpos = NextPos(curpos,1); //探索下一位置 } else { if(!Stack_Empty(st)) //當前位置不能通過 { Stack_Pop(st,e); while(e.di == 4 && !Stack_Empty(st)) { MarkPrint(maze,e.seat); Stack_Pop(st,e); // 留下不能通過的標記，并退回一步 } if(e.di < 4) { e.di+=1; // 換下一個方向探索 Stack_Push(st,e); //再次記錄路徑 curpos = NextPos(e.seat,e.di); // 當前位置設為新方向的相鄰塊 } } } }while(!Stack_Empty(st)); //當?？沾輾＃祷厥?Destroy_Stack(st); return res;}void PrintMap(MapType maze) //打印地圖{ for(int i = 0;i<ROWSIZE;++i) { for(int j = 0;j<COLSIZE;++j) { printf("%2d",maze[i][j]); } printf("/n"); } printf("/n");}以上就是迷宮的詳細解釋，希望能幫助到大家。后面再添加我的測試文件。
#include"AfxStd.h"#include"Maze.h" int main(){ MapType maze ={ //一開始地圖的創建 {1,1,1,1,1,1,1,1,1,1}, {1,0,1,1,1,1,1,1,1,1}, {1,0,0,0,0,0,0,0,0,1}, {1,0,0,0,1,1,1,1,0,1}, {1,0,0,0,1,1,1,1,0,1}, {1,0,1,1,1,1,0,0,0,1}, {1,0,1,1,1,1,1,1,1,1}, {1,0,0,0,0,0,0,1,1,1}, {1,0,1,1,1,1,0,0,0,1}, {1,1,1,1,1,1,1,1,1,1}, }; PosType start={1,1},end={8,8}; PrintMap(maze); //打印初始地圖 MazePath(maze,start,end); PrintMap(maze); //打印迷宮解法 return 0;}以上就是本文的全部內容，希望對大家的學習有所幫助，也希望大家多多支持武林網。
新聞熱點
疑難解答
圖片精選
