文章目录
- 2.1 深搜
- 定义&模板
- acwing3429全排列
- 洛谷1238走迷宫
- acwing843N皇后问题
- acwing2404自然数的拆分问题
小标题的超链接为原题链接,点击跳转
2.1 深搜
定义&模板
回溯法是一种选优搜索法,又称为试探法,按选优条件向前搜索,以达到目标。但当探索到某一步时,发现原先选择并不优或达不到目标,就退回一步重新选择,这种走不通就退回再走的技术为回溯法,而满足回溯条件的某个状态的点称为“回溯点”。
回溯基于深度优先搜索算法(英语:Depth-First-Search,简称DFS),这是一种用于遍历或搜索树或图的算法。
————————————————
版权声明:本文为CSDN博主「Bow.贾斯汀」的原创文章,遵循CC 4.0
BY-SA版权协议,转载请附上原文出处链接及本声明。
原文链接:https://blog.csdn.net/qq_61323055/article/details/124898025
回溯法的应用:
- 组合问题:N个数里面按一定规则找出k个数的集合
- 切割问题:一个字符串按一定规则有几种切割方式
- 子集问题:一个N个数的集合里有多少符合条件的子集
- 排列问题:N个数按一定规则全排列,有几种排列方式
- 棋盘问题:N皇后,解数独等等
// 基本模板
int check(参数)
{
if(满足条件)
return 1;
return 0;
}
void dfs(int step)
{
判断边界
{
相应操作
}
尝试每一种可能
{
满足check条件
标记
继续下一步dfs(step+1)
恢复初始状态(回溯的时候要用到)
}
}
acwing3429全排列
题目
代码
#include<bits/stdc++.h>
using namespace std;
const int N = 1e2;
char ans[N]; // 排列结果
char a[N]; // input
bool v[N]; // v[i]用于标记第i个字符是否使用过
int n;
void dfs(int d)
{
if(d==n+1)
{
for(int i=1; i<=n; i++) cout << ans[i];
cout << endl;
return;
}
for(int i=1; i<=n; i++)
{
if(!v[i])
{
ans[d] = a[i];
v[i] = true;
dfs(d+1);
ans[d] = 0;
v[i] = false;
}
}
return;
}
int main()
{
string input;
cin >> input;
n = input.size();
for(int i=1; i<=n; i++) a[i] = input[i-1];
// for(int i=1; i<=n; i++) cout << a[i];
dfs(1);
}
洛谷1238走迷宫
题目
代码
// 迷宫问题
#include <bits/stdc++.h>
using namespace std;
const int N = 1010;
typedef pair<int, int> PII;
#define x first
#define y second
// 方向数组
int dx[4]={0,-1,0,1};
int dy[4]={-1,0,1,0};
int n, m;// 地图大小
int a[N][N];// 地图的值
int v[N][N];// 标记数组,记录走过的点
vector<PII> ans;// 存储路径
PII st, ed;// 存放起点和终点的位置
bool flag = false; // 保存是否有解
bool boundary(int x, int y)
{
if(x<=n && x>=1 && y<=m && y>=1) return true;
else return false;
}
bool check(int x, int y)
{
return (boundary(x, y) && a[x][y] && !v[x][y]); // 边界
}
void dfs(PII now)
{
if(now.x == ed.x && now.y == ed.y) // 出口
{
flag = true;
for(int i=0; i<ans.size()-1; i++) cout << "(" << ans[i].x << "," << ans[i].y << ")" << "->";
cout << "(" << ans[ans.size()-1].x << "," << ans[ans.size()-1].y << ")" << endl;
}
for(int k=0; k<4; k++)
{
PII nxy;
nxy.x = now.x + dx[k];
nxy.y = now.y + dy[k];
if(check(nxy.x, nxy.y))
{
v[nxy.x][nxy.y] = true;
ans.push_back(nxy);
dfs(nxy);
ans.pop_back();
v[nxy.x][nxy.y] = false;
}
}
return;
}
int main()
{
cin >> n >> m;
for(int i=1; i<=n; i++)
for(int j=1; j<=m; j++)
cin >> a[i][j];
cin >> st.x >> st.y >> ed.x >> ed.y;
// 起点已经经过
v[st.x][st.y] = 1;
ans.push_back(st);
dfs(st);
if(!flag) cout << "-1" << endl;
return 0;
}
acwing843N皇后问题
题目
代码
// acwing843N皇后问题
#include <bits/stdc++.h>
using namespace std;
typedef pair<int, int> PII;
#define x first
#define y second
vector<int> row(30);
vector<int> col(30);
vector<int> LL(30);
vector<int> RR(30);
char ans[11][11];
int n;
void print()
{
for(int i=1; i<=n; i++)
{
for(int j=1; j<=n; j++)
{
cout << ans[i][j];
}
cout << endl;
}
}
bool check()
{
if(count(row.begin(), row.end(), 2)) return false;
if(count(col.begin(), col.end(), 2)) return false;
if(count(LL.begin(), LL.end(), 2)) return false;
if(count(RR.begin(), RR.end(), 2)) return false;
return true;
}
void dfs(int d)
{
if(d == n+1)
{
print();
cout << endl;
return;
}
for(int i=1; i<=n; i++)
{
row[d]++, col[i]++, LL[d+(n-i+1)-1]++, RR[d+i-1]++, ans[d][i]='Q';
if(check()) dfs(d+1);
row[d]--, col[i]--, LL[d+(n-i+1)-1]--, RR[d+i-1]--, ans[d][i]='.';
}
}
int main()
{
cin >> n;
for(int i=1; i<=n; i++)
for(int j=1; j<=n; j++)
ans[i][j] = '.';
dfs(1);
return 0;
}
acwing2404自然数的拆分问题
题目
代码
// acwing2404自然数的拆分问题
#include <bits/stdc++.h>
using namespace std;
int n;
vector<int> ans(10);
bool check(int x)
{
return x <= n;
}
void print(int l)
{
for(int i=1; i<l-1; i++)
{
cout << ans[i] << "+";
}
cout << ans[l-1] << endl;
}
void dfs(int s, int l, int now)
{
if(s == n)
{
print(l);
return;
}
for(int i=now; i<n; i++)
{
int ns = s+i;
ans[l] = i;
if(check(ns)) dfs(ns, l+1, i);
ans[l] = 0;
}
}
int main()
{
cin >> n;
dfs(0, 1, 1);
}