Skip to content

11047: 【原1047】The Clocks

题目

题目描述

author: USACO 原OJ链接:https://acm.sjtu.edu.cn/OnlineJudge-old/problem/1047

Description

Consider nine clocks arranged in a 3x3 array thusly:

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

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

|-------|    |-------|    |-------|
|       |    |       |    |       |
|   O   |    |   O---|    |   O   |
|   |   |    |       |    |   |   |
|-------|    |-------|    |-------|
    G            H            I

The goal is to find a minimal sequence of moves to return all the dials to 12 o'clock. Nine different ways to turn the dials on the clocks are supplied via a table below; each way is called a move. Select for each move a number 1 through 9 which will cause the dials of the affected clocks (see next table) to be turned 90 degrees clockwise.

Move Affected clocks
---- ---------------
1    ABDE
2    ABC
3    BCEF
4    ADG
5    BDEFH
6    CFI
7    DEGH
8    GHI
9    EFHI

Example

Each number represents a time according to following table:

9 9 12       9 12 12       9 12 12        12 12 12      12 12 12
6 6 6  5 ->  9  9  9  8->  9  9  9  4 ->  12  9  9  9-> 12 12 12
6 3 6        6  6  6       9  9  9        12  9  9      12 12 12

[But this might or might not be the `correct' answer; see below.]

Input Format

Lines 1-3: Three lines of three space-separated numbers; each number represents the start time of one clock, 3, 6, 9, or 12. The ordering of the numbers corresponds to the first example above.

Output Format

A single line that contains a space separated list of the shortest sequence of moves (designated by numbers) which returns all the clocks to 12:00.

If there is more than one solution, print the one which gives the lowest number when the moves are concatenated (e.g., 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

Hint

Notice that the order in which we apply moves is irrelevant, and that applying a move four times is the same as applying it not at all.

Thus there are only \(4^9 = 262144\) move sequences that need to be tried, so we might as well just try them all.

We don't generate them shortest first, but looking at sequences of the same length, we generate the lesser ones before the greater ones, so we only need to keep track of the shortest working sequence we've found.

Limits

Time limit: 1000ms, memory limit: 30000kb.

FineArtz's solution

/* The Clocks */
#include <iostream>
using namespace std;

int a[10], ans[10] = {0}, t[10] = {0}, l = 40;
initializer_list<int> imp[10] = {
    {0},
    {1, 2, 4, 5},
    {1, 2, 3},
    {2, 3, 5, 6},
    {1, 4, 7},
    {2, 4, 5, 6, 8},
    {3, 6, 9},
    {4, 5, 7, 8},
    {7, 8, 9},
    {5, 6, 8, 9}};

inline void rotate(int a[10], int x, initializer_list<int> il){
    for (int i : il){
        a[i] = (a[i] + 3 * x) % 12;
    }
}

void work(int t[10]){
    int len = 0, b[10];
    for (int i = 1; i <= 9; ++i)
        b[i] = a[i];
    for (int i = 1; i <= 9; ++i){
        if (t[i])
            ++len;
        rotate(b, t[i], imp[i]);
    }
    for (int i = 1; i <= 9; ++i)
        if (b[i])
            return;
    if (len < l){
        l = len;
        for (int i = 1; i <= 9; ++i)
            ans[i] = t[i];
    }
}

int main(){
    for (int i = 1; i <= 9; ++i){
        cin >> a[i];
        a[i] %= 12;
    }
//    t[4] = t[5] = t[8] = t[9] = 1;
//    work(t);
    for (int i = 0; i < 262144; ++i){
        work(t);
        ++t[9];
        int j = 9;
        while (t[j] == 4){
            t[j] = 0;
            ++t[--j];
        }
    }
    for (int i = 1; i <= 9; ++i)
        for (int j = 1; j <= ans[i]; ++j)
            cout << i << ' ';
    cout << endl;
    return 0;
}

ligongzzz's solution

#include <iostream>
#include <vector>
#include <queue>
using namespace std;

vector<vector<int>> mdata = {
    {1,2,4,5},
    {1,2,3},
    {2,3,5,6},
    {1,4,7},
    {2,4,5,6,8},
    {3,6,9},
    {4,5,7,8},
    {7,8,9},
    {5,6,8,9}
};

vector<int> vdata(10);

class clock {
public:
    int ttime[10] = { 0 };
    int last = 0;
};

queue<clock> qdata;

bool check(const clock& cur_time) {
    for (int i = 1; i <= 9; ++i) {
        if (i != 12)
            return false;
    }

    return true;
}

void bfs(const clock& cur_time) {
    for (int i = 1; i <= 9; ++i) {
        qdata.push(cur_time);
    }

    while (!qdata.empty()) {

    }
}


int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);

    for (int i = 1; i <= 9; ++i)
        cin >> vdata[i];



    return 0;
}

yyong119's solution

#include <iostream>
 
using namespace std;
int data[4][4]={0},mina=1000,answer[1000],way[1000],number[10]={0};
void work(int ii)
{
    if (ii==1)
    {
        data[1][1]=(data[1][1]+3)%12;
        data[1][2]=(data[1][2]+3)%12;
        data[2][1]=(data[2][1]+3)%12;
        data[2][2]=(data[2][2]+3)%12;
    }
    else if (ii==2)
    {
        data[1][1]=(data[1][1]+3)%12;
        data[1][2]=(data[1][2]+3)%12;
        data[1][3]=(data[1][3]+3)%12;
    }
    else if (ii==3)
    {
        data[1][2]=(data[1][2]+3)%12;
        data[1][3]=(data[1][3]+3)%12;
        data[2][2]=(data[2][2]+3)%12;
        data[2][3]=(data[2][3]+3)%12;
    }
    else if (ii==4)
    {
        data[1][1]=(data[1][1]+3)%12;
        data[2][1]=(data[2][1]+3)%12;
        data[3][1]=(data[3][1]+3)%12;
    }
    else if (ii==5)
    {
        data[1][2]=(data[1][2]+3)%12;
        data[2][1]=(data[2][1]+3)%12;
        data[2][2]=(data[2][2]+3)%12;
        data[2][3]=(data[2][3]+3)%12;
        data[3][2]=(data[3][2]+3)%12;
    }
    else if (ii==6)
    {
        data[1][3]=(data[1][3]+3)%12;
        data[2][3]=(data[2][3]+3)%12;
        data[3][3]=(data[3][3]+3)%12;
    }
    else if (ii==7)
    {
        data[2][1]=(data[2][1]+3)%12;
        data[2][2]=(data[2][2]+3)%12;
        data[3][1]=(data[3][1]+3)%12;
        data[3][2]=(data[3][2]+3)%12;
    }
    else if (ii==8)
    {
        data[3][1]=(data[3][1]+3)%12;
        data[3][2]=(data[3][2]+3)%12;
        data[3][3]=(data[3][3]+3)%12;
    }
    else if (ii==9)
    {
        data[2][2]=(data[2][2]+3)%12;
        data[2][3]=(data[2][3]+3)%12;
        data[3][2]=(data[3][2]+3)%12;
        data[3][3]=(data[3][3]+3)%12;
    }
}
void dfssearch(int jj)
{
    int iii,jjj;
    bool ok=true;
    for (iii=1;iii<=3;iii++) for (jjj=1;jjj<=3;jjj++) if (data[iii][jjj]!=0) ok=false;
    if (ok && jj-1<mina)
    {
        mina=jj-1;
        for (iii=1;iii<=mina;iii++) answer[iii]=way[iii];
    }
    else if (!ok && jj-1<mina)
    {
        for (iii=way[jj-1];iii<=9;iii++)
        {
            if (number[iii]==3) continue;
            work(iii);
            number[iii]++;
            way[jj]=iii;
            dfssearch(jj+1);
            work(iii);
            work(iii);
            work(iii);
            number[iii]--;
        }
    }
}
int main()
{
 
    int i,j;
    for (i=1;i<=3;i++)
    for (j=1;j<=3;j++)
    {
        cin >> data[i][j];
        if (data[i][j]==12) data[i][j]=0;
    }
    way[0]=1;
    dfssearch(1);
    for (i=1;i<=mina-1;i++) cout << answer[i] << ' ';
    cout << answer[mina];
    return 0;
}