内存:128  时间:1

题目描述

编写一个求解迷宫问题的程序,要求输出迷宫的所有路径,并求最短路径长度及最短路径。

 

规定:

S:迷宫的入口

D:迷宫的出口

X:障碍物,无法从这里通过

*:空地

 

搜索顺序优先度:↑、→、↓、←

输入

输入的第一行包含一个数字n,接下来的n行输入一个n*n的迷宫地图。

输出

输出迷宫的所有路径,每一种路径占一行。最后输出所有路径中最长路径和最短路径的长度。

样例输入

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

样例输出

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

提示

1、使用栈求解

2、搜索顺序优先度:↑、→、↓、←

3、若没有路径可以走出迷宫,则输出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
",maxx,minn);  
    return 0;  
}

代码来源于互联网,仅供参考!