# 迷宫问题（栈与队列）

S：迷宫的入口

D：迷宫的出口

X：障碍物，无法从这里通过

*：空地

``````6
XXXXXX
XS**XX
X*X**X
X***XX
XX**DX
XXXXXX``````

``````→→↓↓↓→
→→↓↓←↓→→
↓↓→→↓→
↓↓→↓→→
8 6``````

``````#include<stdio.h>
#include<iostream>
#include<algorithm>
#include<string.h>
#define SizeMax 105
using namespace std;
int n,maxx=0,minn=0xffff;
char a[10][10];
typedef struct
{
char data[SizeMax][5];
int top;
} SqStack;
SqStack *s=(SqStack*)malloc(sizeof(SqStack));
void push(SqStack *&s,string k)                 //入栈
{
char *e=(char*)k.data();                    //将string类型转换成char*
if(s->top==SizeMax-1)return;
s->top++;
strcpy(s->data[s->top],e);                  //入栈
}
void print(SqStack *s)                          //输出
{
for(int i=0; i<=s->top; i++)
cout<<s->data[i];
cout<<endl;
}
void dfs(int x,int y,int k)                     //深度优先扫描
{
if(a[x][y]=='D')
{
maxx=maxx<k?k:maxx;                     //最大值
minn=minn>k?k:minn;                     //最小值
print(s);
return;
}a[x][y]='X';                               //走过的路用‘X’填充，防止出现重复路线
for(int i=0; i<4; i++)
{
if(i==0){if(a[x-1][y]!='X'&&x-1>=0)push(s,"↑"),dfs(x-1,y,k+1),s->top--;}        //向上
else if(i==1){if(a[x][y+1]!='X'&&y+1<n)push(s,"→"),dfs(x,y+1,k+1),s->top--;}    //向右
else if(i==2){if(a[x+1][y]!='X'&&x+1<n)push(s,"↓"),dfs(x+1,y,k+1),s->top--;}    //向下
else if(i==3){if(a[x][y-1]!='X'&&y-1>=0)push(s,"←"),dfs(x,y-1,k+1),s->top--;}   //向左
}a[x][y]='*';                               //回溯结束后解开被填充的路口
}
int main()
{
cin>>n;
for(int i=0; i<n; i++)
scanf("%s%*c",a[i]);
s->top=-1;
int x,y;
for(int i=0; i<n; i++)
for(int j=0; j<n; j++)
if(a[i][j]=='S')                    //确定‘S’的位置
{
x=i,y=j;
goto end1;
}
end1:
dfs(x,y,0);
if(maxx==0)minn=0;
printf("%d %d\n",maxx,minn);
return 0;
}``````

``````#include<stdio.h>
#include<iostream>
#include<algorithm>
#include<string.h>
#define SizeMax 105
using namespace std;
int n,maxx=0,minn=0xffff;
char a[10][10];
typedef struct
{
char data[SizeMax][5];
int top;
} SqStack;
SqStack *s=(SqStack*)malloc(sizeof(SqStack));
void push(SqStack *&s,string k)                 //入栈
{
char *e=(char*)k.data();                    //将string类型转换成char*
if(s->top==SizeMax-1)return;
s->top++;
strcpy(s->data[s->top],e);                  //入栈
}
void print(SqStack *s)                          //输出
{
for(int i=0; i<=s->top; i++)
cout<<s->data[i];
cout<<endl;
}
void dfs(int x,int y,int k)                     //深度优先扫描
{
if(a[x][y]=='D')
{
maxx=maxx<k?k:maxx;                     //最大值
minn=minn>k?k:minn;                     //最小值
print(s);
return;
}a[x][y]='X';                               //走过的路用‘X’填充，防止出现重复路线
for(int i=0; i<4; i++)
{
if(i==0){if(a[x-1][y]!='X'&&x-1>=0)push(s,"↑"),dfs(x-1,y,k+1),s->top--;}        //向上
else if(i==1){if(a[x][y+1]!='X'&&y+1<n)push(s,"→"),dfs(x,y+1,k+1),s->top--;}    //向右
else if(i==2){if(a[x+1][y]!='X'&&x+1<n)push(s,"↓"),dfs(x+1,y,k+1),s->top--;}    //向下
else if(i==3){if(a[x][y-1]!='X'&&y-1>=0)push(s,"←"),dfs(x,y-1,k+1),s->top--;}   //向左
}a[x][y]='*';                               //回溯结束后解开被填充的路口
}
int main()
{
cin>>n;
for(int i=0; i<n; i++)
scanf("%s%*c",a[i]);
s->top=-1;
int x,y;
for(int i=0; i<n; i++)
for(int j=0; j<n; j++)
if(a[i][j]=='S')                    //确定‘S’的位置
{
x=i,y=j;
goto end1;
}
end1:
dfs(x,y,0);
if(maxx==0)minn=0;
printf("%d %d\n",maxx,minn);
return 0;
}``````