vijosP1026毒药?解药?

hash。

怎么感觉叫状态压缩bfs比较合适呢?

#include<cstdio>
#include<algorithm>
#include<cstring>
using namespace std;
const int maxn = 10 + 5;
const int maxm = 100 + 10;
const int maxg = 1024 + 10; bool st[maxn],h[maxg];
int mp[maxm][maxn];
int d[maxg][maxn];
int n,m,finish; inline int Hash(bool a[]) {
int x=1,s=0;
for(int i=1;i<=n;i++) {
s+=x*a[i];
x*=2;
}
return s;
} void bfs() {
int l=0,r=1;
finish=(1<<n)-1;
while(l<r) {
for(int i=1;i<=m;i++) {
for(int j=1;j<=n;j++) {
if(mp[i][j]==1) st[j]=1;
else if(mp[i][j]==-1) st[j]=0;
else st[j]=d[l][j];
}
int x=Hash(st);
if(x==finish) {
printf("%d\n",d[l][0]+1);
return;
}
if(!h[x]) {
h[x]=1;
d[r][0]=d[l][0]+1;
for(int j=1;j<=n;j++) d[r][j]=st[j];
r++;
}
}
l++;
}
printf("The patient will be dead.\n");
} int main() {
scanf("%d%d",&n,&m);
for(int i=1;i<=m;i++)
for(int j=1;j<=n;j++)
scanf("%d",&mp[i][j]);
bfs();
return 0;
}
上一篇:TestNG之参数化


下一篇:C# 微信开发-----微信会员卡(一)