深度优先搜索,简称dfs。我们可以将它跟递归联合在一起。
先回顾一下递归。
我们使用递归完成斐波那契数列的计算:
int fib(int n){
if(n == 1 || n == 2){
return 1;
}
return fib(n - 1) + fib(n - 2);
}
以上递归实现斐波那契实际上就是按照深度优先的方式进行搜索。也就是 “一条路走到黑” 。注意:这里的搜索指的是一种穷举方式,把可行的方案都列举出来,不断尝试,直到找到问题的解。
以上即为Fib(5)的计算过程,我们发现实际上对应着一棵树,这棵树被称为搜索树。
深度优先搜索与递归的区别:
dfs解法:首先找到起点s,走到每个点时,按照左、下、右、上的顺序尝试。每走到下一个点以后,我们把这个点当作起点s,继续顺序尝试。如果某个点上下左右四个方向都尝试过,便回到走到这个点的之前点,称为回溯。然后继续尝试其他方向,直到所有点都尝试过上下左右四个方向。
代码实现:
if(maze[x][y] == 'T'){//T是终点
return
true;
}
vis[x][y] = 1;
maze[x][y] = 'm';
int tx = x - 1, ty = y;
if(in(tx, ty) && maze[tx][ty] != '*' && !vis[tx][ty]){
//在地图内,非障碍物,无访问过
if(dfs(tx, ty)){
return
true;
}
}
int tx = x, ty = y - 1;
if(in(tx, ty) && maze[tx][ty] != '*' && !vis[tx][ty]){
//在地图内,非障碍物,无访问过
if(dfs(tx, ty)){
return
true;
}
}
int tx = x + 1, ty = y;
if(in(tx, ty) && maze[tx][ty] != '*' && !vis[tx][ty]){
//在地图内,非障碍物,无访问过
if(dfs(tx, ty)){
return
true;
}
}
int tx = x, ty = y + 1;
if(in(tx, ty) && maze[tx][ty] != '*' && !vis[tx][ty]){
//在地图内,非障碍物,无访问过
if(dfs(tx, ty)){
return
true;
}
}
vis[x][y] = 0;
maze[x][y] = '.';
return
false;
完整代码
//迷宫
#include<iostream>
using namespace std;
string maze[110];
bool vis[110][110];
int n, m;
bool in(int x, int y){
return 0 <= x && x < n && 0 <= y && y < m;
}
bool dfs(int x, int y){
if(maze[x][y] == 'T'){//T是终点
return true;
}
vis[x][y] = 1;
maze[x][y] = 'm';
int tx = x - 1, ty = y;
if(in(tx, ty) && maze[tx][ty] != '*' && !vis[tx][ty]){
//在地图内,非障碍物,无访问过
if(dfs(tx, ty)){
return true;
}
}
int tx = x, ty = y - 1;
if(in(tx, ty) && maze[tx][ty] != '*' && !vis[tx][ty]){
//在地图内,非障碍物,无访问过
if(dfs(tx, ty)){
return true;
}
}
int tx = x + 1, ty = y;
if(in(tx, ty) && maze[tx][ty] != '*' && !vis[tx][ty]){
//在地图内,非障碍物,无访问过
if(dfs(tx, ty)){
return true;
}
}
int tx = x, ty = y + 1;
if(in(tx, ty) && maze[tx][ty] != '*' && !vis[tx][ty]){
//在地图内,非障碍物,无访问过
if(dfs(tx, ty)){
return true;
}
}
vis[x][y] = 0;
maze[x][y] = '.';
return false;
}
int main(){
//输入地图
cin >> n >> m;
for(int i = 0; i < n; i++){
cin>>maze[i];
}
int x, y;
//找到起始点
for(int i = 0; i < n; i++){
for(int j = 0; j < m; j++){
if(maze[i][j] == 'S'){
x = i; y = j;
}
}
}
if(dfs(x, y)){
//打印
for(int i = 0; i < n; i++){
cout << maze[i] <<endl;
}
}else{
cout<<"No!"<<endl;
}
return 0;
}
然而我们发现代码比较长,而且有很多重复的地方比较冗余。重复的地方在于下一步的运行方向。那么我们可以简化一下代码。
int dir[4][2] = {{-1, 0}, {0, -1}, {1, 0}, {0, 1}};
这里建议使用逆时针或者顺时针的记录,方便使用向左转向右转的实现。for(int i = 0; i < 4; i++){
int tx = x + dir[i][0];
int ty = y + dir[i][1];
if(in(tx, ty) && maze[tx][ty] != '*' && !vis[tx][ty]){
//在地图内,非障碍物,无访问过
if(dfs(tx, ty)){
return
true;
}
}
}
从而减少了代码量。
前面我们只是寻找了是否有可行的路径,现在需要求最少多少步即可到达。
我们使用一个参数来记录前面参数以及走了多少步:step。
int ans = 10000000000;//结果
void dfs(int x, int y, int step){
if(maze[x][y] == 'T'){//T是终点
if(step < ans){
ans = step;
}
return;
}
vis[x][y] = 1;
maze[x][y] = 'm';
for(int i = 0; i < 4; i++){
int tx = x + dir[i][0];
int ty = y + dir[i][1];
if(in(tx, ty) && maze[tx][ty] != '*' && !vis[tx][ty]){
//在地图内,非障碍物,无访问过
dfs(tx, ty, step + 1)
}
}
vis[x][y] = 0;//取消标记
}
ok,明天继续。