深度优先搜索（DFS）和广度优先搜索（BFS）求解迷宫问题

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

OXXXXXXX

OOOOOXXX

XOXXOOOX

XOXXOXXO

XOXXXXXX

XOXXOOOX

XOOOOXOO

XXXXXXXO

O为通路，X为障碍物。

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

深度优先搜索（DFS）

 #include<iostream>

 using namespace std;

 char a1[] = {'O','X','X','X','X','X','X','X','\0'};

 char a2[] = {'O','O','O','O','O','X','X','X','\0'};

 char a3[] = {'X','O','X','X','O','O','O','X','\0'};

 char a4[] = {'X','O','X','X','O','X','X','O','\0'};

 char a5[] = {'X','O','X','X','X','X','X','X','\0'};

 char a6[] = {'X','O','X','X','O','O','O','X','\0'};

 char a7[] = {'X','O','O','O','O','X','O','O','\0'};

 char a8[] = {'X','X','X','X','X','X','X','O','\0'};

 char *p[] = {a1, a2, a3, a4, a5, a6, a7, a8};

 int offset[][] = {{-, }, {, }, {, -}, {, }};　　//偏移量为一位大小，顺序为：上（x-1）、下（x+1）、左(y-1)、右(y+1)

 void DFS(int x, int y)

 {

     if(x ==  && y == )　　　//找到出口

     {

         p[x][y] = '*';

         cout << "One path of the maze:" << endl;

         for(int i = ; i < ; i++)

             cout << p[i] << endl;

         cout << endl;

     }

     for(int i = ; i < ; i++)　　//寻找可行的路径

     {

         int nx = x + offset[i][];　　//试探可走路径，下一位置为当前位置加上偏移量

         int ny = y + offset[i][];

         if(nx>= && nx<= && ny>= && ny<= && p[nx][ny]!='X' && p[nx][ny]!='*')　　//找到可行路径

         {

             p[x][y] = '*';　　//画出路径

             DFS(nx, ny);　　//继续搜索

             p[x][y] = 'O';　　//走不下去了回退

         }

     }

 }

 int main()

 {

     cout << "The size of the maze： row 8， col 8" << endl;

     cout << "The map: " << endl;

     for(int i = ; i < ; i++)

         cout << p[i] << endl;

     DFS(, );

     return ;

 }

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

广度优先搜索（BFS）

 #include<iostream>

 #include<cstring>

 using namespace std;

 char a1[] = {'O','X','X','X','X','X','X','X','\0'};

 char a2[] = {'O','O','O','O','O','X','X','X','\0'};

 char a3[] = {'X','O','X','X','O','O','O','X','\0'};

 char a4[] = {'X','O','X','X','O','X','X','O','\0'};

 char a5[] = {'X','O','X','X','X','X','X','X','\0'};

 char a6[] = {'X','O','X','X','O','O','O','X','\0'};

 char a7[] = {'X','O','O','O','O','X','O','O','\0'};

 char a8[] = {'X','X','X','X','X','X','X','O','\0'};

 char *p[] = {a1, a2, a3, a4, a5, a6, a7, a8};    

 int offset[][] = {{-, }, {, }, {, -}, {, }};

 int vis[][]; //用来标记是否访问过当前位置

 int cnt = ;

 struct Position{

     int x, y;    //当前位置

     int pre;    //前驱点

 }path[*], myqueue[*];

 void BFS()

 {

     memset(vis, , sizeof(vis));

     int front = , rear = ;

     myqueue[rear].x = ;    //入口入队

     myqueue[rear].y = ;

     myqueue[rear].pre = -;

     rear++;

     Position* tmp;

     while(front < rear)

     {

         tmp = &myqueue[front];    //当前位置出队 

         if(tmp->x ==  && tmp->y == )    //到达出口

         {

             while(tmp->pre != -)    //回溯寻找路径

             {

                 path[cnt].x = tmp->x;　　//记录可行路径的位置

                 path[cnt].y =tmp->y;

                 cnt++;

                 tmp = &myqueue[tmp->pre];

             }

             for(int i = ; i < cnt; i++)　　//在地图中可视化路径

             {

                 p[][] = '*';

                 p[path[i].x][path[i].y] = '*';

             }

             cout << "One path of the maze:" << endl;

             for(int i = ; i < ; i++)

                 cout << p[i] << endl;

             cout << endl;

             break;

         }

         for(int i = ; i < ; i++)    //遍历相邻点

         {

             int nx = tmp->x + offset[i][];　　//试探路径

             int ny = tmp->y + offset[i][];

             if(nx>= && nx<= && ny>= && ny<= && p[nx][ny]!='X' && vis[nx][ny]!=)    //满足条件入队

             {

                 vis[nx][ny] = ;

                 myqueue[rear].x = nx;

                 myqueue[rear].y = ny;

                 myqueue[rear].pre = front;

                 rear++;

             }

         }

         front++;

     }

 }

 int main()

 {

     cout << "The size of the maze： row 8， col 8" << endl;

     cout << "The map: " << endl;

     for(int i = ; i < ; i++)

         cout << p[i] << endl;

     BFS();

     return ;

 }