002:拨钟问题

|-------|    |-------|    |-------|
|       |    |       |    |   |   |
|---O   |    |---O   |    |   O   |
|       |    |       |    |       |
|-------|    |-------|    |-------|
    A            B            C    

|-------|    |-------|    |-------|
|       |    |       |    |       |
|   O   |    |   O   |    |   O   |
|   |   |    |   |   |    |   |   |
|-------|    |-------|    |-------|
    D            E            F    

|-------|    |-------|    |-------|
|       |    |       |    |       |
|   O   |    |   O---|    |   O   |
|   |   |    |       |    |   |   |
|-------|    |-------|    |-------|
    G            H            I    
(图 1)

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

3 3 0 
2 2 2 
2 1 2 

#include <cstdio>
#include <cstring>
#include <iostream>

int mode[9];
int minstepcount=36;
char minstep[36];

int initmode()
{
    char *modestr[]={
            "ABDE", "ABC", "BCEF",
            "ADG", "BDEFH", "CFI",
            "DEGH", "GHI", "EFHI"
    };
    for (int i=0; i<9; i++)
    {
        mode[i]=0;
        for (char c='A'; c<='I'; c++)
        {
            mode[i] *= 10;
            if (strchr(modestr[i], c))
                mode[i] += 1;
        }
    }
    return 0;
}

int data2code(int data[])
{
    int result = 0;
    for (int i=0; i<9; i++)
        result = result * 10 + data[i];

    return result;
}

int code2data(int data[], int code)
{
    for (int i=8; i>=0; i--)
    {
        data[i] = code % 10;
        code /= 10;
    }
    return 0;
}

int change(int start, int modenum, int loop)
{
    int resultdata[9], modedata[9];
    code2data(modedata, modenum);
    code2data(resultdata, start);
    for (int i=0; i<loop; i++)
    {
        for (int j=0; j<9; j++)
            resultdata[j] = (resultdata[j]+modedata[j])%4;
    }
    return data2code(resultdata);
}

int dotry(int start, int step[], int n)
{
    if (start==0)
    {
        int stepcount=0;
        for (int i=0; i<n; i++)
        {
            stepcount +=step[i];

            /*for (int j=0; j<step[i]; j++)
                printf("%d ", i+1);
            */
        }
        if (stepcount<minstepcount)
        {
            minstepcount=stepcount;
            minstep[0]='\0';
            char tmp[2];
            tmp[1]='\0';
            for (int i=0; i<n; i++)
                for (int j=0; j<step[i]; j++)
                {
                    tmp[0]='0'+i+1;
                    strcat(minstep, tmp);
                }

        }

        return 0;
    }

    if (n==9)
    {
        return -1;
    }

    for (int i=0; i<4; i++)
    {
        step[n]=i;
        int result=change(start, mode[n], i);
        dotry(result, step, n+1);
    }
}

int main()
{
    int start;
    int data[9], step[9]={0};
    initmode();

    for (int i=0; i<9; i++)
        scanf("%d", &data[i]);
    start = data2code(data);

    dotry(start, step, 0);

    printf("%c", minstep[0]);
    for (int i=1; i<strlen(minstep); i++)
        printf(" %c", minstep[i]);
    printf("\n");
    return 0;
}