首页 > 代码库 > 银河之星(galaxy)
银河之星(galaxy)
当时没来的及做,应该是一道不是太难的搜索题。
首先,可以想到可行解的数量一定远远少于不可行解的数量;
与其我们直接搜索,倒不如我们根据(x,y)构造可行解,然后判断。
代码实现:
1 #include<map> 2 #include<cstdio> 3 #include<cstring> 4 using namespace std; 5 typedef long long LL; 6 const int dx[8] = {0,1,0,-1,1,-1,1,-1}; 7 const int dy[8] = {1,0,-1,0,1,-1,-1,1}; 8 const int ch[9][9] = {{0,2,1,6,8,7,3,5,4},{2,1,0,8,7,6,5,4,3},{1,0,2,7,6,8,4,3,5}, 9 {6,8,7,3,5,4,0,2,1},{8,7,6,5,4,3,2,1,0},{7,6,8,4,3,5,1,0,2}, 10 {3,5,4,0,2,1,6,8,7},{5,4,3,2,1,0,8,7,6},{4,3,5,1,0,2,7,6,8}}; 11 map <LL,int> ma; 12 int n,m,k,X,Y,p[10][10],x[10],y[10]; 13 LL now,goal,fac[10],che[10]; 14 inline int ABS(int x) {return x < 0?-x:x;} 15 void Add(int X1,int Y1,int X2,int Y2){ 16 int A=3*(X1%3)+Y1%3; 17 int B=3*(X2%3)+Y2%3; 18 p[A][B]=p[B][A]=1; 19 } 20 void Work(int a,int b){ 21 for (int l=0;l<8;l++){ 22 int xa=a+dx[l]*3; 23 int yb=b+dy[l]*3; 24 if(xa<1||xa>n||yb<1||yb>m) continue; 25 for(int i=0;i<8;i++){ 26 int xx=xa+dx[i]; 27 int yy=yb+dy[i]; 28 if(xx<1||xx>n||yy<1||yy>m) continue; 29 Add(a,b,xx,yy); 30 } 31 } 32 for (int i=0;i<8;i++){ 33 int xx=a+dx[i],yy=b+dy[i]; 34 if(xx<1||xx>n||yy<1||yy>m) continue; 35 Add(a,b,xx,yy); 36 } 37 } 38 bool dfs(LL now,int tot){ 39 if (now == goal) return 1; 40 if (ma[now]) return 0; 41 else ma[now] = 1; 42 if (tot == 1) return 0; 43 for (int i = 0; i < 9; i++) 44 for (int j = i + 1; j < 9; j++) 45 if (p[i][j] && che[i] && che[j]) { 46 --che[i]; --che[j]; ++che[ch[i][j]]; 47 LL nex = 0; 48 for (int l = 0; l < 9; l++) nex += fac[l]*che[l]; 49 if (dfs(nex,tot-1)) return 1; 50 ++che[i]; ++che[j]; --che[ch[i][j]]; 51 } 52 return 0; 53 } 54 int main(){ 55 #ifdef YZY 56 freopen("galaxy4.in","r",stdin); 57 #endif 58 fac[0] = 1; 59 for (int i = 1; i < 10; i++) fac[i] = fac[i-1]*11LL; 60 while (scanf("%d%d%d%d%d",&k,&n,&m,&X,&Y) != EOF) { 61 memset(p,0,sizeof(p)); memset(che,0,sizeof(che)); ma.clear(); 62 goal = fac[3*(X%3) + Y%3]; 63 for (int i = 0; i < k; i++) { 64 scanf("%d%d",&x[i],&y[i]); 65 ++che[3*(x[i]%3) + y[i]%3]; 66 } 67 for (int i = 1; i <= n; i++) 68 for (int j = 1; j <= m; j++) 69 Work(i,j); 70 LL st = 0; 71 for (int i = 0; i < 9; i++) st += che[i]*fac[i]; 72 if (dfs(st,k)) printf("Yes\n"); 73 else printf("No\n"); 74 } 75 return 0; 76 }
题目来源:Pku 3490
银河之星(galaxy)
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。