C++最も基本的な迷宮問題を解決する
14245 ワード
問題の説明:最も基本的な迷路図を与えて、1つの配列で表して、値0は道があって、1は障害物があって、1本探して、行列の左上の角から、右下の角の最短路まで.最短絡を求めて、みんなが最初に思いついたのはBFSで求めたのかもしれませんが、本文もBFSで最短絡を求めたのです.
ソースコードは次のとおりです.
ソースコードは次のとおりです.
1 /*
2 BFS
3
4
5 **/
6 #include
7 #include
8 #include
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 qmaze;
21 vector 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<<"("<x<<","<y<<")"<<endl;
84
85 p=p->pre;
86 }
87 //cout<
88 }
89 void destroy() //
90 {
91 for(size_t i=0; i )
92 {
93 delete vemaze[i];
94 }
95 }
96 int main()
97 {
98
99
100 bfs();
101 printPath();
102 destroy();
103 return 0;
104 }