???????????????????????????????????????????????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 }