【BZOJ】2719 银河之星

可以将棋子分为9种类型。且可以通过合并使得两个不同种类棋子转换为另一种棋子(不过要注意棋盘大小,有的时候硬要合并会到棋盘外面,可以先把棋盘全部转换,然后枚举每一个棋子的转换)。然后把状态压成一个十位的十进制数就可以记忆化搜索了。

 #include<bits/stdc++.h>
using namespace std;
#define LL long long
#define id(i,j) ((i-1)*3+j-1);
struct point{
int a,b;
}p[];
int k,n,m,x,y,g[][],tot[],change[][];
const int dir[][]={,,,-,,,-,,,,,-,-,,-,-};
LL bg,fin,bin[];
bool flag;
map<LL,int>lis;
bool dfs(LL st){
if(lis[st]){
if(lis[st]==) return true;
return false;
}
if(st==fin) return true;
LL tmp;
for(int i=;i<;i++)
if((st%bin[i+])/bin[i]>){
for(int j=;j<;j++)
if(change[i][j]!=- && (st%bin[j+])/bin[j]>){
tmp=st,tmp=tmp-(bin[i]+bin[j])+bin[change[i][j]];
if(dfs(tmp)) {lis[tmp]=; return true;}
}
}
lis[st]=;
return false;
}
int main(){
bin[]=;
for(int i=;i<=;i++) bin[i]=bin[i-]*;
while(scanf("%d%d%d%d%d",&k,&n,&m,&x,&y)!=EOF){
lis.clear(); bg=; flag=;
int num=id(((x-)%+),((y-)%+));
fin=bin[num];
memset(tot,,sizeof(tot));
memset(change,-,sizeof(change));
for(int a,b,i=;i<=k;i++) {
scanf("%d%d",&a,&b);
p[i]=(point){a,b};
int num=id(((a-)%+),((b-)%+));
tot[num]++;
if(tot[num]==) puts("No"),flag=;
else bg+=bin[num];
}
if(flag) continue;
for(int i=;i<n;i++)
for(int j=;j<m;j++)
g[i+][j+]=id((i%+),(j%+));
for(int i=;i<=n;i++)
for(int j=;j<=m;j++)
for(int d=;d<;d++){
int ta=i+*dir[d][],tb=j+*dir[d][];
if(ta< || ta>n || tb< || tb>m) continue;
change[g[ta-dir[d][]][tb-dir[d][]]][g[i][j]]=change[g[i][j]][g[ta-dir[d][]][tb-dir[d][]]]=g[ta][tb];
}
if(dfs(bg)) puts("Yes");
else puts("No");
}
return ;
}
上一篇:SublimeText3搭建go语言开发环境(windows)


下一篇:MySQL 性能优化的最佳20多条经验分享(二)(转)