链接索引🔗：
第五章 搜索与回溯算法
特别注意：这一章的题目相对于其他算法题目来说比较难，除动态规划外，算是最难的题目。不过，细心 + 基础扎实 + 聪明 = 成功！
废话不多说，开始！
1317：【例5.2】组合的输出
#include <iostream>
#include <vector>
using namespace std;
// dfs函数用于深度优先搜索
void dfs(int start, int n, int r, vector<int>& ***bo) {
// 如果组合的长度等于r，打印当前组合
if (***bo.size() == r) {
for (int i = 0; i < r; i++) {
cout << " " << ***bo[i]; // 每个元素占三个字符的位置
}
cout << endl;
return;
}
// 从start到n遍历每个可能的元素
for (int i = start; i <= n; i++) {
***bo.push_back(i); // 将当前元素添加到组合中
dfs(i + 1, n, r, ***bo); // 递归调用，注意i+1作为新的起点
***bo.pop_back(); // 回溯，移除最后一个元素，尝试下一个可能的元素
}
}
int main() {
int n, r;
cin >> n >> r; // 从用户输入读取n和r的值
vector<int> ***bo; // 用于存储当前的组合
dfs(1, n, r, ***bo); // 从1开始搜索
return 0;
}
#include <bits/stdc++.h>
using namespace std;
int n, r;
vector<int> ans;
vector<bool> vis;
void dfs(int dep);
int main(){
cin >> n >> r;
ans.resize(n + 10, 0);
vis.resize(n + 10, false);
dfs(1);
return 0;
}
void dfs(int dep){
if (dep == r + 1){
for (int i = 1; i < dep; i++){
cout << setw(3) << ans[i];
}
cout << endl;
}
for (int i = ans[dep - 1] + 1; i <= n; i++){
if (!vis[i]){
vis[i] = 1;
ans[dep] = i;
dfs(dep + 1);
vis[i] = 0;
}
}
}
两种方法自己选，我做的是第二种
1318：【例5.3】自然数的拆分
#include <iostream>
#include <vector>
using namespace std;
void dfs(int n, vector<int>& path, int start, int originalN) {
if (n == 0 && path.size() > 1) { // 确保路径包含至少两个数字
cout << originalN << "=";
for (size_t i = 0; i < path.size(); ++i) {
cout << path[i];
if (i < path.size() - 1) cout << "+";
}
cout << endl;
return;
}
for (int i = start; i <= n; ++i) {
path.push_back(i);
dfs(n - i, path, i, originalN);
path.pop_back();
}
}
int main() {
int n;
cin >> n;
vector<int> path;
dfs(n, path, 1, n);
return 0;
}
1212：LETTERS
· 使用一个整数（假设是32位）的每一位来代表一个字母是否被访问过。由于大写字母总共有26个，因此我们只需要26位就足够了。例如，如果’A’被访问过，那么我们就将第0位设为1。
· 每次访问一个新的字母时，我们检查相应的位是否为0（表示该字母还未被访问过）。如果是，则继续DFS；否则，回溯。
· 通过这种方式，我们可以快速检查任何字母的访问状态，并且在回溯时轻松地撤销状态更改。
#include <iostream>
#include <vector>
using namespace std;
int r, s, maxl;
vector<string> a;
void dfs(int x, int y, int len, int vis){
static const int fx[4] = {0, 0, 1, -1};
static const int fy[4] = {1, -1, 0, 0};
maxl = max(maxl, len);
for (int i = 0; i < 4; i++){
int tx = x + fx[i];
int ty = y + fy[i];
if (tx >= 0 && tx < r && ty >= 0 && ty < s){
int b = 1 << (a[tx][ty] - 'A'); //位运算
if (!(vis & b)){
dfs(tx, ty, len + 1, vis | b);
}
}
}
}
int main(){
cin >> r >> s;
a.resize(r);
for (int i = 0; i < r; i++){
cin >> a[i];
}
int f = 1 << (a[0][0] - 'A');
dfs(0, 0, 1, f);
cout << maxl << endl;
return 0;
}
这段代码通过位运算和DFS相结合的方式来避免重复访问字母，并且可以有效地解决超时问题。通过这种方式，我们不仅能够保证不会重复访问相同的字母，还能以更高效的方式追踪每条路径上的字母状态，从而优化整个搜索过程。
当使用位运算来跟踪已访问过的字母时，我们实际上是将一个整数的每一位用作一个标志位，来表示对应的字母是否已经被访问过。这种方法非常高效，因为它允许我们在常数时间内检查和更新访问状态。
让我们以一个简化的例子来演示这个过程。
示例
假设字母矩阵如下：
AB
CD
1
2
并且我们从左上角的A开始移动。
初始状态：
访问A，我们设置一个整数visited来跟踪访问状态。由于A是第一个字母，我们将visited的第0位设为1。如果用二进制表示，visited = 0001（这里为了简化只展示了4位，实际上需要26位来表示所有大写字母）。
移动到B：
接下来，我们尝试移动到B。B对应于visited中的第1位。我们检查这一位是否为0，发现是的（因为visited = 0001），这意味着B尚未被访问。
我们将B标记为已访问，通过将visited与0010进行OR操作（|），结果是visited = 0011。
尝试移动到C：
从B我们尝试向下移动到C。同样，C对应于visited中的第2位。检查这一位，发现是0（visited = 0011）。
标记C为已访问，通过将visited与0100进行OR操作，结果是visited = 0111。
回溯到B并尝试其他方向：
假设我们回溯到B尝试其他方向，此时visited不变，仍然为0111。
但由于A和C已经在visited中标记为已访问，我们不能再访问它们。
1213：八皇后问题
如果不知道国际象棋中的皇后怎么走的话，可以先看一下 1214：八皇后 中的介绍
这道题用回溯来做，大家可以先模拟四皇后的问题，进而推导出八皇后！
回溯：如果位置被一个皇后堵死了，那么就退回去（回溯），重新找！
#include <iostream>
#include <vector>
using namespace std;
int num = 1;
vector<vector<int> > p;
bool check(int x, int y);
void dfs(int step);
int main(){
p.resize(10, vector<int>(10));
dfs(1);
return 0;
}
bool check(int x, int y){
for (int i = 1; i <= 8; i++){
if (p[i][y]) return false;
}
for (int j = 1; j <= 8; j++){
if (p[x][j]) return false;
}
for (int i = 1; i <= 8; i++){
for (int j = 1; j <= 8; j++){
if (i - j == x - y && p[i][j]) return false;
}
}
for (int i = 1; i <= 8; i++){
for (int j = 1; j <= 8; j++){
if (i + j == x + y && p[i][j]) return false;
}
}
return true;
}
void dfs(int step){
if (step == 9){
cout << "No. " << num++ << endl;
for (int i = 1; i <= 8; i++){
for (int j = 1; j <= 8; j++){
cout << p[j][i] << " ";
}
cout << endl;
}
return;
}
for (int j = 1; j <= 8; j++){
if (check(step, j)){
p[step][j] = 1;
dfs(step + 1);
p[step][j] = 0;
}
}
}
1214：八皇后
#include <bits/stdc++.h>
using namespace std;
int dfs(int), print();
int a[9]; //a数组用来输出(记录)皇后串
bool b[9], c[17], d[17]; //标记数组
int ans, n;
int main()
{
//全部默认标记没被占领
memset(b, false, sizeof(b));
memset(c, false, sizeof(c));
memset(d, false, sizeof(d));
int k;
cin >> k;
for (int i = 1; i <= k; i++)
{
ans = 0;
cin >> n;
dfs(1); //从1开始递归
}
return 0;
}
//回溯求解函数
int dfs(int i)
{
for (int j = 1; j <= 8; j++) //搜索可以放的8个位置
{
if (b[j] == false && c[i + j] == false && d[i - j + 7] == false)
{
a[i] = j; //记录列
b[j] = true; //占领过的列记录为真
c[i + j] = true;
d[i - j + 7] = true; //占领两个对角线(d数组)
if (i == 8)
{
print(); //如果满足条件，直接输出
}
else
{
dfs(i + 1); //否则递归
}
b[j] = false; //回溯法，收回上一个放出过的皇后
c[i + j] = false;
d[i - j + 7] = false;
}
}
return 0;
}
//打印函数
int print()
{
ans++;
if (ans == n)
{
for (int i = 1; i <= 8; i++)
{
cout << a[i]; //输出皇后串
}
cout << endl;
}
return 0;
}
1215：迷宫
注意：auto之类的要求编译器是C++11哦！
#include <iostream>
#include <vector>
using namespace std;
bool dfs(vector<string>& maze, vector<vector<bool>>& visited, int ha, int la, int hb, int lb) {
int n = maze.size();
if (ha < 0 || ha >= n || la < 0 || la >= n || maze[ha][la] == '#' || visited[ha][la]) {
return false;
}
if (ha == hb && la == lb) {
return true;
}
visited[ha][la] = true;
vector<int> fx = {0, 0, 1, -1};
vector<int> fy = {1, -1, 0, 0};
for (int i = 0; i < 4; ++i) {
int new_ha = ha + fx[i];
int new_la = la + fy[i];
if (dfs(maze, visited, new_ha, new_la, hb, lb)) {
return true;
}
}
return false;
}
bool can_escape(vector<string>& maze, int ha, int la, int hb, int lb) {
int n = maze.size();
vector<vector<bool>> visited(n, vector<bool>(n, false));
return dfs(maze, visited, ha, la, hb, lb);
}
int main() {
int k;
cin >> k;
for (int t = 0; t < k; ++t) {
int n;
cin >> n;
vector<string> maze(n);
for (int i = 0; i < n; ++i) {
cin >> maze[i];
}
int ha, la, hb, lb;
cin >> ha >> la >> hb >> lb;
if (can_escape(maze, ha, la, hb, lb)) {
cout << "YES" << endl;
} else {
cout << "NO" << endl;
}
}
return 0;
}
1216：红与黑
注意：这里很多变量都是反的！我连续做了四五次才 AC！
思路：
初始化: 创建一个二维数组作为地图，用来存储每个瓷砖的颜色，同时记录地图的宽度W和高度H。
找到起始点: 遍历地图，找到标记为’@'的瓷砖，这是起始点。记录起始点的位置。
深度优先搜索:
从起始点开始，探索所有可以到达的黑色瓷砖(‘.’)。
对于当前的瓷砖，尝试向四个方向（上、下、左、右）移动。
如果下一个瓷砖是黑色的，并且之前没有访问过，那么递归地继续探索这个新瓷砖。
使用一个二维布尔数组来记录每个瓷砖是否已经被访问过，以防止重复计数或无限循环。
计数:
使用一个全局变量或者传递一个引用/指针参数来记录已经访问过的黑色瓷砖数量。
输出结果: 每完成一组数据的DFS后，输出已经访问过的黑色瓷砖数量。
#include <iostream>
#include <vector>
using namespace std;
int w, h;
vector<vector<char> > a;
vector<vector<bool> > vis;
int ***t;
int fx[4] = {0, 0, -1, 1};
int fy[4] = {-1, 1, 0, 0};
void dfs(int x, int y){
vis[y][x] = true;
***t++;
for (int i = 0; i < 4; i++){
int tx = x + fx[i];
int ty = y + fy[i];
if (tx >= 0 && tx < w && ty >= 0 && ty < h && a[ty][tx] == '.' && !vis[ty][tx]){
dfs(tx, ty);
}
}
}
int main(){
while (cin >> w >> h && (w || h)){
a.assign(h, vector<char>(w));
vis.assign(h, vector<bool>(w, false));
***t = 0;
int s1 = -1, s2 = -1;
for (int i = 0; i < h; i++){
for (int j = 0; j < w; j++){
cin >> a[i][j];
if (a[i][j] == '@'){
s1 = j;
s2 = i;
}
}
}
if (s1 != -1 && s2 != -1 && a[s2][s1] == '@'){
dfs(s1, s2);
}
cout << ***t << endl;
}
return 0;
}
1217：棋盘问题
回溯！！！
思路
1、遍历棋盘：从棋盘的第一行开始，尝试在每个允许的位置（即#表示的位置）放置一个棋子。
2、检查冲突：在放置每个棋子之前，检查当前列以及之前的行中是否已经放置了棋子，因为棋子不能放在同一行或同一列。
3、递归：对于每个允许放置棋子的位置，放置一个棋子后，递归地尝试在剩下的行中放置剩余的棋子。
4、回溯：如果当前行没有合法的位置可以放置棋子或已经放置了所有棋子，回溯到上一步，即移除当前行的棋子，尝试下一个可能的位置。
5、计数：每当成功地在棋盘上放置了k个棋子，就增加一种方案。
#include <iostream>
#include <vector>
using namespace std;
int n, k, ans;
vector<string> b;
vector<bool> vis;
void dfs(int r, int p){
if (p == k){ //判断特殊情况
ans++;
return; //结束函数
}
if (r >= n) return;
for (int i = 0; i < n; i++){
if (b[r][i] == '#' && !vis[i]){
vis[i] = true;
dfs(r + 1, p + 1);
vis[i] = false; //回溯，撤销上一步
}
}
dfs(r + 1, p);
}
int main(){
while (cin >> n >> k && n != -1 && k != -1){
b.resize(n);
for (int i = 0; i < n; i++){
cin >> b[i];
}
vis.resize(n, false);
ans = 0;
dfs(0, 0);
cout << ans << endl;
}
return 0;
}
1218：取石子游戏
我认为比较简单
大致思路：
基本逻辑：根据题目描述，我们需要判断在给定的两堆石子数量下，先手是否能够获胜。这可以通过递归地模拟取石子的过程来实现，每次递归时交换玩家的角色。
递归终止条件：如果当前状态下，一堆石子的数量是另一堆的两倍或更多，则当前操作的玩家赢。如果两堆石子中的任何一堆数量为0，则当前操作的玩家输。
搜索过程：从较多的那堆石子中取出一定数量的石子，数量是较少那堆的整数倍，然后递归地调用函数模拟下一步操作。
优化：考虑到可能存在重复状态，我们可以使用记忆化搜索来避免重复计算已经计算过的状态。
#include <iostream>
using namespace std;
bool dfs(int a, int b){
if (a < b) swap(a, b);
if (a % b == 0) return true;
if (a / b >= 2) return true;
return !dfs(a - b, b);
}
int main(){
int a, b;
while (cin >> a >> b && (a || b)){
if (dfs(a, b)) cout << "win" << endl;
else cout << "lose" << endl;
}
return 0;
}
1219：马走日
这里是解决这个问题的基本步骤：
1、初始化棋盘：创建一个n×m的棋盘，所有格子初始标记为未访问。
2、马的移动规则：确定马能移动的8个方向。在中国象棋中，马的移动可以用坐标变化来表示，例如：(2, 1), (2, -1), (-2, 1), (-2, -1), (1, 2), (1, -2), (-1, 2), (-1, -2)。
3、回溯搜索：从初始位置开始，尝试每一种可能的移动。如果移动有效（即移动后的位置在棋盘内且未被访问过），则继续从新位置递归搜索。
4、统计途径总数：每当成功访问到棋盘上的所有点时，途径总数加一。需要注意的是，每访问一个新点，就标记为已访问，回溯后需要撤销这个标记。
#include <iostream>
#include <vector>
using namespace std;
//方向数组——马可能走的8个方向
int fx[8] = {2, 2, -2, -2, 1, 1, -1, -1};
int fy[8] = {1, -1, 1, -1, 2, -2, 2, -2};
int n, m, ***t;
void dfs(vector<vector<bool> >& vis, int x, int y, int step){
if (step == n * m){ //特殊条件，所有的点都已经访问过了
***t++;
return;
}
//遍历8个方向
for (int i = 0; i < 8; i++){
int tx = x + fx[i];
int ty = y + fy[i];
if (tx >= 0 && tx < n && ty >= 0 && ty < m && !vis[tx][ty]){
vis[tx][ty] = true;
dfs(vis, tx, ty, step + 1); //递归
vis[tx][ty] = false; //回溯，撤销上一步的标记
}
}
}
int main(int argv, char* argc[]){
int t, x, y;
cin >> t;
while (t--){
cin >> n >> m >> x >> y;
vector<vector<bool> > vis;
vis.assign(n, vector<bool>(m, false));
***t = 0;
vis[x][y] = true;
dfs(vis, x, y, 1); //深搜
cout << ***t << endl;
}
return 0;
}
这段代码首先定义了一个全局变量***t来统计马遍历棋盘的途径总数。dfs函数是核心函数，它尝试所有可能的移动并递归地搜索整个棋盘。每次成功遍历整个棋盘时，***t会增加。最后，输出每组数据的途径总数。
1220：单词接龙
1221：分成互质组
1222：放苹果
