利用栈的特性求解迷宫路径

  1 #include <bits/stdc++.h>
  2 using namespace std;
  3 #define MAXSIZE 1000
  4 //迷宫地图
  5 int mg[10][10] = {
  6                 {1, 1, 1, 1, 1, 1, 1, 1, 1, 1},
  7                 {1, 0, 0, 1, 0, 0, 0, 1, 0, 1},
  8                 {1, 0, 0, 1, 0, 0, 0, 1, 0, 1},
  9                 {1, 0, 0, 0, 0, 1, 1, 0, 0, 1},
 10                 {1, 0, 1, 1, 1, 0, 0, 0, 0, 1},
 11                 {1, 0, 0, 0, 1, 0, 0, 0, 0, 1},
 12                 {1, 0, 1, 0, 0, 0, 1, 0, 0, 1},
 13                 {1, 0, 1, 1, 1, 0, 1, 1, 0, 1},
 14                 {1, 1, 0, 0, 0, 0, 0, 0, 0, 1},
 15                 {1, 1, 1, 1, 1, 1, 1, 1, 1, 1}
 16 };
 17 //迷宫方块的存储结构
 18 struct Box {
 19     int i;
 20     int j;
 21     int di;
 22 };
 23 //存储路径的栈的存储结构
 24 struct Stack {
 25     Box *data;
 26     int top;
 27 };
 28 //初始化栈
 29 void Init(Stack &S) {
 30     S.data = new Box[MAXSIZE];
 31     S.top = -1;
 32 }
 33 //将元素入栈
 34 bool Push(Stack &S, Box e) {
 35     if (S.top == MAXSIZE - 1) {
 36         return false;
 37     }
 38     else {
 39         S.data[++S.top] = e;
 40         return true;
 41     }
 42 }
 43 //将元素出栈
 44 bool Pop(Stack &S, Box &e) {
 45     if (S.top == -1) {
 46         return false;
 47     }
 48     else {
 49         e = S.data[S.top--];
 50         return true;
 51     }
 52 }
 53 //得到栈顶元素
 54 Box GetTop(Stack &S) {
 55     return S.data[S.top];
 56 }
 57 //判断栈是否为空
 58 bool Empty(Stack &S) {
 59     return S.top == -1;
 60 }
 61 void OutPut(Stack &S) {
 62     Box e;
 63     while (!Empty(S)) {
 64         Pop(S, e);
 65         cout << "(" << e.i << "," << e.j << ")" << endl;
 66 
 67     }
 68 }
 69 //利用栈的路径来求迷宫路径
 70 bool mgpath(int xi, int yi, int xe, int ye) {
 71     Box e;
 72     int i, j, il, jl, di;
 73     bool find;
 74     Stack S;
 75     Init(S);
 76     e.i = xi;
 77     e.j = yi;
 78     e.di = -1;
 79     mg[xi][yi] = -1;
 80     Push(S, e);
 81     while (!Empty(S)) {
 82         e = GetTop(S);
 83         i = e.i;
 84         j = e.j;
 85         di = e.di;
 86         if (i == xe && j == ye) {
 87             OutPut(S);
 88             return true;
 89         }
 90         find = false;
 91         while (di < 4 && !find) {
 92             di++;
 93             switch (di) {
 94             case 0: {il = i - 1; jl = j; break; }
 95             case 1: {il = i; jl = j + 1; break; }
 96             case 2: {il = i + 1; jl = j; break; }
 97             case 3: {il = i; jl = j - 1; break; }
 98             }
 99             if (mg[il][jl] == 0) { find = true; }
100         }
101         if (find) {
102             S.data[S.top].di = di;
103             e.i = il;
104             e.j = jl;
105             e.di = -1;
106             Push(S, e);
107             mg[il][jl] = -1;
108         }
109         else {
110             Pop(S, e);
111             mg[e.i][e.j] = 0;
112         }
113     }
114     return false;
115 }
116 int main() {
117     mgpath(1, 1, 8, 8);
118     return 0;
119 }