## 搜索

### STL队列

>queue \<type\> name;
>
>queue.pop()
>
>queue.front()
>
>queue.back()
>
>queue.empty()
>
>queue.size() 



### 广度优先

图的BFS——在前面的层次一定先访问

树层次遍历，便是树的BFS

算法思想：通过队列，当访问一个节点的时候，先访问该节点，然后将该节点的左右儿子分别入队列

```
queue  <int>  Q创建一个队列

Q.push (root)//根节点加入队列

while (!Q.empty())//队列不空

{

node=Q.front()//获得队首元素

Q.pop()//队首元素出队

print(node.val)//输出当前节点的值

if node.left!=0

Q.push(node.left)//该节点的左儿子不空，将左儿子放入队列

if node.right!=0//该节点的右儿子不空，将右儿子放入队列

Q.push(node.right)

}
```





做标记

一个电梯，可以停在任意一层，并且每个楼层有一个Ki，电梯只有两个按钮，当你在第i层，你如果按下up按钮，上升Ki层或者DOWN下降ki层，可以得出状态转移图。

当你在A楼而去B楼，至少按下UP或者DOWN多少次？

**有向图找最短路径。**

状态转移的概念。

因此单论最短路径，是**贪心 + 优先队列**

**有向无权图的最短路则是BFS。即层次遍历。**

```
#include <bits/stdc++.h>
using namesapce std;
int N,Start,End;
int a[202];// 每一楼层的数字（上升或者下降ki）
int vis[202];//访问，做标记
struct pos
{
int level;//楼层
int steps;//步数
}
void bfs();


int main ()
{
while (scanf("%d ",&N)==1)
{
if (N==0)break;
scanf("%d%d",&Start,&End)//开始与目标楼层
for (int i=1;i<=N;i++)
{
scanf("%d",&a[i]);
vis[i]=0;
}

bfs();
}
return 0;
}

void bfs()
{

pos cur,nex;
cur.level=Start;
cur.steps=0;
queue<pos>qu;
qu.push(cur);
vis[Start]=1;
while(!qu.empty())
{
cur=qu.front();//取出队首
qu.pop();
//当前楼层是否为目标楼层
if (cur.level==End)
{
printf("%d\n",cur.steps);
return ;
}
//往上走
nex.level=cur.level+a[cur.level];
next.steps=cur.steps+1;
if (next.level<=N)
{if (vis[nex.level]==0)
{
vis[nex.level]=1;
qu.push(nex);
}
}
//往下走
nex.level=cur.level-a[cur.level];
nex.steps=cur.steps+1;
if (nex.level>=1)
{if (vis[nex.level]==0)
{vis[nex.level]=1;
qu.push(nex);

}
}

}
printf("-1\n");
return;
//如果没有可选项，就-1
}
不空，取出队首元素，不是的扩展楼层
```

每个楼层对应一个状态





**倒可乐**

两个杯子，容量分别是N,M,可乐的体积为S，S==N+M，N≠M

它们三个能互相倒可乐，如果能平分，请输出倒可乐的最少次数

动态规划和搜索都是状态转移，有转移的规则

只要有搜索

每个节点都是一个状态，即三杯水量+当前倒水最少次数

如何优化、剪枝？已经访问的节点不再访问，判断标记是否重复

即前一个问题

{if (vis[nex.level]==0)

{vis[nex.level]=1;



如何结束？——两个杯子量相同，剩下一个为0

只要有状态（节点）、转移（边），就是一个无权图，可以用搜索的方法（DFS/BFS）

隐式图

i杯内的水量容量大于j的杯内大于j水杯内倒满所需的容量x，则——i-x， j+x

六种方式



**国际象棋**

起始位置为a，目标位置为b，计算从a到b路上骑士移动的最少次数。走日字。

状态：骑士位置

转移：8段程序要写。能不能简化呢？

定义一个坐标差的数组即可，$\{(+1,-2),(+2,-1)...\}$

然后$dir[x][y]$数组来遍历

BFS基本思想：

从状态S开始，利用规则，生成所有可能的状态，构成树的下一层节点。

检查是否出现目标状态G，若未出现，就对该层所有状态节点，分别利用规则，生成再下一层所有状态的节点。一层层往下展开，直到出现目标状态。

查找有两种情况，一种是查找，另一种是遍历，遍历所有情况嘛。

当你有学习的热情，去珍惜这种热情

```
bfs(node root,node target)
{
memset(visit,0,sizeof(visit))
queue<node> Q;
Q.push(root);
visit[root]=1;
while (!Q.empty())
{
Node a=Q.front();
Q.pop();
if (a==target)
return a;
for (a 转移的所有可能状态)
	if (visit[b]) {continue;}
	Q.push(b);
	visit[b]=1;//剪枝，确保每个状态只进队列一次
	
}
return NULL;
}
```

剪枝：搜索的过程是一个搜索树，因为是重复的状态，会造成计算浪费，因此去掉这一枝





### 深度优先

二叉树的遍历

1. 先根遍历（根左右）
2. 中根遍历（左根右）
3. 后根遍历（左右根）

图的DFS呢？

从递归说起,斐波那契数列

为什么深度优先是递归？

首先分析问题的“递归特征”

先写停止结果（不需递归的特殊情况）

再写普通情况（递归）

递归代码简洁但是效率较低



n个数全排列

input 3

output$$A_{3}^{2}$$。

如果前k个数已经排好，剩余的问题就是n-k个 数的全排列。

```
int n;
int num[10],vis[10];
void dfs(int step);
int main()
{
while(scanf("%d",&n)==1)
{
memset(vis,0,sizeof(vis));
dfs(1);//接下来处理第一步(第一位)
}
return 0;

}
void dfs (int step)
{if (step==n+1)
{
for (int i=1;i<=n;i++)
{printf(num[i]);
return ;
}
for (int i=1;i<=n;i++)
{
if (vis[i]==0)
{
num[step]=i;
vis[i]=1;
dfs(step+1);
vis[i]=0;//回溯
}
}

}
step的作用?——正在处理第i位
vis的作用?——第i位上是否有用过？如果没用过,vis[i]=1,则在num[step]=i
(事实上,在数组里num[step]=arr[i],只不过这里简化成了i。因为就是按索引1，2，3,1-N的全排列这样排的，如果是2-N的全排列，就要用arr[i]了)


```

1、2、3之后：

vis:1 0 0，即2、3没被利用

def(2),但是i=3

那么num=1 3 （3）

深度优先搜索的关键在于解决“当下如何做”

至于下一步怎么做，则与当前一样

```
void dfs(int step)
{
if 终止条件（一般是结束递归的情况）
{特殊情况处理}
枚举当前的每一种可能for (i=1;i<=n;i++)
 {枚举的每一种可能中，递归dfs(step+1);}

}
```

[Problem - 1010](http://acm.hdu.edu.cn/showproblem.php?pid=1010)

S:开始

X:墙不能通过

D:出口

. :一般路径

每1s走上下左右，但是格子1s之后就消失

5s正好开门，求路径。

1. 如果在5s后才关闭？利用BFS求最快到达门的时间

2. 5s后才开门呢？

不一样

必须要刚刚好呢？用BFS只能求得最短的时间。

迷宫搜索问题

DFS，如果还用BFS无效搜索较多。

走过的地方做标记，只能求最短。

如果还需要绕一下？BFS只能求出最短的5s，但是9s的可能性呢？所以不能BFS剪枝了BFS剪枝就是做标记嘛。

剪枝条件？

剪枝是在走索的过程中根据你的知识判断后面不用再搜了。

BFS的剪枝容易想到

DFS呢？

如果可走的block总数小于时间，将会产生什么情况？

走不通。

443？也不行，曼哈顿距离为5.

动态规划的剪枝和深度规划的剪枝的区别是什么？

后面不用再搜了，直接得出结论。

奇偶性剪枝

> 行数+列数如果是奇数为1，否则偶数为0
>
> 0的四周为1，1的四周为0
>
> 从0走一步必然到1，从1走一步必然到0
>
> 从而从0到1（1->0）必然奇数，从0->0(1->1)必然偶数
>
> 可以直接判断不可达



行数n、列数m和时间t（也对应着步数），然后就是SXD的字符串

```C++
char Map[9][9];
int n, m, t, di, dj;
bool escape;
int dir[4][2] = {{0, -1}, {0, 1}, {1, 0}, {-1, 0}};
void dfs(int si, int sj, int cnt);
int main()
{
    int i, j, s1, sj;
    while (cin >> n >> m >> t)
    {
        if (n == 0 && m == 0 && t == 0)
            break;
        int wall = 0;
        for (i = 1; i <= n; i++)// 读地图
        {
            for (j = 1; j <= m; j++)
            {
                cin >> Map[i][j];
                if (Map[i][j] == 'S')
                {
                    si = i;
                    sj = j;
                }
                else if (Map[i][j] == 'D')
                {
                    di = i;
                    dj = j;
                }
                else if (Map[i][j] == 'X')
                {
                    wall++
                }
            }
        }
        if (n * m - wall <= t)//走遍所有格子也到达不了时间，剪枝
        {
            cout << "NO" << endl;
            continue;
        }
        escape = 0;
        Map[si][sj] = 'X';//一旦出发不能再经过，即变成墙
        dfs(si, sj, 0);
        if (escape)
            cout << "YES" << endl;
        else
            cout << "NO" << endl;
    }
    return 0;
}


void dfs(int si,int sj,int cnt)//cnt：花了几秒
{
int i,temp;
if (si>n || sj>m || si<=0 || sj<=0) return;//出地图之外
if (cnt==t && si=di && sj=dj) escape=1;//到达目的地
if (escape) return; 
temp=(t-cnt)-[abs(si-di)+abs(sj-dj)];//当前到门的最短距离，没有障碍物的情况下
if (temp<0 ||temp%2==1) return ;
/*
因为剩余可用步数/路径长度（t-cnt）和曼哈顿距离(后两者之和，当前位置到目标位置最短可能路径长度)奇偶性一致

temp表示如果走最短路到终点，还能剩余多少“自由步”（必须通过绕路消耗掉）。
因此 if (temp % 2 == 1) return; 就是判断多出的步数是奇数，无法通过往返消耗，必然无法在正好 R 步到达终点。
t：开门时间
cnt：用的时间
剩余的时间-剩余的距离
如果剩余的时间（剩余路径）是奇数，那么剩余的距离一定是奇数
因为走了t-cnt步之后必须到终点，而这个距离是0偶数
也可以换句话说，曼哈顿距离是剩余距离的一部分，都是当前位置到最终位置，那么奇偶性一定相同
有必要每次都判断吗？
因此不需要在递归中判断，因为每次递归都是同样变化的，只需要放在主函数里。

*/
for (i=0;i<4;i++)
{
	if (Map[si+dir[i][0]][sj+dir[i][1]]!='X')
	{
		Map[si+dir[i][0]][si+dir[i][1]]='X';
		dfs(si+dir[i][0],sj+dir[i][1],cnt+1);
		Map[si+dir[i][0]][sj+dir[i][1]]=".";//为什么又改回来了？因为这是递归啊！后悔了肯定是要变回去的。悔棋就是搜索嘛。能够返回到这一步，说明后面的搜索是失败的。
	}
}
	return;
}
```

先写结束递归的条件，再写递归

仍然是斐波那契数列

普通的dfs:

```
int dfs(int n)
{
if (n==1||n==2) return 1;
else return (dfs(n-1)+dfs(n-2))%100000007;//做了重复计算，所以要用动态规划
}
```

动态规划的数组+递归（深搜）——记忆化搜索（记忆化DP,记忆化DFS），也是DP的一种。

记忆化搜索 = 用 DFS（递归）实现的动态规划（Top-Down DP，自顶向下）

           动态规划（思想）
             /        \
            /          \
    记忆化搜索（Top-Down）递推DP（Bottom-Up）+循环
         ↑
        数组 + 递归


既有用到存储空间数组，又用到递归的简洁。

递归只是：

> **函数调用自己的一种写法**

它解决的是：

代码如何表达问题

**DFS**（深度优先搜索）

DFS 是：

> **按照一条路径一直往下探索状态**，一种搜索策略，对应的是广度优先搜索

通常用递归写。

所以：

DFS ≈ 递归实现的搜索策略

动态规划（DP）

动态规划是一种 **思想**：

> 如果同一个状态会被多次求解，就保存结果。

DP 关注的是：

状态是否重复

**记忆化搜索（Memoization Search）**：是一种通过存储已经遍历过的状态信息，从而避免对同一状态重复遍历的搜索算法。

记忆化搜索是动态规划的一种实现方式。在记忆化搜索中，当算法需要计算某个子问题的结果时，它首先检查是否已经计算过该问题。如果已经计算过，则直接返回已经存储的结果；否则，计算该问题，并将结果存储下来以备将来使用。

```
int dfs(int n)
{
if (fib[b]) return fib[n];
if (n==1 || n==2) fib[n]=1;
else fib[n]=(dfs(n-1)+dfs(n-2))%1000000007;
return fib[n];
}
```

为什么不都用记忆化DFS？有些量不好表示，并且量并不多，依然用DFS。

「记忆化搜索」与「递推」都是动态规划的实现方式，但是两者之间有一些区别。

> **记忆化搜索**：「自顶向下」的解决问题，采用自然的递归方式编写过程，在过程中会保存每个子问题的解（通常保存在一个数组或哈希表中）来避免重复计算。
>
> - 优点：代码清晰易懂，可以有效的处理一些复杂的状态转移方程。有些状态转移方程是非常复杂的，使用记忆化搜索可以将复杂的状态转移方程拆分成多个子问题，通过递归调用来解决。
> - 缺点：可能会因为递归深度过大而导致栈溢出问题。
>
> **递推**：「自底向上」的解决问题，采用循环的方式编写过程，在过程中通过保存每个子问题的解（通常保存在一个数组或哈希表中）来避免重复计算。
>
> - 优点：避免了深度过大问题，不存在栈溢出问题。计算顺序比较明确，易于实现。
> - 缺点：无法处理一些复杂的状态转移方程。有些状态转移方程非常复杂，如果使用递推方法来计算，就会导致代码实现变得非常困难。

适合使用「记忆化搜索」的场景：

1. 问题的状态转移方程比较复杂，递推关系不是很明确。
2. 问题适合转换为递归形式，并且递归深度不会太深。

适合使用「递推」的场景：

1. 问题的状态转移方程比较简单，递归关系比较明确。
2. 问题不太适合转换为递归形式，或者递归深度过大容易导致栈溢出。

记忆化搜索解题步骤

我们在使用记忆化搜索解决问题的时候，其基本步骤如下：

1. 写出问题的动态规划「状态」和「状态转移方程」。
2. 定义一个缓存（数组或哈希表），用于保存子问题的解。
3. 定义一个递归函数，用于解决问题。在递归函数中，首先检查缓存中是否已经存在需要计算的结果，如果存在则直接返回结果，否则进行计算，并将结果存储到缓存中，再返回结果。
4. 在主函数中，调用递归函数并返回结果。

老鼠和奶酪。

城市可以看作一个n*n的网格，在每个网格的洞里，老鼠存储了0~100块的奶酪。现在，它在（0，0）位置，每次吃完便上下左右四个位置，但是，有只猫在洞的附近，所以每次在被猫抓住之前最多能移动k个位置，每次它必须移动到一个比这次有更多奶酪的网格。

给定n和k以及每个奶酪的数量。

老鼠最多能吃到多少块奶酪（直到不能继续活动）？

df(x,y)，从起点(0,0)到(x,y)的最大值 or 从起点(0,0)到走不动的最大值

后者，因为不能确定最终停在哪里。只要输出df(0,0)即可。

那么搜索的过程中？

下一次走的位置必须比上一次大

最多k步

普通dp如何处理？

非线性问题线性化，会造成十分多的重复

递推呢？要先将二维网格转换为线性的

记忆化搜索

```
int dfs(int x,int y){
int answer = 0;
if (ans[x][y])return ans[x][y];
for (int i= 0;i <4;i++)
	for (int j= 1;j <= k;j++) 
	{int xx=x+ dis[i][0] * j;
	int yy=y+ dis[i][1] * j;
	if (OK(xx, yy) && init[xx][yy]>init[x][y])
	answer = max (answer, dfs (xx, yy));
	}
	ans[x][y] = answer + init[x][y];
	return ans[x][y];}
	
int init[102][102];
int ans[102][102];
int dis[4][2]={ 0,1,1,0,0,-1,-1,0 };
int n, k;
bool OK(int x,int y) {
if (x<0 || x>=n ||y<0|| y>=n)
	return false;
return true;
}

int main()
{}
```



不需要做标记，因为总会往更大的去

{于是要用}

每个方向都有k，于是有4k中情况

这个时候要比较的是max，取最大值

这个answer得到的当前走到下一个位置最大的值

下一步能不能走到最优解

从起点到(x,y)

从(x,y)到最后（但是不知道最后的坐标）

从(x,y)到达目标的所有路径

![image-20260306225304545](https://chenalna.oss-cn-hangzhou.aliyuncs.com/img/image-20260306225304545.png)

```
int mp[102]L1021;
int ans[102][102];
int n,m,t;
int dfs(int x,int y)
{ if(ans[x][y]>=0) return ans[x][y]:
ans[x][y]=0;
for (int i=0;i<=mp[x][y];i++)
for (int j=0;j<=mp[x][y]-i;j++)
{if(x+i>=1&&x+i<=n&&y+j<=m&&y+j>=1)
ans[x][y]=(dfs (x+i,y+j)+ans[x][y])%10000;
return ans[x][y];}

int main{
Scanf ("%d",&t);
while(t--)
{ scanf("%d%d",&n,&m);
memset (ans,-1,sizeof (ans));
for (int i=1;i<=n;i++)
for (int j=1;j<=m; j++)
scanf ("%d",&mp[i][j]);
ans[n][m]=1;
printf("%d\n",dfs (1,1)):
}
return0:
}
```

##