作者：吴小熙1108 | 来源：互联网 | 2023-09-25 23:42
好的，接下来就是本萌新的第一篇博客啦。直接上深搜！深度优先搜索（Depth-First-Search），简称“深搜”（dfs），是我们蒟蒻们最基本的搜索操作之一。简单地说，深搜就是
好的，接下来就是本萌新的第一篇博客啦。
直接上深搜！
深度优先搜索（Depth-First-Search），简称“深搜”（dfs），是我们蒟蒻们最基本的搜索操作之一。
简单地说，深搜就是递归。
下面是抄来的解释：
深度优先搜索用一个数组存放产生的所有状态。
（1） 把初始状态放入数组中，设为当前状态；
（2） 扩展当前的状态，产生一个新的状态放入数组中，同时把新产生的状态设为当前状态；
（3） 判断当前状态是否和前面的重复，如果重复则回到上一个状态，产生它的另一状态；
（4） 判断当前状态是否为目标状态，如果是目标，则找到一个解答，结束算法。
（5） 如果数组为空，说明无解。
如果你看不懂，哦，好的，你可以继续看下去了。（当然如果你看懂了，大佬我们可以做朋友嘛?)
下面是一个图解：
假如，我们需要从A走到G去，实线代表的是我们可以走的路。
那么我们可以怎么走？
这种情况下，我们就只能从A>B>C>D>E>F>G这一条路去走，这没有多余方法，所以很简单。
但是这种情况我们就可以有多种选择从A走出。而我们又不知道该怎么走才能到达G点，那么我们选择一直走我们没走过的路，这样就有可能到达G。
比如，我们可以从A到达B，C，D三个点，这是我们选择E点。
当我们从A走到E后，又可以到B,C,D,F四个点，于是我们走到B点。
当我们到达B过后，发现有三条路，分别指向A,C,E三点。
因为我们不走回头路！所以只能走到C点。
当我们走到C过后，有通往B,E,G的三个点的路，我们就可以直接走到G点了。
由此看来这种“不走之前走过的老路”的方法是寻找一条路一直走到终点的。
虽然这种方式可能“绕远路”，但当我们只求到到达目标“不求最快”并且可以“闲心散步”时，这不错的选择。
（一路头铁肝到底！！！！！）
这就是深搜哦！
下面是深搜思路：
1.把所有点标记为“未走过”；//把数组全标记为0或者其他
2.找到起点，终点并看看可以走到哪里；//准备循环
3.选择一节点并判断本节点是否走出地图；//
4.判断这一节点走过没啊；//3、4两步是判断走到该节点是否合法
5.如果没走过就走进该节点；//标记该节点
6.再寻找下一个节点；//深入下一层搜索
7.走到头了就可以回头了//得到返回这就可以回溯了
再附加一道深搜题目：（摘自洛谷 P1219 八皇后// 其实还是来自USACO的！）
P1219 八皇后
题目描述
检查一个如下的6 x 6的跳棋棋盘，有六个棋子被放置在棋盘上，使得每行、每列有且只有一个，每条对角线(包括两条主对角线的所有平行线)上至多有一个棋子。
上面的布局可以用序列2 4 6 1 3 5来描述，第i个数字表示在第i行的相应位置有一个棋子，如下：
行号 1 2 3 4 5 6
列号 2 4 6 1 3 5
这只是跳棋放置的一个解。请编一个程序找出所有跳棋放置的解。并把它们以上面的序列方法输出。解按字典顺序排列。请输出前3个解。最后一行是解的总个数。
//以下的话来自usaco官方，不代表洛谷观点
特别注意: 对于更大的N(棋盘大小N x N)你的程序应当改进得更有效。不要事先计算出所有解然后只输出(或是找到一个关于它的公式），这是作弊。如果你坚持作弊，那么你登陆USACO Training的帐号删除并且不能参加USACO的任何竞赛。我警告过你了！
输入格式
一个数字N (6 <= N <= 13) 表示棋盘是N x N大小的。
输出格式
前三行为前三个解，每个解的两个数字之间用一个空格隔开。第四行只有一个数字，表示解的总数。
输入输出样例
输入 #1
6
输出 #1
2 4 6 1 3 5
3 6 2 5 1 4
4 1 5 2 6 3
4
说明/提示
题目翻译来自NOCOW。
USACO Training Section 1.5
下面是香香源码哦！
源代码：
#include//万能头文件刚住；
using namespace std;//引用不解释；
int h[15],l[15],zx[30],yx[30],N,cnt;
//h==行，l==列，zx==左斜线，rx==右斜线，N是棋盘大小， cnt记录次数；
void dfs (int x)//深度搜索当然是dfs啦
{
if (x>N)//当放满了棋盘的每一行当然就放完了！
{
++cnt;
if (cnt<=3)
{
for(int i=1;i<=N;i++)
cout< cout< }
}
else//没放完就滚下来继续刚啊
for(int i=1;i<=N;i++)
{
if(l[i]||zx[x-i+N]||yx[i+x])
//如果这个格子的同列，同左斜，同右斜上有棋子（被标记为1）
continue;//就 再尝试下一个格子
l[i]=zx[x-i+N]=yx[i+x]=1;//没有标记过就标记嘛
h[x]=i;//存上
dfs(x+1);//再搜索下一行
l[i]=zx[x-i+N]=yx[i+x]=0; //溯源
}
}
int main()//主函数 好短啊。。。。
{
cin>>N;
dfs(1);//直接开始搜索第一排
cout< return 0; //OK收工
}
好啦，本萌新新的第一篇博客就到这里啦！
深度搜索DFS！
京公网安备 11010802041100号