走迷宫
今天讲一下 dfs/bfs 简单的应用——走迷宫。
dfs（深度优先搜索）
dfs 一般都是通过递归来完成（非递归也可以，但是有些麻烦），由于是递归，所以理解 dfs 的关键就在于解决“当下如何做”，而“下一步如何做”则与“当下如何做”是一样的。
下面给出 dfs 的基本模型：
void dfs(int step)
{
判断边界条件
尝试每一种可能 for( ; ; )
{
继续下一步 dfs(step + 1);
}
return;
}
然后让我们正式开始走迷宫！
首先我们需要一张图来存放迷宫，我们使用一个二维数组来完成，迷宫中只有空地和障碍物，所以我们用 0 表示空地，1 表示障碍物， 我们需要来标记一个点是否已经走过，所以定义一个与存放迷宫一样的二维数组，0 表示为走，1 表示已走过，因为是地图，所以我们需要向 4 个方向延伸，再定义一个二维数组来寻找方向。
ok，准备工作已经完成，下面让我们来看一看代码：
#include<bits/stdc++.h>
using namespace std;
//简单dfs
int n,m; //边界
int start_x,start_y,end_x,end_y; //起点，终点
int x,y; //坐标
int G[51][51]; //地图
int book[51][51]; //记录
int Min = 99999999;
//判断
bool judge(int x, int y)
{
if(x < 1 || x > n || y < 1 || y > m || G[x][y] == 1)
return false;
return true;
}
void dfs(int tx, int ty, int step)
{
int next[4][2] = {
{
0,1},{
1,0},{
0,-1},{
-1,0}}; //方向
//出口
if(tx == end_x && ty == end_y)
{
//要最短路径
if(step < Min)
Min = step;
return;
}
//枚举4种走法（上下左右）
for(int i = 0; i < 4; i++)
{
x = tx + next[i][0];
y = ty + next[i][1];
//判断是否满足条件
if(judge(x, y) && !book[x][y])
{
book[x][y] = 1; //标记该点已走过
dfs(x, y, step + 1); //尝试下一个点
book[x][y] = 0; //尝试结束，取消标记
}
}
}
int main()
{
cin >> n >> m;
for(int i = 1; i <= n; i++)
for(int j = 1; j <= m; j++)
cin >> G[i][j];
cin >> start_x >> start_y >> end_x >> end_y;
book[start_x][start_y] = 1; //标记起点已在路径中
dfs(start_x, start_y, 0);
cout << Min << endl;
return 0;
}
注：标记完后一定要取消标记，因为是递归，而且 dfs 是一次要到底的，我们不能因为一次的搜索而影响到其它。
说实话，找最短路径还是 bfs 在行，所以赶快让我们来看一看它吧。
bfs（广度优先搜索）
与 dfs 一条路走到黑不同，bfs 是 “一层一层”往下进行的，它将每一次所能走到的点全都加入队列，直到到达目的地
（bfs 的标记不需要取消，因为 bfs 是将每一个点都入队，有可能不同的“上层”的点会到达相同的“下层”的点，所以这个标记就起了作用——不会把相同的点入队多次）。
下面我们来看一看代码：
#include<bits/stdc++.h>
using namespace std;
//简单bfs
typedef struct _node
{
int x;
int y;
int s; //步数
}node;
int n,m; //边界
int start_x,start_y,end_x,end_y; //起点，终点
int x,y; //坐标
int G[51][51]; //地图
int book[51][51]; //记录
//判断
bool judge(int x, int y)
{
if(x < 1 || x > n || y < 1 || y > m || G[x][y] == 1)
return false;
return true;
}
void bfs(node start)
{
queue<node> q;
int next[4][2] = {
{
0,1},{
1,0},{
0,-1},{
-1,0}}; //方向
//将起点入队
q.push(start);
//标记起点
book[start_x][start_y] = 1;
//队列不为空时循环
while(!q.empty())
{
node now = q.front();
q.pop();
//出口
if(now.x == end_x && now.y == end_y)
{
cout << now.s << endl;
return;
}
//枚举4种走法（上下左右）
for(int i = 0; i < 4; i++)
{
x = now.x + next[i][0];
y = now.y + next[i][1];
//判断是否满足条件
if(judge(x,y) && !book[x][y])
{
node New;
New.x = x;
New.y = y;
New.s = now.s + 1;
book[x][y] = 1; //标记，每个点只需入队一次，所以不需要还原
q.push(New); //入队
}
}
}
cout << "没有通路" << endl;
}
int main()
{
node start;
cin >> n >> m;
for(int i = 1; i <= n; i++)
for(int j = 1; j <= m; j++)
cin >> G[i][j];
cin >> start_x >> start_y >> end_x >> end_y;
start.x = start_x;
start.y = start_y;
start.s = 0;
bfs(start);
return 0;
}
可以看到 dfs 与 bfs 在时间复杂度上是一样的，所以没有什么好坏之分，只是根据不同的情况来选择而已。dfs 更适合目标明确，以找到目标为主要目的的情况，而 bfs 则更适合寻找相对最优解的情况。
最后借用一下《大话数据结构》上的话：
这里还要再多说几句，对于深度和广度而言，已经不是简单的算法实现问题，完全可以上升到方法论的角度。你求学是博览群书，不求甚解，还是深钻细研，鞭策入里；你旅游是走马观花，蜻蜓点水，还是下马看花，深度体验；你交友是四海之内皆兄弟，还是人生得一知己足矣…其实都无对错之分，只视不同人的理解而有了不同的诠释。我个人觉得深度和广度是即矛盾又统一的两个方面，偏颇都不可取， 还望大家自己慢慢体会。
!@#$%^&*~