阿毛的笔记本

修合无人见,存心有天知

dfs练习题两道

#1 n皇后问题

检查一个如下的6 x 6的跳棋棋盘,有六个棋子被放置在棋盘上,使得每行,每列,每条对角线(包括两条主对角线的所有对角线)上都至多有一个棋子。
1 2 3 4 5 6
1 O
2 O
3 O
4 O
5 O
6 O
上面的布局可以用序列2 4 6 1 3 5来描述,第i个数字表示在第i行的相应位置有一个棋子,如下:
行号 1 2 3 4 5 6
列号 2 4 6 1 3 5

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

 

特别注意: 对于更大的N(棋盘大小N x N)你的程序应当改进得更有效。不要事先计算出所有解然后只输出,这是作弊。如果你坚持作弊,那么你登陆USACO Training的帐号将被无警告删除

输入

一个数字N  (6  < =  N  < =  13)  表示棋盘是N  x  N大小的。

输出

前三行为前三个解,每个解的两个数字之间用一个空格隔开。第四行只有一个数字,表示解的总数。

样例输入

6

样例输出

2 4 6 1 3 5 3 6 2 5 1 4 4 1 5 2 6 3 4
#include &lt;bits/stdc++.h&gt;
using namespace std;
int a[100];
bool b[100],c[100],d[100];
int sum=0;
int n;
void prints()
{
if(sum&lt;3){
for(int i=1;i&lt;=n;i++)
{
cout&lt;&lt;a[i];
if(i!=n)cout&lt;&lt;" ";
}

cout&lt;&lt;endl; } sum++; } void queen(int i){ if(i&gt;n) {
prints();
return;
}
else{
for (int j=1;j&lt;=n;j++) { if((!b[j])&amp;&amp;(!c[i+j])&amp;&amp;(!d[i-j+n])) { a[i]=j; b[j]=true; c[i+j]=true; d[i+n-j]=true; queen(i+1); b[j]=false; c[i+j]=false; d[i+n-j]=false; } } } } int main() { cin&gt;&gt;n;
queen(1);
cout&lt;&lt;sum;
return 0;
}

#2 单词接龙

单词接龙是一个与我们经常玩的成语接龙相类似的游戏,现在我们已知一组单词,且给定一个开头的字母,要求出以这个字母开头的最长的“龙”(每个单词都最多在“龙”中出现两次),在两个单词相连时,其重合部分合为一部分,例如 beastastonish,如果接成一条龙则变为beastonish,另外相邻的两部分不能存在包含关系,例如at 和 atide 间不能相连。

 

输入

输入的第一行为一个单独的整数n (n \le 20)表示单词数,以下n 行每行有一个单词,输入的最后一行为一个单个字符,表示“龙”开头的字母。你可以假定以此字母开头的“龙”一定存在.

输出

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

样例输入

5
at
touch
cheat
choose
tact
a

样例输出

23

说明

(连成的“龙”为atoucheatactactouchoose)

NOIp2000提高组第三题

 

#include &lt;bits/stdc++.h&gt;
using namespace std;
string ss[20];
int use[20],length=0,n;
int canlink(string str1,string str2)
{
for(int i=1;i&lt;min(str1.length(),str2.length());i++)
{
int flag=1;
for(int j=0;j&lt;i;j++)
if(str1[str1.length()-i+j]!=str2[j])flag=0;
if(flag) return i;
}
return 0;
}
void solve(string strnow,int lengthnow)
{
length=max(length,lengthnow);
for(int i=0;i&lt;n;i++) { if(use[i]&gt;=2)continue;
int c = canlink(strnow,ss[i]);
if(c&gt;0)
{
use[i]++;
solve(ss[i],lengthnow+ss[i].length()-c);
use[i]--;
}
}
}
int main()
{
memset(use,0,sizeof(use));
cin&gt;&gt;n;
for(int i=0;i&lt;=n;i++) cin&gt;&gt;ss[i];
solve(' '+ss[n],1);
cout&lt;&lt;length;
return 0;
}