Description

考虑将如此安排在一个 3 x3 行列中的九个时钟:

 |-------|    |-------|    |-------|
 |       |    |       |    |   |   |
 |---O   |    |---O   |    |   O   |
 |       |    |       |    |       |
 |-------|    |-------|    |-------|
     A            B            C
 |-------|    |-------|    |-------|
 |       |    |       |    |       |
 |   O   |    |   O   |    |   O   |
 |   |   |    |   |   |    |   |   |
 |-------|    |-------|    |-------|
     D            E            F
 |-------|    |-------|    |-------|
 |       |    |       |    |       |
 |   O   |    |   O---|    |   O   |
 |   |   |    |       |    |   |   |
 |-------|    |-------|    |-------|
     G            H            I

目标要找一个最小的移动顺序将所有的指针指向12点。下面原表格列出了9种不同的旋转指针的方法,每一种方法都叫一次移动。选择1到9号移动方法,将会使在表格中对应的时钟的指针顺时针旋转90度。

移动方法  受影响的时钟
1                ABDE
2                ABC
3                BCEF
4                ADG
5                BDEFH
6               CFI
7               DEGH
8               GHI
9               EFHI

Input

第1-3行: 三个空格分开的数字,每个数字表示一个时钟的初始时间,3,6,9,12。数字的含意和上面第一个例子一样。

Output

单独的一行包括一个用空格分开的将所有指针指向12:00的最短移动顺序的列表。 如果有多种方案,输出那种使其连接起来数字最小的方案。(举例来说5 2 4 6 < 9 3 1 1)。

Sample Input

9 9 12
6 6 6
6 3 6

Sample Output

4 5 8 9

 解题思路:DFS。求出每种移动方法的次数,为0即没有使用该种移动方法,最多为3次,因为四次之后就等同于初始状态。似乎使用位运算会很强大,只是自己不会用。

收获:又学到一种处理输出格式的方法,char *c;c=””或者c=” “来解决输出值与值之间的空格!

——————–我是华丽丽的分割线,哈哈~~————————————————-

#include <stdio.h>

int time[10],ans[9],res[9],min;
int change[9][5]={{0,1,3,4},{0,1,2},{1,2,4,5},{0,3,6},{1,3,4,5,7},{2,5,8},{3,4,6,7},{6,7,8},{4,5,7,8}};
int len[9]={4,3,4,3,5,3,4,3,4};

void solve(int k){
    int i,t;
    if(k==9){                //移动方法的次序。
        for(i=0;i<9;i++){
            if(time[i])
                return ;
        }//全归零
        t=0;
        for(i=0;i<9;i++)
            t+=res[i];
        if(min==0 || t<min){
            min=t;
            for(i=0;i<9;i++)
                ans[i]=res[i];
        }
        return ;
    }
    for(t=0;t<4;t++){        //移动次数
        res[k]=t;
        for(i=0;i<len[k];i++){
            time[change[k][i]]+=3*t;
            time[change[k][i]]%=12;
        }
        solve(k+1);
        for(i=0;i<len[k];i++){
            time[change[k][i]]+=9*t;
            time[change[k][i]]%=12;
        }
    }
}

//这个是验证1~9的影响的方格的字母A~I对应的数字0~8是否有错。事实证明,手写的果断错了一个,以至于WA一次。
void init(){
    char c[10];
    int i;
    while(gets(c)){
        for(i=0;c[i];i++)
            printf(“%d”,c[i]-‘A’);
        printf(“\n”);
    }
}

int main(){
    while(scanf(“%d”,&time[0])!=EOF){
        int i,j;
        char *c;
        for(i=1;i<9;i++){
            scanf(“%d”,&time[i]);
            time[i]%=12;
            ans[i]=res[i]=0;
        }
        time[0]%=12;
        min=0;
        solve(0);
        c=””;
        for(i=0;i<9;i++){
            for(j=0;j<ans[i];j++){
                printf(“%s%d”,c,i+1);
                c=” “;
            }
        }
        printf(“\n”);
    }
    return 0;
}

发表评论

电子邮件地址不会被公开。

Post Navigation