Question

请问c++迷宫问题怎么解

请高手写个关于BFS求解迷宫问题的代码，就是给一个矩阵m为入口，n为出口，问能不能从迷宫出去。要有注释，网上的很多都没注释，看不懂。可以用stl，语言简洁，太复杂看不懂。写得好再加分。

Answer 1

#include<iostream.h>  
#include<iomanip.h>  
#define M 11  
#define N 10  
//默认迷宫结构  
char maze_array[M][N]=  
            {  
                {1,1,1,1,1,1,1,1,1,1},  
                {0,0,0,1,0,0,0,1,0,1},  
                {1,0,0,1,0,0,0,1,0,1},  
                {1,0,0,1,0,1,1,0,1,1},  
                {1,0,1,1,1,0,0,1,0,1},  
                {1,0,0,0,1,0,0,0,0,1},  
                {1,0,1,0,0,0,1,0,1,1},  
                {1,0,1,1,1,1,0,0,1,1},  
                {1,1,1,0,0,0,1,0,1,1},  
                {1,1,1,0,0,0,0,0,0,0},  
                {1,1,1,1,1,1,1,1,1,1}  
            };  
//记录迷宫结点的路过次数  
int maze_node_passby_array[M][N]=  
            {  
                {0,0,0,0,0,0,0,0,0,0},  
                {0,0,0,0,0,0,0,0,0,0},  
                {0,0,0,0,0,0,0,0,0,0},  
                {0,0,0,0,0,0,0,0,0,0},  
                {0,0,0,0,0,0,0,0,0,0},  
                {0,0,0,0,0,0,0,0,0,0},  
                {0,0,0,0,0,0,0,0,0,0},  
                {0,0,0,0,0,0,0,0,0,0},  
                {0,0,0,0,0,0,0,0,0,0},  
                {0,0,0,0,0,0,0,0,0,0},  
                {0,0,0,0,0,0,0,0,0,0}  
            };  
  
//输出当前的迷宫局势  
void print_maze();  
//输出记录路径结点出现次数的数组  
void print_maze_node_passby_array();  
  
  
//路径结点类  
class Maze_Path_Node  
    {  
private:  
        int i;  
        int j;  
        int path_direction;  
        int number;  
public:  
    Maze_Path_Node(int m=0,int n=0,int direct=0,int c=1)//构造函数  
    {  
        i=m;  
        j=n;  
        path_direction=direct;  
        number=c;  
    }  
    Maze_Path_Node(Maze_Path_Node& t)//拷贝构造函数  
    {  
        i=t.get_i();  
        j=t.get_j();  
        path_direction=t.get_path_direction();  
        number=t.get_number();  
    }  
    ~Maze_Path_Node()                       //析构函数  
    {  
    }  
  
    bool operator!=(Maze_Path_Node& t)  
    {  
        if(i==t.get_i()&&j==t.get_j())//&&path_direction==t.get_path_direction()&&maze_node_passby_array[(*this).get_i()][(*this).get_j()]==maze_node_passby_array[t.get_i()][t.get_j()]  
            return 0;  
        else  
            return 1;  
    }  
    Maze_Path_Node& operator=(Maze_Path_Node& t)  
    {  
        if(this!=&t)  
        {  
            i=t.get_i();  
            j=t.get_j();  
            path_direction=t.get_path_direction();  
            number=t.get_number();  
        }  
        return *this;  
    }  
      
    void print_maze_path_node()  
    {  
        cout<<"("<<get_i()<<","  
            <<get_j()<<","  
            <<get_path_direction()  
            <<","  
            <<maze_node_passby_array[get_i()][get_j()]<<")"<<endl<<endl;  
    }  
  
    int get_i(){return i;}  
    int get_j(){return j;}  
    int get_number(){return number;}  
    int get_path_direction(){return path_direction;}  
  
    };  
  
//入口和出口坐标  
Maze_Path_Node maze_entrance(1,0,0);  
Maze_Path_Node maze_exit(9,9,0);   
  
//路径类  
class Maze_Path  
{  
private:  
  
    Maze_Path_Node maze_path[M*N];          //路径  
                              
    int m,n;                                //路径结点的行列坐标  
    int direction;                          //默认路径的前进方向  
    int maze_path_length;                   //路径长度  
  
public:  
    Maze_Path()//  
    {  
        m=maze_entrance.get_i();  
        n=maze_entrance.get_j();  
        direction=get_next_direction();  
        maze_path_length=0;  
        //maze_node_passby_array[maze_entrance.get_i()][maze_entrance.get_j()]=1;  
    }  
    ~Maze_Path(){}  
  
  
    //返回路径长度  
    int get_maze_path_length(){return maze_path_length;}  
  
    //打印路径  
    void print_maze_path();  
  
    //把路径节点存入一维数组中！  
    void push_maze_path_node(Maze_Path_Node m);  
  
    //判断路径是否有回路  
    int is_back();  
  
    //找到下一位置，并且设置为2，重置全局变量direction！  
    void one_more_step();  
  
    //计算得到路径  
    void get_maze_path();  
  
    //简化路径  
    void sim_maze_path();  
  
    //计算出在此结点基础上，下一步移动方向  
    int get_next_direction();  
  
  
    //删除重复路径  
    void delete_useless_path(int i,int m)  
    {  
        int count_i,count_m;  
        for(count_i=i,count_m=m;count_m<=maze_path_length;count_i++,count_m++)  
        {  
            maze_path[count_i]=maze_path[count_m];  
            maze_node_passby_array[maze_path[count_i].get_i()][maze_path[count_i].get_j()]--;  
            if(maze_node_passby_array[maze_path[count_i].get_i()][maze_path[count_i].get_j()]==0)  
                maze_array[maze_path[count_i].get_i()][maze_path[count_i].get_j()]=0;  
        }  
  
        maze_path_length=maze_path_length-(m-i);  
        cout<<endl<<"abcdefghijklmnopqrstuvwxyz"<<endl;  
        print_maze_path();  
        print_maze();  
        print_maze_node_passby_array();  
  
    }