简答题
偏难
#7140
拨钟问题 有9个时钟,排成一个3*3的矩阵。 现在需要用最少的移动,将9个时钟的指针都拨到12点的位置。共允许有9种不同的移动。如下表所示,每个移动会将若干个时…
拨钟问题
有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
输入格式
9个整数,表示各时钟指针的起始位置,相邻两个整数之间用单个空格隔开。其中,0=12点、1=3点、2=6点、3=9点。
输出格式
输出一个最短的移动序列,使得9个时钟的指针都指向12点。按照移动的序号从小到大输出结果。相邻两个整数之间用单个空格隔开。(数据保证答案唯一)
样例输入
3 3 0 2 2 2 2 1 2
样例输出
4 5 8 9
答案与解析
正确答案:<pre class="brush:cpp;toolbar:false">/*
9个操作,每个操作最多做3次
因为超过3次之后就回到原位置了。
所以可以9个for循环枚举每个操作
设置i[10]数组,i[1]~i[9]代表1到9这个操作
A始终受操作1,2,4的影响
时钟初始保存在数组mp[9]里
那么mp[1]的变化就是mp[1]+i[1]+i[2]+i[4]在对4取余
其余时钟变化也可以顺势表示出来
全部加起来求和如果等于0就全部归位了
全部等于0只能是9个0加起来没有别的情况因为不存在负数
*/
#include <bits/stdc++.h>
using namespace std;
int n, mp[10], i[10];
int main() {
for (int i = 1; i <= 9; i++) {
cin >> mp[i];
}
for (i[1] = 0; i[1] < 4; i[1]++) {
for (i[2] = 0; i[2] < 4; i[2]++) {
for (i[3] = 0; i[3] < 4; i[3]++) {
for (i[4] = 0; i[4] < 4; i[4]++) {
for (i[5] = 0; i[5] < 4; i[5]++) {
for (i[6] = 0; i[6] < 4; i[6]++) {
for (i[7] = 0; i[7] < 4; i[7]++) {
for (i[8] = 0; i[8] < 4; i[8]++) {
for (i[9] = 0; i[9] < 4; i[9]++) {
int sum = 0;
sum += (mp[1] + i[1] + i[2] + i[4]) %
4; // 时钟A受操作1和2和4的影响其余同理
sum += (mp[2] + i[1] + i[2] + i[3] + i[5]) % 4;
sum += (mp[3] + i[2] + i[3] + i[6]) % 4;
sum += (mp[4] + i[1] + i[4] + i[5] + i[7]) % 4;
sum += (mp[5] + i[1] + i[3] + i[5] + i[7] + i[9]) % 4;
sum += (mp[6] + i[3] + i[5] + i[6] + i[9]) % 4;
sum += (mp[7] + i[4] + i[7] + i[8]) % 4;
sum += (mp[8] + i[5] + i[7] + i[8] + i[9]) % 4;
sum += (mp[9] + i[6] + i[8] + i[9]) % 4;
if (sum == 0) {
for (int x = 1; x <= 9; x++) {
while (i[x]--)
cout << x << " ";
}
return 0;
}
}
}
}
}
}
}
}
}
}
return 0;
}</pre>
这道题暂未补解析。