深度优先搜索（dfs)

笔者对算法的理解能力有限，欢迎各位大神指正。

原理相信大家都能在网上找到很多，简单来说就是定一个出发点，在分叉口选一条路走到黑，然后再回过头来走一下条路。

我们假设有一个网格：
（1，1）（1，2）（1，3）
（2，1）（2，2）（2，3）
（3，1）（3，2）（3，3）

一个质点从（1，1）出发，只能向右或者向下走，直到走到（3，3）。
我们用下面的代码来记录整棵树

代码如下：

include<bits/stdc++.h>//万能头文件
using namespace std;
int s=0;
int dx[3]={0,1};//方向数组，使同一下标的dx,dy是（0，1）或（1，0），向右或者向下走
int dy[3]={1,0};//方便处理成x+dx[i],y+dy[i]
void dfs(int x,int y)
{
    if(x>3||x<1||y<1||y>3||(x==3&&y==3))//如果越界或者到达终点则返回
    {
        if(x==3&&y==3)//如果到达终点，s++
        {
            cout<<"("<<x<<","<<y<<")"<<endl;
            s++;
            cout<<endl;
        }
        return;
    }
    else
    {
        cout<<"("<<x<<","<<y<<")"<<endl;//输出坐标
        for(int i=0;i<2;i++)//找两个方向
        {
            dfs(x+dx[i],y+dy[i]);
        }
    }
}
int main()
{
    dfs(1,1);//从（1，1）出发
    cout<<s;
    return 0;
}

可以看到结果如图，一共有6种走法：
分别是：

**

假设（2，2）处有障碍不能通过

**

#include<bits/stdc++.h>
using namespace std;
int Map[5][5];//定义一个地图数组，用来标记障碍位置
int s=0;
int dx[3]={0,1};
int dy[3]={1,0};
void dfs(int x,int y)
{
    if(x>3||x<1||y<1||y>3||(x==3&&y==3)||Map[x][y]==1)//遇到障碍也停止
    {
        if(x==3&&y==3)
        {
            cout<<"("<<x<<","<<y<<")"<<endl;
            s++;
            cout<<endl;
        }
        return;
    }
    else
    {
        cout<<"("<<x<<","<<y<<")"<<endl;
        for(int i=0;i<2;i++)
        {
            dfs(x+dx[i],y+dy[i]);
        }
    }
}
int main()
{
    memset(Map,0,sizeof(Map));//让Map数组全是0
    Map[2][2]=1;//把障碍标记为1
    dfs(1,1);
    cout<<s;
    return 0;
}

那么就只剩下两种走法了：

我们也可以从头走到底，只走一条，不显示完整的树
如果是这样的话，他就不一定会走到（3，3）的位置

代码如下：

#include<bits/stdc++.h>
using namespace std;
int Map[5][5];
int s=0;
int dx[5]={0,1,-1,0};//现在设成能走任意方向
int dy[5]={1,0,0,-1};
void dfs(int x,int y)
{
    if(x>3||x<1||y<1||y>3||Map[x][y]==1)//如果越界或者走过就返回
    {
        return;
    }
    else
    {
        Map[x][y]=1;//如果没走过，标记成走过
        cout<<"("<<x<<","<<y<<")"<<endl;
        for(int i=0;i<4;i++)
        {
            dfs(x+dx[i],y+dy[i]);//继续往下搜索四个方向
        }
    }
}
int main()
{
    memset(Map,0,sizeof(Map));
    dfs(1,1);
    return 0;
}

运行结果如下：

这是其中一个走法

掌握这个算法我们可以在很多题目上更加得心应手！欢迎大神、朋友们指正！