搜索常设的状态：
1：当前这一层a[i
2：如果要求递增递减等要求（与上一层的状态有关），还应设置a[i-1],即上一层的状态，以确保递增等要求
3：根据题目进行设计，如讲一个数分解，可设n - (a[1] + a[2] + ...... +a[i])以表示后面所有正整数的和
例题：
把正整数n分解为3 个不同的正整数，如 6 = 1 + 2 + 3，排在后面的数必须大于等于前面的数，输出所有方案。
该类搜索算法的特点在于，将要搜索的目标分成若干“层”，每层基于前几层的状态进行决策，直到达到目标状态。
考虑上述问题，即将正整数n分解成小于等于m个正整数之和，且排在后面的数必须大于等于前面的数，并输出所有方案。
设一组方案将正整数n 分解成 k 个正整数a[1], a[2], ...... a[k] 的和。
我们将问题分层，第i层决定a[i].则为了进行第 i 层决策，我们需要记录三个状态变量：
1 n - (a[1] + a[2] + ...... +a[i])表示后面所有正整数的和；
2 以及a[i-1]表示前一层的正整数，以确保正整数递增；
3 以及 i ,确保我们最多输出m个正整数。
`
int m, arr[103]; // arr 用于记录方案
void dfs(int n, int i, int a) {
if (n == 0) {
for (int j = 1; j <= i - 1; ++j) printf("%d ", arr[j]);
printf("\n");
}
if (i <= m) {
for (int j = a; j <= n; ++j) {
arr[i] = j;
dfs(n - j, i + 1, j); // 请仔细思考该行含义。
}
}
}
// 主函数
scanf("%d%d", &n, &m);
dfs(n, 1, 1);`
红与黑
#include<iostream>
using namespace std;
int dx[] = {0,0,-1,1}, dy[] = {1,-1,0,0};
int w,h;
char g[30][30];
int cnt = 0;
void dfs(int x,int y){
g[x][y] = '#';
cnt++;
for(int i = 0; i < 4; i++){
int a = x + dx[i], b = y + dy[i];
if(a <= 0 || a > h|| b <= 0||b >w ||g[a][b] == '#') continue;
dfs(a,b);
}
}
int main(){
ios::sync_with_stdio(false);
cin.tie(0),cout.tie(0);
bool flag;
while(cin >> w >> h,w||h){
cnt = 0;
flag = 0;
int x, y;
for(int i = 1;i <= h;i++)
for(int j = 1;j <= w;j++)
cin>>g[i][j];
for(int i = 1; i <= h;i++){
for(int j = 1;j <= w;j++){
if(g[i][j] == '@'){
x = i, y = j;
flag = 1;
}
}
if(flag) break;
}
dfs(x,y);
cout<<cnt<<endl;
}
return 0;
}
分成互质组
给定 n 个正整数，将它们分组，使得每组中任意两个数互质。至少要分成多少个组？
输入格式：
第一行是一个正整数 n。
第二行是 n 个不大于10000的正整数。
输出格式：
一个正整数，即最少需要的组数。
数据范围：
1≤n≤10
输入样例：
6
14 20 33 117 143 175
输出样例：
3
1.开始DFS：首先是递归终止条件，判断是否搜到末尾，搜到末尾则更新组数计数的值，返回；
2.继续：每次在已有分组中从头开始搜索，用检索函数判断当前数字是否可以加入分组，若可以，加入后递归向下一个数字搜索
3.新建分组：考虑组数为0的情况、找不到可以加入组的情况，应该设置创建新分组的情况，加入新分组后，同样递归向后搜索。
`
#include<iostream>
#include<algorithm>
using namespace std;
typedef long long LL;
const int N = 20;
int n;
int a[N];
int cnt = 99999;
LL vis[N];
LL gcd(LL a,LL b) {
if(b == 0) return a;
return gcd(b,a % b);
}
void dfs(int k,int step) { //step表示层数
if(step == n+1) { //递归终止条件，判断是否搜到末尾，搜到末尾则更新组数计数的值，返回
if(k < cnt) cnt = k;//求最小互质组
return;
}
for(int i = 1; i <= k; i++){
if(gcd(vis[i],a[step]) == 1) {
vis[i] *= a[step];
dfs(k,step + 1);
//每次在已有分组中从头开始搜索，用检索函数判断当前数字是否可以加入分组，若可以，加入后递归向下一个数字搜索
vis[i] /= a[step];//恢复现场
}
}
vis[k + 1] *= a[step];
dfs(k + 1,step + 1);
//考虑组数为0的情况、找不到可以加入组的情况，应该设置创建新分组的情况，加入新分组后，同样递归向后搜索。
vis[k + 1] /= a[step];
}
int main() {
int temp;
cin >> n;
for(int i = 1; i <= n; i++) {
cin >> a[i];
vis[i] = 1;
}
sort(a + 1,a + 1 + n);
dfs(1,1);
cout << cnt << endl;
return 0;
}`
单词接龙
题目描述:
单词接龙是一个与我们经常玩的成语接龙相类似的游戏。
现在我们已知一组单词，且给定一个开头的字母，要求出以这个字母开头的最长的“龙”，每个单词最多被使用两次。
在两个单词相连时，其重合部分合为一部分，例如 beast 和 astonish ，如果接成一条龙则变为 beastonish。
我们可以任意选择重合部分的长度，但其长度必须大于等于1，且严格小于两个串的长度，例如 at 和 atide 间不能相连。
输入格式
输入的第一行为一个单独的整数 n 表示单词数，以下 n 行每行有一个单词（只含有大写或小写字母，长度不超过20），输入的最后一行为一个单个字符，表示“龙”开头的字母。
你可以假定以此字母开头的“龙”一定存在。
输出格式
只需输出以此字母开头的最长的“龙”的长度。
输入样例：
5
at
touch
cheat
choose
tact
a
输出样例：
23
提示：连成的“龙”为 “atoucheatactactouchoose”
#include<iostream>
#include<string>
#include<cstring>
using namespace std;
int ans,maxn,lx,ly,n,vis[100001],l[100001];
int p;//p求最大单词长度，ans记录单词长度
string a[10001];
char dr;
int find(int x,int y) {
int lx=l[x];//第x个单词的长度
int ly=l[y];//第y个单词的长度
for(int i=lx-1; i>=1; i--){//字符串下标从0到其长度减1，接龙使头接尾 （倒序看前面的单词第几个字母与其相等）
if(a[x][i]==a[y][0]){ // 如果找到字母相等的
int k=0;//统计有几个相同的字母 ,同时从头往尾遍历头被接的单词
for(int j=i+1; j<=lx-1; j++) { //判断从此字母往后的每一个字母是否都相等
k++;
if(a[x][j]!=a[y][k]){
return 0;//有一个不相等就接不了龙
}
}
return ly-(k+1); //全相等返回单词长度
}
}
return 0;
}
void dfs(int x) {
for(int i=1; i<=n; i++) {
if(find(x,i)&&vis[i]<2) {
vis[i]++;
ans+=find(x,i);//统计接的单词长度
dfs(i);
vis[i]--;//回溯
ans-=find(x,i);//回溯，减去接龙重复的单词
}
}
if(p<ans) {//求最大
p=ans;
}
}
int main() {
cin>>n;
for(int i=1; i<=n; i++) {
cin>>a[i];
l[i]=a[i].length();
}
cin>>dr;
for(int i=1; i<=n; i++) {
if(a[i][0]==dr) {
vis[i]++;
ans=l[i];
dfs(i);
vis[i]--;
if(p>maxn) {
maxn=p;
}
}
}
cout<<maxn;
return 0;
}
搜索顺序：
1.每次随意挑选空白格子
2.枚举该格子选哪个数
3.dfs
直接这样写会超时，所以要优化（前两步）：
1.优化搜索顺序：每次选择可填数字最少的格子搜索
2.建立三个数组row[i],存储第i行可以选哪些数，col[i]，存储第i列可以选哪些数
cell[i][j]表示3*3九宫格内可以选哪些数。最后三个数组取交集，取交集可以用位运算（与&）
来进行。三个数组离存储的数都是0~2^9-1,所以二进制表示中有9位（每一位不是0就是1），是1的话
表示这一位可以用，是0表示不可以用。
举个例子：
加入最后执行完&运算后结果是100010101这样一个二进制的9位数，从右往左编号为(0~8)
第0位是1表示0这个数可以用，第2位是1表示2这个数可以用，第4位是1表示4这个数可用……
从中我们发现需要遍历判断哪一位是1，所以要用lowbit运算
所以对于每一个点(x,y)，执行下面操作：
row[x]&col[y]&cell[x/3]y/3,x,y下标是0~8
(0,0) (0,1) (0,2)
(1,0) (1,1) (1,2)
(2,0) (2,1) (2,2)
然后lowbit，对于每一个1，就枚举选上这个数，然后更新状态，即更新row[],col[],cell[]数组，
最后递归到下一层，如果找到方案就返回，没有找到就恢复现场（还原），进行下一步的递归
#include<iostream>
#include<algorithm>
using namespace std;
const int N = 9;
int ones[1 << N], map[1 << N];//ones[]存储二进制表示下有多少个1，map[]存储一个表：1返回0，10返回1，100返回2，1000返回3
int row[N], col[N], cell[3][3];
char str[100];
inline int lowbit(int x)//inline说白了就是加速，减少调用函数的时间，只有非递归函数才能加inline
{
return x & -x;
}
void init()
{
for (int i = 0; i < N; i ++ ) row[i] = col[i] = (1 << N) - 1;
//最开始行和列可以任意选0~8中的数，所以二进制9位里每一位都是1
for (int i = 0; i < 3; i ++ )
for (int j = 0; j < 3; j ++ )
cell[i][j] = (1 << N) - 1;
}
// 求可选方案的交集
inline int get(int x, int y)
{
return row[x] & col[y] & cell[x / 3][y / 3];
}
bool dfs(int cnt)//true表示找到答案，false表示未找到答案
{
if (!cnt) return true;//cnt==0时说明已经把所有格子都填满了
// 找出可选方案数最少的空格
int minv = 10;//最多只有9种选择
int x, y;
for (int i = 0; i < N; i ++ )
for (int j = 0; j < N; j ++ )
if (str[i * 9 + j] == '.')//str[]是一维数组
{
int t = ones[get(i, j)];//交集里有多少个1
if (t < minv)
{
minv = t;
x = i, y = j;
}
}
for (int i = get(x, y); i; i -= lowbit(i))
{
int t = map[lowbit(i)];
// 修改状态
row[x] -= 1 << t;
col[y] -= 1 << t;
cell[x / 3][y / 3] -= 1 << t;
str[x * 9 + y] = '1' + t;//将0~8变为1~9
if (dfs(cnt - 1)) return true;
// 恢复现场，其实就是修改状态的逆运算
row[x] += 1 << t;
col[y] += 1 << t;
cell[x / 3][y / 3] += 1 << t;
str[x * 9 + y] = '.';
}
return false;
}
int main()
{
for (int i = 0; i < N; i ++ ) map[1 << i] = i;
for (int i = 0; i < 1 << N; i ++ )
{
int s = 0;
for (int j = i; j; j -= lowbit(j)) s ++ ;
ones[i] = s; // i的二进制表示中有s个1
}
while (cin >> str, str[0] != 'e')
{
init();
int cnt = 0;//记录一共有多少个要填的格子
for (int i = 0, k = 0; i < N; i ++ )//i,j枚举九宫格中的坐标，k枚举输入中那一行的线性坐标（指针）
for (int j = 0; j < N; j ++ , k ++ )
if (str[k] != '.')
{
int t = str[k] - '1';//题目是1~9.我们用的是0~8
row[i] -= 1 << t;//第i行的第t位的1变成0
col[j] -= 1 << t;//第j列的第t位的1变成0
cell[i / 3][j / 3] -= 1 << t;
}
else cnt ++ ;
dfs(cnt);//将没有填的格子填满
cout << str << endl;
}
return 0;
}
