|
??????? 这两天总算把搜索完结了，但只能说是过了一遍，让我写个题我还是写不出来（头大），打算学下一章基础算法的时候尽量每天再看看搜索题目，争取自己把题目给写出来。
poj1416
????????按样例123456分析，先对1切，对23456递归；对12切，对3456递归；对123切，对456递归。。。。难点就在如何递归。。。这也正是我不会的。。。又是看的题解，giao！
#include<iostream>
#include<cstring>
#include<algorithm>
#include<string>
#include<cstdio>
#include<map>
#include<cmath>
#include<vector>
#include<queue>
#include<list>
#include<stack>
#include<set>
#include<ctime>
#define ll long long
#define CHECK(x,y) (x>=1&&x<=n&&y>=1&&y<=m&&!a[x][y])
//#include<bits/stdc++.h>
using namespace std;
const int maxx=1005;
int aim,pt,a[10],per[10],pie,len,minn;
char sh[30];
void dfs(int k,int sum,int t){
//k是从哪里开始切，sum是和，t是一共多少段
if(sum>aim)
return;
if(k>=len){
if(sum<=aim){
if(sum==minn)
pie++;
else if(abs(aim - sum)<=abs(aim-minn)){
//这地方就得用绝对值，因为minn一开始是最大值，所以aim-minn一直是负数
//程序就不会判到这了
minn=sum;
pie=1;
pt=t;
for(int i=0;i<t;i++) per[i]=a[i];
}
}
return;
}
int pk=0;
for(int i=k;i<len;i++){//主要步骤递归，循环就是找切点的过程（1，23456；12，3456。。。。）
pk=pk*10+(sh[i]-'0');
a[t]=pk;
dfs(i+1,sum+pk,t+1);
}
}
int main(){
// freopen("in.txt","r",stdin);
while(scanf("%d%s",&aim,sh)!=EOF){
if(aim==0&&strcmp(sh,"0")==0) break;
len=strlen(sh),minn=999999,pie=0;
int num=0;
for(int i=0;i<len;i++)
num+=(sh[i]-'0');
if(num>aim){//如果最小的数都大于aim，那么一定找不到
printf("error\n");
continue;
}
num=0;
for(int i=0;i<len;i++)
num=num*10+(sh[i]-'0');
if(num==aim){//判相等
printf("%d %d\n",aim,aim);
// cout<<"yes"<<endl;
continue;
}
dfs(0,0,0);
if(pie>1) printf("rejected\n");
else{
printf("%d ",minn);
for(int i=0;i<pt;i++){
if(i==pt-1)
printf("%d\n",per[pt-1]);
else printf("%d ",per[i]);
}
}
memset(sh,'0',sizeof sh);
}
/* jieshu=clock();
cout<<endl;
cout<<(double)(jieshu-kaishi)/CLOCKS_PER_SEC<<endl;*/
return 0;
}
poj2676
????????我一开始的思路就是从第一个为零的点开始递归，但是最后写完答案一点也不对，递归写得太差了，在网上看的别人的感觉处理得非常好，还有一个难点是小方块判断的处理，方法都在代码里
#include<iostream>
#include<cstring>
#include<algorithm>
#include<string>
#include<cstdio>
#include<map>
#include<cmath>
#include<vector>
#include<queue>
#include<list>
#include<stack>
#include<set>
#include<ctime>
#define ll long long
#define CHECK(x,y) (x>=1&&x<=n&&y>=1&&y<=m&&!a[x][y])
//#include<bits/stdc++.h>
using namespace std;
const int maxx=1005;
char a[15][15];
bool flag1=0;
int zuo[15][15];//数组开的正好或很小会runtime error
void dfs(int x,int y){
// cout<<x<<" "<<y<<endl;
if(flag1) return;
if(y>9){
x++;
y=1;
if(x>9){
flag1=1;
for(int i=1;i<=9;i++){
for(int j=1;j<=9;j++)
cout<<zuo[i][j];
cout<<endl;
}
}
}
if(zuo[x][y]==0){//这样的判断方法真没有想到，真是相当的斯巴拉西了
int f[10]={0,0};
for(int i=1;i<=9;i++)
f[zuo[x][i]]++;
for(int i=1;i<=9;i++)
f[zuo[i][y]]++;
for(int i=(x-1)/3*3;i<(x-1)/3*3+3;i++)//把方格的顺序改为0-9，然后利用计算机除法的特性判断
for(int j=(y-1)/3*3;j<(y-1)/3*3+3;j++)
f[zuo[i+1][j+1]]++;
for(int i=1;i<=9;i++){
if(f[i]==0){
zuo[x][y]=i;
dfs(x,y+1);
zuo[x][y]=0;
}
}
}
else dfs(x,y+1);
return;
}
int main(){
//freopen("in.txt","r",stdin);
int t;
cin>>t;
while(t--){
int pos1,pos2;
for(int i=1;i<=9;i++){
for(int j=1;j<=9;j++){
cin>>a[i][j];
zuo[i][j]=a[i][j]-'0';
}
}
flag1=0;
dfs(1,1);
}
/* jieshu=clock();
cout<<endl;
cout<<(double)(jieshu-kaishi)/CLOCKS_PER_SEC<<endl;*/
return 0;
}
poj1126
????????感觉更像是涂色问题，这题我竟然做过，但全忘了。。。第几个字母和多少种颜色作为递归的参数，对第几个使用的字母进行递归，另外一个字母可以使用以前的颜色，也可以用一个新的颜色
#include<iostream>
#include<cstring>
#include<algorithm>
#include<string>
#include<cstdio>
#include<map>
#include<cmath>
#include<vector>
#include<queue>
#include<list>
#include<stack>
#include<set>
#include<ctime>
#define ll long long
#define CHECK(x,y) (x>=1&&x<=n&&y>=1&&y<=m&&!a[x][y])
//#include<bits/stdc++.h>
using namespace std;
const int maxx=1005;
int n,mp[30][30],color[30],flag;
char s[30];
bool pd(int a,int b){
for(int i=0;i<=n;i++)
if(mp[i][a]&&color[i]==b)//判断与该字母相邻的字母是否用过相同的颜色
return 0;
return 1;
}
void dfs(int p,int num){
if(flag) return;
if(p==n){
flag=1;
if(num-1==1)
printf("%d channel needed.\n",num-1);
if(num-1>1)
printf("%d channels needed.\n",num-1);
return;
}
for(int i=1;i<num;i++){
if(pd(p,i)){
color[p]=i;//用以前的颜色递归
dfs(p+1,num);
if(flag) return;
}
}
color[p]=num;//用新颜色进行递归
dfs(p+1,num+1);
}
int main(){
// freopen("in.txt","r",stdin);
while(cin>>n&&n){
for(int i=0;i<27;i++){
for(int j=0;j<27;j++)
mp[i][j]=0;
}
for(int i=0;i<27;i++)
color[i]=0;
flag=0;
for(int i=1;i<=n;i++){
scanf("%s",s);
int len=strlen(s);
int a=s[0]-'A',b;
for(int j=2;j<len;j++){
b=s[j]-'A';
mp[a][b]=mp[b][a]=1;//存储方式挺特别的
}
}
dfs(0,1);
}
/* jieshu=clock();
cout<<endl;
cout<<(double)(jieshu-kaishi)/CLOCKS_PER_SEC<<endl;*/
return 0;
}
poj1560
????????迭代加深搜索，从n个序列中最长的长度当作新序列的长度，不行就+1进行搜索，从第一个序列开始，若字符一致新序列就添上该字符，长度加1，依次进行
#include<iostream>
#include<cstring>
#include<algorithm>
#include<string>
#include<cstdio>
#include<iomanip>
#include<map>
#include<cmath>
#include<vector>
#include<queue>
#include<list>
#include<stack>
#include<set>
#include<ctime>
#define ll long long
#define CHECK(x,y) (x>=1&&x<=n&&y>=1&&y<=m&&!a[x][y])
//#include<bits/stdc++.h>
using namespace std;
const int maxx=1005;
int n,val[10],pos[10],dep,ans=0;//pos[i]代表第i个序列用到第几个字符了
string c="ACGT";
struct node{
string s;int len;
}a[10];
int get(){//获取单个序列最多还有几个字符没用
int ans=0;
for(int i=0;i<n;i++){
ans=max(ans,a[i].len-pos[i]);
}
return ans;
}
int ida(int cnt){
if(cnt+get()>dep) return 0;//剪枝，若步数加上剩下的字符大于长度，则返回
if(!get()) return 1;
int temp[10];
memcpy(temp,pos,sizeof pos);
for(int i=0;i<4;i++){
bool flag=0;
for(int j=0;j<n;j++){
if(a[j].s[pos[j]]==c[i]){
pos[j]++;
flag=1;
}
}
if(flag){
if(ida(cnt+1)) return 1;
memcpy(pos,temp,sizeof temp);
}
}
return 0;
}
int main(){
// freopen("in.txt","r",stdin);
int t;
scanf("%d",&t);
while(t--){
scanf("%d",&n);
dep=0;
for(int i=0;i<n;i++){
cin>>a[i].s;
a[i].len=a[i].s.size();
dep=max(dep,a[i].len);
pos[i]=0;
}
while(1){
if(ida(0)) break;
dep++;
}
printf("%d\n",dep);
}
/* jieshu=clock();
cout<<endl;
cout<<(double)(jieshu-kaishi)/CLOCKS_PER_SEC<<endl;*/
return 0;
}
poj1667
????????迭代加深搜索，这题看上去好麻烦，我都不知道该如何下手，到最后看的题解，直接打印出对锁的操作，然后进行搜索就行，对递归还是不会。。。
#include<iostream>
#include<cstring>
#include<algorithm>
#include<string>
#include<cstdio>
#include<iomanip>
#include<map>
#include<cmath>
#include<vector>
#include<queue>
#include<list>
#include<stack>
#include<set>
#include<ctime>
#define ll long long
#define CHECK(x,y) (x>=1&&x<=n&&y>=1&&y<=m&&!a[x][y])
//#include<bits/stdc++.h>
using namespace std;
const int maxx=1005;
int center[10]={6,7,8,11,12,15,16,17};//中心的八个方格
int reverseop[10]={5,4,7,6,1,0,3,2};//逆操作
int opt[8][7]={//打表操作
{0,2,6,11,15,20,22},//A
{1,3,8,12,17,21,23},//B
{10,9,8,7,6,5,4},//C
{19,18,17,16,15,14,13},//D
{23,21,17,12,8,3,1},//E
{22,20,15,11,6,2,0},//F
{13,14,15,16,17,18,19},//G
{4,5,6,7,8,9,10},//H
};
int mp[25],max1;
char ans[maxx];
bool flag;
int get(){//
int cnt=0;
int num[4]={0};
for(int i=0;i<8;i++){
num[mp[center[i]]]++;
cnt=max(cnt,num[mp[center[i]]]);
}
return 8-cnt;//返回最少步数
}
void operation(int op){//执行操作
int tmp=mp[opt[op][0]];
for(int i=0;i<6;i++){
mp[opt[op][i]]=mp[opt[op][i+1]];
}
mp[opt[op][6]]=tmp;
}
void ida(int dep,int fa){
if(flag) return;
if(get()+dep>max1) return;//剪枝
if(get()==0){
ans[dep]='\0';
printf("%s\n",ans );
printf("%d\n",mp[center[0]]);
flag=true;
return;
}
for(int i=0;i<8;i++){
if(fa!=-1&&i==reverseop[fa]) continue;
operation(i);
ans[dep]=i+'A';
ida(dep+1,i);
if(flag) return;
operation(reverseop[i]);
}
}
int main(){
// freopen("in.txt","r",stdin);
while(scanf("%d",&mp[0])&&mp[0]){
for(int i=1;i<24;i++)
scanf("%d",&mp[i]);
if(get()==0) {//如果一开始8个数字就相同
printf("No moves needed\n%d\n",mp[center[0]]);
continue;
}
flag=0;
max1=1;
while(1){
ida(0,-1);
if(flag) break;
max1++;
}
}
/* jieshu=clock();
cout<<endl;
cout<<(double)(jieshu-kaishi)/CLOCKS_PER_SEC<<endl;*/
return 0;
}
|