深度优先搜索
深度优先搜索 DFS
定义：是一种枚举所有完整路径以遍历所有情况的搜索方法。
如何实现DFS:
可以使用递归来实现DFS。使用递归系统会调用叫系统栈的东西存放递归中的每一层状态，本质还是栈实现。
深度优先搜索的基本模型
void dfs(int step)
{
判断边界
尝试每一种可能 for(i=1;i<=n;i++)
{
继续下一步 dfs(step+1)
}
返回
}
例子：
-
全排列（DFS思想）：
输出自然数 1 到 n所有不重复的排列，即 n 的全排列，要求所产生的任一数字序列中不允许出现重复的数字。。
#include<stdio.h> int a[10], book[10], n; void dfs(int step)//step表示站在第几个盒子前面 { int i; if (step == n + 1)//如果站在第n+1个盒子前面，则表示前n个盒子已经放好扑克牌 { //输出一种排列（1-n号盒子中的扑克牌编号） for (i = 1; i <= n; i++) printf("%d ", a[i]); printf("\n"); return;//返回之前的一步（最近一次调用dfs函数的地方） } //此时站在第step个盒子面前，应该放那张牌呢？ //按照1、2、3...n的顺序一一尝试 for (i = 1; i <= n; i++) { //判断扑克牌i是否还在手上 if (book[i] == 0)//book[i]等于0表示i号扑克牌在手上 { //开始尝试使用扑克牌i a[step] = i;//将i号扑克牌放入到第step个盒子中 book[i] = 1;//将book[i]设为1，表示i号扑克牌已经不在手上 //第step个盒子已经放好扑克牌，接下来需要走到下一个盒子面前 dfs(step + 1);//这里通过函数的递归调用来实现（自己调用自己） book[i] = 0;//这是非常重要的一步，一定要将刚才尝试的扑克牌收回，才能进行下一次尝试 } } return; } int main() { scanf_s("%d", &n);//输入的时候要注意n为1-9之间的整数 dfs(1);//首先站在1号小盒子面前 return 0; }
-
八皇后 Checker Challenge
一个如下的 6×6 的跳棋棋盘，有六个棋子被放置在棋盘上，使得每行、每列有且只有一个，每条对角线（包括两条主对角线的所有平行线）上至多有一个棋子。
上面的布局可以用序列 2 4 6 1 3 5 来描述，第 i 个数字表示在第 i 行的相应位置有一个棋子，如下：
行号 1 2 3 4 5 6
列号 2 4 6 1 3 5
这只是棋子放置的一个解。请编一个程序找出所有棋子放置的解。
并把它们以上面的序列方法输出，解按字典顺序排列。
请输所有的解。最后一行是解的总个数。
#include<stdio.h>
int n,cnt;//cnt：计数器
int lie[20];//列
int u[40];//左上到右下
int v[40];//右上到左下
int a[20];//记录路径
void pr()
{
for (int i = 1; i <= n; i++)
{
printf("%d ", a[i]);
}
printf("\n");
}
void dfs(int x)//x:行
{
if (x ==n+1 )
{
pr();
cnt++;
return;
}
for (int i = 1; i <= n; i++)
{
if (!lie[i] && !u[x - i + n] && !v[x + i])//u：行减列为定值（加n防止数组越界）；v：行加列为定值
{
a[x] = i;
lie[i] = 1;
u[x - i + n] = 1;
v[x + i] = 1;
dfs(x + 1);
lie[i] = 0;
u[x - i + n] = 0;
v[x + i] = 0;
}
}
return;
}
int main()
{
scanf_s("%d", &n);
dfs(1);
printf("%d", cnt);
return 0;
}
-
迷宫（DFS思想）
给定一个N*M方格的迷宫。给定起点坐标和终点坐标，问: 每个方格最多经过1次，有多少种从起点坐标到终点坐标的方案。在迷宫中移动有上下左右四种方式，每次只能移动一个方格。数据保证起点上没有障碍。
*输入格式：*第一行输入N和M，N为行，M为列。接下来的n行m列为迷宫，0表示空地，1表示障碍物。最后一行输入起点坐标SX,SY，终点坐标FX,FY。
*输出格式：*给定起点坐标和终点坐标，问每个方格最多经过1次，从起点坐标到终点坐标的方案总数。
#include<stdio.h>
int n, m, fx,fy,cnt;
int a[51][51], book[51][51];
void dfs(int x, int y, int step)
{
//方向数组（上、下、左、右）
int xx[] = { 1,0,-1,0 };
int yy[] = { 0,-1,0,1 };
int tx, ty;
if (x == fx && y == fy)//判断是否到达终点
{
cnt++;//次数加一
return;
}
for (int k = 0; k <=4; k++)
{
//计算下一个点的坐标
int tx = xx[k] + x;
int ty = yy[k] + y;
//判断是否越界，是否为障碍物，或者是否已经在路径中
if (tx >= 1 && tx <= n && ty >= 1 && ty <= m && !a[tx][ty] && !book[tx][ty])
{
book[tx][ty] = 1;//标记这个点已经走过
dfs(tx, ty,step+1);//开始尝试下一个点
book[tx][ty] = 0;//尝试结束，取消这个点的标记
}
}
return;
}
int main()
{
int sx, sy;
scanf_s("%d%d", &n, &m);//n为行，m为列
//读入迷宫
for (int i = 1; i <= n; i++)
{
for (int j =1; j <= m; j++)
{
scanf_s("%d", &a[i][j]);
}
}
scanf_s("%d%d%d%d", &sx, &sy, &fx, &fy);//读入起点和终点坐标
//从起点开始搜索
book[sx][sx] = 1;//标记已经在路途中，防止后面重复走
dfs(sx, sy, 0);
printf("%d",cnt);//输出方案总数
return 0;
}