女娲补天之BFS与DFS

BFS

“它从一个起点开始，按照图的宽度层次遍历所有的节点，直到找到目标或者遍历完所有的节点为止。你可以把它想象成一个水波纹，从一个中心点向外扩散，每一圈都是一层。”

宽度优先搜索主要分为两类，第一种是最短距离问题，该类问题一般都是在（棋盘）内部搜索（比如走迷宫），另一类是最小步数问题，一般以整个棋盘作为一个状态整体去搜索不同的状态（比如八数码）。

由于宽搜的性质，其对于解决最小化问题有较强的针对性，其次相对于DFS不会有爆栈的风险，尤其是对于py来说。

宽搜的基本套路：
1. 确定队头元素并入队
2. 进入while队列不空的循环中
3. 弹出队头元素，并确定所有可能入队的点
4. 确定所有的判断条件（是否越界，是否入队过，是否能走等等），找出所有满足条件的点入队，并标记已被访问

注意事项：
1. 有时候状态是一个字符串，可能会用到字典dict
2. 如果题目要求出路径，只需要构造一个pre数组，使用while循环找出路径再（反向）输出。

刷题列表：

AcWing 844. 走迷宫

最短路模型

本题求棋盘内部最短移动次数，想到bfs，是最经典的最短距离问题。

队列中存储的是坐标，所以要传元组/列表进去。

每个点只能入队一次，按理来说需要一个st数组存储是否入队过，但这里要求存储移动次数，每次只有入队了才会统计移动次数，所以二者就能整合成一个dist[i][j]数组，只需要将数组中所有值初始化为-1表示没遍历过即可，dist同时表示从(1, 1)到(i, j)的移动的次数，每次在入队或出队时修改dist数组。

判断条件一共三个，第一个是约束不能出界，第二是该点不能是$1$，即墙壁，第三是这个点之前不能被搜索过，根据BFS的性质，每次向外拓展距离（出队元素）为1的点入队，如果这个点被搜过，说明已经是最短距离了，不能再入队。

def bfs(a, b):
    d[a][b] = 0
    q.append((a, b))
    while len(q) != 0:
        x, y = q[0][0], q[0][1]
        q.popleft()
        for i in range(4):
            nx, ny = x + dx[i], y + dy[i]
            if 1 <= nx <= n and 1 <= ny <= m and d[nx][ny] == -1 and g[nx][ny] == 0:
                d[nx][ny] = d[x][y] + 1
                q.append((nx, ny))
    return d[n][m]

最后返回起点到终点距离即可，d[n][m]

小技巧：
对于周围四个点（上下左右）的搜索，一般采用偏移量数组。

dx, dy = [-1, 1, 0, 0], [0, 0, -1, 1]

AcWing 1076. 迷宫问题

最短路模型拓展1：求路径

BFS要求输出路径，只需要将每一个位置（状态）的前一个位置（状态）存入pre数组中，然后根据终止的状态倒推回初始状态即可。

pre[a][b] = (t[0], t[1])

本题可以反向查找，这样输出的时候就相当于是正向输出了hhh，很神奇，也就是从终点搜到起点，再输出路径。

bfs(n - 1, n - 1)

x, y = 0, 0
while True:
    print(x, y)
    if x == n - 1 and y == n - 1: break
    x, y = pre[x][y]

AcWing 188. 武士风度的牛

最短路模型拓展2：马走棋

相较于模板题的上下左右四个方向，这里可以移动的方向变为了日字形，总共八个方向。

dx, dy = [-2, -1, 1, 2, 2, 1, -1, -2], [1, 2, 2, 1, -1, -2, -2, -1]

本题同样要求最小步数，所以用BFS。

用dist[i][j]来存储从原点移动到点(i, j)的步数，初始化为-1，将判重的st数组功能合并。

dist = [[-1] * N for _ in range(N)]

BFS如何找到终点退出？
在寻找新的点加入队列时进行判断，如果新的点等于终点，意味着下一步就要移动到终点了，输出dist[上一层] + 1

if a == xh and b == yh: return dist[t[0]][t[1]] + 1

搜寻新的点是否能够入队的判断条件仍然是三个
1. 新的点的坐标是否越界
2. 新的点是否能走（可能是障碍）
3. 新的点是否曾经走过（曾经入队过）

bfs完整过程：
(xk, yk)为起点坐标，(xh, yh)为终点坐标

def bfs():
    q.append((xk, yk))
    dist[xk][yk] = 0
    while q:
        t = q.popleft()
        for i in range(8):
            a, b = t[0] + dx[i], t[1] + dy[i]
            if a == xh and b == yh: return dist[t[0]][t[1]] + 1
            if a < 0 or a >= n or b < 0 or b >= m: continue
            if dist[a][b] != -1: continue
            if g[a][b] == '*': continue
            q.append((a, b))
            dist[a][b] = dist[t[0]][t[1]] + 1

洛谷 P1443 马的遍历

马走日简单版

注意BFS求最短路问题可以省略st数组，直接将距离数组初始化为-1。

AcWing 1100. 抓住那头牛

最短路模型拓展3：一维

不管是乘以2还是加一或是减一，每次操作花费的时间都是1，相当于路径都是$1$，符合BFS求最短路的模型

本题主要问题是，数组应该开多大，评论区得证只需要开70000多？刚刚没找到在哪里hhh
所以这里开两倍空间肯定够了

这里没有for循环枚举每一种情况了，需要三个if循环直接判断，如果新坐标满足不越界并且没有被访问过，就加入队列。

因为需要求最小操作数，同理初始化dist数组为-1，这里一维即可。

import collections
q = collections.deque()
N = 200010
dist = [-1] * N
def bfs(x):
    dist[x] = 0
    q.append(x)

    while q:
        t = q.popleft()
        if t == m: return dist[t]
        if 2 * t < N and dist[2 * t] == -1:
            q.append(2 * t)
            dist[2 * t] = dist[t] + 1
        if t + 1 < N and dist[t + 1] == -1:
            q.append(t + 1)
            dist[t + 1] = dist[t] + 1
        if t - 1 < N and dist[t - 1] == -1:
            q.append(t - 1)
            dist[t - 1] = dist[t] + 1

n, m = map(int, input().split())
print(bfs(n))

洛谷 P1135 奇怪的电梯

一维最短路问题

这里是一维的最短路，在电梯上或者下，虽然每一次能移动多层，但每次都是按一次按钮，可以看作BFS的最短路问题。

感觉自己写复杂了，可以在BFS中直接退出的，只要队列里popleft的是目标楼层，就直接返回d[b]即可。

这里数据范围不大，所以也过了。

def bfs():
    global a
    global b
    q = collections.deque()
    q.append(a)
    st[a] = True
    while q:
        t = q.popleft()
        for i in range(1, 3):
            nl = t + w[t] * ((-1) ** i)
            if 1 <= nl <= n and not st[nl]:
                d[nl] = d[t] + 1
                st[nl] = True
                q.append(nl)

    if d[b] == 0:
        return -1
    else:
        return d[b]

洛谷 P2895 Meteor Shower S

二维最短路问题

本题特殊的点在于如果保证每次走到的点在走的时候不被炸到？

之前想的是。。。md隔了两天忘了怎么想的了，反正非常复杂，用了多个矩阵存储信息。

但一看到题解的时候幡然醒悟。。太巧妙了吧

之前碰到的类似迷宫问题，经常会判断点上的值是什么，比如是#就代表墙壁，不能走，那么在这里，可以先把整个地图初始化为INF，然后对每个被炸的点（以及被波及的点）上的值改成其的爆炸时间，由于一个点可能会被波及多次，所以每次更新点上值的时候取一个min就好了，更新成最早爆炸的时间。

那么，只要我们的步数小于该点上的值（毕竟我们每次只走一步）就能移动，直到第一次碰到INF的点，说明找到了安全区。

真的太妙了，回看还是一样妙

def bfs():
    q = collections.deque()
    q.append((0, 0))
    st[0][0] = True
    while q:
        t = q.popleft()
        if time[t[0]][t[1]] == INF: return d[t[0]][t[1]]
        for i in range(4):
            nx, ny = t[0] + dx[i], t[1] + dy[i]
            if nx < 0 or ny < 0: continue
            if time[nx][ny] <= d[t[0]][t[1]] + 1: continue
            if st[nx][ny]: continue
            st[nx][ny] = True
            d[nx][ny] = d[t[0]][t[1]] + 1
            q.append((nx, ny))

    return -1

AcWing 1097. 池塘计数

Flood-Fill模型：利用BFS统计连通块数量

这里每个点至多遍历一遍，没有其他要求，所以只需要一个st数组即可。

Flood-Fill模型不像最短距离问题只需要一个队列，这里对每一个可能的点都要重新构建一个队列，每次构建一个队列，就要把这个连通块中所有的点都遍历一点，如果不遍历完的话可能导致一个连通块变成两个甚至更多，计算出错。

for i in range(n):
    for j in range(m):
        if st[i][j] == False and g[i][j] == 'W':
            bfs(i, j)
            cnt += 1

做题时卡了一下如何计算所有连通块的数量，放在里面每次入队出队的时候+1都不对，其实放在外面即可，因为每次只要新的队列创建成功，说明连通块数量+1了。

小技巧：
对于周围八个点（上下左右，左上左下，右上右下）的搜索，一般采用使用两层for循环并剔除中间这个点即可。

for a in range(t[0] - 1, t[0] + 2):
            for b in range(t[1] - 1, t[1] + 2):

bfs过程：

def bfs(x, y):
    q = collections.deque()
    q.append((x, y))
    st[x][y] = True
    while q:
        t = q.popleft()
        for a in range(t[0] - 1, t[0] + 2):
            for b in range(t[1] - 1, t[1] + 2):
                if a == t[0] and b == t[1]: continue
                if 0 <= a < n and 0 <= b < m and not st[a][b] and g[a][b] == 'W':
                    q.append((a, b))
                    st[a][b] = True

AcWing 1098. 城堡问题

Flood-Fill模型拓展1：连通块面积

根据题意可知，本题仍是求图中连通块数量，但略有拓展，需要求出面积最大的房间。

本题输入比较怪，但可以先放下输入，先思考在正常输入下如何计算。

思路同Flood-Fill模板题，对于每一个没被搜索过的点，都创建一个队列将其插入，然后用BFS，将其周围所有距离为1并且没被搜索过并且没有阻挡（可达到的点）放入队列。

这里拓展了连通块的面积，只要每次BFS的入队或出队时，area += 1即可，每次计算完一个连通块，更新最大值。

简而言之就是在外部计算连通块数量，在内部计算连通块面积最大值（记得用global）

对于本题的输入而言，1，2，4，8，都是2的次方，所以对于已知的每个点四个方向上门框之和，可以用位运算的方式来判断这个方位上是否有门，就能知道这个方向能不能移动了。

if g[x][y] >> i & 1 == 1: continue

注意这里dx和dy数组的顺序要和门的顺序相对应

bfs过程：

def bfs(x, y):
    global maxn
    area = 0
    q = collections.deque()
    st[x][y] = True
    q.append((x, y))
    while q:
        t = q.popleft()
        area += 1 #每次入队时面积+1
        for i in range(4):
            a, b = t[0] + dx[i], t[1] + dy[i]
            if a < 0 or a >= n or b < 0 or b >= m: continue
            if st[a][b]: continue
            if g[t[0]][t[1]] >> i & 1 == 1: continue
            q.append((a, b))
            st[a][b] = True
    maxn = max(area, maxn) # 内部更新最大值

每个没被遍历过的点都要入队（Flood-Fill特点）：

cnt = 0
for i in range(n):
    for j in range(m):
        if st[i][j] == False:
            bfs(i, j)
            cnt += 1 # 外部计算连通块数量

AcWing 1106. 山峰和山谷

Flood-Fill模型拓展2：连通块和周围点的大小关系

本题对连通块提出了更高的要求，分为山峰和山谷，需要对连通块周围的点和连通块中的点的大小进行判断。

和普通Flood-Fill模型的模板一样，仍然是对于每个没有被搜索过的点创建一个队列将其插入，采用bfs找出这个连通块的所有元素。

本题仍然是八连通，所以还是采用两层循环。

不同点在于这里判断的顺序容易出错，在一般情况下，出界，是否搜索过等判断条件的顺序是无所谓的，但这里需要将这个连通块周围所有元素的大小和连通块中元素大小进行比较，所以这里的st[a][b]的判断要放在最后。

if i == t[0] and j == t[1]:continue
if i < 0 or i >= n or j < 0 or j >= n: continue
if g[i][j] > g[t[0]][t[1]]: has_higher = True
elif g[i][j] < g[t[0]][t[1]]: has_lower = True
elif st[i][j] == False:
    q.append((i, j))
    st[i][j] = True

首先是八连通两重循环中间点的判断，其次是是否出界的判断，那么接下来所有的点都是合法的，只不过有的点被搜过了而已。

该点的大小和连通块中元素相比存在三种可能（大于，小于和等于）

如果存在周围的点高于连通块中的元素，那么has_higher = True，存在点高于这个连通块。

如果存在周围的点低于于连通块中的元素，那么has_lower = True，存在点低于这个连通块。

如果这个点等于连通块中元素，并且没有被搜索过，那么将其入队。

注意判断是否重复入队放在了最后，如果先判断是否重复入队再对大小进行比较，那么就会有些点无法被判断到，导致出错。

那么判断山峰还是山谷也很有意思，根据两个全局变量，has_higher和has_lower值，若单论True来给山峰和山谷数量+1，如果二者都为True，周围又有比他高的又有比他矮的，其实是不能加的。

所以这里用反向判断，如果has_higher为False，说明周围没有比他高的，那么山峰+1。

同理如果has_lower为False，说明周围没有比他矮的，都比他高，那么山谷+1。

注意：题目中指出如果整个图中元素值都一样，那么既是山峰也是山谷，所以上面两个判断条件不能加else，单纯写两个if判断。

if has_higher == False:
                shanfeng += 1
            if has_lower == False:
                shangu += 1

完整的BFS判断：

def bfs(x, y):
    global has_lower
    global has_higher
    q = collections.deque()
    q.append((x, y))
    st[x][y] = True
    while q:
        t = q.popleft()
        for i in range(t[0] - 1, t[0] + 2):
            for j in range(t[1] - 1, t[1] + 2):
                if i == t[0] and j == t[1]:continue
                if i < 0 or i >= n or j < 0 or j >= n: continue
                if g[i][j] > g[t[0]][t[1]]: has_higher = True
                elif g[i][j] < g[t[0]][t[1]]: has_lower = True
                elif st[i][j] == False:
                    q.append((i, j))
                    st[i][j] = True

AcWing 173. 矩阵距离

多源BFS模型

本题可以看作一个有多个起始状态的Flood-Fill算法，把矩阵中每一个为1的点看作起点，整个矩阵都可以通行，对于每个位置，从任意的起点出发，求到达该位置需要的最小步数。

在这种具有多个起始状态的问题称为多源BFS。

多源BFS：从多个源点出发的bfs算法，只需要将多个源点都连一条边权为0的边到虚拟源点,那么问题就等价于从虚拟源点开始BFS。

那么就相当于一开始直接将所有源点加入BFS的队列即可。

def bfs(): # 做一遍正常的BFS
    while q:
        t = q.popleft()
        for i in range(4):
            a, b = t[0] + dx[i], t[1] + dy[i]
            if a < 0 or a >= n or b < 0 or b >= m: continue
            if dist[a][b] != -1: continue
            dist[a][b] = dist[t[0]][t[1]] + 1
            q.append((a, b))


# 将所有为1的点加入队列
for i in range(n):
    for j in range(m):
        if g[i][j] == 1:
            dist[i][j] = 0
            q.append((i, j))
bfs()

AcWing 845. 八数码

最小步数模型：状态之间的转化

最小步数模型一般有两个状态，一个是给定的初始状态，另一个是按照一定要求转变后的目标状态。

从初始状态转移到目标状态——>求最小步数

这里的状态可能会是一个字符串，甚至一个矩阵，一个图，目前碰到的解决办法都是转化为字符串存入队列中去。

Q1：如何将3*3的矩阵转化为字符串存储？

Q2：一维坐标如何对应到三维坐标？

Q3：dist数组
既然要求最小步数，则必然有dist数组，最短距离模型的dist数组一般是一个坐标对应移动步数，dist开二维即可，但这里是字符串和移动步数对应，所以需要使用dict字典存储dist数组，将字符串和数字联系在一起，字符串表示状态，数字表示距离。

目前来说，我认为这种存储方式是最小步数模型的共性。

Q4：移动步数
每次进行一次操作，上下左右交换一次就相当于移动了一次，所以只需要在每次合法操作后更新dist

dis[new] = dist[old] + 1

Q4：为什么转换完成后py不需要还原
在y总C++代码中，在循环进行上下左右交换的时候，每次字符串$t$存入数组后都需要，但py不需要，因为C++修改的是字符串$t$本身，而py中是将字符串转为列表进行修改后再转回字符串存入dist数组，原来的字符串$t$并没有改变hh

BFS过程：

def bfs(s):
    end = '12345678x' # 定义目标状态
    q.append(s) # 初始化队列
    dis = dict()
    dis[s] = 0 # 初始化dist数组
    while q:
        t = q.popleft(
        d = dis[t])  # 记录当前状态的距离
        if t == end: # 如果是最终状态则返回距离
            return dis[t]
        index = t.find('x')  # 查询x在字符串中的下标，然后转换为在矩阵中的坐标
        x = index // 3
        y = index % 3

        for i in range(4):
            nx, ny = x + dx[i], y + dy[i] # 求转移后x的坐标
            if 0 <= nx <= 2 and 0 <= ny <= 2: # 当前坐标没有越界
                tmp = list(t)
                tmp[index], tmp[nx * 3 + ny] = tmp[nx * 3 + ny], tmp[index] # 转移x
                net = ''.join(tmp)
                if net not in dis: # 如果当前状态是第一次遍历，记录距离，入队
                    dis[net] = d + 1
                    q.append(net)
    return -1

AcWing 1107. 魔板

最小步数模型拓展1：记录转移过程

基本思路和八数码没有太大区别，只多了需要记录每次转移过程使用了哪种操作。

但如果只记录每次用哪种操作的话，最后没法倒推回去，所以还需要记录转移过程（转移中的所有状态），最后从结束状态倒推即可。

这里同样使用字典，实现字符串和元组的映射。

pre[new] = ('操作类型', old)

本题用一个列表m[3]存储三种操作对应新的字符串，利用数字$0$，$1$，$2$和字符$A$，$B$，$C$的ASCII码之间的关系存储每次操作的类型。

---

注意：ord()函数只能求字符的ASCII码，无法操作int型变量，这里需要加一个str

i = 0
print(ord(str(i)))

输出：

48

---

完整的pre更新方程：

pre[new] = (chr(ord(str(i)) + 17), old)

只不过本题三个操作比较复杂一点，需要耐心利用切片和交换以及join函数。

def move0(s):
    s = s[::-1]
    return s

def move1(s):
    res = list(s)
    res = [res[3]] + res[0:3] + res[5:8] + [res[4]]
    return ''.join(res)


def move2(s):
    res = list(s)
    res[1], res[2], res[5], res[6] = res[6], res[1], res[2], res[5]
    return ''.join(res)

BFS过程：

def bfs(a, s):
    if a == s: return 0 # a是目标状态，s是起始状态
    q.append(s)
    dist[s] = 0
    while q:
        t = q.popleft()
        m = [0] * 3
        m[0] = move0(t)
        m[1] = move1(t)
        m[2] = move2(t)
        for i in range(3):
            if m[i] not in dist:
                dist[m[i]] = dist[t] + 1
                pre[m[i]] = (chr(ord(str(i)) + 17), t)
                q.append(m[i])
                if m[i] == a: return dist[m[i]]

注意：最后需要倒叙输出

res = []
x = aim
while x != start:
    res.append(pre[x][0])
    x = pre[x][1]
if res:
    res = res[::-1]
    res = ''.join(res)
    print(res)

AcWing 179. 八数码

最小步数模型拓展1：记录转移过程

和魔板区别不大，甚至更简单hh，和845的八数码相比，只需要同样用一个字典来实现每次状态（字符串）和元组的映射，元组包括操作类型和上一层状态。

这里不像魔板可以用数字$0$，$1$，$2$和字符$A$，$B$，$C$的ASCII码之间的关系存储每次操作的类型。

我这里采用一个字典实现，$0$，$1$，$2$，$3$和$u$，$d$，$l$，$r$的对应关系，直接查找即可。

query[0] = 'u'
query[1] = 'd'
query[2] = 'l'
query[3] = 'r'

DFS

深搜也分为两类，第一类是内部搜索，所有点都在棋盘内部，每个点都是一个状态并且都只能被搜索一次，不需要恢复现场，比如迷宫，红黑图等Flood-Fill算法。

连通性问题，BFS和DFS都能用，建议BFShh

第二类是外部搜索，如果将整个棋盘当作一个状态，每次进行新的搜索时要保证上一层都一样，需要恢复现场，就比如在棋盘的格子里面填数，第一个点填1，这一轮搜索完之后，第一个点想填2，那么就要先把之前填写的1给去除，也就需要恢复现场。
比如n皇后，递归实现指数型枚举等，都是把整个棋盘，整个数字串当成一个状态，通常可以看作一棵搜索树。

DFS模板：

dfs()//参数用来表示状态  
{  
    if(到达终点状态)  
    {  
        ...//根据题意添加  
        return;  
    }  
    if(越界或者是不合法状态)  
        return;  
    if(特殊状态)//剪枝
        return ;
    for(扩展方式)  
    {  
        if(扩展方式所达到状态合法)  
        {  
            修改操作;//根据题意来添加  
            标记；  
            dfs（）；  
            (还原标记)；  
            //是否还原标记根据题意  
            //如果加上（还原标记）就是 回溯法  
        }  

    }  
}

注意：DFS容易爆栈，需要手动设置，一般到2*10**5会爆掉，就听天由命吧

sys.setrecursionlimit()

外部搜索三大注意点：
1. 顺序：找到一种搜索顺序，能把各种情况都枚举出来（一定要是全部方案）/问题通常是最值和方案数
2. 回溯：保证搜索树每次以一个相同的状态进行向下拓展
3. 剪枝：如下

剪枝技巧：
1. 优化搜索顺序： 大部分情况下，我们应该优先搜索分支数量较少的节点（小猫爬山）
2. 排除等效冗余：前3个苹果中选两个，选12和21是一样的，没必要重复搜索，采用一个start变量
3. 可行性剪枝：迷宫问题中的墙/边界等
4. 最优化剪枝：求最小值问题的时候，当前值已经大于了目前存的最小值，可以直接剪枝

刷题列表：

AcWing 1112. 迷宫

DFS的连通性模型，判断两个点之间是否联通（经典迷宫），注：路径不一定是最小值。

内部搜索不用恢复捏

感觉DFS都是在函数前半部分判断是否搜索到了终点然后退出的。

DFS过程：

def dfs(x, y):
    if g[x][y] == '#': return False
    if x == hb and y == lb: return True  # 找到终点退出
    st[x][y] = True
    for i in range(4):
        nx, ny = x + dx[i], y + dy[i]
        if nx < 0 or nx >= n or ny < 0 or ny >= n: continue
        if st[nx][ny] == True: continue
        if dfs(nx, ny): return True
    return False

AcWing 1113. 红与黑

DFS连通性问题拓展1：求连通块的面积

采用全局变量res求连通块的面积

def dfs(x, y):
    global res
    st[x][y] = True
    res += 1

    for i in range(4):
        nx, ny = x + dx[i], y + dy[i]
        if nx < 1 or nx > n or ny < 1 or ny > m: continue
        if st[nx][ny]: continue
        if g[nx][ny] == '#': continue
        dfs(nx, ny)

这样对比下来，感觉Flood-Fill模型还是用BFS好了，还不用担心爆栈。

AcWing 1116. 马走日

外部搜索的方案统计

（这个感觉就是DFS好做了）

BFS可以安心内部搜索（Flood-Fill）和最短路模型，外部搜索还是给DFS吧

本题采用一个全局变量统计方案数，每次按照🐎的移动方案（走日）进行DFS，直到遍历过的点数等于棋盘所有格子数量，也就是遍历了整个棋盘，可以return，然后方案数+=1。

所以DFS需要传入三个参数，分别是横纵坐标以及当前搜索了多少个点。

本题是外部搜索，所以需要回溯还原哦。

def dfs(x, y, u):
    global res # 全局变量统计方案数
    if u == n * m:
        res += 1
        return None

    st[x][y] = True
    for i in range(8):
        nx, ny = x + dx[i], y + dy[i]
        if nx < 0 or nx >= n or ny < 0 or ny >= m: continue
        if st[nx][ny] == True: continue
        dfs(nx, ny, u + 1)

    st[x][y] = False # 回溯还原

AcWing 1117. 单词接龙

搜索顺序模型

如何想到用DFS呢，感觉从搜索树的角度来思考会比较好

---

既然需要拼接，那我们就需要预处理所有单词两两拼接重合的长度，本题要求接龙单词最长，那么对于两个字符串拼接，重合的部分越短，才能让拼接后形成的新字符串长度越长，所以找到所有单词两两拼接重合部分的最小长度即可。

g[i][j]表示第$i$个子符串与第$j$个子符串拼接重合的最小长度。

预处理的过程：

for i in range(n):
    for j in range(n):
        a, b = w[i], w[j]
        for k in range(1, max(len(a), len(b))):
            if a[0 - k:] == b[:k]:
                g[i][j] = k
                break  # 第一次找到就退出，第一次找到就是最小的

因此DFS需要传入两个参数，一个是当前拼接的字符串，另一个就是当前末尾的单词是哪个（这样就知道g[i][j]的i是哪个了）
dfs(dragon,last)：dragon表示当前的单词龙，last表示上一个连接到字符串的单词是第几个。

每个单词最多用两次，这里需要一个used[]数组记录每个单词使用的次数，同样是外部搜索，记得还原

完整的DFS：

def dfs(dra, last):
    global ans
    ans = max(ans, len(dra))

    used[last] += 1

    for i in range(n):
        if g[last][i] and used[i] < 2:
            dfs(dra + w[i][g[last][i]:], i)

    used[last] -= 1

AcWing 94. 递归实现排列型枚举

最经典的外部搜索。

根据搜索树，可以通过依次枚举每一个位置放哪个数来做。

st数组判重，path数组记录路径，外部搜索需要回溯，记得还原~

（忘了图源自哪位大佬了）

DFS过程：

def dfs(u):
    if u == n:
        for i in range(n):
            print(path[i], end = ' ')
        print()
        return

    for i in range(1, n + 1):
        if st[i] == False:
            path[u] = i
            st[i] = True
            dfs(u + 1)
            st[i] = False

    b[u] = False
    dfs(u + 1)

AcWing 842. 排列数字

排列，外部搜索，同上

AcWing 93. 递归实现组合型枚举

相对于上一题的排列，这里的只需要枚举组合，即123和321属于一类。

只需要加入一个start来记录这一层加入的数是第几个，下一层从这个数后面开始寻找，这样保证不会出现重复的情况，这也意味着我们可以省去判重的st数组。

def dfs(u, start):
    if u == m:
        for i in range(m):
            print(path[i], end = ' ')
        print()
        return
    for i in range(start, n + 1):
        path[u] = i
        dfs(u + 1, i + 1)

注意这里start初始传入的是1哦

AcWing 92. 递归实现指数型枚举

前两题是枚举每个位置上哪个数，这里位置数量不确定了，所以就按照每个数选不选来枚举。

DFS过程：

def dfs(u):
    if u > n:
        for i in range(1, n + 1):
            if b[i] == True:
                print(i, end = " ")
        print()
        return

    b[u] = True  # 选第u个数字
    dfs(u + 1)

    b[u] = False # 不选第u个数字
    dfs(u + 1)

想到如果题意变成在前$m$个数中至多选择$n$个，其实同样是这个DFS方程，就是在$1$-$n$之间指数型枚举

AcWing 843. n-皇后问题

外部搜索（整个棋盘是一个状态）

根据题意，每个皇后都不能在同一行，同一列和同一斜线上，那么其实可以按行来搜索，反正每行只能放一个hh

正负斜线的问题：利用斜率解决

（看基础课找到的图，同样忘了来源hh）

又是熟悉的DFS过程：记得回溯还原

def dfs(x):
    if x == n :
        for i in range(n):
            for j in range(n):
                print(path[i][j], end = "")
            print()
        print()
        return

    for y in range(n):
        if col[y] == False and udg[y - x + n] == False and dg[x + y] == False:
            path[x][y] = 'Q'
            col[y], dg[x + y], udg[y - x + n] = True, True, True
            dfs(x + 1)
            path[x][y] = '.'
            col[y], dg[x + y], udg[y - x + n] = False, False, False

AcWing 1118. 分成互质组

搜索顺序之（减少搜索层数？

最暴力的思路是遍历每一个元素，然后遍历每一个分组，看他能否放到其中一个分组中去，如果不行的话就开个新的组。

y总提供了一个优化后的爆搜，是对第二个分组遍历的优化，如果每次我们都只针对一个分组，每次只放到最后一组中去，或者说拿着盘子，依次扫描每个物品，往盘子里放可以放的。

注意这个所有能放在这个盘子里的物品放完之后，就再也不会往里面放东西了。

对于每一种的元素来说，需要的是组合而非排列，组内元素为123和321是同一组，所以参考递归实现组合枚举，引入一个start变量。

这里DFS传入4个变量，分别是当前组的编号，当前组的容量，当前已分组完毕的元素个数，从哪个位置开始选择元素，即上一次遍历到的数字的下一个位置【组合套路(定一个遍历顺序)】

def dfs(g, gc, tc, start):
    global res
    if g >= res: return  # 剪枝，最优性剪枝，求最小值，只要比目前的最小值还大就不可能了 
    if tc == n: res = g
    flag = True
    for i in range(start, n):
        if not st[i] and check(groups[g], gc, i):
            st[i] = True
            groups[g][gc] = w[i]
            dfs(g, gc + 1, tc + 1, i + 1)
            st[i] = False
            flag = False

    # 遍历已经完成，已经没有元素可以再加入这个组中        
    if flag:  
        dfs(g + 1, 0, tc, 0)

这里判断是否互质用了gcd函数，可惜的是内置函数会超时hhh，返回的是$a$和$b$的最大公因数。

def gcd(a, b):
    return gcd(b, a % b) if b != 0 else a

感觉这篇写的不是很清楚，下周回来复习

AcWing 165. 小猫爬山

本题贪心会出错捏，安心暴搜。

对于每只小猫，都有两种选择，放到当前的某个缆车上或新开一辆缆车（感觉和互质组有点像），这里主要是剪枝的思路，对于每一辆缆车而言，一定是先放重量大的猫，接下去的分支会比较少（可能都直接占满了）。

所以可以先对猫的重量进行排序，然后再爆搜。

u表示当前已经开了多少组，x表示当前放了多少只猫

def dfs(u, x):
    global res
    if u >= res: return  # 最优性剪枝
    if x == n: 
        res = u
        return

    for i in range(u):  # 爆搜每个缆车看放不放
        if g[i] + w[x] <= m:
            g[i] += w[x] 
            dfs(u, x + 1)
            g[i] -= w[x]
    g[u] = w[x] 
    dfs(u + 1, x + 1)
    g[u] = 0

w.sort()
w.reverse()  # 优化搜索顺序

洛谷 P2392 kkksc03考前临时抱佛脚

外部搜索

对于每个组里面的题目，应该要分成相互之间差最小的两组，可以直接暴搜所有的情况然后取一个最小值，因为分成的每个组都数量不固定，所以我觉得不适合用BFS，可以参考递归实现指数型枚举中对每个元素选不选的情况。

这里如果选就放到组1中去，不选就放到组2中去，属于外部搜索，所以需要回溯还原。而且是按顺序来的，就不需要st数组了。

如果所有元素都被分配完了就对当前的差和之前得到的最小值进行比较，如果小于当前的最小值，那么更新此时两组中的较大值。

def dfs(u, n):
    global w1, w2, min_cha, k
    if u == n:
        if abs(w1 - w2) < min_cha:
            min_cha = abs(w1 - w2)
            k = max(w1, w2)
        return

    w1 += l[u]
    dfs(u + 1, n)


    w1 -= l[u] # 回溯

    w2 += l[u]
    dfs(u + 1, n)

    w2 -= l[u]

但不知道为什么第一个点T了捏

洛谷 P1036 选数

外部搜索

从n个数中选择k个数，经典排列模型，需要start变量。

def dfs(u, start):
    global s
    global res
    if u == k:
        if check(s): res += 1
        return

    for i in range(start, n):
        s += w[i]
        dfs(u + 1, i + 1)

        s -= w[i]

这里多一个判断素数的函数，赶紧背

def check(n):
    if n < 2:
        return False
    i = 2
    while i <= n // i:
        if n % i == 0:
            return False
        i += 1
    else:
        return True

洛谷 P2036 PERKET

外部搜索（爆搜所有组合）

这题和临时抱拂脚很像，但抱佛脚需要将所有的元素都用到，但这里不要求，并且这里酸度是乘，苦度是加。

每个配料都是选或者不选，感觉不用开始因子start