走迷宫

 

#include<iostream>
using namespace std;

class Maze
{
    struct intersection
    {
        int left;
        int forward;
        int right;
    }* dir;
    int crossing;
    int exit;
public:
    Maze(int x):crossing(x)
    {
        dir=new intersection[x+1];
    }
    friend istream& operator>>(istream& in,Maze m);
    void setExit(int x)
    {
        exit=x;
    }
    int visit(int x)     //只能搜索一条路径             
    {                                            
        if(x>0)
        {
            if(x==exit)                            
            {                                   
                cout<<"postion :"<<x<<endl;
                return 1;
            }
            if(visit(dir[x].left))
            {
                cout<<"postion :"<<x<<endl;
                return 1;
            }
            if(visit(dir[x].forward))
            {
                cout<<"postion :"<<x<<endl;
                return 1;
            }
            if(visit(dir[x].right))
            {
                cout<<"postion :"<<x<<endl;
                return 1;
            }
        }
        return 0;
    }
};

istream& operator>>(istream& in,Maze m)
{
    for(int i=1;i<=m.crossing;i++)
        cin>>m.dir[i].left>>m.dir[i].forward>>m.dir[i].right;
    return in;
}

int main()
{
    int i;
    cout<<"input Maze's scale:";
    cin>>i;
    Maze fancy(i);
    cout<<"input values:";
    cin>>fancy;
    cout<<"input the exit:";
    cin>>i;
    fancy.setExit(i);
    cout<<"input the beginning visit place:";
    cin>>i;
    fancy.visit(i);
    return 0;
}

//input Maze's scale:
//6
//input values:
//0 2 0
//3 5 6
//0 0 4
//0 0 0
//0 0 7
//7 0 0
//input the exit:7
//input the beginning visit place:1

//postion :7
//postion :5
//postion :2
//postion :1

 

通过dfs依次确定从入口到出口的交叉点，逆序打印出路线的每一个交叉点

通过结果可以看出，dfs在多解时的搜索结果的顺序与搜索时的条件限制顺序一致，先向左搜索，然后向前，最后向右搜索，在平面（矩阵）、立体中用dfs、bfs时应用了相同的方法