搜索与回溯

有重复元素的排列问题

题目描述

设R={r1，r2，……，rn}是要进行排列的n个元素。其中元素r1，r2，……，rn可能相同。使设计一个算法，列出R的所有不同排列。

给定n以及待排列的n个元素。计算出这n个元素的所有不同排列。

输入

第1行：元素个数n（1<=n<500）

第2行：一行字符串，待排列的n个元素,都是小写字母

输出

计算出的n个元素的所有不同排列（按字典序），最后一行是排列总数。

思路一：使用STL的next_permutation。next_permutation可以生成字典序的下一个排列， 当到达最大排列时（降序排列）自动终止。

但在 n 较大时会超时！！！本题就超时了

#include<iostream> #include<algorithm> using namespace std; int main(){ int n,num=0; string s; cin>>n>>s; // 先将字符串升序排序，才能获得所有全排列 sort(s.begin(),s.end()); do{ cout<<s<<endl; num++; }while(next_permutation(s.begin(), s.end())); cout<<num; return 0; }

思路二：回溯 + DFS

#include<iostream> using namespace std; int n,num; string s; // 存储a-z个数 int zm[27]; // 存储当前排列 char path[505]; void print(){ for(int i=0;i<n;i++){ cout<<path[i]; } cout<<'\n'; // 防止时间超限 } void dfs(int index){ if(index==n){ print(); num++; return; } // 从小到大遍历字母尝试填入 for(int i=1;i<=26;i++){ if(zm[i]>0){ path[index]='a'+(i-1); zm[i]--; dfs(index+1); zm[i]++; // 回溯 } } } int main(){ ios::sync_with_stdio(false); // 防止时间超限 cin.tie(nullptr); cin>>n>>s; for(int i=0;i<s.size();i++){ zm[s[i]-'a'+1]++; } dfs(0); cout<<num; return 0; }

组合的输出

题目描述

从n个元素中抽出r个元素(不分顺序且r<＝n)，简单地将n个元素理解为自然数1，2，…，n，从中任取r个数。输出所有组合。

例如n＝5，r＝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

输入

一行两个自然数n、r(1<n<21，1<＝r<＝n)。

输出

所有的组合，每一个组合占一行且其中的元素按由小到大的顺序排列，每个元素占三个字符的位置（右对齐），所有的组合也按字典顺序。

思路：递归 + 回溯，保证元素严格递增

#include<iostream> using namespace std; int n,r; int path[22]; void print(){ for(int i=0;i<r;i++){ printf("%3d",path[i]); } cout<<'\n'; } void dfs(int index,int p){ if(index==r){ print(); return; } for(int i=p;i<=n;i++){ path[index]=i; // 元素递增，下一个元素>当前 dfs(index+1,i+1); } } int main(){ cin>>n>>r; dfs(0,1); return 0; }

N皇后问题

题目描述

在N*N的棋盘上放置N个皇后（n<=10）而彼此不受攻击（即在棋盘的任一行，任一列和任一对角线上不能放置2个皇后），编程求解所有的摆放方法。

输入

n

输出

每行输出一种方案，每种方案顺序输出皇后所在的列号，每个数占5列（输出时按字典序）。若无方案，则输出no solute!

思路：同行、同列、同对角线（行差 = 列差）不能放

代码：

#include<iostream> using namespace std; int n,count; // 存放每行棋子的列号 int path[15]; bool is_valid(int ind,int col){ // 遍历已经放好的所有行 for(int i=1;i<ind;i++){ // 同列 if(path[i]==col){ return false; } if(abs(ind-i)==abs(col-path[i])){ return false; } } return true; } void dfs(int index){ if(index==n+1){ count++; for(int i=1;i<=n;i++){ printf("%5d",path[i]); } cout<<'\n'; return; } for(int i=1;i<=n;i++){ // 第index行，第i列是否合规 if(is_valid(index,i)){ path[index]=i; dfs(index+1); } } } int main(){ cin>>n; dfs(1); if(count==0){ cout<<"no solute!"; } return 0; }

子集和问题

题目描述

S={ x1， x2，…， xn}是一个正整数的集合，c是一个正整数。判定是否存在S的一个子集S1，使得子集S1和等于c。

输入

第1行有2个正整数n和c，n表示S的个数，c是子集和的目标值。接下来的1 行中，有n个正整数，表示集合S中的元素。

输出

当问题无解时，输出“No Solution!”。
如果有多个解，输出子集 数字下标字典序最小的解

子集和 = 每个数 选 / 不选，最终和等于 c；下标字典序最小 = 优先选前面的数字

思路一：从左到右遍历数字（n ≤ 20）

1. 先尝试选当前这个数字
2. 判断：选了它之后，剩下的目标和，能不能被后面的数字凑出来
3. 能凑出来 → 选
4. 不能凑出来 → 不选，试下个数字

#include<iostream> #include<vector> using namespace std; int n,c; vector<int>v; vector<int>ans; //选第index个数，当前和为sum，能否凑到c bool dfs(int index,int sum){ if(sum==c) return true; //当前和超了|n个数已经选完 if(sum>c||index>=n) return false; //尝试当前数 ans.push_back(v[index]); if(dfs(index+1,sum+v[index])){ //能凑成c return true; } ans.pop_back(); //不能选，不选 return dfs(index+1,sum); //尝试下一个数 } int main(){ cin>>n>>c; v.resize(n); for(int i=0;i<n;i++) cin>>v[i]; if(dfs(0,0)){ for(int i=0;i<ans.size();i++){ cout<<ans[i]<<" "; } }else{ cout<<"No Solution!"; } return 0; }

时间超限73%！

思路二：01背包（n ≤ 1000）。定义dp[j]：是否能凑出和为 j 的子集，初始化dp[0] = True

再找字典序最小解，从第一个数字开始，能选就选，直到凑出目标和

#include<iostream> #include<vector> using namespace std; int n,c; vector<int>v; vector<bool>dp; int main(){ cin>>n>>c; v.resize(n); dp.resize(c+1); for(int i=0;i<n;i++) cin>>v[i]; dp[0]=true; for(int i=0;i<n;i++){ for(int j=c;j>=v[i];j--){ dp[j]=dp[j]||dp[j-v[i]]; //j能凑出或j-v[i]能凑出 } } if(dp[c]){ int res=c; for(int i=0;i<n;i++){ if(res>=v[i]&&dp[res-v[i]]){ //当前数字可以选，选后剩余和能被凑出 cout<<v[i]<<" "; res-=v[i]; if(res==0){ return 0; } } } }else{ cout<<"No Solution!"; } return 0; }

时间超限36%！

思路三：DFS + 剪枝优化。和超限剪枝、剩余和不足剪枝、找到解立即停止

#include<iostream> #include<vector> using namespace std; int n,c,total; vector<int>v; //存储数据 vector<int>path; //存储解 //从第index个元素开始，当前和为sum，剩余元素和为remain，能否凑到c bool dfs(int index,int sum,int remain){ if(sum==c) return true; //找到解，直接返回 if(sum>c||index>=n) return false; //和超过|所有数已遍历，退出 if(remain+sum<c) return false; //剩余解+当前和<目标，退出 path.push_back(v[index]); //添加当前元素 remain-=v[index]; //剩余和-当前元素（不可能再选） if(dfs(index+1,sum+v[index],remain)){ //能凑到c return true; } path.pop_back(); //弹出当前元素 return dfs(index+1,sum,remain); //不选当前元素，试下一个元素 } int main(){ cin>>n>>c; v.resize(n); for(int i=0;i<n;i++){ cin>>v[i]; total+=v[i]; //总和 } if(dfs(0,0,total)){ //从第0个开始，和为0，剩余总和 for(int i=0;i<path.size();i++){ cout<<path[i]<<" "; } return 0; } cout<<"No Solution!"; return 0; }

图的m着色问题

题目描述

对于给定的无向连通图G和m种不同的颜色，如果有一种着色法使G中每条边的2个顶点着不同颜色，则称这个图是m可着色的。

输入

第1行有3个正整数n（n<=100），k 和m，表示给定的图G有n个顶点和k条边，m种颜色。顶点编号为1，2，…，n。接下来的k行中，每行有2个正整数u,v，表示图G 的一条边(u,v)。

输出

不同的着色方案数

思路：DFA+回溯。遍历顶点，给当前顶点尝试所有颜色（遍历相邻顶点，确保颜色不重复），能着色则递归下一个顶点。所有顶点染色完成，方案数 + 1。

#include<iostream> using namespace std; int n,k,m,sum; //graph表示图的连通性，color标记顶点颜色 int graph[101][101],color[101]; bool is_valid(int v,int c){ for(int i=1;i<=n;i++){ //遍历相邻边 if(graph[i][v]&&color[i]==c){ //如果和相邻边的颜色一样，颜色不能涂 return false; } } return true; } void dfs(int index){ if(index==n+1){ //若所有顶点都已涂色，方案数+1 sum++; return; } for(int i=1;i<=m;i++){ //遍历颜色 if(is_valid(index,i)){ color[index]=i; //能涂则上色 dfs(index+1); //涂下一个 color[index]=0; //回溯 } } } int main(){ cin>>n>>k>>m; int u,v; for(int i=0;i<k;i++){ cin>>u>>v; graph[u][v]=1; graph[v][u]=1; //无向图 } dfs(1); //从顶点1开始 cout<<sum; return 0; }

自然数的拆分问题

题目描述

任何一个大于1的自然数n，总可以拆分成若干个小于n的自然数之和。现在给你一个自然数n，要求你求出n的拆分成一些数字的和。每个拆分后的序列中的数字从小到大排序，且字典序小的序列需要优先输出。

输入

待拆分的自然数n。

输出

若干数的加法式子

思路：DFA + 回溯

#include<iostream> #include<vector> using namespace std; int n; vector<int>ans; //存储解 void dfs(int cur,int sum){ //当前数字为cur，当前累加和sum if(sum==n){ //找到一个解 cout<<ans[0]; for(int i=1;i<ans.size();i++){ cout<<"+"<<ans[i]; } cout<<endl; return; } //从cur开始选(递增)，最大不超过剩余和 且 不能是数本身 for(int i=cur;i<=n-sum&&i<n;i++){ ans.push_back(i); dfs(i,sum+i); ans.pop_back(); //回溯 } } int main(){ cin>>n; dfs(1,0); //入口 return 0; }

整数的划分

题目描述

将整数n分成k份，且每份不能为空，任意两个方案不相同(不考虑顺序)，问有多少种不同的分法。

例如：n=7，k=3，下面三种分法被认为是相同的。

1,1,5;
1,5,1;
5,1,1.

输入

n,k (6<n≤200，2≤k≤6)

输出

1个整数，即不同的分法。

思路：定义dp[ i ][ j ]为把数字 i 分成 j 份的方案数。状态转移方程分两种情况：1.至少含有一个数字1，dp[i][j]=dp[i-1][j-1]；2.不含有1，每个数都>=2，则将每一个数都-1，dp[i][j]=dp[i-j][j]。

所以，dp[i][j]=dp[i-1][j-1]+dp[i-j][j]

代码：

#include<iostream> using namespace std; //dp[i][j]表示将i分为j份的方案数 int dp[205][10]; int main(){ int n,k; cin>>n>>k; for(int i=1;i<=n;i++){ for(int j=1;j<=k;j++){ if(i<j) dp[i][j]=0; else if(i==j) dp[i][j]=1; else dp[i][j]=dp[i-1][j-1]+dp[i-j][j]; } } cout<<dp[n][k]; return 0; }

面积

题目描述

编程计算由“*”号围成的下列图形的面积。如下图所示，在10*10的二维数组中，“*”围住了15个点，因此面积为15。

0 0 0 0 0 0 0 0 0 0

0 0 0 0 * * * 0 0 0

0 0 0 0 * 0 0 * 0 0

0 0 0 0 0 * 0 0 * 0

0 0 * 0 0 0 * 0 * 0

0 * 0 * 0 * 0 0 * 0

0 * 0 0 * * 0 * * 0

0 0 * 0 0 0 0 * 0 0

0 0 0 * * * * * 0 0

0 0 0 0 0 0 0 0 0 0

输入

输入矩阵，其中*用数字1代替

输出

输出面积

思路：把所有和边界连通的 0全部标记掉，最后统计矩阵里剩下的0即可

代码：

#include<iostream> using namespace std; int graph[10][10]; int dx[4]={0,0,-1,1},dy[4]={-1,1,0,0}; void dfs(int i,int j){ graph[i][j]=1; for(int k=0;k<4;k++){ int x=i+dx[k],y=j+dy[k]; if(x<0||x>9||y<0||y>9) continue; // 注意越界判断 if(graph[x][y]==0){ dfs(x,y); } } } int main(){ for(int i=0;i<10;i++){ for(int j=0;j<10;j++){ cin>>graph[i][j]; } } for(int i=0;i<10;i++){ if(graph[0][i]==0){ dfs(0,i); } } for(int i=0;i<10;i++){ if(graph[9][i]==0){ dfs(9,i); } } for(int i=0;i<10;i++){ if(graph[i][0]==0){ dfs(i,0); } } for(int i=0;i<10;i++){ if(graph[i][9]==0){ dfs(i,9); } } int sum=0; for(int i=0;i<10;i++){ for(int j=0;j<10;j++){ if(graph[i][j]==0){ sum++; } } } cout<<sum; return 0; }

BFS扩展

最少转弯问题

题目描述

n×m（n,m<=100）个方块，任何一个方块不是平地就是高山。平地可以通过，高山则不能。现在你处在地图的（x1,y1）这块平地，问：你至少需要拐几个弯才能到达目的地（x2,y2）？如图，最少的拐弯次数为5。

思路：沿直线扩展的 BFS。用dist记录到达每个点的最少拐弯次数，初始化为无穷大，起点拐弯次数为 0。从当前点向四个方向一直走，直到 出界 / 高山，同一方向的所有点拐弯次数 = 当前点 + 1，更新后入队。第一次到达终点时，输出拐弯次数。

代码：

#include<iostream> #include<queue> #include<cstring> using namespace std; const int INF=0x3f3f3f3f; int n,m,sx,sy,ex,ey; int graph[101][101]; int dist[101][101]; int dx[4]={-1,1,0,0}; int dy[4]={0,0,-1,1}; int bfs(){ queue<pair<int,int>>q; q.push({sx,sy}); dist[sx][sy]=-1; // 从起点向任何方向的拐弯次数为0 while(!q.empty()){ auto now=q.front(); q.pop(); int x=now.first,y=now.second; if(x==ex&&y==ey){ return dist[ex][ey]; } for(int i=0;i<4;i++){ int xx=x+dx[i],yy=y+dy[i]; //只要不越界、不是高山，就一直走 while(xx>=1&&xx<=n&&yy>=1&&yy<=m&&graph[xx][yy]!=1){ // 如果这个点的拐弯次数能更小，就更新 if(dist[xx][yy]>dist[x][y]+1){ dist[xx][yy]=dist[x][y]+1; q.push({xx,yy}); } // 继续沿当前方向 xx+=dx[i],yy+=dy[i]; } } } return -1; } int main(){ cin>>n>>m; for(int i=1;i<=n;i++){ for(int j=1;j<=m;j++){ cin>>graph[i][j]; } } cin>>sx>>sy>>ex>>ey; memset(dist,INF,sizeof(dist)); cout<<bfs(); return 0; }