拨钟问题
有9个时钟，排成一个3*3的矩阵。
现在需要用最少的移动，将9个时钟的指针都拨到12点的位置。共允许有9种不同的移动。如下表所示，每个移动会将若干个时钟的指针沿顺时针方向拨动90度。
移动 影响的时钟
1 ABDE
2 ABC
3 BCEF
4 ADG
5 BDEFH
6 CFI
7 DEGH
8 GHI
9 EFHI
时间限制：1000
内存限制：65536
输入
9个整数，表示各时钟指针的起始位置，相邻两个整数之间用单个空格隔开。其中，0=12点、1=3点、2=6点、3=9点。
输出
输出一个最短的移动序列，使得9个时钟的指针都指向12点。按照移动的序号从小到大输出结果。相邻两个整数之间用单个空格隔开。
样例输入
3 3 0
2 2 2
2 1 2
样例输出
4 5 8 9
我们确定了1,2,3的情况数，那么得到一个灯A,B,C的状态，而只有移动4能够改变A，
移动5能够改变B，移动6能够改变C，那么移动4-6的次数也确定了。
同样，这时只有移动7能够改变D，移动9能够改变F，这时移动7和9的次数也确定了。
最后，时钟A,B,C,D,F都已经到达12点，E,G,H,I还没确定，只剩下移动8能够改变GHI，
所以只要检查E是否已经到达12点以及，GHI的时钟数是否相等就行了。
最后找到一个移动次数最小的情况。
#include<iostream>
#include<string.h>
using namespace std;
//我们确定了1,2,3的情况数，那么得到一个灯A,B,C的状态，而只有移动4能够改变A，
//移动5能够改变B，移动6能够改变C，那么移动4-6的次数也确定了。
//
//同样，这时只有移动7能够改变D，移动9能够改变F，这时移动7和9的次数也确定了。
//
//最后，时钟A,B,C,D,F都已经到达12点，E,G,H,I还没确定，只剩下移动8能够改变GHI，
//所以只要检查E是否已经到达12点以及，GHI的时钟数是否相等就行了。
//
//最后找到一个移动次数最小的情况。
int main()
{
int i = 0;
int j = 0;
int minArr[9] = {0};
int minSum = 99999;//最少次数
int myClock[9] = {0};//时钟初始状态
int opr[9] = {0};
int tempClock[9];//过程状态
for(i = 0; i < 9; i++) {
cin >> myClock[i];//读入状态
tempClock[i] = myClock[i];//赋值过程状态
}
for(opr[0] = 0; opr[0] < 4; opr[0]++) { //第一个操作的结果
for(opr[1] = 0; opr[1] < 4; opr[1]++) { // 第二个操作的结果
for(opr[2] = 0; opr[2] < 4; opr[2]++) { // 第三个操作的结果
// 计算123操作带来的影响
int sum = 0;
memcpy(tempClock, myClock, sizeof(myClock));
tempClock[0] += (opr[0] + opr[1]) % 4;//处理A
tempClock[1] += (opr[0] + opr[1] + opr[2]) % 4;//处理B
tempClock[2] += (opr[1] + opr[2]) % 4;//处理C
tempClock[3] += opr[0] % 4;//处理D
tempClock[4] += (opr[0] + opr[2]) % 4;//处理E
tempClock[5] += opr[2] % 4;//处理F
// 计算456操作的次数
opr[3] = (4 - (tempClock[0] % 4)) % 4;//4操作影响A，所以A差几次，4就操作几次
opr[4] = (4 - (tempClock[1] % 4)) % 4;//5操作影响B，所以B差几次，5就操作几次
opr[5] = (4 - (tempClock[2] % 4)) % 4;//6操作影响C，所以C差几次，6就操作几次
// 计算456操作的影响
tempClock[3] += (opr[3] + opr[4]) % 4;
tempClock[4] += opr[4] % 4;
tempClock[5] += (opr[4] + opr[5]) % 4;
tempClock[6] += opr[3] % 4;
tempClock[7] += opr[4] % 4;
tempClock[8] += opr[5] % 4;
// 计算79操作的次数
opr[6] = (4 - (tempClock[3] % 4)) % 4;
opr[8] = (4 - (tempClock[5] % 4)) % 4;
// 79操作影响
tempClock[4] += (opr[6] + opr[8]) % 4;
tempClock[6] += opr[6] % 4;
tempClock[7] += (opr[6] + opr[8]) % 4;
tempClock[8] += opr[8] % 4;
if((tempClock[4] % 4) == 0 && (((tempClock[6] % 4) == (tempClock[7] % 4)) && ((tempClock[7] % 4) == (tempClock[8]) % 4))) {
opr[7] = (4 - (tempClock[6] % 4)) % 4;
for(i = 0; i < 9; i++) {
sum += opr[i];
}
if(sum < minSum) {
memcpy(minArr, opr, sizeof(opr));
minSum = sum;
}
}
}
}
}
for(i = 0; i < 9; i++) {
for(j = 0; j < minArr[i]; j++) {
cout << i + 1 << " ";
}
}
cout << endl;
return 0;
}
#include <bits/stdc++.h>
using namespace std;
int main(){
int miniArr[10]={0};//每种操作最少次数
int miniSum=9999;//最少 操作数
int myClock[10];//初始时间
int tempClock[10];//过程时间
int opr[10]={0};//操作数组，下标为1代表1操作
for(int i=1;i<=9;i++){
cin>>myClock[i];
tempClock[i]=myClock[i];
}
for(opr[1]=0;opr[1]<4;opr[1]++){
for(opr[2]=0;opr[2]<4;opr[2]++){
for(opr[3]=0;opr[3]<4;opr[3]++){
memcpy(tempClock,myClock,sizeof(myClock));
int sum=0;
//计算123操作带来的影响
tempClock[1]= tempClock[1]+(opr[1]+opr[2])%4;//A
tempClock[2]= tempClock[2]+(opr[1]+opr[2]+opr[3])%4;//B
tempClock[3]= tempClock[3]+(opr[2]+opr[3])%4;//C
tempClock[4]= tempClock[4]+opr[1]%4;//D
tempClock[5]= tempClock[5]+(opr[2]+opr[3])%4;//E
tempClock[6]= tempClock[6]+opr[3]%4;//F
//计算456的操作次数
opr[4]= (4- tempClock[1]%4)%4;
opr[5]= (4- tempClock[2]%4)%4;
opr[6]= (4- tempClock[3]%4)%4;
//计算456操作带来的影响
tempClock[4]=tempClock[4]+(opr[4]+opr[5])%4;//D
tempClock[5]=tempClock[5]+opr[5]%4;//E
tempClock[6]=tempClock[6]+(opr[3]+opr[5])%4;//F
tempClock[7]=tempClock[7]+opr[4]%4;//G
tempClock[8]=tempClock[8]+opr[5]%4;//H
tempClock[9]=tempClock[9]+opr[6]%4;//I
//计算79的操作次数
opr[7]= (4- tempClock[4]%4)%4;
opr[9]= (4- tempClock[6]%4)%4;
//计算79操作带来的影响
tempClock[5]=tempClock[5]+(opr[7]+opr[9])%4;//E
tempClock[7]=tempClock[7]+opr[7]%4;//G
tempClock[8]=tempClock[8]+(opr[7]+opr[9])%4;//H
tempClock[9]=tempClock[9]+opr[9]%4;//I
if(tempClock[5]%4==0 && tempClock[7]%4==tempClock[8]%4 && tempClock[8]%4==tempClock[9]%4){
//计算8的操作次数
opr[8]= (4- tempClock[7]%4)%4;
for(int i=1;i<=9;i++){
sum+=opr[i];
}
if(sum<miniSum){
memcpy(miniArr,opr,sizeof(opr));
miniSum=sum;
}
}
}
}
}
for(int i=1;i<=9;i++){
for(int j=0;j<miniArr[i];j++){
cout<<i<<" ";
}
}
cout<<endl;
return 0;
}