栈-----数组存储结构及其操作算法实现-----迷宫求解
//file:mystack.h#ifndef _MYSTACK_H_INCLUDE_#define _MYSTACK_H_INCLUDE_#define N 10002template <typename T>class Stack{public: Stack():stack_top(0) {} void push(T t){s[stack_top++] = t;} void pop(){stack_top--;} T top(){return s[stack_top-1];} bool empty(){return stack_top == 0;}private: int stack_top; T s[N];};#endif // _STACK_H_INCLUDE_//迷宫求解#include <iostream>#include<cstdio>#include "mystack.h"#define maxlen 102using namespace std;int mat[maxlen][maxlen];int dir[4][2]= {{-1,0},{1,0},{0,-1},{0,1}};//移动的方向struct node{ int x,y;};void path(int m,int n){ Stack<node> s; node ol,ne; mat[0][0]=1; ol.x=0,ol.y=0; while(!s.empty()) { s.pop(); } s.push(ol); while(!s.empty()) { ol=s.top(); if(ol.x==m-1&&ol.y==n-1) { break; }//终点 int flag=0; for(int l=0; l<4; l++) { ne.x=ol.x+dir[l][0]; ne.y=ol.y+dir[l][1]; if(ne.x<0||ne.y<0||ne.x>m-1||ne.y>n-1||mat[ne.x][ne.y]!=0) //边界条件判断 {flag++;continue;} if(mat[ne.x][ne.y]==0) { s.push(ne); mat[ne.x][ne.y]=1; } } if(flag==4) s.pop();//四个方向都不行 } node f; Stack<node> s1; while(!s.empty()) { f=s.top(); s1.push(f); s.pop(); }//把原来哪个栈倒过来压入s1中 while(!s1.empty()) { f=s1.top(); printf("(%d,%d)\n",f.x,f.y); s1.pop(); }//倒过来输出}int main(){ int m,n,i,j; cin >> m >> n; for(i=0; i<m; i++) for(j=0; j<n; j++) cin >> mat[i][j]; path(m,n); return 0;}