深度优先搜索（DFS），即按照深度优先的顺序搜索的算法。
深度优先搜索一般使用栈来实现。
[USACO1.5] 八皇后 Checker Challenge
题目描述
一个如下的 6 × 6 6 \times 6 6×6 的跳棋棋盘，有六个棋子被放置在棋盘上，使得每行、每列有且只有一个，每条对角线（包括两条主对角线的所有平行线）上至多有一个棋子。
上面的布局可以用序列 2 4 6 1 3 5 2\ 4\ 6\ 1\ 3\ 5 2 4 6 1 3 5 来描述，第 i i i 个数字表示在第 i i i 行的相应位置有一个棋子，如下：
行号 1 2 3 4 5 6 1\ 2\ 3\ 4\ 5\ 6 1 2 3 4 5 6
列号 2 4 6 1 3 5 2\ 4\ 6\ 1\ 3\ 5 2 4 6 1 3 5
这只是棋子放置的一个解。请编一个程序找出所有棋子放置的解。
并把它们以上面的序列方法输出，解按字典顺序排列。
请输出前
3
3
3 个解。最后一行是解的总个数。
输入格式
一行一个正整数 n n n，表示棋盘是 n × n n \times n n×n 大小的。
输出格式
前三行为前三个解，每个解的两个数字之间用一个空格隔开。第四行只有一个数字，表示解的总数。
样例 #1
样例输入 #1
6
样例输出 #1
2 4 6 1 3 5
3 6 2 5 1 4
4 1 5 2 6 3
4
提示
【数据范围】
对于
100
%
100\%
100% 的数据，
6
≤
n
≤
13
6 \le n \le 13
6≤n≤13。
题目翻译来自NOCOW。
USACO Training Section 1.5
代码实现
#include<iostream>
using namespace std;
#define MAX_N 13
int ans[MAX_N+5];
int vis_col[MAX_N+5]={0},vis_dui1[MAX_N*2+5]={0},vis_dui2[MAX_N*2+5];
int n,cnt=0;
void dfs(int row)
{
if(row==n+1)
{
cnt++;
if(cnt<=3)
{
for(int i=1;i<=n;i++)
{
if(i!=1)cout<<" ";
cout<<ans[i];
}
cout<<endl;
}
return ;
}
for(int i=1;i<=n;i++)
{
if(vis_col[i])continue;
if(vis_dui1[i-row+n])continue;
if(vis_dui2[i+row-1])continue;
vis_col[i]=1;
vis_dui1[i-row+n]=1;
vis_dui2[i+row-1]=1;
ans[row]=i;
dfs(row+1);
vis_col[i]=0;
vis_dui1[i-row+n]=0;
vis_dui2[i+row-1]=0;
}
}
int main()
{
cin>>n;
dfs(1);
cout<<cnt;
return 0;
}
[NOIP2000 提高组] 单词接龙
题目背景
注意：本题为上古 NOIP 原题，不保证存在靠谱的做法能通过该数据范围下的所有数据。
本题为搜索题，本题不接受 hack 数据。关于此类题目的详细内容
NOIP2000 提高组 T3
题目描述
单词接龙是一个与我们经常玩的成语接龙相类似的游戏，现在我们已知一组单词，且给定一个开头的字母，要求出以这个字母开头的最长的“龙”（每个单词都最多在“龙”中出现两次），在两个单词相连时，其重合部分合为一部分，例如 beast 和 astonish，如果接成一条龙则变为 beastonish，另外相邻的两部分不能存在包含关系，例如 at 和 atide 间不能相连。
输入格式
输入的第一行为一个单独的整数 n n n 表示单词数，以下 n n n 行每行有一个单词，输入的最后一行为一个单个字符，表示“龙”开头的字母。你可以假定以此字母开头的“龙”一定存在。
输出格式
只需输出以此字母开头的最长的“龙”的长度。
样例 #1
样例输入 #1
5
at
touch
cheat
choose
tact
a
样例输出 #1
23
提示
样例解释：连成的“龙”为 atoucheatactactouchoose。
n ≤ 20 n \le 20 n≤20。
代码实现
#include<iostream>
#include<vector>
using namespace std;
#define MAX_N 20
string arr[MAX_N+5];
int to[MAX_N+5][MAX_N+5];
int cnt[MAX_N+5]={0};
vector<int>start;
int n;
int final_ans=0;
void dfs(int k,int ans)
{
final_ans=max(final_ans,ans);
for(int i=1;i<=n;i++)
{
if(to[k][i]&&cnt[i]!=2)
{
cnt[i]++;
dfs(i,ans+arr[i].size()-to[k][i]);
cnt[i]--;
}
}
return ;
}
int main()
{
cin>>n;
char st;
for(int i=1;i<=n;i++)cin>>arr[i];
cin>>st;
for(int i=1;i<=n;i++)
{
if(arr[i][0]==st)start.push_back(i);
for(int j=1;j<=n;j++)
{
int max_len=min(arr[i].size(),arr[j].size());
for(int len=1;len<=max_len;len++)
{
int j_pos=len-1;
int flag=1;
int sz=arr[i].size();
for(int k=sz-1;k>=(sz-len);k--)
{
if(arr[i][k]==arr[j][j_pos--])continue;
flag=0;
break;
}
if(flag)
{
if(len==max_len)break;
to[i][j]=len;
break;
}
}
}
}
for(auto fir:start)
{
cnt[fir]+=1;
dfs(fir,arr[fir].size());
cnt[fir]-=1;
}
cout<<final_ans;
return 0;
}
[USACO05DEC] Scales S
题目描述
约翰有一架用来称牛的体重的天平。与之配套的是 $ N \ ( 1 \leq N \leq 1000 ) $ 个已知质量的砝码（所有砝码质量的数值都在 32 32 32 位带符号整数范围内）。
每次称牛时，他都把某头奶牛安置在天平的某一边，然后往天平另一边加砝码，直到天平平衡，于是此时砝码的总质量就是牛的质量（约翰不能把砝码放到奶牛的那边，因为奶牛不喜欢称体重，每当约翰把砝码放到她的蹄子底下，她就会尝试把砝码踢到约翰脸上）。
天平能承受的物体的质量不是无限的，当天平某一边物体的质量大于 $ C \ ( 1 \leq C \leq 2^{30} ) $ 时，天平就会被损坏。砝码按照它们质量的大小被排成一行。并且，这一行中从第 3 3 3 个砝码开始，每个砝码的质量至少等于前面两个砝码（也就是质量比它小的砝码中质量最大的两个）的质量的和。
约翰想知道，用他所拥有的这些砝码以及这架天平，能称出的质量最大是多少。由于天平的最大承重能力为 C C C，他不能把所有砝码都放到天平上。
现在约翰告诉你每个砝码的质量，以及天平能承受的最大质量，你的任务是选出一些砝码，使它们的质量和在不压坏天平的前提下是所有组合中最大的。
输入格式
第 1 1 1 行输入两个用空格隔开的正整数 $ N $ 和 $ C $。
第 2 2 2 到 $ N+1 $ 行：每一行仅包含一个正整数，即某个砝码的质量。保证这些砝码的质量是一个不下降序列。
输出格式
输出一个正整数，表示用所给的砝码能称出的不压坏天平的最大质量。
样例 #1
样例输入 #1
3 15
1
10
20
样例输出 #1
11
代码实现
#include<iostream>
#include<algorithm>
using namespace std;
#define MAX_N 1000
int fama[MAX_N+5];
int final_ans=0;
int n,c;
bool cmp(int a,int b)
{
return a>b;
}
void dfs(int i,int ans)
{
if(i==n)
{
final_ans=max(final_ans,ans);
return ;
}
if(ans+fama[i+1]<=c)dfs(i+1,ans+fama[i+1]);
if(ans+fama[i+1]+fama[i+2]>c)
dfs(i+1,ans);
return ;
}
int main()
{
cin>>n>>c;
for(int i=1;i<=n;i++)cin>>fama[i];
sort(fama+1,fama+1+n,cmp);
dfs(0,0);
cout<<final_ans;
return 0;
}
【XR-2】奇迹
题目背景
相信奇迹的人，本身就和奇迹一样了不起。——笛亚 《星游记》
题目描述
我们称一个日期为一个八位数，第 1~4 位构成年，第 5~6 位构成月，第 7~8 位构成日，不足位数用 0 补足。同时，要求日期所代表的这一天真实存在，且年的范围为 1~9999。
出现奇迹的日期都存在相同的特点：由“日”组成的两位数，由“月+日”组成的四位数，由“年+月+日”组成的八位数均为质数。但并不是所有存在这样特点的日期都一定会出现奇迹。
现在，你得到了一个可能会出现奇迹的日期，然而不幸的是这个日期却是残缺的，八位中可能有若干位无法确定。你需要知道这个日期有多少种可能，这样你才能做好充足的准备去迎接奇迹的到来。
输入格式
本题有多组数据。
第一行一个正整数 T T T，表示数据组数。
接下来的
T
T
T 行，每行一个八位字符串。其中第
i
i
i 位如果为 -，则表示日期的第
i
i
i 位无法确定，否则表示日期的第
i
i
i 位为字符串中第
i
i
i 位上的数字。
输出格式
对每组数据，一行一个整数，表示答案。
样例 #1
样例输入 #1
2
53-7-3-7
20190629
样例输出 #1
6
0
提示
【样例 1 1 1 说明】
53-7-3-7 的
6
6
6 种可能的日期如下：
53070307
53070317
53170307
53370307
53570317
53770307
【数据规模与约定】
一共
10
10
10 个测试点，记
c
c
c 为八位字符串中 - 的个数。
对前 9 9 9 个测试点，在第 i i i 个测试点中保证 c = i − 1 c = i - 1 c=i−1。
对 100 % 100\% 100% 的数据保证 1 ≤ T ≤ 10 1 \le T \le 10 1≤T≤10。
代码实现
#include<iostream>
#include<math.h>
using namespace std;
#define MAXSIZE 10000005
int prim[10005],zhishu[10005],vis[10005],runnian[10005];
int m_to_d[13]={0,31,28,31,30,31,30,31,31,30,31,30,31};
int ans=0;
int cnt=0;
int s[9];
void Init()
{
for(int i=2;i<=10005;i++)
{
if(!vis[i])
{
prim[++cnt]=i;
zhishu[i]=1;
vis[i]=1;
}
for(int j=1;j<=cnt;j++)
{
if(i*prim[j]>10005)break;
vis[prim[j]*i]=1;
if(i%prim[j]==0)break;
}
}
for(int i=1;i<=9999;i++)
{
if(i%4==0)
if(i%100!=0)runnian[i]=1;
else if(i%400==0)runnian[i]=1;
}
return ;
}
bool pdzs(int x)
{
if(x < 2) return 0;
for(int i= 1; i <= cnt; i++)
if(x % prim[i] == 0) return x == prim[i];
return 1;
}
void dfs(int pos,int num,int rn,int dy)
{
if(pos==0)
{
if(num<=1231)return ;
if(rn==1&&!runnian[num/10000])return ;
if(pdzs(num))ans++;
return ;
}
if(pos==4)
{
if(num<31||num>1231)return ;
if(dy==1&&m_to_d[num/100]!=31)return ;
if(!pdzs(num))return ;
if(num%100==29&&num/100==2)rn=1;
}
if(pos==6)
{
if(num==0||num>31)return ;
if(!pdzs(num)) return ;
if(num==31)dy=1;
}
if(s[pos]==-1)for(int i=0;i<=9;i++)dfs(pos-1,num+i*pow(10,8-pos),rn,dy);
else dfs(pos-1,num+s[pos]*pow(10,8-pos),rn,dy);
}
int main()
{
int t;
cin>>t;
Init();
while(t--)
{
ans=0;
char c;
for(int i=1;i<=8;i++)
{
cin>>c;
s[i]=(c=='-'?-1:c-'0');
}
dfs(8,0,0,0);
cout<<ans<<endl;
}
return 0;
}
油滴扩展
题目描述
在一个长方形框子里，最多有 N N N 个相异的点，在其中任何一个点上放一个很小的油滴，那么这个油滴会一直扩展，直到接触到其他油滴或者框子的边界。必须等一个油滴扩展完毕才能放置下一个油滴。那么应该按照怎样的顺序在这 N N N 个点上放置油滴，才能使放置完毕后所有油滴占据的总面积最大呢？（不同的油滴不会相互融合）
注：圆的面积公式 S = π r 2 S = \pi r^2 S=πr2，其中 r r r 为圆的半径。
输入格式
第一行，一个整数 N N N。
第二行，四个整数 x , y , x ′ , y ′ x, y, x', y' x,y,x′,y′，表示长方形边框一个顶点及其对角顶点的坐标。
接下来 N N N 行，第 i i i 行两个整数 x i , y i x_i, y_i xi,yi，表示盒子内第 i i i 个点的坐标。
输出格式
一行，一个整数，长方形盒子剩余的最小空间（结果四舍五入输出）。
样例 #1
样例输入 #1
2
20 0 10 10
13 3
17 7
样例输出 #1
50
提示
代码实现
对于 100 % 100\% 100% 的数据， 1 ≤ N ≤ 6 1 \le N \le 6 1≤N≤6，坐标范围在 [ − 1000 , 1000 ] [-1000, 1000] [−1000,1000] 内。
#include<iostream>
#include<math.h>
using namespace std;
#define PI 3.1415926535
double x[10],y[10],r[10];
double xa,xb,ya,yb;
double s;
double yd=0;
int vis[10],w[10];
int n;
double dis(int a,int b)
{
return sqrt(pow(x[a]-x[b],2)+pow(y[a]-y[b],2));
}
void dfs(int id,double num)
{
if(id==n+1)
{
yd=max(yd,num);
return ;
}
for(int i=1;i<=n;i++)
{
if(vis[i])continue;
vis[i]=1;
w[id]=i;
r[id]=1000000;
r[id]=min(r[id],fabs(xa-x[i]));
r[id]=min(r[id],fabs(xb-x[i]));
r[id]=min(r[id],fabs(ya-y[i]));
r[id]=min(r[id],fabs(yb-y[i]));
for(int j=1;j<id;j++)
{
double dd=dis(w[id],w[j]);
if(dd<=r[j])
{
r[id]=0;
break;
}
r[id]=min(r[id],dd-r[j]);
}
dfs(id+1,num+PI*r[id]*r[id]);
vis[i]=0;
}
return ;
}
int main()
{
cin>>n;
cin>>xa>>ya>>xb>>yb;
s=fabs(xa-xb)*fabs(ya-yb);
for(int i=1;i<=n;i++)r[i]=1000000;
for(int i=1;i<=n;i++)cin>>x[i]>>y[i];
dfs(1,0);
s-=yd;
printf("%.0lf",s);//自带四舍五入
return 0;
}