数据结构—线性实习题目（二）5迷宫问题（栈）

迷宫问题（栈）

#include <iostream>​
#include <assert.h>
using namespace std;int qi1, qi2;
int n;
int m1, p1;
int** Maze = NULL;
int** mark = NULL;struct items
{int x, y, dir;
};struct offsets {int a, b;char* dir;
};const int stackIncreament = 20;
template <class T>
class SeqStack {
public:SeqStack(int sz = 50);~SeqStack() { delete[] elements; }void Push(const T& x);bool Pop(T& x);bool getTop(T& x);bool IsEmpty() const { return (top == -1) ? true : false; }bool IsFull() const { return (top == maxSize - 1) ? true : false; }int getSize() const { return top + 1; }void MakeEmpty() { top = -1; }void print();//friend ostream& operator<<(ostream& os, SeqStack<T>& s) {}
private:T* elements;int top;int maxSize;void overflowProcess();
};template <class T>
SeqStack<T>::SeqStack(int sz) : top(-1), maxSize(sz) {elements = new T[maxSize];assert(elements != NULL);
}template <class T>
void SeqStack<T>::overflowProcess() {T* newArray = new T[maxSize + stackIncreament];if (newArray == NULL) {cerr << "存储分配失败！" << endl;exit(1);}for (int i = 0; i < top; i++) newArray[i] = elements[i];maxSize += stackIncreament;delete[] elements;elements = newArray;
}template <class T>
void SeqStack<T>::Push(const T& x) {if (IsFull() == true) overflowProcess();elements[++top] = x;
}template <class T>
bool SeqStack<T>::Pop(T& x) {if (IsEmpty() == true) return false;x = elements[top--];return true;
}template <class T>
bool SeqStack<T>::getTop(T& x) {if (IsEmpty() == true) return false;x = elements[top];return true;
}template <class T>
void SeqStack<T>::print() {items item;SeqStack<items> temp(n);while (this->IsEmpty() == false) {this->Pop(item);temp.Push(item);}while (temp.IsEmpty() == false) {temp.Pop(item);cout << item.y << " " << item.x << endl;}
}offsets move1[4] = {{1,0,(char*)"N" },{0,-1,(char*)"W"},{-1,0,(char*)"S"},{0,1,(char*)"E"}};void path(int m, int p) {int i, j, d, g, h;mark[qi1][qi2] = 1;SeqStack<items> st(m * p);items tmp;tmp.x = qi1;tmp.y = qi2;tmp.dir = 0;st.Push(tmp);while (st.IsEmpty() == false) {st.Pop(tmp);i = tmp.x;j = tmp.y;d = tmp.dir;while (d < 4) {g = i + move1[d].a;h = j + move1[d].b;if (g == m1 && h == p1) {st.print();cout << j << " " << i << endl;cout << p1 << " " << m1 << endl;return;}if (Maze[g][h] == 0 && mark[g][h] == 0) {mark[g][h] = 1;tmp.x = i;tmp.y = j;tmp.dir = d;st.Push(tmp);i = g; j = h; d = 0;   // 修改}else d++;}}cout << "no path in Maze" << endl;
}
int m = 0, p = 0;
int main() {int i, j, num;cin >> m >> p;n = m * p;int** arr = new int* [p];for (int i = 0; i < p; i++) {arr[i] = new int[m];for (int j = 0; j < m; j++) {cin >> num;if (num == 4) {m1 = i;p1 = j;}if (num == 3) {qi1 = i; qi2 = j;num = 0;}arr[i][j] = num;}}Maze = arr;int** arr2 = new int* [p];for (int i = 0; i < p; i++) {arr2[i] = new int[m];for (int j = 0; j < m; j++) {arr2[i][j] = 0;}}mark = arr2;path(m1, p1);return 0;
}