http://acm.hdu.edu.cn/showproblem.php?pid=2269很好的運用了位運算。。。三進制狀態壓縮。。
#include<stdio.h>
#include<string>
char hash[177148]={0};
char thing[11][21];
int n;
struct Q{
short int tep,b,c;
}q[177148];
int head,tail,empty,K=1;
int ku[] = {1,3,9,27,81,243,729,2187,6561,19683,59049};
int ku2[] = {1,2,4,8,16,32,64,128,256,512,1024};
bool eat[2048];
bool flag;
int maxt,a,b,c;
int find(char a[]) {
int i;
for(i=0;i<n;i++)
if(strcmp(a,thing[i])==0)
return i;
return -1;
}
void GetEat()
{
char buf[11],str[999];
int i,j,a,num=0;
j = 0;
gets(str);
for(i=0;str[i];i++)
{
if(str[i]==' ')
{
buf[j] = 0;
j = 0;
a = find(buf);
if(a>=0)
num += ku2[a];
}
else
buf[j++] = str[i];
}
buf[j] = 0;
a = find(buf);
if(a>=0)
num += ku2[a];
int max = (1<<n)-1;
for(i=num;i<=max;i++)
if((i&num)==num)
eat[i] = true;
}
bool _hash(int b,int c)
{
int i;
int sum = 0;
for(i=0;i<n && (b||c);i++)
{
sum += (b&1)*ku[i] + (c&1)*ku[i]*2;
b >>= 1;
c >>= 1;
}
if(hash[sum]!=K) {
hash[sum] = K;
return true;
}
return false;
}
void dfs(int start,int maxt,int &x)
{
if(maxt<0)
return ;
if(!eat[x] && _hash(b,c))
{
tail ++;
q[tail].b = b;
q[tail].c = c;
q[tail].tep = q[head].tep + 1;
}
if(maxt==0)
return ;
for(int i=start;i<n;i++)
{
int k = 1<<i;
if((x&k)==k)
{
x -= k;
b += k;
if(c==0)
flag = true;
dfs(i+1,maxt-1,x);
if(flag)
return ;
b -= k;
x += k;
}
}
}
int bfs()
{
head = tail = 0;
q[head].b = 0;
q[head].c = (1<<n) - 1;
q[head].tep = 0;
flag = false;
while(head <= tail)
{
a = (1<<n) - 1;
b = q[head].b;
c = q[head].c;
a ^= (b|c);
if(q[head].tep&1) {
a = a|b;
b = 0;
dfs(0,maxt,a);
}
else {
c = c|b;
b = 0;
dfs(0,maxt,c);
}
if(flag)
return q[head].tep + 1;
head ++;
}
return -1;
}
int main()
{
int m,i;
while(scanf("%d%d%d",&n,&m,&maxt)==3)
{
for(i=0;i<n;i++)
scanf("%s",thing[i]);
getchar();
memset(eat,false,sizeof(eat));
for(i=0;i<m;i++)
GetEat();
if(maxt>=n) {
puts("1");
continue;
}
printf("%d\n",bfs());
K ++;
}
return 0;
}
posted on 2009-03-22 10:05
shǎ崽 閱讀(302)
評論(0) 編輯 收藏 引用