Part 3.1 深度优先搜索

深度优先搜索（DFS），即按照深度优先的顺序搜索的算法。

深度优先搜索一般使用栈来实现。

[USACO1.5] 八皇后 Checker Challenge

题目描述

一个如下的 $6\times 6$ 的跳棋棋盘，有六个棋子被放置在棋盘上，使得每行、每列有且只有一个，每条对角线（包括两条主对角线的所有平行线）上至多有一个棋子。

上面的布局可以用序列 $246135$ 来描述，第 $i$ 个数字表示在第 $i$ 行的相应位置有一个棋子，如下：

行号 $123456$

列号 $246135$

这只是棋子放置的一个解。请编一个程序找出所有棋子放置的解。
并把它们以上面的序列方法输出，解按字典顺序排列。
请输出前 $3$ 个解。最后一行是解的总个数。

输入格式

一行一个正整数 $n$，表示棋盘是 $n\times 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\%$ 的数据，$6\le n\le 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$ 行每行有一个单词，输入的最后一行为一个单个字符，表示“龙”开头的字母。你可以假定以此字母开头的“龙”一定存在。

输出格式

只需输出以此字母开头的最长的“龙”的长度。

样例 #1

样例输入 #1

5
at
touch
cheat
choose
tact
a

样例输出 #1

23

提示

样例解释：连成的“龙”为 atoucheatactactouchoose。

$n\le 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$ 位带符号整数范围内）。

每次称牛时，他都把某头奶牛安置在天平的某一边，然后往天平另一边加砝码，直到天平平衡，于是此时砝码的总质量就是牛的质量（约翰不能把砝码放到奶牛的那边，因为奶牛不喜欢称体重，每当约翰把砝码放到她的蹄子底下，她就会尝试把砝码踢到约翰脸上）。

天平能承受的物体的质量不是无限的，当天平某一边物体的质量大于 $ C \ ( 1 \leq C \leq 2^{30} ) $ 时，天平就会被损坏。砝码按照它们质量的大小被排成一行。并且，这一行中从第 $3$ 个砝码开始，每个砝码的质量至少等于前面两个砝码（也就是质量比它小的砝码中质量最大的两个）的质量的和。

约翰想知道，用他所拥有的这些砝码以及这架天平，能称出的质量最大是多少。由于天平的最大承重能力为 $C$，他不能把所有砝码都放到天平上。

现在约翰告诉你每个砝码的质量，以及天平能承受的最大质量，你的任务是选出一些砝码，使它们的质量和在不压坏天平的前提下是所有组合中最大的。

输入格式

第 $1$ 行输入两个用空格隔开的正整数 $ N $ 和 $ C $。

第 $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$ 行，每行一个八位字符串。其中第 $i$ 位如果为 -，则表示日期的第 $i$ 位无法确定，否则表示日期的第 $i$ 位为字符串中第 $i$ 位上的数字。

输出格式

对每组数据，一行一个整数，表示答案。

样例 #1

样例输入 #1

2
53-7-3-7
20190629

样例输出 #1

6
0

提示

【样例 $1$ 说明】

53-7-3-7 的 $6$ 种可能的日期如下：

53070307
53070317
53170307
53370307
53570317
53770307

【数据规模与约定】

一共 $10$ 个测试点，记 $c$ 为八位字符串中 - 的个数。

对前 $9$ 个测试点，在第 $i$ 个测试点中保证 $c=i-1$。

对 $100\%$ 的数据保证 $1\le T\le 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$ 个点上放置油滴，才能使放置完毕后所有油滴占据的总面积最大呢？（不同的油滴不会相互融合）

注：圆的面积公式 $S=\pi r^2$，其中 $r$ 为圆的半径。

输入格式

第一行，一个整数 $N$。

第二行，四个整数 $x,y,x^{\prime },y^{\prime }$，表示长方形边框一个顶点及其对角顶点的坐标。

接下来 $N$ 行，第 $i$ 行两个整数 $x_i,y_i$，表示盒子内第 $i$ 个点的坐标。

输出格式

一行，一个整数，长方形盒子剩余的最小空间（结果四舍五入输出）。

样例 #1

样例输入 #1

2
20 0 10 10
13 3
17 7

样例输出 #1

50

提示

代码实现

对于 $100\%$ 的数据，$1\le N\le 6$，坐标范围在 $[-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;
}