用下面这个简单的迷宫图作为例子：
OXXXXXXX
OOOOOXXX
XOXXOOOX
XOXXOXXO
XOXXXXXX
XOXXOOOX
XOOOOXOO
XXXXXXXOO为通路，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 }
这是一个只有一条通路的迷宫，具体要根据需求进行修改以满足。