- 总时间限制:
- 1000ms
- 内存限制:
- 65536kB
- 描述
-
有9个时钟，排成一个3*3的矩阵。
|-------| |-------| |-------|
| | | | | | |
|---O | |---O | | O |
| | | | | |
|-------| |-------| |-------|
A B C |-------| |-------| |-------|
| | | | | |
| O | | O | | O |
| | | | | | | | |
|-------| |-------| |-------|
D E F |-------| |-------| |-------|
| | | | | |
| O | | O---| | O |
| | | | | | | |
|-------| |-------| |-------|
G H I
(图 1)现在需要用最少的移动，将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 解题思路：9重循环枚举
#include <iostream> using namespace std; int main()
{
int clock[];
for (int i = ; i <= ; ++i)
cin >> clock[i]; int minCnt = ; //保存拨动的最小次数
int i1, i2, i3, i4, i5, i6, i7, i8, i9;
int result[];
for (i1 = ; i1 <= ; ++i1)
for (i2 = ; i2 <= ; ++i2)
for (i3 = ; i3 <= ; ++i3)
for (i4 = ; i4 <= ; ++i4)
for (i5 = ; i5 <= ; ++i5)
for (i6 = ; i6 <= ; ++i6)
for (i7 = ; i7 <= ; ++i7)
for (i8 = ; i8 <= ; ++i8)
for (i9 = ; i9 <= ; ++i9)
{
if ((i1 + i2 + i4 + clock[]) % == &&
(i1 + i2 + i3 + i5 + clock[]) % == &&
(i2 + i3 + i6 + clock[]) % == &&
(i1 + i4 + i5 + i7 + clock[]) % == &&
(i1 + i3 + i5 + i7 + i9 + clock[]) % == &&
(i3 + i5 + i6 + i9 + clock[]) % == &&
(i4 + i7 + i8 + clock[]) % == &&
(i5 + i7 + i8 + i9 + clock[]) % == &&
(i6 + i8 + i9 + clock[]) % == )
{
int sum = i1 + i2 + i3 + i4 + i5 + i6 + i7 + i8 + i9;
if (sum < minCnt) //如果当前拨动的次数小于最小拨动次数
{
minCnt = sum;
result[] = i1;
result[] = i2;
result[] = i3;
result[] = i4;
result[] = i5;
result[] = i6;
result[] = i7;
result[] = i8;
result[] = i9;
}
}
} for (int i = ; i <= ; ++i)
for (int j = ; j <= result[i]; ++j)
cout << i << ' '; return ;
}