用下面这个简单的迷宫图作为例子:

OXXXXXXX
OOOOOXXX
XOXXOOOX
XOXXOXXO
XOXXXXXX
XOXXOOOX
XOOOOXOO
XXXXXXXO

O为通路,X为障碍物。

深度优先搜索就像是一条路走到黑,走到黑,黑了再回来。有种递归的感觉。

深度优先搜索(DFS)

 1 #include<iostream>
 2 using namespace std;
 3
 4 char a1[] = {'O','X','X','X','X','X','X','X','\0'};
 5 char a2[] = {'O','O','O','O','O','X','X','X','\0'};
 6 char a3[] = {'X','O','X','X','O','O','O','X','\0'};
 7 char a4[] = {'X','O','X','X','O','X','X','O','\0'};
 8 char a5[] = {'X','O','X','X','X','X','X','X','\0'};
 9 char a6[] = {'X','O','X','X','O','O','O','X','\0'};
10 char a7[] = {'X','O','O','O','O','X','O','O','\0'};
11 char a8[] = {'X','X','X','X','X','X','X','O','\0'};
12 char *p[8] = {a1, a2, a3, a4, a5, a6, a7, a8};
13
14 int offset[4][2] = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}};  //偏移量为一位大小,顺序为:上(x-1)、下(x+1)、左(y-1)、右(y+1)
15
16 void DFS(int x, int y)
17 {
18     if(x == 7 && y == 7)   //找到出口
19     {
20         p[x][y] = '*';
21         cout << "One path of the maze:" << endl;
22         for(int i = 0; i < 8; i++)
23             cout << p[i] << endl;
24         cout << endl;
25     }
26     for(int i = 0; i < 4; i++)  //寻找可行的路径
27     {
28         int nx = x + offset[i][0];  //试探可走路径,下一位置为当前位置加上偏移量
29         int ny = y + offset[i][1];
30         if(nx>=0 && nx<=7 && ny>=0 && ny<=7 && p[nx][ny]!='X' && p[nx][ny]!='*')  //找到可行路径
31         {
32             p[x][y] = '*';  //画出路径
33             DFS(nx, ny);  //继续搜索
34             p[x][y] = 'O';  //走不下去了回退
35         }
36     }
37 }
38
39 int main()
40 {
41     cout << "The size of the maze: row 8, col 8" << endl;
42     cout << "The map: " << endl;
43     for(int i = 0; i < 8; i++)
44         cout << p[i] << endl;
45
46     DFS(0, 0);
47     return 0;
48 }

 

广度优先搜索则是遍历与当前位置相邻的所有可行点,就像是病毒,传播速度很快。一传十,十传百的感觉。
求解时需要与队列相结合。

广度优先搜索(BFS)

 1 #include<iostream>
 2 #include<cstring>
 3 using namespace std;
 4
 5 char a1[] = {'O','X','X','X','X','X','X','X','\0'};
 6 char a2[] = {'O','O','O','O','O','X','X','X','\0'};
 7 char a3[] = {'X','O','X','X','O','O','O','X','\0'};
 8 char a4[] = {'X','O','X','X','O','X','X','O','\0'};
 9 char a5[] = {'X','O','X','X','X','X','X','X','\0'};
10 char a6[] = {'X','O','X','X','O','O','O','X','\0'};
11 char a7[] = {'X','O','O','O','O','X','O','O','\0'};
12 char a8[] = {'X','X','X','X','X','X','X','O','\0'};
13 char *p[8] = {a1, a2, a3, a4, a5, a6, a7, a8};
14
15 int offset[4][2] = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}};
16 int vis[8][8]; //用来标记是否访问过当前位置
17 int cnt = 0;
18
19 struct Position{
20     int x, y;    //当前位置 
21     int pre;    //前驱点 
22 }path[8*8], myqueue[8*8];
23
24 void BFS()
25 {
26     memset(vis, 0, sizeof(vis));
27     int front = 0, rear = 0;
28
29     myqueue[rear].x = 0;    //入口入队 
30     myqueue[rear].y = 0;
31     myqueue[rear].pre = -1;
32     rear++;
33
34     Position* tmp;
35     while(front < rear)
36     {
37         tmp = &myqueue[front];    //当前位置出队 
38
39         if(tmp->x == 7 && tmp->y == 7)    //到达出口 
40         {
41             while(tmp->pre != -1)    //回溯寻找路径 
42             {
43                 path[cnt].x = tmp->x;  //记录可行路径的位置
44                 path[cnt].y =tmp->y;
45                 cnt++;
46                 tmp = &myqueue[tmp->pre];
47             }
48
49             for(int i = 0; i < cnt; i++)  //在地图中可视化路径
50             {
51                 p[0][0] = '*';
52                 p[path[i].x][path[i].y] = '*';
53             }
54             cout << "One path of the maze:" << endl;
55             for(int i = 0; i < 8; i++)
56                 cout << p[i] << endl;
57             cout << endl;
58             break;
59         }
60
61         for(int i = 0; i < 4; i++)    //遍历相邻点 
62         {
63             int nx = tmp->x + offset[i][0];  //试探路径
64             int ny = tmp->y + offset[i][1];
65             if(nx>=0 && nx<=7 && ny>=0 && ny<=7 && p[nx][ny]!='X' && vis[nx][ny]!=1)    //满足条件入队 
66             {
67                 vis[nx][ny] = 1;
68                 myqueue[rear].x = nx;
69                 myqueue[rear].y = ny;
70                 myqueue[rear].pre = front;
71                 rear++;
72             }
73         }
74         front++;
75     }
76 }
77
78 int main()
79 {
80     cout << "The size of the maze: row 8, col 8" << endl;
81     cout << "The map: " << endl;
82     for(int i = 0; i < 8; i++)
83         cout << p[i] << endl;
84
85     BFS();
86     return 0;
87 }

这是一个只有一条通路的迷宫,具体要根据需求进行修改以满足。

01-13 16:03