https://www.luogu.org/problem/show?pid=1213
题目描述
考虑将如此安排在一个 3 x 3 行列中的九个时钟:
目标要找一个最小的移动顺序将所有的指针指向12点。下面原表格列出了9种不同的旋转指针的方法，每一种方法都叫一次移动。选择1到9号移动方法，将会使在表格中对应的时钟的指针顺时针旋转90度。
移动方法 受影响的时钟
1 ABDE
2 ABC
3 BCEF
4 ADG
5 BDEFH
6 CFI
7 DEGH
8 GHI
9 EFHI
Example
[但这可能不是正确的方法，请看下面]
输入输出格式
输入格式：
第1-3行: 三个空格分开的数字，每个数字表示一个时钟的初始时间，3,6,9,12。数字的含意和上面第一个例子一样。
输出格式：
单独的一行包括一个用空格分开的将所有指针指向12:00的最短移动顺序的列表。
如果有多种方案，输出那种使其连接起来数字最小的方案。(举例来说5 2 4 6 < 9 3 1 1)。
输入输出样例
输入样例#1：
9 9 12 6 6 6 6 3 6
输出样例#1：
4 5 8 9
说明
题目翻译来自NOCOW。
USACO Training Section 1.4
搜索每次移动方案的使用次数、每次用原始时钟判断一次。、
每次使用移动方法多余3时就转一圈没意义了。
1 #include <algorithm> 2 #include <cstring> 3 #include <cstdio> 4 5 int op[9][9]={{1,1,0,1,1,0,0,0,0}, 6 {1,1,1,0,0,0,0,0,0}, 7 {0,1,1,0,1,1,0,0,0}, 8 {1,0,0,1,0,0,1,0,0}, 9 {0,1,0,1,1,1,0,1,0}, 10 {0,0,1,0,0,1,0,0,1}, 11 {0,0,0,1,1,0,1,1,0}, 12 {0,0,0,0,0,0,1,1,1}, 13 {0,0,0,0,1,1,0,1,1}}; 14 int tmp[10],tim[10],cnt[10]; 15 16 inline void read(int &x) 17 { 18 x=0; register char ch=getchar(); 19 for(;ch>'9'||ch<'0';) ch=getchar(); 20 for(;ch>='0'&&ch<='9';ch=getchar()) x=x*10+ch-'0'; 21 } 22 23 bool judge(int *a) 24 { 25 for(int i=0; i<9; ++i) 26 if(a[i]) return 0; 27 return true; 28 } 29 30 void DFS(int num) 31 { 32 memcpy(&tmp,&tim,sizeof(tim)); 33 for(int i=0; i<9; ++i) 34 for(int j=0; j<9; ++j) 35 tmp[i]=(tmp[i]+op[j][i]*cnt[j])%4; 36 if(judge(tmp)) 37 { 38 for(int i=0; i<9; ++i) 39 for(int j=0; j<cnt[i]; ++j) 40 printf("%d ",i+1); 41 std::exit(0) ; 42 } 43 if(num==9) return ; 44 for(int i=0; i<4; ++i) 45 cnt[num]=i,DFS(num+1); 46 } 47 48 int Aptal() 49 { 50 for(int i=0; i<9; ++i) 51 read(tim[i]),tim[i]/=3,tim[i]%=4; 52 DFS(0); 53 return 0; 54 } 55 56 int Hope=Aptal(); 57 int main(){;}