数据结构作业，wsl

主要是搓的有点久。。

详细注释。。我好闲

//迷宫程序：我不太理解书上这个迷宫究竟是怎么输入的。。。
//所以这里用'#'表示围墙，用'.'表示可通路径；用A表示入口，用S表示出口。
//先输入迷宫的规模(m*n)，然后进行具体数据读入，并保证周围一定有围墙
//栈迷宫算法（输出任意路径）
//ps 如果是最短路径的话用队列+bfs会比较好
#include<bits/stdc++.h>
using namespace std;
const int maxn=1e3+7;
bool vis[maxn][maxn];//标记已经经过
char g[maxn][maxn];//存图
int m,n;
int dx[]={1,0,-1,0};//下一个节点的x变化
int dy[]={0,1,0,-1};//下一个节点的y变化
struct Stack{
    int x;
    int y;
}S[maxn];
int top=0;
void init(){//初始化，栈顶为0，vis全设为false，清空图
    top=0;
    memset(vis,false,sizeof(vis));
    memset(g,0,sizeof(g));
}
void Push(int x,int y){//入栈
    S[top].x=x;
    S[top].y=y;
    top++;
}
void Pop(){//出栈
    top--;
}
void Top(int &x,int &y){//取栈顶元素
    if(top==0) return;
    x=S[top-1].x;
    y=S[top-1].y;
}
bool Empty(){//判断栈是否为空
    if(top) return false;
    else return true;
}
void solve(){
    int x,y;
    while(!Empty()){
        Top(x,y);//栈顶元素出栈
        bool fl=true;
        int nx=x+dx[0],ny=y+dy[0];//向dx，dy方向移动
        int cnt=0;
        while(g[nx][ny]=='#'||vis[nx][ny]||nx<0||ny<0||nx>=m||ny>=n){//走不动
            cnt++;
            if(cnt>3){//cnt>3说明四个方向都不通
                Pop();//栈顶元素出栈，这个节点无路可走
                fl=false;
                break;
            }
            nx=x+dx[cnt];ny=y+dy[cnt];//换个方向在走
        }
        if(!fl) continue;//和第52行相关，如果这个节点都不能走，那么再取新的栈顶进行新的循环
        Push(nx,ny);//新的节点入栈
        vis[nx][ny]=true;//标记经过
        if(g[nx][ny]=='S'){//如果此节点为终点，输出栈中所有元素
//            while(!Empty()){//这是一个倒序输出
//                int i,j;
//                Top(i,j);
//                cout<<i<<' '<<j<<endl;
//                Pop();
//            }
            for(int i=0;i<top;i++){
                cout<<S[i].x<<' '<<S[i].y<<endl;
            }//比较作弊的方法正序输出经过的每个结点
        }
    }
}
int main(){
    init();
    int ax,ay;
    cin>>m>>n;//m行n列
    for(int i=0;i<m;i++){//存图，并记录起点位置
        for(int j=0;j<n;j++){
           char c;cin>>c;
            g[i][j]=c;
           if(c=='A') {ax=i;ay=j;}//记录起点位置
        }
    }
    Push(ax,ay);//起点先入栈
    vis[ax][ay]=true;//标记经过起点
    solve();
}