Buer blog | 详情

方法介绍

回溯是一种搜索方式，回溯的本质是穷举，穷举所有可能，然后选出一个想要的答案，如果想要回溯法更高效一点，可以加一些剪枝操作，但也改不了回溯法就是穷举的本质。所以回溯法并不高效，使用他是因为没得选，有些问题能暴力出来就不错了，撑死再剪枝一下。回溯一般能解决的问题如下：

组合问题：N个数里面按一定规则找出k个数的集合
切割问题：一个字符串按一定规则有几种切割方式
子集问题：一个N个数的集合里有多少符合条件的子集
排列问题：N个数按一定规则全排列，有几种排列方式
棋盘问题：N皇后，解数独等等

所有的回溯法都可以抽象成树形结构，因为回溯法解决的都是在集合中递归查找子集，集合的大小就构成了树的宽度，递归的深度就构成了树的深度。

回溯伪代码：

void backtracking(参数) {
    if (终止条件) {
        存放结果;
        return;
    }

    for (选择：本层集合中元素（树中节点孩子的数量就是集合的大小）) {
        处理节点;
        backtracking(路径，选择列表); // 递归
        回溯，撤销处理结果
    }
}

1336: 练57.1 全排列问题

#include <bits/stdc++.h>
using namespace std;

int f[11];//标记哪些数字使用过
int a[11];// 存放全排列的结果
int n;//输入的数字
//递归函数:为a数组每个元素赋值 
void backtrack(int k){//k代表搜索的层数或深度 
	if(k>n){//所有层安置完（走到了最深），输出存储好的答案 
		for(int i=1;i<=n;i++){
			printf("%5d",a[i]);
		}
		printf("\n"); 
	} 
	for(int i=1;i<=n;i++){//当前层数对应的位置所有的安置可能 
		if(!f[i]){//如果前面的层还没用过i，就存起来并打标记 
			a[k]=i;
			f[i]=true;//保留现场 
			backtrack(k+1);//继续向内层 递归
			f[i]=false;//恢复 
		} 
	} 
} 

int main(){
	scanf("%d",&n);
	backtrack(1);
	return 0;
}

2062: 大洪水

#include<bits/stdc++.h>
using namespace std;
int n,m,ans;
char a[1005][1005];
void dfs(int x,int y){
	if(x<1||x>n||y<1||y>m||a[x][y]=='0') return;
	a[x][y]='0';
	dfs(x+1,y);
	dfs(x-1,y);
	dfs(x,y+1);
	dfs(x,y-1);
}
int main(){
	cin>>n>>m;
	memset(a,'0',sizeof(a));
	for(int i=1;i<=n;i++){
		for(int j=1;j<=m;j++){
			cin>>a[i][j];
		}
	}
	for(int i=1;i<=n;i++){
		for(int j=1;j<=m;j++){
			if(a[i][j]!='0'){
				ans++;
				dfs(i,j);
			}
		}
	}
	cout<<ans;
}

P2802 回家

#include<bits/stdc++.h>
#define MAXN 10
#define inf 0x3f3f3f3f
using namespace std;
int a[MAXN][MAXN], vis[MAXN][MAXN];
int n, m, sx, sy, fx, fy;// (sx,sy)为起点坐标，(fx,fy)为终点坐标，当然n，m是行和列
int sum;//用来统计最少步数的，一开始要初始化为最大(如上面预处理inf）
int to[][2] = { {0,1},{0,-1},{-1,0},{1,0} };//模拟4个方向
void dfs(int u, int v,int ans,int t)//(u,v)代表当前小H所在坐标，ans记录当前的血量，t记录到目前为止已耗费的时间
{
	if (u == fx && v == fy)//到家啦~
	{
		sum = min(sum, t);//保留最小步数
		return;
	}
	if (t >= sum)//这个if是后加的，是为了剪枝（之前没加也过了。。）当然，如果都模拟到这一步了，小H还没到达终点时，t就已经比之前的一种到达家的路径所耗费时间更多了，这条路就不再下去了
		return;
	if (ans > 1)//这是之前所说的，我在模拟每一步之前，我的血量一定要大于1，不然就返回了（返回相当于这段的dfs没执行了，因为if外边下面啥没有= =）
	{
		for (int i = 0; i < 4; i++)//模拟出上下左右走
		{
			int q = u + to[i][0], w = v + to[i][1];//模拟走一格之后的坐标
			if (q >= 0 && q < n&&w >= 0 && w < m && vis[q][w]<=22 && a[q][w] != 0)//走到这个格子时，我不能超边界&&限制每个格子所走的步数&&不能是大板墙~
			{
				vis[q][w] ++;//走过的次数+1
				if (a[q][w] == 4)
				{
					dfs(q, w, 6, t + 1);//如果我走到了4了，当然我就回满血了~~ 并且步数+1
				}
				else
				{
					dfs(q, w, ans - 1, t + 1);//否则我走到这只是扣血，步数也要+1
				}
				vis[q][w] --;//减少这个格子的次数，消除影响
			}
		}
	}
}
int main()
{
	cin >> n >> m;
	sum = inf;//初始化
	memset(vis, 0, sizeof(vis));//初始化
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < m; j++) {
			cin >> a[i][j];
			if (a[i][j] == 2)
				sx = i, sy = j;//找出起点坐标
			else if (a[i][j] == 3)
				fx = i, fy = j;//找出家坐标
		}
	}
	dfs(sx, sy, 6, 0);//从起点开始，血量为6，步数为0。开始深搜
	if (sum == inf)//如果sum没有被更新，那就说明没有达到家
		cout << "-1" << endl;
	else
		cout << sum << endl;//否则输出这个最短时间
	return 0;
}