深度优先搜索 (DFS)
先根遍历：根、左子树、右子树
中根遍历：左子树、根、右子树
后根遍历：左子树、右子树。根
引例
题目描述
输入一个正整数 n，按照字典序输出 1 到
n 的全排列，每个排列占一行，数字间用空格分隔。
| 示例输入 |
示例输出 |
3 |
1 2 3
1 3 2
2 1 3
2 3 1
3 1 2
3 2 1 |
字典序：dfs使用VIS标记和 vis[i]=0 回溯
基本模型
深度优先搜索的基本模型:
void dfs(int step)
{
特殊情况处理 (一般是结束递归的情况)
枚举当前每一种可能 for(i=1; i<=n; ++i)
在枚举的每一种可能中, 递归dfs(step+1);
}
|
C++ 实现示例
#include <cstdio>
#include <iostream>
#include <cstring>
using namespace std;
bool vis[12];
int num[12];
int n;
void dfs(int steps){
if(steps==n+1){
for(int i=1;i<=n;i++)
printf("%d",num[i]);
printf("\n");
return ;
}
for(int i=1;i<=n;i++){
if(!vis[i]){
vis[i]=1;
num[steps]=i;
dfs(steps+1);
vis[i]=0;
}
}
return ;
}
int main(){
while(scanf("%d",&n)!=EOF){
memset(vis,0,sizeof(vis));
dfs(1);
}
return 0;
}
|
例题二：迷宫搜索
题目名： B. 手机的诱惑 运行时间限制: 1000ms 运行内存限制: 32768kb ###
题目描述
张晨乐在一个古老的迷宫中发现了一个手机，这个手机深深地吸引了他。然而，当他拿起手机，迷宫开始摇晃，张晨乐能感觉到地面下沉。他意识到：这个手机只是一个诱饵！于是，他不顾一切地试图冲出这个迷宫。
迷宫是一个大小为N*M的矩形，有一扇门，一开始，门是关闭的，并在第T秒打开一瞬间（小于1秒的时间）。因此，张晨乐必须刚好在第T秒钟到达门口。
每一秒，他都可以向上，下，左，右四个相邻的位置中的任意一个移动。一旦他进入一个新的地方，这个地方的地面就会开始下沉，并在下一秒消失。因此，他不能在一个地方停留超过一秒钟，也不能再进入曾经走过的地方。
请问，可怜的张晨乐能够逃出迷宫吗？
输入
输入由多个测试用例组成。
每个测试用例的第一行包含三个整数N, M和T (1 < N, M < 7; 0 < T
< 50)，分别表示迷宫的大小和门打开的时间。
接下来的N行给出迷宫布局，每行包含M个字符。
每个字符含义如下: - ‘X’ : 不能进入的墙 - ‘S’ : 起点 - ‘D’ : 门 - ‘.’
: 可以行走的地方
输入以三个0结束，这个测试用例不被处理。
输出
对于每组测试数据，如果张晨乐能够逃出迷宫，则请输出”YES”，否则，请输出”NO”。每组数据输出占一行。
输入样例
4 4 5
S.X.
..X.
..XD
····
3 4 5
S.X.
..X.
...D
0 0 0
|
输出样例
奇偶性剪枝：
-1753014075386.webp)
0->1 一定是奇数次
算法细节：走过的标记为wall
’X’，回溯时重置为road ‘.’
#include <cstdio>
#include <iostream>
#include <cstring>
#include <cmath>
using namespace std;
int n,m,t;
int wall;
int x,y,xx,yy;
int cx[]={1,0,-1,0};
int cy[]={0,1,0,-1};
char map[10][10];
bool escape;
void dfs(int sx,int sy,int cnt){
if(escape){
return ;
}
if(sx<=0 sx>n sy<=0 sy>m){
return ;
}
if((t-cnt-abs(sx-xx)-abs(sy-yy))<0){
return ;
}
if(cnt==t && sx==xx && sy==yy){
escape=1;
return ;
}
for(int i=0;i<4;i++){
if(map[sx+cx[i]][sy+cy[i]]!='X'){
map[sx+cx[i]][sy+cy[i]]='X';
dfs(sx+cx[i],sy+cy[i],cnt+1);
map[sx+cx[i]][sy+cy[i]]='.';
}
}
}
int main(){
while(scanf("%d%d%d",&n,&m,&t),nmt){
wall=0;
escape=0;
memset(map,0,sizeof(map));
getchar();
for(int i=1;i<=n;i++){
for(int j=1;j<=m;j++){
scanf("%c",&map[i][j]);
if(map[i][j]=='S'){
x=i;
y=j;
map[i][j]='X';
}
else if(map[i][j]=='X'){
wall++;
}
else if(map[i][j]=='D'){
xx=i;
yy=j;
}
}
getchar();
}
if(m*n-wall<=t){
cout<<"NO"<<endl;
continue;
}
int temp=t-abs(x-xx)-abs(y-yy);
if(temp%2==1){
cout<<"NO"<<endl;
continue;
}
dfs(x,y,0);
if(escape){
cout<<"YES"<<endl;
}
else{
cout<<"NO"<<endl;
}
}
return 0;
}
|
DFS二分图匹配：
匈牙利算法： N 次 DFS 子问题分解
-1753014122337.webp)
###
例题：Problem Description RPG girls
今天和大家一起去游乐场玩，终于可以坐上梦寐以求的过山车了。可是，过山车的每一排只有两个座位，而且还有条不成文的规矩，就是每个女生必须找个个男生做partner和她同坐。但是，每个女孩都有各自的想法，举个例子把，Rabbit只愿意和XHD或PQK做partner，Grass只愿意和linle或LL做partner，PrincessSnow愿意和水域浪子或伪酷儿做partner。考虑到经费问题，boss刘决定只让找到partner的人去坐过山车，其他的人，嘿嘿，就站在下面看着吧。聪明的Acmer，你可以帮忙算算最多有多少对组合可以坐上过山车吗？
Input 输入数据的第一行是三个整数K , M ,
N，分别表示可能的组合数目，女生的人数，男生的人数。0<K<=1000
1<=N
和M<=500.接下来的K行，每行有两个数，分别表示女生Ai愿意和男生Bj做partner。最后一个0结束输入。
Output
对于每组数据，输出一个整数，表示可以坐上过山车的最多组合数。
#include <cstdio>
#include <iostream>
#include <cstring>
using namespace std;
bool map[2020][2020];
int links[2020];
bool used[2020];
int k,n,m;
bool dfs(int s){
for(int j=1;j<=m;j++){
if(!used[j] && map[s][j]){
used[j]=1;
if(links[j]==0 dfs(links[j])){
links[j]=s;
used[j]=0;
return true;
}
used[j]=0;
}
}
return false;
}
int hungary(){
int ans=0;
memset(links,0,sizeof(links));
for(int i=1;i<=n;i++){
memset(used,0,sizeof(used));
if(dfs(i)){
ans++;
}
}
return ans;
}
int main(){
while(scanf("%d",&k),k){
cin>>n>>m;
memset(map,0,sizeof(map));
for(int i=0;i<k;i++){
int x,y;
scanf("%d%d",&x,&y);
map[x][y]=1;
}
cout<<hungary()<<endl;
}
return 0;
}
|
变式题目：
- 最小顶点覆盖：最少量的顶点链接所有边
数量等同于二分匹配
有两台机器A和B以及N个需要运行的任务。
每台机器有多种不同的模式，而每个任务都恰好在一台机器上运行。如果它在机器A上运行，则机器A需要设置为模式
a[i]，如果它在机器B上运行，则机器B需要设置为模式b[j]。每台机器上的任务可以按照任意顺序执行，但是每台机器每转换一次模式需要重启一次。
请合理为每个任务安排一台机器并合理安排顺序，使得机器重启次数尽量少。
#include <cstdio>
#include <iostream>
#include <cstring>
using namespace std;
bool map[110][110];
int links[110];
bool used[110];
int n,m,k;
bool dfs(int s){
for(int j=1;j<=m;j++){
if(!used[j] && map[s][j]){
used[j]=1;
if(links[j]==0 dfs(links[j])){
links[j]=s;
return true;
}
used[j]=0;
}
}
return false;
}
int hungary(){
memset(links,0,sizeof(links));
int ans=0;
for(int i=1;i<=n;i++){
memset(used,0,sizeof(used));
if(dfs(i)){
ans++;
}
}
return ans;
}
int main(){
while(scanf("%d",&n),n){
cin>>m>>k;
memset(map,0,sizeof(map));
for(int i=0;i<k;i++){
int id,x,y;
scanf("%d%d%d",&id,&x,&y);
if(x==0 y==0){
continue;
}
map[x][y]=1;
}
cout<<hungary()<<endl;
}
return 0;
}
|
- DAG图最小路径覆盖：（DAG：有向无环图）
最少的路覆盖所有的点 例题：
有一个城镇，它的所有街道都是单行的，并且每条街道都是和两个路口相连。同时已知街道不会形成回路。
你的任务是编写程序求最小数量的伞兵，这些伞兵可以访问（visit）所有的路口。对于伞兵的起始降落点不做限制。
解题方法：拆点形成二分图：
-1753014536944.webp)
DAG最小路径覆盖数=节点数-二分图最大匹配数 核心
最大独立集：
独立节点数=节点数-最大匹配数
组合游戏：博弈论
定义：有规则，有限，无法继续进行为败者
必败点（P点）：前一个选手取胜
必胜点（N点）：下一个选手取胜
- 所有的终结点都是必败点
- 从必胜点一定有方法到必败点
- 从必败点只能走到必胜点
算法： eg1
取子游戏: S = {1, 3, 4}
第一步：标记所有终结点为必败点P
第二步：标记所有一步到P的点为必胜点
第三步：标记所有操作都到达N的点为必胜点
第四步：若没有新的P点，跳出 ———-有新的P点，回到二
疑问：如果三个人呢 ？？？？？？？
eg2:玩游戏的小男孩
------------
------------
------------
------1----
-----S-----
------------
------------
------------
------2----
-----3------
------------
------------
------------
------------
------------
|
#include <cstdio>
#include <iostream>
#include <cstring>
using namespace std;
int main(){
int t;
cin>>t;
while(t--){
int n,m;
cin>>n>>m;
if(n%(m+1)==0){
cout<<"Rabbit"<<endl;
}
else{
cout<<"Grass"<<endl;
}
}
return 0;
}
|
可以想为两堆牌（1,0）（0,1）（1,1）
eg3：nim游戏
-1753014724280.webp)
从三堆（5,7,9）中选一堆任取扑克牌：
nim-Sum两数按位异或得出结果
-1753014737304.webp)
对于位置各堆nim和为0：则为必败点
NIM图游戏状态转移
sg函数：定义：不等于后继节点sg值的最小的非负整数
需要记忆化DFS
性质： 定理1：sg值>0 必胜点
————sg值=0 必败点 定理2：大sg值为小sg值nim和
例子：
-1753014809799.webp)
#include <cstdio>
#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
int f[1010];
int k,m;
int s[1010];
int h[1010];
int sg(int ss){
bool g[1010]={0};
for(int i=0;i<k;i++){
int t=ss-s[i];
if(t<0){
break;
}
if(f[t]==-1){
f[t]=sg(t);
}
g[f[t]]=1;
}
for(int i=0;i<1010;i++){
if(!g[i]){
return i;
}
}
}
int main(){
while(scanf("%d",&k),k){
memset(f,-1,sizeof(f));
for(int i=0;i<k;i++){
scanf("%d",&s[i]);
}
sort(s,s+k);
cin>>m;
for(int i=0;i<m;i++){
int cc;
cin>>cc;
int ans=0;
for(int j=0;j<cc;j++){
int temp;
cin>>temp;
ans^=sg(temp);
}
if(ans){
cout<<"W";
}
else{
cout<<"L";
}
}
cout<<endl;
}
return 0;
}
|
记忆化递归 在递归前判断是否已经算过 eg例题：
题目描述：
老鼠在某个城市储存了一些奶酪，城市可以看成一个n*n的网格，在每个网格的洞里，老鼠存储了0~100块的奶酪。现在，它准备享用这些美味。开始，它在(0,0)的位置，每吃光一个地方的奶酪，就转移到边上水平或者垂直的位置。麻烦的是，有只猫在洞的附近，所以它每次在被猫抓住之前最多只能移动k个位置，更糟糕的是，每吃掉一个地方的奶酪，就会变胖。所以，为了下一次逃跑有足够的能量，每次它必须移动到一个比这次有更多奶酪的网格。
给定n和k以及每个网格的奶酪数量；
请计算：老鼠最多能吃到多少块奶酪（直到不能继续活动）？
- 可以dp 线性化：将所有点按奶酪数量排序，即可dp