IOI'94 The Clocks ( Binary Enumeration )

PEG Judge - IOI '94 - The Clocks
一開始想用 PFS，後來想一想沒有權重可以直接BFS，寫完丟出去才發現 RE / TLE。。

// Will TLE O( ( ans.size() ) ! )
#include <bits/stdc++.h>
using namespace std;

struct State{
    int clk[ 9 ];
    State(){}
    void read(){
        for(int i = 0; i < 9; ++i){
            int t; scanf("%d", &t);
            t /= 3;
            t %= 4; // t: [ 0, 3 ]
            clk[ i ] = t;
        }
    }
    void clk90(int id){
        clk[ id ] = ( clk[ id ] + 1 ) % 4;
    }
    void dial(int op){
        if( op == 1 )
            clk90( 0 ), clk90( 1 ), clk90( 3 ), clk90( 4 );
        if( op == 2 )
            clk90( 0 ), clk90( 1 ), clk90( 2 );
        if( op == 3 )
            clk90( 1 ), clk90( 2 ), clk90( 4 ), clk90( 5 );
        if( op == 4 )
            clk90( 0 ), clk90( 3 ), clk90( 6 );
        if( op == 5 )
            clk90( 1 ), clk90( 3 ), clk90( 4 ), clk90( 5 ), clk90( 7 );
        if( op == 6 )
            clk90( 2 ), clk90( 5 ), clk90( 8 );
        if( op == 7 )
            clk90( 3 ), clk90( 4 ), clk90( 6 ), clk90( 7 );
        if( op == 8 )
            clk90( 6 ), clk90( 7 ), clk90( 8 );
        if( op == 9 )
            clk90( 4 ), clk90( 5 ), clk90( 7 ), clk90( 8 );
    }
    bool done(){
        for(int i = 0; i < 9; ++i)
            if( clk[ i ] )
                return false;
        return true;
    }
    bool operator < (const State &oth) const{
        for(int i = 0; i < 9; ++i){
            if( clk[ i ] != oth.clk[ i ] )
                return clk[ i ] < oth.clk[ i ];
            return true;
        }
    }
    void print(){
        for(int i = 0; i < 9; ++i)
            printf("%d%c", clk[ i ], i == 8 ? '\n' : ' ');
    }
} s0;

struct Seq{
    vector<int> vec;
    Seq(){ vec.clear(); }
    void print(){
        for(int i = 0; i < vec.size(); ++i)
            printf("%d%c", vec[ i ], i == vec.size() - 1 ? '\n' : ' ');
    }
};

struct SeqState{
    Seq seq;
    State state;
    SeqState(){}
    SeqState(Seq _seq, State _state): seq( _seq ), state( _state ){}
};

void solve(){
    queue< SeqState > que;
    que.push( SeqState( Seq(), s0 ) );
    set< State > vis;
    vis.insert( s0 );
    while( !que.empty() ){
        Seq seq = que.front().seq;
        State state = que.front().state;
        que.pop();
        state.print();
        if( state.done() ){
            seq.print();
            return;
        }
        for(int i = 1; i <= 9; ++i){
            State ns; // memcpy( &ns, &state, sizeof(ns) );
            ns = state;
            ns.dial( i );
            if( vis.count( ns ) ) continue;
            vis.insert( ns );
            Seq nseq; // memcpy( &nseq, &seq, sizeof(nseq) );
            nseq = seq;
            nseq.vec.push_back( i );
            que.push( SeqState( nseq, ns ) );
        }
    }
}

int main(){
    s0.read();
    solve();
    return 0;
}

因為事實上這個操作序列是可以長達 20以上的，例如
input:
12 12 12 12 12 12 12 12 9
output:
2 2 3 3 3 4 4 5 5 5 6 6 6 7 7 7 8 8 8 9 9 9
而這種無腦搜索考慮了排列，所以階層級的 20! > 1e18真是天文數字，而且還沒 TLE就已經 MLE了。注意到這些操作之間是不會相互影響的且順序是沒有差別的，因此事實上會導致不同結果的操作數只有 4 ^ 9種，每個盤面都只能選擇 不轉、90、180、270度其中一個。為了方便枚舉，我將每個盤面用 2個位元表示，所以 9個盤面用 18個位元表示。枚舉所有狀態並嘗試，如果符合要求就更新答案。

#include <bits/stdc++.h>
using namespace std;

struct State{
    int clk[ 9 ];
    State(){}
    void read(){
        for(int i = 0; i < 9; ++i){
            int t; scanf("%d", &t);
            t /= 3;
            t %= 4; // t: [ 0, 3 ]
            clk[ i ] = t;
        }
    }
    void clk90(int id){
        clk[ id ] = ( clk[ id ] + 1 ) % 4;
    }
    void dial(int op){
        if( op == 1 )
            clk90( 0 ), clk90( 1 ), clk90( 3 ), clk90( 4 );
        if( op == 2 )
            clk90( 0 ), clk90( 1 ), clk90( 2 );
        if( op == 3 )
            clk90( 1 ), clk90( 2 ), clk90( 4 ), clk90( 5 );
        if( op == 4 )
            clk90( 0 ), clk90( 3 ), clk90( 6 );
        if( op == 5 )
            clk90( 1 ), clk90( 3 ), clk90( 4 ), clk90( 5 ), clk90( 7 );
        if( op == 6 )
            clk90( 2 ), clk90( 5 ), clk90( 8 );
        if( op == 7 )
            clk90( 3 ), clk90( 4 ), clk90( 6 ), clk90( 7 );
        if( op == 8 )
            clk90( 6 ), clk90( 7 ), clk90( 8 );
        if( op == 9 )
            clk90( 4 ), clk90( 5 ), clk90( 7 ), clk90( 8 );
    }
    bool done(){
        for(int i = 0; i < 9; ++i)
            if( clk[ i ] )
                return false;
        return true;
    }
    void print(){
        for(int i = 0; i < 9; ++i)
            printf("%d%c", clk[ i ], i == 8 ? '\n' : ' ');
    }
} s0;

struct Seq{
    vector<int> vec;
    Seq(){ vec.clear(); }
    bool operator < (const Seq &oth) const{
        if( vec.size() != oth.vec.size() )
            return vec.size() < oth.vec.size();
        for(int i = 0; i < vec.size(); ++i)
            if( vec[ i ] != oth.vec[ i ] )
                return vec[ i ] < oth.vec[ i ];
        return true;
    }
    void print(){
        for(int i = 0; i < vec.size(); ++i)
            printf("%d%c", vec[ i ], i == vec.size() - 1 ? '\n' : ' ');
    }
};

void solve(){
    assert( !s0.done() );
    Seq ans;
    for(int S = 1; S < ( 1 << 18 ); ++S){
        State z = s0;
        Seq seq;
        for(int i = 0; i < 9; ++i){
            int t = ( S >> ( i * 2 ) ) % 4;
            for(int j = 0; j < t; ++j){
                z.dial( i + 1 );
                seq.vec.push_back( i + 1 );
            }
        }
        if( z.done() ){
            if( ans.vec.empty() || seq < ans )
                ans = seq;
        }
    }
    ans.print();
}

int main(){
    s0.read();
    solve();
    return 0;
}