Amaok | 阿毛的笔记本

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行的相应位置有一个棋子，如下：

[cc]行号 1 2 3 4 5 6[/cc]

[cc]列号 2 4 6 1 3 5[/cc]

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

 

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

输入

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

输出

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

样例输入

[cc]6[/cc]

样例输出

[cc]2 4 6 1 3 5 3 6 2 5 1 4 4 1 5 2 6 3 4[/cc]

[cc]
#include <bits/stdc++.h>
using namespace std;
int a[100];
bool b[100],c[100],d[100];
int sum=0;
int n;
void prints()
{
if(sum<3){
for(int i=1;i<=n;i++)
{
cout<<a[i];
if(i!=n)cout<<” “;
}

cout<<endl; } sum++; } void queen(int i){ if(i>n) {
prints();
return;
}
else{
for (int j=1;j<=n;j++) { if((!b[j])&&(!c[i+j])&&(!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>>n;
queen(1);
cout<<sum;
return 0;
}
[/cc]

#2 单词接龙

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

 

输入

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

输出

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

样例输入

[cc]5
at
touch
cheat
choose
tact
a[/cc]

样例输出

[cc]23[/cc]

说明

（连成的“龙”为atoucheatactactouchoose）

NOIp2000提高组第三题

 

[cc]

#include <bits/stdc++.h>
using namespace std;
string ss[20];
int use[20],length=0,n;
int canlink(string str1,string str2)
{
for(int i=1;i<min(str1.length(),str2.length());i++)
{
int flag=1;
for(int j=0;j<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<n;i++) { if(use[i]>=2)continue;
int c = canlink(strnow,ss[i]);
if(c>0)
{
use[i]++;
solve(ss[i],lengthnow+ss[i].length()-c);
use[i]–;
}
}
}
int main()
{
memset(use,0,sizeof(use));
cin>>n;
for(int i=0;i<=n;i++) cin>>ss[i];
solve(‘ ‘+ss[n],1);
cout<<length;
return 0;
}
[/cc]

Amaok