搜索专题
POJ Best Sequence
http://poj.org/problem?id=1699
题意：给你n个字符窜，求其所能拼接的最短长度。
分析：预处理下，dp[i][j]表示j接在i后头的最短长度，然后记忆化搜索 这里注意的是 ACTT CT 这个答案是6 因为T和/0不相等 还有就是刚进入的时候，要把当前的字符窜算进去，应为pos代表的是前一个，若带入是-1的话，会超出数组。 dp[i][j]表示状态i，第j个结尾。
#include<stdio.h>
#include<algorithm>
#include<string.h>
using namespace std;
const int MN=30;
const int INF=999999;
char s[MN][MN];
int dp[MN][MN];//j接在i后头最短是多长
int f[1024][MN];
int n;
int judge(int len1,int len2,int pos1,int pos2)
{
int ans=len2,tmp,tt=0;
if(len1>len2) tt=len1-len2;
for(int i=tt; i<len1; i++)
{
tmp=len2;
if(s[pos1][i]==s[pos2][0])
{
int x=i,y=0;
while(1)
{
if(s[pos1][x++]!=s[pos2][y++]) break;
if(x==len1) return len2-y;
}
}
}
return len2;
}
void work()
{
for(int i=0; i<n; i++)
{
int len1=strlen(s[i]);
for(int j=0; j<n; j++)
{
if(i==j) continue;
int len2=strlen(s[j]);
int tmp=judge(len1,len2,i,j);
dp[i][j]=tmp;
}
}
}
int DFS(int ans,int pos)
{
if(f[ans][pos]!=-1) return f[ans][pos];
if(ans==0) return f[ans][pos]=0;
int sum=INF;
for(int i=0; i<n; i++)
{
if(ans&(1<<i))
{
ans^=(1<<i);
int tmp=DFS(ans,i)+dp[pos][i];
ans^=(1<<i);
if(sum>tmp)
{
sum=tmp;
// de[i]=pos;
}
}
}
return f[ans][pos]=sum;
}
void debug1()
{
for(int i=0; i<n; i++)
{
printf("%d: ",i);
for(int j=0; j<n; j++)
if(i!=j) printf("%d ",dp[i][j]);
puts("");
}
}
int main()
{
int i,j,T;
scanf("%d",&T);
while(T--)
{
memset(f,-1,sizeof(f));
scanf("%d",&n);
memset(dp,0,sizeof(dp));
for(i=0; i<n; i++)
{
scanf("%s",s[i]);
}
work();
// debug1();
int sum=INF;
for(i=0; i<n; i++)
{
int l=strlen(s[i]);
int tmp=(1<<n)-1;
tmp^=(1<<i);
f[(1<<n)-1][i]=l+DFS(tmp,i);
}
int tt;
for(i=0; i<n; i++)
{
if(sum>f[(1<<n)-1][i])
{
sum=f[(1<<n)-1][i];
}
}
printf("%d\n",sum);
}
return 0;
}POJ 1950 Dessert http://poj.org/problem?id=1950 题意：n个数1 2 3.......n,加入运算符使其结果为0 分析：dfs搜索，具体看代码，主要是几个数字结合的时候，前一个数要先减去，再加上结合的数。 9.10=9*100+10 而不是9*10+10 还有这里只打印前20个
#include<stdio.h>
#include<string.h>
#include<algorithm>
using namespace std;
#define LL long long
int cas;
const int MN=20;
char num[2000][100];
char tmp[MN*MN];
int n;
void DFS(int cur,LL sum,int cnt,LL pre,int flag)
{//当前第几个数，当前的和，当前字符个数，前一个数十什么，前一个符号是+还是-
if(cur==n+1)
{
if(sum==0)
{
tmp[cnt]='\0';
strcpy(num[cas++],tmp);
}
return ;
}
for(int i=0; i<3; i++)
{
if(i==0)
{
tmp[cnt]='+';
if(cur<10)
{
tmp[cnt+1]=cur+'0';
DFS(cur+1,sum+cur,cnt+2,cur,1);
}
else
{
tmp[cnt+1]=cur/10+'0';
tmp[cnt+2]=cur%10+'0';
DFS(cur+1,sum+cur,cnt+3,cur,1);
}
}
else if(i==1)
{
tmp[cnt]='-';
if(cur<10)
{
tmp[cnt+1]=cur+'0';
DFS(cur+1,sum-cur,cnt+2,cur,2);
}
else
{
tmp[cnt+1]=cur/10+'0';
tmp[cnt+2]=cur%10+'0';
DFS(cur+1,sum-cur,cnt+3,cur,2);
}
}
else
{
tmp[cnt]='.';
if(cur<10)
{
tmp[cnt+1]=cur+'0';
if(flag==1) DFS(cur+1,sum-pre+pre*10+cur,cnt+2,pre*10+cur,flag);
else DFS(cur+1,sum+pre-pre*10-cur,cnt+2,pre*10+cur,flag);
}
else
{
tmp[cnt+1]=cur/10+'0';
tmp[cnt+2]=cur%10+'0';
if(flag==1) DFS(cur+1,sum-pre+pre*100+cur,cnt+3,pre*100+cur,flag);
else DFS(cur+1,sum+pre-pre*100-cur,cnt+3,pre*100+cur,flag);
}
}
}
}
int main()
{
int i,j;
while(scanf("%d",&n)!=EOF)
{
cas=0;
tmp[0]='1';
DFS(2,1,1,1,1);
for(i=0; i<min(cas,20); i++)
{
printf("%c",num[i][0]);
for(j=1; num[i][j]; j++)
if(num[i][j-1]>='0' && num[i][j-1]<='9' && num[i][j]>='0' && num[i][j]<='9') printf("%c",num[i][j]);
else printf(" %c",num[i][j]);
puts("");
}
printf("%d\n",cas);
}
return 0;
}POJ 1111 Image Perimeters http://poj.org/problem?id=1111 题意：读题很久很久。。。还是没懂 求一个中心X，所能涉及的最远区域所构成的图形周长（八个方向），这里周长所围的是一个矩形。 分析：dfs~~~
#include<stdio.h>
#include<string.h>
const int MN=50;
int row[]={-1,1,0,0,-1,-1,1,1};
int col[]={0,0,-1,1,-1,1,-1,1};
char num[MN][MN];
bool vis[MN][MN];
int n,m;
int sum;
void DFS(int x,int y)
{
vis[x][y]=1;
for(int i=0;i<8;i++)
{
int xx=x+row[i];
int yy=y+col[i];
if((xx==0 || yy==0 || xx>n || yy>m))
{//刚开始i<4在外面这括号，这样对于下面那组数据过不去
//因为(3,2)这个点是X,从(1,1)斜着过去，无法continue，导致sum多加了
if(i<4) sum++;
continue;
}
if(num[xx][yy]!='X' && i<4) sum++;
else if(num[xx][yy]=='X' && vis[xx][yy]==0)
{
DFS(xx,yy);
}
}
}
int main()
{
int x,y;
while(scanf("%d%d%d%d",&n,&m,&x,&y))
{
if(n+m+x+y==0) break;
memset(vis,0,sizeof(vis));
//memset(num,0,sizeof(num);/////////
for(int i=1;i<=n;i++)
{
scanf("%s",num[i]+1);
}
sum=0;
DFS(x,y);
printf("%d\n",sum);
}
return 0;
}
/*
3 3 1 2
.X.
X.X
.X.
2 2 2 2
XX
XX
*/POJ 1416 Shredding Company http://poj.org/problem?id=1416 题意：给你两个数，将第二个数重新组合其结果最接近第一个数的结果是多少，其组合方式是所有位进行相加或合并
#include<stdio.h>
#include<string.h>
const int MN=100;
char s[MN];
char str[MN];
char tmp[MN];
int n;
int ans;
int len;
int flag;
void DFS(int cur,int sum,int pre,int cnt)
{
if(cur==len)
{
if(sum<=n)
{
if(sum>ans)
{
flag=1;
ans=sum;
tmp[cnt]='\0';
strcpy(str,tmp);
}
else if(sum==ans)
{
flag=2;
}
}
return ;
}
for(int i=0;i<=1;i++)
{
if(i==0)
{
tmp[cnt]=' ';
tmp[cnt+1]=s[cur];
DFS(cur+1,sum+s[cur]-'0',s[cur]-'0',cnt+2);
}
else
{
tmp[cnt]=s[cur];
DFS(cur+1,sum-pre+pre*10+(s[cur]-'0'),pre*10+(s[cur]-'0'),cnt+1);
}
}
}
int main()
{
int i,j;
while(scanf("%d%s",&n,s))
{
if(n==0 && strcmp(s,"0")==0) break;
flag=0;
ans=-1;
len=strlen(s);
ans=0;
tmp[0]=s[0];
DFS(1,s[0]-'0',s[0]-'0',1);
if(flag==0) printf("error\n");
else if(flag==2) printf("rejected\n");
else
{
printf("%d",ans);
printf(" %s",str);
printf("\n");
}
}
return 0;
}POJ 3187 Backward Digit Sums http://poj.org/problem?id=3187 题意：
3 1 2 4
4 3 6
7 9
16 输入和结果，以及个数的长度，输出第一行的数分析：搜索+杨辉三角。 由杨辉三角性质可知当，每个数相加的次数就是c[i][j]，所以枚举的时候直接当前值j*c[n][cur]
#include<stdio.h>
#include<string.h>
int num[100];
int ans[100];
int vis[100];
int x[20][20];
int flag;
int n,m;
void DFS(int cur,int sum)
{
if(flag==1) return ;
if(cur==n+1)
{
if(sum==m)
{
flag=1;
memcpy(ans+1,num+1,sizeof(int)*n);
return;
}
return ;
}
for(int j=1; j<=n; j++)
{
if(flag==1) return ;
if(vis[j]==0)
{
vis[j]=1;
num[cur]=j;
if(cur==1 || cur==n)
DFS(cur+1,sum+j);
else DFS(cur+1,sum+j*x[n][cur]);
vis[j]=0;
}
}
}
void init()
{
for(int i=1; i<=10; i++)
{
x[i][1]=x[i][i]=1;
for(int j=1; j<=i-1; j++)
{
x[i][j]=x[i-1][j-1]+x[i-1][j];
}
}
//printf("%d",x[10][1]);
}
int main()
{
int i,j;
init();
while(scanf("%d%d",&n,&m)!=EOF)
{
memset(vis,0,sizeof(vis));
flag=0;
DFS(1,0);
printf("%d",ans[1]);
for(i=2; i<=n; i++)
printf(" %d",ans[i]);
printf("\n");
}
return 0;
}POJ 1154 LETTERS http://poj.org/problem?id=1154
#include<stdio.h>
#include<string.h>
const int MN=100;
const int INF=0x7fffffff;
int vis[MN][MN];
char str[MN][MN];
int flag[200];
int row[]= {-1,1,0,0};
int col[]= {0,0,-1,1};
int ans;
int n,m;
void DFS(int x,int y,int sum)
{
if(sum>ans) ans=sum;
vis[x][y]=1;
flag[str[x][y]]=1;
for(int i=0; i<4; i++)
{
int xx=row[i]+x;
int yy=col[i]+y;
if(xx>=1 && yy>=1 && xx<=n && yy<=m && vis[xx][yy]==0 && flag[str[xx][yy]]==0)
{
DFS(xx,yy,sum+1);
}
}
vis[x][y]=0;
flag[str[x][y]]=0;
}
int main()
{
int i,j;
while(scanf("%d%d",&n,&m)!=EOF)
{
memset(str,0,sizeof(str));
memset(flag,0,sizeof(flag));
memset(vis,0,sizeof(vis));
for(i=1; i<=n; i++)
{
scanf("%s",str[i]+1);
}
ans=0;
DFS(1,1,1);
printf("%d\n",ans);
}
return 0;
}POJ 1979 Red and Black http://poj.org/problem?id=1979
#include<stdio.h>
#include<string.h>
const int MN=100;
const int INF=0x7fffffff;
int vis[MN][MN];
char str[MN][MN];
int row[]= {-1,1,0,0};
int col[]= {0,0,-1,1};
int ans;
int n,m;
struct Node
{
int x,y;
} s;
int DFS(int x,int y)
{
int sum=0;
vis[x][y]=1;
for(int i=0; i<4; i++)
{
int xx=x+row[i];
int yy=y+col[i];
if(xx>=1 && xx<=n && yy>=1 && yy<=m && vis[xx][yy]==0 && str[xx][yy]=='.')
{
sum+=DFS(xx,yy)+1;
}
}
return sum;
}
int main()
{
int i,j;
while(scanf("%d%d",&m,&n)!=EOF)
{
if(n==0 && m==0) break;
memset(str,0,sizeof(str));
memset(vis,0,sizeof(vis));
for(i=1; i<=n; i++)
{
scanf("%s",str[i]+1);
for(j=1; j<=m; j++)
{
if(str[i][j]=='@')
{
s.x=i;
s.y=j;
}
}
}
ans=DFS(s.x,s.y)+1;
printf("%d\n",ans);
}
return 0;
}POJ 2157 Maze http://poj.org/problem?id=2157 题意：判断S能否到G，其中可能包含A~E的门，而打开该门需要找出图中相应的所有打开该门的钥匙 分析：多次dfs，当有新门能打开的话，就重新dfs
#include<stdio.h>
#include<string.h>
const int MN=110;
int vis[MN][MN];
char str[MN][MN];
int n,m;
int A,B,C,D,E;
int row[]= {-1,1,0,0};
int col[]= {0,0,-1,1};
int num1[200];
int num2[200];
int flag;
struct Node
{
int x,y;
} s,e;
void DFS(int x,int y)
{
vis[x][y]=1;
if(x==e.x && y==e.y)
{
flag=1;
return ;
}
for(int i=0; i<4; i++)
{
int xx=x+row[i];
int yy=y+col[i];
if(xx>=1 && xx<=n && yy>=1 && yy<=m && str[xx][yy]!='X' && vis[xx][yy]==0)
{
if(str[xx][yy]>='A' && str[xx][yy]<='E') continue;
DFS(xx,yy);
num2[str[xx][yy]]++;
}
}
}
void work(int i,int j)
{
if(str[i][j]=='S')
{
s.x=i;
s.y=j;
}
else if(str[i][j]=='G')
{
e.x=i;
e.y=j;
}
num1[str[i][j]]++;
}
void judge(char c)
{
for(int i=1; i<=n; i++)
{
for(int j=1; j<=m; j++)
{
if(str[i][j]==c || str[i][j]==c-'a'+'A')
str[i][j]='.';
}
}
}
int main()
{
int i,j;
char c;
while(scanf("%d%d",&n,&m))
{
if(n==0 && m==0) break;
flag=0;
memset(num1,0,sizeof(num1));
memset(num2,0,sizeof(num2));
memset(vis,0,sizeof(vis));
for(i=1; i<=n; i++)
{
scanf("%s",str[i]+1);
for(j=1; j<=m; j++)
{
work(i,j);
}
}
int sor=1;
while(sor!=0)
{
memset(num2,0,sizeof(num2));
memset(vis,0,sizeof(vis));
sor=0;
DFS(s.x,s.y);
for(c='a'; c<='e'; c++)
{
if(num2[c]==num1[c] && num2[c]!=0)
{
sor=1;
judge(c);
}
}
if(flag) break;
}
if(flag) printf("YES\n");
else printf("NO\n");
}
return 0;
}POJ 2245 http://poj.org/problem?id=2245 题意：按升序输出序列的中所有的六个数 分析：背包思想，放于不放，不要循环，直接判断该cur下，其值要不要储存，循环了的话会重复
#include<stdio.h>
#include<string.h>
#include<algorithm>
using namespace std;
const int MN=30;
int num[MN];
int tmp[MN];
int n;
bool cmp(int a,int b)
{
return a<b;
}
void DFS(int cur,int cnt)
{
int i;
if(cnt==6)
{
printf("%d",tmp[0]);
for(i=1; i<6; i++)
printf(" %d",tmp[i]);
puts("");
return ;
}
if(cur==n) return ;
tmp[cnt]=num[cur];
DFS(cur+1,cnt+1);
DFS(cur+1,cnt);
}
int main()
{
int i,j;
int flag=0;
scanf("%d",&n);
while(1)
{
if(n==0) break;
for(i=0; i<n; i++)
scanf("%d",&num[i]);
int t=num[n-1];
sort(num,num+n,cmp);
DFS(0,0);
scanf("%d",&n);
if(n==0) break;
else printf("\n");
}
return 0;
}POJ 2248
http://poj.org/problem?id=2248
题意：输出长度最短的一组数，该组中的每一个数必须由其前面的两个数相加得到 分析：DFS+剪枝
#include<stdio.h>
#include<string.h>
const int MN=110;
const int INF=0x7fffffff;
int num[MN];
int tmp[MN];
int n;
int ans;
void DFS(int cur,int MAX)
{
if(cur>ans || cur>9) return ;//剪枝
if(tmp[cur]==n)
{
if(cur<ans)
{
ans=cur;
memcpy(num,tmp,sizeof(int)*(cur+1));
}
return ;
}
for(int j=cur; j>=0; j--)//从大到小搜
{
int t=tmp[j]+tmp[cur];
if(t<=n && t>MAX)//限制条件
{
tmp[cur+1]=t;
DFS(cur+1,t);
}
}
}
int main()
{
while(scanf("%d",&n) && n)
{
tmp[0]=1;
ans=INF;
DFS(0,1);
if(ans>100) printf("%d",n);
printf("%d",num[0]);
for(int i=1; i<=ans; i++)
printf(" %d",num[i]);
puts("");
}
return 0;
}POJ 2436 Disease Management http://poj.org/problem?id=2436 题意：n头牛，d种病毒，每头牛携带的病毒种类数量不同，问限制在k种病毒的情况下最多可以有几只牛 分析：dfs+位运算 将病毒选取方式赋为一种状态，将每头牛携带的病毒也赋为一种状态，枚举病毒的选取情况 然后筛选牛，当牛的状态和病毒状态相融合，将牛筛选出来。
#include<stdio.h>
#include<string.h>
const int MN=40000;
int num[1100];
int n,d,k;
int res;
int work1(int pos)
{
int cas=0;
for(int i=0; i<n; i++)
{
if(((num[i]&pos)==0))
{
cas++;
}
}
return cas;
}
void DFS(int cur,int ans,int cnt)
{
if(cnt==k)
{
int cas=work1(ans);
if(res<cas) res=cas;
return ;
}
if(cur==d) return ;
ans^=(1<<cur);
DFS(cur+1,ans,cnt+1);
DFS(cur+1,ans^(1<<cur),cnt);
}
int main()
{
while(scanf("%d%d%d",&n,&d,&k)!=EOF)
{
for(int i=0; i<n; i++)
{
int t;
scanf("%d",&t);
int xx=0;
for(int j=0; j<t; j++)
{
int a;
scanf("%d",&a);
xx=xx^(1<<(a-1));
num[i]=xx;
}
}
res=0;
DFS(0,(1<<d)-1,0);
printf("%d\n",res);
}
return 0;
}若要回溯的话，需要记录回溯的东西的时候，记录的数组应该是局部的，全局的话会在下一个状态的时候把上一个状态的数据给覆盖了
#include<stdio.h>
#include<string.h>
const int MN=400000;
int dp[MN];
int num[1100];
int vis[1100];
int n,d,k;
int res;
int work1(int pos,int rem[])
{
int cas=0;
for(int i=0; i<n; i++)
{
if(vis[i]==0 && ((num[i]&pos)==0))
{
vis[i]=1;
rem[cas++]=i;
}
}
return cas;
}
void work2(int cas,int rem[])
{
for(int i=0; i<cas; i++)
{
vis[rem[i]]=0;
}
}
void DFS(int cur,int ans,int cnt,int sum)
{
if(cnt==k)
{
if(res<sum) res=sum;
return ;
}
int rem[1100];
int MAX=0;
if(cur==d) return ;
ans^=(1<<cur);
int cas=work1(ans,rem);
DFS(cur+1,ans,cnt+1,sum+cas);
if(MAX<sum) MAX=sum;
work2(cas,rem);
DFS(cur+1,ans^(1<<cur),cnt,sum);
}
int main()
{
while(scanf("%d%d%d",&n,&d,&k)!=EOF)
{
memset(dp,-1,sizeof(dp));
memset(vis,0,sizeof(vis));
for(int i=0; i<n; i++)
{
int t;
scanf("%d",&t);
int xx=0;
for(int j=0; j<t; j++)
{
int a;
scanf("%d",&a);
xx=xx^(1<<(a-1));
num[i]=xx;
}
}
res=0;
DFS(0,(1<<d)-1,0,0);
printf("%d\n",res);
}
return 0;
}POJ 1077 Eight
http://poj.org/problem?id=1077
题意：九宫格，问最少通过多少次移动能将，九个数字的位置按照顺序排列好 分析：BFS+康托展示 单向BFS POJ超时，双向BFS速度很快，通过这道题学到了康托这个标记方式，就9个数转换成1个数字形成状态（该排列是所有排列种的第几位） 单向BFS（stl超时，用数组模拟队列），front队头=1，rear队尾=2，插入的时候rear++，结束的时候front++，判断while（front<rear）
#include<stdio.h>
#include<string.h>
#include<string>
#include<iostream>
#include<queue>
using namespace std;
int row[]={-1,1,0,0};
int col[]={0,0,-1,1};
int fac[20];
int vis[1000000];
char index[]="udlr";
int e[10],aim;
char path[1000000];
int pre[1000000];
struct Node
{
int s[10];
int pos;
int x,y;//坐标
int status;//记录康托展开状态
}first,Q[1000000];
int Cantor(int *s)
{
int sum=0;
for(int i=0;i<9;i++)
{
int cnt=0;
for(int j=i+1;j<9;j++)
{
if(s[i]>s[j]) cnt++;//继续比i位的数字小的个数
}
sum+=(cnt*fac[9-i-1]);
}
return sum;//返回该顺序是9个数的第多少位
}
void Print(int cur)
{
if(pre[cur]==-1) return ;
Print(pre[cur]);
printf("%c",path[cur]);
}
void BFS()
{
int front=1,rear=2;
pre[first.status]=-1;
vis[first.status]=1;
Q[front]=first;
while(front<rear)
{
Node t1=Q[front];
if(t1.status==aim)
{
Print(t1.status);
return;
}
Node t2;
for(int i=0;i<4;i++)
{
t2=t1;
t2.x=t1.x+row[i];
t2.y=t1.y+col[i];
if(t2.x>=0 && t2.x<3 && t2.y>=0 && t2.y<3)
{
t2.pos=t2.x*3+t2.y;
t2.s[t1.pos]=t2.s[t2.pos];
t2.s[t2.pos]=0;
t2.status=Cantor(t2.s);
if(!vis[t2.status])
{
vis[t2.status]=1;
path[t2.status]=index[i];
pre[t2.status]=t1.status;
Q[rear]=t2;
rear++;
}
}
}
front++;
}
printf("unsolvable\n");
}
void init()
{
fac[0]=1;
for(int i=1;i<=9;i++)
{
fac[i]=fac[i-1]*i;
}
for(int i=1;i<=8;i++) e[i-1]=i;
e[8]=0;
aim=Cantor(e);
}
int main()
{
char s[110];
int i,j;
init();//求阶乘
while(gets(s+1)!=NULL)
{
s[0]=' ';
int x,y;
x=y=0;
int cas=0;
for(i=0;s[i];i++)
{
if(s[i]==' ' && s[i+1]!=' ')
{
char ch;
sscanf(&s[i+1],"%c",&ch);
if(ch=='x')
{
first.pos=cas;
first.x=cas/3;
first.y=cas%3;
first.s[cas++]=0;
}
else first.s[cas++]=ch-'0';
y++;
if(y==3) x++,y=0;
}
}
first.status=Cantor(first.s);
memset(vis,0,sizeof(vis));
BFS();
puts("");
}
return 0;
}双向BFS，速度很快，这里出现的问题是 当结束点在起点或终点的时候，由于pre=-1，所以我定义两个数组，pre1代表起点的，pre2终点的
#include<stdio.h>
#include<string.h>
#include<queue>
using namespace std;
const int MN=1000000;
int pre1[MN],pre2[MN],vis[MN];
char path1[MN],path2[MN];
int row[]= {-1,1,0,0};
int col[]= {0,0,-1,1};
char index1[]="udlr";
char index2[]="durl";
int fac[10];
struct Node
{
int s[10];
int pos;
int status;
} first,aim;
queue<Node>Q1,Q2;
int Cantor(int *s)
{
int sum=0;
for(int i=0; i<9; i++)
{
int cnt=0;
for(int j=i+1; j<9; j++)
{
if(s[i]>s[j]) cnt++;
}
sum+=(cnt*fac[9-i-1]);
}
return sum+1;
}
void init()
{
fac[0]=1;
for(int i=1; i<9; i++) fac[i]=fac[i-1]*i;
for(int i=0;i<8;i++) aim.s[i]=i+1;
aim.s[8]=0;
aim.status=Cantor(aim.s);
aim.pos=8;
}
void Print1(int Status)
{
if(pre1[Status]==-1) return ;
Print1(pre1[Status]);
printf("%c",path1[Status]);
}
void Print2(int Status)
{
if(pre2[Status]==-1) return ;
printf("%c",path2[Status]);
Print2(pre2[Status]);
}
void solve(int Status)
{
Print1(Status);
Print2(Status);
}
void BFS()
{
int x,y;
while(!Q1.empty()) Q1.pop();
while(!Q2.empty()) Q2.pop();
pre1[first.status]=pre2[aim.status]=-1;
vis[first.status]=1;
vis[aim.status]=2;
Q1.push(first);
Q2.push(aim);
if(first.status==aim.status)
{
printf("\n");
return ;
}
while(!Q1.empty() && !Q2.empty())
{
Node ts1=Q1.front(),ts2;
Node te1=Q2.front(),te2;
Q1.pop();Q2.pop();
for(int i=0; i<4; i++)
{
ts2=ts1;
x=ts1.pos/3+row[i];
y=ts1.pos%3+col[i];
if(x>=0 && x<3 && y>=0 && y<3)
{
ts2.pos=x*3+y;
ts2.s[ts1.pos]=ts2.s[ts2.pos];
ts2.s[ts2.pos]=0;
ts2.status=Cantor(ts2.s);
if(!vis[ts2.status])
{
vis[ts2.status]=1;
path1[ts2.status]=index1[i];
pre1[ts2.status]=ts1.status;
Q1.push(ts2);
}
else if(vis[ts2.status]==2)
{
path1[ts2.status]=index1[i];
pre1[ts2.status]=ts1.status;
if(ts2.status==aim.status) Print1(ts2.status);
else solve(ts2.status);
return ;
}
}
te2=te1;
x=te1.pos/3+row[i];
y=te1.pos%3+col[i];
if(x>=0 && x<3 && y>=0 && y<3)
{
te2.pos=x*3+y;
te2.s[te1.pos]=te2.s[te2.pos];
te2.s[te2.pos]=0;
te2.status=Cantor(te2.s);
if(!vis[te2.status])
{
vis[te2.status]=2;
path2[te2.status]=index2[i];
pre2[te2.status]=te1.status;
Q2.push(te2);
}
else if(vis[te2.status]==1)
{
path2[te2.status]=index2[i];
pre2[te2.status]=te1.status;
if(te2.status==first.status)Print2(te2.status);
else solve(te2.status);
return ;
}
}
}
}
printf("unsolvable");
}
int main()
{
int i,j;
init();
char s[30];
while(gets(s+1)!=NULL)
{
s[0]=' ';
int cas=0;
for(i=0; s[i]; i++)
{
if(s[i]==' ' && s[i+1]!=' ')
{
if(s[i+1]!='x') sscanf(&s[i+1],"%d",&first.s[cas++]);
else
{
first.pos=cas;
first.s[cas++]=0;
}
}
}
first.status=Cantor(first.s);
BFS();
puts("");
}
return 0;
}HDU 1043 这个要从后向前搜，将所有状态都遍历出来，然后再判断vis【status】是否存在来输出
#include<stdio.h>
#include<string.h>
#include<string>
#include<iostream>
#include<queue>
using namespace std;
int row[]= {-1,1,0,0};
int col[]= {0,0,-1,1};
int fac[20];
bool vis[1000000];
char index[]="durl";
int e[10];
char path[1000000];
int pre[1000000];
struct Node
{
int s[10];
int pos;
int x,y;//坐标
int status;//记录康托展开状态
} first,aim;
queue<Node>Q;
int Cantor(int *s)
{
int sum=0;
for(int i=0; i<9; i++)
{
int cnt=0;
for(int j=i+1; j<9; j++)
{
if(s[i]>s[j]) cnt++;//继续比i位的数字小的个数
}
sum+=(cnt*fac[9-i-1]);
}
return sum;//返回该顺序是9个数的第多少位
}
void Print(int cur)
{
if(pre[cur]==-1) return ;
printf("%c",path[cur]);
Print(pre[cur]);
}
void BFS()
{
while(!Q.empty()) Q.pop();
aim.x=2;
aim.y=2;
aim.pos=8;
pre[aim.status]=-1;
Q.push(aim);
vis[aim.status]=1;
while(!Q.empty())
{
Node t1=Q.front();
Q.pop();
Node t2;
for(int i=0; i<4; i++)
{
t2=t1;
t2.x=t1.x+row[i];
t2.y=t1.y+col[i];
if(t2.x>=0 && t2.x<3 && t2.y>=0 && t2.y<3)
{
t2.pos=t2.x*3+t2.y;
t2.s[t1.pos]=t2.s[t2.pos];
t2.s[t2.pos]=0;
t2.status=Cantor(t2.s);
if(!vis[t2.status])
{
vis[t2.status]=1;
path[t2.status]=index[i];
pre[t2.status]=t1.status;
Q.push(t2);
}
}
}
}
}
void init()
{
fac[0]=1;
for(int i=1; i<=9; i++)
{
fac[i]=fac[i-1]*i;
// printf("%d ",fac[i]);
}
for(int i=1; i<=8; i++) aim.s[i-1]=i;
aim.s[8]=0;
aim.status=Cantor(aim.s);
//printf("%d ",aim);
}
int main()
{
char s[110];
int i,j;
init();//求阶乘
BFS();
while(gets(s+1)!=NULL)
{
s[0]=' ';
int x,y;
x=y=0;
int cas=0;
for(i=0; s[i]; i++)
{
if(s[i]==' ' && s[i+1]!=' ')
{
char ch;
sscanf(&s[i+1],"%c",&ch);
if(ch=='x')
{
first.pos=cas;
first.x=cas/3;
first.y=cas%3;
first.s[cas++]=0;
}
else first.s[cas++]=ch-'0';
y++;
if(y==3) x++,y=0;
}
}
first.status=Cantor(first.s);
if(vis[first.status])
{
Print(first.status);
puts("");
}
else printf("unsolvable\n");
}
return 0;
}POJ 1186 方程的解数 http://poj.org/problem?id=1186 分析：求解的个数，由于未知数x只有6个，所以将他对半，让左半部分等于又半部分，dfs1搜索左半部分取得值得个数，dfs2搜索又半部分 由于其值很大，又需要记录其状态，所以用hash来搞定，取余法
#include<stdio.h>
#include<string.h>
const int MN=4000000;
int k[10],p[10];
bool vis[MN];
int hash[MN];
int num[MN];
int M,n;
int Mid;
int ans;
int locate(int s)
{
int pos;
if(s<0) pos=(-s)%MN;
else pos=s%MN;
while(vis[pos] && hash[pos]!=s)
if(++pos>=MN) pos-=MN;
return pos;
}
void DFS_left(int cur,int sum)
{
if(cur==Mid)
{
int pos=locate(sum);
num[pos]++;
vis[pos]=1;
hash[pos]=sum;
return ;
}
for(int i=1; i<=M; i++)
{
int tmp=k[cur];
for(int j=0; j<p[cur]; j++)
{
tmp*=i;
}
DFS_left(cur+1,sum+tmp);
}
}
void DFS_right(int cur,int sum)
{
if(cur==n)
{
sum=-sum;
int pos=locate(sum);
if(hash[pos]==sum)
ans+=num[pos];
return ;
}
for(int i=1; i<=M; i++)
{
int tmp=k[cur];
for(int j=0; j<p[cur]; j++)
{
tmp*=i;
}
DFS_right(cur+1,sum+tmp);
}
}
int main()
{
int i;
while(scanf("%d",&n)!=EOF)
{
scanf("%d",&M);
for(i=0; i<n; i++)
{
scanf("%d%d",&k[i],&p[i]);
}
Mid=n/2;
ans=0;
memset(num,0,sizeof(num));
memset(vis,0,sizeof(vis));
memset(hash,-1,sizeof(hash));
DFS_left(0,0);
DFS_right(Mid,0);
printf("%d\n",ans);
}
return 0;
}本文参与 腾讯云自媒体分享计划，分享自作者个人站点/博客。
原始发表：2013-10-07 ，如有侵权请联系 cloudcommunity@tencent.com 删除
评论
登录后参与评论
推荐阅读