搜索

BFS 广度优先搜索
求最小距离
用队列

求最小距离和Dijkstra作对比
BFS求最短路要求每一步都是1
如果所有边权都是1，那么用队列相当于用优先队列

BFS求最短路要求每一步一定是1吗？
不一定
边权只有 0 和 1 的BFS，可以用双端队列
如果有边权是 2 呢？可能可以把这一条边拆成2个长度为 1 的边

BFS的时间复杂度是多少？
点数+边数，其实就是边数
点数 * 每个点的方案数
比如在马的遍历中 8*n*m

如果是车的遍历呢，有障碍物
直接做BFS，时间复杂度是 nm(n+m)
可以优化，相当于优化最小的转弯个数
d[i][j][k] 到 (i, j) 位置，面向 k 方向，最小步数
向前移动，不消耗步数
选择转向，消耗1步

DFS 深度优先搜索
问连通块个数 / 大小
用栈（非递归） 或者 用递归

二维平面

游戏/比较一般的

树上的
图上的

P1219 [USACO1.5]八皇后 Checker Challenge
P1706 全排列问题
P1157 组合的输出
P2036 [COCI2008-2009#2] PERKET
P1605 迷宫
P1036 选数
P1019 单词接龙
P2404 自然数的拆分问题
P1535 [USACO08MAR]Cow Travelling S

5 * 5 的棋盘
从 (sx, sy) 到 (ex, ey) 走若干步
同一个位置不能走两次，问方案数
不要求最短路

这个题目必须用深搜

98884
2 3 4 2 0 0 2 0 0

3

P1219 [USACO1.5]八皇后 Checker Challenge

比较基础的问题

  1. 不确定层数的 多层循环
  2. 输出全排列
  3. 输出组合
  4. 输出子集

枚举全排列：
P1706 全排列问题
for (int i = 0; i < n; i++)
{
a[i] = i + 1;
}
// sort(a, a + n);
do
{
for (int i = 0; i < n; i++)
{
printf(" %d", a[i]);
}
printf("\n");
}
while (next_permutation(a, a + n));

1 2 2
2 1 2
2 2 1

枚举组合 例题：
P1157 组合的输出

0 1 2 3 4 数组下标
0 0 1 1 1
0 1 0 1 1
0 1 1 0 1
0 1 1 1 0
1 0 0 1 1
1 0 1 0 1
1 0 1 1 0
1 1 0 0 1
1 1 0 1 0
1 1 1 0 0

1 2 3 4 5 数组下标
0 0 0 1 1
0 0 1 0 1
0 0 1 1 0
0 1 0 0 1
0 1 0 1 0
0 1 1 0 0
1 0 0 0 1
1 0 0 1 0
1 0 1 0 0
1 1 0 0 0

15 = 0b1111 = {3, 2, 1, 0}
11 = 0b1011 = {3, 1, 0}

枚举子集 例题：
P2036 [COCI2008-2009#2] PERKET

P1605 迷宫
P1036 选数

P1019 单词接龙

aba
aca
ada
aea
afa
aga
aha
aia

pizza
at
atide
ide

P2404 自然数的拆分问题

初始 a
a -> aa
a -> ab
a -> ac
a -> ad
a -> ae
a -> af

int factorial(int x)
{
if (f[x] > 0)
{
return f[x];
}
f[x] = (x == 0 ? 1 : (x == 1 ? 1 : x * factorial(x - 1)));
return f[x];
}

search 4 types

  1. 2D array
  2. general
  3. tree
  4. graph

dfs

  1. unknown times for loops
  2. generate all permutations
  3. generate all combinations
  4. generate all subsets

for (int i = 0; i < n; i++)
{
a[i] = i;
}

do
{
output
}
while (next_permutation(a, a + n));

choose 2 from 4

1 2
1 3
1 4
2 3
2 4
3 4

a[0] = 0;
a[1] = 0;
a[2] = 1;
a[3] = 1;

do
{

}
while (next_permutation(a, a + n));

22 = 10110 = {4, 2, 1}

bfs = shortest path, one state is small enough to be pushed into the queue.
dfs = others

tree: almost all use dfs
graph: tarjan

P1596 [USACO10OCT]Lake Counting S
P5198 [USACO19JAN]Icy Perimeter S

P1825 [USACO11OPEN]Corn Maze S

5 6

W##

@W=#

(x1, y1) (x2, y2)

x1 ^ x2 ^ x
y1 ^ y2 ^ y

(x, y)

P2730 [USACO3.2]魔板 Magic Squares

x / 100 % 10
x % 1000 / 100

2 3 4 2 0 0 2 0 0

P4268 [USACO18FEB]Directory Traversal G

the answer of the root

folder1/file1
folder1/folder2/file2
folder3/file3
file4

3 5 7 4 1 2 9 6 8

P2853 [USACO06DEC]Cow Picnic S
P2725 [USACO3.1]邮票 Stamps
P2017 [USACO09DEC]Dizzy Cows G
P2666 [USACO07OCT]Bessie's Secret Pasture S
P2690 [USACO04NOV]Apple Catching G
P2895 [USACO08FEB]Meteor Shower S
P6207 [USACO06OCT] Cows on Skates G
P1219 [USACO1.5]八皇后 Checker Challenge

P1930 [USACO3.3]亚瑟王的宫殿
P2921 [USACO08DEC]Trick or Treat on the Farm G
P2962 [USACO09NOV]Lights G
P3067 [USACO12OPEN]Balanced Cow Subsets G

1. [W##](#w)
  1. @W=#
≡