首页 > 代码库 > The Clocks

The Clocks

The Clocks

题目链接:http://poj.org/problem?id=1166

题意:给出9个时钟的初始状态,问最少通过几次操作,能使每个时钟指向12点(每次操作都会使对应时钟顺时针旋转90度)

暴搜

考虑到每种操作最多进行3次(如果进行4次就和不进行操作一样),直接用49的暴搜

代码如下:

 1 #include <cstdio>
 2 #include <vector>
 3 #include <cstring>
 4 #define pb(x) push_back(x)
 5 #define mk(x,y) make_pair(x,y)
 6 #define f(x) (x-‘A‘)
 7 using namespace std;
 8 typedef pair<int,int> P;
 9 int a[9],ans[9],s[9],Min;
10 vector<int>p[9];
11 void check(){
12     int sum=0,b[9];
13     for(int i=0;i<9;++i)b[i]=a[i];
14     for(int i=0;i<9;++i){
15         sum+=s[i];
16         for(int j=0;j<(int)p[i].size();++j){
17             int t=p[i][j];
18             b[t]=(b[t]+s[i])%4;
19         }
20     }
21     for(int i=0;i<9;++i)
22         if(b[i])return;
23     if(sum<Min){
24         Min=sum;
25         for(int i=0;i<9;++i)ans[i]=s[i];
26     }
27 }
28 void dfs(int op){
29     if(op>=9){
30         check();
31         return;
32     }
33     for(int i=0;i<4;++i){
34         s[op]=i;
35         dfs(op+1);
36     }
37 }
38 int main(void){
39     p[0].pb(f(A)),p[0].pb(f(B)),p[0].pb(f(D)),p[0].pb(f(E));
40     p[1].pb(f(A)),p[1].pb(f(B)),p[1].pb(f(C));
41     p[2].pb(f(B)),p[2].pb(f(C)),p[2].pb(f(E)),p[2].pb(f(F));
42     p[3].pb(f(A)),p[3].pb(f(D)),p[3].pb(f(G));
43     p[4].pb(f(B)),p[4].pb(f(D)),p[4].pb(f(E)),p[4].pb(f(F)),p[4].pb(f(H));
44     p[5].pb(f(C)),p[5].pb(f(F)),p[5].pb(f(I));
45     p[6].pb(f(D)),p[6].pb(f(E)),p[6].pb(f(G)),p[6].pb(f(H));
46     p[7].pb(f(G)),p[7].pb(f(H)),p[7].pb(f(I));
47     p[8].pb(f(E)),p[8].pb(f(F)),p[8].pb(f(H)),p[8].pb(f(I));
48     Min=100000000;
49     for(int i=0;i<9;++i)scanf("%d",&a[i]);
50     dfs(0);
51     for(int i=0;i<9;++i)
52         for(int j=0;j<ans[i];++j)
53             printf("%d ",i+1);
54 }

 

The Clocks