蓝桥杯备赛 Day 19 加练dfs

是否需要回溯?
输入参数有哪几个(当前dfs和下一个dfs什么会变?)？
是否需要返回值?

一.1158: 八皇后

P1158 - 八皇后 - New Online Judge (ecustacm.cn)
学习:
1.dfs输入为层数，即行号i，因为是每行只放一个，下一个dfs就是i+1
2.输出void，因为下一层无需返回上一层值
3.需要一开始判断递归返回条件，更新结果
代码:

#include <bits/stdc++.h>using namespace std;
const int N=15;
int a[N][N],cnt,n; //0未放置，1放置 
vector<vector<int>> ans(3,vector<int>(n,0));//前3组解 //输入为横坐标i,无返回值 
void dfs(int i){//i==n+1,得到一组解，返回寻找下一组if(i==n+1){//更新ansif(cnt<3){for(int i=1;i<=n;i++){for(int j=1;j<=n;j++){if(a[i][j])	ans[cnt].emplace_back(j);}} }//更新cntcnt++;} //遍历列for(int j=1;j<=n;j++){bool flag=true;//同一列有放置 for(int k=1;k<i;k++){if(a[k][j]){flag=false;break;}}if(!flag)	continue;//左上方有放置for(int k=1;(i-k)>=1 && (j-k)>=1;k++){if(a[i-k][j-k]){flag=false;break;}}if(!flag)	continue;//右上方有放置for(int k=1;(i-k)>=1 && (j+k)<=n;k++){if(a[i-k][j+k]){flag=false;break;}}if(!flag)	continue; //当前位置能够放置，更新a，dfs(i+1),恢复aa[i][j]=1;dfs(i+1);a[i][j]=0; } //返回return; 
}int main(){ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);cin>>n;//从第1行开始dfs(1); //输出答案for(int i=0;i<3;i++){for(int j=0;j<n;j++){cout<<ans[i][j]<<" ";}cout<<"\n";} cout<<cnt;return 0;
}

二.3472 八皇后

3472. 八皇后 - AcWing题库
学习:
1.dfs思想同上一题一样
2.此题多了记录所有答案，且通过id快速访问某个答案，即数组的优点，内部元素是一个串，即string类型,开:

vector<string> ans;//解

升序排序即可(字典序)
代码:

#include <bits/stdc++.h>using namespace std;
const int N=15;
int a[N][N],n=8,m; //0未放置，1放置 
vector<string> ans;//解 //输入为横坐标i,无返回值 
void dfs(int i){//i==n+1,得到一组解，返回寻找下一组if(i==n+1){//更新ansstring s="";for(int i=1;i<=n;i++){for(int j=1;j<=n;j++){if(a[i][j])	s+=to_string(j);}} ans.emplace_back(s);} //遍历列for(int j=1;j<=n;j++){bool flag=true;//同一列有放置 for(int k=1;k<i;k++){if(a[k][j]){flag=false;break;}}if(!flag)	continue;//左上方有放置for(int k=1;(i-k)>=1 && (j-k)>=1;k++){if(a[i-k][j-k]){flag=false;break;}}if(!flag)	continue;//右上方有放置for(int k=1;(i-k)>=1 && (j+k)<=n;k++){if(a[i-k][j+k]){flag=false;break;}}if(!flag)	continue; //当前位置能够放置，更新a，dfs(i+1),恢复aa[i][j]=1;dfs(i+1);a[i][j]=0; } //返回return; 
}int main(){ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);//从第1行开始dfs(1); 			//升序 sort(ans.begin(),ans.end());cin>>m;//输出答案while(m--){int b;cin>>b;cout<<ans[b-1]<<endl;}return 0;
}

三.P1605 迷宫

P1605 迷宫 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)
学习:
1.经典图像dfs
2.记得起点更新a数组
a[sx][sy]=-1;
3.不需要以下代码:

//不能加下面一个，因为在dfs前会a[nx][ny]=-1，所以下面这个代码会直接return 
//当前位置访问过或障碍物，return
//if(a[x][y]!=0)	return; 

代码:

#include <bits/stdc++.h>using namespace std;
typedef long long ll;
int a[10][10]; //-1:访问,0:未访问,1:障碍物
int n,m,t,sx,sy,ex,ey;
int dx[]={1,-1,0,0},dy[]={0,0,1,-1};
ll ans;bool inMap(int x,int y){return 1<=x && x<=n && 1<=y && y<=m;
} //输入参数坐标x,y,无返回值 
void dfs(int x,int y){//结束if(x==ex && y==ey){ans++;return;} //不能加下面一个，因为在dfs前会a[nx][ny]=-1，所以下面这个代码会直接return //当前位置访问过或障碍物，return//if(a[x][y]!=0)	return; //访问下一个位置for(int i=0;i<4;i++){int nx=x+dx[i],ny=y+dy[i];if(!inMap(nx,ny))	continue;//访问过或障碍物，跳过if(a[nx][ny]!=0)	continue;//访问新位置a[nx][ny]=-1;dfs(nx,ny);//回溯恢复a[nx][ny]=0; } //返回return; }int main(){ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);cin>>n>>m>>t;cin>>sx>>sy>>ex>>ey;while(t--){int tx,ty;cin>>tx>>ty;a[tx][ty]=1;}//dfsa[sx][sy]=-1;dfs(sx,sy); cout<<ans;return 0;
}

四.P1434 [SHOI2002] 滑雪

学习:
1.用到记忆化,为什么要用到?
原因:
(1)遍历nxm的dfs:

//dfs
for(int i=1;i<=n;i++){for(int j=1;j<=m;j++){if(!dp[i][j]){ans=max(ans,dfs(i,j));}	}
} 

(2)确定dfs返回类型:返回值为从当前位置滑的最长长度
(3)遍历(i,j)时会获得下游左边的滑的最长长度，因此可以记忆化储存，避免重复遍历
2.记忆化优化部分:
(1)dfs遍历优化:

if(!dp[i][j]){ans=max(ans,dfs(i,j));
}	

(2)dfs内部提前return:

//如果已经算过当前位置滑的最长长度，直接返回
if(dp[x][y])	return dp[x][y];

3.dfs三步走:
(1)输入参数:
输入参数坐标x,y
(2)返回类型:
返回值为从当前位置滑的最长长度

int dfs(int x,int y){}

int cnt=1; 

return cnt; 

(3)递归条件:
隐式递归:不能往四周滑:返回cnt,不能往下滑cnt=1
4.注意:
(1)cnt初始化是1，不是0!!!
(2)更新cnt,取max操作，因为会往四周滑，不确定哪条最长

//能往下滑 
if(a[x][y]>a[nx][ny]){//这边是max cnt=max(cnt,dfs(nx,ny)+1);
}

代码:

#include <bits/stdc++.h>using namespace std;
typedef long long ll;
int a[105][105]; //高度
int dp[105][105];//从当前位置滑的最长长度 
int n,m;
int dx[]={1,-1,0,0},dy[]={0,0,1,-1};
int ans;bool inMap(int x,int y){return 1<=x && x<=n && 1<=y && y<=m;
} //输入参数坐标x,y,返回值为从当前位置滑的最长长度 
int dfs(int x,int y){//如果已经算过当前位置滑的最长长度，直接返回if(dp[x][y])	return dp[x][y]; int cnt=1; for(int i=0;i<4;i++){int nx=x+dx[i],ny=y+dy[i];if(!inMap(nx,ny))	continue;//能往下滑 if(a[x][y]>a[nx][ny]){//这边是max cnt=max(cnt,dfs(nx,ny)+1);}} //返回cnt,不能往下滑cnt=0dp[x][y]=cnt; return cnt; }int main(){ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);cin>>n>>m;for(int i=1;i<=n;i++){for(int j=1;j<=m;j++){cin>>a[i][j];}}//dfsfor(int i=1;i<=n;i++){for(int j=1;j<=m;j++){if(!dp[i][j]){ans=max(ans,dfs(i,j));}	}} cout<<ans;return 0;
}

五.指数型枚举

92. 递归实现指数型枚举 - AcWing题库
学习:
1.取/不取,2^n,不管顺序

输出案例://这是空行
3
2
2 3
1
1 3
1 2
1 2 3

2.跟8皇后一样，递归层数，即第i个数字
3.需要回溯
4.输出答案那边复杂些
5.思考为什么答案这个顺序输出，深刻理解递归!!!
6.注意:vector不是pop_back(i),是pop_back(),无参数
代码:

#include <bits/stdc++.h>using namespace std;
int n;
vector<int> ans;//输入参数第i个数，无返回值
void dfs(int i){//递归结束if(i==n+1){//输出结果if(!ans.empty()){for(auto &x:ans){cout<<x<<" ";}	} cout<<"\n";return;} //不选dfs(i+1);//选 ans.emplace_back(i);dfs(i+1);ans.pop_back();
} int main(){ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);cin>>n;dfs(1);return 0;
}

六.排列型枚举

94. 递归实现排列型枚举 - AcWing题库
学习:
1.输出样例

1 2 3
1 3 2
2 1 3
2 3 1
3 1 2
3 2 1

2.相比于上面的指数型，排列型更复杂一点，需要一个vis数组来判断这个数有没有放过
3.且dfs的参数i不是第i个数，而是放置的第i个位置(跟8皇后很像)，需要遍历数字1-n，去判断有没有放过然后dfs(i+1)
4.需要回溯
5.注意:不要用visit,会有歧义，尽量用缩写vis
代码:

#include <bits/stdc++.h>using namespace std;
int n;
vector<int> ans;
int vis[10]; //某个数是否放过 //输入参数为排列答案的第i个次序,无返回值
void dfs(int i){//递归结束if(i==n+1){//输出结果for(auto &x:ans){cout<<x<<" ";}	cout<<"\n";return;} //遍历1-nfor(int j=1;j<=n;j++){//j摆第i位if(!vis[j]){ans.push_back(j);vis[j]=1;dfs(i+1); ans.pop_back();vis[j]=0;}	} 
} int main(){ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);cin>>n;dfs(1);return 0;
}

七.组合型枚举

93. 递归实现组合型枚举 - AcWing题库
学习:
1.输入样例:

5 3

即5个数排3个位置
输出样例:

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

(1)与排列型枚举不同的是，排列位置变成m，小于n，改个递归结束条件即可
(2)要求组合数字升序，对dfs加一个参数x,表示前i-1放的值x,遍历从1-n变成x+1-n即可
代码:

#include <bits/stdc++.h>using namespace std;
int n,m;
vector<int> ans;
int vis[10]; //某个数是否放过 //输入参数为排列答案的第i个次序,前i-1放的值x,无返回值
void dfs(int i,int x){//递归结束if(i==m+1){//输出结果for(auto &x:ans){cout<<x<<" ";}	cout<<"\n";return;} //遍历x+1-nfor(int j=x+1;j<=n;j++){//j摆第i位if(!vis[j]){ans.push_back(j);vis[j]=1;dfs(i+1,j); ans.pop_back();vis[j]=0;}	} 
} int main(){ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);cin>>n>>m;dfs(1,0);return 0;
}

八.油田 Oil Deposits

油田 Oil Deposits - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)
学习:
1.连通块问题，因为要一个区域一个区域的判断，所以要对整个地图遍历进行dfs，通过一个vis数组判断是否访问过确保一个连通块只访问一次
2.因为这是多次输入，所以maze和vis开局部变量，要传入到dfs中，引用传递更快
代码:

#include <bits/stdc++.h>using namespace std;
typedef long long ll;
int n,m;
//横，竖，对角线 
int dx[]={1,1,0,-1,-1,-1,0,1},dy[]={0,1,1,1,0,-1,-1,-1};bool inMap(int x,int y,const int &n,const int &m){return 1<=x && x<=n && 1<=y && y<=m;
}//无返回值，输入地图，坐标和结果 
void dfs(vector<vector<char>> &maze,vector<vector<int>> &vis,int x,int y,const int &n,const int &m){//标记访问过vis[x][y]=1;//向四周访问for(int i=0;i<8;i++){int nx=x+dx[i],ny=y+dy[i];if(!inMap(nx,ny,n,m))	continue;//未访问过的油田继续搜索if(!vis[nx][ny] && maze[nx][ny]=='@'){dfs(maze,vis,nx,ny,n,m);} } }int main(){ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);cin>>n>>m;while(n!=0 || m!=0){vector<vector<char>> maze(n+1,vector<char>(m+1,'0'));vector<vector<int>> vis(n+1,vector<int>(m+1,0)); //判断是否搜索过,0:未搜索过,1:搜索过 for(int i=1;i<=n;i++){for(int j=1;j<=m;j++){cin>>maze[i][j];}}ll ans=0;//搜索油田区域 for(int i=1;i<=n;i++){for(int j=1;j<=m;j++){//未搜索过的油田搜索 if(!vis[i][j] && maze[i][j]=='@'){dfs(maze,vis,i,j,n,m);ans++;}}}cout<<ans<<endl;cin>>n>>m; }return 0;
}

九.P1019 [NOIP2000 提高组] 单词接龙

P1019 [NOIP2000 提高组] 单词接龙 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)
学习:
1.dfs是简单的，就是回溯
2.难点在于dfs参数传什么，怎么寻找拼接位置
3.每次搜索完更新了总的拼接字符串，答案也求总的拼接字符串的最大长度，故dfs传入参数就是当前总的拼接字符串,直接用max更新ans即可，难点就在于怎么寻找拼接位置
4.利用substr寻找拼接位置:
substr(i,j):获取子字符串[i,j)
substr(i):获取子字符串[i,最后)

//寻找下一个拼接的字符串for(int i=1;i<=n;i++){if(vis[i]>=2)	continue;//获取拼接位置,j从1开始,后面min保证两个字符串不存在包含关系for(int j=1;j<min( (int)str.size(),(int)s[i].size() );j++){//最难的部分,str:[str.size()-j,最后),s[i]:[0,j) if(str.substr(str.size()-j)==s[i].substr(0,j)){vis[i]++;//拼接:s[i]:[j,最后) dfs(str+s[i].substr(j));vis[i]--;} } } 

十.821. 跳台阶

821. 跳台阶 - AcWing题库
学习:
1.可以用动态规划
2.可以暴力dfs
3.可以记忆化
代码:
1.暴力:

#include <bits/stdc++.h>using namespace std;
typedef long long ll;
int n;
ll ans;//输入第i级台阶，无返回值，无需回溯
void dfs(int i){//递归结束if(i>n)	return;if(i==n){ans++;} //走1级dfs(i+1);//走2级 dfs(i+2);
} int main(){ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);cin>>n;dfs(0);cout<<ans;return 0;
}

2.记忆化

#include <bits/stdc++.h>using namespace std;
typedef long long ll;
int n;
ll ans;
ll dp[20];//输入第i级台阶，返回当前台阶到第n级的方案，无需回溯
ll dfs(int i){//剪枝if(dp[i])	return dp[i]; //递归结束if(i>n)	return 0;if(i==n)	return dp[i]=1;ll cnt=0;//走1级或2级 cnt=dfs(i+1)+dfs(i+2);return dp[i]=cnt;
} int main(){ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);cin>>n;cout<<dfs(0);return 0;
}

十一.P1036 [NOIP 2002 普及组] 选数

P1036 [NOIP 2002 普及组] 选数 - 洛谷
学习:
1.组合型枚举
2.这题题意有些不清楚，要求:计算出和为素数共有多少种,但是同一个素数是算多次，而不是算一次，不用set判断
代码:

//组合型枚举 
#include <bits/stdc++.h>using namespace std;
const int N=25;
int a[N];
int n,k;
set<int> flag;
int ans;bool isZhi(int x){//<=1肯定不是if(x<=1)	return false;else if(x==2)	return true;else{for(int i=2;i<=sqrt(x);i++){if(x%i==0)	return false;}return true;} 
}//无返回值，输入为当前选第i个数, 第i-1个数选的是第j个数,前i-1个数的和 
void dfs(int i,int j,int cnt){//递归结束if(i==k){if(isZhi(cnt)){		ans++;			}return;} //如果k-i>n-(j+1)+1=n-j,则选不够if(k-i>n-j)	return; //选j+1-nfor(int x=j+1;x<=n;x++){dfs(i+1,x,cnt+a[x]);} 
}int main(){ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);cin>>n>>k;for(int i=1;i<=n;i++)	cin>>a[i];for(int t=1;t<=n-k+1;t++){dfs(1,t,a[t]);}cout<<ans;return 0;
}

十二.P2089 烤鸡

P2089 烤鸡 - 洛谷
学习:
1.排列型枚举，但是层数是10，每层有3种选择，需要剪枝
2.注意这里的N最大值不是n的最大值，而是方案的最大值，尽可能开大点，不然最后两个测试点过不去
代码:

//排列型枚举 
#include <bits/stdc++.h>using namespace std;
const int N=100000;
int a[N][10],b[10];
int n,ans;//输入为第i个调味料,当前总质量之和,无返回值,无需回溯 
void dfs(int i,int cnt){//剪枝 if(cnt>n)	return;//不能有0 if(cnt+10-i>n)	return;//递归结束if(i==10){if(cnt==n){for(int j=0;j<10;j++){a[ans][j]=b[j];}ans++;}return;} //搜索for(int j=1;j<=3;j++){b[i]=j;dfs(i+1,cnt+j);} 
} int main(){ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);cin>>n;dfs(0,0);if(ans==0)	cout<<0;else{cout<<ans<<"\n";for(int i=0;i<ans;i++){for(int j=0;j<10;j++){cout<<a[i][j]<<" ";}cout<<"\n";}}return 0;
}

十三.P1088 [NOIP 2004 普及组] 火星人

P1088 [NOIP 2004 普及组] 火星人 - 洛谷
学习:
1.排列型枚举，O(N!)，N太大会超时
2.调用算法库函数next_permutation,它接受一个范围（通常是数组的起始和结束迭代器），并将范围内的元素重新排列为下一个字典序更大的排列,然后重新排列m次即可
代码:

#include <bits/stdc++.h>
using namespace std;
int a[100000];
int n,m;int main()
{ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);cin>>n>>m;for(int i=1;i<=n;++i) cin>>a[i];for(int i=1;i<=m;++i) next_permutation(a+1,a+n+1);for(int i=1;i<=n;++i) cout<<a[i]<<" ";return 0;
}