问题描述：给定一个基本的迷宫图，用一个数组表示，值0表示有路，1表示有障碍物，找一条，从矩阵的左上角，到右下角的短路。求短路，大家先想到的可能是用BFS求，本文也是BFS求短路的。
　　源代码如下：
1 /*
2 使用BFS解决迷宫问题
3
4
5 **/
6 #include<iostream>
7 #include<queue>
8 #include<vector>
9 using namespace std;
10 struct MaNode{
11     int x;
12     int y;
13     MaNode *pre;
14     MaNode(int x1=0，int y1=0，MaNode *p =NULL ):x(x1)，y(y1)，pre(p)
15     {
16     }
17 };
18 const int maxr=5;
19 const int maxc=5;
20 queue<MaNode*> qmaze;
21 vector<MaNode*> vemaze; //保存节点，以便释放
22
23 int maze[maxr][maxc] = {
24     0，0，0，0，0，
25     0，1，0，1，0，
26     0，0，0，0，0，
27     0，1，1，1，0，
28     0，0，0，1，0，
29  };
30 void visit(int x，int y， MaNode *p )  //访问节点
31 {
32     struct MaNode *p2 = new MaNode(x，y，p);
33     //p2->x = x;
34     //p2->y =y;
35     //  p2->pre = p;
36      maze[x][y] = 2; //标识已经访问
37     qmaze.push(p2);
38 }
39 void bfs() // 宽度优先搜索
40 {
41     MaNode *head = new MaNode;
42     qmaze.push(head);
43     while( !qmaze.empty() )
44     {
45         MaNode *p= qmaze.front();
46         //int x=  p->x+1;
47         //int y= p->y+1;
48         vemaze.push_back(p);
49         qmaze.pop();
50         if( p->x ==maxr-1 && p->y==maxc-1 )
51         {
52              break;
53         }
54         if(p->x +1 <=maxr  && maze[p->x+1][p->y] ==0  )
55         {
56             visit(p->x+1，p->y，p);
57         }
58         if(p->y+1 <=maxc&& maze[p->x][p->y+1] ==0 )
59         {
60           visit(p->x，p->y+1，p);
61         }
62        if( p->x-1 >=0  && maze[p->x-1][p->y] ==0 )
63        {
64
65
66        visit(p->x-1，p->y，p);
67        }
68       if( p->y-1 >=0  && maze[p->x][p->y-1] ==0 )
69        {
70
71        visit(p->x，p->y-1，p);
72        }
73
74     }
75
76
77 }
78 void printPath()  //打印路径
79 {
80     MaNode *p  = vemaze[vemaze.size()-1];
81     while( p != NULL )
82     {
83         cout<<"("<<p->x<<"，"<<p->y<<")"<<endl;
84
85         p=p->pre;
86     }
87     //cout<<endl;
88 }
89 void destroy()  //销毁节点
90 {
91     for(size_t  i=0; i<vemaze.size() ; i++ )
92     {
93         delete vemaze[i];
94     }
95 }
96 int main()
97 {
98
99
100     bfs();
101     printPath();
102    destroy();
103    return 0;
104 }