poj1166

 1 #include <iostream>
 2 using namespace std;
 3 
 4 int clock[3][3];
 5 int clo[3][3];
 6 int movel[9][3][3]={1,1,0,1,1,0,0,0,0,
 7                    1,1,1,0,0,0,0,0,0,
 8                    0,1,1,0,1,1,0,0,0,
 9                    1,0,0,1,0,0,1,0,0,
10                    0,1,0,1,1,1,0,1,0,
11                    0,0,1,0,0,1,0,0,1,
12                    0,0,0,1,1,0,1,1,0,
13                    0,0,0,0,0,0,1,1,1,
14                    0,0,0,0,1,1,0,1,1};
15 int num[10]={0};
16 int n=0;
17 int nu[10000];
18 int minn=10000;
19 int minnu[10000];
20 void zhuan(int step);
21 void zhizhen();
22 bool same();
23 int main()
24 {
25     for(int i=0;i<3;i++)
26         for(int j=0;j<3;j++)
27             cin >>clock[i][j];
28     zhuan(0);
29     for(int i=0;i<minn;i++)
30         cout <<minnu[i]<<" ";
31     return 0;
32 }
33 
34 void zhuan(int step)
35 {
36     if(step==9)
37     {
38         n=0;
39         zhizhen();
40         if(same()&&n<minn)
41         {
42             minn=n;
43             for(int i=0;i<minn;i++)
44                 minnu[i]=nu[i];
45         }
46         return;
47     }
48     for(int i=0;i<4;i++)
49     {
50         num[step]=i;
51         zhuan(step+1);
52     }
53 }
54 
55 void zhizhen()
56 {
57     for(int i=0;i<3;i++)
58     {
59         for(int j=0;j<3;j++)
60             clo[i][j]=clock[i][j];
61     }
62     for(int i=0;i<9;i++)
63     {
64         for(int m=0;m<num[i];m++)
65         {
66             nu[n]=i+1;
67             n++;
68             for(int j=0;j<3;j++)
69             {
70                 for(int k=0;k<3;k++)
71                     clo[j][k]=(clo[j][k]+movel[i][j][k])%4;    
72             }        
73         }
74     }
75 }
76 bool same()
77 {
78     bool ret=true;
79     for(int i=0;i<3;i++)
80     {
81         for(int j=0;j<3;j++)
82         {
83             if(clo[i][j]!=0)
84             {
85                 ret=false;
86             }
87         }
88     }
89     return ret;
90 }