OpenOJ-P1166:拨钟问题[枚举]

题目

题目链接
有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 

思路

难得有一个中文的题面，这个题目是北京大学Mooc枚举部分的课后习题，所以我们先考虑枚举的思路。
题目要处理的时钟一共有9个，对每个时钟的操作情况各有三种，故一共有3^9=19683种情况，显然枚举思想是可以完成任务的。
接下来就要考虑对枚举程序的设计了，我们要进行的是对这9个钟的操作次数进行枚举，这里采用了多重循环来实现枚举，题目中要求的事求出最短路径，实际上在循环进行时，操作总数是从小到大增长的，故求出的第一个可行解就为最短路径。

代码

#include <iostream>
#include <cstdio>

using namespace std;

int clk[10];
int tmp[10]; //操作时在临时变量里操作，不要改变原始状态

int main(void)
{
    for(int i = 0; i < 9; ++i)
        scanf("%d", &clk[i]);
    for(int i1 = 0; i1 <= 3; ++i1)
        for(int i2 = 0; i2 <= 3; ++i2)
        for(int i3 = 0; i3 <= 3; ++i3)
        for(int i4 = 0; i4 <= 3; ++i4)
        for(int i5 = 0; i5 <= 3; ++i5)
        for(int i6 = 0; i6 <= 3; ++i6)
        for(int i7 = 0; i7 <= 3; ++i7)
        for(int i8 = 0; i8 <= 3; ++i8)
        for(int i9 = 0; i9 <= 3; ++i9) {
            tmp[0] = (clk[0]+i1+i2+i4)%4;
            tmp[1] = (clk[1]+i1+i2+i3+i5)%4;
            tmp[2] = (clk[2]+i2+i3+i6)%4;
            tmp[3] = (clk[3]+i1+i4+i5+i7)%4;
            tmp[4] = (clk[4]+i1+i3+i5+i7+i9)%4;
            tmp[5] = (clk[5]+i3+i6+i5+i9)%4;
            tmp[6] = (clk[6]+i4+i7+i8)%4;
            tmp[7] = (clk[7]+i5+i7+i8+i9)%4;
            tmp[8] = (clk[8]+i6+i8+i9)%4;
            if(tmp[0]+tmp[1]+tmp[2]+tmp[3]+tmp[4]+tmp[5]+tmp[6]+tmp[7]+tmp[8] == 0) {
                for(int i = 0; i < i1; ++i) printf("1 ");
                for(int i = 0; i < i2; ++i) printf("2 ");
                for(int i = 0; i < i3; ++i) printf("3 ");
                for(int i = 0; i < i4; ++i) printf("4 ");
                for(int i = 0; i < i5; ++i) printf("5 ");
                for(int i = 0; i < i6; ++i) printf("6 ");
                for(int i = 0; i < i7; ++i) printf("7 ");
                for(int i = 0; i < i8; ++i) printf("8 ");
                for(int i = 0; i < i9; ++i) printf("9 ");
            }
        }
    return 0;
}