迷宫问题（栈与队列）
时间： 1ms 内存：128M
描述：
编写一个求解迷宫问题的程序，要求输出迷宫的所有路径，并求最短路径长度及最短路径。
规定：
S：迷宫的入口
D：迷宫的出口
X：障碍物，无法从这里通过
*：空地
搜索顺序优先度：↑、→、↓、←
输入：
输入的第一行包含一个数字n，接下来的n行输入一个n*n的迷宫地图。
输出：
输出迷宫的所有路径,每一种路径占一行。最后输出所有路径中最长路径和最短路径的长度。
示例输入：
6
XXXXXX
XS**XX
X*X**X
X***XX
XX**DX
XXXXXX示例输出：
→→↓↓↓→
→→↓↓←↓→→
↓↓→→↓→
↓↓→↓→→
8 6提示：
参考答案（内存最优[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;
}参考答案（时间最优[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;
}题目和答案均来自于互联网，仅供参考，如有问题请联系管理员修改或删除。