ni1.cpp

经典的迷宫算法

#include<iostream>
#include<stack>
#include<malloc.h>
using namespace std;
struct SHAGUO
{
    int x;
    int y;    
};
int **array;
int outx=0,outy=0;//出口坐标
stack<SHAGUO>shaguo;
void Creat(int sum)
{
    int i,j;
    array=(int **)malloc((sum+2)*sizeof(int *));
    for( i=0;i<=sum+1;i++)
        array[i]=(int *)malloc((sum+2)*sizeof(int));
    i=0;/*下面把迷宫四周设成墙   ,0 代表墙，1代表路*/
    for(j=0;j<=sum+1;j++)
    {
        array[i][j]=0;
        array[j][i]=0;
    }
    i=sum+1;
    for(j=0;j<=sum+1;j++)
    {
        array[i][j]=0;
        array[j][i]=0;
    }
    cout<<"请输入迷宫，0代表墙，1代表路,3代表出口,入口默认为(1,1)"<<endl;
    
    for(i=1;i<=sum;i++)
        for(j=1;j<=sum;j++)
            cin>>array[i][j];            
    for(i=1;i<=sum;i++)
        for(j=1;j<=sum;j++)
        {
            if(array[i][j]==3)
            {
                outx=i;
                outy=j;
            }
        }
        if(!(outx||outy))
        {
            cout<<"没有出口!程序将采用默认出口( "<<sum<<" , "<<sum<<" )"<<endl;
            outx=sum;
            outy=sum;
            array[sum][sum]=1;

        }
}
void ok(int num)
{
    cout<<endl<<"走出来啦!"<<endl;
    SHAGUO shaguo1;
    int x,y;
    while(!shaguo.empty())
    {
        shaguo1=shaguo.top();
        x=shaguo1.x;
        y=shaguo1.y;
        array[x][y]=4;
        shaguo.pop();
    }
    array[outx][outy]=4;
    for(x=1;x<=num;x++)
    {
        for(y=1;y<=num;y++)
        {
            if(array[x][y]==4)
                cout<<'\1'<<' ';
            else cout<<'*'<<' ';
        }

            cout<<endl;
    }
    system("pause");
    exit(0);
}
void bad()
{
    cout<<endl<<"没有路!"<<endl;
    system("pause");
    exit(0);
}
void go(int num)
{
    SHAGUO shaguo2,shaguo1;
    shaguo2.x=1;
    shaguo2.y=1;
    shaguo.push(shaguo2);
    int X=1,Y=1;
    int come=1;//探索方向
    while(1&&!shaguo.empty())
    {
        shaguo1=shaguo.top();
        X=shaguo1.x;
        Y=shaguo1.y;
        switch(come)
        {
        
        case 1://向下
            {
                
                X=X+1;
                if(array[X][Y]&&array[X][Y]!=2)//不是走下面上来的
                {
                    if(X==outx&&Y==outy)
                        ok(num);
                    shaguo2.x=X;
                    shaguo2.y=Y;
                    array[X][Y]=2;
                    shaguo.push(shaguo2);
                    come=1;
                }
                else 
                {
                    come++;
                }
        
            }break;
        case 2://向右
            {
                Y=Y+1;
                if(array[X][Y]&&array[X][Y]!=2)
                {
                    if(X==outx&&Y==outy)
                        ok(num);
                    shaguo2.x=X;
                    shaguo2.y=Y;
                    shaguo.push(shaguo2);
                    array[X][Y]=2;
                    come=1;
                    
                }
                else
                {                
                    come++;
                }
            }break;
        case 3:
            {
                X=X-1;
                if(array[X][Y]&&array[X][Y]!=2)
                {
                    if(X==outx&&Y==outy)
                        ok(num);
                    shaguo2.x=X;
                    shaguo2.y=Y;
                    shaguo.push(shaguo2);
                    array[X][Y]=2;
                    come=1;
                }
                else
                {
                    come++;
                }
            }break;
            case 4://向右
            {
                Y=Y-1;
                if(array[X][Y]&&array[X][Y]!=2)
                {
                    if(X==outx&&Y==outy)
                        ok(num);
                    shaguo2.x=X;
                    shaguo2.y=Y;
                    shaguo.push(shaguo2);
                    array[X][Y]=2;
                    come=1;
                }
                else
                {
                    come=1;
                    array[X][Y]=0;
                    shaguo.pop();
                    if(!shaguo.empty())
                    {
                       shaguo1=shaguo.top();
                       if(shaguo1.x==1&&shaguo1.y==1)
                        bad();
                    }
                    else bad();
                }

            }break;
        }
    }
    bad();

}
void main()
{    
    cout<<"请输入迷宫大小，只需输入迷宫的维数，8即是8*8的迷宫"<<endl;
    int sum;
    cin>>sum;  
    Creat(sum);
    go(sum);
    
}