//==================================迷宫问题（又称电路板问题)===============================
#include<iomanip.h>
#include<fstream.h>
//=========================================类声明==============================
template <class T> class queue;
template <class T>
class node
{
    friend class queue<T> ;
    private:
        T data;
        node<T>  * next;
};
//----------
template <class T>
class queue
{
    public:
        queue(){front=rear=NULL;}
        ~queue();
        void enqueue(T a);
        bool dequeue(T& savedeq);
        bool empty();
        
    private:
        node<T> * front;
        node<T> * rear;
};
//----------
class position
{
public:
    int row;
    int col;
};
//==============================================类函数声明=================================
template<class T>
queue<T>::~queue()
{
    node<T>* p;
    for(int i=0;front;i++)
    {
        p=front;
        front=front->next;
        delete p;
    }
}
//----------
template<class T>
bool queue<T>::empty()
{
    return front==NULL;
}
//----------
template<class T>
void queue<T>::enqueue(T a)
{
    node<T> * p=new node<T>;
    p->data=a;
    p->next=NULL;
    if(front==NULL&&rear==NULL)
    {
        rear=front=p;
    }
    else
    {
        rear->next=p;
        rear=p;
    }
}
//----------
template<class T>
bool queue<T>::dequeue(T& savedeq)
{
    if(front==NULL&&rear==NULL)
        return 0;
    node<T> * p=front;
    front=front->next;
    savedeq=p->data;
    if(front==NULL)
        rear=NULL;
    delete p;
    return 1;
}
//============================================主程序====================================
void main()
{
    //-------------------------------------初始化迷宫--------------------------------
    
    cout<<"请在文本中输入迷宫方阵.（障碍物用x表示，可通行路径用0表示满意）每行结尾用'.'标识"<<endl;
    cout<<"结束后按任意键继续："<<endl;
    char wait;
    cin>>wait;
lb: ifstream fin1,fin2;                                                //对象声明
    cout<<"输入文件路径:";                                             //文件路径指定
    char * road=new char [30];
    cin>>road;
    fin1.open(road,ios::in|ios::out|ios::nocreate);                    //打开文件
    if(!fin1)                                                          //文件不存在处理
    {
        cout<<"无此文件"<<endl;
        fin1.close();
        goto lb;
    }
    char g;
    int han=0,lie=0;
    while(fin1>>g)
    {
        if(g=='.')
            ++han;
        if(han==0)
            lie++;
    }
    fin1.close();
    fin2.open(road);
    int ** p=new int* [han+2];
    for(int i=0;i<=han+1;i++)
        p[i]=new int[lie+2];
    
    for(i=0;i<=han+1;i++)
    {
        p[i][0]=-1;
        p[i][lie+1]=-1;
    }
    for(int j=0;j<=lie+1;j++)
    {
        p[0][j]=-1;
        p[han+1][j]=-1;
    }
    for(i=1;i<=han;i++)
        for(j=1;j<=lie+1;j++)
            if(fin2>>g&&g!='.')
            {
                if(g=='0')
                p[i][j]=0;
                if(g=='x')
                p[i][j]=-1;
                
            }
    fin2.close();
    cout<<endl;
    cout<<"你输入的迷宫是："<<endl;
    cout<<endl;
    for(i=1;i<=han;i++)
    {
        for(j=1;j<=lie;j++)
            cout<<setw(3)<<p[i][j];
        cout<<endl;
        cout<<endl;
    }
    //----------
    int h1,l1,h2,l2;                                                   // 入口出口设置
    cout<<"入口的行:";
    cin>>h1;
    cout<<"入口的列:";
    cin>>l1;
    cout<<"出口的行:";
    cin>>h2;
    cout<<"出口的列:";
    cin>>l2;
    position start,finish;
    start.row=h1;
    start.col=l1;
    finish.row=h2;
    finish.col=l2;
    //----------
    position offset[4];                                                //辅助移动对象
    offset[0].row=0;
    offset[0].col=1;
    offset[1].row=1;
    offset[1].col=0;
    offset[2].row=0;
    offset[2].col=-1;
    offset[3].row=-1;
    offset[3].col=0;
    //----------
    int length;                                                        //变量声明
    position here,nb;
    //----------
    here.row=start.row;                                                //寻找出口程序
    here.col=start.col;
    queue<position> assist;
    while(true)
    {
        for(i=0;i<4;i++)
        {
            nb.row=here.row+offset[i].row;
            nb.col=here.col+offset[i].col;
            if(p[nb.row][nb.col]==0)
            {
                p[nb.row][nb.col]=p[here.row][here.col]+1;
                if(nb.row==finish.row&&nb.col==finish.col)
                    break;
                assist.enqueue(nb);
            }
        }
        if(nb.row==finish.row&&nb.col==finish.col)
        break;
        if(assist.empty())
        {
            cout<<"不存在通往出口的路"<<endl;
            char x;
            cin>>x;
            return;
        }
        assist.dequeue(here);
    }
    //----------
    length=p[finish.row][finish.col];                                  //回溯入口
    cout<<endl;
    cout<<"出口到入口的长度是"<<length<<endl;
    here.row=finish.row;
    here.col=finish.col;

    for(i=length;i>=2;i--)
    {
        for(j=0;j<4;j++)
        {
            nb.row=here.row+offset[j].row;
            nb.col=here.col+offset[j].col;
            if(p[nb.row][nb.col]==i-1)
                break;
        }
        p[nb.row][nb.col]=-2;
        here.row=nb.row;
        here.col=nb.col;
    
    }
    //-----------
    char ** result=new char* [han+2];                                  //二维数组转字符型
    for(i=0;i<=han+1;i++)
        result[i]=new char[lie+2];
    for(i=1;i<=han;i++)                 
    {
        for(j=1;j<=lie;j++)
        {
            if(p[i][j]==-2)
                result[i][j]='*';
            else
                if(i==h1&&j==l1)
                result[i][j]='a';
                else
                    if(i==h2&&j==l2)
                    result[i][j]='z';
                    else
                        if(p[i][j]==-1)
                            result[i][j]='#';
                        else
                            result[i][j]='_';
        }
    }
    //-----------
    ofstream fout;                                                     //迷宫输出到文本中
    fout.open(road,ios::app);
    fout<<endl;
    fout<<"以下是迷宫路线："<<endl;
    fout<<endl;
    for(i=1;i<=han;i++)               
    {
        for(j=1;j<=lie;j++)
            fout<<setw(3)<<result[i][j];
        fout<<endl;
        fout<<endl;
    }
    fout<<"(入口 a 出口 z 路径 * 可通行路径 _ 障碍物 #)"<<endl;
    fout.close();
    cout<<endl;
    cout<<"结果已保存到"<<road<<endl;
    char z;
    cin>>z;
}









    


[em3]