Flood Fill

枚举每个未遍历的节点，然后从该节点出发，进行bfs
那么通过模拟以上过程就可以找到与当前点联通的一个块
该算法称为Flood fill

最短路模型

对于求解最短路：
1. 建立正向图，从起点出发，记录前驱节点，之后从终点开始统计答案，然后reverse答案。
2. 建立反向图，从终点出发，记录前驱节点，之后起点统计答案。

多源BFS

在一开始时，创建一个超级源点，将所有的起点向超级源点连边，那么从超级源点做一遍最短路
等价于从所有节点分别做一遍最短路。因为所有起点向超级源点连边的边权为0

康托展开

Acwing魔板

int cantor(string s){
    int res = 0, len = s.size();
    for(int i = 0;i < len; ++ i){
        int cnt = 0;
        for(int j = i + 1;j < len; ++ j) if(s[i] > s[j]) cnt ++ ;
        res += cnt * fact[len - i - 1];
    }
    return res;
}
string inv_cantor(int x){
    string res = e;
    int cnt;
    bool st[10] = {false};
    for(int i = 0;i < 8; ++ i){
        cnt = x / fact[8 - i - 1];
        x %= fact[8 - i - 1];
        for(int j = 1;j <= 8; ++ j){
            if(st[j]) continue;
            if(!cnt){
                st[j] = 1;
                res[i] = j + '0';
                break;
            }
            cnt -- ;
        }
    }
    return res;
}

最小步数模型

将棋盘或者数组映射成一个唯一的数或者字符串，将其作为state，然后对于每一步转移
求出新的state，最后dist[end] 就是答案。
当然，每个状态在第一次被遍历的时候时最小的。
小技巧：dist可一开始设置为一个不合法的数，表示未被搜过，这样可以将st数组省去

双端队列广搜

如果一个图的边权非零即一，那么就可以使用双端队列替换dijkstra中的优先队列。
利用deque进行搜索，每次如果边权为1，则加入到队尾，否则加入到队头。
拓展：如果一个图中，所有边权都是非负的，且只出现两种边权，那么也可以使用双端队列广搜
将小的看为0，大的看为1即可。

双向广搜

两种方法：
1. 维护一个队列，正代表正向搜，负代表反向搜
2. 维护两个队列，一个正向，一个反向
注意：每次都需要拓展一层的节点、注意特判起点终点相同的情况
优化：每次找队列size较小的拓展

A*

在最短路中，如果边权都是非负的，那么就可以使用启发式函数来优化搜索过程
假设真实值是 g(s) 估价函数为 f(s) 只需要保证 g(s) >= f(s) + dist[s]
常用启发函数：
1. 建立反图，用反图的dist作为估价函数
2. 曼哈顿距离(八数码：逆序对为奇数无解)、切比雪夫距离

DFS之连通性模型

首先找到没有被遍历的点，从这个点出发：
1. 如果已经遍历过邻接点，那么直接continue
2. 如果没有遍历过邻接点，那么接着dfs下去
其实就是Flood fill的深搜版本

DFS之搜索顺序

1. 枚举当前位置放哪个数
2. 枚举当前数放哪个位置

DFS之剪枝与优化

1. 优化搜索顺序
    可以从大到小枚举、或者从小到大枚举，选择状态数少的
2. 可行性剪枝
    如果当前出发的方案不可行，直接pass掉整个搜索树
3. 最优性剪枝
    如果当前答案为 res，全局最优解为ans，那么当res >= ans时，已经不会更新我的ans了，直接return
4. 排除等效冗余
    如果当前元素未搜索成功，则所有和当前相同的元素在此位置也不会搜索成功
5. 记忆化
    就是dp的深搜版本
6. 上下界剪枝
    比如要选的元素和不超过t，那么当前搜索的上限就是t，下限根据题目要求可同理得出
7. 提前break机制
    如果当前发现一组可行解，直接return true，并沿路一直返回

迭代加深

当搜索层数较多，但是答案只出现在低层次中，就可以使用迭代加深去优化
维护一个 depth 表示当前的深度，每次递归当前深度，如果有解，则返回，否则，继续加深深度
由于我们的树深度是呈指数增加的，所以前几层的所有节点都有可能没最后一层节点多
所以迭代加深并不会延慢搜索

bool dfs(int depth, int max_depth){
    if(depth > max_depth) return false;
    if(check()) return true;
    // 逻辑判断
}
int depth = 1;
while(!dfs(0, depth)) depth ++ ;

双向DFS、Meet in the middle

运用空间换时间的思想，首先搜出一半并将他们存到数组里，或者set之类的数据结构中，然后排序
然后搜索另一半，之后对于另一半搜索出的答案，直接在之前的数组中二分，并作出判断即可

IDA*

对上面的迭代加深引入估价函数
常见的估价函数：
1. 逆序对
2. 曼哈顿距离