问题描述：给定一个最基本的迷宫图，用一个数组表示，值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 } |
