目录

回溯法简介

回溯法模板

例题

蓝桥 oj 1508 N皇后

题目描述

输入描述

输出描述

输入输出样例

示例 1

解

---

回溯法简介

回溯法一般是DFS（深度优先搜索）实现，DFS是一种遍历或搜索图、树或图像等数据结构的算法，当然这个图、树未必要存储下来（隐式处理就是回溯法），常见的是通过某种关系构造出来的搜索树，搜索树一般是排列型搜索树（总结点个数一般为n!级别）和子集型搜索树（总节点个数一般为2^n级别）

排列型就是每次枚举选哪个，子集型就是对于每一个元素选或不选（结果与顺序无关）。

DFS从起始节点开始，沿着一条路径尽可能深入的搜索（一条路走到黑），直到无法继续为止，然后回溯到前一个节点，继续探索其他路径，直到遍历完整个图或树。

DFS使用栈或递归来管理节点的遍历顺序，一般使用递归。

很多时候DFS和回溯法不必过度区分。

回溯法模板

//求1~n的全排列
int a[N];
bool vis[N];void dfs(int dep)//dep表示深度
{if (dep == n + 1)//说明前面的n层都已经算完了 直接输出结果{for (int i = 1; i <= n; i++)cout << a[i] << ' ';cout << endl;return;}for (int i = 1; i <= n; ++i){//排除不合法的路径if (vis[i])continue;//表示数字i是否使用过//修改状态vis[i] = true;a[dep] = i;//下一层dfs(dep + 1);//恢复路径vis[i] = false;//恢复了现场才能往下一个方式递归}
}

例题

蓝桥 oj 1508 N皇后

题目描述

在 N×N 的方格棋盘放置了 N 个皇后，使得它们不相互攻击（即任意 2 个皇后不允许处在同一排，同一列，也不允许处在与棋盘边框成 45 角的斜线上。你的任务是，对于给定的 N，求出有多少种合法的放置方法。

输入描述

输入中有一个正整数 N≤10，表示棋盘和皇后的数量

输出描述

为一个正整数，表示对应输入行的皇后的不同放置数量。

输入输出样例

示例 1

输入

5

输出

10

解

#include<iostream>
using namespace std;const int N = 15;int n,ans = 0;int vis[N][N];//表示被多少个皇后占用了void dfs(int dep)
{if (dep == n + 1){ans++;return;}for (int i = 1; i <= n; i++){if (vis[dep][i])continue;//表示当前位置已经被占用了//修改状态for (int _i = 1; _i <= n; _i++)vis[_i][i]++;//dep行和第i列占用掉for (int _i = dep, _j = i; _i >= 1 && _j >= 1; _i--, _j--)vis[_i][_j]++;//斜线 左上for (int _i = dep, _j = i; _i <= n && _j >= 1; _i++, _j--)vis[_i][_j]++;//斜线 左下for (int _i = dep, _j = i; _i <= n && _j <= n; _i++, _j++)vis[_i][_j]++;//斜线 右下for (int _i = dep, _j = i; _i >= 1 && _j <= n; _i--, _j++)vis[_i][_j]++;//斜线 右下dfs(dep + 1);//恢复现场for (int _i = 1; _i <= n; _i++)vis[_i][i]--;//dep行和第i列占用掉for (int _i = dep, _j = i; _i >= 1 && _j >= 1; _i--, _j--)vis[_i][_j]--;//斜线 左上for (int _i = dep, _j = i; _i <= n && _j >= 1; _i++, _j--)vis[_i][_j]--;//斜线 左下for (int _i = dep, _j = i; _i <= n && _j <= n; _i++, _j++)vis[_i][_j]--;// 右下for (int _i = dep, _j = i; _i >= 1 && _j <= n; _i--, _j++)vis[_i][_j]--;//斜线 右下}}int main()
{cin >> n;dfs(1);cout << ans << endl;return 0;
}