开源中文网

您的位置: 首页 > 编程开发 > C++语言编程 > 正文

C++数据结构 泛洪法求解最短路径

来源:  作者:

广度优先搜索解决迷宫问题,同时要求给出最短路径。回溯法无法求出最短路径,必须借助BFS。泛洪法是非常常见的电路设计中使用的布线算法。下面的例子先构造一个迷宫(0表示空地,1表示墙),求出起始点到结束点的最短路径(不能斜穿,必须x/y轴方向移动) 
源代码如下,在centOS Linux5.2+gcc4.1.2上编译运行通过,结果正确。 
#include<cstdlib> 
#include<iostream> 
using namespace std; 
class node{ 
int x; 
int y; 
int d;//is path or wall 
int s;//steps count 
bool flood;//flooded 
bool mark; 
public: 
node():x(-1),y(-1),d(0),s(0),flood(false),mark(false){} 
node(int ix,int iy,int id,bool iflood):x(ix),y(iy),d(id),s(0),flood(iflood),mark(false){} 
friend ostream& operator<<(ostream& os,const node& in){ 
if(in.d==1)cout<<'1'; 
else{ 
if(in.mark)cout<<'*'; 
else cout<<'0'; 

return os; 

void set(int ix,int iy,int id){x=ix;y=iy;d=id;} 
void set(int ix,int iy){x=ix;y=iy;} 
void sets(int is){s=is;} 
void setflood(){flood=true;} 
void setmark(){mark=true;} 
int getd()const{return d;} 
int gets()const{return s;} 
int getx()const{return x;} 
int gety()const{return y;} 
bool getflood()const{return flood;} 
int isPos(int ix,int iy)const{return x==ix && y==iy;} 
}; 
struct pos{int dx;int dy;}; 
template <int x,int y> 
class map{ 
static pos pos4[8];//={ {-1,-1},{-1,0},{-1,1},{0,-1},{0,1},{1,-1},{1,0},{1,1}}; 
node buf[x][y]; 
int sx,sy,ex,ey; 

int stackTop; 
int step; 
int nextTop; 
#define PUSH(x,y) stack[stackTop++].set(x,y) 
#define GET(i) stack[i] 
node stack[40];//enough in our demo program; 
node next[10]; 
public: 
explicit map(int ib[x][y]){ 
for(int i=0;i<x;++i){ 
for(int j=0;j<y;++j){ 
buf[i][j].set(i,j,ib[i][j]); 


stackTop=0; 
step=0; 
nextTop=0; 

friend ostream& operator<<(ostream& os,const map& m){ 
for(int i=0;i<x;++i){ 
for(int j=0;j<y;++j){ 
cout<<m.buf[i][j]; 

cout<<'\n'; 

return os; 

bool set(int x1,int y1,int x2,int y2){ 
if(x1<0 || x1>=x-1 || x2<0 || x2>=x-1 
||y1<0 || y1>=y-1 || y2<0 || y2>=y-1){ 
cout<<"map::set() get wrong parameter\n"; 
return false; 

if(buf[x1][y1].getd()==1){ 
cout<<"started from wall! error\n"; 
return false; 

if(buf[x2][y2].getd()==1){ 
cout<<"ended at wall! error\n"; 
return false; 

if(x1==x2 && y1==y2){ 
cout<<"start and end equals! error\n"; 
return false; 

buf[x1][y1].setflood(); 
buf[x2][y2].setflood(); 
sx=x1; 
sy=y1; 
ex=x2; 
ey=y2; 
PUSH(sx,sy);//init start point 
return true; 
}//end init set() 
void finish(){ 
cout<<"found path\n"; 
buf[ex][ey].setmark(); 
node* plast=&buf[ex][ey]; 
while(--step){ 
for(int p=0;p<4;++p){ 
int px=plast->getx()+pos4[p].dx; 
int py=plast->gety()+pos4[p].dy; 
if(px<0 || px>x-1 || py<0 || py>y-1)continue;//invalid pos, ignore it 
if(buf[px][py].getflood()==1 
&&buf[px][py].gets()==step){ 
buf[px][py].setmark(); 
plast=&buf[px][py]; 
break; 



buf[sx][sy].setmark(); 
cout<<*this; 
exit(0); 

int findNexts(const node& n){ 
for(int p=0;p<4;++p){//for its 4 directions 
int px=n.getx()+pos4[p].dx; 
int py=n.gety()+pos4[p].dy; 
if(px<0 || px>x-1 || py<0 || py>y-1)continue;//invalid pos, ignore it 
if(px==ex && py==ey)finish();//found path and end 
if(buf[px][py].getflood()==1)continue;//meets old path 
if(buf[px][py].getd()==1)continue;//meets wall 
bool found=false; 

for(int n=0;n<nextTop;++n){//put it into next[] 
if(next[n].isPos(px,py)){//if found pos already in next[] 
found=true; 
if(next[n].gets()>step){ 
next[n].sets(step); 

break; 
}//end for next[] 

if(found==false){ 
next[nextTop++].set(px,py); 
next[nextTop-1].sets(step); 
}//end if found 
}//for 4 directions end 
return nextTop==0? 0:1; 

void solv(){//solve the best path, or tell there's no path 
while(true){ 
++step; 
nextTop=0; 
int sum=0; 
for(int i=0;i<stackTop;++i){ 
int X=GET(i).getx(); 
int Y=GET(i).gety(); 
sum+=findNexts(buf[X][Y]); 
}//end for all elements in stack 
if(sum==0){ 
cout<<"path not found!\n"; 
exit(0); 

stackTop=0; 
for(int m=0;m<nextTop;++m){ 
int xx=next[m].getx(); 
int yy=next[m].gety(); 
buf[xx][yy].sets(step); 
buf[xx][yy].setflood(); 
stack[stackTop++].set(xx,yy); 

}//end while 
cout<<"No path found:(\n";//path not found 

}; 
template <int x,int y> 
pos map<x,y>::pos4[8]={ {-1,0},{0,-1},{0,1},{1,0}}; 

int main(void){ 
node n; 
int data[7][9]={ 
{0,0,0,1,0,0,0,0,0}, 
{0,0,1,0,0,1,0,1,1}, 
{0,1,0,0,0,1,0,0,0}, 
{0,0,0,0,0,1,0,0,0}, 
{0,0,1,1,1,1,1,0,0}, 
{0,1,0,0,1,0,0,0,0}, 
{0,1,0,0,0,0,1,0,0} 
}; 
map<7,9> m(data); 
cout<<m; 
if(m.set(0,0,5,3)){ 
cout<<"map::set()"<<'\n'; 
m.solv(); 

cout<<m; 
return 0; 



程序输出>a.out 
*001***00 
*01**1*11 
*1**01**0 
***0010*0 
0011111*0 
010*1***0 
010***100 
星号代表路径

Tags:数据结构
关于开源中文网 - 联系我们 - 广告服务 - 网站地图 - 版权声明