C++写的宽度优先查找最短路径（可用于迷宫和，电路布线等）

#include<iostream> #include<stdlib.h> #include<vector> #include<algorithm> using namespace std ; class point { friend void inputgrid(point&,point&) ; friend void outputpath(int,point *) ; friend bool findpath(point start,point finish, int &plen,point *&path ) ; private : int row,col ; } ; char map[20][20]; int grid[20][20],r,c; vector<vector<point> >roads; //存放所有最短布线路径 void inputgrid(point &start,point &finish) { cout<<"请输入矩阵长宽:"<<endl ; cin>>r>>c ; cout<<"输入网格（输入E为开始，S为结束，#为墙，. 为通路）"<<endl ; for(int i=1 ;i<=r ;i++) { for(int j=1 ;j<=c;j++) { cin>>map[i][j] ; if(map[i][j]=='E') { start.row=i; start.col=j; grid[i][j]=0; } if(map[i][j]=='S') { finish.row=i; finish.col=j; grid[i][j]=0; } if(map[i][j]=='.') grid[i][j]=0; if(map[i][j]=='#') grid[i][j]=1; } } } bool findpath(point start,point finish, int &plen, point * &path) { if((start.row==finish.row)&&(start.col==finish.col)) { plen = 0 ; return true ; } point offset[4] ; offset[0].row=0 ; offset[0].col=1 ; //右 offset[1].row=1 ; offset[1].col=0 ; // 下 offset[2].row=0 ; offset[2].col=-1; //左 offset[3].row=-1; offset[3].col=0 ; // 上 point here,nbr ; here.row=start.row ; here.col=start.col ; grid[start.row][start.col] = 2 ; vector<point>Q ; do { for(int i=0 ;i<4 ;i++) { nbr.row=here.row + offset[i].row ; nbr.col=here.col + offset[i].col ; if(grid[nbr.row][nbr.col]==0) { grid[nbr.row][nbr.col] = grid[here.row][here.col]+1 ; if((nbr.row==finish.row)&&(nbr.col==finish.col)) break ; Q.push_back(nbr) ; } } if((nbr.row==finish.row)&&(nbr.col==finish.col)) break ; //完成布线？ int k = Q.size() ; if(k==0) return false ; //队列为空，表示无解 else { here.row = Q[0].row ; here.col = Q[0].col ; Q.erase(Q.begin(),Q.begin()+1) ; } }while(true) ; vector<point>a; a.push_back(finish); roads.push_back(a); for(int ii=0;ii<roads.size();ii++){ plen=grid[roads[ii][roads[ii].size()-1].row][roads[ii][roads[ii].size()-1].col]-2; for(int k=plen-1;k>=0;k--){ here=roads[ii][roads[ii].size()-1]; //找前驱位置 int t=0; //标记与here相邻个数 for(int q=0;q<4;q++){ nbr.row=here.row+offset[q].row; nbr.col=here.col+offset[q].col; if(grid[nbr.row][nbr.col]==k+2){ t++; if(t==1) roads[ii].push_back(nbr); else{ vector<point> a(roads[ii].begin(),roads[ii].end()-1); a.push_back(nbr); roads.push_back(a); } } } if(t==0){ii--;roads.erase(roads.begin()+ii);break;} } } plen = grid[finish.row][finish.col] - 2 ; return true; } int main() { point s,f,*p ; int le ; while(1){ inputgrid(s,f) ; if(findpath(s,f,le,p)) cout<<"最短路径长度："<<le<<" "<<roads.size ()<<endl; // outputpath(l,p) ; else cout<<"-1"<<endl ; } return 0 ; } //==================================== //输出实例： // 4 4 // //#E## //..## //#..# //##.S