c++ 使用广度优先算法走迷宫，并记录搜索出来的路径。最终标记出来
#########################################################
#include <iostream>
#include <vector>//const int 12=12;
//const int 12=12;using std::cout;
using std::endl; using std::vector; struct node { int x; int y; int s; int px; int py; };typedef struct node Node;
vector<Node> route(12*12);vector<vector<int> > vec;
vector<vector<int> > book(12,vector<int>(12,0)); int dx=10, dy=11,min=9999999; int next[4][2]={ {-1,0},{0,-1},{1,0},{0,1}}; int head, tail;void show(vector<vector<int> > avec)
{ vector<vector<int> >::const_iterator cit; vector<int>::const_iterator it; for(cit=avec.begin(); cit!=avec.end();++cit) { vector<int> pvec = *cit; for(it=pvec.begin();it!=pvec.end();++it) cout << *it << " "; cout << endl; } } vector<vector<int> > block(int x1, int y1, int x2, int y2, vector<vector<int> > avec) { for(int i=x1;i<=x2;++i) { for(int j=y1;j<=y2;++j) avec[i][j]=1; } return avec; } vector<vector<int> > init() { vector<vector<int> > avec(12, vector<int>(12,0)); for(int i=0;i<12;++i) { avec[i][0]=1; avec[i][12-1]=1; } for(int j=0;j<12;++j) { avec[0][j]=1; avec[12-1][j]=1; }avec[1][0]=0; //in
avec[10][11]=0; // out avec[2][1]=1; avec[2][2]=1; avec[3][2]=1; avec[4][2]=1; avec[6][2]=1; avec[6][1]=1; avec[1][7]=1; avec=block(2,4,3,7,avec); avec=block(5,5,6,9,avec); avec=block(8,1,8,4,avec); avec=block(8,6,9,7,avec); avec=block(8,9,9,10,avec); avec=block(2,9,4,9,avec); avec[5][10]=1; avec[10][7]=1; return avec; }//void bfs(int sx, int sy, int dx, int dy)
vector<node> bfs(int sx, int sy, int dx, int dy) { vector<Node> route(12*12);route[tail].x=sx;
route[tail].y=sy; route[tail].s=0; tail++;while(head < tail)
{ for(int i=0;i<4;++i) { int nx=route[head].x+next[i][0]; int ny=route[head].y+next[i][1];if(nx<0 || nx > 12-1 || ny < 0 || ny > 12-1)
continue; if(vec[nx][ny]==0 && book[nx][ny]==0) { book[nx][ny]=1; route[tail].x=nx; route[tail].y=ny; route[tail].s=route[head].s+1; route[tail].px=route[head].x; route[tail].py=route[head].y; tail++; }if(nx==dx && ny==dy)
{ if (route[tail-1].s < min) min=route[tail-1].s; cout << min << endl; return route; } } head++; }vector<Node> x;
return x; }void lable(vector<Node> vn, vector<vector<int> > &avec)
{ int temp=min; int nx=dx; int ny=dy; for(int i=tail-1;i>0;--i) { int x=vn[i].x; int y=vn[i].y; int px=vn[i].px; int py=vn[i].py; int s=vn[i].s; if(s==temp && x==nx && y==ny) { avec[px][py]=9; cout << s << "\t" << temp << endl; nx=px; ny=py; --temp; } } }int main(void)
{ vec=init(); int sx=1; int sy=0; vec[sx][sy]=9;show(vec);
route=bfs(sx,sy,dx,dy); //cout << head << "\t" << tail << " " << min << endl; //for(int i=0;i<=tail;++i) //{ // cout << i << " " << route[i].x << " " << route[i].y << " " << route[i].s << " " << route[i].px << " " << route[i].py << endl; //} lable(route, vec); show(vec); } #################################运行的结果：
1 1 1 1 1 1 1 1 1 1 1 1
9 0 0 0 0 0 0 1 0 0 0 1 1 1 1 0 1 1 1 1 0 1 0 1 1 0 1 0 1 1 1 1 0 1 0 1 1 0 1 0 0 0 0 0 0 1 0 1 1 0 0 0 0 1 1 1 1 1 1 1 1 1 1 0 0 1 1 1 1 1 0 1 1 0 0 0 0 0 0 0 0 0 0 1 1 1 1 1 1 0 1 1 0 1 1 1 1 0 0 0 0 0 1 1 0 1 1 1 1 0 0 0 0 0 0 1 0 0 0 0 1 1 1 1 1 1 1 1 1 1 1 1 20 1 1 1 1 1 1 1 1 1 1 1 1 9 9 9 9 0 0 0 1 0 0 0 1 1 1 1 9 1 1 1 1 0 1 0 1 1 0 1 9 1 1 1 1 0 1 0 1 1 0 1 9 0 0 0 0 0 1 0 1 1 0 0 9 0 1 1 1 1 1 1 1 1 1 1 9 0 1 1 1 1 1 0 1 1 0 0 9 9 9 9 9 9 0 0 1 1 1 1 1 1 0 1 1 9 1 1 1 1 0 0 0 0 0 1 1 9 1 1 1 1 0 0 0 0 0 0 1 9 9 9 0 1 1 1 1 1 1 1 1 1 1 1 1