前言
在说搜索方式之前
先讲一个简单的问题：求数的全排列
比如说，123 的全排列就是：123、132、213、231、312、321
这很简单吧
全排列的个数就是这个数的位数的阶乘，即 123 的全排列的个数是 （ 3！=3×2×1）
假如要用 C 语言来写呢？
应该很快就能想到，3个for循环嘛
分别控制位上的数字不重复就行了
那么假如数字更大一点呢？
比如说 123456789
一共九位，那么这个数的全排列的个数就是 （ 9！= 362880）
实际上这个数字的全排列是能用 9 个for循环写出来
不过那样看着是十分臃肿麻烦的
下面就通过学习一下深度搜索，来给这样的问题寻找一下新的思路吧
深度优先搜索
简单的说就是一条路走到底，碰壁再退回找其他路
先用 123 的全排列来举个例子
先开一个数组嘛，int num[10]（方便理解，这里就不用0下标了）
先从第一个格子（num[1]）开始：能放入的数字有三个,分别为1，2，3
走到第二个格子：能放入的剩下两个，如果前面放了1，那么现在能放2，3
走到第三个格子：能放的只剩下一个了
最后走到第四个格子：哦？现在手里没数字了，那就说明一个排列组合已经形成
这个时候你要形成一个新的排列组合，最简单的方式是什么呢？
没错，拿起离你最近的数字，往后面退，看是否有能交换顺序的数字
（这也应该是高中数学求排列组合的一种基本方式了
有了这个思想，我们尝试将其转化为代码实现👇
#include<stdio.h>
int num[10];//各个位上的数字，默认为零
int hand[10];//手中的牌,下标对应数字，值0就是有，1就是没有
int n;
void func(int count)//cnt表示站在第几个盒子面前
{
if (count == n + 1)//假如走到最后一位的外面去了，那么说明排列完毕
{
for (int i = 1; i <=n; i++)
{
printf("%d", num[i]);
}
printf("\n");
return;
}
for (int i = 1; i <= n; i++)
{
if (hand[i] == 0)//手上有这张牌，就放进去
{
num[count] = i;
hand[i] = 1;
//接着进入下一个盒子
func(count + 1);//递归
hand[i] = 0;//func在return之后将格子里的数字要拿出来，这步很重要
}
}
return;
}
int main()
{
scanf_s("%d", &n);
func(1);
return 0;
}
假如我们输入一个5，
那么运行结果就是这样的👇
具体来看看代码吧，（假如要用for循环的话，估计你还没敲到一半，我已经敲完了👌
这段代码的核心就在于递归（自己调用自己
好了（这一句话隔着上一句话已经十多分钟了，一直在组织语言如何更准确的表达整个过程😂
5 位数不太好表达，这里还是用 3 位数 123 来分析一下原理
123 是如何重新排列为 132的？以及递归在这个过程中起到的作用：
假如我们要求的是 123 的全排列，使用上面的代码，进行逐层分析
首先有至少4个格子叭
我们从第一个格子开始，有一个从 1 到 3 的 3 次循环，选取手中有的牌并且放入格子，然后立马进入第二个格子，这时（第一个格子的循环是仍然存在的，只是停留在了 1 ）
到了第二个格子，又是一个从 1 到 3 的 3 次循环，重复上面的操作，然后进入第三个格子
进入了第三个格子，还是有一个 3 次循环，如果是第一次形成排列（123）
，那么循环从 1 到 3 ，在3的时候刚好结束，然后走到了第四个格子，完成一次排列
关键点来了，由于这是一个递归过程，完成排列后手里会收回相应格子使用过的牌
此时，第三个格子的循环已经结束，但是第二个格子的循环还没结束呢
第一个排列的时候，第二个格子的循环刚好走到 2 是吧，接下来就是第三次循环（2是被收回了的），由于第三个格子刚好收回了数字 3，那么第二个格子就放进去 3 ，根据代码，能放进去就会移动到下一个格子，并且开启新的循环选择，第三个格子刚好选到 2 ，那么就形成了新的排列（132）
可能会有疑问，开启第三个格子的新循环时，为什么没有选择到 1 ？
答：仔细观察代码，在循环中，拿回手牌的时间在后一个格子执行完毕之后，第二个格子开始只进行了第二次循环选择了2，剩了一次循环，第二个格子选择完 2 后由于循环并没有结束，所以并没有return回到第一个格子那里，也就是第二个格子的func函数没有执行完毕，因此第一个格子中的 1 是不会被收回的。
（深吸一口气）😫
其实这个代码的核心行也不过 20 行，却饱含深度优先搜索的基本模型
本质上还是依赖循环，只不过减少了许多不必要的遍历
理解的关键就在于：当下应该怎样做？以及深度优先这个词的概念
一个基本的深度优先搜索的基本模型👇
void dfs(int step)
{
//判断边界
for (int i = 1; i <= n; i++)//尝试每一种可能
{
//继续下一步
dfs(step + 1);
}
//返回
}说点题外的，递归这个东西可能理解起来会有点抽象
这里简单的举个例子，用于理解递归逻辑
#include<stdio.h>
int n;
void func(int x)
{
if (x < n)
{
int t;
scanf_s("%d", &t);
func(x + 1);
printf("%d", t);
}
return;
}
int main()
{
scanf_s("%d", &n);
func(0);
return 0;
}上面这段代码，输入一个数字的长度，然后输入相应位数，然后倒序打印
只不过用了递归的思想
就这个例子而言，scanf输入，func递归调用，printf打印，这三步是最关键的
先进入func，录入一个数字之后进入下一个位置，此时printf的函数就被搁置，然后继续录入……
可以看作这样一个过程：从左到右每一位都执行了func函数，但是都没有执行完毕，只有最后一位录入后，才从最后开始倒着往前结束之前的函数
用代码来看大致是这样👇
scanf_s("%d", t1);
{
scanf_s("%d", t2);
{
scanf_s("%d", t3);
printf("%d", t3);
}
printf("%d", t2);
}
printf("%d", t1);可以看到虽然 t1 是最早录入的，但是确实最晚打印的，123便倒序为321
走迷宫
学习搜索，就离不开迷宫
简单的来说迷宫就是一个二维数组，用数值来区分障碍和道路
上面已经学习了深度优先的搜索方式
这里就简单的实践一下
题目：生成一个迷宫，保证迷宫有解，设立起点坐标和目标坐标，一步走一格，求起点到目标的最短路径
先想想吧，离不开基本模型
直接上代码👇
#include<stdio.h>
int a[51][51];
int mark[51][51];
int n, m;//n为行，m为列
int startx, starty, endx, endy;
int min = 999999999;
void func(int x, int y, int step)
{
int next[4][2] = { {0,1},//向右
{1,0},//向下走
{0,-1},//向左走
{-1,0}//向右走
};
int tx, ty, k;
if (x == endx && y == endy)
{
if (step < min)
{
min = step;
}
return;
}
for (int k = 0; k <=3; k++)//模拟上下左右 四种走法
{
tx = x + next[k][0];
ty = y + next[k][1];
//还要判断是否越界
if (tx <1 || tx >n || ty <1 || ty > m)
continue;//越界就不考虑这一种走法了
if (a[tx][ty] == 0 && mark[tx][ty] == 0)//判断没走过的空地
{
mark[tx][ty] = 1;//标记为走过
func(tx, ty, step + 1);
mark[tx][ty] = 0;//这两步似曾相识吧
}
}
return;
}
int main()
{
scanf_s("%d %d", &n, &m);
for (int i = 1; i <=n; i++)
{
for (int j = 1; j <=m; j++)
{
int t;
scanf_s("%d", &t);
a[i][j] = t;
}
}//录入迷宫，0为空地，1为障碍物
scanf_s("%d %d %d %d", &startx, &starty, &endx, &endy);//录入起点和终点
mark[startx][starty] = 1;
func(startx, starty, 0);
printf("%d", min);
return 0;
}小结：深度优先搜索以深度为优先的原则进行遍历，因此会尽可能深入到图的某一分支，直到无路可走才回退。这使得深度优先搜索在寻找路径、判断连通性、找连通分量等问题上具有广泛应用。
需要注意的是，深度优先搜索可能陷入无限循环，因此在实现时需要考虑避免重复访问节点的情况，例如通过使用一个标记数组来记录节点的访问状态，也就是上面的mark数组起到的作用。
广度优先搜索
还是接着用迷宫这个模型来学习
深度优先搜索如其名，一条路走到尽头才回来
那么广度优先的话，肯定就不会一条路走到“死”啦
遇到选择时，会尝试每一种决策
可以想象为，原地转一圈看哪里可以走（写入计划里），按照计划顺序往外走一步，再转一圈后记下这时周围的情况（放到后面的计划里），然后退到上一步，看上一步的计划是否走完，如果没走完就继续上一步剩余的计划，重要的是，每走到一新位置，都要原地转一圈，将能走的写入计划，执行计划要按照先后顺序进行
举个例子（先不管坐标的问题，只是理解概念），我在起点先转一圈，发现能走 右边 和 下边，那么我就在计划里写上 right1，down1，之后执行计划向右走一步，发现能走的只有下边，便在计划后边加上 down2 ，那么现在计划就成了 【right1，down1，down2 】，第一个计划就这样完成，因为我们要优先尝试一个点的所有方式，所以这时候要退回到刚刚那个点，去完成刚那个点的剩余计划，于是进行down1计划
网上找了两张图，可以试着理解👇
如果我这里讲的不清楚的话，那就来看看代码的思路叭
广度优先肯定和深度优先是不一样的哦
由于广度优先追求的是一个广度，那么递归思想带来的“一冲到底”肯定就不能使用了
不过在之前的文章中，学习了队列的相关知识
看看上面我所说的《计划》这个词，是否能和队列联系起来呢？
上代码👇：
#include<stdio.h>
struct note //结构体实现队列
{
int x;
int y;
int s;
};
struct note queue[2501];
int head=1, tail=1;
int map[51][51];
int mark[51][51];//用于标记哪些路是走过的
int step = 0;
int main()
{
int next[4][2] = {
{0,1},
{1,0},
{0,-1},
{-1,0}
};//方向数组
int n, m,flag=0;
scanf_s("%d %d", &n, &m);//录入行、列
for(int i=1;i<=n;i++)
{
for (int j = 1; j <= m; j++)
{
int t;
scanf_s("%d", &t);
map[i][j] = t;
}
}//录入地图
int startx, starty, endx, endy;
scanf_s("%d %d %d %d", &startx, &starty, &endx, &endy);
mark[startx][starty] = 1;//先标记起点坐标
queue[tail].x = startx;
queue[tail].y = starty;
queue[tail].s = 0;
tail++;
while (head < tail)
{
for (int i = 0; i < 4; i++)//尝试四个方向
{
int tx = queue[head].x + next[i][0];
int ty = queue[head].y + next[i][1];
if (tx<1 || tx>n || ty<1 || ty>m)//判断是否越界
continue;
//如果不越界就加长队列
if (map[tx][ty] == 0 && mark[tx][ty] == 0)//没有障碍物，也没有走过的格子
{
mark[tx][ty] = 1;
queue[tail].x = tx;
queue[tail].y = ty;
queue[tail].s = queue[head].s + 1;
tail++;
}
if (tx == endx && ty == endy)
{
flag = 1;//只是一个标志变量，减少不必要的循环
break;
}
}
if (flag == 1)
break;//说明已经找到了
head++;//没有找到的话就后移head，继续重复这个过程
}
printf("%d", queue[tail - 1].s);
return 0;
}如果队列能够看懂的话，那这段代码应该没什么难度，只是初想可能想不到用队列来解决
小结：广度优先搜索从起始节点开始，逐层向外扩展，先遍历距离起始节点较近的节点，然后再访问离起始节点更远的节点。
与深度优先的不同点：广度优先搜索遍历过程中不会陷入无限循环，因为每个节点只被访问一次，并且按照距离起始节点的远近顺序进行访问。
海岛面积
题目：海岛面积
简言之，给一个地图录入海拔，0是海拔为0（就是海洋的意思），大于 0 就是相对应的海拔
给出一个海岛上的坐标，求这个海岛的面积
结合上面的广度优先搜索方式，做这道题就会十分简单了
上代码👇：
#include<stdio.h>
struct note
{
int x;
int y;
};
struct note queue[2501];
int head=1, tail=1;
int map[51][51];
int mark[51][51];//用于标记哪些路是走过的
int step = 0;
int max = 1;
int main()
{
int next[4][2] = {
{0,1},
{1,0},
{0,-1},
{-1,0}
};//方向数组
int n, m,flag=0;
scanf_s("%d %d", &n, &m);//录入行、列
for(int i=1;i<=n;i++)
{
for (int j = 1; j <= m; j++)
{
int t;
scanf_s("%d", &t);
map[i][j] = t;
}
}//录入地图
int startx, starty;
printf("请输入坐标：\n");
scanf_s("%d %d", &startx, &starty);
mark[startx][starty] = 1;//先标记起点坐标
queue[tail].x = startx;
queue[tail].y = starty;
tail++;
while (head < tail)
{
for (int i = 0; i < 4; i++)//尝试四个方向
{
int tx = queue[head].x + next[i][0];
int ty = queue[head].y + next[i][1];
if (tx<1 || tx>n || ty<1 || ty>m)//判断是否越界
continue;
//如果不越界就加长队列
if (map[tx][ty] != 0 && mark[tx][ty] == 0)//不能是海洋，而且没走过的
{
queue[tail].x = tx;
queue[tail].y = ty;
mark[tx][ty] = 1;//标记这个点
tail++;
max++;
}
}
head++;//没有找到的话就后移head，继续重复这个过程
}
printf("\n该点面积为:%d\n", max);
return 0;
}可以看出基本的模型吧
程序的执行结果👇
当然，利用深度优先也可以做出这道题
这里就不写代码了，有兴趣自己试试吧（困😩
