usaco6.5.4 The Clocks

一 原题

The Clocks
IOI'94 - Day 2
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.

MoveAffected clocks
1ABDE
2ABC
3BCEF
4ADG
5BDEFH
6CFI
7DEGH
8GHI
9EFHI
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.]

PROGRAM NAME: clocks
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.
SAMPLE INPUT (file clocks.in)
9 9 12
6 6 6
6 3 6
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 OUTPUT (file clocks.out)
4 5 8 9


二 分析

没啥好说的。。BFS


三 代码

运行结果:

USER: Qi Shen [maxkibb3]
TASK: clocks
LANG: C++

Compiling...
Compile: OK

Executing...
   Test 1: TEST OK [0.000 secs, 5280 KB]
   Test 2: TEST OK [0.000 secs, 5280 KB]
   Test 3: TEST OK [0.014 secs, 6072 KB]
   Test 4: TEST OK [0.042 secs, 6600 KB]
   Test 5: TEST OK [0.056 secs, 6864 KB]
   Test 6: TEST OK [0.196 secs, 7088 KB]
   Test 7: TEST OK [0.238 secs, 7392 KB]
   Test 8: TEST OK [0.224 secs, 5780 KB]
   Test 9: TEST OK [0.224 secs, 5812 KB]

All tests OK.

YOUR PROGRAM ('clocks') WORKED FIRST TIME! That's fantastic -- and a rare thing. Please accept these special automated congratulations.


AC代码:

/*
ID:maxkibb3
LANG:C++
PROB:clocks
*/

#include cstdio
#include vector
#include queue

using namespace std;

// #define local

const short action[9][9] = {
    {1, 1, 0, 1, 1, 0, 0, 0, 0},
    {1, 1, 1, 0, 0, 0, 0, 0, 0},
    {0, 1, 1, 0, 1, 1, 0, 0, 0},
    {1, 0, 0, 1, 0, 0, 1, 0, 0},
    {0, 1, 0, 1, 1, 1, 0, 1, 0},
    {0, 0, 1, 0, 0, 1, 0, 0, 1},
    {0, 0, 0, 1, 1, 0, 1, 1, 0},
    {0, 0, 0, 0, 0, 0, 1, 1, 1},
    {0, 0, 0, 0, 1, 1, 0, 1, 1}
};

bool vis[1000000];

struct Clock {
    short t[9];
    vectorshort trace;
}st;

inline int h(const Clock c) {
    int ret = 0, base = 1;
    for(int i = 0; i  9; i++) {
        ret += c.t[i] * base;
        base *= 4;
    }
    return ret;
}

int main() {
#ifndef local
    freopen("clocks.in", "r", stdin);
    freopen("clocks.out", "w", stdout);
#endif
    for(int i = 0; i  9; i++) {
        scanf("%hd", st.t[i]);
        st.t[i] = (st.t[i] / 3) % 4;
    }
    if(h(st) == 0) return 0;

    queueClock q;
    vectorshort ans;
    q.push(st);
    vis[h(st)] = true;
    bool end = false;
    while(!q.empty()) {
        Clock hd = q.front(), nxt;
        q.pop();
        for(int i = 0; i  9; i++) {
            if(end) break;
            for(int j = 0; j  9; j++) {
                nxt.t[j] = (hd.t[j] + action[i][j]) % 4;
            }
            int hashval = h(nxt);
            if(vis[hashval]) continue;
            nxt.trace = hd.trace;
            nxt.trace.push_back(i);
            if(hashval == 0) {
                end = true;
                ans = nxt.trace;
            }
            q.push(nxt);
            vis[hashval] = true;
        }
        if(end) break;
    }

    printf("%d", ans[0] + 1);
    for(int i = 1; i  ans.size(); i++) {
        printf(" %d", ans[i] + 1);
    }
    printf("\n");

    return 0;
}


最新回复(0)
/jishu_2F9FOEJIYAAM7fgEEuofkz2WItfnvR3DQGFhvF4aOoJc_3D4858283
8 简首页